图神经网络(其它)

一、GIN

  1. 对图结构数据的学习需要有效地对图结构进行表示。最近,对图表示学习graph representation learning 的图神经网络 Graph Neural Network: GNN 引起了人们的广泛兴趣。GNN 遵循递归邻域聚合方案,其中每个顶点聚合其邻居的representation 向量从而计算顶点的新的 representation

    已经有很多 GNN 的变体,它们采用不同的邻域聚合方法、graph-level 池化方法。从实验上看,这些 GNN 变体在很多任务(如顶点分类、链接预测、图分类)中都达到了 state-of-the-art 性能。但是,新的 GNN 的设计主要基于经验直觉empirical intuition、启发式heuristics、以及实验性experimental 的反复试验。

    人们对 GNN 的性质和局限性的理论了解很少,对 GNN 的表达容量representational capacity 的理论分析也很有限。论文 《HOW POWERFUL ARE GRAPH NEURAL NETWORKS?》 提出了一个用于分析GNN 表达能力representational power 的理论框架。作者正式刻画characterize 了不同 GNN 变体在学习表示represent 和区分distinguish 不同图结构上的表达能力expressive

  2. 作者的灵感主要来自于GNNWeisfeiler-Lehman:WL 图同构检验graph isomorphism test 之间的紧密联系。

    WL-test 是一种强大的、用于区分同构图的检验。类似于 GNNWL-test 通过聚合其网络邻域的特征向量来迭代更新给定顶点的特征向量。WL-test 如此强大的原因在于它的单射聚合更新 injective aggregation update,这可以将不同的顶点邻域映射到不同的特征向量。

    作者的主要洞察是:如果 GNN 的聚合方案具有很高的表达能力expressive 并且建模单射函数injective function,那么 GNN 可以具有与 WL-test 一样强大的判别力discriminative power

    为了从数学上形式化该洞察,我们的框架首先将给定顶点的邻居的特征向量集合表示为 multiset,即可能包含重复元素的集合。可以将 GNN 中的邻域聚合视为 multiset 上的聚合函数 aggregation function over the multiset 。因此,为了具有强大的表示能力representational powerGNN 必须能够将不同的 multiset 聚合为不同的表示。我们严格研究了multiset 函数的几种变体,并从理论上刻画了它们的判别力discriminative power ,即不同的聚合函数如何区分distinguish 不同的multisetmultiset 函数的判别力越强,则底层GNN 的表示能力就越强。

    然后我们设计出一种简单的架构 Graph Isomorphism Network:GIN,该架构被证明是 GNN 中最具表达能力的most expressive ,并且和 WL-test 一样强大。

    我们在图分类数据集上进行实验来验证我们的理论,其中GNN 的表达能力expressive power 对于捕获图结构至关重要。具体而言,我们比较了使用各种聚合函数的 GNN 的性能。实验结果证明了最强大most powerfulGNN(即我们提出的 GIN)在实验中也具有很高的表示能力,因为它几乎完美拟合训练数据。而能力更弱less powerfulGNN 变体通常对于训练数据严重欠拟合underfit 。此外,GIN 在测试集上的准确率也超过了其它GNN 变体,并在图分类 benchmark 上达到了 state-of-the-art 性能。

  3. 论文的主要贡献:

    • 证明GNN 在区分图结构方面最多和 WL-test 一样强大。
    • 给出邻域聚合函数和图readout 函数在什么条件下所得的 GNNWL-test 一样强大。
    • 识别那些无法被主流的GNN 变体(如 GCN,GraphSAGE)判别的图结构,然后刻画这些GNN-based 模型能够捕获的图结构。
    • 设计了一个简单的神经网络架构,即 Graph Isomorphism Network: GIN,并证明了其判别力/表示能力 discriminative/representational power 等于 WL-test
  4. 单射函数:假设 是集合 到集合 的映射。如果所有 都有 ,则称 是 从 的单射。

  5. 尽管 GNN 在经验上取得成功,但是在数学上研究GNN 特性的工作很少。

    • Scarselli 等人的工作表明:早期的 GNN 模型在概率上逼近测度函数。
    • Lei 等人表明,他们提出的架构位于graph kernelPKHS 中,但没有明确研究它可以区分哪些图。

    这些工作中的每一个都专注于特定的体系结构,并且不容易推广到多种体系结构。相反,我们的研究为分析和刻画一系列GNN 模型的表征能力提供了一个通用框架。

    另外,近期提出了一些基于 GNN 的体系结构大多数没有理论推导,与此相比,我们的 GIN 是有理论推导的,而且简单、强大。

1.1 GNN 模型

  1. 我们首先总结一些常见的 GNN 模型。

  2. 令图 ,其中:

    • 为顶点集合。
    • 为边集合, 表示顶点 之间的边。
    • 每个顶点 关联一个顶点特征向量 ,其中 为特征向量维度。

    通常我们关心图上的两类任务:

    • 顶点分类任务:每个顶点 关联一个标签 ,任务目标是学习顶点 的一个representation 向量 ,使得顶点 的标签能够通过 来预测。
    • 图分类任务:给定一组图 ,以及每个图的标签 ,任务目标是学习图 的一个representation 向量 ,使得图 的标签能够通过 来预测。
  3. GNN 利用图结构和顶点特征 来学习顶点的representation 向量 ,或者学习整个图的representation 向量

    现代 GNN 使用邻域聚合策略,在该策略中我们通过聚合邻域的representation 来迭代更新顶点的 representation 。在经过 次迭代聚合之后,顶点的representation 将捕获其 k-hop 邻域内的结构信息。

    以数学公式来讲,GNN 的第 层为:

    其中:

    • 为顶点 在第 层的 representation。另外 初始化为 ,即
    • 为顶点 的直接邻居顶点集合。
    • 为第 层的聚合函数, 为第 层的拼接函数。
  4. 的选择至关重要。已经提出了很多聚合函数:

    • GraphSAGE 的最大池化变体中,聚合函数为:

      其中:

      • 为可学习的参数矩阵,它是跨顶点、跨层共享。
      • 为逐元素的最大池化。
      • relu 非线性激活函数。

      GraphSAGE 中的拼接函数为简单的向量拼接:

      其中 [,] 表示向量拼接, 为可学习的参数矩阵。

    • Graph Convolutional Networks: GCN 中,聚合函数采用逐元素的均值池化。此时聚合函数、拼接函数整合在一起:

      其中 MEAN(.) 为逐元素的均值池化, 为可学习的参数矩阵。

  5. 对于顶点分类任务,顶点 最后一层的representation 就是顶点 representation

    对于图分类任务,READOUT 函数聚合所有顶点最后一层的 representation 从而得到整个图的 representation

    READOUT 函数可以是简单的置换不变函数permutation invariant function,例如求和函数;也可以是更复杂的graph-level 池化函数。

1.2 WL-test

  1. 图同构问题graph isomorphism problem 是判断两个图在拓扑结构上是否相同。这是一个具有挑战性的问题,尚不知道多项式时间polynomial-time 的算法。

    除了某些极端情况之外,图同构的 Weisfeiler-Lehman(WL) test 是一种有效且计算效率高的算法,可用于各种类型的图。它的一维形式是 naïve vertex refinement ,它类似于 GNN 中的邻域聚合。

  2. WL-test 过程中,每个顶点都分配一个label。注意:这里的 label 和分类任务中的label 不同,这里的 label 更多的表示“属性”, 而不是“监督信息”。

  3. WL-test 对顶点邻域进行反复迭代,最终根据两个图之间的顶点label 是否完全相同,从而判断两个图是否同构的。

    WL-test 迭代过程如下:

    • 聚合顶点及其邻域的 label
    • 将聚合后的label 经过哈希函数得到不同的、新的label ,即 relabel

    如下图所示:

    • 首先将图中每个顶点初始化为 label = 1

    • 然后经过三轮迭代,最终:

      • 1 具有 1label = 82label = 72label = 9
      • 2 具有1label = 82label = 72label = 9

      因此我们不排除图1 和图 2 同构的可能性。

    下图的哈希函数为:

    注意:这里的 label 集合需要根据label 大小排序,并且每次哈希之后都需要分配一个新的 label

  4. 《Weisfeiler-lehman graph kernels》 根据 WL-test 提出了 WL subtree kernel 来衡量两个图的相似性。核函数利用 WL tet 的不同迭代中使用的顶点label 数作为图的特征向量。

    直观地讲,WL test 次迭代中顶点 label 代表了以该顶点为根的、高度为 的子树结构。因此 WL subtree kernel 考虑的图特征本质上是不同根子树的计数。

    如下图所示为一棵高度 WL subtree 。 这里 label = 8 的顶点代表一棵高度为 1subtree 模式,其中subtree 根节点的 label2、包含label=3label=5 的邻居顶点。

1.3 模型

  1. 我们首先概述我们的框架,下图说明了我们的思想:GNN 递归更新每个顶点的representation 向量,从而捕获网络结构和邻域顶点的representation ,即它的 rooted subtree 结构。

    在整篇论文中,我们假设:

    • 顶点输入特征来自于可数的范围countable universe
    • 模型的任何layerrepresentation 也是来自可数的范围。

    为便于说明,我们为每个representation vector (输入特征向量是第0 层的 representation vector)分配唯一的 labellabel 范围在 。即对于任意 ,都为它分配一个 label ,其中 函数为双射函数。

    然后顶点的邻域顶点 representation vector 就构成一个 multiset :由于不同的顶点可以具有相同的 representation 向量,因此同一个 label 可以在 multiset 中出现多次。

    下图中:

    • 左图:一个图结构的数据。
    • 中图:rooted subtree 结构,用于在 WL test 中区分不同的图。
    • 右图:如果 GNN 聚合函数捕获顶点邻域的 full multiset,则 GNN 能够以递归的方式捕获 rooted subtree 结构,从而和 WL test 一样强大。

  2. multiset 定义:multisetset 概念的推广,它允许包含相同的多个元素。正式地讲,,multiset 是一个 2-tuple ,其中:

    • 为底层的set ,它包含唯一distinct 的元素。
    • 给出这些元素的重复数量multiplicity
  3. 为研究 GNN 的表示能力,我们分析GNN 何时将两个顶点映射到 embedding 空间中的相同位置。

    直观地看,能力强大的 GNN 仅在两个顶点具有相同subtree 结构、且subtree 上相应顶点具有相同特征的情况下才将两个顶点映射到相同的位置。

    由于 subtree 结构是通过顶点邻域递归定义的,因此我们可以将分析简化为:GNN 是否将两个邻域(即两个multiset)映射到相同的 embeddingrepresentation

    能力强大的 GNN 绝对不会将两个不同的邻域(即representation 向量的 multiset)映射到相同的representation。这意味着聚合函数必须是单射函数。因此我们将 GNN 的聚合函数抽象为神经网络可以表示的、multiset 上的函数,并分析它们能否表示multiset 上的单射函数。

    接下来我们使用这种思路来设计能力最强maximally powerfulGIN。最后我们研究了主流的 GNN 变体,发现它们的聚合函数本质上不是单射的因此能力较弱,但是它们能够捕获图的其它有趣的特性。

1.3.1 定理

  1. 我们首先刻画characterize GNN-based 通用模型的最大表示能力 representational capacity

    • 理想情况下,能力最强大maximally powerfulGNN 可以通过将不同的图结构映射到 embedding 空间中不同的representation 来区分它们。这种将任意两个不同的图映射到不同 embedding 的能力意味着解决具有挑战性的图同构问题。即,我们希望将同构图映射到相同的 representation,将非同构图映射到不同的 representation

    • 在我们的分析中,我们通过一个稍弱的准则 slightly weaker criterion 来刻画 GNN 的表示能力:一种强大的powerful、启发式的heuristic、称作 Weisfeiler-Lehman(WL) 的图同构测试graph isomorphism test

      WL-test 通常工作良好,但是也有一些例外,如正规图regular graph。正规图是图中每个顶点的 degree 都相同。如:立方体包含四个顶点,每个顶点的 degree3,记作 4k3

  2. 引理2 :令 为任意两个非同构图non-isomorphic graph 。如果一个图神经网络 映射到不同的 embedding,则 WL-test 也会判定 是非同构的。

    证明:这里采用反证法。

    假设经过 轮迭代之后,图神经网络 满足 ,但是 WL-test 无法区分 是非同构的。这意味着在 WL-test 中从迭代0 到迭代 的顶点 label collection 都相同。

    具体而言, 在第 轮迭代都具有相同的 label multiset 、以及相同的顶点邻域label 集合 。其中 为顶点 WL-test 轮迭代中的 label 。否则WL-test 在第 轮迭代将具有不同的顶点 label collection 从而区分出 是非同构的。

    现在我们证明:如果 ,则有 ,其中 。我们用数学归纳法证明:

    • 时,结论显然成立。因为 WL-testGNN 都使用顶点的特征向量来初始化。如前所述,对于任意 ,都为它分配一个 label ,其中 函数为双射函数。因此如果 则有

    • 假设对于第 次迭代成立。

    • 考虑第 次迭代:如果对于 ,则有:

      根据第 次迭代的假设,我们有:

      由于两个图 采用同一个神经网络 来计算,因此它们使用相同的AGGREGATE 函数和 COMBINE 函数。因此相同的输入(如邻域特征)产生相同的输出。因此有:

      因此第 次迭代成立。

    因此如果 WL-test 顶点 label 满足 ,则有 对于任意迭代轮次 成立。因此对于 ,它们具有相同的顶点representation 集合 。由于 graph-level readout 函数对于顶点representation 集合是排列不变的permutation invariant,因此有 ,矛盾。

  3. 根据引理2,任何基于聚合的 GNN 在区分不同图结构方面最多和 WL-test 一样强大。

    一个自然的问题是:是否存在和 WL-test 一样强大的 GNN?在定理3 中,我们将证明:如果邻域聚合函数和 graph-level readout 函数是单射的,则得到的 GNNWL-test 一样强大。

  4. 定理3:令 为一个 GNN。在具有足够数量 GNN 层的条件下,如果满足以下条件,则 WL-test 判定为非同构的两个图 映射到不同的 embedding

    • 通过以下方程递归地聚合和更新顶点representation

      其中 函数、 函数都是单射函数。且 作用在 multiset 上。

    • graph-level readout 函数是单射函数。其中 readout 函数作用在顶点embedding multiset 上。

    证明:令 是满足条件的图神经网络。令 为任意两个图,其中 WL-test 次迭代后判定它们是非同构的。

    我们假设 更新顶点的 representation 为:

    其中 都是单射函数。

    假设 WL-test 应用一个预定义的单射函数 来更新顶点 label

    其中 不是从数据中学习,而是预定义的。

    接下来我们通过数学归纳法证明:对于任意迭代轮次 ,存在一个单射函数 ,使得

    • 时结论显然成立。因为 WL-testGNN 都使用顶点的特征向量来初始化。如前所述,对于任意 ,都为它分配一个 label ,其中 函数为双射函数。因此如果 则有 。此时 ,即 这个双射函数的反函数。

    • 假设对于 时也成立。

    • 现在考虑第 次迭代。根据:

      由于单射函数的复合函数也是单射函数,因此存在某个单射函数 ,使得:

      则有:

      因此复合函数 就是我们想要的单射函数。因此第 轮迭代成立。

    因此对于任意迭代轮次 ,总是存在单射函数 使得

    经过 次迭代之后,WL-test 判定 是非同构的,这意味着 label multiset 不同。则由于函数 的单射性injectivity 的顶点 embedding 集合 也是不同的。

  5. 对于可数集,单射性injectiveness 很好地描述了一个函数是否保持输入的唯一性distinctness 。顶点输入特征是连续的不可数集则需要进一步考虑。

    此外,刻画学到的 representationembedding 空间中的邻近程度(如果两个 embedding 不相等的话)也很有意义。我们将这些问题留待以后的工作,本文重点放在输入顶点特征来自可数集的情况,并仅考虑输出 representation 相等/不等的情况。

  6. 引理 4 :假设输入特征空间 是可数的countable。令 GNN 层可学习的函数, 。且 是定义在 size 有界的multiset 上的函数。则 的输出空间(即顶点 representation )也是可数的。

    证明:证明之前我们先给出一个众所周知的结论,然后将其简化:对于任意 是可数的。即:有限个可数集的笛卡尔积是可数的。我们观察到 是可数的,因为从归纳中可以清楚地得到证明。为了表明 是可数的,我们构造了一个双射函数

    现在回到我们的的引理证明。如果我们可以证明在可数集上的、size 有限的 multiset 上定义的任何函数 的值域range 也是可数的,则对于任意 上述引理成立。

    现在我们的目标是证明 的值域是可数的。

    首先,因为 是神经网络layer 定义良好well-defined 的函数,因此很明显 的映射是单射函数。这足以表明所有的 multiset 是可数的。

    由于两个可数集的并集也是可数的,因此 也是可数的,其中 dummy 元素且不在 中。

    正如 是可数的,则 也是可数的。则存在一个单射函数,对于某个 ,它将 中的 multiset 的集合映射到 。 我们如下构建这个单射函数:

    • 由于 是可数的,因此存在一个映射 使得将 映射到自然数。

    • 我们对于 中所有元素按照 排序,假设结果为 ,其中

    • 由于 multiset size 有界,则存在 ,使得 对于所有 成立。然后我们定义 为:

      其中最后 个元素填充 dummy element

    显然 是单射函数,因为对于任意 size 有界的 multiset ,仅当 。因此 的值域是可数的。

  7. 这里还值得讨论 GNN 在图结构判别能力上的一个重要优点,即:捕获图结构的相似性。

    • WL-test 中的顶点特征向量本质上是one-hot 编码,因此无法捕获 subtree 之间的相似性。

    • 相反,满足定理3 条件的 GNNsubtree 嵌入到低维空间来推广WL-test。这使得 GNN 不仅可以区分不同的结构,还可以学习将相似的图结构映射到相似的 embedding 从而捕获不同图结构之间的依赖关系。

      捕获node label 的结构相似性有助于泛化generalization,尤其是当subtree 的共现co-occurrence 很稀疏时、或者存在边噪音和/或顶点特征噪音时。

1.3.2 GIN

  1. 在研究出能力最强maximally powerfulGNN 的条件之后,我们接下来将设计一种简单的架构,即图同构网络Graph Isomorphism Network:GIN。可以证明GIN 满足定理3 中的条件。

    GINWL-test 推广从而实现了 GNN 的最大判别力。

  2. 为建模用于邻居聚合的 multiset 单射函数,我们研究了一种 deep multiset 理论,即:使用神经网络对 multiset 函数进行参数化。

    我们的下一个引理指出:sum 聚合实际上可以表示为 multiset 上的通用单射函数。

  3. 引理5:假设输入特征空间 是可数的。存在一个函数 ,使得 对于每个有界sizemultiset 是唯一的unique 。进一步地,任何 multiset 函数 可以分解为: ,其中 为某个函数。

    证明:我们首先证明存在一个映射 ,使得 对于每个有界sizemultiset 是唯一的 。

    由于 是可数的,因此存在一个映射 使得将 映射到自然数。因为 multiset 的基cardinality 是有界的,则存在自然数 使得对于所有 都有 成立。因此我们可以选择 为: 。 可以将这个 视为 one-hot 向量或 N-digit 数字的压缩表示。因此 multiset 的单射函数。

    是排列不变的permutation invariant,因此它是定义良好的 well-definedmultiset 函数。对于任意 multiset 函数 ,我们可以通过让 来构建这样的 。现在这样的 是定义良好的,因为 是单射函数。

  4. 引理5《Deep sets》中的结论从 set 扩展到 multisetdeep multisetdeep set 之间的重要区别是:某些流行的 set 单射函数 (如均值聚合)不再是 multiset 单射函数。

    通过将引理5 中的通用 multiset 函数建模机制作为构建块 building block,我们可以设想一个聚合方案,该方案可以表示单个顶点及其邻域的 multiset 上的通用函数,因此满足定理3 中的第一个条件。

    我们的下一个推论是在所有这些聚合方案中选择一个简单而具体的形式。

  5. 推论6:假设 是可数的。存在一个函数 ,使得无限多的选择 (包括无理数), 对于每个pair 都是唯一的 unique,其中 , 有界sizemultiset 。更进一步地,任何定义在这种 pair 上的函数 可以分解为: ,其中 为某个函数。

    证明:接着推论5 的证明过程,我们考虑 ,其中 的定义延续推论 5

    。我们的目标是当 是一个无理数时,对于任意 成立,其中

    我们用反证法证明。

    对于任意 ,假设存在 使得 但是 成立。考虑以下两种情况:

    • 此时 意味着

      根据推论5 该等式不成立,因为