Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting.

Area of Science:

• Graph Neural Networks
• Graph Representation Learning
• Network Science

Background:

• Standard Graph Neural Networks (GNNs) exhibit limitations in capturing graph structural information, bounded by the Weisfeiler-Leman (WL) graph isomorphism test.
• This limitation hinders their ability to detect and count graph substructures, which are crucial for tasks in network science and bioinformatics.

Purpose of the Study:

• To introduce Graph Substructure Networks (GSNs), a novel architecture designed to overcome the expressive limitations of standard GNNs.
• To develop a topologically-aware message passing scheme that effectively encodes graph substructures.

Main Methods:

• Propose Graph Substructure Networks (GSNs) utilizing a substructure encoding approach within a message passing framework.
• Theoretically analyze the expressive power of GSNs, demonstrating superiority over the WL test and providing conditions for universality.
• Maintain desirable GNN properties like locality and linear complexity while enhancing discriminative capabilities.

Main Results:

• GSNs are theoretically shown to be strictly more expressive than the WL graph isomorphism test.
• The architecture can disambiguate graph isomorphism instances that are challenging for standard GNNs.
• State-of-the-art results were achieved on graph classification and regression tasks across molecular graphs and social networks.

Conclusions:

• Graph Substructure Networks offer a powerful and topologically-aware alternative to standard GNNs.
• GSNs effectively capture and leverage graph substructural information for improved performance.
• This approach advances graph representation learning, particularly in domains where substructures are functionally relevant.