MAG-GNN: Reinforcement Learning Boosted Graph Neural Network

2023-10-29 · NeurIPS 2023 11

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.

📄 PDF Abstract BibTeX arXiv:2310.19142

Code (0)

등록된 구현이 없습니다.

Tasks

Combinatorial OptimizationGraph Learning Graph Neural Network reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Methods 이 논문이 사용한 방법론

SET Dynamic Sparse Training method where weight mask is updated randomly periodically

Graph Neural Network 설명 없음

Interpretable Reinforcement Learning with Ensemble Methods

2018-09-19 · Alexander Brown, Marek Petrik

We propose to use boosted regression trees as a way to compute human-interpretable solutions to reinforcement learning problems. Boosting combines several regression trees to improve their accuracy without significantly …

BIG-bench Machine Learning Interpretable Machine Learning regression reinforcement-learning+2

INSPIRE-GNN: Intelligent Sensor Placement to Improve Sparse Bicycling Network Prediction via Reinforcement Learning Boosted Graph Neural Networks

2025-07-31 · Mohit Gupta, Debjit Bhowmick, Rhys Newbury, Meead Saberi 외 arxiv

Accurate link-level bicycling volume estimation is essential for sustainable urban transportation planning. However, many cities face significant challenges of high data sparsity due to limited bicycling count sensor cov…

Reinforcement Learning Graph Neural Network

Attacking Graph Convolutional Networks via Rewiring

2019-06-10 · Yao Ma, Suhang Wang, Tyler Derr, Lingfei Wu 외

Graph Neural Networks (GNNs) have boosted the performance of many graph related tasks such as node classification and graph classification. Recent researches show that graph neural networks are vulnerable to adversarial …

General Classification Graph Classification Node Classification Reinforcement Learning

Convergent Boosted Smoothing for Modeling GraphData with Tabular Node Features

2021-09-29 · ICLR 2022 4 · Jiuhai Chen, Jonas Mueller, Vassilis N. Ioannidis, Soji Adeshina 외

Many practical modeling tasks require making predictions using tabular data composed of heterogeneous feature types (e.g., text-based, categorical, continuous, etc.). In this setting boosted decision trees and related e…

Boosted Stochastic Frank-Wolfe for Constrained Nonconvex Optimization

2026-05-24 · Navil Nandhan, Abbas Khademi, Antonio Silveti-Falls arxiv

The boosted Frank-Wolfe algorithm accelerates the classical Frank-Wolfe algorithm by better aligning the update direction with the negative gradient. Its analysis, however, has been limited to deterministic convex proble…