Provable Guarantees for Spectral Structured Prediction

Violet Zheng; Jean Honorio

cs.LGSep 16, 2026

Provable Guarantees for Spectral Structured Prediction

Authors: Violet Zheng, Jean Honorio

Organizations: CIS, The University of Melbourne

Abstract

Structured prediction is the simultaneous prediction of multiple labels, and is widely used in various fields, such as natural language processing and computer vision. In this paper, we study binary node label recovery on signed graphs with edge-flip noise, a model introduced by (Globerson et al., 2015), via a simple spectral method that decodes node labels from the signs of the principal eigenvector of the noisy signed adjacency matrix. We develop graph structure-agnostic theoretical guarantees for approximate inference of node labels as well as guarantees for maximum angle deviation with respect to the ground truth node labels. By leveraging tools from matrix concentration theory and eigenvector perturbation analysis, we derive new concentration inequalities that explicitly quantify the effect of the spectral gap of the adjacency matrix, number of nodes, degree distribution, and noise level. As a corollary, we relate our general results to the Cheeger constant and provide results for different classes of graphs. We perform several synthetic experiments to validate our theory. To the best of our knowledge, we are the first to provide theoretical guarantees for the spectral-based approach. As a byproduct of our analysis, we derive technical results that might be of independent interest and useful for other machine learning problems.

Figures & tables

Panel of Figure 1 — Figure 1 : Effect of the structural term $\frac{(\lambda_{n-1}(\mathbf{L})-d_{\max}+d_{\mathrm{avg}})^{2}}{d_{\max}}$ on the angle deviation (a) and proportion of correctly recovered node labels (b) for Erdös–Rényi graphs (with varying edge density and $n$ ) with $p=0.4$ . Error bars at 95% confidence level over 30 repetitions. As predicted by Corollaries 1 and 2 , the higher the structural term, the lower the angle deviation and the higher the proportion of correctly recovered node labels.

Figure 2 : Effect of number of nodes $n$ on the runtime of our spectral method (Spectral) and semidefinite programming (SDP) for Erdös–Rényi graphs (60% edge density) for $p=0.4$ . Error bars at 95% confidence level over 10 repetitions. Spectral structured prediction is a far more efficient algorithm. SDP was run only up to graphs of size 500 nodes due its high runtime.

Panel of Figure 3 — Figure 3 : Effect of edge-noise parameter $p$ on the angle deviation (a) and proportion of correctly recovered node labels (b) for $d$ -regular expanders ( $d=6$ ) of $n=200$ nodes. Error bars at 95% confidence level over 30 repetitions. Our spectral method (Spectral) and semidefinite programming (SDP) produced comparable results.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 4 — Figure 4 : Effect of edge-noise parameter $p$ on the angle deviation (a) and proportion of correctly recovered node labels (b) for Erdös–Rényi graphs (60% edge density) of $n=200$ nodes. Error bars at 95% confidence level over 30 repetitions. Our spectral method (Spectral) and semidefinite programming (SDP) produced comparable results.

Panel of Figure 5 — Figure 5 : Effect of edge-noise parameter $p$ on the angle deviation (a) and proportion of correctly recovered node labels (b) for complete graphs of $n=200$ nodes. Error bars at 95% confidence level over 30 repetitions. Our spectral method (Spectral) and semidefinite programming (SDP) produced comparable results.

Panel of Figure 6 — Figure 6 : Effect of number of nodes $n$ on the angle deviation (a) and proportion of correctly recovered node labels (b) for Erdös–Rényi graphs (60% edge density) with $p=0.4$ . Error bars at 95% confidence level over 30 repetitions. Our spectral method (Spectral) and semidefinite programming (SDP) produced comparable results.

Panel of Figure 7 — Figure 7 : Effect of number of nodes $n$ on the angle deviation (a) and proportion of correctly recovered node labels (b) for $d$ -regular expanders ( $d=6$ ) with $p=0.4$ . Error bars at 95% confidence level over 30 repetitions. Our spectral method (Spectral) and semidefinite programming (SDP) produced comparable results.

Panel of Figure 8 — Figure 8 : Effect of number of nodes $n$ on the angle deviation (a) and proportion of correctly recovered node labels (b) for complete graphs with $p=0.4$ . Error bars at 95% confidence level over 30 repetitions. Our spectral method (Spectral) and semidefinite programming (SDP) produced comparable results.

Explore similar work

Spectral Embeddings Leak Graph Topology: Theory, Benchmark, and Adaptive Reconstruction
Apr 22, 2026Thinh Nguyen-Cong, Truong-Son Hy, Thang N. DinhGraph Edge Sparsification Federated Graph Learning
Department of Computer Science Virginia Commonwealth University Richmond, VA, USA · Department of Computer Science The University of Alabama at Birmingham Birmingham, AL, USA
A Spectral Theory of Normalized Corrected GNN Propagation
Jun 22, 2026Qihan Chen, Wei Li, Meng Qin +1Graph Neural Networks Propagation
Center for Discrete Mathematics, Fuzhou University · School of Computer and Information Science, Fujian Agriculture and Forestry University · Department of Strategic & Advanced Interdisciplinary Research, Pengcheng Laboratory (PCL), Shenzhen, Guangdong, China
Closed-Form Node Classification with Exact Graph Unlearning
May 25, 2026Aditya Gaur, Charu SharmaGraph Representation Learning Graph Neural Networks
Machine Learning Lab · IIIT Hyderabad

Apr 22, 2026, cs.LGJ/K move · Enter open · S save

Spectral Embeddings Leak Graph Topology: Theory, Benchmark, and Adaptive Reconstruction

Thinh Nguyen-Cong, Truong-Son Hy, Thang N. Dinh

Department of Computer Science Virginia Commonwealth University Richmond, VA, USA · Department of Computer Science The University of Alabama at Birmingham Birmingham, AL, USA

Graph Edge Sparsification Federated Graph Learning Theory

Open paper AskPDF arXiv

Graph Neural Networks (GNNs) excel on relational data, but standard benchmarks unrealistically assume the graph is centrally available. In practice, settings such as Federated Graph Learning, distributed systems, and privacy-sensitive applications involve graph data that are localized, fragmented, noisy, and privacy-leaking. We present a unified framework for this setting. We introduce LoGraB (Local Graph Benchmark), which decomposes standard datasets into fragmented benchmarks using three strategies and four controls: neighborhood radius

d

, spectral quality

k

, noise level

σ

, and coverage ratio

p

. LoGraB supports graph reconstruction, localized node classification, and inter-fragment link prediction, with Island Cohesion. We propose AFR (Adaptive Fidelity-driven Reconstruction), a method for noisy spectral fragments. AFR scores patch quality via a fidelity measure combining a gap-to-truncation stability ratio and structural entropy, then assembles fragments using RANSAC-Procrustes alignment, adaptive stitching, and Bundle Adjustment. Rather than forcing a single global graph, AFR recovers large faithful islands. We prove heat-kernel edge recovery under a separation condition, Davis--Kahan perturbation stability, and bounded alignment error. We establish a Spectral Leakage Proposition: under a spectral-gap assumption, polynomial-time Bayesian recovery is feasible once enough eigenvectors are shared, complementing AFR's deterministic guarantees. Experiments on nine benchmarks show that LoGraB reveals model strengths and weaknesses under fragmentation, AFR achieves the best F1 on 7/9 datasets, and under per-embedding

(ε,δ)

-Gaussian differential privacy, AFR retains 75% of its undefended F1 at

ε=2

. Our anonymous code is available at https://anonymous.4open.science/r/JMLR_submission

Abstract

Explore similar work

Spectral Embeddings Leak Graph Topology: Theory, Benchmark, and Adaptive Reconstruction

A Spectral Theory of Normalized Corrected GNN Propagation

Closed-Form Node Classification with Exact Graph Unlearning