Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspective
This work addresses a fundamental gap in understanding GNN behavior for researchers, revealing that feature distribution on graph topology mediates graph convolution effects, which is incremental but clarifies prior overlooked mechanisms.
The paper investigates how the dependence between graph topology and node features (A-X dependence) affects graph neural networks (GNNs), finding that reducing this dependence through feature shuffling consistently improves GNN performance in node classification tasks.
How would randomly shuffling feature vectors among nodes from the same class affect graph neural networks (GNNs)? The feature shuffle, intuitively, perturbs the dependence between graph topology and features (A-X dependence) for GNNs to learn from. Surprisingly, we observe a consistent and significant improvement in GNN performance following the feature shuffle. Having overlooked the impact of A-X dependence on GNNs, the prior literature does not provide a satisfactory understanding of the phenomenon. Thus, we raise two research questions. First, how should A-X dependence be measured, while controlling for potential confounds? Second, how does A-X dependence affect GNNs? In response, we (i) propose a principled measure for A-X dependence, (ii) design a random graph model that controls A-X dependence, (iii) establish a theory on how A-X dependence relates to graph convolution, and (iv) present empirical analysis on real-world graphs that align with the theory. We conclude that A-X dependence mediates the effect of graph convolution, such that smaller dependence improves GNN-based node classification.