Research map / Graph learning / GNN architectures
Towards characterizing the value of edge embeddings in Graph Neural Networks
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.
Shows theoretically that maintaining edge embeddings can yield much shallower memory-constrained GNNs than node embeddings (depth separations via communication/time-space lower bounds), and empirically that edge-based GCNs match or beat node-based GCNs, especially on hub-node star graphs and tree-based Ising marginal tasks.
Problem
Whether maintaining and updating edge embeddings in GNNs gives representational benefits (depth/memory tradeoffs) over standard node-embedding message passing, beyond symmetry-based (WL) analyses.
Approach
Introduces local memory-constrained computation models for node and edge message-passing protocols, proves depth/memory separations on MAP inference and symmetric tasks using Grigoriev-style information-flow lower bounds through hub nodes, shows no separation without memory constraints, and validates empirically with edge-based GCN ablations versus node-based GCN.
Key results
- On benchmarks, Edge-GCN matches or beats node GCN: ZINC MAE 0.3297 vs 0.3430, CIFAR-10 accuracy 57.44 vs 55.71, Peptides-Func AP 0.6867 vs 0.6816, though MNIST accuracy is lower (94.37 vs 95.29).
- On star-graph synthetic regression with 16 leaves and planted depth 5, edge-based RMSE is 0.007 vs 0.3336 for node-based.
- Theory: MAP estimation on a hub-and-paths graph needs TB >= sqrt(n)-1 for node protocols while an edge protocol uses O(1) rounds and O(1) bits; without memory constraints node protocols simulate edge protocols with one extra round.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace node embeddings with edge embeddings initialized from endpoint node embeddings (ablation) | GCN · ZINC | MAE: 0.3430\pm 0.034 -> 0.3297\pm 0.011 | Helped |
| replace node embeddings with edge embeddings initialized from endpoint node embeddings (ablation) | GCN · MNIST | accuracy: 95.29 \pm 0.163 -> 94.37 \pm 0.065 | Hurt |
| replace node embeddings with edge embeddings initialized from endpoint node embeddings (ablation) | GCN · CIFAR-10 | accuracy: 55.71 \pm 0.381 -> 57.44 \pm 0.387 | Helped |
| replace node embeddings with edge embeddings initialized from endpoint node embeddings (ablation) | GCN · Peptides-Func | AP: 0.6816\pm 0.007 -> 0.6867\pm 0.004 | Helped |
| replace node embeddings with edge embeddings initialized from endpoint node embeddings (ablation) | GCN · Peptides-Struct | MAE: 0.2453 \pm 0.0001 -> 0.2437 \pm 0.0005 | Helped |
| replace node embeddings with edge embeddings (ablation) | GCN trained on planted edge-based labels · Star graph with 64, 32, and 16 leaves across planted depths 5, 3, and 1 | RMSE: 64 leaves, depth 5: 0.3790 -> 0.004; 64 leaves, depth 3: 0.3596 -> 0.011; 64 leaves, depth 1: 0.3752 -> 0.008; 32 leaves | Mixed |
| use edge embeddings instead of node embeddings (ablation) | GCN for Ising marginal prediction · Tree graphs: complete binary tree, path graph, and randomly sampled trees | MSE | Helped |
| make the GCN directed, maintaining embeddings for each edge direction (ablation) | Node-U and Edge-U · Ising marginal prediction on tree graphs | MSE | Helped |
Surprising findings
- Edge-GCN is worse than node GCN on MNIST accuracy (94.37 vs 95.29), so the advantage is not uniform.
- Without memory constraints, symmetry alone yields no separation: any symmetric edge protocol can be simulated by a symmetric node protocol with one extra round.
Limitations
- Edge-based architectures incur significant computational overhead, especially on dense graphs.
- Separations are proven for specific constructed graphs and tasks (hub-and-paths, star, complete graphs), not general graphs.
- Benchmark improvements are small and mixed (MNIST decreases).
Experimental setup
Datasets: ZINC MNIST CIFAR-10 Peptides-Func Peptides-Struct
Benchmarks: ZINC MNIST CIFAR-10 Peptides-Func Peptides-Struct star-graph synthetic regression Ising marginal prediction on trees
Metrics: MAE accuracy average precision RMSE MSE
Baselines: GCN (node-based) Node-U Node-D
Builds on: GCN Weisfeiler-Lehman test belief propagation Grigoriev's method for time-space tradeoffs
Closest papers by meaning
- A Theoretical Comparison of Graph Neural Network Extensions (ICML 2022 · similarity 0.90)
- Graph Neural Networks Are More Than Filters: Revisiting and Benchmarking from A Spectral Perspective (ICLR 2025 · similarity 0.88)
- Towards Bridging Generalization and Expressivity of Graph Neural Networks (ICLR 2025 · similarity 0.88)
- Edge Prompt Tuning for Graph Neural Networks (ICLR 2025 · similarity 0.88)
- On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning (NeurIPS 2025 · similarity 0.88)
- Learning Efficient Positional Encodings with Graph Neural Networks (ICLR 2025 · similarity 0.88)
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.