Discovering the Representation Bottleneck of Graph Neural Networks
This addresses a fundamental limitation in GNNs for graph learning tasks, offering a method to improve interaction modeling, though it is incremental as it builds on existing rewiring techniques.
The paper tackles the problem of graph neural networks (GNNs) failing to capture the most informative node interactions for diverse graph learning tasks, discovering a representation bottleneck caused by inductive biases in graph construction. It proposes a novel graph rewiring approach that dynamically adjusts node receptive fields, achieving superior performance over state-of-the-art baselines in experiments on real-world and synthetic datasets.
Graph neural networks (GNNs) rely mainly on the message-passing paradigm to propagate node features and build interactions, and different graph learning problems require different ranges of node interactions. In this work, we explore the capacity of GNNs to capture node interactions under contexts of different complexities. We discover that GNNs usually fail to capture the most informative kinds of interaction styles for diverse graph learning tasks, and thus name this phenomenon GNNs' representation bottleneck. As a response, we demonstrate that the inductive bias introduced by existing graph construction mechanisms can result in this representation bottleneck, \emph{i.e.}, preventing GNNs from learning interactions of the most appropriate complexity. To address that limitation, we propose a novel graph rewiring approach based on interaction patterns learned by GNNs to dynamically adjust each node's receptive fields. Extensive experiments on both real-world and synthetic datasets prove the effectiveness of our algorithm in alleviating the representation bottleneck and its superiority in enhancing the performance of GNNs over state-of-the-art graph rewiring baselines.