Research map / Graph learning / Graph self-supervised learning

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

NeurIPS 2026 · Graph learning › Graph self-supervised learning · approach: Heterophily and imbalance on graphs

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives the first non-asymptotic, distribution-free theory of when graph structure helps transductive node classification, building on nuclear-norm graph clustering and a feature-augmented convex clustering.

Problem

When does graph structure actually help transductive node classification, given node-specific features? The paper targets the lack of a non-asymptotic, distribution-free theoretical answer.

Approach

Generalizes classical convex clustering to incorporate node features and combines it with nuclear-norm graph clustering, yielding finite-sample recovery guarantees that characterize when graph structure provably improves classification.

Experimental setup

Builds on: nuclear-norm graph clustering convex clustering

Closest papers by meaning

• Structural Entropy Based Graph Structure Learning for Node Classification (AAAI 2024 · similarity 0.89)
• THESAURUS: Contrastive Graph Clustering by Swapping Fused Gromov-Wasserstein Couplings (AAAI 2025 · similarity 0.88)
• TFGDA: Exploring Topology and Feature Alignment in Semi-supervised Graph Domain Adaptation through Robust Clustering (NeurIPS 2024 · similarity 0.87)
• Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via Contextual Stochastic Block Models (ICML 2025 · similarity 0.86)
• Node Identifiers: Compact, Discrete Representations for Efficient Graph Learning (ICLR 2025 · similarity 0.86)
• Local Graph Clustering with Noisy Labels (ICLR 2024 · similarity 0.86)