PaperlayerView exact revision on arXiv

Source-linked AI summary

Is Homophily a Necessity for Graph Neural Networks?

Yao Ma, Xiaorui Liu, Neil Shah, Jiliang Tang

arXiv:2106.06134v4cs.LGstat.ML

TL;DR

Semi-supervised node classification with GNNs is often linked to homophily, raising whether GCNs can generalize to heterophilous graphs. This paper combines theory, controlled graph analyses, and benchmark experiments to characterize when GCNs succeed, finding that neighborhood-pattern similarity—not homophily alone—can support strong performance.

  • Problem

    The paper examines whether strong homophily is necessary for GCNs to achieve good semi-supervised node-classification performance.

  • Method

    The authors analyze GCN embeddings theoretically, study controlled graph models and neighborhood distributions, and evaluate benchmark graphs empirically.

  • Results

    GCNs can perform strongly on some heterophilous graphs when same-label nodes share similar neighborhood patterns and different classes remain distinguishable.

  • Takeaways & Limitations

    Homophily is not necessary for strong GCN performance; the relevant condition is whether neighborhood patterns support similar same-label embeddings and class separation.

  • Takeaways & Limitations

    The theoretical analysis relies on assumptions about feature distributions, feature dimensions, bounded features, and independently sampled neighbor labels.

Abstract

from arXiv · show

Graph neural networks (GNNs) have shown great prowess in learning representations suitable for numerous graph-based machine learning tasks. When applied to semi-supervised node classification, 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 such carefully designed methods on some commonly used heterophilous graphs. This motivates us to reconsider whether homophily is truly necessary for good GNN performance. We find that this claim is not quite true, and in fact, GCNs can achieve strong performance on heterophilous graphs under certain conditions. Our work carefully characterizes these conditions, and provides supporting theoretical understanding and empirical observations. Finally, we examine existing heterophilous graphs benchmarks and reconcile how the GCN (under)performs on them based on this understanding.

1 INTRODUCTION

This paper revisits the belief that strong homophily is essential for GNN success, finding that GCNs can perform well on some heterophilous graphs under suitable conditions.

  • A perfectly heterophilous graph can still yield perfect GCN performance through neighborhood feature aggregation.In the toy example, one-layer aggregation maps blue nodes to 1 and orange nodes to 0.
  • GCNs can outperform heterophily-specific models on some heterophilous graphs after careful hyperparameter tuning.
  • GCNs can achieve good performance when same-label nodes share similar neighborhood patterns, regardless of graph homophily or heterophily.
  • The paper distinguishes “good” heterophily, where GCNs can perform strongly, from “bad” heterophily, where they usually fail.
  • The study characterizes these conditions theoretically and examines commonly used homophilous and heterophilous benchmarks to explain GCN performance.

2 PRELIMINARIES

The preliminaries define graph structure, node features, labels, homophily, and GNN aggregation, establishing the notation and task setting used throughout the paper.

  • A graph consists of nodes V and edges E, with adjacency matrix A encoding which node pairs are connected.
  • Each node has a feature vector x_i and label y_i, while labels are observed only for a subset of nodes in semi-supervised node classification.
  • Homophily is measured by the fraction of edges connecting nodes with the same labels.
  • Graphs with large homophily ratios are considered highly homophilous, whereas graphs with low ratios are considered heterophilous.
  • GNNs learn node representations by aggregating and transforming information over graph structure.
  • A GCN operation transforms and averages neighboring features using a degree matrix and learnable parameter matrix.Locally, the aggregation averages transformed features from a node’s neighbors, which may include the node itself.

3 GRAPH CONVOLUTIONAL NETWORKS UNDER HETEROPHILY

The paper revisits whether GCNs require homophily and finds that they can perform well on heterophilous graphs when same-label nodes share similar, distinguishable neighborhood patterns. Theory and experiments connect GCN performance to neighborhood-distribution similarity, node degree, and noise rather than homophily alone.

  • Empirical motivation: Prior work treats GCNs as ill-suited to heterophilous graphs, but careful tuning lets GCNs outperform heterophily-specific models on some benchmarks.This motivates reconsidering whether strong homophily is crucial for strong GCN performance.
  • Conditions for GCN performance: GCNs can work well when nodes with the same label share similar neighborhood patterns, even when the graph is heterophilous.The paper distinguishes “good” heterophily from “bad” heterophily according to neighborhood-pattern structure.
  • Theoretical explanation: Under the paper’s assumptions, same-label nodes have equal expected GCN embeddings, while higher-degree nodes are more likely to lie close to those expectations.Good classification additionally requires different classes to have distinguishable neighborhood distributions.
  • Theoretical explanation: GCN aggregation can improve linear separability when node degree exceeds (p + q)^2/(p − q)^2 in the two-class CSBM analysis.The threshold depends on degree and the distinguishability of neighborhood distributions.
  • Theoretical explanation: When p = 9q or 9p = q, the threshold is approximately 1.23, so nodes with degree greater than 1 can benefit under both extreme homophily and extreme heterophily.When p ≈ q, neighborhood distributions are hard to distinguish and only extremely high-degree nodes can benefit; when p = q, GCN aggregation cannot help.
  • Empirical observations: On synthetic Cora graphs, GCN accuracy follows a V-shape as homophily decreases, reaching 86% accuracy at h = 0.25.Further targeted edge additions can continue increasing performance, indicating that GCNs can work well under certain heterophilous conditions.
  • Empirical observations: At h = 0.25, increasing neighborhood-distribution noise γ worsens performance, showing that similarity among neighborhood patterns matters beyond the homophily ratio.When noise is sufficiently high, adding edges continually decreases performance.

4 REVISITING GCN’S PERFORMANCE ON REAL-WORLD GRAPHS

The section evaluates GCNs and MLPs on real-world graphs, then interprets GCN performance through cross-class neighborhood similarity. GCNs perform well when class neighborhoods are distinguishable, but poorly when intra- and inter-class similarities converge.

  • Experimental setup: The experiments compare GCN and MLP performance across homophilous citation networks and heterophilous benchmark graphs.Datasets include Cora, Citeseer, Pubmed, Chameleon, Squirrel, Actor, Cornell, Wisconsin, and Texas.
  • Qualitative analysis: Cross-class neighborhood similarity is used to explain why GCN succeeds or fails on individual datasets.The analysis examines representative datasets including Cora, Chameleon, Actor, and Cornell.
  • Cora: Cora has substantially higher intra-class than inter-class neighborhood similarity, indicating distinct neighborhood patterns.
  • Chameleon: Chameleon generally has higher intra-class than inter-class similarity, but label-group gaps may increase errors within groups.
  • Actor and Cornell: Actor and Cornell have nearly equivalent intra-class and inter-class similarities, making class neighborhoods difficult to distinguish and producing poor GCN performance.Cornell’s 183 nodes and 280 edges make its similarity estimates especially sensitive to individual nodes.

5 RELATED WORK

The related-work section situates GCNs within the development of graph neural networks and summarizes the view that their aggregation behaves as feature smoothing. Recent work consequently links GNN performance to homophily and proposes variants for heterophilous graphs.

  • Graph neural network development: GCNs simplify earlier spectral graph neural networks and motivated numerous variants differing in feature transformation and aggregation.
  • Homophily assumptions: GNN aggregation is commonly understood as feature smoothing, motivating claims that strong homophily is important for their effectiveness.
  • Heterophily-focused work: Recent studies claim, assume, or remark that GNNs have homophily-related limitations and develop methods targeting heterophilous graphs.

6 CONCLUSION

The paper concludes that strong homophily is not necessary for GCN performance. Its analysis and experiments instead relate success to neighborhood-pattern separability, while acknowledging that bad heterophily remains challenging.

  • Conclusion: The paper’s supported conclusion is that GCNs can work well on heterophilous graphs when same-label nodes share similar neighborhood patterns and classes remain distinguishable.
  • Conclusion: Bad heterophily still poses challenges for GNN models, so dedicated efforts remain necessary.
  • Theoretical analysis: The paper’s theoretical analysis characterizes when GCNs learn similar embeddings for same-label nodes under distributional assumptions.
  • CSBM analysis: In the CSBM analysis, GCN embeddings can improve classification over raw features when node degree exceeds (p + q)^2/(p − q)^2.
  • Synthetic experiments: The generated-graph experiments vary neighborhood-distribution structure, added edges K, and homophily ratio h to examine GCN behavior.The distributions are specified separately for Cora- and Citeseer-based graphs.

C.2 RESULTS ON MORE DATASETS: CH A M E L E O N AND SQ U I R R E L

Experiments on graphs generated from Squirrel and Chameleon show that GCN performance can initially decline and later improve as designed heterophilous edge patterns dominate. In the limit of many added edges, GCN accuracy approaches 100% while homophily approaches zero.

  • Results on more datasets: Chameleon and Squirrel: On Squirrel and Chameleon, GCN performance follows a V-shape as edges are added.Performance first decreases, then increases as the designed neighborhood pattern masks the original graph patterns.
  • GCN’s performance in the limit: As K →∞, the homophily ratio approaches 0 while GCN accuracy approaches 100%.This behavior is observed for sufficiently diverse class-conditional neighbor distributions.
  • Graph generation procedure: The edge-addition procedure samples a node, draws a target label from D_yi, and connects to a uniformly sampled node of that label.With noise level γ, an edge is added when a uniform random draw is at most γ.
  • Model comparison: The experiments compare standard GCN with H2GCN, GPRGNN, and CPGNN, which were designed specifically for heterophilous graphs.The comparison focuses on whether a carefully tuned standard GCN can outperform heterophily-specific methods.

D.1 DATASETS

The dataset section summarizes the benchmark graphs and describes an MLP+GCN classifier that linearly combines two-layer GCN and MLP outputs before classification. Parameters are tuned over shared search ranges to support fair comparisons.

  • Datasets: The study reports node counts, edge counts, homophily ratios, and class counts for its datasets.These benchmark summary statistics are provided in Table 8.
  • MLP+GCN: MLP+GCN linearly combines the output features of two-layer GCN and MLP models for classification.The GCN and MLP outputs each have dimensions |V|×|C|, and α balances the two components before row-wise softmax.
  • Experimental settings: The parameter search tunes learning rate, weight decay, and dropout across predefined option sets.For MLP+GCN, α is searched over {0.2, 0.4, 0.6, 0.8, 1}; GPR-GNN uses PPR initialization.
  • Experimental settings: Experiments run on Intel Xeon E5-2680 v4 CPUs and NVIDIA Tesla K80 GPUs.The reported hardware setup uses a cluster environment.

E HEATMAPS FOR OTHER BENCHMARKS

Heatmaps compare intra-class and inter-class neighborhood similarity across additional benchmarks. High-homophily graphs show clearer within-class similarity, while Squirrel exhibits weaker and more mixed patterns.

  • Heatmaps for other benchmarks: Squirrel’s intra-class similarity is generally higher than inter-class similarity, but the differences are weak.Its mixed neighborhood patterns are consistent with middling GCN performance.
  • Heatmaps for other benchmarks: Citeseer and Pubmed have higher intra-class neighborhood similarity than inter-class similarity.The heatmaps show this pattern clearly on both graphs.

F EXTENDING THEOREM 2 TO MULTIPLE CLASSES

The multi-class extension analyzes how GCN changes class means and variances in a K-class CSBM. GCN reduces both inter-class distances and intra-class spread, so separability improves when variance reduction outweighs mean-distance contraction.

  • Model and setup: The K-class CSBM uses equal-sized class sets with intra-class edge probability p and inter-class edge probability q.Node features are sampled for each class, and the analysis considers the resulting Gaussian embeddings.
  • Decision geometry: The multi-class construction uses equidistant class means and hyperplanes that partition the feature space into class-specific decision regions.For three classes, the means form an equilateral triangle and the decision boundaries create three areas.
  • Effects of graph convolution: After graph convolution, classes remain symmetric, while inter-class mean distances and intra-class standard deviations are reduced.The distance reduction factor depends on p, q, and K; the variance reduction depends on node degree.
  • Implications for separability: Linear separability reflects a trade-off between reduced inter-class distance, which impairs separation, and reduced within-class deviation, which improves it.The analysis rescales class distances before comparing misclassification probabilities.
  • Threshold condition: For nodes with degree larger than (p+(K−1)q)^2/(p−q)^2, GCN can reduce the misclassification rate.Below the corresponding threshold, the misclassification probability increases after graph convolution.

G OTHER METRICS THAN COSINE SIMILARITY

Using Euclidean and Hellinger distances instead of cosine similarity yields similar cross-class neighborhood patterns on Chameleon. Additional synthetic Cora and Citeseer experiments produce V-shaped GCN performance curves under the tested neighborhood distributions.

  • G OTHER METRICS THAN COSINE SIMILARITY: Euclidean and Hellinger distance heatmaps show patterns similar to those obtained with cosine similarity on Chameleon.Because larger distance means lower similarity, Figure 11 values should be interpreted oppositely to Figure 5.
  • G OTHER METRICS THAN COSINE SIMILARITY: The additional Cora neighborhood-distribution experiments generate graphs following two named patterns and evaluate GCN performance on them.Figures 12 and 13 correspond to Cora Neighborhood Distribution Patterns 1 and 2.
  • G OTHER METRICS THAN COSINE SIMILARITY: The additional Citeseer neighborhood-distribution experiments likewise evaluate GCN performance under two named patterns.Figures 14 and 15 correspond to Citeseer Neighborhood Distribution Patterns 1 and 2.
  • G OTHER METRICS THAN COSINE SIMILARITY: Cora and Citeseer results under these additional patterns present V-shaped curves similar to the γ=0 curves in Figure 3.The stated similarity applies to Figures 12–15.

H.1.2 EXTREME NEIGHBORHOOD DISTRIBUTION PATTERNS

Extreme single and all neighborhood distributions further test whether distinguishable class-specific patterns support GCN performance under low homophily. Single patterns can yield near-perfect performance, whereas overlapping all-pattern distributions limit performance even at very low homophily.

  • H.1.2 EXTREME NEIGHBORHOOD DISTRIBUTION PATTERNS: Extreme patterns represent labels connected to a single different label or to all other labels except themselves.The paper names these configurations single and all neighborhood distributions.
  • H.1.2 EXTREME NEIGHBORHOOD DISTRIBUTION PATTERNS: Almost perfect GCN performance occurs on Cora single-pattern graphs as homophily approaches 0.The paper attributes this to clearly distinguishable single neighborhood distributions across labels.
  • H.1.2 EXTREME NEIGHBORHOOD DISTRIBUTION PATTERNS: Around 70% GCN performance remains on the rightmost Cora all-pattern graph, where homophily is 0.03 despite adding almost 50 times as many edges.The all-pattern distributions are similar because different labels share four labels, producing less distinguishable heterophily.
  • H.1.2 EXTREME NEIGHBORHOOD DISTRIBUTION PATTERNS: Citeseer experiments show observations similar to those made for Cora.The Citeseer single-pattern result is shown in Figure 18, and the all-pattern result in Figure 19.

I LIMITATION

The theoretical analysis is bounded by simplifying assumptions and by its graph and model scope. The authors identify nonlinearity, feature independence, sparse-graph modeling, and extension beyond GCNs as areas requiring further investigation.

  • I LIMITATION: The analysis drops GCN nonlinearity, assumes feature independence in Theorem 2, and therefore has limited generality.The experiments suggest the analysis holds with nonlinearity, but formal investigation remains valuable.
  • I LIMITATION: The CSBM-based theory is not ideal for modeling sparse graphs commonly observed in real-world settings.The authors call for analysis of more general graphs.
  • I LIMITATION: The current theoretical analysis focuses mainly on GCNs, with future work extending it to more general message-passing neural networks.The paper notes that a similar analysis line may apply to broader message-passing models.
Loading 2106.06134v4…