在本文中，作者认为图同构设置对于分析图神经网络的表达能力来说太过有限，并建议基于度量嵌入进行更广泛的设置。

前文回顾

《图深度学习：成果、挑战与未来》
《图神经网络的表达能力与 Weisfeiler-Lehman 测试》
《如何设计局部的、计算效率高的、可证明的图神经网络？》

本文最初发表在 TowardsDataScience 博客，经原作者 Michael Bronstein 授权，InfoQ 中文站翻译并分享。

Weisfeiler-Lehman（WL）测试【1】是图论多项式时间迭代算法层次结构的总称，为图同构提供了必要但不充分的条件。在图深度学习的背景下，消息传递神经网络被证明与 1-WL 测试一样强大【2】。进行更高阶、更强大的 k-WL 测试会导致图神经网络复杂度和非局部运算【3】，这在实际应用中是不切实际的。

我们在最近的一篇论文【4】中介绍了一种不同的方法，即打破 Weisfeiler-Lehman 层次结构，并采用一种能够感知局部图结构（如环、团和道路）的消息传递机制。这使得图神经网络具有标准消息传递架构的诱人的局部性和低复杂度，同时被证明比 2-WL 更强大，至少不低于 3-WL。这样的观点为图论中的开放性问题打开了深层次的联系，而这些问题是以前在图神经网络表达力方面从未探索过的。

故事到此结束了吗？我相信，我们可以通过改变对这一问题的看法，我们还可以做得更好，我将在本文中讨论几个方向。

近似同构。虽然从与图同构问题的联系中，人们对图神经网络的表达能力有了重要的认识，但这种设置本身是相当有限的。图神经网络可以看做是试图找到一个嵌入 f(G) 的图，具有期望性质 f(G)=f(G’) 当且仅当 G~G’。不幸的是，由于 Weisfeiler-Lehman 测试是图同构的必要条件，但不是充分条件，因此只有一种方法可行：如果 G~G’，则 f(G)=f(G’)，但反过来并不一定成立：两个非同构图可以导致相等的嵌入。

在实际应用中，我们很少处理完全同构的图，而是处理近似同构的图，如下图所示：

近似同构图的示例：图中两对 G、G’ 和 G、G" 是非同构的。但是，G 和 G’ 只有一条边不同，因此比 G 和 G"“更同构”，而 G 和 G" 有五条边不同。

量化“近似同构”概念的是当方式是度量 d 的形式，如果两个图相似，则度量 d 就大，否则，度量 d 就小。图编辑距离【5】或 Gromov-Hausdorff 距离【6】是两个可能的例子。重要的是，将度量定义为 d(G,G’)=0，当且仅当 G~G’，这意味着两个同构图是不可区分的【7】。关于等距嵌入问题：

对于所有 G、G’，$|f(G)-f(G’)|=d(G,G’)$ (♠)

尝试用用欧几里得距离 |.| 代替图的距离，以使两个距离相等（在这种情况下，嵌入 f 被称为“等距”或“保持距离”）。对图神经网络表达能力的研究表明，在 Weisfeiler-Lehman 测试成功的图族上，可以用多项式时间构造满足 (♠) 的图嵌入。这个设置似乎限制太多了。首先，很有可能不可能设计出一个局部的、有效的算法来保证所有图的 (♠)【8】。其次，图同构问题对近似同构图不提供任何保证，在这种情况下， d(G,G’)>0。原则上是可能的，例如，更多相似的图在嵌入空间中相似度较低，即 $d(G,G’)<d(G,G")$，但 $|f(G)-f(G’)|>|f(G)-f(G")|$。

另一方面，度量公式提供了更多的灵活性。不要求 (♠) 完全成立，而是可以通过约束度量扩张来放松它。

可以通过限制度量扩张来放松它，而不是要求 (♠) 完全成立。

对于 $C\geqslant 1$，则 $c^{-1} d(G,G’) ≤ |f(G)−f(G’)| ≤ c d(G,G’)$ (♣)

这可以表示为嵌入 f 的双李普希茨（bi-Lipschitz）常数 c。这意味着嵌入不会“拉伸”或“收缩”距离 d 的 Ground Truth 图超过因子 c，理想情况下，因子 c 应尽可能接近于 1。

注意，图同构是 (♣) 的特例，因为对于同构图 G~G’，有 d(G,G’)，从而 f(G)=f(G’)。如上所述，这不可能对所有图都能实现。相反，模型 (♣) 可以进一步放宽，允许附加度量失真 ε。

对于 $C\geqslant 1$，则 $c^{-1}d(G,G’)−ε ≤ |f(G)−f(G’)| ≤ c d(G,G’)+ε$ (♦)

它设置了同构图之间的可以相距多远的公差。在许多应用程序中，这是一个很小的代价，如果一个应用程序能够满足 (♦) 比 (♠) 大得多的图族。

近似等距嵌入问题。

可能近似等距。近似同构问题可以改写为“可能近似正确”（probably approximately correct，PAC）形式的概率陈述：

$𝖯( c^{-1}d(G,G’)−ε ≤ |f(G)−f(G’)| ≤ c d(G,G’) )>1−δ$

其中，“近似”是在度量扩张 c 的意义上理解的，而“可能”是对于图的某些分布来说，边界（♦）具有很高的概率 1−δ【9】。这种设置可能比确定性近似等距嵌入问题更容易分析。

桥接连续和离散结构。最后但并非不重要的是，图神经网络表达力问题主要集中在图的拓扑结构上。然而，在大多数实际应用中，图还具有节点或边的特征或属性，通常表示为向量【10】。度量框架通过定义属性图之间的适当距离自然地处理这两种结构。

作为最后的意见，我要提醒大家也应该记住，大多数关于图神经网络表达能力的研究著作都是建立在图论经典成果基础上的最近进展。扩展到其他数学领域，例如度量几何学，似乎是一条很有前途的途径，有望在不久的将来结出硕果。

参考文献

【1】《图的标准型化简及其代数》（The reduction of a graph to canonical form and the algebra which appears therein)，B. Weisfeiler、A. Lehman，1968 年，英译本。

【2】《图神经网络有多强大？》（How powerful are graph neural networks?），K. Xu 等人，2019 年，Proc.ICLR。

【3】《可证明的强大图神经网络》（ Provably powerful graph neural networks），K. Xu 等人，2019 年，Proc.ICLR。

【4】《利用子图同构计数提高图神经网络的表达能力》（Improving graph neural network expressivity via subgraph isomorphism counting），G. Bouritsas 等人，2020 年，arXiv:2006.09252。

【5】《用于模式识别的属性关系图间的距离度量》（A distance measure between attributed relational graphs for pattern recognition），A. Sanfeliu、K.-S. Fu，1983 年，IEEE Trans. Systems, Man, and Cybernetics (3):353–362。

【6】《黎曼变量的结构度量）（Structures métriques pour les variétés riemanniennes），M.Gromov，1981 年。

【7】从技术上讲，d 是一个伪度量，可以视为模同构关系图的商集 𝒢⧵~ 上的度量。

【8】我之所以说“可能”，是因为图同构问题是否存在多项式时间解尚未可知。这种假设算法似乎不太可能具有实际的时间和空间复杂性。

【9】在 N. M. Kriege 等人之前，有人曾使用概率度量设置来分析图核。《图核理论表达性的性质测试框架》（A property testing framework for the theoretical expressivity of graph kernels），2018 年，Proc. IJCAI。

【10】虽然 Weisfeiler-Lehman 框架在技术上适用于彩色图，但它仅限于具有离散特征集的节点。

作者介绍：

Michael Bronstein，伦敦帝国理工学院教授，Twitter 图机器学习研究负责人，CETI 项目机器学习领导、Twitter 图机器学习负责人、研究员、教师、企业家和投资者。

原文链接：

https://towardsdatascience.com/beyond-weisfeiler-lehman-approximate-isomorphisms-and-metric-embeddings-f7b816b75751

创作场景

图神经网络表达能力不足时，我们能做什么？