MLP

最近一些工作通过解耦Message-Passing 和 Feature Learning的方式来提升GNN的可拓展性，这里对一小部分相关工作做一个小总结。 1. Combining Label Propagation and Simple Models Out-performs Graph Neural Networks （ICLR2021） 模型首先忽略图结构，用简单模型（MLP），只使用节点特征预测label： $$ \min \sum_{i \in L_{t}} \ell\left(f\left(x_{i}\right), y_{i}\right) $$ 考虑一个inductive bias：预测误差与邻近度关系强相关，对图中所有节点的误差做校正。 具体来说，首先计算一个初始的误差矩阵$E$，其中训练集误差如下 $$ E_{L_{t},:}=Y_{L_{t},:}-Z_{L_{t},:} $$ 其他节点的误差未知：$E_{L_{v},:}=0, \quad E_{U,:}=0$。然后通过Label Propagation将误差矩阵在图上做平滑，使得相邻节点的误差相似： $$ \hat{E}=\underset{W \in \mathbb{R}^{n \times c}}{\arg \min } \operatorname{trace}\left(W^{T}(I-S) W\right)+\mu||W-E||_{F}^{2} $$ 由此得到所有节点的误差矩阵$\hat{E}$。然后用$\hat{E}$对基础MLP预测做校正，这个post-processing过程不涉及训练参数，校正后的预测为： $$ Z^{(r)} = Z + \hat{E} $$ 考虑homophily：校正的预测label要满足相邻节点label相似。 注意，这里不直接对$Z^{(r)}$做Label Propagation，而是构造了一个label矩阵$H \in \mathbb{R}^{n \times c}$，其中将训练集真实label和验证+测试集校正label加入$H$中，然后对$H$做label propagation： $$ \begin{aligned} H_{L_{t},:}&=Y_{L_{t},:} \\ H_{L_{v} \cup U,:}&=Z_{L_{v} \cup U,:}^{(r)} \end{aligned} $$ Label Prop: $$ H^{(t+1)}=(1-\alpha) H+\alpha S H^{(t)} $$ 最后直接用收敛的$H$做预测，即$\hat{Y} = H^{\infty}$，node $i$ 的预测class为： $$ y_i = \arg \max _{j \in\{1, \ldots, c\}} \hat{Y}_{i j} $$ ...