GraphQNTK: Quantum Neural Tangent Kernel for Graph Data
Authors: Yehui Tang
Junchi Yan
Venue: NeurIPS 2022 Accept (2022)

Abstract: Graph Neural Networks (GNNs) and Graph Kernels (GKs) are two fundamental tools used to analyze graph-structured data.  Efforts have been recently made in developing a composite graph learning architecture combining the expressive power of GNNs and the transparent trainability of GKs. However, learning efficiency on these models should be carefully considered as the huge computation overhead. Besides, their convolutional methods are often straightforward and introduce severe loss of graph structure information. In this paper, we design a novel quantum graph learning model to characterize the structural information while using quantum parallelism to improve computing efficiency. Specifically, a quantum algorithm is proposed to approximately estimate the neural tangent kernel of the underlying graph neural network where a multi-head quantum attention mechanism is introduced to properly incorporate semantic similarity information of nodes into the model. We empirically show that our method achieves competitive performance on several graph classification benchmarks, and theoretical analysis is provided to demonstrate the superiority of our quantum algorithm. Source code is available at \url{https://github.com/abel1231/graphQNTK}.

GraphQNTK: Quantum Neural Tangent Kernel for Graph Data
Yehui Tang, Junchi Yan"
Department of Computer Science and Engineering
MoE Key Lab of Artificial Intelligence
Shanghai Jiao Tong University
Kyehuitang, janjunchi edu. cn
Abstract
Graph Neural Networks (GNNs) and Graph Kernels (GKs) are two fundamental tools used to analyze graph-structured data. Efforts have been recently made in de- veloping composite graph learning architecture combining the expressive power of GNNs and the transparent trainability of GKs. However, learning efficiency on these models should be carefully considered the huge computation overhead. Besides, their convolutional methods are often straightforward and introduce severe loss of graph structure information. In this paper. we design a novel quantum graph learning model to characterize the structural information while using quantum parallelism improve computing efficiency. Specifically. a quantum algorithm proposed to approximately estimate the neural tangent kernel of the underlying graph neural network where multi-head quantum attention mechanism is intro- duced to properly incorporate semantic similarity information of nodes into the model. We empirically show that our method achieves competitive performance several graph classification benchmarks, and theoretical analysis is provided to demonstrate superiority of our quantum algorithm. Source code available at bittps://gihhie com 1231//111///// hatp///rrph/KKKKK/
Introduction
Fusing quantum computing and classic machine learning has become promising subject of research. Quantum- based algorithms have been proposed in recent years, from naive quantum non- paramerttt
machine learning [2 36
43 32
to classic-
hybrid deep leaning 7 10 46
37
14]. Despite
that quantum machine learning (QML) has shown its potential in many machine learning tasks, quantum computing for graph learning is still in its early stage [61]. Inspired by the two popular classes methods for learning on graph data, i.e., Graph Neural Networks (GNNs) 20) 39 21 67
and Graph Kernels (GKs) 24 several works attempt to build quantum graph learning architecture that captures the structural information of graph data, such as Quantum Graph Neural Networks
(QGNNs) (64 7 I [6 I and Quantum Graph Kernel Methods (QGKs) [56
3
25 A brief
review about quantum graph learning illustrated in Fig. 1
have been developed to dissolve the characteristics of the graph into the quantum model. However, most present quantum graph learning models are hybrid such that the expressive capability depends more on the complexity of the classic modules 70]. It is difficult characterize the structure information and attribute information of the graph by the quantum components without the participation of classic modules. Even worse, the frequent interactions between classical systems and quantum environments generally incur additional overhead [55] It is unclear whether the introduced quantum module
Some quantum subroutines for attribute encoding 5 70 and structural encoding 64 46
"Junchi Yan is the correspondence author who is also with Shanghai AI Laboratory.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

can improve the performance of the model as well as the training efficiency. Besides, most of existing proposals for quantum machine learning for graphs lack a clear demonstration of a quantum superiority for tasks on classical datasets.
Using quantum computing power boost the trainability and expressive behaviour of classic machine learning models provides one of the most promising direction for quantum machine learning. It demonstrated that the power of quantum computing could be used to find atypical but useful
patterns that classical systems are not considered to be able to generate effectively [4 24 28) and
accelerate the training process of existing classic models 36 43 [T]. Several quantum algorithms based on the HHL algorithm [22] show the exponential speedup compared with their classical counterpart, with a assumption that a quantum random access memory (QRAM) [35 is accessible. Recent literature employ quantum algorithms to efficiently train deep neural networks
12
45
71 reconstruct unsupervised clustering (34 and supervised kernel classifier [43]. is hopeful that
quantum computing could provide a new learning paradigm. In addition, simulations and physical experiments have proved the potential of using quantum algorithms to encode and process regular classical data such as text and image [60 (6.
Beyond vanilla GNNs and GKs, composite graph learning studies have emerged that com- bine the advantages of both areas 50
Input Graph
Encodiing
Process
Processing
Post
18 In this literature, Graph Neural Tangent Kernel (GNTK) [17] based on neural tangent kernel (NTK) 31 shines its lights on elegantly fus- ing GNNs and GKs, leading to new prospec- tives of training and analysing infinite-widhh GNNs. However, the computation overheads is extremely large due to either the dense gram matrix 177, or the large number of substructures to be compared after graph decomposition [TO]. Prospectively, the barrier that conventional model is difficult to train and scale up is expected to be cireumvented with the help of the uniqueness of quantum computing. Early research involves altering the amplitude of quantum basis states to accomplish a quantum logic operations (8), which is prof- itable from the huge quantum Hilbert space to encode the normalized data. Recently, simultaneous transformation of basic states in quantum superposition using quantum parallelism is regarded as remarkable manifestation of quantum superiority, which is successfully implemented in classic machine learning to reduce the computational overheads [36, 37 71]. These strategies could be helpful in the regime of training graph models with either the non-convex nature of the training procedure, or the poor scalability w.r.t. training size.
Quantum walk
Quantum Unit
Deep Neural Network
Adiabatic evolution
structure Information
Conditional unitary
Vector meserur Machine
Inter actioitio
Variational circuit
Support Vector Regression
node aftr abtribute
QRAM
Classical Unit
Figure 1: Overview of quantum graph learning,
In this paper, we focus on quantum machine learning of graph-structured data with attributed nodes and binary edges. Inspired by recent quantum neural network methods [37] 71] that efficiently reconstruct the dynamics of classic neural networks using quantum computing techniques, new quantum graph learning model is proposed which is analogue to train an infinite-width GNN with attention mechanism, where the number of heads goes infinity. Our contributions are:
Attention-enhanced GNTK. Infinite-width GNN is a well established term in the GNN literature 17 29), and GNTK [77 is a powerful tool to analyze the GNN. However, the traditional feature ag- gregation of the vanilla GNTK is straightforward, limiting itself within joint neighborhoods. In this paper, multi-head attention mechanism is introduced to properly incorporate semantic similarity information of disconnected nodes but with similar features to improve model expressiveness.
Kernel methods for evaluating the dynamics of wide and deep GNNs. It is generally hard to train a deep GNN with attention, especially when the width of GNN, the width of attention layer, the number of heads goes to large. We properly incorporate into GNTK by using NTK theory. We use kernel methods to capture the dynamics of infinite-wind width GNN with infinite-width attention, thus avoiding the huge overhead of training a wide and deep GNN.
width multi-head attention
Speedup introduced by quantum computing. Although GNTK is a useful method to train an infinite-width GNN, its cost still grows quadratically with respect to the volume of data, which is intractable for large datasets. We re-design the Attention-enhancee GNTK by splitting into small components and reuniting them using the quantum linear algebra subroutines. The produced

---

quantum graph kernel GraphQNTK, theoretically reduces the computational complexity from ( (NN) benefited from the quantum parallelism.
2 Methodology
2.1 Preliminaries
first briefly review the most common setting for GNNs and the corresponding NTK, and by the way the notation is given. A graph G (V, E) is denoted by collection of nodes V and edges E. Each node has a d-dimensional feature vector h, E R. E V, and H E Rnxd is the feature matrix stacking all nodes features. For graph classification, we consider the dataset with set of graphs (G1..... GN } S G and their labels (UI,..., UN S y. Our goal is to learn to predict labels of unseen graphs.
The formulation of GNN. The differences of GNNs mainly depend on the different settings of message propagation process. Here we consider simple message passing framework (20) and the propagation of the I-th (1 E [L] layer is given as:
h
E (EN(u)
h h(-1)
(1)
h2
Co d'
Way Co
Wh-1''
W
jdd (w,f) (w166)))
(2)
d'R-1
where (u)) denotes the neighbors of u, Co is the scaling factor, d' is the output dimension of the 1-th layer and the r-th connecco layers,
element-wise activated function, and W R is learnable weights performing on the input for R times of the I-th layer (equivalent to R fully-connected layers without the bias term).
For graph classification, the output is a permutation invariance function acting on the collection of all node features in the last layer. The popular sum_pooling ing function is adopted: hG EnEv h
NTK of the infinite-width GNN. Consider training set (xx, V/ v:)) R R. When an over- parameterized fully connected network f0, x) .Rd
whose width is allowed to go to infinity and parameters 0 are randomly initialized and trained with gradient descent, the dynamics of the network equivalent to the kernel regression 33 This is the so called neural tangent kernel (NTK);
H(t) Of (0(t). 24) 0f (0,
(3)
00
00
which remains constant during training, i.e., H(I) H()). And replace H(I) with H for convenience. The final prediction for a test datapoint x,
f(x.) H.
where y; = and k. E RRN is the vector whose i-th element denotes the NTK value between and X..
It is discovered that convolutional neural networks (CNNs) with wndinite-width channels and infinite number of filters also have the same behaviour (2) Inspired by this, Du al. [17 adopts the designing strategy of NTK and leverages a GNN architecture to design new graph kernels, which called GNTK. The dynamics of training the GNTK equivalent to train an infinitely-wide GNN initialized with random weights trained with gradient descent. Specifically, consider two input graph V ní, the GNTK θ E Rax'' and the relative covariance matrix Σ Roxn' in the 1-th layer of the feature aggregation phase described in Eq.
G= (V, E) and G' (V', E') with [V| and
after fully-connected layers are given by
Σ (G,G") un
Σ
Σ
E (G,
(EN(N)U(U) ('EN()))(())
(5)
@0% G")
Σ
Σ
[0] R
(")
3

---

which is an affine transformation of the input GNTK and covariance respectively where and GC, G') uw are both defined to be h, hy. We replace them with and [ G')] uw respectively without ambiguity.
O ( G)] aal
( G))
The successive fully-connected layers defined in Eq, are used to update the node hidden feature after aggregation. Specifically, the GNTK of the fully-coom cully-connected layer is recursively associated to that of the previous layer, and the transformation is given by
[>] (G,G)l (rr-1) ([
(G, (G, E [R]
where (f)); : []- I denotes the the conjugate activation function corresponding the activated function with centered Gaussian processes of covariance at the r-th fully- cully-comnected layer, as described in [1] And the derivation of the covariance is
Σ (G,G') uul
à (a(r- (E) (G, (G,
where å denotes the derivative of Given Eq. feature update phase denoted by Eq. is given by
6 and Eq. the transformation of the GNTK for the
2
II [. (
( (G, G") uu
(O'(GG
Σ E (G, um
(8)
Therefore, computing each element of the GNTK (or covariance) matrix is only reliant the element at the same place of the GNTK (or covariance) matrix in the previous fully-connected layer. The final GNTK corresponding the two input graphs G and G' determined by the sum sum__oom ham_pooling function:
@ (G,G))
Σ WE WEV.WEV
[0 (G, G')
Intuitively, calculating each element of the GNTK of fully-connected layers could be accelerating by proper quantum kernel estimation algorithm. However, indirect to realize an end-to-end speedup for GNTK since calculating the element of GNTK requires affine transformation. To circumvent this barrier, we derive a unitary quantum aggregation transformation to bridge the gap between quantum kernel methods and estimation of GNTK.
2.2 QNTK with Attention Mechanism
Before giving the analytical quantum reconstruction of GNTK with multi-head attention mechanism. first elaborate how to integrate the transformer layer into the GNN described in Sec. 2.1 The resulting GraphQNTK can be efficiently reconstructed by quantum computing paradigm, which gives quadratic speed-up and estimate the GNTK is shown in Fig. 2
the classic estimation of GNTK. The mechanism to build the GNN
GNN with multi-head attention. bution of each node's neighbor to the central node as equally important, which can be viewed as learning an averaged filter across the whole graph [66), leading to great loss of structure information. Besides, the aggregation only is performed within the adjoining neighbors under the assumption that the graph is homophilous. The method may fail to learn effective graph structures for message passing [2]. To capture the global node similarity semantics the provided graph, numerous attempts that employ transformer for graph learning have been developed [27 51 53 68). Consider the input feature matrix H E Nx'' where denotes the number of samples and s' is the dimension of feature at layer / before implementation of the transformer. The single transformer layer is to project the input H Nxe' by three matrices, i.e., W R W E IR' x and W E R x to the corresponding representations Q' K' Vl. The formulation is given as
The aggregation process of vanilla GCN 39 regards the contri-
Q' = Q'=H', W
K' H'W,, v'= =HH'' W
A ( V G' Q'K'"
(10)

---

GNN with Attention Mechanism
Infinite-witth-lmiit GNTK
Ø (G, (G, E (G.G)
Quantum Aggregation Transfomation
Attention (ransformer)
Quantum Arthmetic
Dg (G,G") 0 G")
Recursively
Update (fully connected layers)
Σ (G, 0 (G,
Quantum Estimation
Nisi
Inner Product Eslimaaion
E) (G, (G,
Aggregate (affine traneformation)
Figure 2: Framework for GNN with attention mechanism and its corresponding GNTK. The GNN comprises a message transmission process similar to the vanilla GCN but involves transformer at the tail of the model (excluding the last layer), which characterizes the global semantic similarity between each pairs of nodes. The neighbor aggregation is kept since the two nodes connected by an edge often have stronger semantic relationship. The dynamics of the unfinitewwidth-lle analogous to kernel methods and we reconstruct it by quantum algorithms to estimate the kernel.
GNN
where Ç denotes an element-wise activated function. The multi-head attention alternative is given by
H
H
W
(11)
out
where W )xM projects the N x Mst concatenated multi-head feature matrix back to N s matrix.
Let and @ denote the neural network Gaussian Process Kernel (NNGP) [51] and NTK after the transformer layer, and let Y and Ô be the input NNGP and NTK before the transformer layer. Consider two input feature vector and x'. When the output dimension of the transformer layer and the number of heads go to infinity, ie., s 20,8 + s0 - 00, M + co, the output NTK is:
+ (x,x) 2Y (x,x) Y (x,,) 3 (x,x)
Y (xxxx)))'
(12)
Y (x,x') = ( (x, (x,x) Y (x,x) Y (xxxx)))
where the under the restriction that 1) W/ and W share the same weighs, and 2) scaling the dot products between Q' and K' by their dimension instead of the square root of the same quantity, i.e., G Q'K'T The detailed proof can be found in [26].
x
To efficiently estimate the element of the NTK defined by the transformer layer using quantum parallel, we slightly modify the Eq. as
xx x') = 2Y (x, + T (x, x)) o o (x,x',
(13)
Y (x, TT (x) C Y (x,x'),
where T (x, x") is the result of matrix multiplication between the column vector of the diagonal of Y x) and row vector of the diagonal of Y (x', x'), and T is the result of matrix multiplication between the diagonal of those two matrix after activated operation. For simplicity use, we consider identity function as the activated operation, i.e, - I. It is reasonable to accept this modification since in the limit of infinite width neural network the output converges in distribution to a multivariate normal with a block diagonal covariance [5]]. Notice that the difference between the definition of NTK is that the former denotes the expectation with respect to
NNGP and the covariance output before the actívated operation, while the later after the denotes the expectation with respect to the output after the activated operation 31. Consequently, we consider that Y is equal to the covariance of NTK within the transformer layer as the result of the identity activated function.
5

---

GNTK with infinite-width-lmmit attention. To appropriately incorporate semantic similarity in- formation of nodes into the model, a multi- attention mechanism implemented at the tail of the each GNN layer except the first and the last layer, and the calculation of the GNTK with infinite-width-ling attention is to insert an additional procedure after the fully connected layers. For the two input graphs G and G', the formulation derived by Eq.
13 is given as
@ R (G,
E (G, (G, = =
+ I (G, G")
1O's (G, G')] un!
uni
(14)
Eh (G,
uw! (G. (G.G) neve [E'R (G, (G) un
where T (G, G") (') is the result of matrix multiplication between the column vector of the diagonal of ER (G, and row vector the diagonal of Σ G'). The affine transformation the input GNTK corresponding to the aggregation phase as described in Eq. is changed to (similar to 2));
[ (G) uu
E
E "G,'))
(15)
"EN(wUUA)) (a)
2.3 The Proposed GraphQNTK
We first show that estimating the single-layer GraphQNTK and its covariance with infinite-width- limit attention mechanism can be efficiently reconstructed in the regime of quantum computing, and generalize to the multi-layer model. The following statements only consider two input graphs G = EV) and G (V', E") with [V| = n and [V' = n', and the corresponding feature matrix H [h..... h ..T...... h,j] E Raxd and H' [hT.... ...... ......... h E R xd The approximate estimation of GNTK is denoted as θ E Bexn' and its element @un- The corresponding covariance is Σ E Raxn' and Emw.. We use Oar E R to represent GraphQNTK after readout. We omit the subscript R for clarity. The same setting can be easily generalized to the arbitrary pair of graphs G, G' E G by introducing auxiliary index registers. First, we introduce the quantum data
structure accessible the classical data, as commonly used by QML algorithms [52 36 34 7T).
Feature encoding. Using the storage structure as stated in our proposed Theorem I in Appendix, the feature matrix can be prepared into the QRAM at the initialization of the algorithm. The data encoding only occurs a single time and readout operation only takes logarithmic complexity time with respect to the number of samples and dimension of feature d. The quantum representations corresponding to the encoded feature vector and feature matrix are as follows
(u) 10) + (u) [b,)
10)
b ll lu),
(16)
Iu') (0) - (n') [bw), 10)
Estimation of the initialized NTK. The empirical uncentered covariance of inputs [ G')
and
and the initialized GNTK [ G')] uy is the inner product between h, and h Fol- lowing a similar approach to (37] the inner product between two vectors with respect to their quantum representations can be estimate efficiently by introducing an auxiliary register. Specifically, estimation of the inner product h h can be performed by constructing the state v (Iu) (u (0)))) [bw)) + [u)[u') [1) b })). Applying Hadamard gate on the third register gives the
state [u)lu") (VPuw J0, ) ) + vI - Puwe [1, fuw')) where P.w 1+h h2 is the estimation of the inner product. This procedure takes (log d') time and denote this quantum operation by DO and we add a subscript to denote the corresponding conditioned operator, i.e, D uw represents DO is conditioned acting on the basis state coupled with state (0) + lu)lu"). We can perform the D in su- perposition such that the state Vin/ Σnev Evev [u)]ud)) (VPine J0, Juu') v1 -a-a Pan' [1, Faw)))
can be generated in time O(log(nd)).
Quantum aggregation transformation. Recall that an affine transformation (refer to Eq. 5 and Eq. 15 acting on the GNTK and its covariance relative to the neighborhood aggregation defined by Eq. Therefore, it is indirect to realize end-to-end speedup similar to the estimation of the inner

---

product since the transformation of each element of NTK and the covariance is not independent. To
circumvent this barrier, we derive a unitary quantum aggregation transformation approximately reconstruct the affine transformation. Consider the quantum operation Do |u) uu' [0) (0)
[u)lu") (VPaw |0, Iur') + v1 - Paa' [1, (une)) that is employed to estimate the inner product of two feature vectors. Define a unitary operator which is used to perform aggregation transformation
u
E E E
(u) (o') (ul (e") @ D
(17)
(EN(U))(M) ("E(("))(())
which can be generated by introducing conditional quantum evolution [22] The operation @ denotes the tensor product. We apply the U with Hadamard gates to the given initial state, which is given as
H 00 03
u
Σ 0yp0
l0, o²) 10/10)
+ H E
E
l0, (V Poe 10, Dov') + VI Por (1,
(18)
(E)(a)
Σ E
Vow 103 V= lohher) +...
(EN(u) ('E((N)U(a))
where v. (other) represents other computational basis states except for 10) with amplitude vs, and the detailed mathematical expression and the scalar for state normalization omitted since the result of the affine transformation has been embedded into the amplitude of [0) The (-)& denotes that there could be multiple unitary operations acting on multiple registers, depending the number of qubits required to encode the classic data. Similar to the inner product estimation, the quantum aggregation transformation can be performed in superposition and the resulting superposition is
Σ weV w'EV'
|u)lu') (VAuee 10, )ou') ) + /1 Aue [1, Baan')))
Vnn'
(19)
V EveN(w)u(u) EwENGHU(We VPe
|o|
The amplitude VAww can be encoded into an ancillary register by using Amplitude Es- timation (Theorem 3) and Median Evaluation (Theorem 4 The obtained quantum state Vnn? Evev Ev'vy' uu) [Aww')))) \BBwar) whose third register carries the approximate result after aggregation transformation described in Eq. 5 and Eq [15 where |Awu' - Awu'l S E and (yaur) is a garbage state. The runtime is (log(nd))ogl
and A is the proximity defined by the Median Evaluation. Note that A is actually the polynomial combination of the element wiiee square root of the NTK from the previous layer, thus it is an approximate aggregation transformation. In the experiment, we empirically show that this approximation has restrictive effect on the performance.
Quantum kernel estimation. For fully-connected neural network, the calculation of each ele- ment of the NTK and its covariance is only reliant on the element at the same position of the covariance matrix in the previous fully-connected layer. Besides, the affine transformation of the GNTK and its covariance can be efficiently approximated by quantum aggregation transforma- tion and the result has been embedded into the basis states of superposition. In general, there exits unitary V Σn Jx,0) 0) + En Ix, f()) for any classical function with the same time complexity to evaluate each element of the NTK and each element of the covariance [48] 71. Specifically, an oracle which operates as the same as classical function defined by Eq. g is im- plemented on the third register of 1 Σuev Evev- [u)]u")) A,w (Bww)) The resulting NTK is
Vani Vani Enev Ewev |u) (//w" @@ww)) (Bwwr) where @... is the approximate estimation of its classical counterpart after R fully-connected layers. The oracle is expected to be with the same complexity of its classical counterpart, which is associative to the number of fully-connected layers and independent on the number of training samples n. For estimation of the GNTK after transformer layer (Eq. 14). the covariance Σ/2 (G, G) for any G E & requires to be estimated in advance. means that the state 1 Emev Evev (u) (u') Eunr Bawn))lee (Bowr) must be estimated for any G(V, E) E before input the different graphs, and we only consider the element when u u'. By taking the partial trace on the second register, we obtain the state 1 Σnev (ui Eww) |Buu) for graph G and
Vn
7

---

L Ewev. | (wrr)buwrr) for graph G'. Thus, estimation of the GNTK and its covariance
vn corresponding to the multiplication part in Eq. 14 is given
Σ NEV Y'V
[u)lu')| W
Σ
|u)la')|@un' uw x Euu Bula))/uul
Vnn'
NEV W'EV'
[u)lu()| Eue x Dwr)
mm
BEV W'EV'
vnn
WEV W'EV'
(20)
This is performed by using the conditional quantum adder and the multiplier conditioned on the index register. i.c. (u) and In',, which are designed by [63] [54] 4T]. The final GNTK after the transformer layer can be directly generated by additional quantum arithmetic operations that perform an element-wise addition between the covariance to the GNTK.
Estimation the GNTK for multiple layers. The quantum aggregation transformation requires that the approximate NTK and its covariance are embedded into the amplitudes of a superposition. However, after the quantum kernel estimation, these matrix are embedded into the quantum basis states of superposition. To extract them back to the amplitudes, we apply Conditional Rotation (37 on the register containing the approximate GNTK (and the covariance), which is given by
Σ
Σ N'EV'
(u)lu') O un')
Σ
Σ
(u)lu')aaui [0) + v a [1)),
Vnn'
Vnn'
a'EV'
(21)
(u)lu') Emur)
Σ
lu))la")Our/110 (0) + / b2 [1)),
V nnn'
nnn
NEV N'ev'
NEV
N'eV'
where aue'
max _..)) and bun max.
We denote this quantum operation as
D', {I,...,,) L). where DL used for the quantum readout operation. Similar to the operation Do, the quantum aggregation transformation can be performed by generating a unitary operator by introducing conditional quantum evolution. Notice that Oun' and bua' can be viewed /Pw. in the setting of the single-layer GraphQNTK.
Quantum readout. The resulting NTK is embedded into the basis states of superposition since the algorithm ends up in the fully-connected layers. Similar to the classic readout operation, the summation of all the elements of the NTK matrix the L-th layer is required. We use Conditional Rotation to extract the NTK back to the amplitude, and define unitary O which is generalization of the unitary U. where
O= EEEX
Σ
(u) 10') (ul (6'l & D
(22)
VEV V'EV The unitary O sums the square root of all the elements of the GraphQNTK matrix. And the resulting GraphQNTK between two input graphs ① Euevva'vv v _ where O und nxn'
the GraphQNTK of the last layer.
Quantum inference to unseen data. We assume that the test data and the label of the training set already encoded into the QRAM such that kk)) RR,, the GraphQNTK between the test graph G*, can he evaluated as the same way to the evaluation between the training data. Let 2 E N
denote the GraphQNTK. The final prediction for test datapoint G. is
f'(G") = @
(23)
which requires solving the linear equation [E) = θ "y) and performing inner product estimation on (k, [E. A popular quantum algorithm which is designed to solve the quantum linear systems problem (QLSP) is developed by [13.. and its runtime is (log(N)) polylog (Rs/c)) where is the sparsity of matrix ② and is the condition number. To realize the quantum speedup, assume a specific sparsity pattern is created in the quantum storage that only keeps O(log N) number of non-zero elements of the N N GraphONTK matrix and the well-conditioning is achieved by using Gershgorin circle theorem similar to 711]
2.4 Complexity Study
In Sec. 2.3 we discuss how to approximately estimate GNTK using quantum computing paradigm between two input graphs. The time complexity dominated by the quantum aggregation trans- formation procedure it requires encoding the amplitude into an additional register, which takes
8

---

Table 1: Classification accuracies on graphs with discrete node attributes. The AttTntionGNTK denotes the GNTK with attention mechanism without both sparsity and well conditioning, while the GraphQNTK is the kemnl after performing these two transformations to meet the conditions for the use of quantum matrix inversion. The results of other models are taken from 17 except QS-CNN, which we evaluate on our dataset separation.
Dataset
MUTAG
PROTEINS
PTC
NCI1
IMDB-B
IMDB-M
WL subtree 57
90.4 = 5.7
7.10
59.9 + 4.3
86.0 = 1.8
73.8 3.9
AWL 30
87.9 9.8
51.5 5.9
RetGK 69
90.3 = 1.1
7.6
62.5 + 1.6
84.5 0.2
7199
47.7 0.3
GNTK 17
90.0 8.5
4.26
67.9 + 6.9
84.2 1.5
76.9 +.6 3.6
52.8 + 4.6
GCN 39
85.6 = 5.8
76.0
64.2 + 4.3
80.2 0.2::20 2.0
74.0 3.4
GraphSAGE 21
85.1 7.6
75.9 3.2
63.9 7.7
7..
72.3
50.9 2
PatchySAN 49
92.6 - 4.2
75.9
60.0 4.8
1.96
71.0 2.2
45.2
GIN 67
89.4 5.6
7.8
82.7 6.0
75.1 5.1
52.3 2.8
QS-CNN 70
93.1 4.7
78.2 + 4.6
66.0 4.4
2.,4
72.1 3.7
46.2 - 4.2
AttentionGNTK
90.0 = 8.5
76.2 + 3.8
66.2 + 5.1
84.1 1.2
76.9 + 3.2
52.9 = 3,5
GraphQNTK
88.4 6.5
71.1 + 3.2
62.9 + 5.0
77.2 = 2.7
73.3 + 3.6
48.1 + 4.3
(llo((nd)log(1/4) (/) time. Other quantum operations including estimation of the inner prod- uet, estimation of the GNTK within the neighborhood aggregation and the fully-connected feature updating and quantum readout are totally unitary operations which can be efficiently performed under the regime of quantum computing. For estimating GNTK of each pairs the graphs (G, G') where G, G' G. each element of GraphQNTK θ can be generated simultancously by introducing auxiliary index registers. The quantum runtime (log(Nnd)) However, evaluating GNTK the anfinite-width-ling attention requires computing the kernel where the input can be implemented time O(N). The result should be stored in QRAM advance which will be used update GNTK corresponding the multi-head attention described in Eq. [ Therefore, takes ( log( Nnd)) time to train the proposed quantum graph learning model, which achieves quadratic speedup compared the existing GKs and completed approaches with O(N2) time.
same graphs, which
Experiments
We evaluate our method for both GNTK and GraphQNTK with attention mechanism several graph classification datasets involving either discrete continuous attributes. All the experiments are performed on a workstation with single machine with 1TB memory, one physical CPU with 28 cores Intel(R) Xeon(R) W-3175X CPU @ 3.10GHz, and a single GPU (Nvidia Quadro RTX 8000). For our method and all the compared models, We follow the same setting [7 67]. and report the average test accuracy and standard deviation over 10-fold eross validation on each dataset.
3.1 Experiments Setup
Datasets. For graph with discrete attributes, the benchmark datasets include four bioinformatics datasets MUTAG, PTC, NCI1, PROTEINS and three social network datasets IMDB-BINARE IMDB- MULTI. For each graph, the input attributes is category of the node and they are transformed to one-hot encoding representations. For datasets where the graphs have node features, i.c. only graph structure matters, we use degrees as input node features. For graph with continuous attributes, we selcect four benchmark datasets including ENZYMES. PROTEINS full, BZR, COX2. All the datasets can be found in [38] The statistic information of the datasets are given in Tab. 3 Appendix.
Compared baselines. We compare our method with ofate-of-the-ar GKs such WL kernel [57]
AWL 330, RetGK (69]. GNTK [17, WWL 62). and GNNs including GCN [39] PatchySAN [49
GCKN [0). GraphSAGE 21 and GIN 67 For quantum graph learning, there are very few baseline
available. We report the performance of the quantum walk based subgraph convolutional neural
network (QS-CNN) developed by (70). The data separation use is the same (67] for graph

---

Table 2: Classification accuracies on graphs with continuous attributes. The accuracies of other models are taken from [Q]. We only take the results of GCKN under the supervised learning for a fail comparison. We utilize the similar settings that preprocess the continuous node features to normalized feature vector as in [62] for fair comparison (Note that the data encoded into the QRAM requires normalization, thus it is reasonable to use this data- prepossessing operation).
Dataset
ENZYMES
PROTEINS
BZR
COX2
RBF-WL WL 66
68.4 1.5
81.0 1.7 0.3
75.5 = 1.5 7
HGK-W WL
0.7
7..9
0.6
HGK-SP 47
6.4
7.2
7.74
72.6112
WWL 62
0.9
77.9 0.8
8..4+
78.3 19.3:00 0.5
GNTK 17
6.
75.7
0..5
79.6 0.4
GCKN 10
72.8 1.0
77.6 0.4
86.4
81.7 - 0.7
AttentionGNTK
69.2
76.8 + 1.2
86.7 + 1.3
82.1 = 0.4
GraphQNTK
6.7
72.5 0.3
80.1 + 1.7
74.3 1.9
datasets with discrete attributes. For graph dataset with continuous attributes, we follow the same protocol as used in 62 to normalize the input feature vectors for a fair comparison.
3.2 Experiment Results
We apply different
settings to E 4,,4,6,8 and E {1, (1) and select the model with the best averaged accuracy. We test the kernel regression using SVM classifier and the regularization parameter is determined using the search protocol which is the same as the (17]. We report the performance of the quantum approximate GNTK before and after the matrix sparsity and conditioning operations. The numerical results are listed in Tab. T for datasets with discrete attributes and Tab, 2 for datasets with continuous attributes. The attention method we integrate to the infinite-width GNNs brings to an improvement in the performance of the model. The results show that the GNTK with attention mechanism achieves better classification accuracy for graph data with medium number of nodes and edges. It is demonstrated that the infinite-width limit attention captures global node similarity semantics and learns effective structure of the provided graph. which brings an remarkable accuracy improvement of the model compared with the vanilla GNTK (17]. Moreover, our model performs better than QS- QS-CNN on more than 60% of the datasets with discrete attributes, given the caveat that QS-CNN is hybrid graph learning model where the contribution of the classic components (CNNs, spatial message passing) in their model cannot be ignored. While the matrix sparsity and conditioning operations have great influence on the model's performance, it can be found that the classification performance of GNTK evaluated by quantum algorithms still comparable with that of GKs and vanilla GNNs, where tradeoff exists between the performance of the model and the quantum computational efficiency.
4 Conclusion and Broader Impact
This paper has presented quantum graph learning model to characterize the structural information while using quantum parallelism to improve computing efficiency. We propose quantum algorithm to approximately estimate the neural tangent kernel of the underlying graph neural network where multi-head quantum attention mechanism is introduced to incorporate semantic similarity of nodes. Empirical results graph classification tasks well theoretical analysis show the superiority of our method. The limitation of the paper is that currently it only addresses graph-level embedding and we leave node-level quantum learning for future work. Our work may raise concerns for encryption, privacy protection etc. when the quantum hardware become more feasible.
Acknowledgement
This work was partly supported by National Key Research and Development Program of China A21000,0 National Natural Science Foundation of China (61972250, 7206 127003,,, and Shanghai Municipal Science and Technology (Major) Project (2021SHZDZX0102 2251 105 100).
10

---

References
[1] Xing Ai, Zhihong Zhang, Luzhe Sun, Junchi Yan, and Edwin Hancock. Decompositional quantum graph neural network. arXiv:2201 2000::20010005888 2022.
[2] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances in Neural Information Processing Systems, 32, 2019.
[3] Lu Bai, Luca Rossi, Andrea Torsello, and Edwin Hancock. A quantum jensen- shannon graph kernel for unattributed graphs. Pattern Recognition, 2015.
[4] Lu Bai, Luca Rossi, Lixin Cui, Zhihong Zhang, Peng Ren, Xiao Bai, and Edwin Hancock. Quan- tum kernels for unattributed graphs using discrete- time quantum walks. Pattern Recognition Letters, 2017.
[5] Lu Bai, Yuhang Jiao, Lixin Cui, Luca Rossi, Yue Wang, Philip Yu, and Edwin Hancock. Learning graph convolutional networks based on quantum vertex information propagation. IEEE Transactions on Knowledge and Data Engineering, 2021.
[6] Johannes Bausch. Recurrent quantum neural networks. Advances in Neural Information Processing Systems, 33: 366-1399,,, 2020.
[7] Kerstin Beer, Megha Khosla, Julius Köhler, and Tobias Osborne. Quantum machine learning of graph-structured data. urXiv:2103. 100.07,703 2021.
[8] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 2017.
[9] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53-74, 2002.
[10] Dexiong Chen, Laurent Jacob, and Julien Mairal. Convolutional kernel networks for graph- structured data. In International Conference on Machine Learning, pages 1576-1586. PMLR, 2020.
[11] Samuel Yen-Chi Chen, Tzu-Chieh Wei, Chao Zhang, Haiwang Yu, and Shinjae Yoo. Hybrid crantum-elassicee graph convolutional network. arXiv:2101.0m 1899 2021.
[12] Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. Advances in Neural Information Processing Systems, 33:19314-111 199266,,166 2020.
[13] Andrew M Childs, Robin Kothari, and Rolando D Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing, 16(6); 1950, 2017.
[14] Iris Cong, Soonwon Choi, and Mikhail D Lukin. Quantum convolutional neural networks. Nature Physics, 2019.
[15] Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and dual view on expressivity, Advances In Neural Information Processing Systems, 29, 2016.
[16] Stefan Dernbach, Arman Mohseni-Kabir Siddharth Pal, and Don Towsley. Quantum walk neural networks for graph-structue data. In Complex Networks and Their Applications, 2018.
[17] Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. Advances in Neural Information Processing Systems, 32, 2019.
[18] Jinyuan Fang, Shangsong Liang. Zaiqiao Meng, and Qiang Zhang. Gaussian process with graph convolutional kernel for relational learning. In Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, pages 353-363, 2021.
11

---

[19] Tulia Georgescu. Quantum enhancement in generative models. Nature Reviews Physics, 4(6): 362-362, 2022.
[20] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference machine learning. pages
PMLR, 2017.
[21] Will Hamilton, Zhitao Ying, and Jure Leskovec, Inductive representation learning on large graphs. Advances in Neural Information Processing Systems, 30, 2017.
[22] Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters, 2009.
[23] David Haussler. Convolution kernels discrete structures. Technical report, Department of Computer Science, University of California, 1999.
[24] Vojtëch Havlíčck, Antonio D Córcoles, Kristan Temme, Aram W Harrow, Abhinav Kandala, Jerry M Chow, and Jay M Gambetta. Supervised learning with quantum -enanced feature spaces. Nature, 567(7747):20--21,, 2019.
[25] Louis-Paul Henry, Slimane Thabet, Constantin Dalyac, and Loic Henriet. Quantum evolution kernel: Machine learning on graphs with programmable arrays of qubits. Physical Review A, 2021.
[26] Jiri Hron, Yasaman Bahri, Jascha Sohl-Dickstein, and Roman Novak. Infinite attention: Nngp and ntk for deep attention networks. In International Conference on Machine Learning, pages 4376 4386. PMLR, 2020.
[27] Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogeneous graph transformer. In Proceedings of The Web Conference 2020, pages 2704-2710, 2020.
[28] HisinYYuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hart- mut Neven, and Jarrod R McClean. Power of data in quantum machine learning. Nature communications, 12(1): 1-9, 2021.
[29] Wei Huang, Yayong Li, weitao Du, Richard Xu, Jie Yin, Ling Chen, and Miao Zhang. Towards deepening graph neural networks: A GNTK- based optimization perspective. In International Conference on Learning Representations, 2022.
[30] Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In International confereennnnnccconcnncccc on machine learning, pages 21 2186-22 2195. PMLR, 2018
[31] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[32] Ashish Kapoor, Nathan Wiebe, and Krysta Svore. Quantum perceptron models. Advances in neural information processing systems, 29, 2016.
[33] Julia Kempe. Quantum random walks: an introductory overview. Contemporary Physics, 2003.
[34] Iordanis Kerenidis and Jonas Landman. Quantum spectral clustering. Physical Review A, 103 (4):042415, 2021.
[35] Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Schloss Dagstuhl-Lcibniz-Zettrum fuer Informatik, 2017.
[36] Iordanis Kerenidis. Jonas Landman, Alessandro Luongo, and Anupam Prakash. q-means:
A quantum algorithm for unsupervised machine learning. Advances in Neural Information Processing Systems. 32, 2019.
[37] Iordanis Kerenidis, Jonas Landman, and Anupam Prakash. Quantum algorithms for deep convolutional neural networks. In International Conference on Learning Representations, 2020.
12

---

[38] Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neu- mann. Benchmark data sets for graph kernels, 2016. URL http://graphierrelss.ooo
tu fuu-dormuudd.. de
[39] Thomas N. Kipf and Max Welling. Semi- Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017.
[40] Tao Lei, Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Deriving neural architectures from sequence and graph kernels. In International Conference on Machine Learning pages 2024-2033 PMLR, 2017.
[41] Hai-Sheng Li, Ping Fan, Haiying Xia, Huiling Peng, and Gui-Lu Long. Efficient quantum arith- metic operation circuits for quantum image processing. SCIENCE CHINA Physics, Mechanics Astronomy, 6388):1-33, 2020.
[42] Junyu Liu, Francesco Tacchino, Jennifer Glick, Liang Jiang, and Antonio Mezzacapo. Rep- resentation learning via quantum neural tangent kernels. arXiv preprint arXiv:2 2021.
[43] Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme, A rigorous and robust quantum speed-up in supervised machine learning. Nature Physics, 2021.
[44] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum algorithms for supervised and unsupervised machine learning. arXiv preprint arXiv: 30..011 2013.
[45] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, (0(9):631-333 2014.
[46] Péter Mernyei, Konstantinos Meichanetzidis, and Ismail Ilkan Ceylan. Equivariant quantum graph cireuits. In International Conference on Machine Learning, pages 15401-15420. PMLR, 2022.
[47] Christopher Morris, Nils M Kriege, Kristian Kersting, and Petra Mutzel. Faster kernels for graphs with continuous attributes via hashing. 2016 IEEE 16th International Conference on Data Mining (ICDM), pages 1095-1 1000. IEEE, 2016.
[48] Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.
[49] Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. International conference on machine learning, pages 2014-2023. PMLR, 2016.
[50] Giannis Nikolentzos, Polykarpos Meladianos, Antoine J-P Tixier, Konstantinos Skianis, and Michalis Vazirgiannis. Kernel graph convolutional neural nets, 2018.
[51] Roman Novak, Lechao Xiao, Yasaman Bahri, Jaehoon Lee, Greg Yang, Daniel A. Abolafia, Jeffrey Pennington, and Jascha Sohl-dickstein. Bayesian deep convolutional networks with many channels are gaussian processes. In International Conference on Learning Representations, 2019.
[52] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Physical review letters, 2014.
[53] Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Self-supervised graph transformer on large-scale molecular data. Advances in Neural Information Processing Systems, 33: 12559- 2020.
[54] Lidia Ruiz-Perez and Juan Carlos Carcia-Escartts Quantum arithmetic with the quantum fourier transform. Quantum Information Processing, 16(6):1-14, 2017.
[55] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. An introduction to quantum machine learning. Contemporary Physics, 56(2):172-185, 2015.
[56) Maria Schuld, Kamil Brádler, Robert Israel, Daiqin Su, and Brajesh Gupt. Measuring the similarity of graphs with gaussian boson sampler. Physical Review A, 2020.
13

---

[57] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9). 2011.
[58] Kazuya Shimizu and Ryuhei Mori. Exponential-imme quantum algorithms for graph coloring problems. Latin American Symposium on Theoretical Informatics, pages 387-398. Springer, 2021.
[59] Norihito Shirai, Kenji Kubo, Kosuke Mitarai, and Keisuke Fujii. Quantum tangent kernel. arXiv preprint arXiv:2111.02955 2021.
[60] Francesco Tacchino, Chiara Macchiavello, Dario Gerace, and Daniele Bajoni. An artificial neuron implemented on actual quantum processor. upj Quantum Information, 5(1):1-8, 2019.
[61] Yehui Tang, Junchi Yan, and Hancock Edwin. From quantum graph computing to quantum graph learning: A survey. arXiv preprint arXiv:2202.09500 2022.
[62] Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares-López, Bastian Rieck, and Karsten Borg- wardt. Wasserstein weisfeiler-lehman graph kernels. Advances in Neural Information Processing Systems, 32, 2019.
[63] Vlatko Vedral, Adriano Barenco, and Artur Ekert. Quantum networks for elementary arithmetic operations. Physical Review A, 54(1):147, 1996.
[64] Guillaume Verdon, Trevor McCourt, Enxhell Luzhnica, Vikash Singh, Stefan Leichenauer, and Jack Hidary. Quantum graph neural networks. arXiv:1909. 2019.
[65] Nathan Wiebe, Ashish Kapoor, and Krysta M Svore. Quantum algorithms for nearest-neighhor methods for supervised and unsupervised learning. Quantum Information Computation, 15 (3-4):316-356, 2015.
[66] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1 ):4 24, 2020.
[67] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
[68] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34, 2021.
[69] Zhen Zhang, Mianzhi Wang, Yijian Xiang, Yan Huang, and Arye Nehorai. Retgk: Graph kernels based on return probabilities of random walks. Advances in Neural Information Processing Systems, 31, 2018
[70] Zhihong Zhang, Dongdong Chen, Jianjia Wang, Lu Bai, and Edwin R Hancock. Quantum-based subgraph convolutional neural networks. Pattern Recognition, 2019.
[71] Alexander Zlokapa, Hartmut Neven, and Seth Lloyd. A quantum algorithm for training wide and deep classical neural networks. arXiv:2107.099000 09200, 2021.
14

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], , or [N/A] - You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below,
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "v8yaYFh1V2F", "reviewer": "Reviewer_4zaS", "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.\n\nTo 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. \n\nExperiments show the proposed quantum model performs competitively against both GNNs and the GKs, and theoretical analysis explains the speedup benefited from quantum algorithms.\n", "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?\n\n2. In the experiment, the performance of GraphQNTK is significantly weaker than that of AttentionGNTK. Could you explain this phenomenon?\n\n3. 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. \n", "limitations": "Please see my questions.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ This work is clearly motivated and well written\nThe background of the research, the motivation of quantum graph learning for graph classification and the related work are all clearly stated and summarized.\n+ The first for introducing attention mechanism in quantum graph learning\nThe 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.\n+ Quantum speedup for improved GNTK  \nTo 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.\n+ Extensive numerical evaluation\nThis 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. \n\nWeaknesses:\n- 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. \n- 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.\n\nOverall, 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SpR14dzzMt", "reviewer": "Reviewer_7X59", "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.", "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.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. With the attention mechanism, the proposed quantum graph learning model is better at capturing global information of the graph.\n2. 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)$.\n\nWeaknesses:\n\n1. From the reported results, the performance of the proposed GraphQNTK is not competitive compared to the baselines. \n2. 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2wa6yyqsZ-", "reviewer": "Reviewer_DbrA", "summary": "The authors propose a Quantum Neural Tangent Kernels (QNTK) approach for GNNs.\nThe 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.\nThe 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.\n\nThe 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.", "questions": "1. Please clarify what do you mean by infinite width of GNNs, and what is the actual width of GNNs.\n2.Please demonstrate your method with more layers.\n3.Please provide runtimes for your method and compare it to other methods.\n4.Can you please explain why your method is not working on node classification?", "limitations": "The authors discussed potential negative societal impact adequately .", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.The authors propose a method that involves quantum computing and GNNs, a subject that is relatively new and less researched.\n2.The proposed method is claimed to accelerate GNNs - this is a major point in the field of GNNs.\n\nWeaknesses:\n1. 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)). \n\n2.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.\n\n3.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.\n\n4.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.\n\n5.Figure 1 is not self contained and also not explained in text properly. It is not clear what 'SVC' and 'SVR' means. \n\n6.Line 108 is not clear. The authors need to define what k* means. What is x* ?\n\n7.The experimental results show inferior results compared to the considered methods. \n\n8.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.\n\n9.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.\n\n10.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?\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept