Graph Neural Network Is A Mean Field Game

Thank you for acknowledging the contributions of our work. We are thrilled and grateful for your insightful feedback, which has significantly contributed to enhancing the quality of our manuscript. In the following responses, W and Q represent Weaknesses and Questions, and A represents the corresponding answer.

W1a: The paper appears not to be written for the ML/GNN community.

A1a:: Thank you for your constructive comment. We have reorganized the introduction. Since our overarching goal is to unify the existing GNN models in the MFC framework, we intended to make the introduction section self-contained by covering the learning principle and current challenges. Due to the page limit, a large portion of the experiment results have been moved to the Appendix.

Please refer to the revised manuscript.

W1b: I believe the motivation is that the proposed framework can offer a solution for all learning tasks an data sets, but this motivation (or any other) is not given precisely enough in the introduction.

A1b:: Thank you for your constructive comment. One of our major motivations is to overcome the bias of any assumption on the characteristics of graph topology. To achieve it, we formulate GNN as a mean-field game and introduce MFC theory to use the best game policy for the unseen graph data. The state-of-the-art performance on both homophilic and heterophilic data (shown in Table 2) underscores the advantage of our MFC framework for designing new GNN models. We have clarified the motivation of our work in the revised manuscript (please refer to Sec. 2.1).

W1c:: The concept of mean field theory and why it can be used for GNNs is not well explained for reader with ML background.

A1c:: Thank you for your constructive comment, due the limit page, we added a detailed explanation in the original manuscript for why GNN is a mean file game in Appendix A.5, and Figure 4 shows the evolution of our Nash-GNN from GNN. For clarity, we have added a clear explanation in the revised manuscript, please refer to Sec 2.4 (line 316 to line 328).

W1d:: Some important information can only be found in the appendix or footnotes

A1d:: Thank you for your constructive comment, we removed some important information into the main manuscript, please refer to the highlighted part in the updated manuscript.

W2 & Q4: The authors claim in the intro, that state of the art performance is not well suited for the underlying graph problem (p2., line 89-97) but evaluate their algorithm comparing it to state of the art.

A2:: Thank you for your thoughtful comment. Our intention was to validate this claim empirically. Therefore, we conducted a comprehensiveevaluation of our algorithm by comparing it against the current state-of-the-art methods to highlight the differences and limitations in existing approaches.

W3 & Q5: The authors claim to be the first to propose a graph meta-learning method (p. 7, line 330), but I found several other papers

A3:: We apologize for the confusion. Our major contribution is a novel MFC framework to design novel GNN models for unseen graph data. We are aware of existing work on meta-learning on graph data. Therefore, we are not going to claim that our method is the first effort to explore graph meta-learning. Instead, we simply highlight in the text that our work has a meta-learning flavor. We have carefully reviewed our current write-up to make sure there is no such indication related to the innovation of meta-learning.

W4 & Q6: The GIN model is missing in the benchmark algorithms.

A4: Thank you for your comment, we have added GIN as the benchmark algorithm (please refer to Table 3 and Appendix B.2). The data splitting method follows this work https://arxiv.org/abs/1911.07979.

W5: The read thread can be improved.

A5:: Thank you for your comment. We have rephrased the hard part according to all reviewers’ comments. Please refer to the marked parts in the revised manuscript.

W6: There is no comprehensive state-of-the-art section.

A6:: Thank you for your valuable comment. We have added a comprehensive state-of-the-art section, please refer to Appendix B.2.

W6: Figure 1 does not really help in understanding the method and figure 3 is confusing.

A7: Thank you for this comment. We have improved Fig. 1 and Fig. 3, and we have added more explanation for Fig. 3, please refer to Fig.1 and Fig. 3 in the updated manuscript.

Dear, Reviewer ihdE,

We really appreciate your constructive comment. We are trying our best to address your concerns promptly.

• For Fig.1, we have redrawn it and uploaded it at https://anonymous.4open.science/r/Nash-GNN-4570/Fig1_revised.png.

• For Fig. 3, we have redrawn it and uploaded it at https://anonymous.4open.science/r/Nash-GNN-4570/Fig3_revised.png. Also, we can replace it by using the pseudo-code (please refer to Appendix A.6).

We greatly appreciate your suggestion and assure you that it will be incorporated into the final version.

Thank you very much for your valuable contribution!

We will make every effort to thoroughly address all of your concerns. We sincerely hope you can reconsider your rating.

Best,

Authors

Dear, Reviewer ihdE,

We sincerely appreciate your time and effort in reviewing our manuscript and providing such constructive feedback. As the author-reviewer discussion phase is nearing its end, we wanted to check if you have any further comments or questions regarding our responses. We would be more than happy to continue the conversation if needed. If we have addressed your concerns, would you like to update your rating?

Thank you so much.

Best,

Authors

Thank you for acknowledging the contributions of our work. We are thrilled and grateful for your insightful feedback, which has significantly contributed to enhancing the quality of our manuscript. In the following responses, W and Q represent Weaknesses and Questions, and A represents the corresponding answer.

W1: ...the paper to be very hard to understand...

A1: We apologize for the confusion. We reviewed and restructured the storyline of our work, Specifically, we have added a “Background and Motivation” section (please refer to line 151 to line 176 in the updated manuscript) to highlight the significance of the variational framework of mean-field control as a novel approach for developing innovative GNN models. The structure of the "2 Methods" section has been reorganized, as illustrated in the right panel of the updated Fig. 1. First, we frame the feature representation learning in GNN as a dynamical system of minimizing an energy function via a pre-defined gradient flow. Second, we extend the conventional graph diffusion process to a reaction-diffusion model, yielding a general mean-field control framework that unities most of the current GNN works. Furthermore, we reformulated the functional $\Theta_1$ and $\Theta_2$ as the control pattern in the mean field, which allows us to reshape the message-passing mechanism in GNNs. By learning the control patterns from the underlying graph data, we are able to jointly identify the most suitable learning mechanism and fine-tune the GNN hyper-parameters in a “meta-learning” paradigm.

W2: ...There seems to be an overall distinct lack of clarity in the work...

A2: We have rephrased and rewritten almost 30% of the write-up. We appreciate the valuable feedback that allows us to significantly improve the clarity of our work. Please refer to the marked BOLD line parts in the updated manuscript.

W3: Figure 1 is quite non-standard presenting a rather imprecise analogy.

A3: We partially agree with this reviewer that the cartoon in Fig. 1 might not be conventional in a technical conference. However, we respectfully argue that the analogy exactly highlights the limitations of current GNN models and clearly conveys our proposed solution to address this challenge. The page limit is partly responsible for this confusion, so allow us to provide a more detailed explanation in this rebuttal. If the reviewer finds it helpful, we will incorporate it into the final version.

The example of gearbox is used to illustrate the issue that the current GNN model applies the fixed learning mechanism (same gear) to all graph data. While current GNN models demonstrate promising learning performance, it is highly likely that their effectiveness stems more from data-fitting capabilities than from a good understanding of the graph learning mechanism, making them prone to overfitting. Take the gearbox in the manual transmission car as an example. Although it is mechanically possible to drive on the highway using low gears, it is uncommon because, over time, it can cause damage to the engine. In this context, the ability to shift gears according to different traffic conditions is highly desirable. Similarly, we propose to incorporate an (outer-loop) learning component, on top of the (inner-loop) GNN optimization, to identify the most suitable learning mechanism by shaping the control patterns $\Theta_1$ and $\Theta_2$.

W4: Figure 2 is quite confusing and dense, it might be worth swapping Figure 2 with algorithm 1 in the appendix as that to me is much more clear.

A4: We appreciate this constructive comment. We will swap Fig. 2 and the table of Algorithm 1 in the final version.

W5: Figure 3 is quite confusing, the caption needs more information.

A5: We apologize for the confusion. We have updated the plotting of Fig. 3 as well as the caption. Please check the highlighted part in the new version. Thanks.

I would like to thank the authors for their large effort in this rebuttal. Reading the reviews from ihDe, I tend to agree with their point that the paper does not seem to be written for a “GNN audience”. I would also like to acknowledge the review from aaZh, where they mention that the “paper was clear and easy to follow” — something which I personally disagree with. I believe that the new revision does increase its readability, but the amount of changes make me wonder if another review cycle would be needed. Perhaps the AC can comment on this.

I am not opposed to the acceptance of this work, but I do not believe that I have understood it well enough to provide a definite accept score. For this reason I would like to increase my score, but keep my confidence at a 2. This is not a comment on the technique but rather mostly on the presentation. I do believe sections such as 2.3.1 are in the right direction, but in my opinion still more work is needed to increase the target audience of this work.

Thank you for acknowledging the contributions of our work. We are thrilled and grateful for your insightful feedback, which has significantly contributed to enhancing the quality of our manuscript. In the following responses, W and Q represent Weaknesses and Questions, and A represents the corresponding answer.

W1: While the proposed framework is intriguing, it does not address several important challenges such as over-smoothing, over-squashing, and the ability to capture long-range dependencies in graphs. As a result, it is unclear whether the framework can mitigate these problems.

A1: Thank you for your constructive comments from an application perspective. In a high-level pitch, we conjecture that one possible solution to address the common issues in GNN, such as over-smoothing and over-squashing, is to use the appropriate learning mechanism in information exchange between connected graph nodes. For instance, in homophilic graph data, neighboring nodes are encouraged to have similar feature representations. Otherwise, in heterophilic graphs, information exchange should be discouraged, even if the connectivity is strong. In this regard, our major contribution is to present a novel learning paradigm by conceptualizing the feature representation learning in GNN as a mean field game. By capitalizing on the variational framework and physical principles, we proposed to learn the optimal control pattern that allows us to achieve state-of-the-art performance by using the most effective learning mechanism for the unseen graph data.

Although we have not specifically evaluated the effectiveness of addressing the over-smoothing issue in our original submission, we demonstrate the learned control patterns in Fig. 3 left, where we found the learned control pattern is highly correlated with the graph homophily ratio. In addition, we have conducted an extra experiment to demonstrate that our method enables the use of a much deeper network architecture by mitigating the over-smoothing issue. The results are shown as follows. We will include this result in the final version if this reviewer thinks it is necessary.

In addition, unlike traditional GNNs, directly solving PDEs in our method enables fine-grained control over the speed and range of information propagation, allowing for more selective and localized information flow. This control helps prevent excessive information aggregation, ensuring that node representations do not neutralize too quickly, thus mitigating the over-smoothing problem.

W2: Some of the datasets used in the experiments are either relatively small

A2: Thank you for this valuable comment. We have added two node property predictions (single-label classification) in OGB dataset (i.e., ogbn-arxiv and ogbn-products). We still keep the results of Texas, Wisconsin, and Cornell since they have been reported in many other GNN works.

We can observe that our Nash-GNN can achieve considerable results, we have added these results in the revised manuscript (please refer to Table 8).

W3: It would be good to clarify the conditions required for the optimization problem in Eq. (6) to be well-posed, i.e., to have a unique solution. Moreover, when Eq. (6) is non-convex, how does converging to a local minimum influence the model's predictive performance?

A3: Thank you for your constructive comment. In our formulation, ensuring that Eq. 6 is a convex function is a necessary condition for identifying the critical point. This is why we utilize an Input Convex Neural Network (ICNN) to model the function.

Dear, Reviewer aaZh,

We sincerely appreciate your time and effort in reviewing our manuscript and providing such constructive feedback. As the author-reviewer discussion phase is nearing its end, we wanted to check if you have any further comments or questions regarding our responses. We would be more than happy to continue the conversation if needed. If we have addressed your concerns, would you like to update your rating?

Thank you so much.

Best,

Authors

Dear Reviewers,

We hope that our rebuttal has addressed your concerns and now we provide more clarity and understanding of our work in light of your valuable feedback.

We sincerely appreciate your thoughtful comments and invite you to reach out with any additional questions or requests for clarification.

We hope to contribute to the esteemed ICLR and the broader "learning on graphs and other geometries & topologies" community by having this paper published.

Thank you for your time and consideration.

Best,

Authors