New Algorithm Learns Graph Models from Single Data Trajectories

Traditional methods for learning the structure of graphical models often assume that data samples are independent and identically distributed. However, many real-world applications, such as sensor networks or financial markets, provide temporally correlated observations, like a single continuous trajectory. This paper introduces a novel polynomial-time algorithm that addresses this challenge by learning the structure of a sparse Gaussian graphical model directly from such a single Glauber dynamics trajectory. The algorithm is designed to overcome the limitations of relying on mixing times, which can be problematic for long, dependent sequences. It comprises three main components: first, estimating conditional variances to normalize the trajectory without altering the underlying graph; second, a local edge test that extracts pairwise influence from short update windows; and third, a robust median-based estimator to aggregate these local statistics, ensuring accuracy despite the temporal dependencies inherent in a single trajectory.