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 。

存疑

参考:

【1】《Graph-MLP: 用MLP与优化优雅地超越GNN


Graph-MLP--Node Classification without Message Passing in Graph
https://lijianxiong.work/2024/20240513/
作者
LJX
发布于
2024年5月13日
许可协议