Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting

By Giorgos Bouritsas, Fabrizio Frasca, Stefanos P. Zafeiriou, Michael M. Bronstein. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020

547 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Materials Chemistry, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/6360aaece0d6bf153183b9ecd075f42f7b127cc9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Materials Chemistry

In Statistical and Nonlinear Physics

Citations in the corpus

Graph Neural Networks with Learnable Structural and Positional Representations (2021, methodology): “, 2020b; Dwivedi & Bresson, 2021), or can inform about specific sub-structures (Bouritsas et al., 2020; Bodnar et al., 2021).”
DiGress: Discrete Denoising diffusion for graph generation (2022, background): “For example, Bouritsas et al. (2022) proposed adding counts of substructures of interest, and Beaini et al. (2021) proposed adding spectral features, which are known to capture important properties of graphs (Chung & Graham, 1997).”
Benchmarking Graph Neural Networks (2023, background): “, 2022), (ii) improving expressive power of GNNs (Valsesia et al., 2021; Bouritsas et al., 2022; Bevilacqua et al., 2021), (iii) pooling mechanisms (Mesquita et al.”
Discovering Invariant Rationales for Graph Neural Networks (2022, methodology): “Although structure features are shown to be helpful in mitigating feature distribution shift, DIR still performs better than GSN.”
Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks (2021, background): “In particular, similarly to Bouritsas et al. (2020), we benchmark it on 9 synthetic datasets comprising families of Strongly Regular (SR) graphs.”
Long Range Graph Benchmark (2022, unknown): “For instance, the task in the ZINC molecular dataset [29, 14] is associated with counting local structures and it has been revealed that a substructure-counting based model [7] would optimally require counts of 7-length substructures for the best performance.”
Recipe for a General, Powerful, Scalable Graph Transformer (2022, methodology): “Expressivity in terms of sub-structure identification and the Weisfeiler-Leman (WL) test is achieved via providing a rich set of PE/SE, as proposed in various works [3, 34, 15, 5, 6] and detailed in Section 3.”
Weisfeiler and Lehman Go Cellular: CW Networks (2021, methodology): “[10], if the L2-distance between the embeddings of two complexes is larger than = 0.”