On Performance Discrepancies Across Local Homophily Levels in Graph Neural Networks

Donald Loveland, Jiong Zhu, Mark Heimann, Benjamin Fish, Michael T Schaub, Danai Koutra
Proceedings of the Second Learning on Graphs Conference, PMLR 231:6:1-6:30, 2024.

Abstract

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. We ground the practical implications of this work through granular analysis on five real-world datasets with varying global homophily levels, demonstrating that (a) GNNs can fail to generalize to test nodes that deviate from the global homophily of a graph, and (b) high local homophily does not necessarily confer high performance for a node. We further show that GNNs designed for globally heterophilous graphs can alleviate performance discrepancy by improving performance across local homophily levels, offering a new perspective on how these GNNs achieve stronger global performance.

Cite this Paper

BibTeX
@InProceedings{pmlr-v231-loveland24a, title = {On Performance Discrepancies Across Local Homophily Levels in Graph Neural Networks}, author = {Loveland, Donald and Zhu, Jiong and Heimann, Mark and Fish, Benjamin and Schaub, Michael T and Koutra, Danai}, booktitle = {Proceedings of the Second Learning on Graphs Conference}, pages = {6:1--6:30}, year = {2024}, editor = {Villar, Soledad and Chamberlain, Benjamin}, volume = {231}, series = {Proceedings of Machine Learning Research}, month = {27--30 Nov}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v231/loveland24a/loveland24a.pdf}, url = {https://proceedings.mlr.press/v231/loveland24a.html}, abstract = {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. We ground the practical implications of this work through granular analysis on five real-world datasets with varying global homophily levels, demonstrating that (a) GNNs can fail to generalize to test nodes that deviate from the global homophily of a graph, and (b) high local homophily does not necessarily confer high performance for a node. We further show that GNNs designed for globally heterophilous graphs can alleviate performance discrepancy by improving performance across local homophily levels, offering a new perspective on how these GNNs achieve stronger global performance.} }
Endnote
%0 Conference Paper %T On Performance Discrepancies Across Local Homophily Levels in Graph Neural Networks %A Donald Loveland %A Jiong Zhu %A Mark Heimann %A Benjamin Fish %A Michael T Schaub %A Danai Koutra %B Proceedings of the Second Learning on Graphs Conference %C Proceedings of Machine Learning Research %D 2024 %E Soledad Villar %E Benjamin Chamberlain %F pmlr-v231-loveland24a %I PMLR %P 6:1--6:30 %U https://proceedings.mlr.press/v231/loveland24a.html %V 231 %X 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. We ground the practical implications of this work through granular analysis on five real-world datasets with varying global homophily levels, demonstrating that (a) GNNs can fail to generalize to test nodes that deviate from the global homophily of a graph, and (b) high local homophily does not necessarily confer high performance for a node. We further show that GNNs designed for globally heterophilous graphs can alleviate performance discrepancy by improving performance across local homophily levels, offering a new perspective on how these GNNs achieve stronger global performance.
APA
Loveland, D., Zhu, J., Heimann, M., Fish, B., Schaub, M.T. & Koutra, D.. (2024). On Performance Discrepancies Across Local Homophily Levels in Graph Neural Networks. Proceedings of the Second Learning on Graphs Conference, in Proceedings of Machine Learning Research 231:6:1-6:30 Available from https://proceedings.mlr.press/v231/loveland24a.html.

Related Material