arxiv: 2604.25156 · v1 · submitted 2026-04-28 · 📊 stat.ME

Recognition: unknown

Online Learning for Autoregressive Multilayer Stochastic Block Models under Stationarity and Non-Stationarity

Fan Wang , Haotian Xu , Yi Yu

Authors on Pith no claims yet

Pith reviewed 2026-05-07 15:48 UTC · model grok-4.3

classification 📊 stat.ME

keywords autoregressive multilayer stochastic block modelonline estimationcommunity detectiondynamic networksnon-stationary processestensor spectral methodsrecursive updates

0 comments

The pith

An autoregressive multilayer stochastic block model permits online recursive estimation to achieve minimax-optimal rates for community recovery in both stationary and non-stationary dynamic networks.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a first-order autoregressive multilayer stochastic block model in which edge formation and dissolution probabilities are governed by shared latent community memberships across layers and time. Under stationarity it develops an online procedure that uses recursive updates followed by tensor-based spectral refinement, and proves non-asymptotic estimation rates together with minimax optimality and community recovery guarantees. For non-stationary regimes that include abrupt changes or gradual drifts, an adaptive windowed version of the algorithm automatically segments the data and delivers matching guarantees when applied segment-wise. This matters because real-world multilayer networks such as social or biological interaction data rarely obey temporal independence or strict stationarity, so an online method that tracks communities without full recomputation addresses a practical gap.

Core claim

The central claim is that the AR(1)-MSBM, with edge probabilities determined by latent community memberships shared across layers and evolving according to first-order autoregressive dependence, admits an online estimation procedure based on recursive updates and tensor spectral refinement that attains non-asymptotic rates which are minimax optimal under stationarity; the same rates and community recovery guarantees are recovered in a non-stationary setting by an adaptive windowed algorithm applied under a quasi-stationary segmentation framework.

What carries the argument

The AR(1)-MSBM with shared latent community memberships that determine edge probabilities across layers and consecutive time points via autoregressive dependence; the mechanism is the recursive online update combined with tensor-based spectral refinement for parameter estimation and community detection.

If this is right

Online recursive updates allow tracking of evolving communities without recomputing from scratch at each time step.
Minimax-optimal non-asymptotic rates hold for both parameter estimation and community recovery when the stationarity assumption is satisfied.
An adaptive windowed procedure automatically detects and segments structural changes while preserving the stationary rates on each segment.
Community recovery guarantees remain valid under the quasi-stationary segmentation framework even when global stationarity is violated.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The shared-membership assumption across layers suggests the method could be applied to multiplex data where one set of communities drives multiple relation types.
If real networks exhibit slow drifts rather than abrupt changes, the adaptive window mechanism may still segment effectively but would require tuning the change-detection threshold.
Extensions to higher-order autoregressive dependence or time-varying number of communities are natural next steps that preserve the recursive-update structure.

Load-bearing premise

Edge probabilities are fully determined by latent community memberships that are identical across layers and obey a strict first-order autoregressive dependence.

What would settle it

A synthetic or real dataset exhibiting either higher-order temporal dependence between time points or layer-specific community structures where the proposed non-asymptotic rates fail to hold or community recovery accuracy drops below the claimed level.

Figures

Figures reproduced from arXiv: 2604.25156 by Fan Wang, Haotian Xu, Yi Yu.

**Figure 1.** Figure 1: Illustration of the adaptive window selection procedure ( view at source ↗

**Figure 2.** Figure 2: Examples of the sequence {Θt i,j,l}t∈[T] with T = 100, V (t) = t −1/2 , G = 5, {T1, T2, T3, T4} = {20, 40, 60, 80}. Circles mark the segment starting values{Θ Tg−1+1 i,j,l }g∈[G] . Definition 4 introduces a flexible framework through a general drift function V (t), which can be seen as a generalization of the fixed rate t −1/2 used in Huang and Wang (2024). The function V (t) regulates the maximal within-s… view at source ↗

**Figure 3.** Figure 3: Stationary simulation results: mean clustering error (1−ARI) over time with pointwise 95% Monte Carlo confidence bands. Top-Left: Scenario I (weak signal in both transition probabilities and marginals). Top-Right: Scenario II (signal only in transition probabilities). Bottom-Left: Scenario III (opposing layer structures; signals cancel under aggregation). Bottom-Right: Scenario IV (sparse signal masked by … view at source ↗

**Figure 4.** Figure 4: Non-stationary simulation results. mean over time with Top row: ErrΘ(t). Middle row: Err∆(t). Bottom row: window size ˆkt. Columns (left to right): Scenarios I–IV. Curves show Adaptive, Full-history, Fixed-window (ˆkt = 30) and Fixed-window (ˆkt = 20); shaded bands denote mean ± standard deviation (error rows only). Dashed lines indicate phase boundaries at t = 50 and t = 100. or destinations as nodes. For… view at source ↗

**Figure 5.** Figure 5: Estimated community and adaptation dynamics for the U.S. air transportation network. Top: community size trajectories (K = 3). Middle: switch rate. Bottom: selected window size ˆk(t). The results are shown in view at source ↗

read the original abstract

Dynamic multilayer networks arise in many applications where multiple types of relations among a common set of nodes evolve over time. Existing approaches often assume temporal independence, focus on single-layer networks or impose stationarity, limiting their applicability in practice. In this paper, we introduce a first-order autoregressive multilayer stochastic block model (AR(1)-MSBM), in which edge formation and dissolution probabilities between consecutive time points are determined by latent community memberships and shared across layers. Under stationarity, we propose an online estimation procedure based on recursive updates and tensor-based spectral refinement. We establish non-asymptotic estimation rates, prove their minimax optimality and derive guarantees for community recovery. We further consider a non-stationary setting that allows both abrupt changes and gradual shifts, and develop an adaptive windowed online algorithm that automatically adjusts to unknown structural changes. Under a quasi-stationary segmentation framework, we derive estimation and community recovery guarantees that match the stationary results when applied segmentwise. Our theoretical findings are supported by extensive numerical experiments, with code available online.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper adds an AR(1) layer to multilayer SBMs and supplies online recursive estimators plus adaptive windows that come with non-asymptotic minimax rates and recovery bounds.

read the letter

The core contribution is the AR(1)-MSBM, where edge probabilities between consecutive times are driven by shared latent communities across layers. Under stationarity they combine recursive updates with tensor spectral refinement to get an online estimator. They prove non-asymptotic rates that match the minimax lower bound and give community recovery guarantees. For the non-stationary case they introduce an adaptive window procedure that segments the sequence and reapplies the stationary results on each piece, again with matching guarantees. Experiments back the claims and code is released.

Referee Report

0 major / 2 minor

Summary. The paper introduces a first-order autoregressive multilayer stochastic block model (AR(1)-MSBM) in which edge formation and dissolution probabilities between consecutive time points are determined by latent community memberships shared across layers. Under stationarity, it proposes an online estimation procedure based on recursive updates and tensor-based spectral refinement, establishing non-asymptotic estimation rates that are proven minimax optimal together with community recovery guarantees. For the non-stationary case, it develops an adaptive windowed online algorithm under a quasi-stationary segmentation framework that yields matching guarantees when applied segmentwise. The theoretical findings are supported by numerical experiments with code made available online.

Significance. If the non-asymptotic rates, minimax optimality, and recovery guarantees hold as stated, the work provides a timely extension of stochastic block models to dynamic multilayer settings with explicit temporal dependence and online estimation. The adaptive handling of both abrupt and gradual changes under quasi-stationarity addresses a practical limitation of existing stationary or independent-time assumptions. Reproducibility via released code is a positive feature.

minor comments (2)

[Abstract] Abstract: the claim of 'non-asymptotic estimation rates' and 'minimax optimality' is stated without reference to the specific theorem numbers or the precise dependence on the number of nodes, layers, or time points; adding these pointers would improve readability.
[Abstract] The description of the non-stationary extension mentions 'quasi-stationary segmentation' but does not clarify how the segmentation is detected or how the window size is chosen in the algorithm; a brief algorithmic outline or pseudocode reference would help.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and accurate summary of our work on the AR(1)-MSBM, including the online estimators, minimax-optimal rates, community recovery guarantees, and the adaptive windowing approach for non-stationarity. We appreciate the recognition of the model's relevance to evolving multilayer networks and the value of the released code for reproducibility. The recommendation for minor revision is noted.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper defines a new AR(1)-MSBM with community-driven transition probabilities shared across layers, introduces an online recursive estimator using tensor spectral refinement for the stationary case, derives non-asymptotic rates, establishes minimax optimality via standard lower-bound arguments, and provides community recovery guarantees. The non-stationary extension employs adaptive windowing under quasi-stationary segmentation with matching per-segment guarantees. No step reduces a claimed result to a fitted input, self-citation, or definitional tautology; the chain extends existing SBM spectral methods to the autoregressive multilayer setting with independent theoretical support.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

Ledger populated from abstract only; full paper may contain additional fitted parameters or unstated assumptions.

axioms (2)

domain assumption Edge formation and dissolution probabilities are determined by latent community memberships and are shared across layers.
Core modeling choice stated in the abstract for the AR(1)-MSBM.
domain assumption The temporal dependence is strictly first-order autoregressive.
Required for the recursive update and stationarity analysis described.

invented entities (1)

AR(1)-MSBM no independent evidence
purpose: Model for dynamic multilayer networks with temporal edge dependence.
New model introduced in the paper.

pith-pipeline@v0.9.0 · 5480 in / 1418 out tokens · 65852 ms · 2026-05-07T15:48:27.623358+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

48 extracted references · 11 canonical work pages

[1]

Exactly median-unbiased estimation of first order autoregressive/unit root models

Donald WK Andrews. Exactly median-unbiased estimation of first order autoregressive/unit root models. Econometrica: Journal of the Econometric Society, pages 139--165, 1993

1993
[2]

Approximately median-unbiased estimation of autoregressive models

Donald WK Andrews and Hong-Yuan Chen. Approximately median-unbiased estimation of autoregressive models. Journal of Business & Economic Statistics, 12 0 (2): 0 187--204, 1994

1994
[3]

Adaptively tracking the best bandit arm with an unknown number of distribution changes

Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Conference on Learning Theory, pages 138--158. PMLR, 2019

2019
[4]

Optimal dynamic regret in proper online learning with strongly convex losses and beyond

Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in proper online learning with strongly convex losses and beyond. In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 1805--184...

2022
[5]

Non-stationary stochastic optimization

Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations research, 63 0 (5): 0 1227--1244, 2015

2015
[6]

Change point estimation in a dynamic stochastic block model

Monika Bhattacharjee, Moulinath Banerjee, and George Michailidis. Change point estimation in a dynamic stochastic block model. Journal of machine learning research, 21 0 (107): 0 1--59, 2020

2020
[7]

Transfer learning for contextual multi-armed bandits

Changxiao Cai, T Tony Cai, and Hongzhe Li. Transfer learning for contextual multi-armed bandits. The Annals of Statistics, 52 0 (1): 0 207--232, 2024

2024
[8]

Tony Cai and Anru Zhang

T. Tony Cai and Anru Zhang. Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics . The Annals of Statistics, 46 0 (1): 0 60 -- 89, 2018. doi:10.1214/17-AOS1541. URL https://doi.org/10.1214/17-AOS1541

work page doi:10.1214/17-aos1541 2018
[9]

Modeling the multi-layer nature of the european air transport network: Resilience and passengers re-scheduling under random failures

Alessio Cardillo, Massimiliano Zanin, Jes \'u s G \'o mez-Gardenes, Miguel Romance, Alejandro J Garc \' a del Amo, and Stefano Boccaletti. Modeling the multi-layer nature of the european air transport network: Resilience and passengers re-scheduling under random failures. The European Physical Journal Special Topics, 215 0 (1): 0 23--33, 2013

2013
[10]

Autoregressive networks with dependent edges

Jinyuan Chang, Qin Fang, Eric D Kolaczyk, Peter W MacDonald, and Qiwei Yao. Autoregressive networks with dependent edges. Journal of the Royal Statistical Society Series B: Statistical Methodology, page qkag063, 2026

2026
[11]

Structural reducibility of multilayer networks

Manlio De Domenico, Vincenzo Nicosia, Alexandre Arenas, and Vito Latora. Structural reducibility of multilayer networks. Nature communications, 6 0 (1): 0 1--9, 2015

2015
[12]

Detection and localization of change points in temporal networks with the aid of stochastic block models

Simon De Ridder, Benjamin Vandermarliere, and Jan Ryckebusch. Detection and localization of change points in temporal networks with the aid of stochastic block models. Journal of Statistical Mechanics: Theory and Experiment, 2016 0 (11): 0 113302, 2016

2016
[13]

Chao Gao, Yu Lu, and Harrison H. Zhou. Rate-optimal graphon estimation . The Annals of Statistics, 43 0 (6): 0 2624 -- 2652, 2015. doi:10.1214/15-AOS1354. URL https://doi.org/10.1214/15-AOS1354

work page doi:10.1214/15-aos1354 2015
[14]

Consistent estimation of dynamic and multi-layer block models

Qiuyi Han, Kevin Xu, and Edoardo Airoldi. Consistent estimation of dynamic and multi-layer block models. In International Conference on Machine Learning, pages 1511--1520. PMLR, 2015

2015
[15]

An optimal statistical and computational framework for generalized tensor estimation

Rungang Han, Rebecca Willett, and Anru R Zhang. An optimal statistical and computational framework for generalized tensor estimation. The Annals of Statistics, 50 0 (1): 0 1--29, 2022

2022
[16]

A stability principle for learning under nonstationarity

Chengpiao Huang and Kaizheng Wang. A stability principle for learning under nonstationarity. Operations Research, 0 0 (0): 0 null, 2024. doi:10.1287/opre.2024.0766. URL https://doi.org/10.1287/opre.2024.0766

work page doi:10.1287/opre.2024.0766 2024
[17]

Journal of Classification2(1), 193–218 (1985) https://doi.org/10.1007/BF01908075

Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of Classification, 2 0 (1): 0 193--218, 1985. doi:10.1007/BF01908075

work page doi:10.1007/bf01908075 1985
[18]

Online optimization: Competing with dynamic comparators

Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online optimization: Competing with dynamic comparators. In Artificial Intelligence and Statistics, pages 398--406. PMLR, 2015

2015
[19]

Autoregressive networks

Binyan Jiang, Jialiang Li, and Qiwei Yao. Autoregressive networks. Journal of Machine Learning Research, 24 0 (227): 0 1--69, 2023

2023
[20]

Community detection on mixture multilayer networks via regularized tensor decomposition

Bing-Yi Jing, Ting Li, Zhongyuan Lyu, and Dong Xia. Community detection on mixture multilayer networks via regularized tensor decomposition. The Annals of Statistics, 49 0 (6): 0 3181--3205, 2021

2021
[21]

Multilayer networks

Mikko Kivel \"a , Alex Arenas, Marc Barthelemy, James P Gleeson, Yamir Moreno, and Mason A Porter. Multilayer networks. Journal of complex networks, 2 0 (3): 0 203--271, 2014

2014
[22]

Computational and statistical thresholds in multi-layer stochastic block models

Jing Lei, Anru R Zhang, and Zihan Zhu. Computational and statistical thresholds in multi-layer stochastic block models. The Annals of Statistics, 52 0 (5): 0 2431--2455, 2024

2024
[23]

A dynamic stochastic block model for multidimensional networks, 2025

Ovielt Baltodano López and Roberto Casarin. A dynamic stochastic block model for multidimensional networks, 2025. URL https://arxiv.org/abs/2209.09354

work page arXiv 2025
[24]

Statistical clustering of temporal networks through a dynamic stochastic block model

Catherine Matias and Vincent Miele. Statistical clustering of temporal networks through a dynamic stochastic block model. Journal of the Royal Statistical Society Series B: Statistical Methodology, 79 0 (4): 0 1119--1141, 08 2016. ISSN 1369-7412. doi:10.1111/rssb.12200. URL https://doi.org/10.1111/rssb.12200

work page doi:10.1111/rssb.12200 2016
[25]

Bernstein inequality and moderate deviations under strong mixing conditions

Florence Merlev \`e de, Magda Peligrad, and Emmanuel Rio. Bernstein inequality and moderate deviations under strong mixing conditions. In High dimensional probability V: the Luminy volume, volume 5, pages 273--293. Institute of Mathematical Statistics, 2009

2009
[26]

A general methodology for fast online changepoint detection

Per August Jarval Moen. A general methodology for fast online changepoint detection. arXiv preprint arXiv:2504.09573, 2025

work page arXiv 2025
[27]

Change point localization in dependent dynamic nonparametric random dot product graphs

Oscar Hernan Madrid Padilla, Yi Yu, and Carey E Priebe. Change point localization in dependent dynamic nonparametric random dot product graphs. Journal of Machine Learning Research, 23 0 (234): 0 1--59, 2022

2022
[28]

Bias reduction in autoregressive models

KD Patterson. Bias reduction in autoregressive models. Economics Letters, 68 0 (2): 0 135--141, 2000

2000
[29]

Spectral and matrix factorization methods for consistent community detection in multi-layer networks, 2018

Subhadeep Paul and Yuguo Chen. Spectral and matrix factorization methods for consistent community detection in multi-layer networks, 2018. URL https://arxiv.org/abs/1704.07353

work page arXiv 2018
[30]

2019 , bdsk-url-1 =

Marianna Pensky. Dynamic network models and graphon estimation . The Annals of Statistics, 47 0 (4): 0 2378 -- 2403, 2019. doi:10.1214/18-AOS1751. URL https://doi.org/10.1214/18-AOS1751

work page doi:10.1214/18-aos1751 2019
[31]

Spectral clustering in the dynamic stochastic block model

Marianna Pensky and Teng Zhang. Spectral clustering in the dynamic stochastic block model . Electronic Journal of Statistics, 13 0 (1): 0 678 -- 709, 2019. doi:10.1214/19-EJS1533. URL https://doi.org/10.1214/19-EJS1533

work page doi:10.1214/19-ejs1533 2019
[32]

A remark on stirling's formula

Herbert Robbins. A remark on stirling's formula. The American mathematical monthly, 62 0 (1): 0 26--29, 1955

1955
[33]

The bias of autoregressive coefficient estimators

Paul Shaman and Robert A Stine. The bias of autoregressive coefficient estimators. Journal of the American Statistical Association, 83 0 (403): 0 842--848, 1988

1988
[34]

Clustering network layers with the strata multilayer stochastic block model

Natalie Stanley, Saray Shai, Dane Taylor, and Peter J Mucha. Clustering network layers with the strata multilayer stochastic block model. IEEE transactions on network science and engineering, 3 0 (2): 0 95--105, 2016

2016
[35]

Tracking most significant shifts in infinite-armed bandits

Joe Suk and Jung-hun Kim. Tracking most significant shifts in infinite-armed bandits. arXiv preprint arXiv:2502.00108, 2025

work page arXiv 2025
[36]

Tracking most significant arm switches in bandits

Joe Suk and Samory Kpotufe. Tracking most significant arm switches in bandits. In Conference on Learning Theory, pages 2160--2182. PMLR, 2022

2022
[37]

Detecting dynamic community structure in functional brain networks across individuals: A multilayer approach

Chee-Ming Ting, S Balqis Samdin, Meini Tang, and Hernando Ombao. Detecting dynamic community structure in functional brain networks across individuals: A multilayer approach. IEEE Transactions on Medical Imaging, 40 0 (2): 0 468--480, 2020

2020
[38]

Bureau of Transportation Statistics

U.S. Bureau of Transportation Statistics . Transtats: T-100 domestic segment (all carriers). https://www.transtats.bts.gov/, 2026. U.S. Department of Transportation; accessed February 21, 2026

2026
[39]

High-dimensional probability: An introduction with applications in data science, volume 47

Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018

2018
[40]

Optimal change point detection and localization in sparse dynamic networks

Daren Wang, Yi Yu, and Alessandro Rinaldo. Optimal change point detection and localization in sparse dynamic networks. The Annals of Statistics, 49 0 (1): 0 203--232, 2021

2021
[41]

Multilayer random dot product graphs: Estimation and online change point detection

Fan Wang, Wanshan Li, Oscar Hernan Madrid Padilla, Yi Yu, and Alessandro Rinaldo. Multilayer random dot product graphs: Estimation and online change point detection. Journal of the Royal Statistical Society Series B: Statistical Methodology, page qkaf051, 2025

2025
[42]

Rates of convergence of spectral methods for graphon estimation

Jiaming Xu. Rates of convergence of spectral methods for graphon estimation. In International Conference on Machine Learning, pages 5433--5442. PMLR, 2018

2018
[43]

Dynamic stochastic blockmodels for time-evolving social networks

Kevin S Xu and Alfred O Hero. Dynamic stochastic blockmodels for time-evolving social networks. IEEE Journal of Selected Topics in Signal Processing, 8 0 (4): 0 552--562, 2014

2014
[44]

Detecting communities and their evolutions in dynamic social networks—a bayesian approach

Tianbao Yang, Yun Chi, Shenghuo Zhu, Yihong Gong, and Rong Jin. Detecting communities and their evolutions in dynamic social networks—a bayesian approach. Machine learning, 82 0 (2): 0 157--189, 2011

2011
[45]

Tensor svd: Statistical and computational limits

Anru Zhang and Dong Xia. Tensor svd: Statistical and computational limits. IEEE Transactions on Information Theory, 64 0 (11): 0 7311--7338, 2018

2018
[46]

Heteroskedastic pca: Algorithm, optimality, and applications

Anru R Zhang, T Tony Cai, and Yihong Wu. Heteroskedastic pca: Algorithm, optimality, and applications. The Annals of Statistics, 50 0 (1): 0 53--80, 2022

2022
[47]

A flexible latent space model for multilayer networks

Xuefei Zhang, Songkai Xue, and Ji Zhu. A flexible latent space model for multilayer networks. In International Conference on Machine Learning, pages 11288--11297. PMLR, 2020

2020
[48]

Improved analysis for dynamic regret of strongly convex and smooth functions

Peng Zhao and Lijun Zhang. Improved analysis for dynamic regret of strongly convex and smooth functions. In Learning for Dynamics and Control, pages 48--59. PMLR, 2021

2021