PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning structural balance of graphs from quantum spectral features

Stefano Scali, Oleksandr Kyriienko

arXiv:2609.11736v1quant-phcond-mat.dis-nncs.LGcs.SI

TL;DR

The paper addresses learning structural balance in signed graphs using quantum spectral features from problem-dependent Ising Hamiltonians. It introduces DOS-QPE and finds that exact DOS determines the frustration index across 1.4 × 10^5 graphs, while five moments achieve a mean error of 0.4 sign flips.

  • Problem

    The frustration index measures signed-graph distance from balance but is NP-hard to compute, motivating learnable spectral representations for moderate instances.

  • Method

    Signed graphs are encoded as Ising Hamiltonians, whose standardized DOS moments count signed closed walks and remain switching-invariant; DOS-QPE samples the spectral density directly.

  • Results

    Across 1.4 × 10^5 labeled graphs, the exact DOS determines the frustration index, while five DOS moments recover it with a mean error of 0.4 sign flips.

  • Takeaways & Limitations

    The framework connects quantum spectral estimation with classical learning without requiring the quantum device to solve the underlying combinatorial optimization problem.

  • Takeaways & Limitations

    Retaining higher moments requires progressively larger registers, and their added accuracy becomes harder to retain as graph size grows.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper develops DOS-based spectral features for signed-graph learning by encoding graphs as Ising Hamiltonians. It benchmarks these features on exactly labeled frustration-index prediction and introduces quantum extraction routes, including DOS-QPE.

  • Signed-graph spectra provide permutation-invariant features for systems with antagonistic relations, including social networks, financial correlations, and spin glasses.The frustration index measures the minimum number of sign flips needed to reach balance and is NP-hard to compute.
  • Across 1.4 × 105 exactly labeled graphs, the exact DOS determines the frustration index, while five moments recover it with mean absolute error below 0.4 sign flips at n = 12.Edge and triangle counting incurs twice the error on the same splits.
  • The approach embeds each signed graph as an Ising Hamiltonian and uses standardized DOS moments as size-free, switching-invariant learning features.The moments count signed closed walks through an exact combinatorial identity.
  • DOS-QPE applies phase estimation to a purified maximally mixed probe so each shot samples directly from the spectral density.The alternative quantum route estimates the trace of time evolution through Hadamard tests.
  • At zero field, classical sampling enables certification of the quantum feature-extraction procedures against exact ground truth.For general dynamics, normalized-trace estimation is DQC1-complete and is believed to be classically intractable.

II. SPECTRAL FEATURES FROM THE DENSITY OF STATES

The DOS is a normalized spectral probability density whose Fourier transform is the normalized trace of time evolution. The method compresses this density into five standardized moments that retain combinatorial information while remaining dimensionless and size-free.

  • The DOS is a normalized sum of delta functions over Hamiltonian eigenvalues, and its Fourier transform is the normalized trace of time evolution.Estimating the trace over time and inverting the transform recovers the DOS.
  • Raw energy moments expand into counts of closed walks, whereas learning uses central moments after affine rescaling of the spectrum.The central moments are computed from the discrete spectral levels and their DOS weights.
  • Five standardized moments provide dimensionless, size-free features that capture the rescaled spectrum's width and four leading shape parameters.The spectrum is first mapped to the unit interval so features are comparable across graph sizes.
  • The feature pipeline encodes a graph, estimates its DOS by classical or quantum sampling, compresses it into five moments, and feeds those features to a classically trained model.The encoding determines which invariances the resulting features inherit and which structure they can represent.

III. FRUSTRATION INDEX

The frustration index quantifies how far a signed graph is from structural balance by minimizing sign reversals. Its coloring formulation connects the problem to cut optimization and supports exact dataset labeling.

  • The frustration index L(G) is the minimum number of edge sign reversals needed to produce a balanced graph.Balance requires every cycle to contain an even number of negative edges.
  • Deleting the edges counted by the frustration index is equivalent to flipping their signs, so L(G) also counts the fewest deletions needed to restore balance.Both operations yield the same minimum.
  • A vertex 2-coloring formulation counts edges whose signs disagree with the coloring-induced relation, and minimizing this count yields L(G).This is the formulation used to label the datasets exactly with an integer linear program.
  • For an all-negative signed graph, the frustration-index formulation reduces to MAXCUT, making its decision version NP-complete.By contrast, deciding whether a graph is perfectly balanced, L = 0, is solvable in linear time.

IV. ISING GRAPH EMBEDDING

The signed graph is mapped directly to an Ising Hamiltonian whose ground-state energy encodes frustration and whose spectrum is invariant under switching. This direct encoding preserves balance-relevant sign information that a signed line-graph encoding discards.

  • The direct Ising encoding assigns ferromagnetic couplings to positive edges and antiferromagnetic couplings to negative edges, with zero coupling between non-neighbors.The couplings are Jij = −σij.
  • The Hamiltonian's ground-state energy exactly encodes the frustration index because satisfied edges contribute −1 and frustrated edges contribute +1.Learning L(G) can therefore use spectral statistics instead of directly solving the ground-state optimization problem.
  • Switching signs across a vertex cut is implemented by Hamiltonian conjugation, preserving the spectrum, DOS, and all DOS moments.The resulting features match the switching invariance of the frustration index while retaining sign information absent from unsigned spectra.
  • The signed line-graph embedding is spectrally sign-blind, whereas the direct encoding preserves the switching-class information relevant to balance.Consequently, the direct encoding is adopted for the learning pipeline.

V. MOMENTS OF THE ISING DENSITY OF STATES

At zero field, the DOS spectrum has fixed integer support and a graph-independent rescaled mean, while standardized moments capture its graph-dependent shape. The feature set retains edge count alongside four size-free standardized moments.

  • The zero-field spectrum lies on integers from −|E| to |E| with fixed parity, and rescaling gives x = (E + |E|)/(2|E|).
  • Because tr H = 0, the rescaled spectrum has mean x̄ = 1/2 and no graph-dependent information.
  • The two moment families satisfy μk = Mk/(2|E|)^k for k ≥2 after rescaling.
  • M2 = |E|, so the first feature encodes edge count while the remaining standardized moments γ3 through γ6 describe DOS shape.

A. Why moments encode frustration

The Ising DOS moments expand into signed closed-walk counts that remain invariant under switching. Odd moments directly encode sign imbalance, whereas even moments combine sign-independent pairings with signed-circuit corrections.

  • DOS energy moments retain only edge tuples with even degree at every vertex, which decompose into closed circuits and yield switching-invariant sign products.
  • M3 = −6(t+ − t−), so the third moment counts triangle imbalance through balanced and unbalanced triangle counts.
  • Odd moments are purely sign-sensitive, while even moments include dominant sign-independent edge pairings and corrections from short signed circuits.
  • The fourth and fifth moments receive sign-sensitive corrections from squares and pentagons, respectively.

B. Classical samplability at zero field

At zero field, the full Ising DOS can be sampled classically by uniformly drawing spin assignments and evaluating their energies, providing scalable feature generation and an exact target for quantum pipelines. A transverse field preserves fixed-order moment formulas but removes this known classical density sampler.

  • Independent DOS samples are generated by uniformly sampling spin assignments and evaluating E(s), at O(m) cost per draw for any graph size.
  • For n = 10 graphs with |E| = 39, increasing frustration from L = 0 to 10 raises γ3 from −1.90 to −0.15 and lowers γ4 from 8.42 to 2.74.
  • Classical Monte Carlo reproduces the entire zero-field spectral density, scales feature generation to arbitrary graph size, and supplies an exactly certifiable target for quantum routes.
  • With a transverse field, fixed-order moments remain closed-form polynomials in hx, but the diagonal structure is lost and no classical density sampler is known.

VI. LEARNING THE FRUSTRATION INDEX

The exact DOS determines the frustration index across 1.4 × 10^5 labeled graphs, while five standardized moments provide a compact, size-free representation that supports accurate estimation and size transfer. Combined features perform best in-distribution, but normalized DOS features transfer more reliably beyond the training sizes than raw counts.

  • Empirical ceiling: The exact density of states determines L for every one of the 1.4 × 10^5 labeled graphs, establishing a unit-accuracy ceiling for DOS-based prediction.Graphs were grouped by exact energy histogram to prevent leakage, and no DOS-sharing group contained different frustration-index values.
  • Estimation results: At n = 12, combining DOS moments with counting features reaches 0.688 ± 0.007 accuracy, while moments alone achieve 0.550 ± 0.006 and counting features 0.433 ± 0.008.For ordinal prediction, all features achieve 0.340 ± 0.003 MAE, compared with 0.388 ± 0.007 for moments alone and 0.759 ± 0.010 for counting features.
  • Estimation results: Five DOS moments outperform edge, negative-edge, and triangle counts at every graph size, capturing signed circuits missed by those counting features.Classical spectral balance summaries can outperform the DOS moments at some sizes, while the combined feature family remains strongest overall.
  • Scope and limitation: The method is intended for estimation and quantum-compatible feature extraction, not to outperform direct optimization at the small sizes studied.A 20-restart greedy search recovers the exact index on at least 99.8% of graphs and costs less than exact-DOS enumeration at n = 12.
  • Size transfer: Training through n = 11 and testing at n = 12 yields 0.621 ± 0.005 accuracy with the full feature set, versus 0.215 ± 0.001 for non-size-normalized spectral-balance summaries.Moments-plus-counts reaches 0.566 ± 0.007, while moments alone reach 0.350 ± 0.001 accuracy and 0.588 ± 0.001 MAE.
  • Real networks: On Gahuku-Gama, trained on graphs four vertices smaller, moments assign 0.574 ± 0.016 probability to the true L = 7 and predict 7.09 ordinally.Adding raw counts instead assigns 0.978 probability to the incorrect L = 9 class, illustrating the extrapolation risk of size-dependent features.

VII. QUANTUM PIPELINES

The paper compares trace sampling with DOS-QPE for extracting density-of-states features and evaluates their accuracy, shot efficiency, and register requirements. DOS-QPE reaches comparable classifier performance with far fewer shots, while finite-register kernel bias limits the highest reliable moment order.

  • DOS-QPE: DOS-QPE applies phase estimation to a purified maximally mixed state, so each measurement directly samples the spectral density for moment estimation.Bell-pair preparation produces the maximally mixed system state, and the phase register controls powers of U before inverse Fourier transformation and measurement.
  • Shot efficiency: More than two orders of magnitude more measurements are required for NISQ trace sampling to match DOS-QPE performance.At 10^4 shots, DOS-QPE reaches 0.764 ± 0.016 while trace sampling reaches 0.612 ± 0.008 and does not match it within the studied range.
  • Register resolution: At n = 8, M = 10 and M = 12 reach the exact-moment ceiling, whereas a 6-bit register saturates at 0.727 ± 0.012 versus 0.786 ± 0.012.Increasing shots cannot remove the plateau deficit because it is caused by register-dependent kernel bias.
  • Classical training, quantum deployment: Classically trained models transfer successfully to quantum-sampled features at M = 10 and M = 12 but degrade sharply at smaller registers.For M = 12, transfer accuracy is 0.789 ± 0.014 versus 0.784 ± 0.016 self-trained; at M = 6 it is 0.422 ± 0.016 versus 0.725 ± 0.011.
  • Moment accuracy: DOS-QPE matches classical Monte Carlo through the sixth moment at M = 12, but its accuracy degrades rapidly at higher moment orders.The QPE kernel introduces bias that shot increases cannot remove; adding register qubits reduces sixth-moment bias while increasing controlled evolutions.

VIII. DISCUSSION

The discussion positions the method as an average-case spectral approach with a classically certifiable zero-field benchmark and broader quantum scope beyond that setting. It also identifies hardware routes, application domains, and the importance of matching Hamiltonian symmetry to graph invariances.

  • Empirical interpretation: Exact DOS features determine the frustration index across the full dataset, while the five-moment representation remains below that ceiling.The authors characterize these as average-case statements over natural ensembles and two real networks, complementary to worst-case intractability.
  • Scope and complexity: The zero-field benchmark permits exact classical certification, while beyond zero field normalized-trace estimation is DQC1-complete.This separates a classically accessible certification regime from dynamics for which no efficient classical sampler is known.
  • Hardware: Neutral-atom arrays provide a hardware route for implementing the required Ising dynamics through programmable Rydberg-mediated interactions.The discussion identifies analog evolution and gate-based control as available implementation modes.
  • Applications: The framework extends to spin glasses, regulatory and protein-interaction networks, and correlation clustering through compact switching-invariant DOS features.These applications involve signed interactions or related signed-graph problems.
  • Representation design: The direct signed-graph encoding preserves switching-class information, whereas a line-graph encoding provably discards sign information.The authors attribute representation effectiveness to matching Hamiltonian symmetry with the learning problem's invariances.

IX. CONCLUSIONS

The paper introduces DOS-based quantum spectral features for signed-graph learning and benchmarks them on frustration-index prediction. Exact DOS features determine the target across 1.4 × 10^5 graphs, while DOS-QPE provides shot-efficient quantum extraction with direct deployment of classically trained models.

  • IX. CONCLUSIONS: Exact DOS determines the frustration index across 1.4 × 10^5 labeled graphs, while five moments recover it with a mean error of 0.4 sign flips.The five-moment representation is substantially smaller than the full density while retaining strong predictive information.
  • IX. CONCLUSIONS: DOS-QPE samples the spectral density with orders of magnitude fewer shots than Hadamard-test trace sampling.Its output can be used directly by models trained on classical features.
  • IX. CONCLUSIONS: At zero field, classical DOS sampling enables exact certification, whereas beyond zero field the underlying trace-estimation problem is DQC1-complete.The latter regime provides access to spectral features for which no efficient classical sampler is known.

Appendix A: Line graphs cannot hear frustration

The product-sign line-graph encoding is spectrally blind to the original signing, so its spectral features cannot determine frustration. This information loss occurs at the embedding stage, before classification.

  • Spectral equivalence: The signed line graph is switching-equivalent to the all-positive line graph of the underlying graph.The equivalence follows from diagonal conjugation by the edge-sign matrix.
  • Spectral equivalence: Its adjacency, signed-Laplacian, and corresponding Ising spectra are independent of the original edge signs.Therefore, spectral statistics derived from this encoding are identical across signings of the same underlying graph.
  • Failure to recover frustration: All-positive and all-negative triangles have frustration indices 0 and 1 but identical line-graph spectra.Thus no function of the line-graph spectrum can compute the frustration index.
  • Implication: The failure affects moments, DOS, gaps, and other spectral measures, and arises before any machine-learning classifier is applied.The statement is specific to the product-sign line graph; alternative bidirected-incidence conventions are outside its scope.
Loading 2609.11736v1…