The Library
Optimal partition recovery in general graphs
Tools
Tools
Tools
Yu, Yi, Madrid, Oscar and Rinaldo, Alessandro (2022) Optimal partition recovery in general graphs. In: 25th International Conference on Artificial Intelligence and Statistics, Online, 28-30 Mar 2022. Published in: Proceedings of Machine Learning Research, 151 pp. 4339-4358. ISSN 2640-3498.
|
PDF
WRAP-Optimal-partition-recovery-in-general-graphs-Yu-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1534Kb) | Preview |
Official URL: https://proceedings.mlr.press/v151/yu22b.html
Abstract
We consider a graph-structured change point problem in which we observe a random vector with piece-wise constant but otherwise 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 or, equivalently, of estimating the cut separating the sub-graphs over which the mean remains constant. Although graph-valued signals of this type have been previously studied in the literature for the different tasks of testing for the presence of an anomalous cluster and of estimating the mean vector, no localisation results are known outside the classical case of chain graphs. When the partition S consists of only two elements, we characterise the difficulty of the localisation problem in terms of four key parameters: the maximal noise variance σ2, the size Δ of the smaller element of the partition, the magnitude κ of the difference in the signal values across contiguous elements of the partition and the sum of the effective resistance edge weights |∂r(S)| 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 κ2Δσ−2|∂r(S)|−1≲1, no consistent estimator of the true partition exists. On the other hand, when κ2Δσ−2|∂r(S)|−1≳ζnlog{r(|E|)}, with r(|E|) being the sum of effective resistance weighted edges and ζn being any diverging sequence in n, we show that a polynomial-time, approximate ℓ0-penalised least squared estimator delivers a localisation error – measured by the symmetric difference between the true and estimated partition – of order κ−2σ2|∂r(S)|log{r(|E|)}. Aside from the log{r(|E|)} term, this rate is minimax optimal. Finally, we provide discussions on the localisation error for more general partitions of unknown sizes.
| Item Type: | Conference Item (Paper) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | |||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Statistics | |||||||||
| Library of Congress Subject Headings (LCSH): | Gaussian distribution , Graph algorithms, Combinatorial analysis , Graph theory | |||||||||
| Journal or Publication Title: | Proceedings of Machine Learning Research | |||||||||
| Publisher: | ML Research Press | |||||||||
| ISSN: | 2640-3498 | |||||||||
| Official Date: | 2022 | |||||||||
| Dates: |
|
|||||||||
| Volume: | 151 | |||||||||
| Page Range: | pp. 4339-4358 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Open Access (Creative Commons) | |||||||||
| Date of first compliant deposit: | 4 October 2022 | |||||||||
| Date of first compliant Open Access: | 4 October 2022 | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Conference Paper Type: | Paper | |||||||||
| Title of Event: | 25th International Conference on Artificial Intelligence and Statistics | |||||||||
| Type of Event: | Conference | |||||||||
| Location of Event: | Online | |||||||||
| Date(s) of Event: | 28-30 Mar 2022 | |||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
