PaperlayerView exact revision on arXiv

Source-linked AI summary

ComNetX: Local Hierarchical Adaptation for Dynamic Community Detection

Aleksandr Konovalov, Anna Uporova, Alexander Drobyshev, Iaroslav Egorov, Grigoriy Bokov

arXiv:2608.16906v1cs.SIcs.AIcs.LG

TL;DR

Dynamic community detection must balance the semantic fidelity of full recomputation with the efficiency and transferability of local updates. ComNetX provides a solver-agnostic hierarchical wrapper that preserves affected-community context through contraction, while Local Leiden achieves a 41.9 +/- 0.2x speedup with final modularity within 0.006 of full recomputation on the largest real graph.

  • Problem

    Existing dynamic community detection approaches either repeatedly recompute unchanged graph regions or use solver-specific updates with limited transferability and potentially insufficient community context.

  • Method

    ComNetX maintains a community hierarchy, closes updated regions over affected communities, contracts them into local instances, and invokes existing topology-only or feature-aware solvers.

  • Results

    Local Leiden retains large runtime advantages across resolution settings, reaching 41.6–44.8× speedups on dyn pubmed and 135.9–161.8× on arxivmath.

  • Takeaways & Limitations

    Locality is most suitable when affected communities remain small, while monitored diagnostics can identify cases where a full refresh is preferable.

  • Takeaways & Limitations

    Hub-heavy or very large updates may approach full-snapshot cost or lose boundary context, and representation-learning backends are more sensitive to restricted context and features.

Abstract

from arXiv · show

Dynamic community detection is commonly addressed either by full-snapshot recomputation or by solver-specific dynamic procedures. Full recomputation preserves the semantics of mature static solvers, but it repeatedly processes unchanged graph regions when updates are small. Solver-specific dynamic methods can reduce this cost, but their update rules often have limited transferability across objectives, feature representations, and implementations. In addition, localizing computation only by graph distance may omit community context needed by high-quality solvers. We introduce ComNetX, a solver-agnostic hierarchical adaptation framework for local dynamic updates. ComNetX maintains a multi-level community state, expands the updated region, closes it over affected communities, and contracts these communities into compact local instances. This affected-community closure and contraction preserve solver context while restricting computation to the changed part of the graph. The same interface can wrap modularity heuristics, graph-clustering models that use node features, and native dynamic solvers as local backends. We evaluate ComNetX through a multi-backend study on six real networks, longer real-data streams for topology-based backends, and controlled dynamic stochastic block model stress streams. The results show that ComNetX can preserve the quality of strong modularity-based solvers while reducing update time on large graphs: in paired runs on the largest real graph, Local Leiden keeps final modularity within 0.006 of full-snapshot recomputation while achieving a 41.9 +/- 0.2x speedup. The combined protocols also identify regimes where locality breaks down and a full refresh is preferable.

I. INTRODUCTION … B. Community Detection Interface

ComNetX is presented as a solver-agnostic hierarchical framework for dynamic community detection that localizes updates while preserving affected-community context. It supports classical, feature-aware, and dynamic solvers through a common interface and evaluates their compatibility across multiple dynamic settings.

  • I. INTRODUCTION: Dynamic community detection supports monitoring, recommendation, anomaly detection, and exploratory analysis, with modularity, Louvain, and Leiden remaining widely used foundations.Dynamic networks arise in social, communication, biological, and information systems.
  • I. INTRODUCTION: Existing dynamic methods reuse partitions, apply incremental modularity updates, or process affected neighborhoods, but their rules are often tied to specific objectives or solvers.Feature-aware and GNN-based methods increase the cost of repeated full-snapshot processing, motivating a shared adaptation framework.
  • I. INTRODUCTION: Locality creates a quality-efficiency tradeoff: small subgraphs lose community context, whereas large subgraphs erase the computational benefit of local processing.The challenge is to inspect only a bounded neighborhood while preserving the base solver’s quality.
  • I. INTRODUCTION: ComNetX maintains a community hierarchy, identifies affected communities, builds compact aggregated subproblems, and invokes the selected solver only on those local instances.Aggregation preserves surrounding community context and can transfer node attributes when required.
  • I. INTRODUCTION: The evaluation combines a multi-backend compatibility study, longer real-data streams, and controlled DSBM stress streams spanning random, hub-centered, and community-internal updates.The study is designed to compare full-snapshot recomputation with local processing across varied dynamic conditions.
  • A. Dynamic Graph Model: Each snapshot G_t=(V,E_t,A_t,X) uses a fixed vertex universe, while edge updates may isolate vertices or reconnect previously isolated vertices.Node attributes are represented in X when available; otherwise synthetic or no features may be used.
  • A. Dynamic Graph Model: A signed batch update Δ_t encodes edge-weight insertions, increases, deletions, and decreases, with endpoints of nonzero entries forming the directly affected set S_t.The affected set is defined by vertices incident to at least one changed edge.
  • B. Community Detection Interface: The solver interface treats community detection as a black box receiving adjacency A, optional features X, and an optional warm-start partition y_0.It covers Leiden and FLMIG, feature-aware models DMoN, MAGI, and S2CAG, and dynamic backends MFC and DF-Leiden used locally.

C. Modularity

The topology-based evaluation uses modularity with resolution parameter γ = 1 in the main experiments, supplemented by a resolution-sensitivity ablation. Because modularity is not ground truth and has known resolution limits, normalized mutual information is also reported when labels are available.

  • Metric setup: Modularity is the primary metric for topology-based evaluation on weighted directed or undirected graphs.The formulation uses a weighted adjacency matrix A and partition labels c_i.
  • Metric setup: γ = 1 is used in the main experiments, with resolution sensitivity checked in the ablation study.For undirected symmetric adjacency, the formulation recovers the standard undirected definition.
  • Metric limitations: Modularity is not a ground-truth measure and is affected by known resolution limits.These limitations motivate reporting an external-agreement metric when labels are available.
  • External agreement: Normalized mutual information (NMI) is reported as a compact external-agreement measure whenever ground-truth labels are available.NMI uses symmetric normalization based on empirical mutual information and entropy.

III. METHODOLOGY · A. Overview · B. Affected Region and Hierarchical Closure

ComNetX is a solver-agnostic local adaptation layer that preserves a base solver’s objective and community context while reoptimizing only affected regions. It expands updates, closes them under current communities, contracts local subproblems hierarchically, and writes revised labels back.

  • A. Overview: ComNetX wraps a base solver B without changing the objective it optimizes.After each batch update, it constructs a compact local instance preserving context around affected vertices.
  • A. Overview: The maintained state includes the accumulated sparse adjacency matrix At.
  • A. Overview: The maintained state includes the feature matrix X when the backend requires features.
  • A. Overview: The hierarchy Ct ∈ZL×n stores each vertex’s community label at every hierarchy level.After updates, ComNetX expands batch endpoints to a small graph neighborhood and reoptimizes intersecting communities.
  • A. Overview: At each level, affected communities are contracted into supernodes, the base solver runs on the contracted graph, and labels map back to original vertices.This workflow restricts computation to local subproblems while retaining hierarchical community structure.
  • B. Affected Region and Hierarchical Closure: A small radius r expands the directly affected set using shortest-path distance in the graph induced by nonzero symmetrized-adjacency entries.
  • B. Affected Region and Hierarchical Closure: Radius expansion alone can omit community context needed to determine whether partially included communities should split, merge, or remain unchanged.
  • B. Affected Region and Hierarchical Closure: At each hierarchy level, ComNetX closes the affected set under current community labels, allowing those communities to be relabeled while preserving labels outside the closure.Radius expansion identifies potentially revised communities; hierarchical closure supplies their full current context to the local backend.

C. Local Aggregation · D. Relabeling and Hierarchy Update

ComNetX contracts affected communities into sparse, solver-compatible local instances while preserving edge-weight structure and, when applicable, aggregating node features. It warm-starts and relabels the hierarchy, projects updated labels back to vertices, and cuts inter-community edges so subsequent levels refine only produced communities.

  • C. Local Aggregation: At level ℓ, ComNetX assigns compact identifiers to current communities and constructs a sparse membership matrix Pℓ for the local instance.The matrix represents community membership in the level-specific working set.
  • C. Local Aggregation: During aggregation, ComNetX removes edges crossing level-ℓ communities, producing the next working adjacency from within-community structure.The restricted affected-level adjacency remains embedded in the original n × n index space.
  • C. Local Aggregation: Edge weights between supernodes equal the sums of edge weights between their corresponding level-ℓ communities.This preserves aggregate structural weights exactly during contraction.
  • C. Local Aggregation: For feature-aware backends, ComNetX uses normalized feature aggregation, while topology-only solvers skip feature aggregation.In reported feature-aware runs, structural edge weights are preserved and do not additionally reweight the aggregated features.
  • D. Relabeling and Hierarchy Update: The contracted instance receives a warm-start partition from the previous hierarchy, which backends lacking warm-start support simply ignore.Previous level labels are renumbered into compact labels before invoking the base solver.
  • D. Relabeling and Hierarchy Update: The base solver runs on the aggregated instance, and its labels are projected back by assigning each supernode’s vertices to the corresponding new local cluster.ComNetX reuses existing community identifiers where possible to avoid relabeling unchanged regions.
  • D. Relabeling and Hierarchy Update: After each level update, ComNetX cuts edges whose endpoints belong to different communities, ensuring the next level refines only communities produced so far.Before the hierarchy loop, expanded affected vertices become singletons at the deepest stored level, while affected higher-level communities inherit finer labels.

E. Complexity and Locality

ComNetX’s per-update cost combines neighborhood expansion, sparse aggregation, and one backend call per hierarchy level, with backend memory determined by the contracted local graph. Locality is instance-dependent: high-degree updates or large affected communities can approach full recomputation, motivating computational guardrails and the studied r = 1, L = 3 configuration.

  • Per-update complexity: ComNetX performs neighborhood expansion, sparse aggregation, and one backend call per hierarchy level for each update.The backend operates on contracted local instances rather than the full snapshot.
  • Memory footprint: The backend-call memory footprint is governed by the contracted local graph, not the full snapshot.The contracted instance is characterized by its nonzero count and, when applicable, aggregated feature dimension.
  • Locality limits: For r = 1, the expanded set is bounded by changed-edge endpoints plus their degrees, so hub endpoints can destroy locality despite few changed edges.More generally, expansion depends on the degree profile around the update and is upper-bounded only by |V | without degree-distribution assumptions.
  • Locality limits: Affected-community closure is governed by the sizes of communities touched by the expanded set, while contraction cannot increase the nonzero count beyond the induced local subgraph.The number of affected communities satisfies kℓ≤min(bt, |Pℓ|).
  • Fallback criterion: If the expanded, closed, or contracted local instance exceeds a predefined computational budget, ComNetX should fall back to full recomputation.The practical guardrails are bt/|V |, maxℓhℓ/|V |, and maxℓ¯mℓ/ nnz(At).
  • Experimental configuration: The experiments use r = 1 and L = 3 because larger radii quickly expand the inspected region, whereas depth values below three reduce hierarchical benefit.This configuration was selected for the studied graphs.

IV. EXPERIMENTS

The experiments evaluate ComNetX as a local adapter for static and dynamic community detection solvers, comparing it with full-snapshot recomputation and native dynamic baselines. They examine quality–time trade-offs, inspected graph scope, component effects, and stability across update conditions.

  • Experimental design: The evaluation compares ComNetX with full-snapshot recomputation and native dynamic baselines after sequences of graph updates.It focuses on the quality–time trade-off for static and dynamic community detection solvers.
  • Research questions: RQ1 asks whether ComNetX preserves community quality while reducing update time relative to full-snapshot recomputation.
  • Research questions: RQ2 asks whether the same local adaptation can improve or complement native dynamic community detection algorithms.
  • Research questions: RQ3 measures how much of the graph is inspected after neighborhood expansion, community closure, and contraction.
  • Research questions: RQ4 examines how radius expansion, hierarchy depth, feature representation, closure, and contraction control the quality–efficiency trade-off.
  • Research questions: RQ5 assesses stability across different update streams, longer horizons, and adversarially large affected regions.

A. Experimental setup · 1) Datasets and Evaluation Protocols: · 2) Metrics:

The study evaluates ComNetX across six symmetrized real-world networks and controlled dynamic stochastic block model streams using protocols that vary backend coverage, update granularity, and horizon. It measures community quality, external agreement, structural diagnostics, and cumulative processing time.

  • 1) Datasets and Evaluation Protocols:: Six real-world networks with ground-truth labels are symmetrized into undirected graphs, enabling uniform baseline inputs and external clustering evaluation.Ground-truth labels complement modularity with external metrics.
  • 1) Datasets and Evaluation Protocols:: P1 partitions each edge sequence into 1000 coarse batches, initializes on G999, and processes the final batch as ten chronological mini-batches for broad backend coverage.The 999:10 protocol includes expensive GNN baselines.
  • 1) Datasets and Evaluation Protocols:: P2 uses 999:50, 999:100, and 9:500 strategies to test finer update granularity and longer-horizon adaptation from an earlier initial graph.Each p:q strategy splits the final coarse batch into q mini-batches after initializing from p batches.
  • 1) Datasets and Evaluation Protocols:: P3 generates dynamic stochastic block model streams from planted-partition graphs with controlled update layers varying rate and whether changes are random, hub-centered, or community-internal.These conditions produce streams with different affected-region structures.
  • 1) Datasets and Evaluation Protocols:: Because ground-truth partitions have lower modularity than the strongest modularity-optimizing outputs, external agreement is interpreted alongside the structural objective.High-modularity partitions may refine or reorganize label classes without matching them exactly.
  • 2) Metrics:: Modularity Q and final-graph NMI evaluate structural community quality and label agreement, with NMI remaining comparable across differing community counts.NMI is label-permutation invariant.
  • 2) Metrics:: Mean conductance and normalized cut provide complementary structural diagnostics for full and Local Leiden on the two largest 999:10 streams.These metrics are not optimization targets.
  • 2) Metrics:: Total processing time T is cumulative wall-clock time across all measured update mini-batches, excluding data-format conversion and using paired comparisons when repeated measurements exist.Comparisons are paired by dataset, method, and batch strategy.

3) Baselines: … 1) Compatibility Study Across Backends:

The study benchmarks ComNetX across static, feature-aware, and native dynamic backends, using a three-level, radius-one local configuration. Across six real datasets, the adapter substantially reduces runtime while preserving or varying quality depending on the backend and degree of retained global context.

  • 3) Baselines:: The baselines span static full-snapshot solvers, feature-aware graph-clustering models, and native dynamic methods evaluated on the same symmetrized graph sequences.Leidenalg is the main topology-only static baseline, while DMoN, MAGI, S2CAG, and PRGPT variants broaden representation and solver coverage.
  • 3) Baselines:: 100 epochs for MFC, one iteration for FLMIG, and 10 epochs for S2CAG, MAGI, and DMoN define the reported iterative-training configurations.MAGI and DMoN are not assigned ground-truth cluster counts; MAGI selects clusters using a vMF-mixture elbow criterion followed by k-means.
  • 3) Baselines:: The compatibility study covers all six real datasets and implemented baselines, with focused runtime-pressure comparisons among Leidenalg, DF-Leiden, and S2CAG.Complete two-dataset blocks use dyn pubmed and arxivmath, while other backends remain in the breadth study.
  • 4) Configuration of the proposed local adaptation:: Three hierarchy levels and neighborhood radius one expand update endpoints to immediate graph neighbors before affected-community closure.Larger radii can quickly approach the full graph on several datasets, motivating the radius-one default.
  • 4) Configuration of the proposed local adaptation:: Normalized aggregation is used for feature-aware local configurations, with the reported S2CAG compatibility row using dataset features.Table V separately evaluates dataset, random, and one-hot representations.
  • 1) Compatibility Study Across Backends:: Table II compares each conventional Naive or native Dynamic baseline with its locally adapted variant across all protocol P1 datasets.Geometric mean speedups exclude zero-time and out-of-memory entries, and the Local adapter makes the arxivmath MFC, MAGI, and DMoN rows finite.
  • 1) Compatibility Study Across Backends:: 41.9× speedup is reported for Leidenalg on arxivmath, while Local Leiden closely tracks full-snapshot recomputation in aggregate quality.Table III additionally reports 17.1 ± 0.2× on dyn pubmed; quality deltas are computed as adapter minus baseline over finite runs.
  • 1) Compatibility Study Across Backends:: DMoN and MAGI become executable on large graphs because only small neighborhood graphs are materialized on the GPU, while DF-Leiden also benefits from locality on sufficiently large graphs.DMoN is near break-even in aggregate runtime but avoids the full-snapshot out-of-memory failure on arxivmath.

2) Statistical Robustness: · 3) Comparison with Native Dynamic Methods: · 4) Locality and Workload Reduction:

Across repeated runs, ComNetX preserves the qualitative topology-only findings, accelerates feature-aware backends, and can outperform native dynamic methods in some operating regimes without universally dominating them. Locality remains strong at radius one, while backend execution—especially neural processing—limits the benefits of graph-size reduction.

  • 2) Statistical Robustness:: Five paired repetitions of identical 999:10 streams show stable topology-only conclusions, including small Leiden modularity gaps and large speedups.Local rows use fixed three-level, radius-one configurations against corresponding naive or native baselines.
  • 2) Statistical Robustness:: 10.2× runtime reduction and improved modularity on arxivmath show that ComNetX can accelerate a feature-aware S2CAG backend with real attributes.On dyn pubmed, native dynamic DF-Leiden is already efficient, limiting the usefulness of Local DF-Leiden.
  • 2) Statistical Robustness:: 0.128/6.17 to 0.127/5.33 mean conductance/Ncut on dyn pubmed and 0.0011/8.73 to 0.0009/6.96 on arxivmath support the directed Leiden check.The directed streams show the same qualitative pattern as symmetrized rows, with Q = 0.78… on dyn pubmed and essentially unchanged or slightly lower mean conductance.
  • 3) Comparison with Native Dynamic Methods:: 8.4±0.1× speedup on arxivmath and 7.4× at the 500-update horizon show Local DF-Leiden can outperform its native counterpart, but not on dyn pubmed.The 500-update horizon remains faster while losing final NMI on both datasets; MFC runs out of memory on the largest full-dynamic setting.
  • 3) Comparison with Native Dynamic Methods:: Local DF-Leiden improves modularity on both large datasets with nearly neutral aggregate NMI in paired 999:10 rows, but the comparison is not universal dominance.Native dynamic solvers remain important speed baselines when they already process updates efficiently.
  • 4) Locality and Workload Reduction:: Below 5% on all datasets and below 1% on dyn pubmed and arxivmath, radius-one neighborhoods support the default locality setting.At r = 3, these two graphs reach about 27–31% of vertices, while r = 4 exceeds half; ComNetX therefore uses hierarchical community closure instead of deeper expansion.
  • 4) Locality and Workload Reduction:: Sub-percent or near-percent contracted edge fractions demonstrate that hierarchical closure and contraction can produce compact local backend instances, although speedups remain backend-dependent.The locality profiles summarize final-level closure and contracted-edge behavior across dyn cora, dyn pubmed, and arxivmath.
  • 4) Locality and Workload Reduction:: Millisecond-scale expansion, closure, aggregation, and projection leave backend execution dominant for Leiden on arxivmath and every S2CAG row.S2CAG additionally performs feature materialization, sparse tensor construction, and training; on 80 GB A100 GPUs, parallelism can mask graph-size reduction.

5) Ablation Study: · 6) Real-Data Long-Horizon Robustness:

The ablations show that ComNetX’s topology, feature, closure, and contraction choices trade quality against runtime, while contraction preserves context and limits local workload. Long-horizon streams retain substantial speedups, but growing NMI gaps make drift an explicit consideration.

  • 5) Ablation Study:: On dyn pubmed, L = 2, r = 0 achieves Q = 0.783 and 94.5× speedup, while L = 1, r = 1 remains fast at 54.4× with less quality loss.Topology parameters are not monotone quality knobs.
  • 5) Ablation Study:: On arxivmath, L = 1, r = 0 reaches 634.3× speedup with Q = 0.879, despite r ≥1 rows having nearly identical Q ≈0.881.Increasing radius sharply raises runtime while adding little quality on this stream.
  • 5) Ablation Study:: Across γ = 0.5, 1, and 2, Local Leiden achieves 41.6–44.8× speedups on dyn pubmed and 135.9–161.8× on arxivmath.The modularity gaps QLocal −QFull are −0.004, −0.026, and −0.053 on dyn pubmed, versus −0.004, −0.010, and −0.013 on arxivmath.
  • 5) Ablation Study:: The compact random-feature Local S2CAG row is close to the dataset-feature Local row while being cheaper, supporting it as a default when attributes are unavailable or costly.Real features can still help, especially on dyn cora, while random features become competitive mainly on smaller contracted instances.
  • 5) Ablation Study:: Removing closure or contraction can reduce time when overhead dominates, but no contraction creates an instance about 12× larger and loses modularity on dyn cora.On larger graphs, removing closure is fastest but loses substantial modularity, whereas removing contraction can enlarge the backend instance by two orders of magnitude.
  • 6) Real-Data Long-Horizon Robustness:: Protocol P2 varies initial-history fraction and update batches to measure dynamic stability with paired 9:500 topology measurements on dyn pubmed and arxivmath.Table VII reports final modularity, final-snapshot NMI, cumulative time, and Local speedup over the corresponding non-local backend.
  • 6) Real-Data Long-Horizon Robustness:: Local Leiden is about 16× faster than full Leiden on dyn pubmed and about 31× faster on arxivmath in long-horizon streams.The NMI gap grows relative to the ten-update setting, especially on dyn pubmed, so drift must be reported explicitly.

7) Controlled DSBM Stress Test: … VI. CONCLUSION

ComNetX is presented as a solver-agnostic hierarchical framework that preserves community context while localizing dynamic updates. Controlled DSBM stress tests define when locality is beneficial and when larger or hub-heavy updates favor full refreshes.

  • 7) Controlled DSBM Stress Test:: Each DSBM graph contains 100,000 vertices, 32 planted communities, target average degree 58, 1% degree-512 hubs, and assortativity pin = 0.97.The stress suite varies update size and touched-vertex type using controlled edge updates from SBM-style planted-partition snapshots.
  • 7) Controlled DSBM Stress Test:: At 0.05% updates, random and hub-centered streams fall below break-even, whereas community-internal streams remain faster than full recomputation.At the smaller update rate, all three locality patterns are faster than full recomputation.
  • 8) Limitations:: Larger or hub-heavy batches should trigger a full refresh because locality can approach full-snapshot cost or lose boundary context.Communities remain small relative to the graph, but restricted context particularly affects representation-learning backends more than Leiden.
  • V. RELATED WORK: Classical community-detection methods use modularity, information flow, label propagation, or related structural criteria, while Louvain and Leiden combine high modularity with scalability.Infomap and label-propagation methods provide alternative flow- and propagation-based views.
  • V. RELATED WORK: Dynamic community-detection methods trade off snapshot quality, temporal consistency, and update efficiency through incremental, flow-based, evolution-based, and continuous-time approaches.The paper instead targets batched snapshot maintenance and reuse of arbitrary solvers under local updates.
  • V. RELATED WORK: Attributed and GNN-based methods extend community detection beyond topology by combining neural embeddings with modularity or clustering losses.Examples include contrastive learning, neural modularity maximization, structural-entropy objectives, and scalable pre-train-and-refine pipelines.
  • VI. CONCLUSION: ComNetX complements prior work by wrapping static, GNN-based, and native dynamic solvers while restricting computation to affected aggregated subproblems.This addresses the trade-off between costly but expressive reusable solvers and efficient routines specialized to fixed dynamic designs.
  • VI. CONCLUSION: ComNetX preserves a community hierarchy, closes affected regions over contextual communities, and contracts them into compact backend instances.The framework addresses unchanged-region recomputation, limited transferability of specialized dynamic algorithms, and context loss from purely neighborhood-based localization.
Loading 2608.16906v1…