arXiv preprint ·
Provable Guarantees for Spectral Structured Prediction
- Published
- Source
- arXiv preprint, posted before peer review
- Published in
- arXiv
- DOI
- 10.48550/arxiv.2609.18527
- Original
- Read it at arXiv
- Cited by
- 0 works, as OpenAlex counts them
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
On the Identifiability of Mixed Ordinal and Exponential Family Causal DAGs under Linear Parametric Models
QVAC Genesis III: A Large-Scale, High-Quality Open Synthetic STEM Corpus for Efficient Language Model Pre-Training
ASPIRE: Asynchronous Batched Self-Speculative Decoding for Long-Context LLM Inference
LLM-as-an-Improver: Turning Verification into Better Candidates
Maximum Strong Independent Sets in Hypergraphs: Reductions, Bounds, and Greedy Certificates
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.