GraphQNTK: Quantum Neural Tangent Kernel for Graph Data

Yehui Tang, Junchi YanNeurIPS 2022 · OpenReview

TL;DR

GraphQNTK is a novel framework that combines the expressive power of Graph Neural Networks (GNNs) with the theoretical transparency of Graph Kernels, accelerated by quantum computing. By introducing an infinite-width multi-head attention mechanism and leveraging quantum parallelism, the authors achieve a quadratic speedup in training efficiency while maintaining competitive performance on graph classification tasks.

The Challenge: Expressivity vs. Transparency

In the world of graph data, researchers usually choose between two paths: Graph Neural Networks (GNNs), which are highly expressive but difficult to analyze (the "black box" problem), and Graph Kernels (GKs), which are mathematically transparent but often less powerful.

A middle ground exists called the Graph Neural Tangent Kernel (GNTK). It describes how an infinitely wide GNN behaves during training, essentially turning a deep learning problem into a kernel regression problem. However, GNTKs face two major hurdles:

  1. Computational Cost: Calculating the kernel matrix for $N$ graphs scales at $O(N^2)$, making it prohibitively slow for large datasets.
  2. Information Loss: Standard GNTKs use simple neighborhood aggregation that often ignores "global" similarities between nodes that aren't directly connected.

Methods: The GraphQNTK Framework

To tackle these issues, the authors propose GraphQNTK, a two-pronged approach that enhances the classical GNTK with attention and accelerates its computation using quantum algorithms.

General Quantum Graph Learning Pipeline

1. Attention-Enhanced GNTK (Classical Innovation)

The authors integrate a multi-head attention mechanism into the GNTK framework. By taking the limit where the number of attention heads and the hidden layer width go to infinity, the attention mechanism becomes a deterministic mathematical transformation. This allows the model to incorporate "semantic similarity"—recognizing that two nodes might be similar because of their features, even if they are far apart in the graph.

Mapping GNNs to Infinite-Width GNTK

2. Quantum Acceleration (Quantum Innovation)

To solve the $O(N^2)$ bottleneck, the authors re-design the GNTK estimation as a quantum algorithm:

  • Feature Encoding: Node attributes are loaded into a Quantum Random Access Memory (QRAM).
  • Quantum Aggregation: They derive a novel unitary transformation to approximate the neighborhood aggregation step in superposition.
  • Quantum Kernel Estimation: By using quantum parallelism, the algorithm estimates the inner products required for the kernel matrix much faster than a classical computer.
  • Linear System Solver: They use quantum linear algebra subroutines (similar to the HHL algorithm) to solve the final prediction equation.

The Result: The theoretical complexity drops from $O(N^2)$ to $O(N)$, a significant quadratic speedup.

Datasets and Key Results

The model was evaluated on several standard graph classification benchmarks, including bioinformatics (MUTAG, PROTEINS, PTC, NCI1), social networks (IMDB-BINARY, IMDB-MULTI), and continuous attribute datasets (ENZYMES, BZR, COX2).

  • Accuracy: The classical version (AttentionGNTK) outperformed vanilla GNTK and several popular GNNs (like GCN and GIN) on social network datasets.
  • Quantum Robustness: The quantum version (GraphQNTK), which includes necessary approximations for quantum hardware, achieved results comparable to state-of-the-art classical graph kernels.
  • Efficiency: The authors provide theoretical proof that their quantum algorithm reduces the computational complexity of training from $O(N^2)$ to $O(N)$, provided the data is stored in QRAM.

Key Insights and Limitations

  • The Power of Infinity: By assuming an "infinite" model, the complex dynamics of training a neural network collapse into a static kernel, which is much easier for a quantum computer to process.
  • Global vs. Local: Adding infinite-width attention gives GraphQNTK a "global" view, allowing it to capture patterns that standard local GNTKs miss.
  • Hardware Requirements: Like most advanced quantum machine learning papers, this requires fault-tolerant quantum computers and QRAM, neither of which are currently available at the necessary scale.
  • Approximation Impact: While the quantum approximations (sparsity and conditioning) allow for speedups, they lead to a slight dip in accuracy compared to the full classical attention model. Finding ways to minimize this "approximation gap" remains an open challenge.

Summary updated

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}.
BibTeX
@inproceedings{tang2022graphqntk,
  author = {Yehui Tang and Junchi Yan},
  title = {{GraphQNTK: Quantum Neural Tangent Kernel for Graph Data}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=SwFFRX7arQ0},
}
Figure