从单条时间轨迹中高效学习高斯图模型结构，无需等待混合时间。
Learning Gaussian Graphical Models from a Glauber Trajectory Without Mixing
- 通过重缩放与局部影响检测，从非独立轨迹中提取边信息。
- 仅需多项式时间与不依赖混合时间的轨迹长度即可准确恢复图结构。
- 适合处理时序相关数据的图学习任务，如生物网络、金融时序建模。
我们研究从单条Glauber动态轨迹中学习n个变量上d-稀疏高斯图模型结构的问题。在经典i.i.d.设定下，已知在一般稀疏性与最小边强度假设下存在亚线性样本量的理论保证，但多项式时间内实现该目标仍为开放问题。为填补此空白，本文提出一个多项式时间算法，仅需单条轨迹即可恢复条件独立图结构，且其轨迹长度要求不依赖于混合时间。技术上，算法包含三个部分：首先估计条件方差并重缩放轨迹，保持原图结构不变；其次设计局部边测试，通过短更新窗口分离成对影响以获取邻接信息；最后使用鲁棒中位数估计器聚合局部统计量，在单条轨迹带来的时序依赖下仍能保证精度。
原文摘要 · Abstract (English)
We study the task of learning the structure of a $d$-sparse Gaussian graphical model on $n$ variables from a single trajectory of Glauber dynamics. Beyond algorithmic considerations, many applications present temporally correlated observations rather than i.i.d.\ samples. In the classical i.i.d.\ setting, under comparably general sparsity and minimum edge-strength assumptions, sublinear-in-$n$ sample guarantees are known, but achieving them in polynomial-time remains open. Motivated in part by this gap, we give a polynomial-time algorithm that recovers the conditional-independence graph from a single Glauber trajectory, with a trajectory-length guarantee that does not depend on the mixing time. Technically, our algorithm has three components. First, we estimate the conditional variances and rescale the trajectory to reduce to the unit-diagonal case, without changing the underlying graph. Second, we design a local edge test that extracts adjacency information from short update windows by isolating pairwise influence. Third, we aggregate these local statistics using a robust median-based estimator, and prove accuracy despite temporal dependence arising from a single trajectory.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。