Temporal Ordered Clustering in Dynamic Networks: Unsupervised and Semi-Supervised Learning Algorithms

Krzysztof Turowski, Jithin K. Sreedharan, Wojciech Szpankowski

Abstract

In temporal ordered clustering, given a single snapshot of a dynamic network in which nodes arrive at distinct time instants, we aim at partitioning its nodes into $K$ ordered clusters $\mathcal{C}_1 \prec \cdots \prec \mathcal{C}_K$ such that for $i < j$, nodes in cluster $\mathcal{C}_i$ arrived before nodes in cluster $\mathcal{C}_j$. This problem is significant for applications like tracking fake news or information spread. We formulate an integer programming framework to find optimal clustering as a strict partial order set, achieving high precision for a fixed density. We develop a sequential importance procedure and design unsupervised and semi-supervised algorithms to approximate the optimal solution. Our methods are validated on synthetic (vertex copying model) and real-world networks (ArXiv, Wikipedia), demonstrating superior performance over traditional heuristics.

Introduction

Inferring the arrival order of nodes from a single network snapshot—a "still photo" of a dynamic process—is a critical challenge in data science. Unlike scenarios where a full history is available, researchers often only have the final state. Determining node age is essential for identifying the source of rumors, tracking biological evolution, or understanding information cascades.

Traditional heuristics, such as the "older is bigger" rule (where degree correlates with age), often fail in complex growth models like the duplication-divergence (DD) model common in biological networks. Furthermore, structural symmetries in graphs often make a total 1-to-N ranking mathematically impossible. To address these issues, we propose Temporal Ordered Clustering: partitioning nodes into chronologically ordered groups where every node in an earlier cluster is older than those in subsequent clusters.

Figure 3: Illustration of the temporal ordered clustering process, from a raw snapshot (a) to identified ordered clusters (b, c).

Methodology

The problem is framed as a constrained optimization task aimed at maximizing precision (correctly ordered pairs) for a given density (total pairs ordered).

Optimization and Relaxation

We initially formulate the problem as an Integer Program (IP). However, due to its high computational complexity ($O(n^{12})$), we introduce a Linear Programming (LP) relaxation ($O(n^7)$) that focuses on finding a partial order. This partial order represents the temporal dependencies between nodes as a directed acyclic graph (DAG).

Figure 4: Directed graph representing partial temporal orders between nodes, where arrows indicate 'older than' relationships.

Sequential Importance Sampling (SIS)

To estimate the probability $p_{u,v}$ that node $u$ is older than node $v$, we develop a Sequential Importance Sampling (SIS) procedure. This method "unwinds" the network by iteratively removing nodes from the final snapshot, effectively reverse-engineering the growth process.

Semi-Supervised Learning

We also introduce a semi-supervised approach that incorporates a small fraction of "perfect pairs" (known historical data). This additional information helps prune the search space and resolve structural symmetries that typically confound unsupervised methods.

Experimental Evaluation

The proposed algorithms were evaluated on several datasets:

  • Synthetic (DD Model): Used as a stress test due to its high symmetry and non-monotonic degree-age relationship.
  • ArXiv Citation Network: A real-world network where publication dates provide the ground truth.
  • Simple English Wikipedia: A network of hyperlinks between articles.
  • CollegeMsg: A private messaging network.

Key Results

  • Performance: The LP-based partial order approach achieved precision nearly identical to the full IP while being significantly faster.
  • Heuristic Comparison: On ArXiv and Wikipedia, our probabilistic sorting algorithm outperformed standard baselines like degree-based sorting.
  • Impact of Supervision: Providing just 1% of the true arrival order led to a dramatic increase in precision, as these labels "break" the structural symmetries in the graph.

Conclusion

Temporal ordered clustering provides a statistically sound framework for reconstructing network history when total ordering is impossible. Our work demonstrates that even in models where degree is a poor proxy for age, probabilistic "unwinding" and partial order optimization can accurately recover chronological structure. Future work will focus on scaling these methods to massive graphs and accounting for network "churn," where nodes and edges are both added and deleted over time.

Summary updated

Abstract

In <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">temporal ordered clustering</i> , given a single snapshot of a dynamic network in which nodes arrive at distinct time instants, we aim at partitioning its nodes into <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$K$</tex-math></inline-formula> ordered clusters <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {C}_1 \prec \cdots \prec \mathcal {C}_K$</tex-math></inline-formula> such that for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$i&lt; j$</tex-math></inline-formula> , nodes in cluster <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {C}_i$</tex-math></inline-formula> arrived before nodes in cluster <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {C}_j$</tex-math></inline-formula> , with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$K$</tex-math></inline-formula> being a data-driven parameter and not known upfront. Such a problem is of considerable significance in many applications ranging from tracking the expansion of fake news to mapping the spread of information. We first formulate our problem for a general dynamic graph, and propose an integer programming framework that finds the optimal clustering, represented as a strict partial order set, achieving the best precision (i.e., fraction of successfully ordered node pairs) for a fixed density (i.e., fraction of comparable node pairs). We then develop a sequential importance procedure and design unsupervised and semi-supervised algorithms to find temporal ordered clusters that efficiently approximate the optimal solution. To illustrate the techniques, we apply our methods to the vertex copying (duplication-divergence) model which exhibits some edge-case challenges in inferring the clusters as compared to other network models. Finally, we validate the performance of the proposed algorithms on synthetic and real-world networks.
BibTeX
@article{turowski2021temporal,
  author = {Krzysztof Turowski and Jithin K. Sreedharan and Wojciech Szpankowski},
  title = {{Temporal Ordered Clustering in Dynamic Networks: Unsupervised and Semi-Supervised Learning Algorithms}},
  journal = {IEEE Trans. Network Science \& Engineering},
  year = {2021},
  doi = {10.1109/tnse.2021.3058376},
}
Figure