Permutation-Invariant Graph Partitioning:How Graph Neural Networks Capture Structural Interactions?
This addresses a gap in graph-related learning for researchers and practitioners, but appears incremental as it builds on existing GNN frameworks.
The paper tackles the problem of Graph Neural Networks (GNNs) under-exploring structural interactions in graphs by proposing Graph Partitioning Neural Networks (GPNNs), which outperform existing GNN models on benchmark tasks.
Graph Neural Networks (GNNs) have paved the way for being a cornerstone in graph-related learning tasks. Yet, the ability of GNNs to capture structural interactions within graphs remains under-explored. In this work, we address this gap by drawing on the insight that permutation invariant graph partitioning enables a powerful way of exploring structural interactions. We establish theoretical connections between permutation invariant graph partitioning and graph isomorphism, and then propose Graph Partitioning Neural Networks (GPNNs), a novel architecture that efficiently enhances the expressive power of GNNs in learning structural interactions. We analyze how partitioning schemes and structural interactions contribute to GNN expressivity and their trade-offs with complexity. Empirically, we demonstrate that GPNNs outperform existing GNN models in capturing structural interactions across diverse graph benchmark tasks.