While Graph Neural Networks (GNNs) have achieved remarkable results in a
variety of applications, recent studies exposed important shortcomings in their
ability to capture the structure of the underlying graph. It has been shown
that the expressive power of standard GNNs is bounded by the Weisfeiler-Leman
(WL) graph isomorphism test, from which they inherit proven limitations such as
the inability to detect and count graph substructures. On the other hand, there
is significant empirical evidence, e.g. in network science and bioinformatics,
that substructures are often intimately related to downstream tasks. To this
end, we propose "Graph Substructure Networks" (GSN), a topologically-aware
message passing scheme based on substructure encoding. We theoretically analyse
the expressive power of our architecture, showing that it is strictly more
expressive than the WL test, and provide sufficient conditions for
universality. Importantly, we do not attempt to adhere to the WL hierarchy;
this allows us to retain multiple attractive properties of standard GNNs such
as locality and linear network complexity, while being able to disambiguate
even hard instances of graph isomorphism. We perform an extensive experimental
evaluation on graph classification and regression tasks and obtain
state-of-the-art results in diverse real-world settings including molecular
graphs and social networks. The code is publicly available at
this https URL

本论文提出了一种基于子结构编码的、具有拓扑感知的信息传递方案 —— Graph Substructure Networks，并通过理论分析和实验评估证明其优于 Weisfeiler-Leman 测试，并在分子图和社交网络等多个领域取得了最先进的结果。