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

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

TL;DR

This paper introduces PICK, a novel score-matching algorithm for causal discovery in temporal network data. PICK significantly speeds up existing methods by introducing an efficient parent-finding subroutine for leaf nodes, making it more scalable for complex, real-world datasets with spatial and temporal dependencies.

What Problem Does This Paper Address?

Identifying causal relationships from data is a fundamental challenge across many scientific and industrial domains. While various causal discovery algorithms exist, score-matching methods have shown promise, especially for nonlinear models. However, these methods are typically limited to static, independent and identically distributed (i.i.d.) data and suffer from high computational costs, particularly during the "pruning" phase required for dense graphs. This bottleneck hinders their application to complex, dynamic systems like temporal networks where data points are not independent and exhibit spatial and temporal correlations. The paper aims to bridge this gap by developing a more efficient and scalable score-matching approach for temporal network data.

Methods

The core innovation of this paper is a new parent-finding subroutine designed to accelerate the pruning step in score-matching algorithms. This subroutine leverages the observation that the variance of a node's score function is influenced by its own variability and that of its children. By analyzing how this variance changes when a potential parent node is removed, the algorithm can efficiently identify the true parents of "leaf" nodes (nodes with no outgoing causal edges).

This subroutine is integrated into a new algorithm called PICK (Parent Identification-based Causal structure learning). PICK extends existing score-matching techniques to handle:

  • Temporal Data: It accounts for dependencies across time steps.
  • Network Interference: It models how nodes within a network can influence each other.
  • Nonlinear Additive Noise Models (ANMs): It is not restricted to linear relationships.

The algorithm iteratively identifies leaf nodes, determines their parents using the novel subroutine, and then prunes the graph. This process is repeated until the causal structure is learned.

Datasets

The paper evaluates PICK on:

  • Synthetic Data: Three types of synthetic datasets were generated to simulate various scenarios, including different nonlinear functions (sine-based and Gaussian processes) and graph structures.
  • Real-World Data:
    • Yelp Dataset: A dataset of restaurant reviews from 2021 was used to model causal relationships between restaurant rating, opening hours, and customer flow, considering geographical proximity as a proxy for network influence.
  • Schs Dataset: A commonly used real-world dataset for biological network analysis.
  • SynTReN Datasets: 10 pseudo-real-world datasets generated from a synthetic gene regulatory network generator.

Key Insights and Ideas

  • Variance of Score Function as a Causal Indicator: The paper ingeniously connects the variance of a node's score function to its causal relationships. This provides a novel way to identify parents, especially for leaf nodes.
  • Efficiency Through Leaf Node Focus: By specifically targeting leaf nodes, the algorithm avoids the computationally intensive full graph pruning, leading to significant speedups.
  • Bridging Static and Temporal Causal Discovery: PICK's ability to handle both static and temporal data on networks unifies these previously distinct problem settings within a single framework.
  • Scalability for Complex Systems: The proposed method addresses the critical need for scalable causal discovery in increasingly complex, dynamic systems prevalent in academia and industry.

Key Results

  • Significant Speedup: PICK is reported to be approximately 10 times faster than existing score-matching methods on static i.i.d. data.
  • High Accuracy: The algorithm maintains high statistical accuracy comparable to or exceeding baseline methods, even on complex temporal network data with interference.
  • Real-World Performance: On the Yelp dataset, PICK predicted the causal graph with the most accuracy compared to baselines.
  • Robustness: The method demonstrates superior finite-sample performance and computational efficiency across various synthetic and real-world scenarios.

Limitations and Future Work

  • Weak Network Interference Assumption: The paper assumes "weak network interference," which might not hold in all real-world scenarios.
  • Computational Bottleneck in Pruning: While PICK significantly improves efficiency, the pruning step can still be a bottleneck for extremely dense graphs. The paper mentions using a general additive model (GAM) for pruning in some experiments to further improve efficiency.
  • Identifiability: The paper briefly discusses identifiability, noting that it's an important problem in SVAR models, and suggests that their method can recover the ground truth causal graph under certain conditions.

Future work could explore extending PICK to handle stronger forms of network interference or more complex causal structures. Further research into optimizing the pruning step for even greater scalability would also be valuable.

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