DASM: Dynamic Autoregressive Subgraph Mining via Two-Stage Policy Alignment

Subgraph mining aims to discover meaningful subgraphs from a large graph given a seed node, with applications in community detection, functional module identification, anti-money laundering, and knowledge discovery. Existing methods typically adopt static approaches that cannot dynamically and intelligently adapt to diverse graph structures. Moreover, training models for subgraph mining faces inherent challenges including exposure bias and the difficulty of learning when to stop expansion. To address these limitations, we propose DASM (Dynamic Autoregressive Subgraph Mining), a novel two-stage framework that models subgraph mining as a sequential decision process. In the first stage, we employ step-wise supervised learning with multi-label objectives and asymmetric F1 loss to teach the model how to select correct next nodes. In the second stage, we apply Group Relative Policy Optimization (GRPO) to align the model with end-to-end mining quality, enabling it to learn optimal stopping decisions through trajectory-level feedback. Our dynamic autoregressive approach allows the model to make state-aware decisions at each step, automatically determining subgraph boundaries without predefined size constraints. Experiments on multiple datasets demonstrate that DASM significantly outperforms existing baselines in terms of F1 score and IoU.