← 研踪 PaperTrailarXiv:2508.20231 · v2
When Graph Structure Provably Helps Classification: Non-Asymptotic Recovery Guarantees
首次提交 2025-08-28 03:22
版本更新 2026-11-11 06:12
雷达观测 2026-11-13 11:12
摘要
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.
作者备注：Accepted at NeurIPS 2026
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-11 06:12 · 最新观测版本
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: 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.
查看此版本解读 →查看此版本原文 ↗