论文标题
与网络套索的本地图聚类
Local Graph Clustering with Network Lasso
论文作者
论文摘要
我们研究用于局部图聚类的网络拉索方法的统计和计算特性。可以通过群集边界和种子节点之间的网络流来优雅地表征Nlasso传递的群集。虽然光谱聚类方法是通过最小化laplacian二次形式的最小化来指导的，但Nlasso最大程度地减少了群集指示信号的总变化。正如理论上和数值上所证明的那样，Nlasso方法可以处理非常稀疏的簇（类似链），这对于光谱聚类很难。我们还验证了一种非平滑优化的原始偶对偶的方法允许以最佳的最坏情况收敛速率近似Nlasso解决方案。
We study the statistical and computational properties of a network Lasso method for local graph clustering. The clusters delivered by nLasso can be characterized elegantly via network flows between cluster boundary and seed nodes. While spectral clustering methods are guided by a minimization of the graph Laplacian quadratic form, nLasso minimizes the total variation of cluster indicator signals. As demonstrated theoretically and numerically, nLasso methods can handle very sparse clusters (chain-like) which are difficult for spectral clustering. We also verify that a primal-dual method for nonsmooth optimization allows to approximate nLasso solutions with optimal worst-case convergence rate.
