报告：王 啸
撰文：熊宇轩
王啸，北京邮电大学，助理教授。研究方向为图神经网络、数据挖掘与机器学习。曾任清华大学计算机系博士后，天津大学博士，美国圣路易斯华盛顿大学联合培养博士，入选2020年微软亚洲研究院铸星学者。
在我们生活的世界中，图数据无处不在，我们可以用图来建模和描述我们的复杂系统。
从马克思主义哲学的角度来说，联系具有普遍性和客观性，所以正是因为联系的存在，万事万物都可以构建成图。
十年前，李国杰院士在「大数据研究的科学价值」一文中指出，复杂网络分析应该是数据科学的重要基石。「科学」研究的是普遍的现象、规律、真理，在数据科学研究领域中，我们可以将生物数据、交通数据、互联网数据、物理化学数据统一成图的形式，即关系网络。
图 1：网络表示学习
我们针对各种各样的图数据提出了相应的应用场景（例如，社区发现、节点分类等）。
为了将数据应用于具体的任务，我们往往首先需要对网络数据进行表征。
几十年以来，计算机从业者通常使用邻接矩阵来表示图和网络。随着表示学习、网络嵌入、深度学习的蓬勃发展，一系列图神经网络应运而生。如今，我们通过深度学习技术对图数据进行表示学习，并将学习到的表征用于后续的任务。
计算机科学家们基于前人在图信号处理领域（谱域）取得的一系列成果推导出了图神经网络的基本思路：在节点之间进行信息的传播聚合以及变换。
图2：GNN 的工作原理
如图 2 所示，图神经网络的每一层中进行的运算可以表示为：
其中， H^l 为第 l 层的节点表征，刻画了与节点相关的网络拓扑结构，信息在该拓扑结构上传播。最后，我们通过 θ 对节点特征进行提取和变换，再通过非线性激活函数得到下一层的节点表征 H^。
从另一个角度来看，我们可以将上式视为先通过 θ 对 H 节点的特征进行特征提取和变换，此后再在网络上进行信息的传播和聚合，从而得到更新后的新网络表征。我们将多个图神经网络层的操作叠加起来，就得到了深度图神经网络。
图 3：对 GNN 的思考
目前，图神经网络（GNN）在节点分类等任务上取得了目前最优的性能，该工作流程之所以奏效，主要原因包含以下几点：
（1）GNN 很好地利用了图的结构，以一种非常自然的方式获取了图上邻居节点的信息。如果我们将单层图神经网络层的操作叠加 N 次，便可以获取某节点 N 阶邻居的信息，这种聚合信息的方式非常灵活。
（2）GNN 得到的节点表示刻画了节点的低频信息，即图上节点之间共性的/相似的信息，节点之间差异较大的高频信息则会被过滤掉。我们往往认为节点与其邻居节点是相似的，而这种叠加传播聚合的过程恰好可以保留相似信息，相当于低通滤波器。
（3）在消息传播机制的框架下，研究者们提出了各种各样的图神经网络，可以有效利用邻居结构信息，同时保留低频信号。
然而，当前的图神经网络框架也存在一些不足，例如：
（1）并未充分利用网络中节点的特征结构。
（2）图神经网络起到低通滤波的作用，然而被过滤掉的高频信息是否也有用呢？如果有，在什么场景下需要高频信息呢？
（3）在众多的图神经网络模型背后，是否能通过统一的目标函数或其它方式描述图神经网络？
1
如何利用节点特征结构
为了利用特征结构，我们在网络拓扑上进行节点的特征传播和聚合，最后得到的嵌入融合了特征和拓扑的信息，理想的融合结果能够为下游任务提取出最相关的信息。
图 4：自适应的多通道 GCN
如图 4 中的 case 1 所示，图的拓扑结构是随机的，但是节点的特征具有很高的判别性，三类节点存在非常明显的特征结构。然而，实验结果表明，相较于多层感知机，GCN 并不能很好地提取节点的特征信息。这说明，纵然节点特征具有很强的判别性，如果节点的拓扑结构不够好，也无法很好地利用特征信息。
因此，我们希望能够有针对性地考虑特征本身的结构，同时考虑拓扑图和特征图。
我们通过 KNN 构造特征图，从而刻画特征视角下的结构信息。接着，我们在拓扑图和特征图上分别应用图神经网络，从而得到两种图特有的嵌入表示。此外，为了提取拓扑图和特征图之间的共性，我们设置了一个公共的图卷积分支，从而学习公共的嵌入。
图 5：AM-GCN 的注意力机制
我们通过注意力机制，动态地调整拓扑结构信息、特征结构信息、公共结构信息对最终的融合表征的贡献，自适应地学习出最适用于下游任务的表征。
图 6：实验结果
实验结果表明，使用针对拓扑结构的 GCN 和使用特征结构的 kNN-GCN 时的模型性能不分伯仲，因此特征结构也具有很大的信息量。
图 7：实验结果
通过对注意力进行分析，我们发现有时拓扑结构更重要，有时特征更重要。
图 8：图结构估计神经网络
上面的工作对特征结构利用进行了一定探索。然而，拓扑图本身也可能存在噪声或缺失，或不能很好地适用于下游的任务。为此，我们进一步提出了一种图结构评估网络，希望能够自动学习一种更适合图神经网络的图结构。
我们认为，好的图结构应该具有以下三点性质：
（1）站在巨人的肩膀上：充分利用网络科学和图数据科学的研究成果，将真实世界中图所具有的基本特征、先验信息利用起来。
（2）兼听则明，偏听则暗：在单一的度量方式下得到的结构可能存在偏差，图上的结构需要在多种度量下都成立。
（3）知己知彼，百战不殆：图结构的学习过程应该与图神经网络联系在一起。
我们通过贝叶斯框架将上述三个性质的引入统一为后验概率最大化问题，并使用 EM 算法对其进行求解。从贝叶斯框架的角度来看，第一个性质提供了先验信息；第二个性质通过观测结果推测图的结构，实际上提供了似然信息。在拥有先验信息和似然信息的情况下，自然地将上述问题转化为后验概率最大化问题。
图 9：实验结果
如图 9 所示，针对仿真数据上包含较多噪声的原始数据，我们可以利用拓扑图的结构，以及根据图神经网络的嵌入学习到的不同阶邻居的观测信息，最终得到如图 9 左下角所示的图结构。
2
如何利用其它频段的信息
目前，许多研究者已经证明，大部分的 GNN 相当于一种低通滤波器。那么，一个自然的问题是，我们是否需要利用低频信号之外的信息？应该如何利用？
图 10：如何利用低频信号之外的信息
如图 10 所示，图中各节点较为一致的信号为低频信号，图中节点之间差异较大的信号为高频信号。为了研究不同频段信号的作用，我们分别考虑同配性（节点与邻居较为相似）图和异配性（节点与邻居差异较大）图。
图 11：不同信息的作用
针对仿真数据，我们可以通过一系列调整，使图数据逐渐从同配性较高变化为异配性较高，并且在该过程中分别观察使用低频信号和高频信号对最终模型准确率的影响。实验结果表明，低频信号在同配性高的图上性能较好，而高频信号在异配性高的图上性能较好。
基于上述发现，我们提出两点思考：（1）如何在 GNN 中使用不同频段的信号？避免传统的 GNN 将低频信号之外的信号屏蔽掉。（2）我们往往缺乏对图的同配性/异配性程度的先验知识。如何自适应地选择合适的频段信号处理目标图数据？
传统的 GNN 在不考虑邻居节点相似度的条件下仅仅保留低频信息。但是我们希望节点保留相似邻居节点的低频信息，并且保留不相似邻居节点的高频信息，从而使网络具有更好的判别性。此外，由于缺乏对图的同配性/异配性程度的先验知识，我们希望能够自动判断保留邻居节点的低频信息还是高频信息。
如图 12 所示，我们提出的 FAGCN 模型可以自适应地提取最合适的频段的信息，在各种实验设定下能够获得稳定的高准确率。
图 12：FAGCN
具体而言，我们设置了两个增强的滤波器：
增强的低通滤波器为：
增强的高频的滤波器为：
图 13：两种增强的滤波器
如图 13 所示，对 GCN 而言，给定图信号 x，我们通过拉普拉斯矩阵的特征向量 U 将 X 变换到某种需要的频率下，并使用形为对角矩阵的参数在该频率下对信号进行滤波（即增强或抑制信号）。在该参数矩阵中，较大的元素可以增强对应的信号，较小的元素可以抑制对应的信号。最后，我们通过图傅里叶逆变换将信号转换回空域。
我们再看信号的频率怎么样保持，主要就是这个gcta起到的作用。我们就看我们这里的gcta是什么样子的？
图 14：增强滤波器效果示意图
对于增强的低通滤波器而言，可以展开为的形式，其中为特征值。如图 14(b)所示，通过观测其二阶幅值可以发现，当特征值较小（对应低频信号）时，图神经网络的幅值较调整前更大，即对低频信号有更好的增强；当特征值较大（对应高频信号）时，图神经网络的幅值较调整前更小，即对高频信息抑制的更加强烈。
同理，如图 14(d)所示，对于增强的高通滤波器而言，高频特征幅值被进一步增大，而低频特征幅值则被进一步抑制。
图 15：增强滤波器的空域解释
从空域角度来看，对于低通滤波器而言，其信号为，即将当前节点与邻居信号节点进行融合，从而得到新的当前节点的表征。在这种迭代的融合过程中，当前节点会与邻居节点越来越相似。
而对于高通滤波器而言，其信号,即当前节点的信息减去邻居节点的信息，从而消除当前节点和邻居节点之间的共性，仅仅保留差异较大的信息。
为了自适应地判断使用高频信息还是低频信息，我们设计了一种注意力机制来学习增强后的第频信号和高频信号的权重：
其中，为当前节点的信息，为邻居节点的信息。我们在聚合邻居信息的过程中，为邻居节点和当前节点的连边赋予了一个权重系数。由于该权重系数的符号可正可负，甚至可以为 0，因此我们可以将该操作视为广义的图注意力。
图 16：系数可视化结果
如图 16 所示，在常见的同配性较高的图上，大多数的系数为正；在异配性较高的图上，系数有正有负，甚至有的系数聚集在零点周围，即引入拓扑结构作用不大，使用节点特征就能够得到较好的效果。可见，FAGCN 模型十分灵活。
3
统一的目标函数
最后我们再来看我们关于统一目标的思考，希望能够找到一个式子，能够把很多的图神经网络囊括进来。
目前学术界涌现出了各种各样的图神经网络，我们希望通过一种统一的目标函数将大多数的图神经网络囊括在一起。
图 17：重新思考 GNN 统一框架
以 GCN、SGC、PPNP 等经典的图神经网络为例，它们的传播机制本质上都是在优化目标函数。
目标函数中的第二项可以展开为，它代表图拉普拉斯系数为正的项，使得当前节点与邻居节点的信息变得更加平滑。目标函数中的第一项代表学到的节点表征跟原本表征之间的关系，即节点特征的拟合项。不同的图神经网络对应不同的和,即图卷积核不同。
图 18：PPNP 传播机制示例
以 PPNP 为例，其传播的机制为优化目标函数：
由于目标函数对 Z 求偏导等于 0，我们可以推导出 PPNP 的传播机制为：
PPNP 之所以比 GCN 更容易缓解过平滑问题，是因为其目标函数相较于 GCN 在图正则的基础上加入了考虑 Z 与 H 之差的项，使得 Z 不仅进行了平滑操作，同时还要满足一定的与原本节点特征 H 的关系。
此外，PPNP 与 DAGNN 的目标函数非常的相似，二者的区别之一在于 PPNP 的图正则项的权重为人工设定的，而 DAGNN 的图正则项权重则是通过注意力机制学习得来。
图 19：设计 GNN 的新视角
通过对目标函数进行修改，我们可以推导出一些新的图神经网络。例如，若我们将 F_1、F_2 设置为具有不同滤波器的图卷积核，就可以推导出各种新的图神经网络。因此，在设计图神经网络时，除了从频域、空域的角度设计各种传播机制，还可以从目标函数的角度出发推导新的图神经网络架构。
由于微信公众号试行乱序推送，您可能不再能准时收到AI科技评论的推送。为了第一时间收到AI科技评论的报道， 请将“AI科技评论”设为星标账号，以及常点文末右下角的“在看”。
