Learning structural balance of graphs from quantum spectral features
Abstract
We develop a quantum approach to spectral feature extraction from the density of states (DOS) of a problem-dependent Hamiltonian, and apply it to machine learning on signed graphs. We propose to embed a signed graph as an Ising model instance with positive and negative interactions, and use the standardized moments of the Ising DOS as features for learning. We show that these moments count signed closed walks, are switching-invariant, and are size-free by construction. As a benchmark, we target learning the frustration index, an NP-hard measure of structural balance that can be labeled exactly at moderate size. At zero field, the models can be sampled classically, allowing the quantum extraction procedure to be certified against exact ground truth. We propose DOS-QPE, a phase estimation on a purified maximally mixed probe, which samples the spectral density with orders of magnitude fewer shots than Hadamard test-based trace sampling and feeds the resulting features directly into classically trained models. On 1.4×105 labeled graphs the exact DOS determines the frustration index, and five moments recover it with a mean error of 0.4, well below one sign flip. Beyond zero field, the underlying trace-estimation problem is DQC1-complete, providing access to spectral features for which no efficient classical sampling method is known. Our work opens routes towards quantum applications in social network balance analysis, spin-glass studies, correlation clustering, and protein-interaction networks.
Related
- A Quantum-Inspired Dequantization Method for Diagonally Weighted Matrix Functions: Application to Learning with Optimized Random Features
- Quantum spectral thermodynamics and active learning enable million-scale exploration of high-entropy ceramics
- Spectral Geometry and Bosonic-Bloch Probes: Explorations in Quantum Learning
- Spectral theory of large data with power-law latent features
- Separating Field--Camp Alignment from Structural Balance in a Frustrated Random-Field Ising Model of Social Networks
BibTeX
@misc{scali2026learning,
title = {{Learning structural balance of graphs from quantum spectral features}},
author = {Stefano Scali and Oleksandr Kyriienko},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11736},
eprint = {2609.11736},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11736},
}
RIS
TY - UNPB
TI - Learning structural balance of graphs from quantum spectral features
AU - Stefano Scali
AU - Oleksandr Kyriienko
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11736
UR - https://arxiv.org/abs/2609.11736
AB - We develop a quantum approach to spectral feature extraction from the density of states (DOS) of a problem-dependent Hamiltonian, and apply it to machine learning on signed graphs. We propose to embed a signed graph as an Ising model instance with positive and negative interactions, and use the standardized moments of the Ising DOS as features for learning. We show that these moments count signed closed walks, are switching-invariant, and are size-free by construction. As a benchmark, we target learning the frustration index, an NP-hard measure of structural balance that can be labeled exactly at moderate size. At zero field, the models can be sampled classically, allowing the quantum extraction procedure to be certified against exact ground truth. We propose DOS-QPE, a phase estimation on a purified maximally mixed probe, which samples the spectral density with orders of magnitude fewer shots than Hadamard test-based trace sampling and feeds the resulting features directly into classically trained models. On 1.4×10^5 labeled graphs the exact DOS determines the frustration index, and five moments recover it with a mean error of 0.4, well below one sign flip. Beyond zero field, the underlying trace-estimation problem is DQC1-complete, providing access to spectral features for which no efficient classical sampling method is known. Our work opens routes towards quantum applications in social network balance analysis, spin-glass studies, correlation clustering, and protein-interaction networks.
ER -