A critical look at the evaluation of GNNs under heterophily: Are we really making progress?

• URL: http://arxiv.org/abs/2302.11640v2
• Date: Sat, 2 Mar 2024 21:17:13 GMT
• Title: A critical look at the evaluation of GNNs under heterophily: Are we really making progress?
• Authors: Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, Liudmila Prokhorenkova
• Abstract summary: It is often believed that standard Graph Neural Networks (GNNs) only work well for homophilous graphs. We show that standard datasets used for evaluating heterophily-specific models have serious drawbacks. We propose a set of heterophilous graphs of varying properties that we believe can serve as a better benchmark for evaluating the performance of GNNs under heterophily.
• Score: 39.62589602648429
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Node classification is a classical graph machine learning task on which Graph Neural Networks (GNNs) have recently achieved strong results. However, it is often believed that standard GNNs only work well for homophilous graphs, i.e., graphs where edges tend to connect nodes of the same class. Graphs without this property are called heterophilous, and it is typically assumed that specialized methods are required to achieve strong performance on such graphs. In this work, we challenge this assumption. First, we show that the standard datasets used for evaluating heterophily-specific models have serious drawbacks, making results obtained by using them unreliable. The most significant of these drawbacks is the presence of a large number of duplicate nodes in the datasets Squirrel and Chameleon, which leads to train-test data leakage. We show that removing duplicate nodes strongly affects GNN performance on these datasets. Then, we propose a set of heterophilous graphs of varying properties that we believe can serve as a better benchmark for evaluating the performance of GNNs under heterophily. We show that standard GNNs achieve strong results on these heterophilous graphs, almost always outperforming specialized models. Our datasets and the code for reproducing our experiments are available at https://github.com/yandex-research/heterophilous-graphs

Related papers

• The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs [59.03660013787925]
  We introduce the Heterophily Snowflake Hypothesis and provide an effective solution to guide and facilitate research on heterophilic graphs. Our observations show that our framework acts as a versatile operator for diverse tasks. It can be integrated into various GNN frameworks, boosting performance in-depth and offering an explainable approach to choosing the optimal network depth.
  arXiv  Detail & Related papers  (2024-06-18T12:16:00Z)
• Evolving Computation Graphs [20.094508902123778]
  Graph neural networks (GNNs) have demonstrated success in modeling relational data, especially for data that exhibits homophily. We propose Evolving Computation Graphs (ECGs), a novel method for enhancing GNNs on heterophilic datasets.
  arXiv  Detail & Related papers  (2023-06-22T14:58:18Z)
• Self-attention Dual Embedding for Graphs with Heterophily [6.803108335002346]
  A number of real-world graphs are heterophilic, and this leads to much lower classification accuracy using standard GNNs. We design a novel GNN which is effective for both heterophilic and homophilic graphs. We evaluate our algorithm on real-world graphs containing thousands to millions of nodes and show that we achieve state-of-the-art results.
  arXiv  Detail & Related papers  (2023-05-28T09:38:28Z)
• Beyond Real-world Benchmark Datasets: An Empirical Study of Node Classification with GNNs [3.547529079746247]
  Graph Neural Networks (GNNs) have achieved great success on a node classification task. Existing evaluation of GNNs lacks fine-grained analysis from various characteristics of graphs. We conduct extensive experiments with a synthetic graph generator that can generate graphs having controlled characteristics for fine-grained analysis.
  arXiv  Detail & Related papers  (2022-06-18T08:03:12Z)
• Exploiting Neighbor Effect: Conv-Agnostic GNNs Framework for Graphs with Heterophily [58.76759997223951]
  We propose a new metric based on von Neumann entropy to re-examine the heterophily problem of GNNs. We also propose a Conv-Agnostic GNN framework (CAGNNs) to enhance the performance of most GNNs on heterophily datasets.
  arXiv  Detail & Related papers  (2022-03-19T14:26:43Z)
• Graph Neural Networks for Graphs with Heterophily: A Survey [98.45621222357397]
  We provide a comprehensive review of graph neural networks (GNNs) for heterophilic graphs. Specifically, we propose a systematic taxonomy that essentially governs existing heterophilic GNN models. We discuss the correlation between graph heterophily and various graph research domains, aiming to facilitate the development of more effective GNNs.
  arXiv  Detail & Related papers  (2022-02-14T23:07:47Z)
• Is Homophily a Necessity for Graph Neural Networks? [50.959340355849896]
  Graph neural networks (GNNs) have shown great prowess in learning representations suitable for numerous graph-based machine learning tasks. GNNs are widely believed to work well due to the homophily assumption ("like attracts like"), and fail to generalize to heterophilous graphs where dissimilar nodes connect. Recent works design new architectures to overcome such heterophily-related limitations, citing poor baseline performance and new architecture improvements on a few heterophilous graph benchmark datasets as evidence for this notion. In our experiments, we empirically find that standard graph convolutional networks (GCNs) can actually achieve better performance than
  arXiv  Detail & Related papers  (2021-06-11T02:44:00Z)
• Beyond Low-Pass Filters: Adaptive Feature Propagation on Graphs [6.018995094882323]
  Graph neural networks (GNNs) have been extensively studied for prediction tasks on graphs. Most GNNs assume local homophily, i.e., strong similarities in localneighborhoods. We propose a flexible GNN model, which is capable of handling any graphs without beingrestricted by their underlying homophily.
  arXiv  Detail & Related papers  (2021-03-26T00:35:36Z)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  Graph neural networks (GNNs) are effective models for representation learning on relational data. Standard GNNs are limited in their expressive power, as they cannot distinguish beyond the capability of the Weisfeiler-Leman graph isomorphism. In this work, we analyze the expressive power of GNNs with random node (RNI) We prove that these models are universal, a first such result for GNNs not relying on computationally demanding higher-order properties.
  arXiv  Detail & Related papers  (2020-10-02T19:53:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.