基于标注提升的ID-GNN： Identity-aware Gr

2021-02-18 本文已影响0人戈季

今天学习斯坦福2021年Jure Leskovec发表在AAAI的工作《Identity-aware Graph Neural Networks》。

由Jure Leskovec组 2019 年的工作《How Powerful are Graph Neural Networks?》证明GNN 算法的表达能力，具有与 Weisfeiler-Lehman 图同构测试一样的表达上限，是不适用于计算集聚系数（cluster coefficient），求图内最短距离问题，判断d-regular图的区别任务的。

本文提出选取中心节点，并通过多轮对异构图中中心节点进行message passing操作的模型ID-GNN，以求其表现能力超越WL-test，并基于此模型提出了一版简化过更快的，可以增强节点特征的ID-GNN网络。

实验效果表明，link prediction的AUC及ROC提升15%，图/节点分类提升3%。

WL限制内的GNN网络是什么样子的，为什么不适合以上三种问题？
WL test是什么？
d-regular图是什么？

预测节点分类相关系数，求图内最短距离问题，判断d-regular图的区别任务的问题介绍和实际效果。

1. Introduction

由于GNN受限于1度WL，最近一些工作，提出模型解决了此类问题。其中包括Ring-GNN， Relative Pool GNN 和G-invariant networks，但他们都受限于复杂度的增长

（为什么？受限于1度WL，证明部分中区别是什么）

作者提出ID-GNN，不同于聚合更新，他采用Message Passing做更新，并且提出简版的ID-GNN模型，加入“图环计算”（cycle counts）用于增强节点信息。其计算由邻接矩阵的次方实现，计算效率较高。

本文有以下贡献：

证明了message passing表示能力超过WL test
从理论和实验验证了ID-GNN的解集大于GNNs
证明了GNN在实际问题的局限，做了case study

2. 前情提要

2.1 同构图测试（WL-test）与 GIN

Weisfeiler-Lehman(WL) test是判断两个graph 是否具有相同的结构（同构）的有效方法

GNN的目标是以图结构数据和节点特征作为输入，以学习到节点（或图）的embedding，用于分类任务。基于邻域聚合的GNN可以拆分为以下三个模块：

Aggregate：聚合一阶邻域特征。
Combine：将邻居聚合的特征与当前节点特征合并，以更新当前节点特征。
Readout（可选）：如果是对graph分类，需要将graph中所有节点特征转变成graph特征。

由前文定理得：

如果GNN中Aggregate、Combine 和 Readout 函数是单射，GNN可以和WL test 一样强大。
基于mean、max aggregate的GNN 不如基于sum aggregate的结构表示性能强大。

$h_v^{(k)} = \mathbb{M}LP^{(k)}((1+\epsilon^{(k)}) \cdot h_v^{(k-1)} + \sum_{u\in N_v} h_v^{(k-1)} ) \tag{1}$

2.2 d-正则图（d-regular graph）

什么是d-正则图。

无向图中的正则图为中每个顶点具有相同数量的邻点；即每个顶点具有相同的度。正则的有向图中每个顶点的内外自由度都要彼此相等。并且满足，边的个数 $E = \frac{n*d}{2}$ ，其中 $n$ 为节点个数， $d$ 为节点度数

图1. $d=2$的正则图

不同于完全图，边的个数 $E = \frac{n*(n-1)}{2}$ ，每个顶点度为 $n-1$

由此， $k$ 正则图存在的必要和充分条件是 $n≥k+1$

2.3 集聚系数（cluster coefficient）

节点局部集聚系数定义为，对图中具体的某一个点，它的局部集聚系数 $C_i$ 表示与它相连的点抱成团（完全图/ clique/ complete graph）的程度。

左图与中心点连接的三个点，相互之间的连接边个数为3，则集聚系数 $C_i=1$

在无向图中，其计算公式为：
$C_i = \frac{|e_{jk} \in N_i, e_{jk} \in E|}{\frac{k_i(k_i)-1}{2}}\tag2$

3. Preliminaries

3.1 ID-GNN

归纳式（inductive）的颜色标注

从中心点 $v$ 出发，选择他们的K-hop节点集合 $G_v^K$ ，并在这个集合网络中标注中心点 $v$ 的颜色，如下图最左节点分类中所示

上图中可以看出，在这三类任务中，给原始节点标注颜色在massage passing建立树的过程中，是可以区分图结构，并进行有效标注的

异构图的信息传导（message passing）

$\mathbb{M}SG(\cdot)$ 有两种使用情景，当此点被颜色标注过使用下标为 $1[s=v]$ 的 $\mathbb{M}SG(\cdot)$ 网络，反之下标为 $0[s=v]$ 。

$m_s^{(k)} = \mathbb{M}SG_{1[s=v]}^{(k)} (h_s^{(k-1)}) \\ h_u^{(k)} = \mathbb{A}GG^{(k)}([m_s^{(k)}，s \in N(u) ], h_u^{(k-1)}) \tag{3}$

Proposition 1：当 $\mathbb{M}SG_1(\cdot) = \mathbb{M}SG_0(\cdot)$ 时，是一个没有原始节点颜色标注的网络，如公式4，根据前情提要，此公式为公式1的变形。由此可见ID-GNN和GIN一样是可导的。
$m_s^{(k)} = \mathbb{M}SG^{(k)} (h_s^{(k-1)}) \\ c = \mathbb{A}GG^{(k)}([m_s^{(k)}，s \in N(u) ], h_u^{(k-1)}) \tag{4}$

添加边信息（edge attribute）

边信息为 $f_{su}$ , 将其加入网络中

$m_s^{(k)} = \mathbb{M}SG_{1[s=v]}^{(k)} (h_s^{(k-1)}, \pmb{f_{su}}) \\h_u^{(k)} = \mathbb{A}GG^{(k)}([m_s^{(k)}，s \in N(u) ], h_u^{(k-1)}) \tag{5}$

Proposition 2：添加了图环计算（cycle count），对于中心点 $v$ 在embedding网络 $h_u^{(k)}$ 上，添加了一维特征 $j$ ，其中 $h_u^{(k)}[j]$ 表示了中心点 $v$ 出发并截至至中心点 $v$ ，长度为 $j$ 环的个数, $j\in (1,k)$

ID-GNN-Fast
该网络的增强ID-GNN-Fast，基于对图环计算（cycle count）计算的改进。由于使用稀疏矩阵，可以使得图环计算变得更快，该图环特征 $x_v ^{+}\in R^k$ , $x_v ^{+}[k] = Diag(A^k)[v]$ ，其中 $A$ 为邻接矩阵。

tips: 邻接矩阵乘法的特殊意义，其对角矩阵为对应节点的环个数。
其 $A^n-A^{(n-1)}$ 为节点的n-hop邻居位置。但此方法有弊端在于内存占用过高。

3.2 Case study

节点层面：预测聚类系数

本例中，输入节点one-hot特征，由公式2得，在此情境下：

$C_v = \frac{h_v^{(k)}[3]}{h_v^{(k)}[2]*h_v^{(k)}[2]-1}\tag6$

由此， $C_v$ 是一个连续函数，依据Universal Approximation，当网络为MLP时满足近似率为 $\epsilon$

边层面：预测可达最短路径

由一对顶点预测其最短路径的方法，基于条件节点embedding：在 $G$ 中的节点 $u$ 对于节点 $v$ 在 $K-hop$ 可达，则存在 $h_{u|v}^{K}=1$

$m_{u|v}^{k}= \begin{cases} 1& \text{if 1[s=v]=1}\\ h_{u|v}^{k-1}& \text{else} \end{cases} \\ h_{u|v}^{k}= \mathbb{M}AX(m_{u|v}^{k}, s\in N_u) \tag{7}$

图层面：分辨d度-正则图

依据Proposition 2对图环的计算，ID-GNN的正则图判定效率如下：

在节点大小为n，正则度为d的情况下

4. Experiments

实验结果