p-Norm Flow Diffusion for Local Graph Clustering
Authors: Kimon Fountoulakis, Di Wang, Shenghao Yang
ICML 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We show that the proposed problem can be solved in strongly local running time for p 2 and conduct empirical evaluations on both synthetic and real-world graphs to illustrate our approach compares favorably with existing methods. |
| Researcher Affiliation | Collaboration | 1School of Computer Science, University of Waterloo, Canada 2Google Research, USA. Correspondence to: Kimon Fountoulakis <kimon.fountoulakis@uwaterloo.ca>, Di Wang <wadi@google.com>, Shenghao Yang <shenghao.uwaterloo.ca>. |
| Pseudocode | Yes | Algorithm 1 Coordinate solver for smoothed dual problem |
| Open Source Code | Yes | The code is available at github.com/s-h-yang/ p Norm Flow Diffusion. |
| Open Datasets | Yes | First, we carry out experiments on various LFR synthetic graphs (Lancichinetti et al., 2008)... The other four datasets are real-world graphs: the Facebook college graphs of John Hopkins (FB-Johns55) and Colgate (Colgate88) (Traud et al., 2012)), the social network Orkut (Yang & Leskovec, 2012)) and the biological network Sfld (Brown et al., 2006). |
| Dataset Splits | No | The paper describes how synthetic graphs are generated and how real-world clusters are filtered and analyzed (e.g., 'For each graph, we start from a random seed node and we repeat the experiment 100 times.'), but it does not provide specific train/validation/test dataset splits or cross-validation details. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware (e.g., GPU/CPU models, memory specifications) used to run the experiments. |
| Software Dependencies | No | The paper states 'We implemented Algorithm 1 in Julia5', but it does not specify any other software dependencies, libraries, or solvers with version numbers. |
| Experiment Setup | Yes | We set the parameter for p-norm diffusion so | | is a constant factor of the volume of some target cluster... We use the same parameter setting of nonlinear power diffusion as what the authors suggested (Ibrahim & Gleich, 2019). For ℓ1-regularized Page Rank, we allow it to cheat in the sense that we use ground truth to choose the parameter giving the best conductance result. |