企业邮箱账号大全_洛阳网络推广公司_北京企业网站seo平台_seo国外英文论坛

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 有多种结构，但每一层通常都可以写成如下形式：

$\begin{array}{rl}& \begin{array}{r}{m}_a^{(t)}={\text{AGGREGATE}}^N\left(\left\{({\tilde{A}}_{vu},h_u^{(t)})|u\in \mathcal{N}(v)\right\}\right),\end{array}\\ & m_v^{(t)}={\text{AGGREGATE}}^I\left(\left\{{\tilde{A}}_{vu}|u\in \mathcal{N}(v)\right\}\right)h_v^{(t)},\\ & \begin{array}{rl}{h}_v^{(t+1)}& =\text{COMBINE}(m_v^{(t)},m_a^{(t)}).\end{array}\end{array}$

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

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}$ 为（带权）度数矩阵。

时间 $O(m{d}^2)$ 空间 $O(m)$

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

该结构的 OOD 泛化性较强

$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]$

时间 $O(sn{d}^2)$ 空间 $O(n)$

GAT

http://arxiv.org/abs/1710.10903
http://arxiv.org/abs/2105.14491 (GATv2)

就是在图上做 attention，原文的 attention score 是用 MLP 算的。

${\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)}$

时间 $O(hn{d}^2+hmd)$ 空间 $O(n^2)$

GATv2 改为： $e\left({\mathbf{h}}_i,{\mathbf{h}}_j\right)={\mathbf{a}}^{\top }\text{LeakyReLU}\left(\mathbf{W}\cdot [{\mathbf{h}}_i\Vert {\mathbf{h}}_j]\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

文章指出 GNN 表达能力的上限是 1-WL-test，而 GIN 可以接近这个上限。

其中聚合函数用 sum 表达能力会比 mean 和 max 强。

$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)$

时间 $O(m{d}^2)$ 空间 $O(m)$

GNN beyond 1-WL-test

后续又提出了一些超越 1-WL-test 表达能力的 GNN，下面尝试整理一下。

NGNN

http://arxiv.org/abs/2110.13197

使用 GNN 套 GNN，学习到的特征从 subtree 变成了 subgraph，但复杂度高了很多。

${\mathbf{m}}_{v,G_w^h}^{t+1}={\sum }_{u\in N(v|G_w^h)}{M}_t({\mathbf{h}}_w^t,{\mathbf{h}}_{u,G_w^h}^t,{\mathbf{e}}_{vu})$

${\mathbf{h}}_{v,G_w^h}^{t+1}=U_t({\mathbf{h}}_{v,G_w^h}^t,{\mathbf{m}}_{v,G_w^h}^{t+1})$

GraphSNN

https://openreview.net/forum?id=uxgg9o7bI_3

根据结构定义边权，从而增强 GNN 的表达能力，方法如下：

计算每个点和所有邻点的导出子图： S v = G ( N ( v ) ∪ { v } ) S_v=G(\mathcal N(v)\cup \{v\}) Sv​=G(N(v)∪{v})

令 $S_{vu}=S_v\cap S_u$

给每条边计算权值：$A_{vu}=\omega (S_v,S_{vu})$

文中 $\omega$ 定义为：$\omega (S_v,S_{vu})=\frac{|E_{vu}||V_{vu}{|}^{\lambda -1}}{|V_{vu}-1|}$，其中 $\lambda >0$

归一化的边权为 ${\tilde{A}}_{vu}=\frac{A_{vu}}{{\sum }_{u\in \mathcal{N}(v)}{A}_{vu}}$

每层 $h_v^{(t+1)}={\mathsf{MLP}}_{\theta }\left({\gamma }^{(t)}\right({\sum }_{u\in \mathcal{N}(v)}{\tilde{A}}_{vu}+1)h_v^{(t)}+{\sum }_{u\in \mathcal{N}(v)}({\tilde{A}}_{vu}+1\left)h_u^{(t)}\right)$

时间 $O(m{d}^2)$ 空间 $O(m)$