Metraipolis › archive › dc_7a8a2e0d8652

Provable Guarantees for Spectral Structured Prediction — arXiv:2609.18527

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.18527
License (as archived)
CC0-1.0
Archived
2026-10-15T15:04:45.249Z
SHA-256 of the archived text
a699c9bfee318d276cc04e443045cdacf7d26407d833a61edd6e45e43176fdc6
Stable URL of this page
https://metraipolis.com/documento/dc_7a8a2e0d8652

How to cite

Provable Guarantees for Spectral Structured Prediction — arXiv:2609.18527 — arXiv (en), https://arxiv.org/abs/2609.18527 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7a8a2e0d8652 (Metraipolis archive dc_7a8a2e0d8652, sha256 a699c9bfee318d276cc04e443045cdacf7d26407d833a61edd6e45e43176fdc6)
BibTeX
@misc{dc7a8a2e0d8652,
  title = {Provable Guarantees for Spectral Structured Prediction — arXiv:2609.18527},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.18527},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7a8a2e0d8652; sha256 a699c9bfee318d276cc04e443045cdacf7d26407d833a61edd6e45e43176fdc6},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.18527. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-17 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.18527 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T14:08:19.126Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).