Task-adaptive sparse graph structure learning with error-edge pruning and anti-smoothing mechanism.

Abstract

Graph Structure Learning (GSL) optimizes graph topologies to enhance node representations. This study reveals a critical limitation: while GSL excels in node-invariant tasks where graph structure remains static, it consistently underperforms in node-variant tasks requiring structural adaptation. To address this, we propose Adaptive Sparse Graph Structure Learning (ASGSL). ASGSL introduces three complementary error-edge pruning strategies: a lightweight gating mechanism, a novel sparsity-inducing regularization with theoretically guaranteed ascending-order pruning, and a constrained neighborhood search. Additionally, we devise two anti-smoothing techniques, effectively mitigating the vicious cycle of node similarity escalation. Experiments on node-invariant and node-variant tasks demonstrate that ASGSL-enhanced GNNs significantly outperform baseline models. Notably, the anti-smoothing mechanisms maintain robust performance in 32-layer deep GNNs, significantly alleviating over-smoothing degradation. Code and data are available at https://github.com/kanyuanliang/ASGSL.