Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyond

• URL: http://arxiv.org/abs/2209.06177v5
• Date: Mon, 15 Apr 2024 21:49:09 GMT
• Title: Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyond
• Abstract summary: Homophily is a graph property describing the tendency of edges to connect similar nodes; the opposite is called heterophily. There is no universally agreed-upon measure of homophily in the literature. We show that commonly used homophily measures have critical drawbacks preventing the comparison of homophily levels across different datasets.
• Score: 36.5554915218563
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Homophily is a graph property describing the tendency of edges to connect similar nodes; the opposite is called heterophily. It is often believed that heterophilous graphs are challenging for standard message-passing graph neural networks (GNNs), and much effort has been put into developing efficient methods for this setting. However, there is no universally agreed-upon measure of homophily in the literature. In this work, we show that commonly used homophily measures have critical drawbacks preventing the comparison of homophily levels across different datasets. For this, we formalize desirable properties for a proper homophily measure and verify which measures satisfy which properties. In particular, we show that a measure that we call adjusted homophily satisfies more desirable properties than other popular homophily measures while being rarely used in graph machine learning literature. Then, we go beyond the homophily-heterophily dichotomy and propose a new characteristic that allows one to further distinguish different sorts of heterophily. The proposed label informativeness (LI) characterizes how much information a neighbor's label provides about a node's label. We prove that this measure satisfies important desirable properties. We also observe empirically that LI better agrees with GNN performance compared to homophily measures, which confirms that it is a useful characteristic of the graph structure.

Related papers

• Graph homophily booster: Reimagining the role of discrete features in heterophilic graph learning [50.99881402425112]
  Graph neural networks (GNNs) have emerged as a powerful tool for modeling graph-structured data.<n>Existing GNNs often struggle with heterophilic graphs, where connected nodes tend to have dissimilar features or labels.<n>We present a new and unexplored paradigm: directly increasing the graph homophily via a carefully designed graph transformation.
  arXiv  Detail & Related papers  (2026-02-06T23:14:10Z)
• Graph Homophily Booster: Rethinking the Role of Discrete Features on Heterophilic Graphs [50.99881402425112]
  Graph neural networks (GNNs) have emerged as a powerful tool for modeling graph-structured data.<n>Existing GNNs often struggle with heterophilic graphs, where connected nodes tend to have dissimilar features or labels.<n>We present a new and unexplored paradigm: directly increasing the graph homophily via a carefully designed graph transformation.
  arXiv  Detail & Related papers  (2025-09-16T00:10:20Z)
• Revisiting Graph Homophily Measures [18.497863598167257]
  Homophily is a graph property describing the tendency of edges to connect similar nodes. Previous works on graph homophily suggested several properties desirable for a good homophily measure. Our paper introduces a new homophily measure - unbiased homophily.
  arXiv  Detail & Related papers  (2024-12-12T14:54:56Z)
• The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challenges [101.83124435649358]
  Homophily principle, ie nodes with the same labels or similar attributes are more likely to be connected. Recent work has identified a non-trivial set of datasets where GNN's performance compared to the NN's is not satisfactory.
  arXiv  Detail & Related papers  (2024-07-12T18:04:32Z)
• What Is Missing In Homophily? Disentangling Graph Homophily For Graph Neural Networks [3.1227658238819855]
  Graph homophily refers to the phenomenon that connected nodes tend to share similar characteristics. The most widely used homophily metrics, such as edge or node homophily, quantify such "similarity" How homophily influences Graph Neural Networks (GNNs) still remains unclear and controversial.
  arXiv  Detail & Related papers  (2024-06-27T02:48:33Z)
• Generation is better than Modification: Combating High Class Homophily Variance in Graph Anomaly Detection [51.11833609431406]
  Homophily distribution differences between different classes are significantly greater than those in homophilic and heterophilic graphs. We introduce a new metric called Class Homophily Variance, which quantitatively describes this phenomenon. To mitigate its impact, we propose a novel GNN model named Homophily Edge Generation Graph Neural Network (HedGe)
  arXiv  Detail & Related papers  (2024-03-15T14:26:53Z)
• Provable Filter for Real-world Graph Clustering [11.7278692671308]
  A principled way to handle practical graphs is urgently needed. We construct two graphs that are highly homophilic and heterophilic, respectively. We validate our approach through extensive experiments on both homophilic and heterophilic graphs.
  arXiv  Detail & Related papers  (2024-03-06T12:37:49Z)
• Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs [48.79929516665371]
  Graphs with homophily-prone edges tend to connect nodes with the same class. Heterophily-prone edges tend to build relationships between nodes with different classes. Existing GNNs only take the original graph during training.
  arXiv  Detail & Related papers  (2023-06-13T08:06:10Z)
• Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All? [61.35457647107439]
  Most real-world homophilic and heterophilic graphs are comprised of a mixture of nodes in both homophilic and heterophilic structural patterns. We provide evidence that Graph Neural Networks(GNNs) on node classification typically perform admirably on homophilic nodes. We then propose a rigorous, non-i.i.d PAC-Bayesian generalization bound for GNNs, revealing reasons for the performance disparity.
  arXiv  Detail & Related papers  (2023-06-02T07:46:20Z)
• Label-Wise Message Passing Graph Neural Network on Heterophilic Graphs [20.470934944907608]
  We investigate a novel framework that performs well on graphs with either homophily or heterophily. In label-wise message-passing, neighbors with similar pseudo labels will be aggregated together. We also propose a bi-level optimization method to automatically select the model for graphs with homophily/heterophily.
  arXiv  Detail & Related papers  (2021-10-15T14:49:45Z)
• 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)
• New Benchmarks for Learning on Non-Homophilous Graphs [20.082182515715182]
  We present a series of improved graph datasets with node label relationships that do not satisfy the homophily principle. We also introduce a new measure of the presence or absence of homophily that is better suited than existing measures in different regimes.
  arXiv  Detail & Related papers  (2021-04-03T13:45:06Z)

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.