论文标题
用图神经网络区分图是多么困难？
How hard is to distinguish graphs with graph neural networks?
论文作者
论文摘要
图形神经网络的标志是他们有能力区分其输入的同构类别。这项研究得出了在消息通话模型（MPNN）中图形同构的分类变体的硬度结果。 MPNN包括当今使用的大多数图形神经网络，当节点获得唯一功能时，它是通用的。该分析依赖于引入的沟通能力度量。容量衡量网络节点在向前传球期间可以交换多少信息，并取决于架构的深度，消息大小，全球状态和宽度。结果表明，MPNN的容量需要与节点数量线性生长，以便网络可以区分树木并四二次地与一般连接图。派生的界限涉及最坏情况和平均案例的行为，并适用于具有/没有独特功能和自适应架构的网络 - 它们也比简单参数所给出的更高两个数量级。一项涉及12个图形分类任务和420个网络的实证研究揭示了实际绩效和理论预测之间的强烈一致性。
A hallmark of graph neural networks is their ability to distinguish the isomorphism class of their inputs. This study derives hardness results for the classification variant of graph isomorphism in the message-passing model (MPNN). MPNN encompasses the majority of graph neural networks used today and is universal when nodes are given unique features. The analysis relies on the introduced measure of communication capacity. Capacity measures how much information the nodes of a network can exchange during the forward pass and depends on the depth, message-size, global state, and width of the architecture. It is shown that the capacity of MPNN needs to grow linearly with the number of nodes so that a network can distinguish trees and quadratically for general connected graphs. The derived bounds concern both worst- and average-case behavior and apply to networks with/without unique features and adaptive architecture -- they are also up to two orders of magnitude tighter than those given by simpler arguments. An empirical study involving 12 graph classification tasks and 420 networks reveals strong alignment between actual performance and theoretical predictions.
