# MAG-GNN: Reinforcement Learning Boosted Graph Neural Network

arXiv: https://arxiv.org/abs/2310.19142 · HTML: https://mlsanity.com/paper/2310.19142/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 38 references that are in the map.
- First posted on arXiv 29 Oct 2023.

## Builds on (most cited first, 30 of 33)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness](https://mlsanity.com/paper/2110.03753/) (2021)
- [Nested Graph Neural Networks](https://mlsanity.com/paper/2110.13197/) (2021)
- [DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks](https://mlsanity.com/paper/2111.06283/) (2021)
- [Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries](https://mlsanity.com/paper/2206.11140/) (2022)
- [How Powerful are K-hop Message Passing Graph Neural Networks](https://mlsanity.com/paper/2205.13328/) (2022)
- [GCN-RL Circuit Designer: Transferable Transistor Sizing with Graph Neural Networks and Reinforcement Learning](https://mlsanity.com/paper/2005.00406/) (2020)
- [Molecular graph generation with Graph Neural Networks](https://mlsanity.com/paper/2012.07397/) (2020)
- [SUGAR: Subgraph Neural Network with Reinforcement Pooling and Self-Supervised Mutual Information Mechanism](https://mlsanity.com/paper/2101.08170/) (2021)
- [MotifNet: a motif-based Graph Convolutional Network for directed graphs](https://mlsanity.com/paper/1802.01572/) (2018)
- [A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests](https://mlsanity.com/paper/2302.07090/) (2023)
- [Ordered Subgraph Aggregation Networks](https://mlsanity.com/paper/2206.11168/) (2022)
- [Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNs](https://mlsanity.com/paper/2210.13978/) (2022)
- [Graph Policy Network for Transferable Active Learning on Graphs](https://mlsanity.com/paper/2006.13463/) (2020)
- [Policy-GNN: Aggregation Optimization for Graph Neural Networks](https://mlsanity.com/paper/2006.15097/) (2020)
- [GraphNAS: Graph Neural Architecture Search with Reinforcement Learning](https://mlsanity.com/paper/1904.09981/) (2019)
- [An Empirical Study of Realized GNN Expressiveness](https://mlsanity.com/paper/2304.07702/) (2023)

## Built on by (most cited first, 11 of 11)

- [GOFA: A Generative One-For-All Model for Joint Graph Language Modeling](https://mlsanity.com/paper/2407.09709/) (2024)
- [Graph Neural Networks for Financial Fraud Detection: A Review](https://mlsanity.com/paper/2411.05815/) (2024)
- [Graphs Meet AI Agents: Taxonomy, Progress, and Future Opportunities](https://mlsanity.com/paper/2506.18019/) (2025)
- [On the Expressive Power of Spectral Invariant Graph Neural Networks](https://mlsanity.com/paper/2406.04336/) (2024)
- [TAGLAS: An atlas of text-attributed graph datasets in the era of large graph and language models](https://mlsanity.com/paper/2406.14683/) (2024)
- [Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Products](https://mlsanity.com/paper/2402.08450/) (2024)
- [A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening](https://mlsanity.com/paper/2406.09291/) (2024)
- [Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality](https://mlsanity.com/paper/2501.03113/) (2025)
- [Learning and Editing Universal Graph Prompt Tuning via Reinforcement Learning](https://mlsanity.com/paper/2512.08763/) (2025)
- [Towards Stable, Globally Expressive Graph Representations with Laplacian Eigenvectors](https://mlsanity.com/paper/2410.09737/) (2024)
- [Topology Enhanced MARL for Multi-Agent Cooperative Decision-Making of CAVs](https://mlsanity.com/paper/2507.12110/) (2025)

## Abstract (arXiv)

While Graph Neural Networks (GNNs) recently became powerful tools in graph learning tasks, considerable efforts have been spent on improving GNNs' structural encoding ability. A particular line of work proposed subgraph GNNs that use subgraph information to improve GNNs' expressivity and achieved great success. However, such effectivity sacrifices the efficiency of GNNs by enumerating all possible subgraphs. In this paper, we analyze the necessity of complete subgraph enumeration and show that a model can achieve a comparable level of expressivity by considering a small subset of the subgraphs. We then formulate the identification of the optimal subset as a combinatorial optimization problem and propose Magnetic Graph Neural Network (MAG-GNN), a reinforcement learning (RL) boosted GNN, to solve the problem. Starting with a candidate subgraph set, MAG-GNN employs an RL agent to iteratively update the subgraphs to locate the most expressive set for prediction. This reduces the exponential complexity of subgraph enumeration to the constant complexity of a subgraph search algorithm while keeping good expressivity. We conduct extensive experiments on many datasets, showing that MAG-GNN achieves competitive performance to state-of-the-art methods and even outperforms many subgraph GNNs. We also demonstrate that MAG-GNN effectively reduces the running time of subgraph GNNs.