Optimal partition recovery in general graphs

arXiv2110.10989MaRDI QIDQ6380919FDOQ6380919

Authors: Yi Yu, Oscar-Hernan Madrid-Padilla, Alessandro Rinaldo 

Publication date: 21 October 2021

Abstract: We consider a graph-structured change point problem in which we observe a random vector with piecewise constant but unknown mean and whose independent, sub-Gaussian coordinates correspond to the $n$ nodes of a fixed graph. We are interested in the localisation task of recovering the partition of the nodes associated to the constancy regions of the mean vector. When the partition $mathcalS$ consists of only two elements, we characterise the difficulty of the localisation problem in terms of four key parameters: the maximal noise variance $sigm{a}^2$, the size $Delta$ of the smaller element of the partition, the magnitude $kappa$ of the difference in the signal values across contiguous elements of the partition and the sum of the effective resistance edge weights $|partia{l}_r(mathcalS)|$ of the corresponding cut -- a graph theoretic quantity quantifying the size of the partition boundary. In particular, we demonstrate an information theoretical lower bound implying that, in the low signal-to-noise ratio regime $kapp{a}^{2}Deltasigm{a}^{-2}|partia{l}_r(mathcalS){|}^{-1}lesssim1$, no consistent estimator of the true partition exists. On the other hand, when $kapp{a}^{2}Deltasigm{a}^{-2}|partia{l}_r(mathcalS){|}^{-1}gtrsimzet{a}_{n}logr(|E|)$, with $r(|E|)$ being the sum of effective resistance weighted edges and $zet{a}_n$ being any diverging sequence in $n$, we show that a polynomial-time, approximate $el{l}_0$-penalised least squared estimator delivers a localisation error -- measured by the symmetric difference between the true and estimated partition -- of order $kapp{a}^{-2}sigm{a}^2|partia{l}_r(mathcalS)|logr(|E|)$. Aside from the $logr(|E|)$ term, this rate is minimax optimal. Finally, we provide discussions on the localisation error for more general partitions of unknown sizes.

This page was built for publication: Optimal partition recovery in general graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6380919)