An Efficient Subgraph GNN with Provable Substructure Counting Power
This work addresses efficiency bottlenecks in graph neural networks for researchers and practitioners, representing an incremental improvement over existing subgraph GNNs.
The paper tackles the problem of subgraph GNNs' high computational and memory costs by introducing a method that uses precomputed structural embeddings based on distance to rooted nodes, achieving significantly faster performance while retaining substructure counting power.
We investigate the enhancement of graph neural networks' (GNNs) representation power through their ability in substructure counting. Recent advances have seen the adoption of subgraph GNNs, which partition an input graph into numerous subgraphs, subsequently applying GNNs to each to augment the graph's overall representation. Despite their ability to identify various substructures, subgraph GNNs are hindered by significant computational and memory costs. In this paper, we tackle a critical question: Is it possible for GNNs to count substructures both \textbf{efficiently} and \textbf{provably}? Our approach begins with a theoretical demonstration that the distance to rooted nodes in subgraphs is key to boosting the counting power of subgraph GNNs. To avoid the need for repetitively applying GNN across all subgraphs, we introduce precomputed structural embeddings that encapsulate this crucial distance information. Experiments validate that our proposed model retains the counting power of subgraph GNNs while achieving significantly faster performance.