An R-Convolution Graph Kernel Based on Fast Discrete-Time Quantum Walk.

Area of Science:

• Graph theory
• Quantum computing
• Machine learning

Background:

• Graph kernels are essential for machine learning on graph-structured data.
• Existing methods struggle with unattributed graphs and distinguishing complex graph families.
• Quantum walks offer a novel approach to capture graph structural information.

Purpose of the Study:

• To introduce a novel R-convolution kernel, the fast quantum walk kernel (FQWK), for unattributed graphs.
• To enhance the accuracy and efficiency of graph classification.
• To enable the distinction of complex graph families often indistinguishable by classical methods.

Main Methods:

• Developed the fast quantum walk kernel (FQWK) utilizing neighborhood-pair substructure similarity.
• Employed superposition amplitude of quantum walks to measure node similarity.
• Designed a fast recursive method for efficient computation of multistep discrete-time quantum walk transition amplitudes.
• Leveraged quantum interference for capturing finer-grained local graph structural features.

Main Results:

• FQWK demonstrates superior computation speed compared to existing quantum walk kernels.
• Extensive experiments show FQWK outperforms state-of-the-art graph kernels in classification accuracy for unattributed graphs.
• FQWK successfully distinguishes cospectral, regular, and strong regular graphs.

Conclusions:

• FQWK is an efficient and accurate graph kernel for unattributed graph classification.
• The method effectively captures subtle local graph structures missed by classical approaches.
• FQWK expands the applicability of graph kernels to more complex graph families.