PaperlayerView exact revision on arXiv

Source-linked AI summary

Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks

Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, Danai Koutra

arXiv:2102.06462v8cs.LG

TL;DR

GCNs suffer from oversmoothing as depth increases and may perform poorly on heterophilous graphs, yet these problems have largely been studied separately. This paper unifies them through node-level metrics for relative degree and heterophily, then uses the resulting insights to design GGCN’s edge corrections. GGCN is reported to be robust to oversmoothing and effective on both heterophilous and homophilous datasets.

  • Problem

    GCNs face oversmoothing with increasing depth and degraded performance on heterophilous graphs, while the two problems have mostly been studied independently.

  • Method

    The paper profiles nodes using relative degree and node-level heterophily, then applies structure-based and feature-based edge corrections, including signed edge weights.

  • Results

    GGCN is reported as robust to oversmoothing, state-of-the-art on highly heterophilous datasets, and competitive on homophilous datasets.

  • Takeaways & Limitations

    Studying oversmoothing and heterophily jointly yields theoretically grounded architectural directions for improving learned GNN representations across domains.

  • Takeaways & Limitations

    Signed edges may hurt performance when a low error rate cannot be guaranteed, and the paper notes a discrepancy in reported versus actual data-split ratios.

Abstract

from arXiv · show

In node classification tasks, graph convolutional neural networks (GCNs) have demonstrated competitive performance over traditional methods on diverse graph data. However, it is known that the performance of GCNs degrades with increasing number of layers (oversmoothing problem) and recent studies have also shown that GCNs may perform worse in heterophilous graphs, where neighboring nodes tend to belong to different classes (heterophily problem). These two problems are usually viewed as unrelated, and thus are studied independently, often at the graph filter level from a spectral perspective. We are the first to take a unified perspective to jointly explain the oversmoothing and heterophily problems at the node level. Specifically, we profile the nodes via two quantitative metrics: the relative degree of a node (compared to its neighbors) and the node-level heterophily. Our theory shows that the interplay of these two profiling metrics defines three cases of node behaviors, which explain the oversmoothing and heterophily problems jointly and can predict the performance of GCNs. Based on insights from our theory, we show theoretically and empirically the effectiveness of two strategies: structure-based edge correction, which learns corrected edge weights from structural properties (i.e., degrees), and feature-based edge correction, which learns signed edge weights from node features. Compared to other approaches, which tend to handle well either heterophily or oversmoothing, we show that {our model, GGCN}, which incorporates the two strategies performs well in both problems.

1. Introduction

GCNs face two performance-degradation problems—oversmoothing with depth and heterophily on graphs whose neighboring nodes often have different classes. The paper unifies them through node-level profiling and motivates GGCN’s structure- and feature-based edge corrections.

  • GCN performance worsens as the number of layers increases, a failure mode termed the oversmoothing problem.
  • GCNs may perform poorly on heterophilous graphs, where many neighboring nodes belong to different classes.
  • Existing heterophily methods use spectral high-frequency filters but neglect that different node behaviors can affect performance differently.
  • Relative degree and node-level heterophily jointly define three node behaviors, two associated with performance degradation.
  • The paper proposes structure-based edge correction and feature-based correction with signed edge weights to address both problems.
  • GGCN combines both correction strategies and is reported as robust to oversmoothing, state-of-the-art on highly heterophilous datasets, and competitive on homophilous datasets.

2. Preliminaries

The preliminaries formulate supervised node classification and describe GCNs as propagation, aggregation, and combination operations. They also present the normalized adjacency propagation used by vanilla GCNs and the linear SGC simplification.

  • The notation defines graph adjacency, node degrees, neighbor sets, node representations, input features, layer parameters, and predicted labels.
  • The paper studies supervised node classification by learning predictions from node representations and labels while minimizing classification loss.
  • An L-layer GCN combines neighborhood propagation and aggregation with combination of aggregated messages and self-representations.
  • Vanilla GCN uses the layer update F^(l+1) = σ(ÃF^(l)W^(l)), with à obtained by symmetrically normalizing the adjacency matrix after adding self-loops.
  • Removing nonlinearities yields SGC, whose layer-l representations are F^(l) = Ã^lF^(0) and whose final classifier is logistic regression.

3. Theoretical Analysis

The theory profiles nodes using homophily and relative degree, whose interplay produces three representation-movement cases. These cases jointly explain when aggregation causes oversmoothing or heterophily-related degradation.

  • Node-level homophily and relative degree characterize representation movements across GCN layers and explain both performance problems.
  • 3.3.1. Movements at the Initial Layer: Three cases arise: heterophilous nodes move toward the other class, low-degree nodes under high homophily move toward it less strongly, and high-degree homophilous nodes are favorable.The third case is the only favorable case in the initial-layer analysis.
  • 3.3.4. Explanation for Heterophily and Oversmoothing: Nodes with low homophily or high homophily but low degree cannot benefit from message aggregation, producing oversmoothing-related degradation.Under certain conditions, aggregation increases their misclassification rate.
  • 3.3.4. Explanation for Heterophily and Oversmoothing: In heterophilous graphs, degradation occurs at the first layer because case 1 and sometimes case 2 nodes dominate.This explains why GCNs may perform worse than MLPs in heterophilous graphs.
  • 3.3.4. Explanation for Heterophily and Oversmoothing: In homophilous graphs, oversmoothing develops from initially beneficial case 3 behavior toward deeper-layer dominance by cases 1 and 2.Misclassified nodes reduce their neighbors’ effective homophily, eventually making most nodes resemble case 1.
  • 3.4. Node Profiling With Signed Edges: Signed edges reduce dependence on initial homophily and can help heterophilous performance and oversmoothing under suitable conditions.The analysis warns that signed edges may hurt performance when a low error rate cannot be guaranteed.

4. Model Design

GGCN implements two theory-motivated edge-correction mechanisms: degree-based structural correction and feature-based signed correction. It also incorporates decaying message aggregation, while retaining robustness without that additional design.

  • GGCN combines structure-based and feature-based edge correction with decaying aggregation to address heterophily and oversmoothing.
  • 4.1. Structure-based Edge Correction: Structure-based correction rescales edge weights using structural degree information to compensate for low-degree nodes.The strategy changes edge-weight ratios because node degrees themselves cannot be modified.
  • 4.2. Feature-based Edge Correction: Feature-based correction learns signed edge weights from node features, allowing negative weights unlike conventional nonnegative attention weights.Cosine similarity approximates the sign function for backpropagation, and positive and negative messages are separated.
  • 4.2. Feature-based Edge Correction: GGCN learns a weighted combination of self-representations, positive messages, and negative messages.The model constrains the combined scaling weights to remain non-negative so signed information retains its intended effect.
  • 4.3. Decaying Aggregation: Decaying aggregation slows representation convergence and is integrated into GGCN as an existing design that empirically increases performance.The paper reports that GGCN remains effective under heterophily and robust to oversmoothing even without this design.

5. Experiments

Experiments evaluate GGCN across graphs with varying homophily, layer depths, and node profiles. GGCN performs strongly across both heterophily and oversmoothing settings, while node-level cases better explain conventional GCN degradation.

  • Q1: Performance Under Homophily & Heterophily: GGCN achieves the best average rank (1.78) across all datasets and the highest accuracy on 5 of 6 heterophilous graphs.Its accuracy improves over the second-best model by around 6% on Chameleon and 3% on Cornell.
  • Q1: Performance Under Homophily & Heterophily: GGCN is the only evaluated model that outperforms MLP across all heterophilous datasets.Heterophily-specific models improve over classic GCN and GAT but do not show a clear advantage over MLP.
  • Q2: Robustness Against Oversmoothing: GGCN and GCNII* increase accuracy as more layers are stacked across four datasets, while GPRGNN and PairNorm also show oversmoothing robustness.GCN and Geom-GCN* degrade rapidly with depth; H2GCN* and GAT encounter memory-related issues when stacking many layers.
  • Q2: Robustness Against Oversmoothing: Models that perform well under heterophily generally show greater resilience to oversmoothing, with Geom-GCN* as an exception.GGCN’s structure-based correction virtually changes node degrees, which positively affects its robustness in practice.
  • Q3: Node Profiling and Performance Prediction: Node profiling better explains GCN performance than graph-level homophily across the evaluated heterophilous datasets.Case 1 dominates Texas, Wisconsin, and Actor, while cases 1 and 2 dominate Squirrel and Chameleon; the cases are defined by node homophily and relative degree.
  • Q4: Empirical Verification of the Two Stages: On Citeseer, high-degree nodes gain accuracy initially but later experience a sharper drop when effective homophily is low, matching the theoretical prediction.The empirical verification measures test accuracy and effective homophily across logarithmically binned node degrees.

6. Related Work

Related work covers foundational GCN architectures, oversmoothing analyses and remedies, and methods designed for heterophilous graphs. Existing approaches commonly address these issues from separate perspectives.

  • Graph Convolutional Neural Networks: GCN research developed from spectral filtering with nonlinearities to localized convolutions and attention-based neighborhood aggregation.These architectures support supervised node classification and related graph-learning applications.
  • Heterophily & GCNs: Figure 2 examines Citeseer node accuracy by degree and relates its stages to mean effective homophily.The related empirical description reports increasing accuracy with degree when effective homophily is high and sharper high-degree declines when it is low.
  • Oversmoothing: Oversmoothing research shows that repeated graph propagation can make node representations converge, motivating residual, skip-link, normalization, dropout, and architectural remedies.The literature includes both empirical solutions and theoretical analyses of representation convergence and expressive-power loss.
  • Heterophily & GCNs: Heterophily research proposes specialized graph designs and high-frequency filters because neighboring nodes may belong to different classes.These methods target challenging heterophilous settings that conventional GCN aggregation may not capture effectively.

7. Conclusion

The paper unifies oversmoothing and heterophily through node-level representation analysis, identifying relative degree and neighborhood heterophily as causes of harmful representation movements. These insights motivate structure- and feature-based corrections in GGCN.

  • 7. Conclusion: Relative degree and node-level heterophily jointly characterize node behaviors across GCN layers and explain both oversmoothing and heterophily.The analysis connects these metrics to movements of node representations and misclassification.
  • 7. Conclusion: Nodes with high heterophily tend to be misclassified after graph convolution, while low-degree nodes can create pseudo-heterophily even in low-heterophily neighborhoods.The paper identifies these as distinct consequences of the unified node-level perspective.
  • 7. Conclusion: Signed edges can alleviate both heterophily and oversmoothing problems.This motivates using signed rather than exclusively positive edge weights.
  • 7. Conclusion: GGCN addresses the identified causes using structure- and feature-based edge-correction mechanisms.The paper presents these as theoretically grounded directions for improving learned graph representations.

A.4.2. THEOREM

Under the non-swapping condition, moving node representations toward the original decision boundary is not beneficial and tends to worsen SGC performance. The theorem formalizes this through a non-decreasing total misclassification rate.

  • A.4.2. THEOREM: Under the theorem’s conditions, the new total misclassification rate is no less than the rate before representation movements.The proof establishes this by contradiction using the optimality of the original decision boundary.
  • A.4.2. THEOREM: Moving representations toward the original decision boundary by a non-zero step is harmful to SGC performance under the non-swapping condition.The non-swapping condition requires w*^T w*' > 0; representation swapping, such as in bipartite graphs, is outside this conclusion.
  • A.4.2. THEOREM: The result applies when representations move toward the original decision boundary or the other class, but not when the two class representations swap positions.The swapping case violates w*^T w*' > 0 and leads to different conclusions.

B.1. Ablation study

The ablation study finds that both edge-correction mechanisms mitigate oversmoothing and improve performance under heterophily, with structure-based correction more consistent across graph types and feature-based correction stronger on heterophilous datasets.

  • B.1. Ablation study: Structure-based correction provides consistent benefits across homophilous and heterophilous datasets, whereas feature-based correction benefits heterophilous datasets more.Signed-message benefits are limited on homophilous graphs when effective homophily is high.
  • B.1. Ablation study: Both structure-based and feature-based edge correction alleviate oversmoothing, with the base model dropping sharply after 32 layers.The structure-based variant generally decreases least at 64 layers on Cora, Citeseer, and Cornell.
  • B.1. Ablation study: 5% accuracy gain at the 8-th layer on Chameleon is achieved by the +str model.This result may help explain GGCN’s large performance gain in Table 1.
  • B.1. Ablation study: Both mechanisms improve the base model under heterophily, while +feat outperforms +str on heterophilous datasets.On Cornell, +feat gains around 24% over the base model and 22% over +str.

B.2. Batch norm & Layer norm

Batch and layer normalization can reduce oversmoothing, but both reduce accuracy on heterophilous data; consequently, GGCN uses neither.

  • Batch norm and layer norm can improve oversmoothing, with layer norm generally outperforming batch norm.Table B.2 highlights the best performance across layers for each model.
  • Layer normalization mitigates dispersion by normalizing across node representations, whereas batch normalization sacrifices nodes that benefit from propagation.Batch normalization is therefore less effective at mitigating oversmoothing and produces a larger accuracy decrease.
  • Both normalization methods decrease accuracy by 2%-3% on heterophilous datasets.Batch normalization also causes a clear accuracy drop on homophilous datasets.
  • Normalization cannot reverse sign flips caused by high heterophily and may instead encourage representations toward the other class.
  • GGCN omits both batch norm and layer norm because of these limitations.

B.3. More on the Initial & Developing Stages

The experiments examine how degree and effective homophily shape accuracy across GCN layers, confirming the theory that node behavior differs between initial and developing stages.

  • Initial and developing stages: In heterophilous datasets, most nodes satisfy case 1, so the initial stage does not occur.
  • Experimental setup: Degree intervals are formed using logarithmic binning with base 2 to compare accuracy across node degrees and layers.
  • Initial and developing stages: Citeseer accuracy initially increases with degree and average effective homophily, but high-degree nodes decline more sharply during the developing stage.
  • Developing stage: During Cora’s developing stage, high-degree nodes lose more accuracy than the remaining node groups.
  • Theory verification: The Citeseer and Cora results verify the conjecture derived from the theorems in Section 3.3.

C.3. Parameters after training

After training, GGCN increases corrected relative-degree weights, consistent with the paper’s theoretical guidance.

  • After training, GGCN learns to increase relative-degree weights, satisfying the stated theorems.Corrected weights combine global scaling with local degree correction.
Loading 2102.06462v8…