Venue: NeurIPS 2022 Conference

Reviews:

final_score: 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.
review_content: summary: The authors propose a Quantum Neural Tangent Kernels (QNTK) approach for GNNs.
The QNTK is based on GNTK, which is briefly covered by the authors, and QNTK is supposed to offer an accelerated version of GNTK through quantum computing.
The authors suggest to incorporate an attention mechanism (a transformer) in order to capture long range interaction of the graph data (as opposed to only 1-hop ring propagation in GCN) to learn global information about the graph.

The authors examine the proposed method on the graph classification task, on several datasets, where the achieved accuracy is less than considered or other existing methods.
strengths_and_weaknesses: Strengths:
1.The authors propose a method that involves quantum computing and GNNs, a subject that is relatively new and less researched.
2.The proposed method is claimed to accelerate GNNs - this is a major point in the field of GNNs.

Weaknesses:
1. From an originality point of view, the concept of QNTK was already proposed in different papers that were not considered in the paper (see for example "Representation Learning via Quantum Neural Tangent Kernels" (arXiv:2111.04225) and "Quantum tangent kernel (arXiv:2111.02951)). 

2.It is not clear what do the authors mean by an infinite width GNN. In the end, the method needs to be deployed in code, so does it mean that the number of channels is simply very large? It is not provided in text what the actual width of the network is.

3.From lines 75-76 it can be thought that the authors propose to use GAT, and thus the claim that it is non-local as opposed to the standard propagation of GCN is not in order. I suggest that the authors clarify that their suggestion is to use a transformer.

4.The authors claim a computational cost reduction from O(N^2) to O(N). However, when deploying a transformer that considers all pairs of nodes, it is not clear to me how the costs are saved.

5.Figure 1 is not self contained and also not explained in text properly. It is not clear what 'SVC' and 'SVR' means. 

6.Line 108 is not clear. The authors need to define what k* means. What is x* ?

7.The experimental results show inferior results compared to the considered methods. 

8.The authors claim for a significant acceleration of computation. However, it is not provided in the experiments. I think that the authors should present training and inference time to compare.

9.The authors consider a few number of layers, up to 8 layers. It is known that many GNNs tend to oversmooth as more layers are added. It is interesting to know how the network behaves with a more layers like 32 and 64.

10.The authors state that the current paper is focused on graph classification and not node classification. However, it is not clear what is the reason for this limitation. Is  it a limitation of the method?



questions: 1. Please clarify what do you mean by infinite width of GNNs, and what is the actual width of GNNs.
2.Please demonstrate your method with more layers.
3.Please provide runtimes for your method and compare it to other methods.
4.Can you please explain why your method is not working on node classification?
limitations: The authors discussed potential negative societal impact adequately .
review_title: null

final_score: 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.
review_content: summary: Graph neural tangent kernel (GNTK) is a powerful tool to combine the expressive ability of Graph Neural Networks (GNNs) and the trainability of Graph Kernels (GKs). The authors argue that, the vanilla feature aggregation operation in existing GNTK is too simple to capture diverse graph properties and training GNTK requires substantial computing efforts due to the kernel complexity.

To overcome these problems, the authors design a novel quantum graph learning model for graph classification. On one hand, to improve GNTK’s expressiveness, the multi-head attention mechanism is for the first time integrated into GNTK. On the other hand, the attention-enhanced GNTK is re-designed and re-implemented with a quantum version for improving the training speed. This is achieved by introducing the quantum aggregation transformation algorithm and the quantum kernel estimation algorithm. These two quantum algorithms make use of quantum superposition and quantum parallelism to realize the transformation of graph tangent kernel matrix, while preserving the dynamics of GNNs with infinite-width graph convolution and attention layers. 

Experiments show the proposed quantum model performs competitively against both GNNs and the GKs, and theoretical analysis explains the speedup benefited from quantum algorithms.

strengths_and_weaknesses: Strengths:
+ This work is clearly motivated and well written
The background of the research, the motivation of quantum graph learning for graph classification and the related work are all clearly stated and summarized.
+ The first for introducing attention mechanism in quantum graph learning
The multi-head attention mechanism is introduced into the GNTK by adapting the GNTK with reasonable modification by the incorporation of more node’s semantic similarity between the adjoining neighbors and nodes with similar features. The formulation of the resulting quantum version of GNTK is achieved by the association of quantum linear algebra subroutines.
+ Quantum speedup for improved GNTK  
To employ the natural properties of quantum computing such as superposition and parallelism, the quantum aggregation transformation algorithm and the quantum kernel estimation algorithm are designed for efficiently calculation of the GNTK. The theoretical analysis demonstrates that training the quantum-based GNTK is quadratically faster than its classical analogue.
+ Extensive numerical evaluation
This paper demonstrates the power of the quantum GNTK model on several graph classification datasets, achieving competitive performance with respect to the GNNs and the GKs. 

Weaknesses:
- The quantum algorithm described in this work is a quantum reconstruction of GNTK with extra attention layers. However, the whole training process is the kernel method, and the relationship between the proposed model and the GNNs is very weak. 
- Although computing GNTK inside quantum devices using the proposed quantum algorithms is very efficient after encoding the node attributes and compiling the specified quantum circuit. It seems that optimization of the whole model requires multiple execution of the same circuit and frequent interactions between classical and quantum environments, which could introduce additional expenses.

Overall, I think the paper is technically novel and considering there is no easy way to deploy the method in a real quantum machine due to hardware limitation in near future, I am fine with the current experiments. I vote to accept this work.
questions: 1. It seems that only the node feature is encoded into the proposed quantum graph learning model before the training starts. How is the structural information of the graph integrated into the whole training process?

2. In the experiment, the performance of GraphQNTK is significantly weaker than that of AttentionGNTK. Could you explain this phenomenon?

3. I am fine with the simulation on your classic computer. But what is the exact cost for your training? Because this is related to the cost for verifying your model’s advantage on a classic computer. 

limitations: Please see my questions.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper introduces an attention based graph neural tangent kernel and proposes a quantum algorithm to approximate it efficiently. Experiments are conducted on seven datasets with discrete attributes and four datasets with continuous attributes.
strengths_and_weaknesses: Strength:

1. With the attention mechanism, the proposed quantum graph learning model is better at capturing global information of the graph.
2. The runtime complexity of the quantum algorithm can be reduced from $O(N^2)$, which appears to normal graph kernel neural network, to $O(N)$.

Weaknesses:

1. From the reported results, the performance of the proposed GraphQNTK is not competitive compared to the baselines. 
2. The ability of capturing global information is advertised as a strength for the proposed model. However, no further theoretical argument or numerical experiment in the main body is presented to justify this feature.

questions: In addition to reducing the runtime complexity, what are the motivations of the proposed model?
limitations: Yes, the authors have addressed these in their work.
review_title: null

Meta-review: metareview: The authors propose a Quantum Neural Tangent Kernels (QNTK) approach for GNNs. The paper shows promising results of using quantum computing to speed up computations for graph data.  This is a novel idea, and the paper presents solid theoretical and empirical evaluations. Thus the AC recommends acceptance. 
confidence: Certain
Decision: Accept