Master’s Thesis Presentation • Machine Learning — Local Graph Clustering Using l1-regularized PageRank AlgorithmsExport this event to calendar

Friday, April 24, 2020 — 4:00 PM EDT

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

Location 
Online Zoom presentation
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
  1. 2021 (204)
    1. December (15)
    2. November (13)
    3. October (12)
    4. September (21)
    5. August (20)
    6. July (17)
    7. June (11)
    8. May (16)
    9. April (27)
    10. March (20)
    11. February (13)
    12. January (19)
  2. 2020 (217)
    1. December (18)
    2. November (12)
    3. October (7)
    4. September (21)
    5. August (28)
    6. July (14)
    7. June (18)
    8. May (16)
    9. April (20)
    10. March (16)
    11. February (25)
    12. January (22)
  3. 2019 (255)
  4. 2018 (217)
  5. 2017 (36)
  6. 2016 (21)
  7. 2015 (36)
  8. 2014 (33)
  9. 2013 (23)
  10. 2012 (4)
  11. 2011 (1)
  12. 2010 (1)
  13. 2009 (1)
  14. 2008 (1)