A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening
Authors: Gecia Bravo Hermsdorff, Lee Gunderson
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 5 Experimental results In this section, we empirically validate our framework and compare it with existing algorithms. We consider two cases of our general framework, namely graph sparsification (excluding regimes involving edge contraction), and graph coarsening (prioritizing reduction of nodes). In addition, as graph reduction is often used in graph visualization, we generated videos of our algorithm simultaneously sparsifying and coarsening several real-world datasets (see footnote 2 and Appendix Section I). |
| Researcher Affiliation | Academia | Gecia Bravo-Hermsdorff* Princeton Neuroscience Institute Princeton University Princeton, NJ, 08544, USA geciah@princeton.edu Lee M. Gunderson* Department of Astrophysical Sciences Princeton University Princeton, NJ, 08544, USA leeg@princeton.edu |
| Pseudocode | Yes | Algorithm 1 Reduce Graph 1: Inputs: graph G, fraction of sampled edges to act upon q, minimum E[r] per edge acted upon d, and a Stop Criterion 2: Initialize e G0 G, t 0, stop False 3: while not (stop) do 4: Sample an independent edge set 5: for (edge e) in (sampled edges) do 6: Compute e, me (see equations (7) and (9)) 7: Evaluate β?e, according to d (see Tables in Figure 1) 8: end for 9: Choose β such that a fraction q of the sampled edges (those with the lowest β?e) are acted upon 10: Probabilistically choose to reweight, delete, or contract these edges 11: Perform reweights and deletions to e Gt 12: Perform contractions to e Gt 13: e Gt+1 e Gt, t t + 1 14: stop Stop Criterion( e Gt) 15: end while 16: return reduced graph e Gt |
| Open Source Code | No | No explicit statement or link providing access to the source code for the methodology described in this paper was found. Footnote 2 links to a YouTube playlist of animated examples, not source code. |
| Open Datasets | Yes | We applied our algorithm without contraction (Ours) and compare with that of Spielman & Srivastava [20] (Spielman et al) using three datasets: Left: a collaboration network of Jazz musicians (198 nodes and 2742 edges) from [51]; Middle: the C. elegans posterior nervous system connectome (269 nodes and 2902 edges) from [52]; and Right: a weighted social network of face-to-face interactions between primary school students, with initial edge weights proportional to the number of interactions between pairs of students (236 nodes and 5899 edges) from [53]. |
| Dataset Splits | No | The paper does not provide specific dataset split information (exact percentages, sample counts, citations to predefined splits, or detailed splitting methodology) for training, validation, or testing. |
| Hardware Specification | No | The paper does not provide specific hardware details (exact GPU/CPU models, processor types, or memory amounts) used for running its experiments. |
| Software Dependencies | Yes | [58] Bell, W., Olson, L. & Schroder, J. Pyamg: Algebraic multigrid solvers in python v3. 0, 2015. URL http://www. pyamg. org. Release 3 (2015). |
| Experiment Setup | Yes | Algorithm 1 Reduce Graph 1: Inputs: graph G, fraction of sampled edges to act upon q, minimum E[r] per edge acted upon d, and a Stop Criterion and Empirically, we find that one is able to set q 1/16 and d 1/4 with minimal loss in reduction quality (see Appendix Section E). |