1. 模型构造思路

整体思路：

message passing系模型都很难将聚集的邻居扩大，也就是多卷几层扩大感受野。一是因为聚合求平均太多层会平滑，即over-smoothing问题，本文主要关注这一问题；二是因为层数增多也会增多参数，但是这一问题可以用共享参数解决，本文重点不在此，但本文提出的方法也成功减少了参数。

message passing本质是Laplacian smoothing，message passing系GNN（如GCN等）会出现over-smoothing问题，即如果网络层数增多，各节点的嵌入都会趋于相近，就无法反映各节点的自有特征。

因此这些模型无法加深层数，只能在较近的邻居之间传播信息，限制其表示能力。但是在需要更多信息，尤其是对于边缘节点（实证结果见Appendix I）和有标签节点较少（实证结果见Figure 3和Appendix H）时，就是需要远程传播信息，所以本文提出了能够更远、更深传播信息而不over-smooth的 PPNP / APPNP 模型。

原始GCN节点之间的影响程度与随机游走分布成比例，随机游走最终会趋于稳定，所以GCN节点影响程度也会趋于相同。PageRank得分即随机游走稳定分布，会得到全图的结构信息。而使用以根节点为teleport set 的 Personalized PageRank（PPR）方法能得到各节点独有的局部结构信息，这样就能保存住各节点的独有信息。

本文提出的PPNP将predict和propagate阶段拆开，在predict阶段仅用节点特征来进行预测，在propagate阶段用PPR对预测值进行信息传递，这样能在远程传播中仍然保留节点局部信息，而且不需要过多的参数。

PPNP使PPR收敛至稳定状态。由于PPNP计算代价过高，在此基础上提出了代价较小的近似模型APPNP，只迭代有限次PPR。

2. Notation和模型介绍

2.1 notation

2.2 PPNP公式

2.3 APPNP公式

3. 详细的数学推导和证明

3.1 message passing系GNN的over-smoothing问题

就我之前对此问题的理解就很直觉，就是感受野越广，各节点邻居重叠越大，所以得到的结果就越像（就，一样的邻居嘛……）。（来自cs224w，可参考我之前撰写的笔记：cs224w（图机器学习）2021冬季课程学习笔记9 Graph Neural Networks 2: Design Space）

在本文中提到GCN本质上是Laplacian smoothing，给了两篇参考文献：

Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper Insights Into Graph Convolutional Networks for Semi-Supervised Learning. In AAAI, 2018.

Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation Learning on Graphs with Jumping Knowledge Networks. In ICML, 2018.

就我简单看了一下第一篇作者自己写的介绍：Laplacian Smoothing and Graph Convolutional Networks – Qimai’s Home，实话实说，没有看懂。就我委实没有搞懂拉普拉斯矩阵那一堆是在搞什么

然后第二篇也是提出influence score I ( x , y )的那篇论文。论文里与之相关的内容我在第一部分和3.2部分写了。

3.2 GCN收敛，RW极限，PageRank和PPR，influence score

PageRank的矩阵表达式、power iteration等可参考我之前写的博文：cs224w（图机器学习）2021冬季课程学习笔记4 Link Analysis: PageRank (Graph as Matrix)

随着GCN层数增加，influence score I ( x , y )  与RW的分布成正比，这个分布随着迭代数（层数）增加，最后会收敛到与起始节点无关的稳定状态。

RW的极限分布 π \piπ 与起始节点（根节点）无关，这个极限分布也是PageRank的结果 π。

3.3 A r w \mathbf{A}_{rw}A

3.4 附录A：证明 Π ppr \Pi_{\text{ppr}}Π

3.5 附录B：证明APPNP收敛于PPNP

还没看，待补。

4. 实验结果

还没写，待补。

5. 代码实现和复现

5.1 论文官方实现

klicperajo/ppnp: PPNP & APPNP models from “Predict then Propagate: Graph Neural Networks meet Personalized PageRank” (ICLR 2019)

还没看，待补。

5.2 PyG官方实现

APPNP类，官方文档：torch_geometric.nn — pytorch_geometric 1.7.2 documentation

源代码：torch_geometric.nn.conv.appnp — pytorch_geometric 1.7.2 documentation

他这个用MessagePassing实现的基类我就没太看懂……就是，唉，当年GCN那个怎么从矩阵拆成向量形式的我就没搞懂，这个我就更没搞懂了！

我看这个实现逻辑里面用到了 gcn_norm() 这个函数，这个我查了一下是GCNConv类里面用到的函数。GCNConv源代码在这里：torch_geometric.nn.conv.gcn_conv — pytorch_geometric 1.7.2 documentation

5.3 我自己写的复现

还没加dropout。

还没优化。

5.3.1 APPNP：dense Tensor

class APPNP_self1(torch.nn.Module):
    #参考PyG设置的参数什么的
    #就PyG设置的就是没有predict部分，所以我也把predict部分放在GNNStack里面了
    #就我想了一下，我觉得用MessagePassing类不方便，就还是用torch的Module类了
    def __init__(self,K,alpha):
        #别的参数暂时省略
        super(APPNP_self1,self).__init__()
        self.K=K
        self.alpha=alpha
    def forward(self, x, edge_index):
        #首先尝试使用dense_tensor，如果不行再转sparse_tensor
        (row, col)= edge_index
        node_num=max(row.max(),col.max())+1
        adj = torch.zeros((node_num,node_num))
        adj=adj.to(hp['device'])
        adj[row, col] = torch.ones(row.numel()).to(hp['device'])
        self_loop=torch.eye(adj.size()[0]).to(hp['device'])  #自环
        adj=adj+self_loop  #\slide{A}
        degree_vector=torch.sum(adj,dim=1).cpu()  #度矩阵
        degree_vector=1/np.sqrt(degree_vector)  #D-1/2
        degree_matrix=torch.diag(degree_vector).to(hp['device'])
        adj=torch.mm(degree_matrix,adj)
        adj=torch.mm(adj,degree_matrix)  #\hat{\slide{A}}
        H=x.clone()
        Z=x.clone()
        for k in range(self.K-1):
            Z=torch.mm(adj,Z)
            Z=Z*(1-self.alpha)
            Z=Z+self.alpha*H
        Z=torch.mm(adj,Z)
        Z=Z*(1-self.alpha)
        Z=Z+self.alpha*H
        Z=F.log_softmax(Z, dim=1)
        return Z

在CPU上跑得贼慢，在GPU上OOM了……

5.3.1 APPNP：稀疏矩阵

我用的是PyTorch的稀疏矩阵（torch.sparse），文档：torch.sparse — PyTorch 1.9.0 documentation

我参考了一下PyG和论文官方实现，PyG用的是torch_sparse，这个库他妈的没有文档就算了，GitHub项目里面代码连个注释都没有。大佬是真的牛逼，他怎么做到自己写的代码自己看得懂的？……

论文官方用的是scipy的稀疏矩阵，这个我还没有了解过。

def edge_index2sparse_tensor(edge_index,node_num):
    sizes=(node_num,node_num)
    v=torch.ones(edge_index[0].numel()).to(hp['device'])  #边数
    return torch.sparse_coo_tensor(edge_index, v, sizes)
class APPNP_self2(torch.nn.Module):    
    def __init__(self,K,alpha):
        #别的参数暂时省略
        super(APPNP_self2,self).__init__()
        self.K=K
        self.alpha=alpha
    def forward(self, x, edge_index):
        node_num=x.size()[0]
        edge_index, _ = pyg_utils.add_self_loops(edge_index,num_nodes=node_num)  #添加自环（\slide{A}）
        adj=edge_index2sparse_tensor(edge_index,node_num)  #将\slide{A}转换为稀疏矩阵
        degree_vector=torch.sparse.sum(adj,0)  #度数向量
        degree_vector=degree_vector.to_dense().cpu()
        degree_vector=1/np.sqrt(degree_vector)
        degree_matrix=torch.diag(degree_vector).to(hp['device'])
        adj=torch.sparse.mm(adj.t(),degree_matrix.t())
        adj=adj.t()
        adj=torch.mm(adj,degree_matrix)
        adj=adj.to_sparse()
        H=x.clone()
        for k in range(self.K-1):
            x=torch.mm(adj,x)
            x=x*(1-self.alpha)
            x=x+self.alpha*H
        x=torch.mm(adj,x)
        x=x*(1-self.alpha)
        x=x+self.alpha*H
        x=F.log_softmax(x, dim=1)
        return x

5.3.3 PPNP

还没写，待补。

5.4 复现实验结果对比

APPNP和C&S复现

未完待续。