Quantum method extracts graph balance features from spectral data
Learning structural balance of graphs from quantum spectral features
Machine LearningSocial and Information Networks
Summary
Understanding the balance of relationships in networks with positive and negative ties is hard to measure, especially for large or complicated graphs. This paper shows how quantum computing can be used to analyze patterns in these networks by representing them as physical models and extracting key features from their spectra. The authors introduce a quantum algorithm that efficiently captures these features and helps predict an important measure called the frustration index, which reflects how balanced or conflicted the network is. Their approach works well even for complex cases where classical methods struggle.
What this means in practice
- •For social network analysts: Identify and quantify conflict patterns in signed social networks by using quantum-extracted spectral features to measure structural balance more effectively.
- •For computational biologists: Use quantum spectral data features to improve analysis of protein-interaction networks that contain mixed positive and negative interactions.
Authors
Stefano Scali, Oleksandr Kyriienko
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\times10^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.