Master’s Thesis Presentation • Machine Learning — Local Graph Clustering Using l1-regularized PageRank Algorithms

Please note: This master’s thesis presentation will be given online.

Chufeng Hu, Master’s candidate
David R. Cheriton School of Computer Science

Local graph clustering methods are used to find small- and medium-scale clusters without traversing the graph. It has been shown that the combination of the Approximate Personalized PageRank (APPR) algorithm and the sweep method can efficiently detect a small cluster around the starting vertex. 

This research explores the optimization framework proposed in the work by Fountoulakis et al., where a connection between the APPR and an l1-regularized objective function is revealed. We propose a coordinate descent method for solving the l1-regularized PageRank problem. We prove that our method has running time that depends on the number of nonzero coordinates in the optimal solution. In addition, we compare 6 optimization algorithms for solving the l1-regularized PageRank problem in large graphs. We demonstrate that the proposed coordinate descent outperforms the original proximal gradient descent, and the accelerated first-order algorithms have the best performance among all algorithms measured in our experiment.

To join this master’s thesis presentation on Zoom, please go to https://zoom.us/j/99920266458?pwd=U1pXbjY2dzl6a0FGbCtIOC8wdEV2dz09.

Meeting ID: 999 2026 6458
Password: 3wQVRM