Research map / Graph learning / GNN architectures
Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspective
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a class-controlled feature homophily measure, a CSBM-X random graph model, and theory showing that smaller A-X dependence improves graph convolution, validated via feature shuffling on real graphs.
Problem
Why does randomly shuffling features among same-class nodes consistently improve GCN node classification, which existing homophily/feature-informativeness theories do not explain? The paper targets the dependence between graph topology and node features (A-X dependence) and its effect on GNNs.
Approach
Introduces class-controlled feature homophily (CFH), a measure of A-X dependence that removes class-mean effects, plus CSBM-X, a random graph model with a parameter tau that controls CFH while holding feature distance and class-homophily fixed; theory shows graph convolution error is minimized when CFH is zero.
Key results
- On all 12 high class-homophily benchmark datasets, GCNII accuracy improves with the shuffled node ratio (mean gain about 4%p; largest about 10%p on Cora-Full).
- On 11 of 12 low class-homophily datasets, GCNII shows small or no gain (mean about 0.5%p).
- On CSBM-X synthetic graphs, the simplified GNN's accuracy is best when graph-level CFH is near zero and decreases as |CFH| grows in either direction.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Shuffle features among same-class nodes | GCNII · 12 high class-homophily benchmark datasets | test accuracy: mean increase of 4%p | Helped |
| Shuffle features among same-class nodes | GCNII · Cora-Full | test accuracy: 10%p | Helped |
| Shuffle features among same-class nodes | GCNII · 11/12 low class-homophily benchmark datasets | test accuracy: mean increase of 0.5%p | No clear effect |
| Increase the ratio of same-class nodes with shuffled features | GCNII · Roman-Empire | test accuracy | Hurt |
| Reduce graph-level class-controlled feature homophily toward zero | Simplified GNN D^{-1}AXW · CSBM-X graphs | test accuracy | Helped |
| Increase feature noise by permuting feature vectors irrespective of class | GCNII with feature shuffle · Real-world benchmark graphs | test accuracy | Hurt |
| Use proximity-based features instead of original features, then shuffle within classes | GNN node classification · Real-world benchmark graphs | test accuracy | Helped |
| Set the CSBM-X dependence parameter τ to zero rather than increasing |τ| | Simplified graph-convolution classifier · CSBM-X graphs | Bayes error rate | Helped |
| Shuffle features among same-class nodes | MLP · Real-world graph benchmarks | test accuracy | No clear effect |
| Shuffle features among same-class nodes | Label propagation · Real-world graph benchmarks | test accuracy | No clear effect |
| Shuffle features among same-class nodes | GPR-GNN and AERO-GNN · Real-world benchmark graphs | test accuracy | Helped |
Surprising findings
- Shuffling features among same-class nodes, which leaves class-feature and class-topology dependence unchanged, consistently improves GCN performance, while MLP and label propagation stay flat.
- Roman-Empire accuracy steadily declines with the shuffle ratio for GCNII, which the authors attribute possibly to its very large diameter.
Limitations
- Theory assumes linear feature-class relations and a symmetric unimodal node-level CFH distribution, a simplified 1-D setting with a simplified GNN.
- The feature shuffle requires test labels and CFH is unknown without them, so it is not directly usable as a method.
- The paper does not provide new benchmark datasets or new GNN architectures addressing varying CFH.
Experimental setup
Datasets: Cora-Full Chameleon Squirrel Roman-Empire Amazon-Ratings Ogbn-ArXiv
Benchmarks: Cora-Full Chameleon Squirrel Roman-Empire Amazon-Ratings Ogbn-ArXiv
Metrics: test accuracy
Baselines: MLP label propagation GPR-GNN AERO-GNN
Builds on: CSBM GCNII GPR-GNN AERO-GNN
Closest papers by meaning
- Let Your Features Tell The Differences: Understanding Graph Convolution By Feature Splitting (ICLR 2025 · similarity 0.90)
- On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspective (NeurIPS 2025 · similarity 0.89)
- On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks (ICML 2025 · similarity 0.88)
- Graph Neural Networks Are More Than Filters: Revisiting and Benchmarking from A Spectral Perspective (ICLR 2025 · similarity 0.88)
- A Topological Perspective on Demystifying GNN-Based Link Prediction Performance (ICLR 2024 · similarity 0.87)
- On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.