【note】GNN

WL-test

https://dl.acm.org/doi/10.5555/1953048.2078187

WL-test 是一个判断图同构问题的启发式算法（可能会把非同构判断成同构）。

1-WL-test 是最简单的一个版本，方法如下：

1. 初始时，点 $v$ 特征为 $l_0(v)$
2. 每次迭代时，用邻点特征的多重集更新每个点的特征，即令 l i ( v ) = f ( { l i − 1 ( u ) ∣ u ∈ N ( v ) } ) l_i(v)=f(\{l_{i-1}(u)|u\in \mathcal N(v)\}) li​(v)=f({li−1​(u)∣u∈N(v)})
3. 最终比较两张图所有点特征的多重集是否相等

迭代 $h$ 次，时间复杂度 $O(hm)$。（就是比较深度为 $h$ 的 dfs 树是否同构）

GNN

GNN 有多种结构，但每一层通常都可以写成如下形式：

$a_v^{(k)}={\text{AGGREGATE}}^{(k)}\left(\left\{h_u^{(k-1)}:u\in \mathcal{N}(v)\right\}\right)$

$h_v^{(k)}={\text{COMBINE}}^{(k)}\left(h_v^{(k-1)},a_v^{(k)}\right)$

下面尝试整理一下常见的几种结构。

GCN (spectral)

https://arxiv.org/abs/1312.6203
https://arxiv.org/abs/1606.09375

有点复杂，见得不多

GCN (spatial)

https://arxiv.org/abs/1609.02907

相对简单且常见

$H^{(l+1)}=\sigma \left({\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}{H}^{(l)}{W}^{(l)}\right)$

其中 $\tilde{A}=A+I_N$ 是邻接矩阵和单位矩阵之和，${\tilde{D}}_{ii}={\sum }_j{A}_{ij}$ 为度数矩阵。

MPNN

https://arxiv.org/abs/1704.01212

$\begin{array}{rl}{m}_v^{t+1}& =\sum _{w\in N(v)}{M}_t(h_v^t,h_w^t,e_{vw})\\ h_v^{t+1}& =U_t(h_v^t,m_v^{t+1})\end{array}$

GraphSAGE

http://arxiv.org/abs/1706.02216

$a_v^{(k)}=\mathrm{MAX}\left(\left\{\mathrm{ReLU}\left(W\cdot h_u^{(k-1)}\right),\forall u\in \mathcal{N}(v)\right\}\right)$

$h_u^{(k)}=W\cdot \left[h_v^{(k-1)},a_v^{(k)}\right]$

GAT

http://arxiv.org/abs/1710.10903

${\alpha }_{ij}=\frac{\exp \left(\text{LeakyReLU}\left({\vec{\mathbf{a}}}^T[\mathbf{W}{\vec{h}}_i\Vert \mathbf{W}{\vec{h}}_j]\right)\right)}{{\sum }_{k\in {\mathcal{N}}_i}\exp \left(\text{LеаkyReLU}\left({\vec{\mathbf{a}}}^T[\mathbf{W}{\vec{h}}_i\Vert \mathbf{W}{\vec{h}}_k]\right)\right)}$

${\vec{h}}_i^{\prime }={\Vert }_{k=1}^K\sigma \left({\sum }_{j\in {\mathcal{N}}_i}{\alpha }_{ij}^k{\mathbf{W}}^k{\vec{h}}_j\right)$

AGNN

http://arxiv.org/abs/1803.03735

P i ( t ) = softmax ( [ β ( t ) cos ⁡ ( H i ( t ) , H j ( t ) ) ] j ∈ N ( i ) ∪ { i } ) P_i^{(t)}=\text{ softmax}{ \left ( [ \beta ^ { ( t ) }\cos(H_i^{(t)},H_j^{(t)})]_{j\in N(i)\cup\{i\}}\right)} Pi(t)​= softmax([β(t)cos(Hi(t)​,Hj(t)​)]j∈N(i)∪{i}​)

H i ( t + 1 ) = ∑ j ∈ N ( i ) ∪ { i } P i j ( t ) H j ( t ) H_i^{(t+1)}=\sum_{j\in N(i)\cup\{i\}}P_{ij}^{(t)}H_j^{(t)} Hi(t+1)​=∑j∈N(i)∪{i}​Pij(t)​Hj(t)​

GIN

http://arxiv.org/abs/1810.00826

$h_v^{(k)}={\mathrm{MLP}}^{(k)}\left(\left(1+{ϵ}^{(k)}\right)\cdot h_v^{(k-1)}+{\sum }_{u\in \mathcal{N}(v)}{h}_u^{(k-1)}\right)$