Learning the Latent State Space of Time-Varying Graphs

Nesreen K. Ahmed, Christopher Cole, Jennifer Neville

Learning the Latent State Space of Time-Varying Graphs

Abstract

Dynamic networks, such as university email systems, are non-stationary, with structural properties that drift in response to external real-world events. Traditional analysis often relies on static snapshots or discrete time-aggregation, which can lose temporal dynamics or become overwhelmed by diurnal noise. This paper presents a framework for uncovering the latent states of graph streams by mapping snapshots into a structural state space. We compare a standard discrete aggregation model with a probabilistic "aging" model where edge existence decays over time. Our results, based on seven months of university email logs, demonstrate that the probabilistic model more effectively filters noise and identifies significant global behavioral shifts corresponding to the academic calendar.

Introduction

Communication networks like email, SMS, and social media consist of rapid, short-lived interactions. Analyzing these as "graph streams" is challenging because their properties are non-stationary. Aggregating data over long periods obscures dynamics, while daily snapshots often fail to distinguish between routine local fluctuations and significant global events. We propose a methodology to learn the higher-level "states" of a network, enabling a clearer visualization of its temporal evolution.

Methods

The framework maps a sequence of graph snapshots into a latent state space using two primary components: representation modeling and structural attribute mapping.

  1. Representation Models: We compare a Discrete Model, where edges exist only within fixed 1-day windows, against a Probabilistic Model. In the latter, edges are treated as having a lifetime; the probability of an edge existing decays exponentially: $p_{ij} = \exp(-(t - t')/\tau)$. This allows older interactions to "age out" gracefully.
  2. State-Space Mapping: Each snapshot is characterized by its average degree and average clustering coefficient. These attributes form a 2D space where snapshots are clustered using K-Means into seven distinct states (A-G).
Figure 1: Comparison of the latent state space mapping for discrete (a) and probabilistic (b) models. The probabilistic model produces more distinct, less noisy clusters.

Datasets

The study utilizes email logs from Purdue University mail servers spanning seven months (August 2011 to February 2012). This period encompasses a full academic semester, including Labor Day, Fall Break, Thanksgiving, and Winter Break.

Results and Discussion

The probabilistic model (with $\tau = 12$ days) significantly outperformed the discrete model in tracking global academic events. While the discrete model's state transitions were erratic due to daily noise, the probabilistic model showed clear, sustained shifts into specific states during university breaks.

Figure 2: State transition diagram for the probabilistic model. The network moves into distinct, sustained states (e.g., State A during Winter Break) that align with the university calendar.

As illustrated in Figure 2, the network enters "State A" during the Winter Break, a state characterized by minimal activity. Notably, the framework distinguishes between different types of breaks based on connectivity intensity; for instance, the model labeled Thanksgiving Break and Fall Break as different states (C and A, respectively), reflecting the varying levels of campus activity and the superior filtering of the probabilistic approach.

Conclusion

By treating network interactions as decaying probabilities, we can effectively filter high-frequency noise and reveal the underlying latent states of dynamic graphs. This approach provides a robust tool for monitoring large-scale social systems and identifying significant structural transitions. Future work will investigate the use of these latent states for predictive modeling of future network characteristics.

Summary updated

Abstract

From social networks to Internet applications, a wide variety of electronic communication tools are producing streams of graph data; where the nodes represent users and the edges represent the contacts between them over time. This has led to an increased interest in mechanisms to model the dynamic structure of time-varying graphs. In this work, we develop a framework for learning the latent state space of a time-varying email graph. We show how the framework can be used to find subsequences that correspond to global real-time events in the Email graph (e.g. vacations, breaks, ...etc.). These events impact the underlying graph process to make its characteristics non-stationary. Within the framework, we compare two different representations of the temporal relationships; discrete vs. probabilistic. We use the two representations as inputs to a mixture model to learn the latent state transitions that correspond to important changes in the Email graph structure over time.
BibTeX
@misc{ahmed2014learning,
  author = {Nesreen K. Ahmed and Christopher Cole and Jennifer Neville},
  title = {{Learning the Latent State Space of Time-Varying Graphs}},
  year = {2014},
  eprint = {1403.3707},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1403.3707},
}
Figure