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