图算法
目录：
正文：
##引言
什么是GNNs
图神经网络（GNNs）广泛应用于图的表征学习，其遵循领域聚合框架，
通过递归聚合和转换相邻节点的特征向量来计算节点的表征向量。
已经提出了许多GNN的变体，并在节点和图形分类任务上取得比较好的结果。
然而，尽管GNN使图形表征学习发生了革命性的变化，但是，对其表示属性和局限性的理解还很有限。
这里提出一个分析GNN捕获不同图结构表现力的理论框架。
描述了各种流行的GNN变体的判别能力。如Graph Convolutional Networks（图卷积神经网络）和GraphSAGE
并表明他们无法学会区分某些简单的图结构。
这里开发了一个简单的体系结构，可以证明其在GNNs类中是最具表现力的，
并且它和Weisfeiler-Lehman（图同构测试）方法一样强大。
在许多图分类基准测试上，通过经验验证了该理论发现，并证明本论文的模型达到了最佳的性能、
介绍
学习图结构数据，例如：分子、社会、生物和金融网络等，需要有效的表征图的结构。
最近，研究者们对使用Graph Neural Network(GNN)方法来对图进行表征学习产生了极大的兴趣。
GNN大部分都遵循**循环递归邻域聚合（或者消息传递）的模式，
其中每个节点聚合其相邻节点的特征向量以计算其新的特征向量。
在k轮聚合迭代后，通过其转换的特征向量来表示该节点，该向量捕获节点的k-hop网络邻节点的结构信息。
然后，可以通过pooling来获得整个图结构的表征，例如对图中所有节点的表征向量求和。
许多基于不同neighborhod aggregation 的GNN变体和graph-level的pooling scheme已经被许多学者提出。
根据经验，这些GNNs已经在许多任务中达到最佳的性能，如节点分类，链接预测和图分类。
然而，新GNN的设计主要是基于经验直觉，启发式和实验试错。
对于GNN的性质和局限性，目前理论层面的解释还比较少。
GNN的表征能力的正式分析还是有限的。
本文提出了一个分析GNN表征能力的理论框架。
从形式上描述了不同GNN变体在学习表征和区分各种图结构方面的表现力。
该框架是受GNNs和WLL测试（Weisfeiler-Lehman图同构测试）紧密联系的启发，
WL测试通过聚合给定节点的邻近节点的特征向量迭代更新其特征向量。
WL测试的强大之处是其注入聚合（injective aggregation）更新，它映射不同节点的邻近节点到不同的特征向量。
主要观点是，如果GNN的聚合模式具有高度的表现力和能够为注入函数建模的话，它就同WL测试一样具有强大的区分能力。
为了数学形式化上述观点，首先抽象出一个节点的邻近节点的特征向量作为多重集，该集合中可能有重复元素。
然后，在GNNs中的邻域聚合（neighbor aggregation）可以抽象为多集上的函数。
我们严格学习不同多集函数的变体，并从理论上描述其识别能力。即不同的聚合函数可以区分不同的多重集。
越具有区分力的多重集函数，GNN的潜在表征能力就越强。
本论文的主要结构总结如下：
-
在区分图结构方面，GNN和WL测试能力一样强大
-
在建立领域聚合（neighbor aggregation）和图池函数（graph pooling）的情况下，GNN和WL测试一样强大
-
识别无法通过流行的GNN变体区分的图结构。例如GCN（kipf&welling， 2017）和GraphSAGE（Hamilton等，2017a），
并且我们对基于GNN模型可以捕获的各种图结构进行了精确的描述。
- 开发了一个简单的神经网络结构，图同构网络（graph Isomorphism network）GIN，并证明其判别/表征能力等同于WL测试
在图分类数据集上，通过实验验证我们的理论，其中GNN的表达能力对于捕获图结构至关重要。
特别是，我们对基于各种聚合函数的GNN性能进行了对比。
结果证实了最强大的GNN（文中的GIN）具有很强的表征能力，可以近乎完美的拟合训练数据。
然而较弱的GNN变体有严重的欠拟合问题。
此外，在许多图分类的基准测试集上，它的表征能力和性能优于其他的GNNs。
预备知识
首先，我们总结一些常见的 GNN 模型，顺便介绍一下相关数学符号的含义。
假设 G = (V, E) 表示一个图，图的节点向量用 X(v) 表示，其中，v ∈ V 。
有两个比较感兴趣的任务：
（1）节点分类，其中每个节点 v ∈ V 都有一个相关的标签 y(v)，目标是学习节点 v 的表征向量 h(v)，节点 v 的标签可以被函数 y(v)=f(h(v)) 所预测。
（2）图分类，其中给定一组图{G1, …, GN }⊆ G 及其标签{y1, …, yN } ⊆ Y，
我们的目标是学习一个表征向量 h(G)，它有助于预测整个图的标签 y(G) = g(h(G))。
图神经网络
GNNs利用图结构和节点特征 X(v) 来学习一个节点的表征向量 h(v)，或者整个图的表征向量 h(G)。
新式的 GNNs 都遵循领域聚合（neighborhood aggregation）策略， 其中我们通过聚合它的邻近节点的表征向量来迭代更新节点的表征向量。
在 k 次迭代后，节点的表征可以在它的 k-hop 网络邻居中捕获结构信息。
形式上，GNN 的第 k 层是：
\[a^{(k)}_v = AGGREGATE^{(k)}({h^(k-1)_u: u \in N(v)}), h^{(k)}_v = COMBINE^{(h^{(k-1)}_v, a^{(k)}_v)}\]其中，\(h^{k}(v)\) 是节点 v 在第 k 的迭代 / 层的特征向量。
我们初始化 h^{0}(v)=X(v)，N(v) 是与 v 节点邻近的一组节点。
在 GNNs 中选择函数 AGGREGATE{k}(·) 和 COMBINE{k}(·) 非常关键。
已经提出了许多用于聚合的体系结构。
在 GraphSAGE 的 pooling 变体（Hamilton et al., 2017a），AGGREGATE 函数形式如下：
\[a^{(k)}_v = MAX({ReLu(W·h^{(k-1)}_u), \forall u \in N(v)})\]其中，W 是可以学习的矩阵，MAX 表示一个 element-wise 的 max-pooling。
| 在 GraphSAGE 的 COMBINE 步是一个线性映射的连接 $$W·[h^{k-1}(v) | a^{k}(v)]$$。 |
在图卷积网络中（GCN）(Kipf & Welling, 2017)，element-wise 的 mean pooling 被替代，AGGREGATE 和 COMBINE 步集成在一体如下：
\[h^{(k)}_v = ReLu(W`MEAN{h^{k-1}_u, \forall \in N(v) \bigcup {v}})\]许多其他的 GNNs 可以类似的表示为 Eq. 2.1 (Xu et al., 2018; Gilmer et al., 2017)。
对于节点分类问题，最后一次迭代的节点表征向量 \(h^{K}(v)\) 用来做预测。
对于图分类问题，READOUT 函数从最后一次迭代中聚合节点特征来获取整个图的表征向量 h(G)：
| h_G = READOUT({h^{(K)}_v | v \in G}) |
READOUT 函数可以是一个简单的置换不变函数，例如求和或者 graph-level 级别的 pooling 函数 (Ying et al., 2018; Zhang et al., 2018)。
Weisfeiler-Lehman 测试
图同构问题指的是验证两个图在拓扑结构上是否相同。
这是一个具有挑战性的问题：因为现在很难知道计算的时间复杂度。
WL（Weisfeiler-Lehman）测试是一种非常有效的一测试图同构的方法，它可以区分各种图。
在 1 维的情况下，它类似于在 GNN 中的领域聚合。
假设每个节点都有一个分类标签，WL 测试（1）迭代聚合节点标签和他们的邻近节点，
（2）将聚合的标签 hash 成唯一的新标签。
如果在某些迭代中两个图的节点标签不同，则该算法判定它们是不同的。
基于 WL 试验，Shervashidze 等人（2011）提出了 WL 子树内核来测量图之间的相似性。
内核使用在 WL 测试不同迭代中的节点标签计数作为图的特征向量。
直观的来看，在 WL 测试的第 k 次迭代中，一个节点的标签表征该根节点的高度为 k 的子树结构（Figure 1）。
因此，WL 子树所考虑的图的特征本质上是图中不同根子树的计数。
理论框架：概述
我们首先概述了分析 GNNs 表达能力的框架。
GNN 递归地更新每个节点的特征向量，以捕获其周围其他节点的网络结构和特征，即其根子树结构（图 1）。
在本文中，我们假设节点输入特征是一个宇宙内可数的数。
对于有限图，我们可以递归地证明在任何固定模型的深层节点特征向量也是一个宇宙内可数的数。
为了简化符号，我们可以为每个特征向量分配一个唯一的标签∈{a，b，c……}。
然后，一组相邻节点的特征向量形成多重集：同一元素可以出现多次，因为不同的节点可以具有相同的特征向量。 多重集定义：多重集是集合的一个广义概念，它允许其元素有多个实例。
更正式地讲，多重集是一个二元组 X =（S，m），其中 S 是由其不同元素组成的 X 的基础集合，而 m：S→N(≥1) 给出了元素的多样性。
为了分析 GNN 的表达能力，我们分析了 GNN 何时将两个节点映射到嵌入空间中的相同位置。
直观地说，最强大的 GNN 仅当两个节点具有相同的子树结构，并且在对应的节点上具有相同的特征时，才会将它们映射到相同的位置。
由于子树结构是通过节点邻域递归定义的（图 1），因此当 GNN 将两个邻域映射到相同的嵌入时，我们可以递归地减少我们的分析。
最强大的 GNN 永远不会将两个不同的邻域（即，特征向量的多重集）映射到相同的位置。 这意味着它的聚合方案是单射的。
因此，我们将 GNN 的聚合方案抽象为其神经网络可以表示的多重集合上的一类函数，并分析它们是否能够表示单射的多重集函数。
接下来，我们使用这种推理开发一个最强大的 GNN。
在第 5 节中，我们研究了流行的 GNN 变体，并发现它们的聚合方案本质上不是单射的，因此功能较弱，但它们可以捕获图形的其他有趣属性。
构建强大的图神经网络
理想情况下，GNN 能够
（1）通过将它们映射到嵌入空间中的不同位置来区分不同的图结构，以及
（2）在嵌入空间中捕获它们的结构相似性。在本文中，我们主要关注第一部分，我们将简要讨论第二部分。
然而，将不同的图映射到不同的嵌入空间的能力意味着可以解决图同构问题。
在我们的分析中，通过一个稍微弱一点的标准来描述 GNN 的表达能力：
魏斯费勒 - 雷曼（WL）图同构测试，除少数特例外，该测试通常工作得很好，特别是规则图（Cai 等人，1992；Douglas，2011；Evdokimov&Ponomarenko，1999）。
引理 2. 设 G1 和 G2 为任何非同构图。
如果一个图神经网络 A: G → R(d) 遵循领域聚合方案，将 G1 和 G2 映射到不同的嵌入，Weisfeiler-Lehman 图同构检验也判定 G1 和 G2 不是同构的。
因此，在区分不同图方面任何基于聚合的 GNN 都至多与 WL 测试一样强大。一个自然的问题是，在原则上是否存与 WL 测试一样强大的 GNN？
我们在定理 3 中得到的答案是肯定的：如果邻居聚合和图池化函数是单射的，那么得到的 GNN 就像 WL 测试一样强大。
定理 3. 设 A：G→R(d) 是一个遵循邻域聚合方案的 GNN。
通过足够的迭代，如果满足以下条件，则 A 可以将通过 Weisfeiler-Lehman 测试的图 G1 和 G2 为非同构图映射到不同的嵌入：
a)A 每次迭代聚合更新节点特征向量
$$h^{(k)}_v = \Phi(h^{(k-1)}_v, f({h^{(k-1)}_u : u \in N(v)}))
b）A 的图级别的 readout 函数，运行在节点特征的多重集上｛h(k)(v)｝，是一个单射函数。
在可数集上，单射性很好地描述了一个函数是否保留了输入的区别性。
在不可数集上，节点特征是连续的，内射性和判别性的概念被“削弱”。
在本文中，我们假设输入节点特征来自可数集。
鉴于输入节点特征的可计数性假设，人们可能会问，GNN 更深层的节点特征的可数性是否仍然适用？ 引理 4 表示是，即可数性可以跨层传播。
引理 4. 假设输入特征空间 X 是可数的，g(k) 是由 GNN 的第 k 层参数化的函数，k=1,..,L。
其中，g(1) 被定义在有限多重集 X ⊂ X 上，g(k) 的范围，节点的隐含特征 h{k}(v) 空间，在 k=1,…,L 都是可数的。
在这里，除了区分不同的图之外，还值得讨论 GNN 的一个重要好处，也就是说，捕捉图结构的相似性。
注意，WL 测试中的节点特征向量本质上是一种独热编码（one-hot 编码），因此不能捕获子树之间的相似性。
相反，满足定理 3 标准的 GNN，通过学习将子树嵌入低维空间来推广 WL 测试。
这使得 GNN 不仅可以区分不同的结构，而且可以学习将相似的图结构映射到相似的嵌入，并捕获图结构之间的依赖关系。
捕捉节点标签的结构相似性对泛化有帮助，特别是在不同的图中当子树的共现稀疏或存在噪声边和节点特征时（Yanardag 和 Vishwanathan，2015）。
图异构网络（GIN）
接下来，我们开发了一个可证明满足定理 3 中条件的模型，从而推广了 WL 测试。
我们将结果体系结构命名为 Graph Isomorphism Network（GIN）。为了模拟领域聚合的单射多重集函数，我们发展了一个“深多重集”的理论，即用神经网络参数化通用多重集函数。
我们的下一个引理表明，求和聚合器可以代表多重集合的单射，事实上，是多重集上的通用函数。
对于有限图，在任何固定模型的深层节点特征向量是一个宇宙内可数的数
节点输入特征：一个宇宙内可数的数
为每个特征向量分配一个唯一的标签 \(\in {a,b,c,...}\)
多重集：
一组相邻节点的特征向量。同一元素可以出现多次，因为不同的节点可以具有相同的特征向量。
一个二元组 X=(S, m)，其中S是由其不同元素组成的X的基础集合，而m：S->N(>=1)给出了元素的多样性。
多重集是集合的一个广义概念，它允许其元素有多个实例。
最强大的GNN，聚合方案是单射的
因此，将GNN的聚合方案抽象为一类函数，神经网络可以表示的多重函数集合上的一类函数
并分析它们是否能够表示单射的多重集函数。
附录
引理2：
设G1和G2为任何非同构图。
如果一个图神经网络 A:G -> R(d)遵循领域聚合方案，将G1和G2映射到不同的嵌入。
WL图同构检验也判定G1和G2不是同构的
证明：
假设：k次迭代以后，一个GNN算法A，得到 \(A(G_1) \neq A(G_2)\)，而WL测试不能确定\(G_1\)和\(G_2\)是不同构。
在WL测试里，从0到k迭代：\(G_1\)和\(G_2\)总是有相同的节点标签集合。
特别的是，因为\(G_1\)和\(G_2\)的【WL节点标签\({l^{(i)}_v}\)有相同的集合】，同样【节点邻居\({(l^{(i)}_v, {l^{(i)}_u: u \in N(v)})}\)有相同集合】
否则，当不同的多重集获得唯一的新标签时，WL测试将在迭代i+1中获得不同的\(G_1\)和\(G_2\)节点标签集合。
WL测试总是将相邻节点的不同多重集重新标记为不同的新标签。
可以看到，当\(G=G_1或G_2\)，如果WL节点标签\(l^{(i)}_v=l^{(i)}_u\)，我们总能得到在每次迭代GNN的节点特征都满足\(h^{(i)}_v = h^{(i)}_u\)
当迭代次数i=0时，这很显然成立的原因是：WL和GMM是以相同的节点特征开始的。
假设在第j次迭代依然成立，那么对于任意\(u,v,l^{(j+1)}_v=l^{(j+1)}_u\)，满足：
\[(l^{(j)}_u, {l^{(j)}_w: w \in N(v)})=(l^{(j)}_u, {l^{(j)}_w: w \in N(u)})\]在我们的假设下，第j次迭代，可以得到：
\[(h^{(j)}_u, {h^{(j)}_w: w \in N(v)})=(h^{(j)}_u, {h^{(j)}_w: w \in N(u)})\]在GNN的加总过程中，会应用相同的AGGREGATE和COMBINE。
当输入相同时，比如节点特征，会得到相同的输出。
因此：\(h^{(j+1)}_v=h^{(j+1)}_u\)。
通过归纳，
如果WL节点标签\(l^{(i)}_v=l^{(i)}_u\)，那么在每次迭代i中总能得到\(h^{(i)}_u=h^{(i)}_v\)。
这一点其实表明，创建了一个有效映射函数\(\Phi\)，使得对于任意\(v \in G\)，都有\(h^{(i)}_v=\Phi(l^{(i)}_v)\)
由此可知，\(G_1和G_2\)具有相同的WL邻居标签的多重集，\(G_1和G_2\)也拥有相同的GNN领域特征集合：
\[{(h^{(i)}_v, {h^{(i)}_u: u \in N(v)})}={(\Phi(l^{(i)}_v), {\Phi(l^{(i)}_u): u \in N(v)})}\]因此，\({h^{(i+1)}_v}\)是相同的。
尤其是，对于\(G_1和G_2\)，GNN节点特征有相同的集合。
由于图级读出函数相对于节点特征集合是排列不变的， 从而A（g1）=A（g2）。因此，我们达成了一个矛盾。
利用CNN来学习任意图结构
https://www.leiphone.com/news/201606/aewwFhhu9SCeIqUG.html
论文摘要
许多重要问题可以划归到图像数据学习框架里。我们针对学习卷积神经网络提出了一个框架，可以适用于任何图形。这些图形可以是无向的，定向的，也可以是具有离散和连续节点和边缘属性。类似于基于图形的卷积网络，可以再本地化的可连接输入区域上允许，我们提出了一种普遍方法，可以从图形中提取本地化的可连接区域。使用既定的基准数据集，我们展示了带有最先进图形内核的学习功能表现，是具有竞争力的，同时，它们的计算效率也是非常高的。
一、概述
在这篇论文中，我们的目标是卷积神经网络解决一大类基于图形的学习问题。我们想到了以下两个问题：
-
给定一个图形集合，学习一项功能，可以用于在未见图形上进行分类和回归。任意两个图的节点不一定是对应的。举个例子，集合中的每一个图形都可以“模型化”一种化合物，输出也可以是一个功能，将未见组件定位到癌细胞的活性水平。
-
给定一个大图，学习图形表现，可以用来推断看不见的图形属性，比如节点类型或是缺少的边。我们提出了一个框架，用于学习定向和无向图形类别的表现。这些图形可以有多个离散和连续属性的节点和边，可能有多个类型的边。和识别图像的卷积神经网络类似，我们利用输入的图像构建了局部连接的邻域。这些邻域构建效率高，可以充当卷积网络的感知域，让卷积网络有成效地学习图像特征。
| ICML论文 | 利用CNN来学习任意图结构 |
图1：一个3*3感受域的卷积神经网络。该域可以覆盖图形被移动，从左到右，从上到下，通过使用一个特定跨越（这里：1）和零填充（这里：0）(a).被感受域所读取的值被转化成一个现行层，并反馈送至一个卷积架构(b). 被创建的感受域和感受域的形状的节点序列完全由超参数决定。
| ICML论文 | 利用CNN来学习任意图结构 |
图2. 建议架构的一个图例通过一个图形标记程序，从图中选择一个节点序列。对于序列中的一些节点，局部领域图将会被拼装且正则化。正则化的邻域也将被用作感受域，并且和现有的卷积神经网络组件进行整合。
此处建议的方式根据卷积神经网络（CNN）识别图像的理论（福岛邦彦，1980年； Atlaset等人，1988年；LeCun等人，1998年、2015年)而设计，并将这些理论拓展应用在任意图上。
图1展示了卷积神经网络识别图像的局部连接感知域。
一个图像可以表现为正方形格网的图形，其节点就代表像素。现在，一个卷积神经网络可以被视为穿越一个节点序列（图1（a）中的节点1到4，每个节点之间形成大小固定的邻域图（图1（b）的3乘3格网））。邻域图可以充当感知域，通过像素节点解读特征值。由于像素的空间顺序并不清晰，邻域的图从左到右、从上到下生成节点序列，这种序列的确定过程是独特的。自然语言处理（NLP）的问题也同样是独一无二的，因为每个句子（及其句法树）都决定了一些词语的序列。然而，对多个图形集合来说，某个特定问题的顺序（空间、时间或是其他顺序）是缺失的，图形的节点并不对应。在这种情况下，必须解决两个问题：(i)确定邻域产生的节点序列；(ii) 计算邻域图形的正则化，即一种从图形特征转换到矢量特征的独特映射。每个输入图形首先确定邻域生成的节点（及其顺序）。在生成这些节点的邻域里都能提取一个k节点，并进行正则化。也就是说，以固定的线性顺序，进行空间的独特映射。经过正则化的邻域可以成为某个考量节点的感受域。最终，卷积层和稠密层等特征学习组成部分与正则化的邻域相结合，形成卷积神经网络的感受域。
图2展示了PATCHY-SAN结构。该结构在运用现有方式时有诸多优势：
首先，它效率很高，很容易并行，可以应用于大图形；第二，对于计算生物学和社交网络分析等多个领域的应用来说，可视化网络主题非常重要（Milo等人, 2002），PATCHY-SAN支持特征可视化，那样可以深入了解图形结构特征；第三，PATCHY-SAN并未创造另一个图核，而是学习依靠应用的特征，无需做特征工程的工作。我们的理论贡献在于，界定图形及其复杂性的正则化问题；提供一种比较方法，比较各种图形集合的图形标记方式；显示PATCHY-SAN归纳图像卷积神经网络的结果。我们通过运用标准的数据集展现出，和高级水平的图核相比，经过学习图像的卷积神经网络不但有效，而且效率很高。
Weisfeiler-Lehman
Weisfeiler-Lehman算法通常被用在解决图的相似性问题上，虽然算法要解决的问题聚焦在Graph层面上，但是其立足点还是在节点上，
如果我们能够找到一种衡量节点独立性（unique）的方法，那么我们就可以将图视作一个包含这些独立性节点的集合，两张图的相似性可以转化为两个集合的Jaccard相似度。
何谓节点独立性？其实在前面《浅析图卷积神经网络》中，我们谈到图中的一个节点同时具有attribute和structure的信息，需要同时从这两方面来对节点作Identifaction。
很自然地，structure信息还是通过节点的邻居来刻画，Identifaction可以通过hashing来高效判断。如果设Φ(vi)表示节点vi的特征信息（attribute），那么更新函数可量化为：
\[\Phi(v_i)=h(\Phi(v_i)), {\Phi(v_j)|v_j \in N(v_i)}\]其中，h是一个哈希函数，理想的性质是满足仅有相同的输入才有相同的输出，这里相当于对每个节点都计算了一个指纹（fingerprint），
算法里需要不断地迭代更新上式，直到独立性节点个数不再上升，但实际为了计算效率与效果的综合考虑迭代2～3轮就可以了。
下面举例说明Wisfeiler-Lehman算法
给定两图G和G'，其中每个节点都已经打上了标签（实际应用中，有些时候我们并拿不到节点的标签，这时可以对节点都标上“1”这个标签）
要比较G和G'的相似性，我们来看看weisfeiler-lehman算法是怎么做的：
1、aggregate邻居节点的标签得到一个标签的字符串，对字符串进行升序排列。
2、对字符串进行哈希处理，这里生成了一个一一映射的字典，这一步也可以使用其它的字符串哈希函数，只要保证碰撞率尽量小就可以。
- 将哈希过的值重新赋值给相应的节点
这样第一轮迭代之后，G={6、6、8、10、11、13}，G'={6，7，9，10，12，13}于是利用Jaccard公式就可以计算出G和G`的相似度了，如果需要更严格的对比，可以持续迭代上述过程。
参考文献： https://chuansongme.com/n/2829470051132
https://mp.weixin.qq.com/s/s6E2vV1KrQDI4SeAnkYTKw
https://github.com/weihua916/powerful-gnns/blob/master/models/mlp.py