PaperlayerView exact revision on arXiv

Source-linked AI summary

Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?

Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, Doina Precup

arXiv:2109.05641v1cs.LGcs.SI

TL;DR

GNNs do not consistently outperform graph-agnostic networks, and heterophily is considered a factor in that gap. This paper develops similarity-based metrics and an adaptive channel-mixing framework for heterophily; ACM-augmented models achieve state-of-the-art performance on most of 10 real-world tasks.

  • Problem

    GNNs do not always outperform graph-agnostic neural networks, and heterophily is considered one reason for this limited advantage.

    Source: §1 · pp. 1–2

  • Method

    The paper derives similarity-matrix metrics reflecting graph structure and features, then proposes ACM to adaptively combine aggregation, diversification, and identity channels.

    Source: §1 · p. 2, §3.1 · p. 4, §4 · p. 5

  • Results

    ACM(II)-GNNs achieve state-of-the-art performance on 8 out of 10 datasets, and ACMII-GCN has an average rank of 3.40 across all datasets.

    Source: §6.2 · p. 9

  • Takeaways & Limitations

    Heterophily is not uniformly harmful to aggregation-based GNNs, and some harmful cases can be addressed through diversification and adaptive channel use.

    Source: §1 · p. 2, §4 · p. 5

    Diversification does not work well in all harmful-heterophily cases, including imbalanced graphs where small distinctive clusters connect densely to a large cluster.

    Source: §4.3 · p. 8

Abstract

from arXiv · show

Graph Neural Networks (GNNs) extend basic Neural Networks (NNs) by using the graph structures based on the relational inductive bias (homophily assumption). Though GNNs are believed to outperform NNs in real-world tasks, performance advantages of GNNs over graph-agnostic NNs seem not generally satisfactory. Heterophily has been considered as a main cause and numerous works have been put forward to address it. In this paper, we first show that not all cases of heterophily are harmful for GNNs with aggregation operation. Then, we propose new metrics based on a similarity matrix which considers the influence of both graph structure and input features on GNNs. The metrics demonstrate advantages over the commonly used homophily metrics by tests on synthetic graphs. From the metrics and the observations, we find some cases of harmful heterophily can be addressed by diversification operation. With this fact and knowledge of filterbanks, we propose the Adaptive Channel Mixing (ACM) framework to adaptively exploit aggregation, diversification and identity channels in each GNN layer to address harmful heterophily. We validate the ACM-augmented baselines with 10 real-world node classification tasks. They consistently achieve significant performance gain and exceed the state-of-the-art GNNs on most of the tasks without incurring significant computational burden.

1 Introduction

GNNs do not consistently outperform graph-agnostic neural networks, and heterophily is considered one reason for this gap. The paper argues that heterophily is not always harmful and introduces metrics and an adaptive framework to address harmful cases.

1 Introduction

  • GNNs do not always outperform traditional neural networks on relational data, and simple MLPs can sometimes outperform them by a large margin.The introduction identifies heterophily as a believed reason for this performance degradation.Source: §1 · pp. 1–2
  • The paper shows that not all heterophilous graphs harm aggregation-based GNNs and that existing homophily metrics cannot determine whether aggregation makes nodes less distinguishable.It constructs a similarity matrix from backpropagation analysis to derive metrics reflecting graph structure and node features.Source: §1 · p. 2
  • The paper proposes Adaptive Channel Mixing (ACM) to adaptively use aggregation, diversification, and identity channels, reporting performance gains on heterophilous node-classification tasks.The introduction describes synthetic experiments, ablations, and real-world evaluations as supporting the gains.Source: §1 · p. 2

2 Preliminaries

The preliminaries establish graph and feature notation, introduce Laplacian-based operators used by the paper, and define label-based homophily metrics. These metrics quantify graph-label consistency, but they assume inconsistency harms GNN performance.

2 Preliminaries

  • The paper represents an undirected connected graph by G=(V,E,A), with nodes V, edges E, adjacency matrix A, and degree matrix D; node features and labels are stored in X and Z.A graph signal x assigns a scalar x_i to each node, and each row of X is a node feature vector.Source: §2 · p. 2

2.1 Graph Laplacian, Affinity Matrix and Their Variants

  • The graph Laplacian L=D−A is symmetric positive semidefinite, and its eigenvectors form the graph Fourier basis; normalized Laplacian and affinity variants are also introduced.The renormalized affinity matrix adds a self-loop to each node and is used in GCN; the paper uses its random-walk form as a mean aggregator.Source: §2.1 · pp. 2–3

2.2 Metrics of Homophily

  • Edge, node, and class homophily measure label consistency in the graph, with class homophily intended to reduce sensitivity to class imbalance that can mislead edge homophily.The metrics range from 0 to 1, but their definitions imply that inconsistency harms GNN performance.Source: §2.2 · p. 3

3 Analysis of Heterophily

The analysis shows that heterophily does not necessarily make aggregation-based GNNs less effective, motivating metrics that account for the aggregation operator and feature similarity. Synthetic-graph tests find these metrics track model performance more appropriately than conventional homophily measures.

3.1 Motivation and Aggregation Homophily

  • In the bipartite example, nodes exchange colors under mean aggregation yet remain distinguishable, so high heterophily alone does not imply harmful aggregation.The example illustrates why conventional homophily measures can miss label information preserved by aggregation.Source: §3.1 · p. 3
  • The analysis simplifies GCN by removing its nonlinearity and uses a post-aggregation similarity matrix to characterize how aggregation affects node predictions.The matrix is S(Â,X)=ÂX(ÂX)^T; the update direction weights prediction errors by node similarity.Source: §3.1 · pp. 3–4
  • Aggregation homophily measures whether nodes assign greater similarity to same-class nodes after aggregation, capturing distinguishability that other metrics miss in the bipartite example.The paper introduces graph aggregation homophily to evaluate graph structure without considering node features, and a modified aggregation similarity that incorporates the similarity matrix.Source: §3.1 · p. 4

3.2 Evaluation and Comparison on Synthetic Graphs

  • Conventional edge, node, and class homophily yield U-shaped performance curves, whereas aggregation homophily yields a nearly monotonic curve and describes the performance relation more adequately.Figure 2 compares SGC-1 and GCN performance across the homophily metrics.Source: §3.2 · p. 5, Figure 2 · p. 5
  • In synthetic graphs, the worst SGC-1 and GCN performance occurs near edge homophily h=1/7≈0.14, where g(h) is minimized, rather than at h=0.The synthetic setup uses d_intra=2 and C=5; this pattern supports aggregation homophily over edge homophily as an indicator of performance.Source: §3.2 · p. 5

4 Adaptive Channel Mixing (ACM) Framework

The framework combines low- and high-frequency graph information, then adaptively mixes aggregation, diversification, and identity channels to address harmful heterophily. Its scope is limited because diversification does not work in every harmful-heterophily case.

4.1 How Diversification Operation Helps with Harmful Heterophily

  • When aggregation makes nodes 1 and 3 resemble class-2 nodes, their neighborhood differences can still distinguish them from nodes 4–7, motivating high-pass diversification.The high-pass filter I − Â assigns negative weights to nodes 4–7 for nodes 1 and 3, moving them away during backpropagation.Source: §4.1 · p. 6
  • For binary classification with X = Z and the random-walk adjacency, every node is diversification distinguishable, supporting the use of high-frequency information alongside aggregation.Theorem 2 gives DD = 1 under these conditions; aggregation and diversification together form a filterbank that extracts low- and high-frequency information.Source: §4.1 · p. 6

4.2 Filterbank in Spectral and Spatial Forms

  • The framework treats low-pass and high-pass filters as aggregation and diversification, respectively; combining them as a filterbank preserves input information when HLP + HHP = I.The paper also describes Laplacians as high-pass filters, affinity matrices as low-pass filters, and MLPs as a special identity filterbank.Source: §4.2 · p. 7

4.3 Adaptive Channel Mixing(ACM) GNN Framework

  • ACM(II)-GCN extracts three channel components and learns node-wise, feature-conditioned weights to combine them, allowing different nodes to use different channel information.The framework can be plugged into spatial GNNs by replacing the low- and high-pass filters with aggregation and diversification operations.Source: §4.3 · p. 7
  • Diversification may fail to distinguish small, distinctive-label clusters densely connected to a large cluster when their neighborhood differences are similar.The authors also report that ACM(II)-GCN takes approximately twice the running time of the original model.Source: §4.3 · pp. 7–8

5 Prior Work

Prior work addresses heterophily through neighborhood, embedding, label-correlation, and propagation designs; filterbank work also applies multiple signal channels to graph learning.

GNNs on Addressing Heterophily

  • MixHop uses multi-hop neighborhoods, Geom-GCN [33] uses geometric relationships between unsupervised embeddings, and H2GCN separates ego and neighbor embeddings, uses higher-order neighborhoods, and combines intermediate representations.The cited approaches respond to weak homophily or heterophily through different structural and representation choices.Source: §5 · p. 8
  • CPGNN [39] models label correlations with a compatibility matrix, while FAGCN [4] and GPRGNN use negative or signed propagation weights to capture high-frequency information.The passage also notes feature- and label-smoothness measurements as potentially useful for guiding heterophily handling.Source: §5 · p. 8

GNNs with Filterbanks

  • Geometric scattering networks [32] use filterbanks to capture channels of variation and have been applied to over-smoothing, while ACM targets heterophilous graphs.The paper distinguishes its target problem from that of [32].Source: §5 · p. 8

6 Experiments on Real-World Datasets

Across ten real-world benchmark datasets, ACM(II)-augmented models boost baseline performance on almost all tasks and achieve state-of-the-art performance on eight. Ablations indicate that added channels and adaptive mixing help on most datasets, with running time approximately doubled.

6.1 Ablation Study & Efficiency

  • The ablation study applies channel components to SGC-1 and GCN, using ten runs and 60%/20%/20% random train, validation, and test splits.It reports average test accuracy, standard deviation, and average epoch running time.Source: §6.1 · p. 8
  • On most datasets, adding high-pass and identity channels helps, adaptive mixing outperforms directly adding the three channels, and ACM(II) approximately doubles running time.The reported ablations include results on strong-homophily datasets such as Cora, CiteSeer, and PubMed.Source: §6.1 · p. 8

6.2 Comparison with State-of-the-art Models

  • The comparison evaluates several GNN baselines and ACM/ACMII variants on nine established datasets plus Deezer-Europe, using repeated runs and dataset-specific split protocols.Deezer-Europe uses five runs with fixed splits; the other listed datasets use ten runs.Source: §6.2 · p. 9
  • ACM(II)-GNNs achieve state-of-the-art performance on 8 of 10 datasets, and ACMII-GCN has the best average rank at 3.40 across all datasets.The reported results are mean accuracy and standard deviation; ACM(II) boosts baseline performance on almost all tasks.Source: §6.2 · p. 9, Table 2 · p. 10

7 Future Work

The authors identify two boundaries for future work: the metrics mainly capture linear feature relations, and filterbanks cannot properly handle every harmful-heterophily case.

7 Future Work

  • The similarity matrix and derived metrics mainly capture linear relations between aggregated node features, which may be insufficient when nonlinear feature information matters for classification.The authors suggest developing a similarity matrix that captures nonlinear feature relations.Source: §7 · p. 10
  • The filterbank method cannot properly handle all harmful-heterophily cases, leaving more challenging heterophilous graphs for future study.This limitation is linked to the case described in section 4.3.Source: §7 · p. 10

Checklist

The checklist and appendices report research-compliance items, hyperparameter references, implementation choices, computing resources, and derivations. Several appendix passages are fragmentary, so the available text supports only limited detail about those derivations.

Checklist

  • The checklist marks the main claims, limitations discussion, theoretical assumptions and proofs, reproducibility details, training settings, and error-bar reporting as addressed.It points to Appendix G for limitations and to Sections 3–4 and Appendices B, D, and E for assumptions and proofs.Source: Checklist · p. 13
  • The checklist reports average test accuracy across repeated runs with standard deviations, and says the compute details are included in the appendix.It also marks the use of existing assets as cited and identifies the dataset split sources, but reports that asset licenses were not mentioned.Source: Checklist · p. 13

A.1 Hyperparameters Searching Range for GNNs on Synthetic Graphs

  • Table 3 is identified as the hyperparameter-search range for synthetic experiments.The supplied passage gives the table’s scope, not its parameter values.Source: Table 3 · p. 14

A.2 Hyperparameters Searching Range for GNNs on Ablation Study

  • Table 4 is identified as the hyperparameter-search range for the ablation study.The supplied passage gives the table’s scope, not its parameter values.Source: Table 4 · p. 14

A.4 Optimal Hyperparameters for Baselines and ACM(II)-GNNs on Real-world Tasks

A.5 Details of the Implementation of ACM and ACMII Frameworks

  • The implementation discussion says SGC variants are implemented as ACM-SGC because SGC has no nonlinearity, while GCNII and GCNII* are not implemented in ACMII due to an incompatibility involving the unfiltered H(0) term.The passage also calls the ACM(II)-GCN and ACM(II)-snowball implementations straightforward.Source: §A.5 · p. 14

A.6 Computing Resources

  • Experiments use NVIDIA V100 GPUs with 16/32 GB GPU memory, an 8-core CPU, and 16G memory, with software based on PyTorch and PyTorch Geometric [11].The passage gives these resources for synthetic and real-world dataset experiments.Source: §A.6 · p. 15

B.1 Derivation in Matrix Form

  • For the output layer, the text defines ˜X = XW, rewrites L, and reports ∆Y′ ∝ ˆAXXT ˆAT(Z − Y) as the displayed expression labeled (15).Source: §B.1 · p. 18, §B.2 · pp. 19–20

C Details of Synthetic Experiments

The synthetic experiments vary edge homophily over a broad range, using a finer grid at low values. The accompanying proof derives the expected edge counts and an optimal homophily value under its stated setup.

C Details of Synthetic Experiments

  • Synthetic graphs use edge-homophily levels from 0.95 down to 0.05, with a finer 0.005 grid over the low range because GNN performance was empirically sensitive there.For each level, intra-class and inter-class edges are sampled using separate multinomial distributions.Source: C Details of Synthetic Experiments · p. 20

D Proof of Theorem 1

  • Under the proof’s assumptions, a node has expected intra-class and inter-class edge counts of dh and (1 − h)d, respectively, excluding the self-loop from the edge-homophily count.The proof states this setup for graphs with at least two classes.Source: D Proof of Theorem 1 · p. 20
  • For the synthetic generation process, fixing d_intra makes total degree d = d_intra/h, and the proof then derives an optimal h in terms of d_intra.The supplied proof passages do not state the resulting expression.Source: D Proof of Theorem 1 · p. 21

D.1 An extension of Theorem 1

The paper extends its analysis of a similarity-based random variable and proves a two-class condition for diversification distinguishability. On synthetic graphs, ACM-GNNs avoid the underperformance seen for plain GNNs at low aggregation homophily.

D.1 An extension of Theorem 1

  • Under the stated conditions, the symmetric random variable has expectation g(h), so the proof gives P(RV ≥ 0) ≥ 0.5 and relates this to Hagg(G) exceeding 0.5 in many real-world tasks.The passage attributes the probability bound to the variable’s symmetric distribution and the theorem’s conditions.Source: §D.1 · p. 21

E Proof of Theorem 2

  • For two classes, the proof shows that same-class nodes have nonnegative residual-filter similarity and different-class nodes have nonpositive similarity, satisfying the stated diversification-distinguishability conditions.The theorem concludes that the diversification distinguishability measure is 1 in this case.Source: E Proof of Theorem 2 · p. 22

F Model Comparison on Synthetic Graphs

  • At low aggregation homophily, plain GNNs are outperformed by graph-agnostic models by a large margin, while ACM-GNNs do not underperform either comparison group across the reported aggregation-homophily levels.Figures 4 and 5 report test-accuracy comparisons for SGC-1/ACM-SGC-1 and MLP-1, and for MLP-2, GCN, and ACM-GCN, respectively.Source: Figure 4 · p. 23, Figure 5 · p. 23, F Model Comparison on Synthetic Graphs · p. 24

G Discussion of the Limitations of Diversification Operation

The discussion identifies a limitation of high-pass filtering: it can fail to distinguish nodes in different small clusters when their surrounding differences are similar.

G Discussion of the Limitations of Diversification Operation

  • The cited example is presented as a case where the high-pass filter does not work well for harmful heterophily.Figure 6 marks the relevant region with a black box.Source: Figure 6 · p. 24
  • In the illustrated case, nodes in classes 1 and 4, and separately classes 2 and 3, assign nonnegative weights to one another under the high-pass similarity matrix.The passage explains the grouping by similar surrounding differences and notes that this can arise when several small clusters connect to a large one.Source: G Discussion of the Limitations of… · p. 24
  • When distinct small clusters connect to a large cluster and their surrounding differences become similar, the high-pass filter cannot distinguish nodes from those clusters.This is the practical setting the discussion identifies for the illustrated limitation.Source: G Discussion of the Limitations of… · p. 24

H The Similarity, Homophily and DD ˆ A,X(G) Metrics and Their Estimations

The section uses similarity-based metrics to examine how graph structure and node features relate to labels before and after aggregation. Its examples show that conventional heterophily scores alone do not explain when GCNs outperform or underperform MLPs, while the proposed scores are not definitive performance thresholds.

H The Similarity, Homophily and DD ˆ A,X(G) Metrics and Their Estimations

  • The metrics distinguish graph-label, feature-label, and aggregated-feature-label consistency to help separate structural from feature-related factors in GNN performance.The authors report that combining the metrics can help identify what might cause performance degradation.Source: H The Similarity, Homophily and DD ˆ… · pp. 24–25
  • For Cornell, Wisconsin, Texas, and Film, aggregation homophily suggests graph structure is not the main cause of GCN underperformance; lower aggregated-feature-label consistency implicates feature aggregation.The passage attributes the performance degradation to aggregated-feature-label inconsistency relative to feature-label consistency.Source: H The Similarity, Homophily and DD ˆ… · p. 24
  • GCN outperforms MLP-2 on Chameleon and Squirrel despite conventional heterophily warnings; on Chameleon, graph-label and aggregated-feature-label consistency help explain the gain.The authors report that traditional homophily metrics fail to explain these results.Source: H The Similarity, Homophily and DD ˆ… · pp. 24–25
  • The estimated metrics are reported accurate within an acceptable error range using a subset of labels, a setting the authors identify as important for real-world applications.The estimation procedure uses training labels after a random 60%/20%/20% train/validation/test split and repeats each estimation 10 times.Source: H The Similarity, Homophily and DD ˆ… · p. 25

I Experiments on Fixed Splits Provided by [33]

J A Detailed Explanation of the Differences Between ACM(II)-GNNs and Several SOTA Models

  • The appendix contrasts ACM's channel mixing with GPRGNN's learning mechanism and compares ACM's node-wise mixing with FAGCN's learned filter, rather than claiming fixed filters are superior.The authors point to real-world task results in Tables 2 and 9 for comparing models with fixed filters and node-wise channel mixing against models with learned filters but no channel mixing.Source: J A Detailed Explanation of the… · p. 26
Loading 2109.05641v1…