What Do GNNs Actually Learn? Towards Understanding their Representations
This work addresses a fundamental gap in understanding GNN representations, which is crucial for researchers and practitioners in graph machine learning, though it is incremental in building on prior expressiveness studies.
The paper investigates what structural information graph neural networks (GNNs) encode into node representations, finding that some models produce identical representations for all nodes while others link representations to walks of specific lengths, and it establishes Lipschitz bounds and analyzes the influence of node features.
In recent years, graph neural networks (GNNs) have achieved great success in the field of graph representation learning. Although prior work has shed light on the expressiveness of those models (\ie whether they can distinguish pairs of non-isomorphic graphs), it is still not clear what structural information is encoded into the node representations that are learned by those models. In this paper, we address this gap by studying the node representations learned by four standard GNN models. We find that some models produce identical representations for all nodes, while the representations learned by other models are linked to some notion of walks of specific length that start from the nodes. We establish Lipschitz bounds for these models with respect to the number of (normalized) walks. Additionally, we investigate the influence of node features on the learned representations. We find that if the initial representations of all nodes point in the same direction, the representations learned at the $k$-th layer of the models are also related to the initial features of nodes that can be reached in exactly $k$ steps. We also apply our findings to understand the phenomenon of oversquashing that occurs in GNNs. Our theoretical analysis is validated through experiments on synthetic and real-world datasets.