2023/12/14 by Asela Hevapathige, Qing Wang, Hevapathige, Asela +1
Computer Science · Engineering · #Advanced Graph Neural Networks #Advanced Memory and Neural Computing #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Graph Theory and Algorithms #Machine Learning (cs.LG)
paper · pdf · doi:10.48550/arxiv.2312.08671
openalex publication_date 2023/12/14 · openalex created_date 2023/12/16 · openalex updated_date 2026/07/28
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.