Are GNNs doomed by the topology of their input graph?
This addresses a fundamental understanding gap in GNN behavior for researchers and practitioners, but it is incremental as it builds on existing knowledge of oversmoothing.
The paper investigates whether Graph Neural Networks (GNNs) are inherently limited by the topology of their input graphs, finding that local topological features interact with message-passing to cause phenomena like oversmoothing or effective learning, with empirical validation of these insights.
Graph Neural Networks (GNNs) have demonstrated remarkable success in learning from graph-structured data. However, the influence of the input graph's topology on GNN behavior remains poorly understood. In this work, we explore whether GNNs are inherently limited by the structure of their input graphs, focusing on how local topological features interact with the message-passing scheme to produce global phenomena such as oversmoothing or expressive representations. We introduce the concept of $k$-hop similarity and investigate whether locally similar neighborhoods lead to consistent node representations. This interaction can result in either effective learning or inevitable oversmoothing, depending on the inherent properties of the graph. Our empirical experiments validate these insights, highlighting the practical implications of graph topology on GNN performance.