cs.LGAug 27, 2025

When Graph Structure Provably Helps Classification: Non-Asymptotic Recovery Guarantees

Authors: Firooz Shahriari-Mehr, Javad Aliakbari, Alexandre Graell i Amat, Ashkan Panahi

Organizations: Department of Computer Science and Engineering Chalmers University of Technology and University of Gothenburg · Department of Electrical Engineering Chalmers University of Technology

Abstract

The joint use of graph structure and node-specific information is central to transductive node classification, yet a fundamental theoretical question remains: when does graph structure actually help? We provide the first deterministic, non-asymptotic, distribution-free answer to this question. We build on nuclear-norm graph clustering and generalized convex clustering. Our formulation of the latter incorporates node features, partial labels, and general convex loss functions, making it suitable for transductive node classification. We analyze each problem separately to characterize when graph structure alone, or node information alone, is sufficient for perfect recovery. We then formulate a unified convex optimization problem through a shared atomic norm representation and prove that combining the two sources expands the range of conditions under which perfect recovery is guaranteed beyond what either source alone can certify. This shows when node information can improve clustering and graph structure can improve classification.

Figures & tables

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Transductive Generalization for GNNs via Optimal Transport

    Mar 10, 2026MoonJeong Park, Seungbeom Lee, Kyungmin Kim +5Transductive LearningGeneralization Bounds

  2. Closed-Form Node Classification with Exact Graph Unlearning

    May 25, 2026Aditya Gaur, Charu SharmaGraph Representation LearningPrivacy-Preserving ML

  3. Graph Transductive Sharpening: Leveraging Unlabeled Predictions in Node Classification

    May 18, 2026Brown Zaz, Mar Gonzàlez I Català, Ferran Hernandez Caralt +2Graph Neural NetworksGraph-Based Semi-Supervised Learning