Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology-NIPS2019

理解图神经网络再学习图拓扑表示方面的能力-NIPS2019

一、引言

1、问题引入

• Despite their practical success, most GCNs are deployed as black boxes feature extractors for graph data. It is not yet clear to what extent can these models capture different graph features. One prominent feature of graph data is node permutation invariance: many graph structures stay the same under relabelling or permutations of the nodes.
  尽管GCN取得了实际成功，但大多数GCN都部署为图形数据的黑匣子功能提取器。 不清楚GNN究竟在多大程度上能够捕获不同的图特征。

2、方案

• we analyze the representation power of GCNs in learning graph topology using graph moments, capturing key features of the underlying random process from which a graph is produced.
  使用图矩来分析GCNs的表达能力，图矩可以捕获图的随机生成过程的关键特征。
• We argue that enforcing node permutation invariance is restricting the representation power of GCNs.
  强制节点置换不变性限制了GCN的表示能力
• We derive the representation power in terms of number of hidden units (width), number of layers (depths), and propagation rules.
  我们根据隐藏单元数（宽度）、层数（深度）和传播规则推导了表示能力。
• We show how a modular design for GCNs with different propagation rules significantly improves the representation power of GCN-based architectures.
  我们展示了具有不同传播规则的GCN模块化设计如何显著提高基于GCN的体系结构的表示能力。
• We apply our modular GCNs to distinguish different graph topology from small graphs.
  我们应用我们的模块化GCN来区分不同的图拓扑和小图。

3、贡献

• We reveal the limitations of graph convolutional networks in learning graph topology. For learning graph moments, certain designs GCN completely fails, even with multiple layers
  and non-linear activation functions.
  我们揭示了图卷积网络在学习图拓扑中的局限性。对于学习图矩，某些设计GCN完全失败，即使是多层和非线性激活函数。
• we provide theoretical guarantees for the representation power of GCN for learning graph moments, which suggests a strict dependence on the depth whereas the width plays a weaker
  role in many cases
  我们为学习图矩的GCN表示能力提供了理论保证，这表明它严格依赖于深度，而在许多情况下宽度的作用较弱
• We take a modular approach in designing GCNs that can learn a large class of node permutation invariant function of of the graph, including non-smooth functions. We find that having different graph propagation rules with residual connections can dramatically increase the representation power of GCNs.
  我们在设计GCN时采用模块化方法，可以学习一大类图的节点置换不变函数，包括非光滑函数。我们发现，使用不同的带有剩余连接的图传播规则可以显著提高GCN的表示能力。
• We apply our approach to build a “graph stethoscope”: given a graph, classify its generating process or topology. We provide experimental evidence to validate our theoretical analysis
  and the benefits of a modular approach.
  我们应用我们的方法来构建一个“图形听诊器”：给定一个图形，对其生成过程或拓扑进行分类。我们提供实验证据来验证我们的理论分析和模块化方法的好处。

二、图矩学习

• 给定一组由未知随机图生成过程生成的图，从图中学习需要我们准确地推断底层生成过程的特征。
• graph moments [5, 23] characterize the random process from which the graph is generated.
  图矩[5,23]描述了生成图的随机过程

2.1、Graph moments

• p阶图矩Mp是邻接矩阵A的p阶多项式的集合平均。
• 图矩编码图的拓扑信息，对图的着色和哈密顿性非常有用。例如，graph power 计算长度为p的节点i到j的路径数。
• 对于大小为N的图，A有N个特征值。将特征值分解应用于图矩，我们得到。图矩对应于特征值∧的分布，特征值∧是表征图生成过程的随机变量。图矩是节点置换不变的，这意味着节点的重新标记不会改变度的分布、给定长度的路径或三角形的数量。
• 学习图矩的问题是学习函数逼近器F，使F:A→ Mp（A），同时保持节点置换不变性。
• BA模型：

1. 不同的图生成模型依赖于不同的图矩
2. BA模型，添加新边的概率与度成正比，度是一阶图矩。
3. 然而，在扩散过程中，平稳分布取决于归一化邻接矩阵?A及其对称化版本?As，定义如下:
   

2.2 Learning with Fully Connected Networks

• 度是一阶图矩
• 给定一组图，每个图20个节点
• 输入图的邻接矩阵，学习节点的度
• 对于全连接（FC）神经网络，鉴于其通用逼近能力，这是一项相当简单的任务[19]。
• 然而，FC网络将邻接矩阵视为向量输入，忽略了底层的图结构，需要大量的训练样本和许多参数才能正确学习度
• 比如，最好的情况，它要求隐藏单位的数量级与图形中的节点数相同
• 因此，FC网络在学习图矩方面效率很低，这促使我们研究更强大的替代方案：图卷积网络。
  

2.3 Learning with Graph Convolutional Networks

• f是传播规则，hi是节点i的属性，W是权重矩阵，b是偏差。

• 因为我们对图形拓扑感兴趣，所以忽略节点属性并将hi设置为1。

• 注意，权重W仅耦合到节点属性h，而不耦合到传播规则f（A）。

• 我们使用具有不同传播规则的单层GCN来学习BA图的节点度。

• 对于线性激活σ（x）=x，学习节点度的解为f（A）=A，W=1和b=0。

• 对于形式为的高阶图矩，单层GCN必须学习函数。

• 如图2所示，f（a）=a的单层GCN可以完美地学习度，即使对于一个N=20个节点的图，只有50个训练样本（图2a）。请注意，GCN只需要1个隐藏单元就可以学习，这比FC网络的效率要高得多。
  

• 然而，如果我们将学习目标设为，如图2b所示，无论样本大小如何，同一GCN在学习图矩时完全失败。这说明了由于排列不变性约束，GCN的局限性。

• 接下来，我们分析了这一现象，并为GCN的表现力提供了理论保证。

三、理论分析

1、FCC学习图矩的定理

• 要了解图形拓扑，完全连接的层需要大量隐藏单元。以下定理用节点数N、矩阶数p和隐单元数N表征了全连通神经网络学习图矩的表示能力。
  

• 如果FC网络完全参数化N×N邻接矩阵A中的每个元素，则输入的维数必须为d=N*N。如果FC网络允许节点之间的权重共享，则输入维度将为d=N

• 定理1说明了FCC学习图矩需要的参数非常多

2、CGN学习图矩定理

• 一般来说，对于一组随机图，具有n

• n>=p的GCN可以学习p阶图矩
  

• 定理2表明，GCN的表示能力强烈依赖于层数（深度），而不是图的大小（宽度）。它还强调了残余连接的重要性。通过在多个GCN层中引入剩余连接，我们可以学习具有线性激活的图矩的任何多项式函数。有趣的是，在[34]中提出的图同构网络（GIN）使用了以下传播规则
  
  

四、模块化设计

• 我们将不同的GCN传播规则视为不同的“模块”，并考虑了三个重要的GCN模块。图3a）显示了单个GCN层的设计，我们在其中组合了三个不同的GCN模块。模块的输出被连接并馈送到节点FC层

• 图3b）显示了带有剩余连接的多层GCN的设计。我们将模块化的GCN层堆叠在彼此的顶部，并连接来自每一层的剩余连接。最后一层聚合所有前一层的输出，包括剩余连接。
  

• 请注意，我们的设计不同于图形注意网络[31]中的多头注意机制，它对所有模块使用相同的传播规则。

• 然而，我们对多层GCN的理论分析表明，以前馈方式简单地将GCN层堆叠在彼此的顶部是相当有限的。

• 如果我们从每一层的输出中添加剩余连接到最终的聚合层，我们将能够逼近图矩的任何多项式函数。

• 我们的模块化方法证明了使用专门的神经网络进行建筑设计的重要性。由于置换不变性，前馈GCN的表示能力非常有限，在学习图拓扑时可能会失败。然而，通过仔细设计，包括不同的传播规则和剩余连接，可以提高GCN的表示能力，以捕获高阶图矩，同时保持排列不变性。

五、相关工作

六、总结

• 了解GCNs可以/不能学习的内容。关注图的矩，这是图拓扑的一个关键特征。
• 我们发现，GCN在学习图矩方面有相当大的限制，多层GCN即使在非线性激活的情况下也无法学习图矩。
• 理论分析提出了一种在保持排列不变性的情况下设计图神经网络的模块化方法。模块化GCN能够区分不同的图形生成模型，以获得令人惊讶的小图形。
• 对于学习图形矩，深度比宽度影响更大。更深层次的GCN更能学习高阶图矩。
• 还强调了将GCN模块与剩余连接相结合在提高GCN表示能力方面的重要性。
• 总结：主要就是这种结合多个传播规则的思想，还有这种堆叠多层GCN加残差模式的设计逼近任意（学习图矩的）多项式函数可以借鉴。