Learning structural balance of graphs from quantum spectral features
A quantum spectral feature method recovered a hard graph-balance measure from just five density-of-states moments.
The paper embeds signed graphs as Ising model instances and uses standardized moments of the Ising density of states as learning features. Those moments count signed closed walks, remain switching-invariant, and avoid graph-size dependence by construction. As a benchmark, the authors learn the frustration index, an NP-hard measure of structural balance, using 140,000 labeled graphs. They report mean error of 0.4 from five moments, and propose a DOS-QPE procedure that samples spectral density with far fewer shots than Hadamard-test trace sampling. ArXiv · AI/CL/LG's note
The paper embeds signed graphs as Ising model instances and uses standardized moments of the Ising density of states as learning features. Those moments count signed closed walks, remain switching-invariant, and avoid graph-size dependence by construction. As a benchmark, the authors learn the frustration index, an NP-hard measure of structural balance, using 140,000 labeled graphs. They report mean error of 0.4 from five moments, and propose a DOS-QPE procedure that samples spectral density with far fewer shots than Hadamard-test trace sampling. ArXiv · AI/CL/LG's note
score 4