Score-matching-based Structure Learning for Temporal Data on Networks

Hao Chen, Kai Yi, Lin Liu, Yu Guang Wang

Introduction

Causal discovery—the task of identifying Directed Acyclic Graphs (DAGs) from observational data—is essential for understanding complex systems in fields ranging from genomics to economics. While recent "score-matching" methods have shown promise in handling nonlinear relationships via Additive Noise Models (ANMs), they face significant limitations. Specifically, they often suffer from a computational bottleneck during the "pruning" phase, which scales cubically ($O(d^3)$) with the number of variables. Furthermore, most existing tools assume data is independent and identically distributed (i.i.d.), failing to account for the temporal dependencies and network interference common in real-world social or biological systems.

The PICK Framework

To address these challenges, the authors propose PICK (Parent Identification-based Causal structure learning for both i.i.d. and temporal data on networKs). Unlike traditional methods that generate a dense graph and prune it post-hoc, PICK integrates parent identification into the topological ordering process.

The PICK algorithm framework and the underlying intuition for parent identification.

The algorithm follows a "find-and-remove" loop. It identifies leaf nodes (nodes with no children) one by one, immediately finds their parents, and removes them from the system. This approach bypasses the expensive $O(d^3)$ pruning step, leading to a significant speedup. To handle network data, PICK utilizes a Structural Vector Autoregressive (SVAR) model that incorporates a sample-wise adjacency matrix, allowing it to model how interconnected units influence each other over time.

Pseudocode for the PICK-t algorithm, detailing the score function estimation and variance-based parent identification.

Core Intuition: Variance as a Structural Signal

The central innovation of PICK is its use of the score function's variance to identify causal structure. In this context, the "score" is defined as the gradient of the log-likelihood of the data.

The authors observed a key mathematical property: the variance of a node's score function is influenced by its children. When a leaf node is identified and removed, the variance of the score function for its parent nodes decreases, while the variance for non-parent nodes remains unchanged. This "variance drop" serves as a reliable signal for parentage, transforming a complex optimization problem into a series of simple variance comparisons.

Experimental Results

The researchers evaluated PICK against synthetic and real-world benchmarks, demonstrating its efficiency and robustness:

  • Computational Efficiency: In static i.i.d. tests, PICK was approximately 10 times faster than existing score-matching methods like SCORE or GraNDAG. It scaled gracefully to 500 nodes, a regime where many nonlinear methods become computationally prohibitive.
  • Real-World Accuracy: On a temporal Yelp dataset (analyzing restaurant ratings and customer flow), PICK correctly identified causal links with a Structural Hamming Distance (SHD) of 0. In contrast, baselines like GraphNOTEARS and LASSO failed to recover the correct structure.
  • Theoretical Soundness: The authors provided proofs showing that PICK is "provably consistent," meaning it is guaranteed to recover the true DAG structure as the sample size increases, provided mild assumptions are met.

Conclusion

PICK represents a significant advancement in causal discovery by leveraging the structural information embedded in score function variance. By integrating parent identification into the ordering process and accounting for network interference, it provides a fast, scalable, and accurate solution for complex temporal data. Future work may involve extending this approach to non-stationary data or systems with non-additive noise.

Summary updated

Abstract

Causal discovery is a crucial initial step in establishing causality from empirical data and background knowledge. Numerous algorithms have been developed for this purpose. Among them, the score-matching method has demonstrated superior performance across various evaluation metrics, particularly for the commonly encountered Additive Nonlinear Causal Models. However, current score-matching-based algorithms are primarily designed to analyze independent and identically distributed (i.i.d.) data. More importantly, they suffer from high computational complexity due to the pruning step required for handling dense Directed Acyclic Graphs (DAGs). To enhance the scalability of score matching, we have developed a new parent-finding subroutine for leaf nodes in DAGs, significantly accelerating the most time-consuming part of the process: the pruning step. This improvement results in an efficiency-lifted score matching algorithm, termed Parent Identification-based Causal structure learning for both i.i.d. and temporal data on networKs, or PICK. The new score-matching algorithm extends the scope of existing algorithms and can handle static and temporal data on networks with weak network interference. Our proposed algorithm can efficiently cope with increasingly complex datasets that exhibit spatial and temporal dependencies, commonly encountered in academia and industry. The proposed algorithm can accelerate score-matching-based methods while maintaining high accuracy in real-world applications.
BibTeX
@misc{chen2024score,
  author = {Hao Chen and Kai Yi and Lin Liu and Yu Guang Wang},
  title = {{Score-matching-based Structure Learning for Temporal Data on Networks}},
  year = {2024},
  eprint = {2412.07469},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2412.07469},
}
Figure