LD2 Scalable Heterophilous Graph Neural Network with Decoupled Embeddings

Neurips 24
推荐指数： #paper/⭐⭐⭐
领域：可扩展图，大图加速
整个文章的理论部分比较多，尽量尽我所能避开一些额外公式。详细文章，见链接

模型架构

如图，整个模型分为与计算和训练两部分。本文的精华在于预训练

LD2–一个解耦的异配图gnn

为了更好的加速，我们使用了多通道结果去增加灵活性。输入的数据是一系列的嵌入矩阵 $[P_1,P_2,\dots ,P_C]$
预计算
$${\mathbf{P}}_A,{\mathbf{P}}_X={\mathrm{A}}^2\mathrm{Prop}(\mathbf{A},\mathbf{X})$$
转换得嵌入
$${\mathbf{H}}^{(L)}=\mathrm{MLP}({\mathbf{P}}_A{\mathbf{W}}_A\Vert {\mathbf{P}}_X{\mathbf{W}}_X).$$

低纬邻接矩阵嵌入

由于二阶邻居信息很少受到同配异配信息的影响，因此我们对二跳邻接矩阵进行建模
$${\mathbf{P}}_A=\arg \underset{\mathbf{P}\in {\mathbb{R}}^{n\times F}}{\min }\Vert {\mathbf{A}}^2-\mathbf{P}{\mathbf{P}}^T{\Vert }_F^2.$$
通过优化F范数，我们可以得到$P_A\in {\mathbb{R}}^{n\times F}$.
(谱分析视角见论文原文)

长距离特征嵌入

用$P_X={\sum }_{l=1}^{L_P}{\theta }_l{\mathbf{T}}^l\mathbf{X}$ 来计算特征，可能不太好(因为数据有高通低通中通)。按照低通高通中通，我们分别定义为 $P_{X,L2},P_H,P_{X,0}$。
那么，
$${\mathbf{P}}_{X,H}=\frac{1}{L_{P,H}}\sum _{l=1}^{L_{P,H}}(\mathbf{I}+\tilde{\mathbf{L}}{)}^l\mathbf{X},({\theta }_l=1,\mathbf{T}=\mathbf{I}+\tilde{\mathbf{L}})$$
$${\mathbf{P}}_{X,L2}=\frac{1}{L_{\mathbf{P},\mathbf{L}2}}\sum _{l=1}^{L_{P,L2}}{\bar{\mathbf{A}}}^{2l}\mathbf{X},({\theta }_l=1,\mathbf{T}={\bar{\mathbf{A}}}^2)$$
$${\mathbf{P}}_{X,0}=\mathbf{X}$$
其中，$\tilde{L}=I-\tilde{A},\overline{A}$是没有自环的邻接矩阵。
(谱分析视角见原文)
拉普拉斯矩阵显然是高通过滤器，A是低通过滤器。这样，我们就可以构造高阶或者低阶如上长距离特征嵌入

近似邻接矩阵传播预计算

近似特征嵌入计算

$${\mathbf{P}}_X=\sum _{l=0}^{L_P}{\theta }_l{\mathbf{T}}^l\mathbf{X}$$
首先，初始值是：${\mathbf{R}}^{(0)}=\mathbf{X}.$传播矩阵是T。拉普拉斯传播T=I+L.嵌入可以表示为迭代形式：
R ( l + 1 ) ( u ) = 2 R ( l ) ( u ) − ∑ v ∈ N ( u ) R ( l ) ( v ) / d a ( u ) d b ( v ) = ∑ v ∈ N ( u ) ∪ { u } α L ( u , v ) d a ( u ) d b ( v ) ⋅ R ( l ) ( v ) \boldsymbol{R}^{(l+1)}(u)=2\boldsymbol{R}^{(l)}(u)-\sum_{v\in\mathcal{N}(u)}\boldsymbol{R}^{(l)}(v)/d^a(u)d^b(v)=\sum_{v\in\mathcal{N}(u)\cup\{u\}}\frac{\alpha_L(u,v)}{d^a(u)d^b(v)}\cdot\boldsymbol{R}^{(l)}(v) R(l+1)(u)=2R(l)(u)−v∈N(u)∑​R(l)(v)/da(u)db(v)=v∈N(u)∪{u}∑​da(u)db(v)αL​(u,v)​⋅R(l)(v)
${\alpha }_T(u,v)$对于T，$\begin{array}{r}{\alpha }_L(u,u)=2d^{\mathbf{a}+\mathbf{b}}(u),{\alpha }_L(u,v)=-1,v\in \mathcal{N}(u)\end{array}$。对于$\tilde{A},\bar{A}$,分别是${\alpha }_A(u,v)=1\text{ and }{\alpha }_A(u,u)=1,0$

近似邻接矩阵嵌入的计算

$${\mathbf{R}}^{(0)}=N(0,1)$$
$${\mathbf{A}}^2\mathrm{as}{\mathbf{R}}^{(l+1)}={\mathbf{A}}^2{\mathbf{R}}^{(l)}$$
之后，执行column-wise normalization
$$\text{orthonormalize}({\mathbf{R}}^{(l+1)})$$
这样，矩阵就满足：
$${\mathbf{A}}^2{\mathbf{R}}^{(L_P)}={\mathbf{R}}^{(L_P)}\mathbf{\Lambda }$$
最后，结果是：
$$\hat{\mathbf{U}}={\mathbf{R}}^{(L_P)},{\hat{\mathbf{P}}}_A=\hat{\mathbf{U}}|\hat{\mathbf{\Lambda }}{|}^{1/2}$$

实验结果：

时间开销：