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.

该研究分析了完全子图枚举的必要性，证明了通过考虑子图的一个小子集可以获得可比较的表达能力，进而提出了MAG-GNN，一种强化学习增强的GNN，用于解决最优子集的组合优化问题。该方法通过将指数复杂度的子图枚举降低为常数复杂度的子图搜索算法，同时保持了良好的表达能力。实验结果显示MAG-GNN在多个数据集上表现出竞争性性能，甚至优于许多子图GNN方法，并有效减少了子图GNN的运行时间。

MAG-GNN：增强学习增强的图神经网络