今天学习斯坦福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的结构表示性能强大。
2.2 d-正则图(d-regular graph)
什么是d-正则图。
无向图中的正则图为中每个顶点具有相同数量的邻点; 即每个顶点具有相同的度。 正则的有向图中每个顶点的内外自由度都要彼此相等。并且满足,边的个数, 其中为节点个数,为节点度数
图1. $d=2$的正则图不同于完全图,边的个数,每个顶点度为
由此,正则图存在的必要和充分条件是
2.3 集聚系数(cluster coefficient)
节点局部集聚系数定义为,对图中具体的某一个点,它的局部集聚系数 表示与它相连的点抱成团(完全图/ clique/ complete graph)的程度。
左图与中心点连接的三个点,相互之间的连接边个数为3,则集聚系数 $C_i=1$在无向图中,其计算公式为:
3. Preliminaries
3.1 ID-GNN
归纳式(inductive)的颜色标注
从中心点出发,选择他们的K-hop节点集合, 并在这个集合网络中标注中心点的颜色,如下图最左节点分类中所示
异构图的信息传导(message passing)
有两种使用情景,当此点被颜色标注过使用下标为的网络,反之下标为。
Proposition 1:当时,是一个没有原始节点颜色标注的网络,如公式4,根据前情提要,此公式为公式1的变形。由此可见ID-GNN和GIN一样是可导的。
添加边信息(edge attribute)
边信息为, 将其加入网络中
Proposition 2:添加了图环计算(cycle count),对于中心点在embedding网络上,添加了一维特征,其中表示了中心点出发并截至至中心点,长度为环的个数,
ID-GNN-Fast
该网络的增强ID-GNN-Fast,基于对图环计算(cycle count)计算的改进。由于使用稀疏矩阵,可以使得图环计算变得更快,该图环特征, ,其中为邻接矩阵。
tips: 邻接矩阵乘法的特殊意义,其对角矩阵为对应节点的环个数。
其为节点的n-hop邻居位置。但此方法有弊端在于内存占用过高。
3.2 Case study
节点层面:预测聚类系数
本例中,输入节点one-hot特征,由公式2得,在此情境下:
由此,是一个连续函数,依据Universal Approximation,当网络为MLP时满足近似率为
边层面:预测可达最短路径
由一对顶点预测其最短路径的方法,基于条件节点embedding:在中的节点对于节点在可达,则存在
图层面:分辨d度-正则图
依据Proposition 2对图环的计算,ID-GNN的正则图判定效率如下:
4. Experiments
实验结果
网友评论