mlsanityData to 7 Oct 2026

Agent-based Graph Neural Networks

arXiv 2206.11010 ↗First posted 22 Jun 2022cs.LG cs.AI stat.MLcited by 13

Not on the map. Why?

Abstract (arXiv)

We present a novel graph neural network we call AgentNet, which is designed specifically for graph-level tasks. AgentNet is inspired by sublinear algorithms, featuring a computational complexity that is independent of the graph size. The architecture of AgentNet differs fundamentally from the architectures of traditional graph neural networks. In AgentNet, some trained textitneural agents intelligently walk the graph, and then collectively decide on the output. We provide an extensive theoretical analysis of AgentNet: We show that the agents can learn to systematically explore their neighborhood and that AgentNet can distinguish some structures that are even indistinguishable by 2-WL. Moreover, AgentNet is able to separate any two graphs which are sufficiently different in terms of subgraphs. We confirm these theoretical results with synthetic experiments on hard-to-distinguish graphs and real-world graph classification tasks. In both cases, we compare favorably not only to standard GNNs but also to computationally more expensive GNN extensions.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). Builds on 60 of its 84 references that are in the map. First posted on arXiv 22 Jun 2022.

Builds on

60 of 84 references.

References · 60

  1. 2017Attention Is All You Needcited by 59,932
  2. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  3. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  4. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  5. 2017Graph Attention Networkscited by 8,854
  6. 2017Inductive Representation Learning on Large Graphscited by 6,284
  7. 2018How Powerful are Graph Neural Networks?cited by 4,355
  8. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  9. 2016Categorical Reparameterization with Gumbel-Softmaxcited by 2,708
  10. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  11. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  12. 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
38 more
  1. 2014DeepWalk: Online Learning of Social Representationscited by 1,543
  2. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  3. 2016The Concrete Distribution: A Continuous Relaxation of Discrete Random Variablescited by 1,135
  4. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  5. 2017MoleculeNet: A Benchmark for Molecular Machine Learningcited by 1,037
  6. 2020On Layer Normalization in the Transformer Architecturecited by 906
  7. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  8. 2021How Attentive are Graph Attention Networks?cited by 818
  9. 2019GNNExplainer: Generating Explanations for Graph Neural Networkscited by 735
  10. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  11. 2020Benchmarking Graph Neural Networkscited by 672
  12. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  13. 2019GraphSAINT: Graph Sampling Based Inductive Learning Methodcited by 618
  14. 2018FastGCN: Fast Learning with Graph Convolutional Networks via Importance Samplingcited by 583
  15. 2019Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networkscited by 540
  16. 2019DeepGCNs: Can GCNs Go as Deep as CNNs?cited by 527
  17. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
  18. 2019Provably Powerful Graph Networkscited by 385
  19. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
  20. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  21. 2020Towards Deeper Graph Neural Networkscited by 296
  22. 2019A Fair Comparison of Graph Neural Networks for Graph Classificationcited by 244
  23. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  24. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  25. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  26. 2020Random Features Strengthen Graph Neural Networkscited by 184
  27. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  28. 2021Training Graph Neural Networks with 1000 Layerscited by 169
  29. 2021Equivariant Subgraph Aggregation Networkscited by 154
  30. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  31. 2020Directional Graph Networkscited by 132
  32. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 117
  33. 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 95
  34. 2020Rethinking pooling in graph neural networkscited by 73
  35. 2021Reconstruction for Powerful Graph Representationscited by 65
  36. 2022Expressiveness and Approximation Properties of Graph Neural Networkscited by 63
  37. 2020Hierarchical Inter-Message Passing for Learning on Molecular Graphscited by 59
  38. 2022A Short Tutorial on The Weisfeiler-Lehman Test And Its Variantscited by 52

50 most cited of 60 All 60 (JSON)

Built on by

Cited by year

Citing papers per year: 2023: 4; 2024: 3; 2025: 6.

13 papers.

Sort:

By area:

  1. 2024ResearchTown: Simulator of Human Research Communitycited by 35
  2. 2023Path Neural Networks: Expressive and Accurate Graph Neural Networkscited by 32
  3. 2023WL meet VCcited by 30
  4. 2025Graphs Meet AI Agents: Taxonomy, Progress, and Future Opportunitiescited by 23
  5. 2023Efficient Subgraph GNNs by Learning Effective Selection Policiescited by 17
  6. 2025Beyond Message Passing: Neural Graph Pattern Machinecited by 17
  7. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  8. 2024Revisiting Random Walks for Learning on Graphscited by 13
  9. 2023MAG-GNN: Reinforcement Learning Boosted Graph Neural Networkcited by 11
  10. 2025Generative Graph Pattern Machinecited by 11
  11. 2025Random Search Neural Networks for Efficient and Expressive Graph Learningcited by 1
  12. 2025Parameter-Free Structural-Diversity Message Passing for Graph Neural Networkscited by 0
1 more
  1. 2025Learn to Jump: Adaptive Random Walks for Long-Range Propagation through Graph Hierarchiescited by 0