Graph-MLP--Node Classification without Message Passing in Graph
《Graph-MLP: Node Classification without Message Passing in Graph》【arxiv 2021】
最近的图神经网络（GNN）都依赖于邻接矩阵来指导特征聚合过程中邻居之间的消息传递，研究工作主要集中在强大的消息传递模块上。然而本文表明没有任何消息传递模块也是可行的。相反地，本文通过设计了一个邻近对比（NContrast）损失，通过隐式利用邻接信息来弥合 GNN 和 MLP 之间的差距。
在模型层面，Graph-MLP仅包括多层感知器、激活函数和层归一化。
模型架构
constrastive loss可以写成:
$$
\ell_i=-\log\frac{\sum_{j=1}^B\mathbf{1}{[j\neq i]}\gamma{ij}\exp\left(sim\left(\boldsymbol{z}i,\boldsymbol{z}j\right)/\tau\right)}{\sum{k=1}^B\mathbf{1}{[k\neq i]}\exp\left(sim\left(\boldsymbol{z}_i,\boldsymbol{z}_k\right)/\tau\right)}
$$
其中
sim是余弦相似度，
$$
\gamma_{ij}\begin{cases}=0,&\text{node }j \ \text{is the }r\text{-hop neighbor of node }i\
\neq0,&\text{node }j \ \text{is not the }r\text{-hop neighbor of node }i\end{cases}
$$
和
$$
hloss_{NC}=\alpha\frac1B\sum_{i=1}^B\ell_i\
loss_{final}=loss_{CE}+loss_{NC}
$$
算法解释
我们可以简化sample的过程，sim改为取向量内积。
这时候对比loss可以变为
$$
\ell=-\log\left(\frac{\sum_jA_{ij}\exp(\langle z_i,z_j\rangle)}{\sum_j(A_{ij}^c)\exp(\langle z_i,z_j\rangle)}\right)
$$
其中$A$是k-hop邻接矩阵，$A^\mathrm{c}$是A的补图。上面的loss可以分成positive和negative两个部分.。
positive的部分:
$$\ell_p=\log\left(\sum_jA_{ij}\exp(\langle z_i,z_j)\rangle\right)$$
对$\ell_p$ 求导，我们有:
$$\frac{\partial\ell_p}{\partial z_i}=\frac{1}{\sum_jA_{ij}\exp(\langle z_i,z_j\rangle)}\biggl(\sum_jA_{ij}\exp(\langle z_i,z_j\rangle)z_j\biggr)$$
对$z_i$做梯度下降，假设步长为$\eta$ ,在第t个iteration当中，我们有
$$z_{i}^{t-1/2}=z_{i}^{t}+\eta\frac{\partial\ell_{p}}{\partial z_{i}}=z_{i}^{t}+\frac{\eta}{\sum_{j}A_{ij}\exp(\langle z_{i}^{t},z_{j}^{t}\rangle)}\left(\sum_{j}A_{ij}\exp(\langle z_{i}^{t},z_{j}^{t}\rangle)z_{j}^{t}\right)$$
上式类似于一个，加了残差连接的graph attention networks。
negative部分：
$$
\begin{aligned}
&z_{i}^{t+1}=z_{i}^{t+1/2}-\eta\frac{\partial\ell_{n}}{\partial z_{i}}=z_{i}^{t+1/2} \
&-\frac{\eta}{\sum_{j}A_{j}^{c}\exp(\langle z_{i}^{t},z_{j}^{t}\rangle)}\Bigg(\sum_{j}A_{j}^{c}\exp(\langle z_{i}^{t},z_{j}^{t}\rangle)z_{j}^{t}\Bigg)
\end{aligned}
$$
是为了让k-hop不相邻的节点的representation不接近，从而避免trival solution的产生。
【1】中提到，从GNN角度上来看是对A的补图做了类似于《Beyond Low-frequency Information in Graph Convolutional Networks》当中的high-pass filter 。
存疑
参考：