PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable dynamic community detection on temporal graphs using graph neural networks

Peijie Zhong, Raul Mondragon, Richard G. Clegg

arXiv:2608.28342v1cs.SI

TL;DR

Dynamic community detection must capture changing memberships at fine temporal resolution while remaining scalable. The paper learns node-time embeddings with diffusion-guided contrastive supervision and clusters them, outperforming static baselines and competing dynamically while scaling to large temporal networks. Synthetic evaluations and an OpenAlex collaboration case study support the approach’s usefulness for evolving communities.

  • Problem

    Dynamic community detection requires labels for evolving node memberships, but snapshot methods depend on predefined windows and link-stream optimization expands over node-time assignments.

  • Method

    The method assigns labels to observed node-time instances, learns low-dimensional embeddings with a temporal encoder and diffusion-guided contrastive learning, then clusters the embedding space.

  • Results

    The method outperforms static baselines and is competitive or better than existing dynamic methods on synthetic temporal networks using AMI and ARI, while maintaining scalability.

  • Takeaways & Limitations

    Time-node-level representation learning provides an effective framework for scalable dynamic community detection and reveals evolving collaboration communities in a large OpenAlex network.

  • Takeaways & Limitations

    Reliable node-time ground-truth community labels are difficult to obtain in real temporal networks, so quantitative evaluation mainly relies on synthetic networks.

Abstract

from arXiv · show

Dynamic community detection on temporal graphs seeks to identify evolving community structures while allowing node memberships to change over time. In this work, we formulate dynamic community detection over observed node-time instances, where each node-time instance in the temporal interaction stream is assigned a cluster label. We propose a diffusion-guided contrastive learning framework that uses a local temporal diffusion affinity matrix to construct positive and negative node-time pairs and organise the learned representations according to their temporal structural relationships. We then apply a clustering algorithm to the resulting embedding space to detect dynamic communities. Experiments on synthetic temporal networks show that the proposed method outperforms static community detection baselines and achieves competitive or better performance than existing dynamic community detection methods in terms of AMI and ARI, while maintaining good scalability. We further apply the method to a large-scale OpenAlex computer science collaboration network from 2016 to 2025, revealing persistent and evolving collaboration communities in real scientific data. These results suggest that time-node-level representation learning provides an effective framework for scalable dynamic community detection on temporal graphs.

1 Introduction

Temporal interactions can change node roles and community memberships, making fixed node labels or static aggregation inadequate. The paper proposes scalable node-time representation learning with diffusion-guided contrastive supervision, followed by clustering.

  • Motivation: Temporal interactions evolve continuously, so a node’s structural role and community membership may change over time.Static labels assigned across the full observation period can therefore miss evolving temporal structure.
  • Motivation: Aggregating a link stream into a static graph may obscure temporal changes in community structure.
  • Approach: The framework assigns labels to observed node-time instances, allowing the same node to receive different labels in different interaction contexts.This preserves fine temporal resolution while representing dynamic membership explicitly.
  • Approach: Low-dimensional node-time representations are learned with a temporal graph encoder and mini-batch optimization rather than direct search over all assignments.
  • Approach: Diffusion-guided contrastive learning organizes representations using local temporal structural relationships, after which a clustering algorithm detects dynamic communities.

2 Related work

Prior work spans static clustering, snapshot-based temporal methods, link-stream optimization, and temporal representation learning, but each leaves limitations for fine-grained scalable dynamic community detection. The proposed approach combines node-time embeddings, local temporal structure, and mini-batch optimization.

  • Prior approaches: Static methods assign one community label per node, whereas dynamic methods allow memberships to vary over time.
  • Node clustering and community detection: Representation learning can support community detection when embeddings preserve the structural relationships that define communities.
  • Snapshot-based detection: Snapshot-based approaches may also require additional treatment when the node set changes substantially, complicating modeling and optimization.
  • Snapshot-based detection: Snapshot-based methods capture temporal evolution but depend on window widths and boundaries that determine which interactions are aggregated.
  • Link-stream detection: Link-stream methods preserve fine-grained temporal information without human-chosen windows, but node-time assignments substantially enlarge the optimization space.
  • Position of this work: The proposed method combines temporal encoders, local temporal random-walk structure, and mini-batch optimization for scalable dynamic community detection.

3 Method

The method formulates temporal community detection as clustering observed node-time instances and integrates temporal representation learning with diffusion-based structural supervision.

  • Framework: The framework defines continuous-time temporal graphs as link streams and clusters observed node-time instances.
  • Framework: Its architecture combines temporal representation learning with diffusion-based structural supervision to learn community-aware node-time embeddings.

3.1 Problem definition

The paper models temporal community detection as assigning labels to observed node-time instances rather than fixed nodes, allowing memberships to change over time.

  • A temporal graph is represented as timestamped interactions whose topology is defined by time-ordered events rather than one fixed adjacency matrix.
  • A node-time instance is an occurrence of a node participating in at least one interaction at a particular timestamp.
  • Dynamic communities assign labels to observed pairs (u,t), so the same node can receive different labels at different times.
  • Synthetic datasets can be evaluated against planted community assignments, whereas real-world temporal networks generally lack ground-truth labels.

3.2 Model structure

The model learns node-time embeddings with a TGAT encoder trained by diffusion-based contrastive and structural matching losses, then clusters those embeddings into dynamic communities.

  • The framework maps nodes into an identity space and combines node identity with timestamps to produce time-varying node-time embeddings.
  • Contrastive loss uses diffusion affinity to pull temporally close nodes together and separate distant nodes.
  • Structural matching loss relates embedding distances to the similarity of diffusion characters around nodes at a given time.
  • Structure-aware mini-batches sample local temporal windows, select roots, and use diffusion-based procedures to obtain locally connected nodes.
  • After training, the learned node-time embedding space is partitioned, assigning each node at a time the cluster containing its embedding.

3.3 Initialisation

The method normalizes timestamps to make temporal encoding comparable across datasets and uses random node vectors because node attributes are unavailable.

  • Each temporal interaction is represented as a triple (u,v,t), with two interacting nodes and their interaction timestamp.
  • Min-max normalization maps timestamps into [0, 1], assigning zero to the earliest interaction and one to the latest.
  • Normalized time distances support exponential decay exp(−|t_2 − t_1|/τ), so temporally closer events receive more influence.
  • Because the studied datasets lack node attributes, each node receives a randomly initialized vector serving as a distinct identifier.

3.4 Temporal graph encoder

A TGAT encoder maps each node-time instance to an embedding by aggregating temporally local neighbors on both sides of the instance timestamp.

  • TGAT maps a node-time instance i=(u_i,t_i) into an embedding z_i in the node-time embedding space.
  • Unlike causal link-prediction TGAT, this offline clustering encoder uses a time-centred local neighborhood around each instance.
  • For each instance, the encoder selects incident interactions before and after its timestamp whose timestamps are closest to it.
  • Multi-layer temporal attention aggregates these local temporal neighbors to produce the node-time representation.

3.5 Sampling structure-aware mini-batch

The method builds structure-aware mini-batches by converting local high-order diffusion affinities into positive node-time neighborhoods and sampling their observed timestamps around a centre time.

  • Diffusion affinity construction: The local graph aggregates temporal edges within a symmetric window around centre time t_c, with temporal decay controlled by τ.The resulting transition matrix captures first-order movement on the local temporal graph.
  • Diffusion affinity construction: The ℓ-order diffusion affinity combines direct adjacency with multi-step diffusion to capture high-order temporal structural proximity.It represents interaction strength between node pairs in the temporal neighbourhood around t_c.
  • Residual neighbourhoods: The degree-corrected null model identifies node pairs whose observed high-order affinity is stronger or weaker than expected from their marginal strengths.Positive residuals define structurally associated nodes, while negative values indicate weaker-than-expected affinity.
  • Residual neighbourhoods: Root nodes are sampled according to high-order strength, giving stronger local activity higher probability while diversifying regions selected across mini-batches.For each root, the positive-residual neighbourhood is obtained from the corresponding row of B(t_c).
  • Node-time mini-batches: Sampled nodes are mapped back to observed node-time instances within the temporal window, with timestamps sampled without replacement and capped at N_s.Sampling probabilities are proportional to the temporal weighting, allowing one node to contribute multiple observed times.
  • Node-time mini-batches: The resulting mini-batch defines positive sets for each node-time instance from the sampled structure-aware relationships.

3.6 Training signals

Training combines diffusion-guided contrastive learning with structure matching so TGAT embeddings reflect both sampled positive relationships and high-order diffusion similarity.

  • Diffusion-guided contrastive learning: The contrastive objective pulls positive node-time embeddings together and pushes negative pairs apart within each mini-batch.It assigns each instance higher relative similarity to positives than to other batch instances.
  • Structure matching: The structure-matching objective compares TGAT similarities with similarities between diffusion-distribution signatures.CountSketch provides a lower-dimensional representation because direct comparison of high-dimensional distributions is expensive.
  • Structure matching: Node-time instances sharing an underlying node and centre time share a diffusion distribution, while sampling weights modify their training contributions.
  • Structure matching: Similarity alignment uses non-diagonal mini-batch pairs and standardises the TGAT and CountSketch similarities to account for different scales.
  • Model training: The total loss L_tot = L_CL + L_matching updates TGAT, which maps each node identity and time to a position in node-time space over fixed training epochs.

3.7 Clustering and creation of communities

After training, the TGAT encoder produces embeddings for observed node-time instances, which K-means clusters into labels that can vary for the same node across time.

  • Embedding generation: The trained TGAT encoder produces an embedding vector for every observed node-time instance, capturing learned temporal interaction patterns and structural relationships.
  • Clustering: K-means clusters the node-time embedding set Z into K communities.
  • Dynamic community labels: Each node-time instance receives a community label, allowing one node to belong to different communities at different time points.Instances with similar temporal interaction patterns and diffusion structures are grouped together.

4 Datasets

The evaluation uses synthetic temporal networks with controlled evolving communities and a large OpenAlex collaboration network to assess recovery, scalability, and interpretability.

  • Dataset rationale: Reliable node-time community ground truth is difficult to obtain in real temporal networks, so quantitative evaluation mainly uses synthetic networks with controlled dynamic structure.The OpenAlex network is used as a real-world case study for scalability and interpretability.
  • Synthetic temporal networks: The synthetic generator first creates layer-wise community memberships whose dependencies can preserve, shift, or reorganise communities across layers.
  • Synthetic temporal networks: Candidate node pairs are divided into intra- and inter-community pairs, while μ controls the proportion of inter-community interactions and the link-node ratio controls network scale.
  • Synthetic temporal networks: Poisson event arrivals transform discrete multilayer community structure into a temporal link stream with monotonically increasing timestamps.Inter-event times are drawn from an exponential distribution and cumulatively summed.
  • OpenAlex collaboration network: The OpenAlex dataset contains 6,524,460 computer-science-labelled works published between 2016 and 2025, although its LLM classification includes some adjacent or unrelated disciplines.
  • OpenAlex collaboration network: The cleaned records form a temporal co-authorship link stream in which authors are nodes and publication times define co-authorship links; topic metadata supports community interpretation.Major subfields include Artificial Intelligence, Information Systems, and Signal Processing.

5 Experiments and results

Experiments evaluate dynamic community detection using node-time AMI and ARI on synthetic networks, runtime scalability, ablations, and a large OpenAlex collaboration network. The proposed method generally maintains strong accuracy and scalability while capturing evolving community structure.

  • Evaluation metrics: AMI and ARI evaluate predicted versus ground-truth community partitions over observed node-time pairs rather than fixed node labels.AMI corrects mutual information for random agreement, while ARI compares pairwise grouping relations under a permutation model.
  • Synthetic temporal networks: Static baselines generally underperform dynamic methods on AMI and ARI, especially when community structure changes more frequently across time layers.Static methods assign one fixed label or representation per node, whereas dynamic methods model changing memberships.
  • Synthetic temporal networks: The proposed method achieves the best or near-best AMI and ARI as network size increases, with relatively small performance fluctuations.At p=0.8, μ=0.2, and 10 time slices, missing LAGO results at larger scales indicate runs exceeded the 60-minute limit.
  • Ablation study: The full model achieves the highest mean AMI and ARI in every ablation setting, while removing either training objective consistently reduces performance.The contrastive-learning and matching objectives provide complementary supervision, and their relative contributions depend on graph configuration.
  • Runtime scalability: Dynamic community detection methods require more computation than static or snapshot-based methods, which generally have lower runtime at large temporal-network scales.Louvain is efficient because it aggregates the graph, while LAGO becomes infeasible at larger scales and GenLouvain loses fine-grained temporal information through layer discretisation.
  • Runtime scalability and case study: The proposed method keeps runtime close to TGC while extending node representations to node-time clustering, balancing scalability with dynamic clustering accuracy.The OpenAlex case study also reveals a persistent community, an early merge, and a later split into two major branches around 2020.

6 Conclusions

The framework formulates dynamic community detection as fine-grained time-node clustering and performs well against static and dynamic methods on synthetic networks. On real data, it produces stable assignments and reveals evolving community patterns without fixed time-window assumptions.

  • 6 Conclusions: Time-node clustering assigns community labels to node occurrences at interaction timestamps, allowing memberships to change more finely than static or time-window clustering.The same node can receive different labels at different times.
  • 6 Conclusions: The method better predicts known synthetic community labels than the tested alternatives, while static methods are faster but perform poorly when communities evolve.GenLouvain is competitive for few, slowly changing time slices but performs poorly with rapid change and many slices.
  • 6 Conclusions: LAGO handles rapidly changing networks more consistently, but performs worse than the proposed method at reproducing ground truth and does not scale to larger networks.
  • 6 Conclusions: On a real network without ground truth, the method produces similar assignments across starting seeds and reveals growth of the largest community and a merger forming the second largest.The analysis does not assume fixed time windows while addressing realistic dataset sizes.
Loading 2608.28342v1…