开发个网站开票名称是什么,网页设计与制作教程第六版,一键优化大师下载,android studio的应用来源#xff1a;AI科技评论作者 | Mr Bear编辑 | 丛 末近年来#xff0c;随着图神经网络在各个领域的火热应用#xff0c;越来越多的学者试图从图论的角度对图神经网络的表达能力进行理论分析#xff0c;并基于这些理论分析开发出了性能强大的模型。然而#xff0c;在实际… 来源AI科技评论作者 | Mr Bear编辑 | 丛 末近年来随着图神经网络在各个领域的火热应用越来越多的学者试图从图论的角度对图神经网络的表达能力进行理论分析并基于这些理论分析开发出了性能强大的模型。然而在实际应用中这些在理论上非常强大的模型的性能往往会受到计算复杂度等因素的限制。本文作者 Michael Bronstein 是一名来 自帝国理工学院的教授同时也是 Twitter 图机器学习项目组的负责人。在本文中他深入浅出地介绍了近年来分析图神经网络表达能力的工作并介绍了他们对于该领域未来发展方向的思考。1图神经网络和 WL 图同构测试之间的关系众所周知传统的前馈神经网络多层感知机是一种通用函数近似器它们能够以任意的准确率逼近任意的平滑函数。对于近期兴起的图神经网络来说其表征性质还不太为人所知。在实验中我们经常可以看到图神经网络在某些数据集上性能优异但同时又在另一些数据集上表现令人失望。为了探究造成这种现象的根本原因我们不得不思考一个问题图神经网络究竟有多强大在探究这一问题的过程中我们所面临的一个挑战是实际应用场景下使用的图往往是连续结构和离散结构节点、边特征、连通性的组合。因此该问题可以被表述为不同的形式。一种可能的形式化定义是图神经网络是否能够区分不同类型的图结构。在图论中这是一种被称为「图同构问题」的经典问题旨在判断两个图在拓扑意义上是否等价。两个同构的图拥有相同的连通性其差别仅仅可能是节点的排列不同。稍令人惊讶的是我们尚不知晓精确的图同构问题的复杂度级别。该问题在多项式时间内不可解它也不是一个 NP 完全NPC问题。有时我们将其复杂度称为一种特殊的「GI 级」GI class。1、Weisfeiler-Lehman 测试Boris Weisfeiler 和 Andrey Lehman 于 1968 年发表的具有开创性意义的论文「The reduction of a graph to canonical form and the algebra which appears therein 」提出了一种高效的启发式算法我们现在将其称为「WL 测试」。最初人们认为 WL 测试可以在多项式时间内求解图同构问题。但一年之后人们就举出了一个反例。然而从概率意义上说似乎 WL 测试对于几乎所有的图都有效。图 1在两个同构图上执行 WL 测试的示例。包含弧线的 hash 圆括号代表多重集。在着色情况不再变化后算法会终止并给出输出结果颜色直方图。若将两图输入给该算法得到的输出相同则说明两图可能同构。WL 测试是建立在迭代式的图重着色图论中的「着色」指的是一种离散的节点标签基础上的在初始状态下每个节点的颜色均不相同。在每一步迭代中算法会聚合节点及其邻居节点的颜色并将它们表征为多重集然后将聚合得到的颜色多重集通过 Hash 函数映射到某种唯一的新颜色上。当达到稳定的着色状态各节点着色状态不再变化后算法终止。当算法终止后若两图的着色情况不同则我们认为它们「非同构」。如果两图着色情况相同它们可能但并不一定是同构的。换句话说WL 测试是图同构的必要非充分条件。有一些非同构的图在接受 WL 测试后得到的着色情况也是相同的而在这种情况下 WL 测试就失效了因此我们只能认为它们「可能同构」。下图展示了其中的一种可能性 图 2显然WL 图同构测试会为上面的两个非同构图生成相同的着色结果此时 WL 测试失效。在化学领域中这两个图分别代表两种不同的化合物「decalin」左图和「bicyclopentyl」右图的分子结构。2、图同构网络GINKeyulu Xu 等人发表的论文「 How powerful are graph neural networks?」和 Christopher Morris 等人发表的论文以及 Thomas 在他至少两年前撰写的博客「GRAPH CONVOLUTIONAL NETWORKS」中注意到WL 测试与图消息传递神经网络有惊人的相似之处它们都在图上进行了一种类似于卷积的操作。相关论文/文章链接https://arxiv.org/abs/1810.00826https://tkipf.github.io/graph-convolutional-networks/在一个消息传递层中每个节点的特征会以聚合其邻居节点特征的方式被更新。对聚合和更新操作的选择是十分重要的只有使用多重集的单射函数才能使其与 WL 算法等价。在前人的研究中「取最最大值」或「取均值」等聚合操作都是一定弱于 WL 的能力它们甚至不能区分非常简单的图结构 图 3通过「取最大值」操作无法区分左图、中图、右图通过「取均值」聚合函数可以区分左图和中图、通过「取最大值」和「取均值」操作均无法区分左图和右图。这是因为通过这些方法从黑色节点的邻居中聚合而来的特征将会是相同的。Xu 提出了一种聚合和更新函数的选择方案它使得消息传递神经网络与 WL 算法等价该网络被称为「图同构网络」GIN。该网络和标准的消息传递神经网络一样强大。但是GIN 不仅仅是一种新的网络架构其主要影响在于它通过一种简单的设定形式化定义了图神经网络表达能力的问题这种设定与图论中的经典问题相关。该网络的思路也启发了许多后续的工作。3、Weisfeiler-Lehman 层次结构使用更加强大的图同构测试是扩展 Xu 和 Morris 等人工作的一个方向。因此László Babai 提出了 k-WL 测试这是 WL 算法在高阶上的扩展它在 k 元组上进行操作而非操作单个节点。除了 1-WL 和 2-WL 测试是等价的(k1)-WL 始终严格强于 k-WLk≥2即对于某些图而言 k-WL 测试失效而 (k1)-WL 测试可以成功判定图是否同构但反之则不然。因此k-WL 是一种层次结构的或随着 k 的增大而逐渐更加强大的图同构测试有时被称为「Weisfeiler-Lehman 层次结构」。我们可以设计出遵循 k-WL 测试的图神经网络这种网络是一定比消息传递架构更加强大的。Morris 等人在论文「 Weisfeiler and Leman go neural: Higher-order graph neural networks 」中提出了第一种这样的架构 k-GNN。相关论文链接https://aaai.org/ojs/index.php/AAAI/article/view/4384/4262传统的消息传递神经网络和这种高阶图神经网络之间最关键的区别在于由于 k-WL 算法在节点的 k 元组上进行操作所以这种高阶图神经网络是非局部的non-local。这对算法的实现及其计算复杂度和存储复杂度都有重要的影响k-GNN 需要 ????(nᵏ) 的存储空间。为了降低复杂度Morris 基于在局部邻居节点中的信息聚合机制设计了一种 k-GNN 的局部版本然而其表达能力要稍微弱于 k-WL。Haggai Maron 提出了一种稍微有些不同的高阶图架构。他基于 k-阶张量定义了一类不变性图网络IGN说明它们与 k-WL 测试一样强大。IGN 是根据 k-WL 的另一种变体衍生而来与 k-GNN 相比IGN 在计算复杂度方面更具优势。具体而言与 3-WL 等价的 IGN「仅仅」具有 n 的平方级的计算复杂度这可能是唯一一种实际可用的严格强于消息传递架构的图神经网络但它的复杂度与消息传递架构的线性复杂度仍然有很大的差距。从理论的角度来看可证明的强大图神经网络的相关工作提供了一种严谨的数学框架它可以帮助研究者们解释并对比不同的算法。许多后继的工作使用图论和分布式局部算法中的各种方法对这些工作的结果进行了扩展。然而从实用的角度来看这些新架构几乎没有产生重大的影响例如Bengio 等人提出的最新的对比基准说明近期这些可证明的强大算法实际上性能要差于之前的技术。在机器学习领域中这并非是一种不寻常的状况。实际上理论和实践之间往往有很大的鸿沟。其中一种可能的解释是这是由对比基准测试本身的缺陷所导致的。但是更深层次的原因也许是更好的表达能力并不一定意味着更好的泛化性能有时甚至恰好相反。此外在具体的应用中图同构模型可能并不能正确地捕获图相似性的实际概念。可以肯定的是这一领域的工作硕果累累它搭建了连通其它学科的桥梁并引入了以前在图上的深度学习领域中没有使用过的方法。2超越 Weisfeiler-Lehman将子结构用于可证明的具有强大表达能力的图神经网络图 4图中的子结构最近发表的具有开创性意义的论文「 How powerful are graph neural networks?」和「 Weisfeiler and Leman go neural: Higher-order graph neural networks 」将图神经网络和图同构测试联系了起来并且观察到了消息传递机制和 WL 测试之间的相似性。「WL 测试」是一种对基于图论的层次化迭代式算法的统称这类算法可以在多项式时间内求解被用于判定图是否同构。k-WL 测试根据某些邻居节点的聚合规则在每一步中对图中顶点的 k 元组重新着色直到达到稳定的着色状态才终止算法。若两图的色彩直方图不同则我们认为它们非同构否则两图可能但不一定同构。 相关论文链接https://arxiv.org/abs/1810.00826 https://aaai.org/ojs/index.php/AAAI/article/view/4384/4262消息传递神经网络最多与 1-WL 测试又称「node colour refinement」算法同等强大。因此它甚至无法区分非常简单的非同构图实例。例如消息传递神经网络无法对三角形进行计数而这种三角形模体motif被认为在社交网络中扮演者重要的角色它与表示用户「紧密联系」程度的聚类系数息息相关。我们可以设计表达能力更强的图神经网络来模拟越来越强大的 k-WL 测试。然而这样的架构会导致计算复杂度很高引入大量的参数。更重要的是这样的架构往往还需要非局部的操作这使得它们并不具备可行性。图 5无法被 1-WL 检测区分但是可以被 3-WL 检测区分开来的非同构图示例。这是由于 3-WL 可以对三角形模体进行计数。 因此基于 WL 层次结构的可证明的强大图神经网络要么性能较弱但较为实用要么性能强大但并不实用。在作者 Michael Bronstein看来应该有另外一种简单的的方式设计既高效有可证明的强大图神经网络我们在与 Giorgos Bouritsas 和 Fabrizio Frasca 等人合作完成的论文「Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting」中提出了这种方法。 相关论文链接https://arxiv.org/abs/2006.092521、图子结构网络图子结构网络的思路实际上十分简单在概念上与位置编码或图元核graphlet描述子相似让消息传递机制感知局部的图结构使其能够根据末端节点之间的拓扑关系以不同的方式计算消息。这是通过向消息传递函数传递与每个节点关联的附加结构描述子来实现的这种描述子是通过子图同构计数实现的。通过这种方式我们可以将图中的节点划分到不同的等价类中这些等价类反映了每个图内部的节点之间以及跨越不同图的节点之间共享的拓扑特性。我们将这种架构称为「图子结构网络」GSN。该网络与标准的消息传递神经网络拥有相同的算法设计、存储复杂度以及计算复杂度但是它在构造结构描述子之前增加了一个预计算步骤。选择需要计数的子结构对于 GSN 的表达能力以及预计算步骤的计算复杂度都是至关重要的。对于包含 n 个节点的图在对包含 k 个节点的子结构进行计数的过程中最差的计算复杂度为 ????(nᵏ)。因此这与高阶图神经网络模型或前文中提到的 Morris 和 Maron 所提出的模型相类似。然而GSN 相较于其它方法具有以下优势1对于「路径」或「环」等类型的子结构GSN 可以以明显较低的复杂度进行技术2具有高昂计算开销的步骤仅仅作为预处理执行一次因此不会影响网络的训练和推理正如在消息传递神经网络中一样网路的训练和推理会保持线性。训练和推理时的存储复杂度也是线性的3最重要的是GSN 的表达能力与 k-WL 测试是不同的在某些情况下GSN 的表达能力要更强。2、GSN 有多强大子结构计数赋予了 GSN 比标准的消息传递神经网络更强的表达能力。首先需要说明的是GSN 的表达能力取决于使用的图的子结构。与 k-WL 测试中的层次结构相同我们可以基于对一种或多种结构进行计数得到 GSN 的不同的变体。通过使用比星型图更复杂的结构GSN 可以获得一定强于 1-WL或等价的 2-WL更强的能力因此也比标准的消息传递架构更强。当使用四元团4-clique时GSN 的能力至少不会弱于 3-WL。在下面的示例中GSN 在强正则图上仍然有效而 3-WL 则失效了图 6包含 16 个顶点的非同构强正则图的示例每个顶点的度为 6每 2 个邻接的顶点拥有 2 个共同邻居。3-WL 测试在本例中失效然而使用四元团的 GSN 可以区分这两个图。在左图被称为「Rooks graph」中每个节点都恰好被包含在一个四元团中。右图Shrikhande graph则包含三元最大团三角形。更一般来说对于各种 ????(1) 阶的子结构而言只要不能通过 3-WL 对其进行计数那么就存在 GSN 能够成功区分而 3-WL 无法区分的图。尽管我们找不出反例但是原则上这种反例是存在的——这也正是我们稍有顾虑地仅仅将 GSN 的能力表述为「至少不会弱于 3-WL」的原因。当 k-WL 中的 k 取更大值时上述结论也成立上图中的强正则图可以被归纳为「k-iosregular」它们是 (k1)-WL 测试失效的实例。使用恰当结构的 GSN 也可以区分这些示例。因此GSN 的表达能力如下图所示图 7GSN 在 WL 层次结构之外。在使用恰当的结构时例如特定规模的团或环GSN 的能力至少不弱于 k-WL。一般来说GSN 的能力究竟有多强呢这仍然是一个开放性的问题。图重构猜想Graph Reconstruction Conjecture假定了根据一张图的所有删除某些节点后得到的子结构恢复出该图的概率。因此如果图重构猜想是正确的那么使用包含 n-1 个节点组成的子结构的 GSN 就可以正确地测试任意图的同构性。然而到现在为止人们只在节点数 n≤11 的图上证明了图重构猜想。其次对如此大的子结构进行计算也是不切实际的。一个更有趣的问题是对于「小型」结构大小为 ????(1) 常数阶与节点数 n 无关而言是否存在相似的结果。我们的实验结果证明使用小型子结构例如环、路径、团的 GSN 对于区分强正则图是有效的而这对于 WL 测试来说是十分困难的。最重要的是GSN 是构建在标准的消息传递架构之上的因此继承了其局部性和线性复杂度。GSN 的超参数包括为了构建结构描述子而计数的结构。也许实际的应用会在「需要的表达能力」、「能保证这种表达能力的结构大小」、「计算复杂度」之间进行权衡。 图 8使用考虑了长度 k≥6 的环结构的 GSN在 ZINC 数据集中显著提升了对分子图的化学性质的预测性能。ZINC 数据集被制药公司用于候选药物的虚拟筛查。这种环结构在有机分子中大量存在。在实验中我们观察到不同的子结构会为不同的问题和数据集带来帮助。因此对于子结构的选择可能需要视具体问题而定。幸运的是在某些实际应用中我们往往知道何种子结构是有用的。例如在社交网络中三角形和高阶的团是很常见的并且有明确的「社会学」解释。在化学领域中环是一种非常常见的模式例如五元、六元芳环在大量的有机分子中都存在。下图显示了一种我们大多数人都很熟悉的示例咖啡因的分子结构。 图 91,3,7—三甲基黄嘌呤俗称咖啡因是一种包含五元、六元环分别表示为红色和黄色的换装化合物。 3超越 Weisfeiler-Lehman近似同构性与度量嵌入 基于图论的在多项式时间内能够求解的算法为图同构问题提供了一种必要不充分条件。在图深度学习领域中研究人员已经证明了消息传递神经网络和 1-WL 测试的能力相当。采用高阶、更强大的 k-WL 测试可以实现具有高计算复杂度的图神经网络此时网络涉及非局部操作而在实际应用程序中这是不实用的。Michael Bronstein 近期在论文「Improving graph neural network expressivity via subgraph isomorphism counting 」中介绍了一种不同的方法它摒弃了 WL 层次结构转而采用了一种消息传递机制这种机制可以感知环、团、路径等局部图结构。这使得我们的图神经网络拥有吸引人的局部性以及标准消息传递架构的低计算复杂度。同时作者可以证明该网络比 2-WL 更强大并且至少不弱于 3-WL。这种视角开启了图论领域中尚未在图神经网络表达性方面被探索过的开放性问题的深层次的联系。相关论文链接https://arxiv.org/abs/2006.09252故事到这里还远未结束。作者表示他相信我们可以通过改变看待问题的角度做得更好。1、近似同构虽然研究人员已经基于图神经网络与图同构问题的联系产生了一些重要的思路但是这种设定本身还是相当具有局限性的。我们可以认为图神经网络试图寻找图嵌入 f(G) 这种嵌入具有我们期望的特性即 f(G)f(G′) 当且仅当 G~G′。不幸的是由于可以通过 WL 测试是判定图同构的必要非充分条件上述我们期望得到的特性只有一个方向能说得通当 G~G′ 时 f(G)f(G′)但反之不一定成立两个非同构的图可能会得出相同的嵌入。在实际应用中我们很少处理完全同构的图而是处理如下图所示的「近似同构」的图图 10近似同构图示例(G, G′)、(G, G″)都是非同构的。但是 G 和 G′ 只有一条边不同而 G 和 G″ 有五条边不同因此 G 和 G′ 拥有比 G 和 G″ 之间「更强的同构性」。我们可以用一种度量指标 d 来量化「近似同构」的概念当两图不相似时 d 的值较大而当两图很相似时 d 的值较小。「图编辑距离」或「Gromov-Hausdorff」距离是两种可能的 d 的示 例。需要注意的是该度量标准可以被定义为d(G,G′)0 当且仅当 G~G′即说明两个同构图难以被区分。保距嵌入isometric embedding问题对于所有的 G, G′有 |f(G)−f(G′)|d(G,G′) (♠)试图使用图嵌入之间的欧氏距离 |.| 替代图的距离我们要求这两种距离是相等的在本例中嵌入 f 是「保距的」。图神经网络表达能力的相关工作说明我们可以在多项式时间内在 WL 测试有效的一系列图上构建满足 (♠) 的图嵌入。而这一设定似乎限制性太强。第一也许我们无法设计一种局部的高效算法保证 (♠) 对于所有图都成立。第二图同构问题中的性质并不一定在近似同构图上成立在 d(G,G′)0 的情况下。一般而言更相似的图在嵌入空间中反而较为不相似的情况也是可能存在的即 d(G,G′)d(G,G″) 但 |f(G)−f(G′)||f(G)−f(G″)|。但是另一方面对度量的形式化定义却提供了更大的灵活性。我们不必要求 (♠) 一定成立可以通过规定「度量膨胀」metric dilation的界对其进行松弛当 c≥1 时c⁻¹ d(G,G′) ≤ |f(G)−f(G′)| ≤ c d(G,G′) (♣)它可以被表示为嵌入 f 的双 Lipschitz 常数。这意味着该嵌入不会使用比 c 大的因子「拉长」或「缩短」真实的图距离。这种嵌入被称为「近似保距」。我们希望得到独立于图特别是与定点数无关的界 c。请注意由于对于同构的图 G~G′我们有 d(G,G′) 且 f(G)f(G′)因此图同构是 (♣) 的特例。如前文所述在所有图上实现这种近似保距是不可能的。然而我们可以允许额外的度量失真 ε从而使模型 (♣) 可以被进一步松弛 当 c≥1时c⁻¹ d(G,G′)−ε ≤ |f(G)−f(G′)| ≤ c d(G,G′)ε (♦)它设置了一个同构图之间距离的容忍度。如果可以满足(♦)的图要比可以满足 (♠) 的图多得多那么对于许多应用程序来说这是一个很小的代价。图 11近似保距嵌入问题2、概率近似保距我们可以以「概率近似正确」PAC的形式将近似同构问题重新写为以下的概率化表达????( c⁻¹ d(G,G′)−ε ≤ |f(G)−f(G′)| ≤ c d(G,G′) )1−δ其中「近似」的思想体现在度量膨胀 c 上而「概率」指的是对于一些图的分布而言界 (♦)有很高的概率 1−δ 成立。这种设定可能会比确定性近似保距嵌入问题更容易分析。3、连接连续和离散的结构最后图神经网络表达能力的问题主要还是关注于图的拓扑结构。然而在大多数实际的应用中图也会包含节点层面或边层面上的特征这些特征往往被表征为向量。度量框架通过定义一种恰当的带属性的图之间的距离很自然地处理了以上两种结构。再次声明人们需要牢记大部分近期研发的有关图神经网络表达能力的工作都是建立在图论领域的经典结果之上的。将这些工作拓展到度量几何等其它的数学领域中似乎是一条很有前景的道路它们很有可能在不久的将来结出硕果。原文链接https://towardsdatascience.com/expressive-power-of-graph-neural-networks-and-the-weisefeiler-lehman-test-b883db3c7c49未来智能实验室的主要工作包括建立AI智能系统智商评测体系开展世界人工智能智商评测开展互联网城市云脑研究计划构建互联网城市云脑技术和企业图谱为提升企业行业与城市的智能水平服务。 如果您对实验室的研究感兴趣欢迎加入未来智能实验室线上平台。扫描以下二维码或点击本文左下角“阅读原文”
