Fast Approximate Spectral Clustering for Dynamic Networks
Authors: Lionel Martin, Andreas Loukas, Pierre Vandergheynst
ICML 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The paper concludes with a proof of concept comparison against Sot A approximation algorithms for Spectral Clustering (Section 5). Our experiments confirm that d CSC yields computational benefits when the graph dynamics are bounded. A case in point: we can cluster 30 000 node graphs 3.9 faster than SC and 1.5 faster than CSC in average. |
| Researcher Affiliation | Academia | 1 Ecole Polytechnique F ed erale de Lausanne, Switzerland. Correspondence to: Lionel Martin <lionel.martin@epfl.ch>, Andreas Loukas <andreas.loukas@epfl.ch>. |
| Pseudocode | Yes | Algorithm 1 Dynamic CSC Input: (G1, G2, . . . , Gτ), p, d Output: (X1, X2, . . . , Xτ) and Algorithm 2 Dynamic CSC with adaptive p Input: (G1, G2, . . . , Gτ), d, k, δ, ϵ Output: (X1, X2, . . . , Xτ) |
| Open Source Code | No | The paper provides a link for IASC, a state-of-the-art baseline method ('https://github.com/charanpald/sandbox'), but does not provide open-source code for their own proposed method (d CSC). |
| Open Datasets | No | The paper mentions using a 'Stochastic Block Model (SBM)' to generate synthetic data for experiments. While SBM is a well-known model, the paper does not provide a direct link, DOI, or specific citation for a pre-existing, publicly available *dataset* that was used, nor does it specify how to access the *generated* data. |
| Dataset Splits | No | The paper describes how graphs are constructed and perturbed for evaluation but does not specify traditional training, validation, or test dataset splits. |
| Hardware Specification | No | The paper does not provide specific hardware details such as CPU/GPU models, memory, or cloud instance types used for running experiments. |
| Software Dependencies | No | The paper states 'All our experiments are designed using the GSPBox (Perraudin et al., 2014)'. However, it does not specify a version number for GSPBox or any other software dependencies. |
| Experiment Setup | Yes | As is common practice, we use the Stochastic Block Model (SBM) to evaluate the efficiency of our spectral clustering method (e.g., G orke et al., 2013; Tremblay et al., 2016). In SBM, data are clustered in k classes and the n nodes are connected at random with edge-wise probability that depends if the two extremities belong to the same cluster (q1) or not (q2 with q2 q1). In the following, we qualify the SBM parameters in terms of the nodes average degree δ and the ratio q2/q1 that captures the graph clusterability (Decelle et al., 2011). Following the recommendations of the former work, we set q2 q1 = δ δ 2( δ+ δ(k 1)) to construct non-trivially clusterable graphs. We replicate the construction of 100 different SBM with the same parameters, then we alter each with 1% of node reassignment and 1% of edges modifications. The modified graph is used for the evaluation of all methods. We set n = 15000, k = 25, δ = 60. |