Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs

• URL: http://arxiv.org/abs/2006.11468v2
• Date: Fri, 23 Oct 2020 08:43:25 GMT
• Title: Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs
• Authors: Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, Danai Koutra
• Abstract summary: We investigate the representation power of graph neural networks in a semi-supervised node classification task under heterophily or low homophily. Many popular GNNs fail to generalize to this setting, and are even outperformed by models that ignore the graph structure. We identify a set of key designs that boost learning from the graph structure under heterophily.
• Score: 28.77753005139331
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the representation power of graph neural networks in the semi-supervised node classification task under heterophily or low homophily, i.e., in networks where connected nodes may have different class labels and dissimilar features. Many popular GNNs fail to generalize to this setting, and are even outperformed by models that ignore the graph structure (e.g., multilayer perceptrons). Motivated by this limitation, we identify a set of key designs -- ego- and neighbor-embedding separation, higher-order neighborhoods, and combination of intermediate representations -- that boost learning from the graph structure under heterophily. We combine them into a graph neural network, H2GCN, which we use as the base method to empirically evaluate the effectiveness of the identified designs. Going beyond the traditional benchmarks with strong homophily, our empirical analysis shows that the identified designs increase the accuracy of GNNs by up to 40% and 27% over models without them on synthetic and real networks with heterophily, respectively, and yield competitive performance under homophily.

Related papers

• Learn from Heterophily: Heterophilous Information-enhanced Graph Neural Network [4.078409998614025]
  Heterophily, nodes with different labels tend to be connected based on semantic meanings, Graph Neural Networks (GNNs) often exhibit suboptimal performance. We propose and demonstrate that the valuable semantic information inherent in heterophily can be utilized effectively in graph learning. We propose HiGNN, an innovative approach that constructs an additional new graph structure, that integrates heterophilous information by leveraging node distribution.
  arXiv  Detail & Related papers  (2024-03-26T03:29:42Z)
• Degree-based stratification of nodes in Graph Neural Networks [66.17149106033126]
  We modify the Graph Neural Network (GNN) architecture so that the weight matrices are learned, separately, for the nodes in each group. This simple-to-implement modification seems to improve performance across datasets and GNN methods.
  arXiv  Detail & Related papers  (2023-12-16T14:09:23Z)
• 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)
• Heterophily-Aware Graph Attention Network [42.640057865981156]
  Graph Neural Networks (GNNs) have shown remarkable success in graph representation learning. Existing heterophilic GNNs tend to ignore the modeling of heterophily of each edge, which is also a vital part in tackling the heterophily problem. We propose a novel Heterophily-Aware Graph Attention Network (HA-GAT) by fully exploring and utilizing the local distribution as the underlying heterophily.
  arXiv  Detail & Related papers  (2023-02-07T03:21:55Z)
• 2-hop Neighbor Class Similarity (2NCS): A graph structural metric indicative of graph neural network performance [4.051099980410583]
  Graph Neural Networks (GNNs) achieve state-of-the-art performance on graph-structured data across numerous domains. On heterophilous graphs, in which different-type nodes are likely connected, GNNs perform less consistently. We introduce 2-hop Neighbor Class Similarity (2NCS), a new quantitative graph structural property that correlates with GNN performance more strongly and consistently than alternative metrics.
  arXiv  Detail & Related papers  (2022-12-26T16:16:51Z)
• Relation Embedding based Graph Neural Networks for Handling Heterogeneous Graph [58.99478502486377]
  We propose a simple yet efficient framework to make the homogeneous GNNs have adequate ability to handle heterogeneous graphs. Specifically, we propose Relation Embedding based Graph Neural Networks (RE-GNNs), which employ only one parameter per relation to embed the importance of edge type relations and self-loop connections.
  arXiv  Detail & Related papers  (2022-09-23T05:24:18Z)
• EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networks [51.42338058718487]
  Graph Neural Networks (GNNs) have received extensive research attention for their promising performance in graph machine learning. Existing approaches, such as GCN and GPRGNN, are not robust in the face of homophily changes on test graphs. We propose EvenNet, a spectral GNN corresponding to an even-polynomial graph filter.
  arXiv  Detail & Related papers  (2022-05-27T10:48:14Z)
• Incorporating Heterophily into Graph Neural Networks for Graph Classification [6.709862924279403]
  Graph Neural Networks (GNNs) often assume strong homophily for graph classification, seldom considering heterophily. We develop a novel GNN architecture called IHGNN (short for Incorporating Heterophily into Graph Neural Networks) We empirically validate IHGNN on various graph datasets and demonstrate that it outperforms the state-of-the-art GNNs for graph classification.
  arXiv  Detail & Related papers  (2022-03-15T06:48:35Z)
• 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)
• Graph Neural Networks with Heterophily [40.23690407583509]
  We propose a novel framework called CPGNN that generalizes GNNs for graphs with either homophily or heterophily. We show that replacing the compatibility matrix in our framework with the identity (which represents pure homophily) reduces to GCN.
  arXiv  Detail & Related papers  (2020-09-28T18:29:36Z)
• Binarized Graph Neural Network [65.20589262811677]
  We develop a binarized graph neural network to learn the binary representations of the nodes with binary network parameters. Our proposed method can be seamlessly integrated into the existing GNN-based embedding approaches. Experiments indicate that the proposed binarized graph neural network, namely BGN, is orders of magnitude more efficient in terms of both time and space.
  arXiv  Detail & Related papers  (2020-04-19T09:43:14Z)

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.