PaperlayerView exact revision on arXiv

Source-linked AI summary

DISRL: Dual-Scale Incremental Semi-Supervised Reinforcement Learning for Dynamic Community Tracking

Tianming Zhang, Jinxu Wang, Yixuan Zhang, Zhengyi Yang, Chenyu Hou, Bin Cao, Jing Fan

arXiv:2610.29315v1cs.LG

TL;DR

Dynamic local community tracking must follow seed-centered communities through changing graph snapshots despite sparse supervision and long-horizon policy errors. DISRL creates seed-specific guidance and decouples policy adaptation within temporal windows from consolidation across windows. It reports consistent gains over state-of-the-art baselines, including F1-score gains of 2.89 and up to 6.42 percentage points on real-world and simulated-evolution datasets, respectively.

  • Problem

    Sparse general-community labels can misalign with seed-specific boundaries as topology changes, while sequential policy transfer can accumulate errors over long horizons.

    Source: §1 · p. 2

  • Method

    DISRL constructs seed-specific adaptive guidance from sparse communities and uses dual-scale policy optimization with within-window adaptation and inter-window parameter updates.

    Source: §1 · p. 2

  • Results

    DISRL consistently outperforms state-of-the-art baselines, with F1-score gains of 2.89 and up to 6.42 percentage points on real-world and simulated-evolution datasets, respectively.

    Source: §1 · p. 2, §5 · p. 9

  • Takeaways & Limitations

    The work provides a dynamic graph benchmark with diverse community evolution patterns for evaluating dynamic local community tracking.

    Source: §5 · p. 9

    The theoretical analysis assumes bounded local adaptation perturbation, bounded temporal drift, and a Lipschitz adaptation operator.

    Source: §3.4 · p. 5

Abstract

from arXiv · show

Dynamic local community detection tracks the evolving community of designated seed nodes across graph snapshots. However, it faces two critical challenges: temporal supervision uncertainty, where sparse and outdated labels fail to provide seed-specific guidance under topology changes, and unbounded error cascades, where sequential policy transfer accumulates exploration errors over long horizons. To address these challenges, we propose DISRL, a Dual-scale Incremental Semi-supervised Reinforcement Learning framework. DISRL introduces a supervision construction module that dynamically generates seed-specific guidance from sparse known communities, and a dual-scale community exploration module that stabilizes policy evolution by decoupling short-term adaptation within temporal windows from long-term parameter consolidation across windows. Furthermore, we construct a dynamic graph benchmark with diverse community evolution scenarios. Extensive experiments demonstrate that DISRL consistently outperforms state-of-the-art baselines under various dynamic settings.

1 Introduction

Dynamic local community tracking must follow seed-centered communities as graph topology changes, despite sparse, potentially outdated supervision and error accumulation across snapshots. DISRL addresses these challenges with seed-specific guidance and dual-scale policy adaptation, and is evaluated on a benchmark of diverse community evolutions.

1 Introduction

  • Sparse general-community labels can mismatch seed-specific boundaries, while splits and mergers can make historical predictions obsolete.Source: §1 · p. 2
  • Sequential policy transfer can compound exploration errors on non-stationary graphs, causing policy drift and degraded performance over long horizons.Source: §1 · p. 2
  • DISRL synthesizes seed-specific pseudo-reference communities and separates within-window policy adaptation from end-of-window master-parameter updates.The stable window-level master initializes the fast policy and remains stationary during the window.Source: §1 · p. 2
  • The benchmark uses empirical network topologies and authentic community structures to represent expansion, shrinkage, splitting, merging, and topological perturbations.Source: §1 · p. 2
  • The paper frames dynamic local tracking as incremental reinforcement-learning exploration around seed nodes, rather than passive temporal embedding aggregation.Source: §1 · p. 2
  • 2.89 and up to 6.42 percentage points are DISRL’s F1-score gains on the real-world and simulated-evolution datasets, respectively.Source: §1 · p. 2

2 Related Work

Prior work spans static community detection and dynamic tracking, but the related-work review identifies gaps in temporal continuity and seed-centered local tracking under sparse supervision.

2 Related Work

  • Static methods, including semi-supervised and RL-based approaches, are designed for static topologies and cannot exploit temporal continuity as communities evolve.Source: §2 · p. 2
  • Traditional dynamic methods model evolution through clustering, incremental updates, and seed-centered tracking, while learning-based methods capture temporal patterns with graph networks or topology-regularized clustering.Source: §2 · p. 2
  • The reviewed dynamic methods rarely address seed-centered local detection under sparse supervision, leaving weak guidance and possible propagation of transient errors across snapshots.Source: §2 · p. 2

3 Methodology

DISRL frames seed-centered community tracking across graph snapshots as sequential reinforcement-learning exploration guided by sparse supervision. It builds seed-specific references, adapts a fast policy within temporal windows, and consolidates policy updates across windows to limit error propagation.

3.1 Problem Formulation and Overview

  • DISRL models each seed’s evolving local community across snapshots using temporal graph evolution and sparse supervision.Its exploration predicts a community containing the designated seed at each snapshot.Source: §3.1 · p. 2

3.2 Supervision Construction Module

  • The supervision construction module uses reference synthesis and relevant-community retrieval to turn macro-level known communities into seed-specific guidance.The reference serves as an inductive bias rather than the final prediction.Source: §3.2 · p. 3, §3.2.1 · p. 3

3.2.1 Reference Community Synthesis.

  • At the first snapshot, DISRL bootstraps a seed-centric reference with a generic policy; later, it projects prior predictions onto the current graph and prunes disconnected fragments.The connected component containing the seed keeps the reference seed-connected after localized edge changes.Source: §3.2.1 · p. 3

3.2.2 Relevant Community Retrieval.

  • DISRL ranks known communities by normalized shortest-path graph-kernel similarity to the reference and selects the top-K as relevant supervision.The kernel compares matching shortest-path lengths between node pairs.Source: §3.2.2 · p. 3

3.3 Dual-scale Community Exploration Module

  • The exploration module coordinates adjacent-snapshot fast-policy adaptation with master-parameter anchoring and transition meta-gradient consolidation at window boundaries.The master parameter limits consecutive propagation of historical exploration errors across long horizons.Source: §3.3 · p. 3

3.3.1 Intra-window Scale Exploration and Fast Adaptation.

  • The Community Explorer trains on rollouts from virtual seeds using retrieved communities for rewards, then greedily expands from the target seed at inference.Its state includes the explored community, candidate boundary, and localized node representations.Source: §3.3.1 · p. 3

3.3.2 Inter-window Scale Meta-Anchoring and Temporal-Decay Gra-

  • Across windows, DISRL approximates transition meta-gradients with a first-order estimate, buffers them, and aggregates them with temporal-decay weights to update the master parameter.The updated master parameter initializes the next window, and recent transitions receive larger weights.Source: §3.3.2 · p. 5

3.4 Theoretical Analysis

  • Under bounded adaptation perturbations and temporal drift with a Lipschitz adaptation operator, DISRL confines direct fast-parameter transfer to at most w−1 transitions per window.The analysis says this window-confined propagation mitigates long-horizon error accumulation.Source: §3.4 · p. 5

4 Experiments

The experiments evaluate DISRL on empirical-network evolution and compare it with static and dynamic baselines, module ablations, and temporal and parameter variants. DISRL leads the reported tracking metrics across settings, with additional analyses of long-horizon behavior and efficiency.

4.1 Experimental Setup

  • The benchmark mutates four empirical networks through expansion, shrinkage, merging, splitting, and background perturbations; evaluation spans Football and four SNAP datasets.The simulated datasets are assessed under expansion and shrinkage, and Amazon and DBLP are also assessed under merging and splitting.Source: §4.1 · pp. 5–6

4.2 Main Results

  • DISRL leads F1-score and Jaccard across settings, with dynamic-baseline F1 gains up to 4.25 pp on Twitter and 6.42 pp on DBLP.On Football, its F1 gain over the strongest dynamic baseline is 2.89 pp.Source: §4.2 · p. 6, Table 2 · p. 7

4.3 Ablation Study

  • All five ablations underperform DISRL, supporting topology-consistent reference construction, similarity retrieval, window-level anchoring, and temporal-decay gradient weighting.The ablations cover removing connected-component extraction, replacing synthesized references with a two-hop neighborhood, random community retrieval, continuous fast-policy transfer, and uniform gradient averaging.Source: §4.3 · pp. 7–8

4.4 Long-Horizon Error Mitigation Analysis

  • DISRL and its window-free variant perform comparably early in Football tracking, then diverge more noticeably in later stages.The comparison spans 24 consecutive snapshots and six temporal windows of w=4.Source: §4.4 · p. 8, Figure 2 · p. 8

4.5 Hyper-parameter Sensitivity

  • K=50 gives stable simulated-dataset performance, while K=100 degrades it; on Football, the best F1-score occurs at K=5.Football performance initially improves as K increases, then declines beyond K=5.Source: §4.5 · p. 8, Figure 3 · p. 8
  • L=2 performs best on Football, whereas L=3 performs best on Amazon, DBLP, and Twitter.The paper relates propagation depth to capturing multi-hop boundary context while limiting remote structural noise.Source: §4.5 · p. 8, Figure 4 · p. 8
  • The study describes w=2 as temporally myopic and w=6 as introducing optimization lag, and presents w=4 as balancing short- and long-term tracking.The stated risks are overfitting transient fluctuations at w=2 and stale gradients at w=6.Source: §4.5 · p. 8, Figure 5 · p. 9

4.6 Additional Experimental Analyses

  • DISRL achieves up to 10.35× speedup over CS-TGN and tracks evolving community boundaries through adaptive supervision construction and dual-scale policy consolidation.The paper places a qualitative case study and efficiency comparison in Appendices C and D, respectively.Source: §4.6 · p. 9

5 Conclusion

DISRL addresses temporal supervision uncertainty and long-horizon error cascades in dynamic local community tracking. The paper also introduces a dynamic graph benchmark, and reports that DISRL outperforms state-of-the-art baselines with improved efficiency and tracking stability.

5 Conclusion

  • DISRL constructs seed-specific adaptive guidance from sparse communities and uses dual-scale policy optimization to address supervision uncertainty and long-horizon error cascades.The framework is for dynamic local community tracking.Source: §5 · p. 9
  • The paper develops a dynamic graph benchmark with diverse community evolution patterns.Source: §5 · p. 9
  • Experiments show that DISRL consistently outperforms state-of-the-art baselines with improved efficiency and tracking stability.Source: §5 · p. 9

A Theoretical Analysis

The analysis bounds fast-parameter tracking error during sequential adaptation, then shows how periodic master-policy anchoring confines direct error propagation to temporal windows. The window-level bound does not guarantee a uniform bound across windows.

A Theoretical Analysis

  • Under Assumptions 1–3, each adjacent-snapshot transition within a temporal window satisfies a single-step fast-parameter error bound.The assumptions bound adaptation perturbation, ideal-parameter drift, and the adaptation operator's Lipschitz constant.Source: A Theoretical Analysis · p. 10
  • For 0 ≤ κ < 1, the tracking-error upper bound remains bounded for fixed initial error; at κ = 1 it grows at most linearly, and for κ > 1 geometric growth is permitted.These upper bounds do not imply that actual tracking error necessarily increases.Source: A Theoretical Analysis · p. 10
  • With constant perturbation ε and no periodic anchoring, the example yields |x_t| = tε, demonstrating that error accumulation can be unbounded.The construction uses an identity adaptation process, ideal parameter x★ = 0, and starts from x_0 = 0.Source: A Theoretical Analysis · p. 10
  • When κ = 1, periodic anchoring bounds the added within-window error by (w−1)(ξ + Δ), while the initial error is set by the evolving master parameter.Because each window spans w snapshots, fast-parameter transfer covers at most w−1 consecutive transitions.Source: A Theoretical Analysis · pp. 10–11
  • With fixed window size smaller than the full sequence, periodic master-policy anchoring restricts direct error propagation to each window and mitigates long-horizon drift risk.The analysis does not establish a uniform error bound across windows because the master-parameter initialization error remains unbounded.Source: A Theoretical Analysis · p. 11

B Evaluation Settings and Hyper-parameters

The dynamic generation procedures evolve graphs through four topological operators, alongside continuous background noise from random node and edge insertions and deletions.

B.1 Dynamic Generation Procedures

  • Expansion injects boundary nodes following local homophily patterns.This operator models community growth.Source: §B.1 · p. 11
  • Shrinkage prunes peripheral members while preserving the community's structural core.This operator models community contraction.Source: §B.1 · p. 11
  • Merging adds bridge edges between structurally related community pairs to unify their labels.Source: §B.1 · p. 11
  • Splitting fractures a cohesive group into disjoint, internally coherent sub-components.Source: §B.1 · p. 11

B.2 Evaluation Protocols

Evaluation covers simulated expansion-and-shrinkage and merge-and-split settings, plus real-world tracking of college football teams across yearly snapshots.

B.2 Evaluation Protocols

  • Expansion-and-shrinkage sequences use four SNAP datasets, with 25 snapshots for Amazon and DBLP and 13 for YouTube and Twitter.The study samples 100 target seeds per dataset; Amazon and DBLP have six expansion steps, six shrinkage steps, then twelve randomly selected expansion or shrinkage steps.Source: §B.2 · p. 11
  • Merge-and-split sequences use Amazon and DBLP, each with four merge operations followed by four split operations across nine snapshots.The setting uses 100 sampled target seeds per dataset.Source: §B.2 · p. 11

B.3 Hyper-parameter Configurations

The supplied passage identifies Table 4 as the source of DISRL's experimental hyper-parameter configurations.

B.3 Hyper-parameter Configurations

C Case Study

Across four DBLP snapshots, DISRL tracks an expanding target community with high F1, while ProCom and CS-TGN lag at the initial change. The account attributes DISRL’s tracking continuity to cold-start bootstrapping and reference-community filtering.

C Case Study

  • DISRL’s F1 scores are 0.93, 0.95, 0.96, and 0.97 from t0 to t3 as the target community expands.The target grows from 7 to 16 nodes across four snapshots.Source: C Case Study · p. 11, Figure 6 · p. 12
  • At t0, ProCom and CS-TGN each score 0.55 F1; at t1, ProCom falls to 0.47, and CS-TGN trails DISRL throughout the window.The figure panels report F1 by method and snapshot.Source: C Case Study · p. 11, Figure 6 · p. 12
  • DISRL’s cold-start bootstrapping isolates the seed’s immediate vicinity, while reference-community synthesis filters disconnected structural noise in later snapshots.The explorer inherits prior predictions as historical context to track expanding boundaries while maintaining continuity.Source: C Case Study · p. 12

D Efficiency Study

Under expansion and shrinkage, DISRL has the lowest reported execution latency across three datasets. Its speed advantage over CS-TGN is attributed to policy adaptation on compact, seed-specific supervision and localized subgraphs.

D Efficiency Study

  • DISRL achieves 1.96×, 4.78×, and 10.35× speedups over CS-TGN across three datasets under expansion and shrinkage.The comparison reports runtime normalized per target seed per snapshot over 50 independent queries.Source: D Efficiency Study · p. 12, Figure 7 · p. 12
  • DISRL has the lowest execution latency among the baselines on all three datasets.The efficiency comparison is under the expansion-and-shrinkage setting.Source: D Efficiency Study · p. 12, Figure 7 · p. 12
  • DISRL adapts its policy on compact Top-K seed-specific supervision and localized subgraphs, avoiding full-graph temporal representation learning.The passage contrasts this with CS-TGN’s temporal GNN processing of snapshot graphs and repeated query scans across epochs.Source: D Efficiency Study · p. 12

Related papers

Loading 2610.29315v1…