Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Spectrally Approximating Large Graphs with Smaller Graphs
Authors: Andreas Loukas, Pierre Vandergheynst
ICML 2018 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | As a proof of concept, Figure 2 compares the actual constants ϵk with the bound of Theorem 3.1 when utilizing REC with a heavy-edge potential to coarsen the following benchmark graphs: (i) a point cloud representing a bunny obtained by re-sampling the Stanford bunny 3Dmesh (Turk & Levoy, 1994) and applying a k-nn construction (N = 1000, r = 0.4, k = 30), (ii) a k-nn similarity graph capturing the geometry of a 2D manifold usually referred to as Swiss roll (N = 1000, r = 0.4, k = 10), (iii) A network describing the interaction of yeast proteins (Rossi & Ahmed, 2015) (N = 1458, r = 0.25, davg = 2, dmax = 56), and (iv) a d-regular graph (N = 400, r = 0.4, d = 20). and Figure 4 depicts the growth of the actual relative error with r. The particular experiment corresponds to a clustering problem involving N = 1000 images, each depicting a selected digit between 0 and 4 from the MNIST database (i.e., K = 5). |
| Researcher Affiliation | Academia | 1 Ecole Polytechnique F ed erale Lausanne, Switzerland. Correspondence to: Andreas Loukas <andreas.loukas@epfl.ch>. |
| Pseudocode | Yes | Algorithm 1 Randomized Edge Contraction (REC) |
| Open Source Code | No | The paper does not include an unambiguous statement that the authors are releasing the code for the work described in this paper, nor does it provide a direct link to a source-code repository. |
| Open Datasets | Yes | As a proof of concept, Figure 2 compares the actual constants ϵk with the bound of Theorem 3.1 when utilizing REC with a heavy-edge potential to coarsen the following benchmark graphs: (i) a point cloud representing a bunny obtained by re-sampling the Stanford bunny 3Dmesh (Turk & Levoy, 1994) and applying a k-nn construction (N = 1000, r = 0.4, k = 30), (ii) a k-nn similarity graph capturing the geometry of a 2D manifold usually referred to as Swiss roll (N = 1000, r = 0.4, k = 10), (iii) A network describing the interaction of yeast proteins (Rossi & Ahmed, 2015) (N = 1458, r = 0.25, davg = 2, dmax = 56), and (iv) a d-regular graph (N = 400, r = 0.4, d = 20). and Figure 4 depicts the growth of the actual relative error with r. The particular experiment corresponds to a clustering problem involving N = 1000 images, each depicting a selected digit between 0 and 4 from the MNIST database (i.e., K = 5). |
| Dataset Splits | No | The paper mentions using the MNIST database and other benchmark graphs but does not specify exact dataset split percentages, absolute sample counts for each split, or reference predefined standard splits with citations that include such details. |
| Hardware Specification | No | The paper does not explicitly describe the specific hardware used to run its experiments, such as GPU models, CPU models, or cloud computing specifications. |
| Software Dependencies | No | The paper does not provide specific software dependency details, such as library or solver names with their version numbers, needed to replicate the experiments. |
| Experiment Setup | Yes | As a proof of concept, Figure 2 compares the actual constants ϵk with the bound of Theorem 3.1 when utilizing REC with a heavy-edge potential to coarsen the following benchmark graphs: (i) a point cloud representing a bunny obtained by re-sampling the Stanford bunny 3Dmesh (Turk & Levoy, 1994) and applying a k-nn construction (N = 1000, r = 0.4, k = 30), (ii) a k-nn similarity graph capturing the geometry of a 2D manifold usually referred to as Swiss roll (N = 1000, r = 0.4, k = 10), (iii) A network describing the interaction of yeast proteins (Rossi & Ahmed, 2015) (N = 1458, r = 0.25, davg = 2, dmax = 56), and (iv) a d-regular graph (N = 400, r = 0.4, d = 20). and The particular experiment corresponds to a clustering problem involving N = 1000 images, each depicting a selected digit between 0 and 4 from the MNIST database (i.e., K = 5). We constructed a 12-nearest neighbor similarity graph and repeated the experiment 10 times, each time using a different image set, selected uniformly at random. and for illustration purposes, we here additionally perform t = {2, 10} steps of a simple power iteration scheme, yielding an O(t M(K 1)) overhead. |