论文地址：Graph-MLP Node Classification without Message Passing in Graph
Overview
?传统GNN的相关工作都强调信息传递（message passing）的重要性，但是作者提出这不是必要的。为此作者设计了一种基于多层感知机的框架——Graph-MLP，该框架在前向传播的过程中并不涉及信息的传递，而是在计算Loss时隐式的引入邻接信息来弥补CNN和MLPs之间的差距。实验结果表明作者提出的框架相对于GNN而言具有更快的运算效率，同时在缺失边的推断场景下更具有鲁棒性（因为推断过程中不需要提供结点之间的邻接信息）。
?作者在文中所作的贡献可以概括如下：
- 提出了第一个不利用信息传递但却在图结点分类任务上取得较好性能的深度学习框架。
- 设计了一个邻居对比损失（Neighboring Contrastive Loss, NContrast Loss）来隐式的聚合图结构到结点的表示学习中。
- 在缺失邻接信息的推断情况下，还能维持较高的推断性能。
Graph-MLP模型
模型结构
?图1中展示的便是Graph-MLP模型，可知它由线性层+激活层+正则化层+Dropout层+线性层+线性层组成。其中激活函数使用的是Gelu，正则化层为Layer Norm（对每个结点的特征向量单独进行归一化）。倒数第二个线性层是用来联合邻接信息计算NContrast Loss的，而最后一个线性层是用来进行结点分类的（最后一层也会计算一个交叉熵损失）。
模型的数学形式
?Graph-MLP用数学公式描述如下：
X
(
1
)
=
D
r
o
p
o
u
t
(
L
N
(
σ
(
X
W
0
)
)
)
Z
=
X
(
1
)
W
1
Y
=
Z
W
2
\begin{aligned} \boldsymbol{X}^{(1)} & = Dropout(LN(\sigma(\boldsymbol{X}\boldsymbol{W}^0))) \\ \boldsymbol{Z} & = \boldsymbol{X}^{(1)}\boldsymbol{W}^1 \\ \boldsymbol{Y} & = \boldsymbol{Z}\boldsymbol{W}^2 \\ \end{aligned}
X(1)ZY?=Dropout(LN(σ(XW0)))=X(1)W1=ZW2?
其中
X
(
l
)
\boldsymbol{X}^{(l)}
X(l)表示第
l
l
l层的特征，
X
(
0
)
=
X
\boldsymbol{X}^{(0)}= \boldsymbol{X}
X(0)=X，即为Node Feature。
Z
\boldsymbol{Z}
Z会被用来计算NContrast Loss，而
Y
\boldsymbol{Y}
Y将用来计算分类损失。
损失函数
?正如前文提到的，Graph-MLP的损失函数由NContrast Loss + 分类损失组成。首先重点介绍下作者提出的NContrast Loss，该损失函数是为了让Graph-MLP模型能够利用图中结点的邻接信息，它借鉴了对比学习（Contrastive Learning）的思想，即在特征空间中连接的结点应该彼此接近，而不连接的结点应该相互远离。在NContrast Loss中，每个结点的
r
r
r?跳邻居被认为是正采样，其他的结点被认为是负采样。该损失函数的数学公式如下：
?
i
=
?
l
o
g
∑
j
=
1
B
1
[
j
≠
i
]
γ
i
j
exp
(
sim
(
z
i
,
z
j
)
/
τ
)
∑
k
=
1
B
1
[
k
≠
i
]
exp
(
sim
(
z
i
,
z
k
)
/
τ
)
\ell_i=-log\frac{\sum_{j=1}^{B}{\boldsymbol{1}_{[j \neq i]}\gamma_{ij}\text{exp}(\text{sim}(z_i,z_j)/ \tau)}}{\sum_{k=1}^{B}{\boldsymbol{1}_{[k \neq i]} \text{exp}(\text{sim}(z_i,z_k)/ \tau)}}
?i?=?log∑k=1B?1[k?=i]?exp(sim(zi?,zk?)/τ)∑j=1B?1[j?=i]?γij?exp(sim(zi?,zj?)/τ)?
上式中，
sim
\text{sim}
sim?表示余弦相似度，
τ
\tau
τ?表示温度参数（temperature parameter）。
γ
i
j
\gamma_{ij}
γij??表示结点
i
i
i?与结点
j
j
j?间的连接强度，其值通过规范化邻接矩阵
A
^
\hat{A}
A^?的
r
r
r??次幂来计算，计算公式如下：
γ
i
j
=
A
^
i
j
r
\gamma_{ij} = \hat{A}_{ij}^{r}
γij?=A^ijr?
γ
i
j
\gamma_{ij}
γij??为非0值当且仅当结点
j
j
j?是结点
i
i
i的
r
r
r跳邻居，即：
γ
i
j
{
≠
0
node?j?is?the?r-hop?neighbor?of?node?i
=
0
node?j?is?not?the?r-hop?neighbor?of?node?i
\gamma_{ij} \begin{cases} \neq0& \text{node j is the r-hop neighbor of node i}\\ =0& \text{node j is not the r-hop neighbor of node i} \end{cases}
γij?{?=0=0?node?j?is?the?r-hop?neighbor?of?node?inode?j?is?not?the?r-hop?neighbor?of?node?i?
而分类损失采用的是传统的交叉熵（用
l
o
s
s
C
E
loss_{CE}
lossCE?表示），因此综上所述Graph-MLP的总损失函数如下：
l
o
s
s
N
C
=
α
1
B
∑
i
=
1
B
?
i
l
o
s
s
f
i
n
a
l
=
l
o
s
s
C
E
+
l
o
s
s
N
C
\begin{aligned} loss_{NC} & = \alpha \frac{1}{B} \sum_{i=1}^{B}{\ell_i} \\ loss_{final} & = loss_{CE} + loss_{NC} \end{aligned}
lossNC?lossfinal??=αB1?i=1∑B??i?=lossCE?+lossNC??
其中
α
\alpha
α为平衡两种损失的权重因子。
Experiments
?作者在Cora、Citeseer和Pumbed三个数据集上进行了相关实验，数据集的统计信息展示如下：
由于Graph-MLP模型前向传播的过程中不需要使用邻接矩阵，因此可以采用Mini-Batch策略进行训练。在每个batch中，需要随机采样 B B B??个结点以及与之对应的邻接信息 A ^ ∈ R B × B \hat{A} \in \mathbb{R}^{B \times B} A^∈RB×B?和结点特征 X ∈ R R × d \boldsymbol{X} \in R^{\mathbb{R} \times d} X∈RR×d?。但由于随机采样，可能存在一些结点 i i i在batch中不存在正样本，这种情况下，采取的策略是不计算结点 i i i的损失。
?上述三个数据集都划分为了训练集、验证集与测试集，其在三个数据集中所占的数量如下表所示：
| Dataset | train | valid | test |
|---|---|---|---|
| Cora | 140 | 500 | 1000 |
| Citeseer | 120 | 500 | 1000 |
| Pubmed | 60 | 500 | 1000 |
超级参数配置说下：
| parameter | configuration |
|---|---|
| epochs | 400 |
| hidden dim (each linear layer) | 256 |
| dropout rate | 0.6 |
| learning rate | [0.001, 0.01, 0.05, 0.1] |
| weight decay | [5e-4, 5e-3] |
| batch size | [2000,3000] |
| τ \tau τ | [0.5, 1.0, 2.0] |
| r r r | [2,3,4] |
| α \alpha α | [0,1,10,100] |
注：测试结果是在验证机上表现最佳的模型上得到的；当 α = 0 \alpha = 0 α=0?时Graph-MLP就变成了最基础的MLP；优化器为Adam。
作者将Graph-MLP与几个SOTA的图学习方法进行了对比，对比结果展示如下：
结论：Graph在Citeseer和Pubmed都取得了最好的效果，尽管在Cora数据集上的效果不是最好的，但也和其他几个模型的性能差不多。作者指出可能是因为Cora数据集构成的图比较小而无法提供足够的对比监督。
效率对比：Graph-MLP VS GNNs
?作者尝试在MLP-based模型的第一个线性层和第二个线性层之间添加信息传递模块例如图卷积（可看作一个两层的GCN模型），然后与Graph-MLP模型进行对比，对比结果如下：
结论：图3可以看出Graph-MLP在Citeseer和Pubmed数据集上取得更好的结果和更快的收敛速度（数量级的差异），在Cora虽然GCN收敛更快但最后二者性能也是可以比较的。从表3可以看出，GCN的推断时间随着图规模的增大而增加（因为要乘以更大的邻接矩阵），而Graph-MLP由于没有使用邻接矩阵所以推断时间在图增大的时候基本不受影响。
超参上的消融实验（Ablation Study）
注：Ablation Study类似于控制变量法，每次修改一个变量，保持其他变量不动，观察这个变量对结果/性能的影响。
?作者在 τ \tau τ、 r r r、 B B B、 α \alpha α、learning rate和weight deacy上进行了消融实验，实验结果展示如下图：
结论： τ \tau τ、 r r r、 B B B??的改变对性能的影响不大；在Cora和Pubmed数据集上 α \alpha α由1变大到10，准确率有所提升，而由10变到100时准确率又下降了一点，在Citeseer数据集上 α \alpha α由1变到100，准确率实值在提升。
嵌入可视化
?作者对 Z Z Z的嵌入进行了可视化展示，用以帮助直观的展示NContrast Loss对原始MLP的作用，结果如下图所示：
结论：随着 α \alpha α的从0增大到100，相同类别的Embedding更加接近，而不同类别的Embedding会不断远离。
缺失连接的推断下的鲁棒性验证实验
?为了证明Graph-MLP在缺失连接下进行推断仍具有良好的鲁棒性，作者在测试过程中的邻接矩阵中添加了噪声，缺失连接的邻接矩阵的计算公式如下：
A
c
o
r
r
=
A
?
m
a
s
k
+
(
1
?
m
a
s
k
)
?
N
A_{corr} = A \otimes mask + (1 - mask) \otimes \mathbb{N}
Acorr?=A?mask+(1?mask)?N
其中
δ
\delta
δ?表示缺失率，
m
a
s
k
∈
n
×
n
mask \in n \times n
mask∈n×n??决定邻接矩阵中缺失的位置，
m
a
s
k
mask
mask?中的元素取1/0的概率为
1
?
δ
/
δ
1-\delta/\delta
1?δ/δ??。
N
∈
n
×
n
\mathbb{N} \in n \times n
N∈n×n?中的元素取1/0的概率都为0.5。
结论：从上图可以看出随着缺失率的增加，GCN的推断性能急剧下降，而Graph-MLP却基本不受影响。