Variational perspective on local graph clustering
From MaRDI portal
Abstract: Modern graph clustering applications require the analysis of large graphs and this can be computationally expensive. In this regard, local spectral graph clustering methods aim to identify well-connected clusters around a given "seed set" of reference nodes without accessing the entire graph. The celebrated Approximate Personalized PageRank (APPR) algorithm in the seminal paper by Andersen et al. is one such method. APPR was introduced and motivated purely from an algorithmic perspective. In other words, there is no a priori notion of objective function/optimality conditions that characterizes the steps taken by APPR. Here, we derive a novel variational formulation which makes explicit the actual optimization problem solved by APPR. In doing so, we draw connections between the local spectral algorithm of and an iterative shrinkage-thresholding algorithm (ISTA). In particular, we show that, appropriately initialized ISTA applied to our variational formulation can recover the sought-after local cluster in a time that only depends on the number of non-zeros of the optimal solution instead of the entire graph. In the process, we show that an optimization algorithm which apparently requires accessing the entire graph, can be made to behave in a completely local manner by accessing only a small number of nodes. This viewpoint builds a bridge across two seemingly disjoint fields of graph processing and numerical optimization, and it allows one to leverage well-studied, numerically robust, and efficient optimization algorithms for processing today's large graphs.
Recommendations
- Experimental and Efficient Algorithms
- Finding and visualizing graph clusters using PageRank optimization
- Finding and visualizing graph clusters using PageRank optimization
- A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
- Mean field analysis of personalized PageRank with implications for local graph clustering
Cites work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
- An r-Dimensional Quadratic Placement Algorithm
- An algorithm for improving graph partitions
- Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters
- Expander flows, geometric embeddings and graph partitioning
- Flow-based algorithms for local graph clustering
- scientific article; zbMATH DE number 6276186 (Why is no real title available?)
- scientific article; zbMATH DE number 3337135 (Why is no real title available?)
- Isoperimetric Partitioning: A New Algorithm for Graph Partitioning
- PageRank beyond the web
- Partitioning Sparse Matrices with Eigenvectors of Graphs
- Random walks and local cuts in graphs
- Variational perspective on local graph clustering
Cited in
(9)- Variational perspective on local graph clustering
- Multiway \(p\)-spectral graph cuts on Grassmann manifolds
- Identifying graph clusters using variational inference and links to covariance parametrization
- Compressive sensing for cut improvement and local clustering
- Statistical guarantees for local graph clustering
- Experimental and Efficient Algorithms
- Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
- Reconciling business analytics with graphically initialized subspace clustering for optimal nonlinear pricing
- Approximating single-source personalized pagerank with absolute error guarantees
This page was built for publication: Variational perspective on local graph clustering
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1739051)
