Research map / Graph learning / Graph algorithms and clustering
QBMK: Quantum-based Matching Kernels for Un-attributed Graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes QBMK, a graph kernel for un-attributed graphs that matches aligned vertices across graphs and compares their CTQW-based quantum Shannon entropies, evaluated with C-SVM classification on ten benchmark datasets.
Problem
Existing graph kernels either ignore structural correspondence between graphs (R-convolution kernels), ignore local or global structure, or treat all aligned vertex pairs equally (vertex-based matching kernels), limiting classification accuracy on un-attributed graphs.
Approach
Compute a quantum Shannon entropy per vertex from the time-averaged CTQW average mixing matrix, align vertices across graphs over multiple depth-based levels, and sum a reproducing-kernel similarity between the entropies of aligned pairs, so that aligned pairs contribute differently depending on their structural differences.
Key results
- QBMK reaches 88.55% on MUTAG and 84.47% on PPIs, and outperforms all compared graph kernels on seven of ten datasets (per the paper).
- On the deep-learning comparison, QBMK (77.60% on D&D, 59.38% on PTC) outperforms most deep learning baselines on two of three datasets, but is not best on D&D.
- The paper reports QBMK is not the best on D&D, PTC and PPIs, but remains competitive.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use QBMK instead of EDBMK | Graph classification with C-SVM · MUTAG | accuracy: 86.35 -> 88.55 ± .43 | Helped |
| Use QBMK instead of JTQK | Graph classification with C-SVM · D&D | accuracy: 79.89 ± .32 -> 77.60 ± .47 | Hurt |
| Use QBMK instead of ISK | Graph classification with C-SVM · PTC | accuracy: 60.26 ± .42 -> 59.38 ± .36 | Hurt |
| Use QBMK instead of JTQK | Graph classification with C-SVM · PPIs | accuracy: 88.47 ± .47 -> 84.47 ± .56 | Hurt |
| Use QBMK instead of SPGK | Graph classification with C-SVM · CATH2 | accuracy: 81.89 ± .63 -> 84.36 ± .65 | Helped |
| Use QBMK instead of EDBMK | Graph classification with C-SVM · BAR31 | accuracy: 70.08 -> 73.66 ± .57 | Helped |
| Use QBMK instead of EDBMK | Graph classification with C-SVM · BSPHERE31 | accuracy: 57.36 -> 62.63 ± .41 | Helped |
| Use QBMK instead of EDBMK | Graph classification with C-SVM · GEOD31 | accuracy: 43.57 -> 47.63 ± .45 | Helped |
| Use QBMK instead of QJSK | Graph classification with C-SVM · Shock | accuracy: 40.60 ± .92 -> 46.26 ± .74 | Helped |
| Use QBMK instead of EDBMK | Graph classification with C-SVM · GatorBait | accuracy: 14.40 -> 15.00 ± .89 | Helped |
| Use QBMK instead of DGCNN | Graph classification · MUTAG | accuracy: 85.83 ± 1.66 -> 88.55 ± .43 | Helped |
| Use QBMK instead of DGCNN | Graph classification · D&D | accuracy: 79.37 ± 0.94 -> 77.60 ± .47 | Hurt |
Surprising findings
- The kernel is not guaranteed positive definite since transitive vertex alignment is not ensured, yet the authors report strong empirical performance.
Limitations
- Kernel is not guaranteed positive definite or transitive in vertex alignment.
- Not the best on D&D, PTC and PPIs datasets.
- Baseline results were copied from original literatures rather than re-run under identical setup.
Experimental setup
Datasets: MUTAG D&D PTC PPIs CATH2 BAR31 BSPHERE31 GEOD31 Shock GatorBait
Benchmarks: MUTAG D&D PTC PPIs CATH2 BAR31 BSPHERE31 GEOD31 Shock GatorBait
Metrics: classification accuracy
Baselines: QJSK JTQK GCGK WLSK SPGK EDBMK DBMK JSSK ISK EigenPool DEMO-Net DGK
Builds on: Depth-based Matching Kernel Quantum Jensen-Shannon Kernel Basic Reproducing Kernel (Xu et al., 2018) Average Mixing Matrix of CTQW
Closest papers by meaning
- GraphQNTK: Quantum Neural Tangent Kernel for Graph Data (NeurIPS 2022 · similarity 0.87)
- KerGM: Kernelized Graph Matching (NeurIPS 2019 · similarity 0.85)
- Equivariant Quantum Graph Circuits (ICML 2022 · similarity 0.84)
- Quantum Positional Encodings for Graph Neural Networks (ICML 2024 · similarity 0.83)
- Optimal algorithmic complexity of inference in quantum kernel methods (NeurIPS 2026 · similarity 0.83)
- Quantum Speedup for Hypergraph Sparsification (ICML 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.