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

The joint use of graph structure and node-specific information is central to transductive node classification, yet a fundamental theoretical question remains unanswered: when does graph structure actually help? We provide the first non-asymptotic, distribution-free answer to this question. We build on nuclear-norm graph clustering and classical convex clustering, generalizing the latter to incorporate 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 there exist conditions under which neither source alone achieves perfect recovery but using both jointly does, revealing a bidirectional synergy: node information improves clustering, while graph structure improves classification.