Homophily modulates double descent generalization in graph convolution networks.

Area of Science:

• Machine Learning
• Network Science
• Statistical Physics

Background:

• Graph neural networks (GNNs) are powerful for relational data but their generalization mechanisms remain unclear.
• Traditional complexity measures do not explain phenomena like double descent or the effect of relational semantics in GNNs.
• Experimental observations of "transductive" double descent in GNNs motivated this theoretical investigation.

Purpose of the Study:

• To analytically characterize generalization in simple graph convolution networks.
• To understand the influence of homophily and heterophily on learning.
• To investigate the impact of graph noise, feature noise, and training data size on GNN risk.

Main Methods:

• Utilizing analytical tools from statistical physics and random matrix theory.
• Applying these tools to the contextual stochastic block model for precise generalization characterization.
• Analyzing the interplay between various noise factors and the number of training labels.

Main Results:

• The study predicts and explains double descent phenomena in GNNs, addressing recent skepticism.
• It clarifies how homophilic and heterophilic data characteristics affect learning.
• Risk in GNNs is shown to be a function of graph noise, feature noise, and training label count.

Conclusions:

• The theoretical framework accurately captures qualitative trends observed in real-world GNNs and datasets.
• Analytic insights were successfully applied to enhance the performance of state-of-the-art GNNs on heterophilic datasets.
• This work provides a foundational understanding of GNN generalization, bridging theory and practice.