Research map / Graph learning / GNN architectures
Graph Neural Networks Gone Hogwild
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 implicitly-defined GNNs (fixed-point and optimization-based) provably tolerate asynchronous "hogwild" inference, and proposes energy GNNs built from partially input-convex networks that outperform other implicit GNNs on synthetic multi-agent tasks.
Problem
GNN state representations for decentralized multi-agent systems break under asynchronous node updates and stale messages, because explicitly-defined multi-layer GNNs assume synchronized layer-wise computation.
Approach
Identify implicitly-defined GNNs (fixed points of contractive updates or minimizers of separable convex energies) as provably robust to partially asynchronous inference, and propose an energy GNN whose convex energy is parameterized by partially input-convex neural networks over neighborhoods.
Key results
- Energy GNN edge-wise with attention reaches 0.25% error on chains and 3.6% on counting, versus 26.9% for IGNN and 35.9% for GSDGNN on chains.
- Under simulated asynchronous inference, implicit GNNs (IGNN, GSDGNN, energy GNN variants) show performance decreases below 0.1%, while GCN and GAT degrade substantially (e.g., GCN count error increases by 584.6%).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use edge-wise rather than node-wise messages (ablation) | Energy GNN · Chains | percentage error: 15.8 ± 17.9 -> 1.2 ± 2.2 | Helped |
| Use edge-wise rather than node-wise messages (ablation) | Energy GNN · Count | relative RMSE percentage error: 19.5 ± 1.7 -> 4.0 ± 3.6 | Helped |
| Use edge-wise rather than node-wise messages (ablation) | Energy GNN · Sum | relative RMSE percentage error: 12.2 ± 0.7 -> 4.9 ± 3.3 | Helped |
| Use edge-wise rather than node-wise messages (ablation) | Energy GNN · Coordinates | relative RMSE percentage error: 41.3 ± 2.4 -> 33.5 ± 3.2 | Helped |
| Use edge-wise rather than node-wise messages (ablation) | Energy GNN · MNIST terrain | classification error: 13.8 ± 0.8 -> 13.0 ± 0.6 | Helped |
| Add neighborhood attention to edge-wise messages (ablation) | Energy GNN · Chains | percentage error: 1.2 ± 2.2 -> 0.25 ± 0.5 | Helped |
| Add neighborhood attention to edge-wise messages (ablation) | Energy GNN · Count | relative RMSE percentage error: 4.0 ± 3.6 -> 3.6 ± 3.8 | Helped |
| Add neighborhood attention to edge-wise messages (ablation) | Energy GNN · Sum | relative RMSE percentage error: 4.9 ± 3.3 -> 6.0 ± 4.0 | Hurt |
| Add neighborhood attention to edge-wise messages (ablation) | Energy GNN · Coordinates | relative RMSE percentage error: 33.5 ± 3.2 -> 30.9 ± 1.8 | Helped |
| Add neighborhood attention to edge-wise messages (ablation) | Energy GNN · MNIST terrain | classification error: 13.0 ± 0.6 -> 13.8 ± 0.8 | Hurt |
| Use an energy GNN rather than IGNN or GSDGNN | Implicitly-defined GNNs · Chains, Count, Sum, Coordinates, MNIST terrain | task error | Helped |
| Switch from synchronous to asynchronous inference | GCN and GAT · Synthetic tasks | task performance | Hurt |
Surprising findings
- Energy GNN with attention is worse than the edge-wise variant on SUM and MNIST, showing that added flexibility does not uniformly help.
Limitations
- Forward pass requires fixed-point or optimization iterations whose cost is not known in advance.
- Convergence rate depends on conditioning of Hessian or Jacobian, which is hard to control, and implicit differentiation requires solving potentially ill-conditioned linear systems.
- Theoretical guarantees rely on constants that may not be readily available.
Experimental setup
Datasets: chains (synthetic) counting (synthetic) sums (synthetic) coordinates (synthetic) MNIST terrain (MNIST-derived) MUTAG PROTEINS PPI
Benchmarks: chains counting sums coordinates MNIST terrain MUTAG PROTEINS PPI
Metrics: percentage error relative RMSE decrease in task performance under asynchronous inference
Baselines: IGNN GSDGNN GCN GAT
Builds on: IGNN GSDGNN partially input-convex neural networks partial asynchronism (Bertsekas and Tsitsiklis) GCN GAT
Closest papers by meaning
- Graph Agent Network: Empowering Nodes with Inference Capabilities for Adversarial Resilience (AAAI 2025 · similarity 0.87)
- On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning (NeurIPS 2025 · similarity 0.85)
- PGODE: Towards High-quality System Dynamics Modeling (ICML 2024 · similarity 0.85)
- Recurrent Graph Neural Networks and Their Connections to Bisimulation and Logic (AAAI 2024 · similarity 0.85)
- Bridging Training and Execution via Dynamic Directed Graph-Based Communication in Cooperative Multi-Agent Systems (AAAI 2025 · similarity 0.85)
- G-Designer: Architecting Multi-agent Communication Topologies via Graph Neural Networks (ICML 2025 · similarity 0.84)
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.