Optimization Online


Exploiting Optimization for Local Graph Clustering

Fountoulakis Kimon (kfount***at***berkeley.edu)
Cheng Xiang (x.cheng***at***berkeley.edu)
Shun Julian (jshun***at***eecs.berkeley.edu)
Roosta-Khorasani Farbod (farbod***at***icsi.berkeley.edu)
Mahoney Michael (mmahoney***at***stat.berkeley.edu)

Abstract: Local graph clustering methods aim to identify well-connected clusters around a given ``seed set'' of reference nodes. The main focus of prior theoretical work has been on worst-case running time properties or on implicit statistical regularization; and the focus of prior empirical work has been to identify structure in large social and information networks. Here, we adopt an optimization perspective on local graph clustering methods. In particular, we clarify the relationship between the local spectral algorithm of (Andersen, Chung and Lang, FOCS '06) and a variant of a well-studied optimization objective. This insight permits us to develop a local spectral graph clustering algorithm that has improved theoretical convergence properties. We also demonstrate the numerical performance of this optimization-based algorithm and some heuristic variants of it.

Keywords: local graph clustering; Page-Rank; l1-regularization; large scale optimization; coordinate descent; iteration complexity

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Combinatorial Optimization (Graphs and Matroids )

Category 3: Convex and Nonsmooth Optimization


Download: [PDF]

Entry Submitted: 02/04/2016
Entry Accepted: 02/05/2016
Entry Last Modified: 02/05/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society