PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Neural Networks for Graphs with Heterophily: A Survey

Xin Zheng, Yi Wang, Yixin Liu, Ming Li, Miao Zhang, Di Jin, Philip S. Yu, Shirui Pan

arXiv:2202.07082v4cs.LG

TL;DR

Homophily-oriented GNNs struggle when linked nodes have different labels, making heterophilic graph learning an important research problem. The paper systematically surveys heterophilic GNNs, organizes them into a three-class taxonomy, and connects them to broader graph domains. It synthesizes advances, challenges, and future directions across heterophilic graph learning.

  • Problem

    Most GNNs rely on homophily, but real-world heterophilic graphs link nodes with different labels, limiting the suitability of homophily-oriented models.

  • Method

    The paper provides a comprehensive review with a taxonomy covering non-local neighbor extension, GNN architecture refinement, and hybrid methods.

  • Results

    The survey synthesizes heterophilic GNN progress and discusses connections with dynamic graphs, over-smoothing, robustness, and graph anomaly detection.

  • Takeaways & Limitations

    The paper identifies research directions involving interpretability, scalability, robustness, data exploration, and broader practical applications for heterophilic GNNs.

Abstract

from arXiv · show

Recent years have witnessed fast developments of graph neural networks (GNNs) that have benefited myriad graph analytic tasks and applications. Most GNNs rely on the homophily assumption that nodes belonging to the same class are more likely to be connected. However, as a ubiquitous graph property in numerous real-world scenarios, heterophily, i.e., nodes with different labels tend to be linked, significantly limits the performance of tailor-made homophilic GNNs. Hence, GNNs for heterophilic graphs are gaining increasing research attention to enhance graph learning with heterophily. In this paper, we provide a comprehensive review of GNNs for heterophilic graphs. Specifically, we propose a systematic taxonomy that governs existing heterophilic GNN models, along with general summaries and detailed analyses. Furthermore, we discuss the relationship between heterophily and various graph research domains, aiming to facilitate the development of more effective GNNs across a spectrum of practical applications and learning tasks in the graph research community. In the end, we point out potential directions to advance and inspire future research and applications on heterophilic graph learning with GNNs.

I. INTRODUCTION

Heterophily, where linked nodes have dissimilar features or labels, challenges GNNs built around homophily and local message passing. This survey organizes heterophilic GNN research, relates it to broader graph domains, and identifies future directions.

  • Motivation: Heterophily links nodes with dissimilar features or different class labels, contrary to the homophily assumption followed by most GNNs.Citation networks often exhibit homophily, whereas online transaction networks can exhibit heterophily.
  • Core Challenges: Uniform local message passing can degrade heterophilic GNN performance by aggregating dissimilar local neighbors while missing similar non-local nodes.The resulting representations may fail to capture discriminative heterophily information.
  • Importance: Heterophilic graph learning remains an open research area requiring expressive, robust, and generalizable GNN models across practical tasks.The survey emphasizes the complexity and diversity of heterophilic graphs across real-world and scientific scenarios.
  • Survey Scope: The survey reviews heterophilic GNNs across data, algorithms, and applications and provides comparisons and concise summaries of model types.It aims to establish connections among methods and clarify how they address heterophily-learning challenges.
  • Taxonomy: Existing heterophilic GNNs are categorized into non-local neighbor extension, GNN architecture refinement, and hybrid methods.The taxonomy groups methods according to how they address heterophily-guided neighbor aggregation and feature updating.
  • Broader Connections: The survey discusses links between heterophily and model robustness, over-smoothing, graph anomaly detection, and future research limitations.Suggested directions include interpretability, robustness, scalability, and heterophilic graph data exploration.

II. PRELIMINARY

The preliminary section defines graph notation, standard GNN message passing, spectral graph convolution, and measures for quantifying homophily and heterophily.

  • Notations: A graph is represented as G = (V, E), with node features X, adjacency matrix A, degree matrix D, and Laplacian L = D − A.Normalized Laplacians include symmetric normalization and random-walk normalization.
  • Spectral Foundations: The Laplacian eigendecomposition ˜L = UΛU^T represents graph frequencies through eigenvectors U and eigenvalues Λ.The eigenvalues correspond to the frequencies or smoothness of the associated eigenvectors.
  • Message Passing: Standard GNN layers aggregate local neighbor messages and update each node representation using its ego representation.The first-layer input is H^(0) = X, and final representations can feed a classifier for node classification.
  • Spectral Graph Convolution: Spectral graph convolution learns a frequency response function that re-weights graph signals across different frequencies.Greater weights on smaller eigenvalues retain more low-frequency information, while larger eigenvalues retain more high-frequency information.
  • Homophily Measures: Graph homophily and heterophily can be measured using node, edge, class, adjusted, and unbiased homophily metrics.Node homophily averages same-class neighbor proportions, whereas edge homophily measures the proportion of same-class edges.

E. Real-World Benchmarks

Real-world benchmark development addresses shortcomings in widely used heterophily datasets and supports evaluation on more reliable graph-learning tasks. The section also frames heterophilic GNNs around semi-supervised node classification and message-passing taxonomy.

  • Benchmark Datasets: Widely used heterophily datasets include six small graphs, while later work introduced larger datasets such as ArXiv-Year, Penn94, Pokec, and YelpChi.The benchmark landscape expanded from early small-scale datasets to larger graphs with diverse properties.
  • Learning Task: Semi-supervised node classification predicts unlabeled node classes from a training graph containing features, adjacency information, and labels for only part of the nodes.The model learns parameters by minimizing cross-entropy over labeled nodes.
  • Framework: A unified framework categorizes heterophilic GNNs from the perspective of their message-passing mechanism.This framework supports the survey’s systematic taxonomy of heterophilic methods.

A. Framework of heterophilic GNNs

Heterophilic GNNs customize neighborhood aggregation and feature updates to address non-locality, class indistinguishability, and multi-layer information integration. The survey groups these models into non-local neighbor extension, GNN architecture refinement, and hybrid methods.

  • Heterophilic GNNs follow three design principles: non-local neighbor sets, class distinguishability, and depth fusion of multi-layer information.
  • The survey categorizes heterophilic GNNs into non-local neighbor extension, GNN architecture refinement, and hybrid methods.These categories correspond respectively to P1, P2 and P3, and all three principles.
  • Non-local neighbor extension methods: Non-local neighbor extension methods incorporate higher-order neighbors through high-order neighbor mixing or potential neighbor discovery.They reconstruct non-local neighbor sets to address the locality limitation of one-hop aggregation.
  • GNN architecture refinement methods: GNN architecture refinement methods distinguish similar and dissimilar neighbors or fuse information across layers, including edge-, feature-, and hybrid-weight aggregation schemes.
  • Hybrid methods: Hybrid methods combine non-local neighbor extension with GNN architecture refinement, but seamlessly integrating both approaches into message passing remains challenging.
  • High-order neighbor mixing: Higher-order neighbor mixing combines representations from one-hop and further k-hop neighbors, with methods differing in how multi-hop information is fused.MixHop aggregates one- and two-hop neighbors, applies different linear transformations, and concatenates the resulting messages; TDGNN fuses cross-hop neighbors before aggregation.

B. Potential Neighbor Discovery

Potential neighbor discovery methods redefine neighborhood structure by identifying homophilic neighbors across the graph using structural, feature-based, or hybrid distance measures. They then incorporate these potential neighbors into local message passing to enhance homophilic information.

  • Potential neighbor discovery constructs new neighbor sets by exploring the entire topology rather than relying only on inherent graph neighbors.Distance measurement in a defined latent space determines which nodes become potential neighbors.
  • Potential neighbor discovery methods use structure-based, feature-based, or hybrid distance measures.
  • Structure-based distance: Structure-based methods identify potential neighbors from geometric relationships defined by graph topology, while Geom-GCN maps the input graph into a continuous latent space.
  • Feature-based distance: Feature-based methods connect each ego node to its top k feature-similar nodes using cosine similarity and kNN selection.TopK selects the K highest-similarity nodes; HES-GSL adds homophily-enhanced self-supervision for similarity learning.
  • Hybrid distance: Hybrid methods combine topology and attribute information to measure correlations between global nodes and discover potential neighbors.HOG-GCN uses a homophily degree matrix, whereas GloGNN measures global correlations from topology and node attributes.
  • Potential neighbor discovery aims to identify high-order homophilic neighbors and add them to local neighborhoods for enhanced homophilic message passing.The approach is intended to identify nodes sharing the same class labels through different distance calculations.

V. HETEROPHILIC GNN ARCHITECTURE REFINEMENT

Architecture refinement methods enhance heterophilic GNNs by revising aggregation and update operations to distinguish neighbor information and combine multi-layer representations. They include feature-related, edge-related, and hybrid weight-assignment schemes, with spectral and spatial approaches adapting information from different graph signals and structures.

  • V. HETEROPHILIC GNN ARCHITECTURE REFINEMENT: Architecture refinement methods revise AGGREGATE(·) and UPDATE(·) to exploit original local and extended non-local neighbors.The taxonomy distinguishes identifiable message aggregation and inter-layer combination as two main design aspects.
  • 1) Edge-Related Weight:: Identifiable message aggregation assigns adaptive edge-aware weights to distinguish similar neighbors from dissimilar ones.These weights can be learned from node features or edge-related information.
  • 1) Edge-Related Weight:: Spectral methods combine low-pass, high-pass, identity, or mid-pass filters to adaptively exploit useful frequency channels while reducing input-signal loss.ACM, AutoGCN, and Mid-GCN respectively provide combinations or adaptations involving these filters.
  • 1) Edge-Related Weight:: Spatial edge-related methods use topology-guided aggregation, including vector-valued weights that operate across attribute dimensions rather than applying one scalar to all attributes.DMP extends scalar node-level weights into vectors computed through relaxed attention weights or element-wise neighbor-weight averaging.
  • 1) Edge-Related Weight:: Other edge-related approaches model edge uncertainty or improve scalability through graph pruning and sampled potential neighbors.GDAMNs use hard and soft attention, while CGP and GOAT target efficient learning on large-scale graphs.

2) Feature-Related Weight:

Feature-related methods refine neighbor representations by learning node-level attention or feature transformations that capture homophily and heterophily. They use attention, prior knowledge, signed or kernel-based transformations, decoupled memory, and capsule routing to make aggregated representations more discriminative.

  • 2) Feature-Related Weight:: Feature-related methods revise neighbor representation learning so node features are less likely to over-smooth and can encode heterophily.They learn node-level attention shared across neighbors or incorporate homophily/heterophily priors into feature transformation.
  • 2) Feature-Related Weight:: Prior-based methods propagate compatibility-based belief estimates or rank neighbors by class-similarity priors for sequential aggregation.CPGNN uses a compatibility matrix, while NLGNN and GPNN order neighbors according to prior belief.
  • 2) Feature-Related Weight:: Attention-based methods learn feature similarity or dissimilarity, including signed messages, positive and negative correlation weights, and gated bi-kernel transformations.These designs separately capture information associated with homophily and heterophily.
  • 2) Feature-Related Weight:: MMP decouples propagation memory from self-embedding, whereas NCGNN uses capsules and dynamic routing to select suitable subgraph features for aggregation.MMP adaptively updates memory and self-embedding; NCGNN aggregates advantageous capsules while constraining irrelevant ones.

3) Hybrid Weight:

Hybrid methods combine node-feature, topological, and positional information to calculate edge weights for node-specific aggregation. The surveyed inter-layer combination methods instead strengthen representations by integrating information across propagation depths.

  • 3) Hybrid Weight:: MWGNN jointly models node features, topology, and positional identity through a meta-weight to derive adaptive graph convolution.The resulting aggregation is node-specific and targets improved node representation learning.
  • 3) Hybrid Weight:: Inter-layer combination methods include representative designs associated with GPR-GNN, JK-Net, and GCNII.These methods are presented as typical approaches for combining information across layers.
  • 3) Hybrid Weight:: WRGNN separates ego-node and neighbor-message mappings, GGCN uses learnable scalar parameters, and ACM separates ego embeddings with an identity filter.These designs preserve distinctions between ego information and aggregated neighbor information.

B. Inter-Layer Combination

Inter-layer combination methods strengthen heterophilic GNNs by integrating representations from different propagation depths. They range from flexible layer aggregation to residual integration and learnable layer weighting, supporting exploration of local-to-global information.

  • B. Inter-Layer Combination: Shallow layers collect local information, while deeper layers implicitly capture global information through repeated neighbor propagation.This motivates combining representations across propagation ranges in heterophilic graphs.
  • B. Inter-Layer Combination: JK-Net combines features from different layers to obtain structure-aware representations across neighborhood ranges.Its layer aggregation can use column-wise combination, max pooling, or attention with LSTM.
  • B. Inter-Layer Combination: GCNII integrates the first-layer embedding at each layer through an initial residual connection, balancing it against the current representation with α.This differs from methods that use all previous intermediate representations.
  • B. Inter-Layer Combination: GPR-GNN adaptively combines each layer’s representation with learnable Generalized PageRank weights, while PowerEmbed interpolates local message-passing features and global spectral information.Together, these approaches support topological feature exploration across multiple propagation rounds.

VI. HYBRID METHODS

Hybrid methods combine expanded neighbor discovery with heterophily-aware architectural refinement. They operate locally within message passing or globally across layers, while dynamic graphs and hypergraphs introduce additional unresolved challenges.

  • Hybrid methods: Hybrid methods combine non-local neighbor expansion with heterophily-guided architecture refinement through local-level or global-level incorporation.Local-level methods modify intra-layer message passing, whereas global-level methods improve inter-layer information transfer.
  • Local-level incorporation: Local-level methods first construct topologies emphasizing local homophily, then aggregate messages over those reconstructed relationships.WRGNN uses neighbor degree sequences to measure structural similarity and reconstruct a multi-relational graph.
  • Local-level incorporation: Potential-neighbor methods rank candidate nodes using attention or relevant relationships to identify heterophilic neighbors similar to the ego node.GPNN uses a pointer network for this ranking, while another method introduces a path-based recurrent aggregator.
  • Global-level incorporation: Global-level incorporation establishes homophilic guidance across the network, exemplified by H2GNN’s separated ego-neighbor embeddings and higher-order neighborhoods.H2GNN also incorporates intermediate representations into the graph neural network.
  • Dynamic graphs: Heterophilic dynamic graphs require identifying homophily components without categorical labels, target-oriented correlations, and dynamic local environments for high-order propagation.These challenges arise from time-varying node relationships and topology-task discordance in spatial-temporal graphs.
  • Hypergraphs: Heterophilic hypergraph research remains early, lacking established heterophily characterizations and architecture designs that capture local hypergraph homophily.Hyperedges may contain nodes from multiple categories, making node-label prediction more intricate than in graphs.

3) Heterophily GNNs on Heterogeneous Graphs:

The survey connects heterophily with heterogeneous graph analysis, adversarial robustness, over-smoothing, and anomaly detection. Across these domains, heterophily-aware modeling is presented as relevant to filtering misleading relations, preserving feature distinctions, and detecting anomalous patterns.

  • Heterogeneous graphs: Heterophilic patterns can coexist with homophilic structures in heterogeneous graphs, motivating characterization and standardized evaluation through the H2GB benchmark.The cited work also reports heterophily in homogeneous graphs across real-world applications.
  • Robustness: Structural attacks on GNNs exhibit heterophily, prompting explicit adversarial filtering and implicit robustness through heterophily-adaptive architectures.GNNGUARD filters adversarial heterophilic edges, while GARNET and ATDGIA treat heterophilic connections as adversarial edges.
  • Over-smoothing: Heterophilic aggregation is linked to information dissipation in deep architectures, while heterophily-oriented designs can exhibit anti-over-smoothing properties.The survey identifies a duality between heterophily modeling and over-smoothing mitigation.
  • Over-smoothing: Theoretical analyses support negatively signed edges in GNNs and connect sheaf structures with both heterophily and over-smoothing.These converging explanations support technologies represented by FAGCN and motivate unified frameworks for stable higher-layer performance.
  • Graph anomaly detection: Fraudulent nodes typically form minority clusters surrounded by normal nodes and exhibit higher heterophily ratios than legitimate entities.Conventional homophilic message passing can amplify heterophily-induced noise, degrading fraud-detection performance.
  • Graph anomaly detection: Adaptive graph filtering combines low- and high-frequency signals to identify heterophilic anomalies with high precision and improve performance over conventional GAD baselines.Other approaches prune heterophilic edges or regularize structural distribution shifts between imbalanced classes.

4) Relation between Graph Heterophily and Uncertainty Modeling:

The survey relates heterophily to uncertainty, self-supervised learning, interpretability, scalability, theory, task diversity, and practical applications. It emphasizes that mixed connection types and non-local dependencies create unresolved modeling and evaluation challenges.

  • Uncertainty modeling: Mixed homophilic and heterophilic connections create topological uncertainty and expose GNN bias toward homophilic patterns.Models trained on semi-homophilic graphs can lose accuracy on purely heterophilic subsets.
  • Uncertainty modeling: Uncertainty-aware methods estimate epistemic uncertainty to identify heterophilic nodes and use probabilistic topology perturbation to improve minor-class representation.GraphTU exploits neighborhood variance through non-parametric topology augmentation.
  • Other explorations: Self-supervised heterophilic learning parallels graph contrastive learning because both seek additional same-class neighbors beyond the localized node view.GREET discriminates edges, while related designs preserve information associated with both homophily and heterophily.
  • Interpretability: Explaining heterophilic GNN predictions is under-explored because useful explanations require discovering both proximal and distant topological structures.This challenge is especially relevant in healthcare and cybersecurity applications.
  • Scalability: Mini-batch sampling can undermine heterophilic relationships because similar and dissimilar neighbors may contribute differently to ego-node representations.The survey identifies preserving heterophily during sampling as an open scalability question.
  • Theory: Heterophilic GNN efficacy lacks a solid theoretical foundation because many methods rely primarily on intuition and empirical evaluation.The survey highlights theoretical analysis under specific conditions as an emerging direction.
  • Diverse tasks: Link-level and graph-level heterophily learning still need suitable benchmark datasets and refined GNN architectures.DisenLink identifies latent-factor effects that make overall similarity low even when linked nodes share particular factors.
  • Practical applications: Heterophilic GNN research remains concentrated on strong heterophilic social and web graphs, leaving biomedicine and chemistry comparatively underexplored.The survey cites protein interactions, drug-drug networks, and fraud detection as practical application areas.

APPENDIX A MEASURE OF HETEROPHILY & HOMOPHILY

The survey reviews how heterophily and homophily are measured, assembles benchmark datasets, and summarizes heterophilic GNN development and evaluation. It highlights metric-specific interpretation, dataset-quality concerns, and stronger performance from recent specialized models on rigorous benchmarks.

  • Measure of Heterophily & Homophily: Hnode, Hedge, and Hclass increase toward 1 with stronger homophily and toward 0 with stronger heterophily, while Hadj and Hun follow the same overall direction.Hadj can occasionally be negative when Hedge is smaller than PC.
  • Measure of Heterophily & Homophily: Node and edge homophily are intuitive but sensitive to class count and class balance, limiting interpretation and comparability across datasets.When every node connects to one node from each class, both metrics equal 1/C.
  • Heterophilic Graph Benchmarks: The survey organizes heterophilic graph benchmarks into standard, large-scale, and high-quality datasets, spanning web, citation, social, and review networks.Large-scale examples include ArXiv-Year, Snap-Patents, Penn94, Pokec, Genius, Deezer-Europe, Twitch-Gamers, and YelpChi.
  • High-Quality Datasets: Standard heterophily benchmarks can produce unreliable results because duplicate nodes in datasets such as Squirrel and Chameleon cause train-test leakage.Removing duplicate nodes strongly affects GNN performance, motivating reliable benchmarks including Roman-Empire, Amazon-Ratings, Minesweeper, Tolokers, and Questions.
  • Performance Comparison: On five high-quality benchmarks, recent models including ACM-GCN, AGS-GNN, and PD-GNN consistently outperform traditional baselines, although some early specialized models are occasionally surpassed.These evaluations are presented as a more realistic assessment of heterophily-specific model utility.
  • Development Timeline: Heterophilic GNN research evolved from layer-intercombination, non-local mixing, and hybrid methods toward adaptive aggregation, dynamic routing, self-supervision, and memory-based attention.The timeline covers notable developments from 2018 onward, including JK-Net, GPR-GNN, GCNII, MixHop, Geom-GCN, H2GCN, FAGCN, NCGNN, GREET, and MMP.
Loading 2202.07082v4…