Neural Tangent Kernels Motivate Graph Neural Networks with Cross-Covariance Graphs

Summary

This study offers a theoretical analysis of Graph Neural Networks (GNNs), emphasizing their infinite-width limit behavior through the lens of the Neural Tangent Kernel (NTK). The research illuminates the constancy of the NTK in such scenarios, advancing the understanding of neural network learning dynamics. Furthermore, the paper explores the implications of varying training intensities across GNN layers, enhancing interpretability in a field often perceived as a 'black box.' The authors validate their theoretical assertions with detailed experiments, utilizing public datasets to ensure reproducibility and credibility. This paper bridges complex theoretical insights with practical machine-learning applications, contributing substantially to the discourse on neural network training, optimization, and generalization. Its rigorous approach and novel findings mark a significant stride in understanding and leveraging the full potential of GNNs.

Strengths

1. By exploring the constancy of the NTK in the infinite-width limit, the study sheds light on complex learning dynamics, enhancing the scientific understanding of how GNNs train and generalize. This rigorous theoretical foundation pushes the boundaries of existing knowledge in neural network behavior. 2. By dissecting layer-specific training implications, the paper contributes to the interpretability of neural networks, helping researchers to better understand and optimize their GNN models, which is particularly valuable in the 'black box' context of deep learning.

Weaknesses

1. While the paper is strong in theoretical analysis, it may not provide extensive insight into the practical applications of the findings. The implications for real-world scenarios, particularly how these theoretical insights into GNNs and NTK behavior could be harnessed for tangible improvements in specific use cases, might not be thoroughly discussed. 2. If the experiments were conducted within a narrow set of conditions or datasets, they might not fully represent the complexities of real-world data and scenarios. This limitation could raise questions about the generalizability of the findings and their robustness when applied to diverse, practical challenges in the field of machine learning.

Questions

1. Given the depth of the research, what do the authors see as the next steps or future directions in this domain? Additionally, are there any inherent limitations or challenges in the proposed methods or findings that might need to be addressed in subsequent research? 2. Can the analysis be extended to deeper (more than 2 layers) GNNs where the aggregation operation is used in internal layers?

Rating

5: marginally below the acceptance threshold

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

2 fair

Contribution

3 good

Summary

The authors delve into the theoretical aspects of Neural Tangent Kernels (NTKs) and their influence on the learning and generalization behaviors of over-parameterized neural networks in supervised learning tasks. They introduce the concept of "alignment" between the eigenvectors of the NTK kernel and the given data, which appears to play a significant role in governing the rate of convergence of gradient descent and the generalization to unseen data. The paper specifically explores NTKs and alignment in the context of Graph Neural Networks (GNNs). The authors' analysis reveals that optimizing alignment corresponds to optimizing the graph representation or the graph shift operator within a GNN. This investigation leads to the establishment of theoretical guarantees concerning the optimality of certain design choices in GNNs.

Strengths

* The paper is well-organized, with a clear delineation of concepts such as NTKs, alignment, and their relevance in the context of GNNs. * The paper's findings have the potential to advance the understanding and analysis of Graph Neural Networks, providing theoretical insights that could be valuable for the community.

Weaknesses

* The paper seems to miss a crucial related work: Huang, W., Li, Y., Du, W., Yin, J., Da Xu, R. Y., Chen, L., & Zhang, M. (2021). "Towards deepening graph neural networks: A GNTK-based optimization perspective," ICLR 2022. Including and discussing this work could provide a more comprehensive perspective and strengthen the literature review section. * The theoretical framework primarily relies on the existing NTK theory regarding optimization and generalization. While the authors have cited relevant works, a more distinct and innovative theoretical contribution that extends beyond the current NTK theories would enhance the paper's novelty and impact. * The paper's discussion on alignment seems closely related to node classification and graph classification tasks. However, there appears to be a lack of relevant examinations or experiments to empirically validate the proposed concepts and theories in these tasks, making it difficult to assess their practical relevance and effectiveness. * The paper could significantly benefit from a more robust and comprehensive experimental section. Ensuring that the experiments thoroughly validate the theoretical findings, involve extensive comparisons with baseline methods, and are evaluated across various datasets and tasks is essential for demonstrating the approach's practical significance and effectiveness. * A more detailed and thorough comparison with existing NTK and GNN methods is necessary. The paper should highlight the proposed approach's novelty and advantages, supported by theoretical or empirical evidence, to clearly showcase the contributions and distinguish the work from existing literature.

Questions

* Could the authors elaborate on how the alignment concept is related to node and graph classification tasks? Are there any practical insights or guidelines on how to effectively apply the proposed theories to these tasks? * Can the authors highlight the novel aspects of their theoretical framework that go beyond the existing Neural Tangent Kernel (NTK) theories? What are the unique contributions that differentiate this work from existing NTK-based studies? * Are there plans to include more comprehensive experiments to validate the proposed theories and concepts? What datasets, tasks, and baselines are considered for these experiments? *Will there be experiments conducted specifically to verify the proposed theorems, such as theorem 2 and theorem 3? If so, could you provide insights into how these verifications will be carried out empirically? * Why the size of $\mathbf{y}_i$ is $\mathbb{R}^{n \times 1}$, given the size of $\mathbf{x}_i$ is $\mathbb{R}^{n \times 1}$? Is there a specific rationale behind this choice of dimensionality? * Could you elucidate the rationale behind choosing the HCP-YA dataset for your experiments? How does this dataset align with the objectives and hypotheses of your study, especially considering that common node classification or graph classification tasks are typically used in related works?

Rating

5: marginally below the acceptance threshold

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

Ethics concerns

The ACKNOWLEDGEMENTS on page 13 might violate the anonymity.

Summary

This paper draws on the idea that NTK based generalization is based on the associations of eigenvectors of the NTK with the data. Drawing on this alignment in the case of a GNN is used to derive the graph shift operator (i.e. equivalent of a graph laplacian) that is different from the input graph. To do this they solve an optimization to derive the graph as being the cross-covariance matrix of the input with the output.

Strengths

Generalizing the NTK to GNNs expands the theory associated with this area, and the suggestion of using a cross covariance matrix involves a graph that uses both input and output variables as nodes, which is not commonly done in current GNNs. The theory could be useful in cases where the graph is not given but constructed as an affinity matrix from data as well.

Weaknesses

The key weakness is that empirically VNNs and graphs that are based on covariance matrices rather than non-linear affinities have fared worse in practice. This may be an instance of the NTK not explaining the entire behavior of neural networks. Moreover the experimental validations seem fairy limited without comparison to GCNs and Graphormers and other modern graph neural network architecture.

Questions

Is this a case of the theory not explaining the entire empirical phenomenon? Can further experiments be performed on a variety of kernels to see what works better in practice on common datasts/

Rating

8: accept, good paper

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

Global response

We are grateful to all reviewers for their insightful feedback and appreciation of our work. We have provided individual responses to all reviewers. In this global response, we focus on (a) the major novelties and implications of our theoretical analysis; (b) a summary of our response to the common concerns regarding experiments; and (c) future directions of our work. **Novelty of our theoretical analysis.** The motivation of our study is based on a generic property of gradient descent, which dictates that the **alignment** between the vector of output data and NTK leads to faster convergence and better generalization. In our paper, we leverage the fact that NTK for a GNN is an explicit function of its graph shift operator and hence, optimizing alignment can inform the choice of graph shift operator in GNNs. *To the best of our knowledge, this optimization viewpoint on alignment and leveraging it for selecting a graph shift operator that leads to provable performance gains is novel when compared with other NTK-based studies in GNNs.* Our theoretical analysis naturally provides a novel insight into constructing a graph in supervised learning tasks, based on the interdependencies between the input and output data, namely, the cross-covariance. This is in contrast to choices prevalent in existing literature that leverage only the relations between the input features for graph construction in GNN models. **Experiments.** The reviewers raised concerns regarding the relevance and sufficiency of the experimental results with respect to the theory presented in the paper. The primary goal of our experiments was to validate the implications of our theoretical analysis on a real-world dataset. Since the proposed choice of cross-covariance-based models consistently outperformed the models with input-based graphs, our initial set of experiments succeeded in validating the theoretical results. In addition, we have **expanded our experiments** in the revised paper as follows: - *Additional datasets.* (see Appendix H.7) To demonstrate that our empirical observations were not constrained to one particular setting, we have also added results for a similar multivariate time-series prediction task on two more datasets that pertain to *traffic forecasting* and *brain activity prediction for ECG modality*. - *Graphs with non-linear affinities.* (see Appendix H.6) We have added results derived by additional choices of input-based graph constructions (including nonlinear affinities). Our results demonstrate that GNNs with cross-covariance graphs outperform these different choices of graphs constructed only from the input data. - *Time-series prediction as specific application.* (see Appendix H.5) The setting in our initial experiment provided the building block for a formal task of time series prediction using past data. We have expanded our experiments in this direction to build a more sophisticated model for time-series prediction on the HCP dataset which utilizes more than just a single previous time step. Within this setting as well, the models with cross-covariance based graph structure outperform those with graphs based solely on the input data. **Future Directions.** We believe that our paper lays the foundation for various research directions and concur with Reviewer bUqG’s assessment that it *“bridges complex theoretical insights with practical machine-learning applications”*. Extending the analyses to GNNs with depth more than two layers or with alternative architectures is expected to add additional analytical challenges that must be explored further. Analyzing the more practical setting where the NTK evolves during training is of particular interest since feature learning does not happen in the infinite-width constant NTK regime. Further, expanding our theoretical framework beyond the limits of our current analysis is another important direction. We have discussed these future directions in Appendix C.