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

Krzysztof Turowski, Jithin K. Sreedharan, Wojciech Szpankowski

This paper, titled "Temporal Ordered Clustering in Dynamic Networks," tackles a fascinating "detective" problem in data science: if you are given a single snapshot of a network (like a social network or a citation graph) without any timestamps, can you figure out the order in which the nodes arrived?

TL;DR

The authors propose a framework to reconstruct the history of a dynamic network by grouping nodes into chronologically ordered clusters. By combining an optimization framework with a novel "reverse-engineering" sampling technique, they can accurately infer the relative age of nodes even in complex networks where traditional methods, like looking at node degrees, completely fail.

What Problem Does This Paper Address?

Most research on dynamic networks assumes we have a "movie" of the network's growth. In reality, we often only have a "still photo"—the final snapshot. Inferring the arrival order of nodes from this snapshot is critical for identifying the source of a rumor, tracking the evolution of biological proteins, or understanding how information spreads.

The challenge is twofold:

  1. Symmetry: In many networks, multiple nodes are structurally indistinguishable. You can't tell which of two identical-looking nodes arrived first.
  2. Heuristic Failure: A common "folk" rule is that older nodes have more connections (higher degree). However, in many realistic growth models—like the "duplication-divergence" model used in biology—this rule is frequently broken, making simple sorting algorithms useless.

The authors address this by moving away from trying to find a perfect 1-to-N ranking. Instead, they aim for Temporal Ordered Clustering: partitioning nodes into ordered groups ($C_1 \prec C_2 \prec \dots \prec C_K$) where everyone in $C_1$ is older than everyone in $C_2$, and so on.

Methods

The authors treat the problem as a constrained optimization task.

  • Optimization Framework: They define "precision" (the fraction of correctly ordered pairs) and "density" (how many pairs the model attempts to order). They initially formulate this as a complex Integer Program (IP) to find the best clusters.
  • Linear Programming (LP) Relaxation: Because the IP is computationally "heavy" ($O(n^{12})$), they relax it into a more manageable Linear Program ($O(n^7)$) that focuses on partial orders.
  • Sequential Importance Sampling (SIS): To solve the LP, they need to know the probability $p_{u,v}$ that node $u$ is older than node $v$. They develop an SIS procedure that "unwinds" the network, starting from the final snapshot and stripping away nodes one by one to estimate these probabilities.
  • Semi-Supervised Learning: They introduce a way to incorporate "perfect pairs"—small amounts of known historical data—to prune the search space and significantly improve the accuracy of the sampling.

Datasets

The researchers evaluated their algorithms on both synthetic and real-world data:

  • Synthetic: Networks generated using the Duplication-Divergence (DD) model. This model is a "stress test" because it creates many symmetries and doesn't follow the "older is bigger" degree trend.
  • ArXiv: A citation network of physics papers where the "ground truth" is the publication date.
  • Simple English Wikipedia: A dynamic network of hyperlinks between articles.
  • CollegeMsg: A private messaging network from a university social platform.

Key Insights and Ideas

  • Clustering as a Necessity: Because of graph symmetries, a total ordering is often mathematically impossible. Clustering isn't just a convenience; it's the only statistically sound way to represent the history of a symmetric graph.
  • The "Aha" on Degree: The paper proves that in the DD model, the oldest nodes are not necessarily the ones with the most edges. This explains why standard greedy algorithms fail and justifies the need for their probabilistic approach.
  • The Power of 1%: One of the most striking findings is that providing the algorithm with just 1% of the true arrival order (semi-supervised) leads to a massive jump in precision. This is because a few known labels can "break" the structural symmetries that otherwise confuse the model.

Key Results

  • Efficiency: The LP-partial-order approach provides nearly identical precision to the full cluster-based IP but runs orders of magnitude faster.
  • Superiority over Greedy: On real-world networks like ArXiv and Wikipedia, the proposed sort-by-pu,v-sum algorithm significantly outperformed greedy baselines (like sorting by degree or neighborhood structure).
  • Near-Perfect Inference: In semi-supervised tests, the model achieved near-perfect clustering (precision close to 1.0) on the ArXiv and Wikipedia datasets with very little training data.

Limitations and Future Work

  • Computational Scaling: While $O(n^7)$ is better than $O(n^{12})$, it is still quite demanding for massive networks with millions of nodes. Further "bookkeeping" optimizations are needed for web-scale graphs.
  • Model Knowledge: The current sampling method requires some knowledge of the underlying growth model (e.g., knowing the network grew via duplication).
  • Dynamic Complexity: The current work focuses on networks that only grow. The authors suggest that future work should tackle "churn"—networks 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},
}

Loading related content...

Figure