MAG-GNN: Reinforcement Learning Boosted Graph Neural Network

Summary

The authors present MAG-GNN, a subgraph-based Graph Neural Network (GNN) method that utilizes reinforcement learning to effectively identify discriminative subgraphs. They empirically assess the performance of MAG-GNN using both synthetic and real-world datasets.

Strengths

- The main elements of the RL framework are properly explained. - The empirical section includes clear and valuable research questions.

Weaknesses

1. The writing is significantly lacking in clarity and context. 2. The presentation of results lacks clarity.

Questions

1. Please provide clarification on what "this property" refers to in line 60. 2. Can you confirm if \mathbf{v} represents a set of k nodes in line 88? It seems so, but the notation is not defined. 3. In line 88, it would be helpful to provide context on why a subgraph GNN creates |V^k(G)| copies of the graph and an intuition of what this quantity represents. 4. In Equation (2), could you specify what j represents? 5. Could you explain what N refers to in Equation (3)? 6. In line 136, when you mention a "2-node-marked graph," could you provide a general definition of a node-marked graph? 7. What is meant by a "GNN run" or "MPNN run"? 8. The explanation in the text of Figure 2 is quite complex. Additional information from the authors would be appreciated to improve comprehension. 9. Is \mathcal{V}^k the same as V^k(G) mentioned in line 172? If so, it would be helpful to use standardized notation to help in understanding. 10. In section 4.1 on training MAG-GNN, it is challenging to grasp all the training procedure details solely from the text. It would be beneficial to include an algorithm that illustrates the training procedure. 11. The captions of Table 1 and Table 2 do not indicate which metrics are being presented. 12. What do the yellow cells indicate in Table 2? 13. All the tables and figures in the experimental section lack error bars. 14. How does the runtime of MAG-GNN vary with m and T in section 6.4 on runtime comparison?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

1 poor

Contribution

3 good

Limitations

The authors have acknowledged the limitations of their proposed approach.

Summary

The paper considers the problem of increased complexity of subgraph GNNs with respect to standard MPNNs, due to the enumeration of the entire bag of subgraphs for every given graph. The authors first study the need of enumerating all subgraphs, and show that there exist graphs where using a small subset of subgraphs have the same discriminative power as the entire bag of subgraphs. Motivated by these cases, the authors propose an RL-based approach, named MAG-GNN, to find the best subset of subgraphs to be employed in the task at hand. The method starts with a subset of subgraphs that are randomly selected. Then, it employs a DQN framework, where the Q-network is parametrized by a subgraph GNN, to replace each subgraph in the subset with a another subgraph. The new subgraph is obtained by replacing only one index of the node tuple identifying the subgraph. Upon reaching a maximum number of steps, the obtained subgraph set is passed through a downstream subgraph GNN for the final predictions.

Strengths

1. The problem of reducing the complexity of subgraph GNNs without trading off performances is significant. The authors identify graphs where a small subset of subgraphs has the same discriminative power as the full bag of subgraphs, which motivates the search for such subsets. 2. The combination of RL with subgraph GNNs is original, and represent a natural way of learning to select subgraphs.

Weaknesses

1. **The paper misses a thorough comparison with a random policy**, where a random subset of subgraphs is randomly selected at every forward pass. The authors consider tangentially the question in the experimental evaluation (Q1) but fail to answer in details. For every dataset you consider, there should be a table entry reporting the performance of the random baseline. **Such baseline should have the same $k$ and the same $m$ that you consider**. Furthermore, it should be based on the same architecture that MAG-GNN uses as downstream prediction model. Only with such comparison we can conclude that MAG-GNN performs better than random. Note that: - The answer of Q1 is insufficient, both because you consider only one dataset, and also because you focus only on one node tuple ($m=1$). Please include a table entry for every dataset. - The experiment in Appendix E reports a comparison with a random baseline that uses ensemble predictions. However, it would make more sense to aggregate the representations of the subgraphs and _then_ perform a prediction, an approach that is indeed followed by subgraph GNNs (as reported in Equation 3). The ensemble method instead predicts using each subgraph separately and then aggregates the predictions, which is clearly less powerful. Please include a comparison with random that does not use the ensemble approach, but that aggregates the representations of the $m$ subgraphs to obtain a graph representation, and then performs the prediction. Note that you should evaluate the same $m$ and $k$ values that you sweep on for MAG-GNN (up to 4 and 6 respectively). 2. **The paper misses comparisons with the I-MLE approach proposed in $k$-OSAN** to select subgraphs, which has exactly the same goal. 3. **The paper misses comparison with many subgraph GNNs**, such as Bevilacqua et al 2022, Zhang et al 2023. These methods obtain better performances than MAG-GNN for example on ZINC, using node-based subgraphs (where the bag of subgraph is of size $\vert V \vert$, and therefore are tractable). It is unclear what is the advantage of training an RL agent, which has much higher training time, and using $k$-order policies with $k>1$, if the performances are worse than node-based subgraph GNNs and the inference time is not better. 4. The comparison on the ZINC dataset is unfair because the model does not respect the parameter budget imposed by the dataset (500k). Currently he budget is twice the one that is allowed (three times if we consider the target q-network). Please fix and ensure you remain within the budget. 5. **The paper misses a thorough comparison with the model using the full bag and $k>1$**. Again, it should be based on the same architecture that MAG-GNN uses as downstream prediction model. Only in this way we can know what is the performance achievable with the full bag, and understand how distant MAG-GNN is from it. Bevilacqua et al 2022. Equivariant Subgraph Aggregation Networks. ICLR 2022 Zhang et al 2023. A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests. ICLR 2023

Questions

1. **What is the performance of _your prediction subgraph GNN_ (which is built on k-OSAN) when trained with random subsets of subgraphs (randomly selected at every forward)**? Note that I am asking to keep your downstream prediction subgraph GNN formulation identical to what you use in MAG-GNN (except the hyperparameter choices) in order to truly understand the impact of the RL agent. Please use $m$ and $k$ up to the values you consider for MAG-GNN. 2. Please include comparison with subgraphs GNNs (Bevilacqua et al 2022, Zhang et al 2023) and with k-OSAN with IMLE. 3. Table 7 shows that MAG-GNN with $m=1$ (and ensemble 3) achieves practically the same performance of the MAG-GNN that uses much higher $m$. Please investigate this aspect. Does it imply that MAG-GNN is effectively only learning to select one subgraph, and the other ones are unimportant (as it can get similar performances when choosing one or many)? 4. I think $f_p$ in Equation 9 should be $f_{rl, p}$. Indeed, using $f_p$ means that you take the representation of graph obtained through the prediction subgraph GNN. However, from the code I think you take the representation of graph obtained through the subgraph GNN that parametrizes the Q-network (that is based on $g_{rl}$). Please clarify. 5. In the SIMUL case, do you reset the replay buffer every time you train your downstream prediction subgraph GNN $g_p$? 6. What is the performance of _your prediction subgraph GNN_ when using the full bag and $k>1$ (that is, for various values of $k>1$)?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

n/a

Summary

The paper aims to locate expressive subgraphs for graph representation learning. To do so, the author proposed to use deep Q Learning for training an efficient agent which optimizes the combinatorial problem of choosing the optimal subgraph. The proposed agent-aided GNN shows good performance and is able to transfer to real-world datasets.

Strengths

Motivation is interesting and the methodology is well explained. The experiment result seems sound. The proposed model is on par with state-of-the-art while using less computational resources.

Weaknesses

* How to train an effective agent seems to be a critical point. Despite that, the author has a brief discussion in sec 4.1, more quantitative analysis and illustration on this part can better support the author's choice of ORD. * The proposed method seems to be on par with the state-of-the-art. While I don't think absolute performance is an important concern given the method is more efficient. I think it's important to investigate in L316 Q3 how much of the RL agent expressiveness benefit the real-world datasets compared to random ones or human-designed ones. ------------------------------------------------------------------------------------- I've read the author's response to me and other reviewers which resolves my concern. I would like to remain my rating as weak accept.

Questions

* In table4, how is no RPE evaluated, why is no RPE on par with training agent on 3-CYCLE 6-CYCLE and SR25?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

N/A

Summary

this paper proposes a strategy to select the optimal subset instead of extensive enumeration for the subgraph GNN. The proposed method can achieve comparative results and reduce the running time.

Strengths

1. the paper is well written and easy to follow. 2. the experiment part is thoroughly detailed。 3. the experiment shows the model can achieve the comparative result with subgraph GNN while significantly reducing the running time.

Weaknesses

N/A

Questions

N/A

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Summary

This paper proposes a reinforcement learning boosted approach to subgraph graph neural networks (GNNs) that achieves high expressivity with constant complexity, instead of the exponential complexity of existing methods. They demonstrate the effectiveness and efficiency of their approach through experiments that compare it with the state-of-the-art methods.

Strengths

1. The paper is well-written. 2. The proposed MAG-GNN can achieve good expressivity while reducing the time complexity of subgraph enumeration.

Weaknesses

1. The authors report that most methods in Table 1 achieve 100% accuracy on the dataset. This suggests that the dataset may be too simple to adequately evaluate the expressivity of a model. The authors should consider applying more challenging datasets to better assess the performance of their models. 2. The table captions are vague and do not provide sufficient information for readers to interpret the experimental results properly. 3. In Section 3, the authors use the same data for training and test, which may lead to overfitting and unrealistic performance. 4. The notation |V^2| should be |V|^2. 5. The proof of the theorem is unclear and lacks details.

Questions

It seems no supporting for this statement: This reduces the exponential complexity of subgraph enumeration to the constant complexity of a subgraph search algorithm while keeping good expressivity

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

The paper does not discuss limitations or potential social impacts.

Summary

The paper introduces MAG-GNN, an RL approach for identifying important subgraphs. This is valuable since models using fewer subgraphs incur lower inference costs. Experimentally, the authors show that MAG-GNN retains the strong performance of sub-graph approaches while reducing the run time.

Strengths

The guiding question of the paper "Are a small number of subgraphs sufficient for graph problems?" is well-motivated. The proposed RL-based approach for identifying subgraphs is well-explained. The approach's performance and efficiency are validated on various benchmark datasets. The negative results of the node-level task are helpful, revealing both the current limit and future potential of the paper.

Weaknesses

**Training efficiency**. While MAG-GNN accelerates inference, the training process becomes more time-consuming. On smaller graphs, this training pipeline may dominate the overall computational costs. **Task scope**. MAG-GNN excels in graph-level tasks but underperforms in node-level tasks, as the authors gracefully acknowledge. **Baseline comparison**. The authors primarily compare MAG-GNN with methods using full subgraphs in the experiment section. Considering its efficiency goals, comparing it with other efficient alternatives, such as applying node/edge pruning approaches to the full graph and then using standard subgraph methods, would be useful.

Questions

Could the authors report the training time of MAG-GNN? Knowing the timeframe compared to baselines would be helpful, given that the training of MAG-GNN is costly. I am wondering if it is possible to visualize the discarded and remaining subgraph structures resulted from RL. Given the complexity and freedom of tuning of the reported RL approach, such visualizations could aid in understanding which subgraph structures are useful and which are not. In particular, it will be informative to apply this visualization technique to toy-like graphs, similar to those in Figure 1, where we already know which subgraph structures matter.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See the "Weaknesses" section above.

After rebuttal

Thanks to the authors for their response. Their reply addressed my questions, and I raised my score accordingly. I think it would be interesting to compare non-random edge drop experiments, though, in a context similar to the lottery ticket hypothesis for graphs (search SNIP, Synflow, etc for attempts on tabular and imagery data). Perhaps this is something worth exploring, if the authors have the time and interest.