Graph Reduction with Spectral and Cut Guarantees
Authors: Andreas Loukas
JMLR 2019 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | To demonstrate the practical benefits of local variation methods, the analysis is complemented with numerical results on representative graphs ranging from scale-free to planar graphs. Compared to both standard (Karypis and Kumar, 1998) and advanced reduction methods (Ron et al., 2011; Livne and Brandt, 2012; Shuman et al., 2016), the proposed methods yield small graphs of improved spectral quality, often by a large margin, without being much slower than naive heavy-edge matching. |
| Researcher Affiliation | Academia | Andreas Loukas EMAIL Laboratoire de traitement des signaux 2, Ecole Polytechnique F ed erale de Lausanne, CH-1015 Lausanne, Switzerland |
| Pseudocode | Yes | Algorithm 1 Multi-level coarsening Algorithm 2 Single-level coarsening by local variation |
| Open Source Code | Yes | The code reproducing the experiments can be accessed online 7. github.com/loukasa/graph-coarsening/tree/v1.1 (DOI 175851068) |
| Open Datasets | Yes | Yeast. Protein-to-protein interaction network in budding yeast, analyzed by Jeong et al. (2001). Airfoil. Finite-element graph obtained by airflow simulation Preis and Diekmann (1997). Minnesota. Road network with N = 2642 vertices, M = 3304 edges, diameter of 99, and degree between 1 and 5 (Gleich, 2008). Bunny. Point cloud consisting of N = 2503 vertices, M = 65490 edges, diameter of 15, and degree between 13 and 97 (Turk and Levoy, 1994). |
| Dataset Splits | No | The paper discusses graph reduction ratios (e.g., "reduction of 70%") and graph properties, but does not provide specific training/validation/test splits for any machine learning task or how the datasets (graphs) themselves were partitioned for experimental evaluation in that sense. |
| Hardware Specification | Yes | The results are displayed in Figures 3a and 3b for subspaces of size 10 and 40, respectively. As with most such comparisons, the actual numbers are only indicative and depend on the programming language utilized (Python), processing paradigm (no parallelism was employed), and hardware architecture (2.2GHz CPU). |
| Software Dependencies | No | The paper mentions the programming language "Python" and the "Py GSP toolbox" (for Kron reduction) but does not provide specific version numbers for any software dependencies, which is required for reproducibility. |
| Experiment Setup | Yes | For all experiments, I set ϵ = aiming for a fixed reduction rather than a restricted spectral approximation guarantee. As recommended by the authors, I performed 20 relaxation sweeps. Further, I set the number of test vectors Q to equal the dimension k of the space I aimed to approximate. As per the author suggestion, the Q = k test vectors are here computed by a single sweep of a Gauss-Seidel iteration. |