On Performance Discrepancies Across Local Homophily Levels in Graph Neural Networks

Understand

Graph Neural Network (GNN) research has highlighted a relationship between high homophily (i.e., the tendency of nodes of the same class to connect) and strong predictive performance in node classification.

• However, recent work has found the relationship to be more nuanced, demonstrating that simple GNNs can learn in certain heterophilous settings.
• To resolve these conflicting findings and align closer to real-world datasets, we go beyond the assumption of a global graph homophily level and study the performance of GNNs when the local homophily level of a node deviates from the global homophily level.
• Through theoretical and empirical analysis, we systematically demonstrate how shifts in local homophily can introduce performance degradation, leading to performance discrepancies across local homophily levels.