Source-linked AI summary
Revisiting Heterophily For Graph Neural Networks
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, Doina Precup
TL;DR
GNNs can underperform traditional NNs on relational data, and existing homophily metrics inadequately characterize harmful heterophily. The paper introduces post-aggregation similarity metrics and ACM, which adaptively mixes aggregation, diversification, and identity channels. Across benchmark tasks, ACM-augmented baselines show substantial gains and often exceed state-of-the-art models, with increased computation and known scope limitations.
Problem
GNNs are not always advantageous on relational data, while existing homophily metrics consider only graph-label consistency and may miss aggregation-relevant heterophily.
Method
The paper defines post-aggregation node similarity metrics, proves that diversification addresses some harmful heterophily cases, and proposes ACM to mix aggregation, diversification, and identity channels adaptively by node.
Results
ACM-augmented baselines achieved 2.04%∼27.50% gains across six benchmark heterophily tasks and significantly outperformed current SOTA models on five named datasets.
Takeaways & Limitations
Adaptive multi-channel filtering provides richer localized information for diverse heterophily situations and can be combined with different GNN architectures.
Takeaways & Limitations
The similarity matrix mainly captures linear, feature-independent relationships, and diversification cannot properly handle all harmful heterophily cases.
Abstract
from arXiv · showhide
Graph Neural Networks (GNNs) extend basic Neural Networks (NNs) by using graph structures based on the relational inductive bias (homophily assumption). While GNNs have been commonly believed to outperform NNs in real-world tasks, recent work has identified a non-trivial set of datasets where their performance compared to NNs is not satisfactory. Heterophily has been considered the main cause of this empirical observation and numerous works have been put forward to address it. In this paper, we first revisit the widely used homophily metrics and point out that their consideration of only graph-label consistency is a shortcoming. Then, we study heterophily from the perspective of post-aggregation node similarity and define new homophily metrics, which are potentially advantageous compared to existing ones. Based on this investigation, we prove that some harmful cases of heterophily can be effectively addressed by local diversification operation. Then, we propose the Adaptive Channel Mixing (ACM), a framework to adaptively exploit aggregation, diversification and identity channels node-wisely to extract richer localized information for diverse node heterophily situations. ACM is more powerful than the commonly used uni-channel framework for node classification tasks on heterophilic graphs and is easy to be implemented in baseline GNN layers. When evaluated on 10 benchmark node classification tasks, ACM-augmented baselines consistently achieve significant performance gain, exceeding state-of-the-art GNNs on most tasks without incurring significant computational burden.
1 Introduction
The paper argues that existing homophily metrics miss how heterophily affects aggregation and introduces ACM to adaptively combine multiple information channels. ACM improves baseline GNNs substantially on heterophilic graphs while remaining competitive on homophilic graphs.
- Motivation: GNNs are not always advantageous over traditional NNs on relational data, with heterophily believed to be an important reason.In some cases, even simple MLPs outperform GNNs by a large margin.
- Motivation: Existing homophily metrics are limited because they consider only graph-label consistency and cannot describe some aggregation effects of heterophily.The paper instead studies post-aggregation node similarity and derives new homophily metrics.
- Approach: The paper proves that local diversification can address some harmful heterophily cases and motivates adaptive use of different filters.The analysis identifies aggregation, diversification, and identity as complementary channels for localized information.
- Approach: ACM adaptively mixes aggregation, diversification, and identity channels node-wisely and locally, augmenting uni-channel baseline GNNs.The framework is designed to account for diverse local heterophily and can be combined with different GNN architectures.
- Results: 2.04% ∼27.5% performance gains were obtained for three baseline GNNs across seven benchmark heterophilic graphs, exceeding SOTA models on all of them.On three homophilic graphs, ACM-augmented GNNs performed at least as well as the uni-channel baselines and remained competitive with SOTA.
2 Preliminaries
The paper introduces graph notation and spectral filtering foundations, then defines standard homophily metrics based on graph-label consistency. These metrics motivate the paper’s post-aggregation perspective.
- Graph notation: The graph is modeled as an undirected connected graph G = (V, E, A) with N nodes and a symmetric adjacency matrix.The feature matrix X stores graph signals by columns, while Z stores one-hot node-label encodings.
- Graph operators: The graph Laplacian L = D −A is symmetric positive semi-definite and has eigenvalues interpreted as graph-signal frequencies.Its eigendecomposition provides the graph Fourier basis.
- Graph operators: Affinity matrices act as low-pass filters, whereas graph Laplacians and their variants act as high-pass filters.Random-walk and symmetric normalized affinity matrices have corresponding normalized Laplacians and are used to represent aggregation choices.
- Graph operators: The renormalized affinity matrix adds self-loops and is widely used in GCNs; the random-walk form behaves as a mean aggregator.The paper uses the random-walk renormalized matrix to bridge spectral and spatial GNN methods.
- Homophily metrics: Edge, node, and class homophily measure graph-label consistency, with values near one indicating homophily and values near zero indicating heterophily.Class homophily additionally aims to reduce sensitivity to imbalanced classes.
3 Analysis of Heterophily
Existing homophily metrics can mischaracterize heterophily because they ignore how graph structure affects post-aggregation node similarity. The proposed aggregation-based metrics better indicate how graph structure influences GNN performance.
- Motivation and Aggregation Homophily: Highly heterophilic graphs can remain class-distinguishable after aggregation, so graph-label consistency alone does not fully characterize harmful heterophily.In the bipartite example, mean aggregation exchanges class colors while preserving distinguishability.
- Motivation and Aggregation Homophily: The post-aggregation similarity matrix measures pairwise similarity between aggregated node features and relates to single-layer GNN behavior.Its entries can be interpreted as weights determining how node predictions are updated from prediction errors.
- Aggregation Homophily: Aggregation homophily incorporates the aggregation operator and post-aggregation similarity, unlike existing metrics based only on graph-label consistency.The metric evaluates whether aggregated nodes assign greater average weight to nodes of their own class.
- Aggregation Homophily: In the bipartite example, H^M_agg(G) = 1 while existing metrics equal 0, correctly reflecting preserved class distinguishability after aggregation.This demonstrates the metric’s advantage for the harmless heterophily case.
- Empirical Evaluation and Comparison on Synthetic Graphs: On synthetic graphs, performance curves under edge, node and class homophily are U-shaped, whereas aggregation homophily yields a nearly monotonic curve.The comparison evaluates SGC-1 and GCN across generated graphs with varying homophily levels.
4 Adaptive Channel Mixing (ACM)
Diversification extracts neighborhood differences that can resolve harmful heterophily, but different nodes may require different filtering choices. ACM therefore mixes aggregation, diversification and identity channels node-wise.
- Diversification Helps with Harmful Heterophily: A high-pass filter can extract neighborhood differences and address some harmful heterophily locally.The paper proves this under stated conditions and shows that nodes can remain distinguishable through local surrounding dissimilarities.
- Diversification Helps with Harmful Heterophily: Diversification assigns negative weights to dissimilar neighbors, helping separate nodes that aggregation makes similar.In the example, nodes {1, 3} move away from nodes {4, 5, 6, 7} during backpropagation.
- Diversification Helps with Harmful Heterophily: In the two-class setting with X = Z and random-walk aggregation, every node is diversification distinguishable and DD_A,Z(G) = 1.This is the stated theoretical result for the diversification operation I − Â_rw.
- Filterbank and Adaptive Channel Mixing (ACM) Framework: ACM combines low-pass aggregation, high-pass diversification and identity channels to adapt to diverse local homophily patterns.Different nodes may need different channels, such as HP for nodes {1, 3} and LP for node 2.
- Filterbank and Adaptive Channel Mixing (ACM) Framework: ACM learns node-wise channel weights and can be integrated into baseline GNN layers through a three-channel architecture.The framework extracts channel features, learns row-wise feature-based weights, and performs adaptive channel mixing.
- Filterbank and Adaptive Channel Mixing (ACM) Framework: ACM layers use more learnable parameters and computation than GCN layers, with detailed runtime comparisons reported separately.For layer l, ACM(II)-GCN has 3F_l−1(F_l + 1) + 9 learnable parameters versus F_l−1F_l in GCN.
- Filterbank and Adaptive Channel Mixing (ACM) Framework: Diversification may fail when small, imbalanced clusters connect densely to one large cluster with similar surrounding differences.In that setting, neighborhood differences may not discriminate nodes in the small clusters.
5 Related Work
Prior work addresses heterophilic graphs through multi-hop feature extraction, smoothness-based measurements and geometry-informed graph representations.
- Related Work: MixHop extracts features from multi-hop neighborhoods to address learning difficulty on graphs with weak homophily.Other approaches use feature and label smoothness measurements to guide GNNs on heterophilic graphs.
- Related Work: Geom-GCN precomputes unsupervised node embeddings and uses graph structure defined by geometric relations.These approaches represent alternative strategies for handling graph heterophily.
6 Empirical Evaluation
The evaluation combines ablations, efficiency measurements, and comparisons with baseline and state-of-the-art models across real-world graph datasets. ACM-augmented models improve baseline performance substantially while adding adaptive channel use and limited computational burden.
- Ablation Study & Efficiency: ACM components were evaluated through ablations on nine benchmark datasets using repeated runs, random data splits, test accuracy, standard deviation, and per-epoch runtime.The study applies ACM components to SGC-1 and ACM/ACMII components to GCN.
- Ablation Study & Efficiency: Additional high-pass and identity channels help on most datasets, while adaptive mixing outperforms directly adding the three channels.The results support node-specific customization of channel usage; t-SNE visualizations also show meaningful patterns from high-pass and identity channels.
- Experimental Setup: The framework is designed to combine with multiple GNN architectures and supports low-pass, high-pass, and identity filtering channels.The experiments include SGC, GCNII, GCN, and snowball networks, alongside baseline and state-of-the-art comparisons.
- Comparison with Baseline and SOTA Models: ACM and ACMII augmentations boost three baseline models by 2.04%∼27.50% across all six selected heterophily tasks.The augmented baselines achieve state-of-the-art performance in the plotted comparisons.
- Comparison with Baseline and SOTA Models: On Cornell, Wisconsin, Texas, Chameleon, and Squirrel, augmented baselines significantly outperform current state-of-the-art models.The reported comparison covers six commonly used benchmark heterophily datasets.
7 Conclusions and Limitations
The paper concludes that post-aggregation similarity metrics and adaptive multi-channel mixing improve heterophilic graph learning. It also identifies limitations involving linear, feature-independent similarity analysis and incomplete coverage of harmful heterophily.
- Limitations: The proposed similarity matrix and homophily metrics primarily capture linear, feature-independent relationships between aggregated node features.The authors suggest investigating similarity matrices that capture nonlinear and feature-dependent relations.
- Limitations: The filterbank method cannot properly handle all cases of harmful heterophily, motivating exploration of alternative approaches.Despite this limitation, the multi-channel mechanism supports adaptive high-pass, low-pass, or identity filtering at different nodes.
Checklist
The paper reports completed methodological, experimental, reproducibility, and ethics checks alongside benchmark results. Experiments use repeated evaluations, reported variability, specified splits, and comparisons on real-world datasets.
- Reproducibility and Ethics: The checklist indicates that the paper reports assumptions, proofs, code and data availability, training details, repeated-run error bars, and computational resources.It also states that authors discussed limitations and found no applicable participant or societal-impact concerns.
- Experimental Results: The full experiments report average accuracy and standard deviation, with ACM or ACMII boosting baselines on almost all tasks and achieving state-of-the-art performance on 9 of 10 datasets.ACMII-GCN+ has the best reported average rank, 4.40, across datasets.
- Experimental Protocol: The experiments use random 60%/20%/20% train, validation, and test splits, with fixed-split comparisons reported separately.The paper states that the same conclusion is obtained for the fixed-split results.
A.4 Ablation Study of Wmix
The ablation studies examine adaptive channel mixing, feature choices, and compatibility across ACM variants and baseline architectures. Wmix generally improves channel-weight diversity, while combined features add cost without significant performance gains.
- Wmix: ACM(II) with Wmix is superior on most datasets, although improvements are not statistically significant on some.
- Wmix: Wmix can mitigate majority bias by enabling more diverse node-wise channel weights when shared feature transformations favor prevalent patterns.
- Raw Features versus Combined Features: Raw and combined feature variants show no significant performance difference in Table 6.
- Raw Features versus Combined Features: Combined features increase computational cost, so the authors choose raw features because redundant channel-extraction information does not improve performance.
- Architecture Compatibility: GCNII and GCNII* are not implemented under ACMII because their residual H(0) term makes aggregation and nonlinear feature extraction order-incompatible.
C.4 Searched Optimal Hyperparameters for Baselines and ACM(II)-GNNs on Real-world Tasks
The appendix documents hyperparameter searches and synthetic-data construction for baseline, ACM, and ACMII models. Synthetic experiments show ACM models remain competitive across aggregation-homophily levels and avoid the severe failures of baseline GNNs on harmful graphs.
- Hyperparameter Search: Hyperparameters are reported separately for random 60%/20%/20% and fixed 48%/32%/20% data splits.
- Synthetic Model Comparison: ACM-GNNs do not underperform baseline GNNs or graph-agnostic models at any aggregation-homophily level in the synthetic experiments.
- Synthetic Model Comparison: When aggregation homophily is small, baseline GNNs are outperformed by graph-agnostic models by a large margin.
D.3 Further Discussion of Aggregation Homophily on Regular Graphs
Regular-graph analysis explains why aggregation performance can be non-monotonic in edge homophily. The derived aggregation-similarity function predicts the observed worst point in the synthetic performance curve.
- Regular-Graph Experiments: The performance turning point in Figure 12 occurs at an edge-homophily level slightly below 0.2.
- Regular-Graph Analysis: The proposition assumes a d-regular graph with independently generated edges having same-class probability h and random-walk aggregation.
- Regular-Graph Analysis: For the synthetic setting with dintra=10 and C=5, g(h) reaches its minimum at h=5/27≈0.1852, matching the lowest SGC-1 and GCN performance.
- Regular-Graph Analysis: g(h) measures the expected similarity difference between same-class and other-class nodes and is linked to aggregation homophily.
- Regular-Graph Analysis: Because the similarity-difference variable is symmetric with minimum expectation zero, aggregation homophily is at least 0.5 in many real-world tasks.
- Diversification: Diversification is perfectly distinguishable in the stated two-class case, with DD_A,X(G)=1.
I The Similarity, Homophily and DD ˆ A,X(G) Metrics and Their Estimations
The paper extends homophily analysis beyond graph-label consistency using aggregation-based similarity and feature-label consistency. These metrics help explain when aggregation harms or improves graph-aware models, while remaining estimable from partial labels.
- Metric Interpretation: On Cornell, Wisconsin, Texas, and Film, lower aggregated-feature-label consistency than raw-feature consistency is associated with aggregation degrading node-feature quality.
- Metric Interpretation: The proposed metrics are reported as more instructive than existing homophily measures for comparing graph-aware and graph-agnostic models.
- Metric Interpretation: Chameleon and Squirrel show that very low traditional homophily does not preclude GCN from outperforming MLP-2.
- Limitations: The aggregation similarity scores are not decisive because they do not account for nonlinear feature structure, so low scores do not guarantee poor GNN performance.
- Metric Estimation: Metric estimates based only on training labels are accurate, with errors within an acceptable range.
- Relation to Prior Work: ACM differs from GPRGNN and FAGCN by learning distinct channel transformations and node-wise adaptive mixing rather than shared or simple additive mixing.