English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper investigates graph clustering in the planted cluster model in thepresence of {\em small clusters}. Traditional results dictate that for analgorithm to provably correctly recover the clusters, {\em all} clusters mustbe sufficiently large (in particular, $\tilde{\Omega}(\sqrt{n})$ where $n$ isthe number of nodes of the graph). We show that this is not really arestriction: by a more refined analysis of the trace-norm based recoveryapproach proposed in Jalali et al. (2011) and Chen et al. (2012), we prove thatsmall clusters, under certain mild assumptions, do not hinder recovery of largeones.  Based on this result, we further devise an iterative algorithm to recover{\em almost all clusters} via a "peeling strategy", i.e., recover largeclusters first, leading to a reduced problem, and repeat this procedure. Theseresults are extended to the {\em partial observation} setting, in which only a(chosen) part of the graph is observed.The peeling strategy gives rise to anactive learning algorithm, in which edges adjacent to smaller clusters arequeried more often as large clusters are learned (and removed).  From a high level, this paper sheds novel insights on high-dimensionalstatistics and learning structured data, by presenting a structured matrixlearning problem for which a one shot convex relaxation approach necessarilyfails, but a carefully constructed sequence of convex relaxationsdoes the job.

Breaking the Small Cluster Barrier of Graph Clustering