A Quantum Spatial Graph Convolutional Neural Network using Quantum Passing Information

Lu Bai, Yuhang Jiao, Luca Rossi, Lixin Cui, Jian Cheng, Edwin R. Hancock

Abstract

This paper proposes a new Quantum Spatial Graph Convolutional Neural Network (QSGCNN) model that can directly learn a classification function for graphs of arbitrary sizes. Unlike state-of-the-art Graph Convolutional Neural Network (GCNN) models, the proposed QSGCNN model incorporates the process of identifying transitive aligned vertices between graphs, and transforms arbitrary sized graphs into fixed-sized aligned vertex grid structures. In order to learn representative graph characteristics, a new quantum spatial graph convolution is proposed and employed to extract multi-scale vertex features, in terms of quantum information propagation between grid vertices of each graph. Since the quantum spatial convolution preserves the grid structures of the input vertices, the proposed QSGCNN model allows to directly employ the traditional convolutional neural network architecture to further learn from the global graph topology, providing an end-to-end deep learning architecture that integrates the graph representation and learning in the quantum spatial graph convolution layer and the traditional convolutional layer for graph classifications.

Introduction

Standard Convolutional Neural Networks (CNNs) are designed for regular grids, like pixels in an image. Graphs, however, are irregular: they have varying numbers of vertices and no natural "order." Existing Graph Convolutional Networks (GCNNs) usually tackle this through spectral methods or spatial methods using pooling layers (like SortPooling or SumPooling) to create fixed-size representations.

However, these pooling methods often lead to significant information loss by discarding lower-ranked vertices or blurring local structural details. Furthermore, most models fail to maintain "transitive alignment"—ensuring consistent vertex mapping across a dataset. The proposed Quantum Spatial Graph Convolutional Neural Network (QSGCNN) solves this irregularity problem by transitively aligning vertices into fixed-size grids and leveraging the unique propagation properties of continuous-time quantum walks.

Methodology

The QSGCNN architecture consists of three innovative stages integrated into an end-to-end pipeline:

1. Transitive Alignment & Grid Construction

Instead of simply sorting vertices by degree, the model uses k-means clustering on depth-based vertex representations to identify "prototype" vertices across the entire dataset. Every graph is then mapped onto a fixed-size grid based on these prototypes. This ensures that the $i$-th row in the feature matrix of Graph A represents the same structural "role" as the $i$-th row in Graph B, establishing a common coordinate system.

Detailed process of computing K-dimensional DB representations, prototype representations, and the K-level correspondence matrix for transitive alignment.

2. Quantum Spatial Graph Convolution

To propagate information between these aligned vertices, the model employs continuous-time quantum walks, specifically using the average mixing matrix ($Q$). Unlike classical random walks, quantum walks are non-ergodic and do not suffer from the "tottering" problem (redundant back-and-forth movement on an edge). This allows the model to better distinguish complex graph topologies and extract multi-scale vertex features while preserving the grid structure.

3. Traditional CNN Integration

Because the previous steps transform the graph into a consistent, fixed-size grid, the model can directly apply standard 1D-CNN layers. This allows the use of well-established deep learning techniques, such as Max-Pooling and Dense layers, to learn global graph characteristics from the quantum-processed features.

The three-stage architecture of QSGCNN: Grid Structure Layer, Graph Convolution Layer, and Classical 1D-CNN Layer.

Experimental Results

The model was evaluated on nine benchmark datasets, including bioinformatics (MUTAG, NCI1, PROTEINS) and social networks (COLLAB, IMDB, REDDIT-BINARY).

  • Accuracy: On the MUTAG dataset, QSGCNN achieved 90.52% accuracy, significantly higher than DGCNN (85.83%) and PSGCNN (88.95%).
  • Social Graphs: It outperformed state-of-the-art graph kernels on the REDDIT-BINARY dataset, reaching 91.50% accuracy.
  • Consistency: Unlike many GNNs that specialize in one domain, QSGCNN remained competitive across both biological and social datasets, proving the robustness of the quantum-spatial approach.

Discussion and Conclusion

The QSGCNN model successfully bridges the gap between irregular graph structures and standard deep learning architectures. By treating centroids of vertex embeddings as "prototypes," the researchers created a common coordinate system for all graphs, effectively "flattening" diverse topologies into a format a standard CNN can understand.

While the current alignment process is transductive (requiring a view of the dataset to define prototypes), the results demonstrate a significant advancement. Future directions include extending this work to edge-based grid structures and exploring directed line graphs to better capture edge information.

Summary updated

Abstract

This paper proposes a new Quantum Spatial Graph Convolutional Neural Network (QSGCNN) model that can directly learn a classification function for graphs of arbitrary sizes. Unlike state-of-the-art Graph Convolutional Neural Network (GCNN) models, the proposed QSGCNN model incorporates the process of identifying transitive aligned vertices between graphs, and transforms arbitrary sized graphs into fixed-sized aligned vertex grid structures. In order to learn representative graph characteristics, a new quantum spatial graph convolution is proposed and employed to extract multi-scale vertex features, in terms of quantum information propagation between grid vertices of each graph. Since the quantum spatial convolution preserves the grid structures of the input vertices (i.e., the convolution layer does not change the original spatial sequence of vertices), the proposed QSGCNN model allows to directly employ the traditional convolutional neural network architecture to further learn from the global graph topology, providing an end-to-end deep learning architecture that integrates the graph representation and learning in the quantum spatial graph convolution layer and the traditional convolutional layer for graph classifications. We demonstrate the effectiveness of the proposed QSGCNN model in relation to existing state-of-the-art methods. The proposed QSGCNN model addresses the shortcomings of information loss and imprecise information representation arising in existing GCN models associated with the use of SortPooling or SumPooling layers. Experiments on benchmark graph classification datasets demonstrate the effectiveness of the proposed QSGCNN model.
BibTeX
@article{bai2023quantum,
  author = {Lu Bai and Yuhang Jiao and Luca Rossi and Lixin Cui and Jian Cheng and Edwin R. Hancock},
  title = {{A Quantum Spatial Graph Convolutional Neural Network using Quantum Passing Information}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2023},
  doi = {10.1109/tkde.2021.3106804},
}
Figure