美文网首页
基于标注提升的ID-GNN: Identity-aware Gr

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

作者: 戈季 | 来源:发表于2021-02-18 12:34 被阅读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对于节点vK-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


    实验结果

    相关文章

      网友评论

          本文标题:基于标注提升的ID-GNN: Identity-aware Gr

          本文链接:https://www.haomeiwen.com/subject/cdlkxltx.html