ICLR24
推荐指数： #paper/⭐⭐
领域： 大图，图扩展
大概的工作：提出了针对子图的虚拟节点，让所有点都与其相连
相关工作：
传统GNN与Inplicit gnn
传统GNN的传播函数：
Z ( l + 1 ) = ϕ ( W ( l ) Z ( l ) S + Ω ( l ) X ) , Z^{(l+1)}=\phi(W^{(l)}Z^{(l)}S+\Omega^{(l)}X), Z(l+1)=ϕ(W(l)Z(l)S+Ω(l)X),
其中，W是可训练参数。S是邻接矩阵(A)。 Ω ( l ) \Omega^{(l)} Ω(l)相当于是加自环的操作
InplicitGNN 则是捕获隐含的长关系。
Z ( l + 1 ) = γ g ( W ) Z ( l ) S + f ( X , G ) , Z^{(l+1)}=\gamma g(W)Z^{(l)}S+f(X,\mathcal{G}), Z(l+1)=γg(W)Z(l)S+f(X,G),
g ( W ) g(W) g(W)映射W进一个Frobenius norm，其中半径小小于1. f ( x , G ) f(x,G) f(x,G)是一个参数化的transformation。
批采样
批采样只考虑子图内的关系，但是Inplicit GNN的优势–长关系获取能力随着子图的建立就会消失。这就意味着，随着批采样的采用，Inplicit的准确率就会降低。
我们的方法：
Coarse node
如图所示，我们提出了coarse node。其是虚拟节点，所有子图内的节点都与其虚拟相连。他的作用相当于汇聚子图所有节点的信息，类似于prototype。coarse node与coarse node 相连，来做数据交换，以此获取长跳数的信息
Mini-batch train
当添加了coarse节点后，我们就可以使用mini-batch采样方法了。比如Graphsage，Shadow-GNN等了。为了构建批处理graph，我们首先从节点集中随机采样目标节点。之后，为了声测会给你每个目标节点v的预测，我们选择一些供相关或者更重要的节点作为辅助节点。例如，PPR。我们使用PPR来确定相对于目标节点v重要还是不重要的节点。具体的是，我们选择top-k 重要的PPR节点。拼接所有目标节点以及他们的附属节点作为新的点集 V s V_{s} Vs，我们得到相应的子图 G s u b G_{sub} Gsub通过两点链接的集合。
Z s u b ∗ = φ ( Z s u b ∗ , X , G ) = γ g ( W ) Z s u b ∗ S s u b + f ( X s u b , G s u b ) , \begin{aligned}Z_{sub}^*=\varphi(Z_{sub}^*,X,\mathcal{G})=\gamma g(W)Z_{sub}^*S_{sub}+f(X_{sub},\mathcal{G}_{sub}),\end{aligned} Zsub∗=φ(Zsub∗,X,G)=γg(W)Zsub∗Ssub+f(Xsub,Gsub),
新的加速方案(这部分看原文吧，借鉴了好几篇文章，并给出自己的见解)
lim l → ∞ vec [ Z ( l ) ] = vec [ Z ∗ ] = ( I − γ [ S ⊗ g ( W ) ] ) − 1 vec [ f ( X , G ) ] \begin{aligned}\lim_{l\to\infty}\operatorname{vec}[Z^{(l)}]=\operatorname{vec}[Z^*]=(I-\gamma[S\otimes g(W)])^{-1}\operatorname{vec}[f(X,\mathcal{G})]\end{aligned} l→∞limvec[Z(l)]=vec[Z∗]=(I−γ[S⊗g(W)])−1vec[f(X,G)]
使用 Neumann series事实 ( I − γ [ S ⊗ g ( W ) ] ) − 1 = ∑ k = 0 ∞ γ k [ S T ⊗ g ( W ) ] k \left(I-\gamma[S\otimes g(W)]\right)^{-1} = \sum_{k=0}^\infty\gamma^k[S^T \otimes g(W)]^k (I−γ[S⊗g(W)])−1=∑k=0∞γk[ST⊗g(W)]k，我们可以得到：
vec [ Z ∗ ] = ∑ k = 0 ∞ γ k [ S T ⊗ g ( W ) ] k vec [ f ( X , G ) ] = ∑ k = 0 ∞ γ k vec [ g ( W ) k f ( X , G ) S k ] . \operatorname{vec}[Z^*]=\sum_{k=0}^\infty\gamma^k\left[S^T\otimes g(W)\right]^k\operatorname{vec}[f(X,\mathcal{G})]=\sum_{k=0}^\infty\gamma^k\operatorname{vec}[g(W)^kf(X,\mathcal{G})S^k]. vec[Z∗]=k=0∑∞γk[ST⊗g(W)]kvec[f(X,G)]=k=0∑∞γkvec[g(W)kf(X,G)Sk].
去掉两侧向量化，可以得到：
Z ∗ = ∑ k = 0 ∞ γ k g ( W ) k f ( X , G ) S k . Z^*=\sum_{k=0}^\infty\gamma^kg(W)^kf(X,\mathcal{G})S^k. Z∗=k=0∑∞γkg(W)kf(X,G)Sk.
为了获得平衡点的最简单逼近，我们可以在某个步骤t直接截断Neumann series，并将V（t）定义为平衡点的逼近：
V ( t ) = ∑ k = 0 t γ k g ( W ) k f ( X , G ) S k ≈ Z ∗ . V^{(t)}=\sum_{k=0}^t\gamma^kg(W)^kf(X,\mathcal{G})S^k\approx Z^*. V(t)=k=0∑tγkg(W)kf(X,G)Sk≈Z∗.
stochastic solver
然而，直接截断诺伊曼系列以获得近似平衡将招致由于正向传播有偏差而不会消失的误差。我们提出stochastic solver
当i>t后，我们令， b i ∼ B e r n o u l l i ( α ) b_i\sim\mathsf{Bernoulli}(\alpha) bi∼Bernoulli(α)
如果 b i = 1 b_{i}=1 bi=1，我们就更新Z使用因素： 1 α ( i − t ) \frac1{\alpha^{(i-t)}} α(i−t)1
Z ^ ( i ) = Z ^ ( i − 1 ) + γ i 1 α ( i − t ) g ( W ) i f ( X , G ) S i . \hat{Z}^{(i)}=\hat{Z}^{(i-1)}+\gamma^i\frac1{\alpha^{(i-t)}}g(W)^if(X,\mathcal{G})S^i. Z^(i)=Z^(i−1)+γiα(i−t)1g(W)if(X,G)Si.
训练
我们使用如下梯度传播：
∂ ℓ ∂ ( ⋅ ) = ∂ ℓ ∂ Z ^ ∗ ( I − J φ ( Z ^ ∗ ) ) − 1 ∂ φ ( Z ^ ∗ , X , G ) ∂ ( ⋅ ) , \frac{\partial\ell}{\partial(\cdot)}=\frac{\partial\ell}{\partial\hat{Z}^*}\left(I-J_\varphi(\hat{Z}^*)\right)^{-1}\frac{\partial\varphi(\hat{Z}^*,X,\mathcal{G})}{\partial(\cdot)}, ∂(⋅)∂ℓ=∂Z^∗∂ℓ(I−Jφ(Z^∗))−1∂(⋅)∂φ(Z^∗,X,G),
其中， Z ^ ∗ = φ ( Z ^ ∗ , X , G ) \hat{Z}^* = \varphi(\hat{Z}^*,X,\mathcal{G}) Z^∗=φ(Z^∗,X,G)， J = ∂ φ ( Z ^ ∗ , X , G ) ∂ Z ^ ∗ J = \frac{\partial\varphi(\hat{Z}^{*},X,\mathcal{G})}{\partial\hat{Z}^{*}} J=∂Z^∗∂φ(Z^∗,X,G)
