Tracking Time-varying Graphical Structure

Erich Kummerfeld, David Danks

Introduction

Learning the structure of graphical models—such as Bayesian networks or causal graphs—is a foundational task in machine learning. However, most traditional algorithms assume a static environment, an assumption that frequently fails in real-world scenarios like financial markets or biological systems. To address this, researchers have introduced LoSST (Locally Stationary Structure Tracker), a novel algorithm designed to learn graphical structures from data streams where the underlying process changes over time. LoSST detects structural shifts in real-time and updates its model accordingly, achieving performance comparable to batch methods in stable settings while significantly outperforming them when the system is in flux.

The Challenge of Shifting Environments

Most algorithms for learning graphical models rely on a fundamental assumption: global stationarity. They assume that the "rules" generating the data never change. In reality, processes are often only locally stationary, meaning they remain stable for a period before abruptly or gradually shifting to a new state.

When a standard "batch" algorithm is fed a dataset containing a structural shift, it attempts to find a single model that explains the entire history. The result is often a "blurry" mess of spurious correlations that accurately represents neither the old nor the new state. Furthermore, many modern applications require online learning, where systems must update their understanding as each new data point arrives, rather than waiting for massive batches of data to be collected and processed offline.

How LoSST Works

The core of the paper is the LoSST algorithm, which functions as an intelligent "wrapper" for existing structure-learning tools (specifically the PC algorithm). Its primary innovation lies in how it tracks the "sufficient statistics" (means and covariances) of a continuous data stream:

  1. Differential Weighting: Instead of treating every historical data point equally, LoSST assigns a dynamic weight to each new point.
  2. Change Detection via Mahalanobis Distance: For every incoming data point, the algorithm calculates its Mahalanobis distance—a statistical measure of how "surprising" the point is given the current model.
  3. The "Aha!" Moment: If a sequence of points consistently shows a poor fit (high distance), LoSST assumes the underlying structure has changed. It then increases the weight of recent points, effectively "washing out" the influence of obsolete historical data.
  4. Pooled p-values: To distinguish between a random, temporary outlier and a genuine structural shift, LoSST uses Liptak’s method to pool p-values over time.
  5. Probabilistic Relearning: Relearning a graph at every single step is computationally prohibitive. Instead, LoSST uses a "noisy-OR" gate mechanism to trigger a full structure-learning update more frequently when a change is suspected, and less frequently during periods of stability.

Experimental Results: Synthetic and Real-World Data

The authors evaluated LoSST using both synthetic Structural Equation Models (SEMs) and real-world economic data.

In simulations using synthetic SEMs (ranging from 4 to 20 variables), the researchers tested scenarios where graph edges were added, removed, or flipped at the 1000th data point. Standard batch algorithms saw their error rates skyrocket and remain high after the shift. LoSST, however, detected the change and typically stabilized on the correct new model within roughly 250 data points.

LoSST vs. Batch performance on structural changes at data point 1000.

For real-world validation, the team used U.S. Bureau of Labor Statistics (BLS) price index volatility data (1967–2011) covering six variables (Apparel, Food, Housing, Medical, Other, and Transportation). LoSST successfully detected historical economic shifts, such as the "Great Moderation"—a well-documented period of decreased economic volatility starting in the early 1980s—as well as a subsequent shift following the 2001 recession.

Mahalanobis distance tracking for US price volatility data, highlighting structural shifts.

Crucially, the algorithm ignored one-off spikes (outliers) while responding accurately to sustained changes in the relationships between price categories.

Key Insights

  • Diligence vs. Convergence: The authors highlight a fundamental trade-off in machine learning. A convergent algorithm eventually ignores noise to settle on a single "truth," while a diligent algorithm remains sensitive enough to detect ongoing changes. LoSST allows researchers to tune this trade-off via specific parameters.
  • No "Online Penalty": One of the most important findings is that LoSST performs just as well as standard batch algorithms when the environment is stable. There is no accuracy cost to using LoSST in "normal" situations, but it provides a massive benefit when things change.
  • Memory Efficiency: Because it only tracks moving statistics and doesn't need to store the entire history of raw data, LoSST is highly efficient for very large or infinite data streams.

Limitations and Future Directions

While powerful, LoSST assumes local stationarity. If a system's structure changes extremely rapidly (e.g., every few data points), the algorithm won't have enough time to accumulate the statistics needed to learn the new structure. Additionally, the current implementation focuses on continuous variables and linear relationships. Extending this framework to discrete Bayesian networks with conditional probability tables is a noted area for future research, though it will likely carry higher computational costs. Finally, the authors suggest that some of the heuristic components, like the specific weight-transformation function, could be refined into purely Bayesian versions in future iterations.

Summary updated

Abstract

Structure learning algorithms for graphical models have focused almost exclusively on stable environments in which the underlying generative process does not change; that is, they assume that the generating model is globally stationary. In real-world environments, however, such changes often occur without warning or signal. Real-world data often come from generating models that are only locally stationary. In this paper, we present LoSST, a novel, heuristic structure learning algorithm that tracks changes in graphical model structure or parameters in a dynamic, real-time manner. We show by simulation that the algorithm performs comparably to batch-mode learning when the generating graphical structure is globally stationary, and significantly better when it is only locally stationary.
BibTeX
@inproceedings{kummerfeld2013tracking,
  author = {Erich Kummerfeld and David Danks},
  title = {{Tracking Time-varying Graphical Structure}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
}
Figure