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 Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Optimal Graph Clustering without Edge Density Signals
Authors: Maximilien Dreveton, Elaine Liu, Matthias Grossglauser, Patrick Thiran
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our numerical experiments on both synthetic and real datasets confirm that spectral clustering algorithms incorporating k2 eigenvectors outperform traditional spectral approaches. Our numerical experiments demonstrate that these methods outperform traditional spectral approaches that rely only on k eigenvectors, both on synthetic and real datasets. 3 Numerical Experiments |
| Researcher Affiliation | Academia | Maximilien Dreveton EPFL EMAIL Elaine S. Liu EPFL EMAIL Matthias Grossglauser EPFL EMAIL Patrick Thiran EPFL EMAIL |
| Pseudocode | Yes | We also provide in the Appendix E the pseudo-code of all the algorithms. Algorithm 1: Spectral Clustering: scikit-learn. Algorithm 2: Spectral Clustering: standard block model variant. Algorithm 3: Spectral Clustering: degree-corrected block model variant. Algorithm 4: Orthogonal Spectral Clustering. Algorithm 5: Subspace Clustering on Spectral Embedding. Algorithm 6: Greedy Subspace Projection Clustering (gspc). Algorithm 7: Thresholded Cosine Spectral Clustering (tcsc). |
| Open Source Code | Yes | Our code is available at https://github.com/mdreveton/neurips-pabm. |
| Open Datasets | Yes | Our numerical experiments on both synthetic and real datasets confirm that spectral clustering algorithms incorporating k2 eigenvectors outperform traditional spectral approaches. Table 3: Summary of some statistics of the real data sets considered. (Mentions datasets like political Blogs, live Journal-top2, citeseer, cora, MNIST, Fashion MNIST, CIFAR-10 with corresponding citations from well-known sources). |
| Dataset Splits | No | The paper does not explicitly mention training/test/validation splits for the real datasets used. For synthetic data, it describes how data was generated (e.g., 'We sampled graphs with n = 900 vertices in k = 3 clusters of same size, average edge density ρ = 0.05.'). For real datasets, it mentions preprocessing steps like 'largest connected components' or 'extract the two largest clusters' or 'k-nearest neighbor graph...obtained from n = 10,000 images' but not explicit data splits for evaluation. |
| Hardware Specification | No | We only used a laptop (CPU, no GPU) to perform the experiments. Some information on the time of execution are provided in the Appendix. |
| Software Dependencies | No | sklearn: Lloyd s algorithm applied to the embedding formed by the k smallest eigenvectors of the graph s normalized Laplacian, corresponding to the implementation available in the scikit-learn library. For subspace clustering, we use the implementation provided in You et al. (2016) and available at https://github.com/Chong You/ subspace-clustering. |
| Experiment Setup | Yes | In Figure 1a, we let ξ = 1 and vary c. This is precisely the setting of Example 1. We observe that pabm and osc variants, which are specifically designed for PABM, recover the clusters when c is large enough, whereas the variants tailored for SBM and DCBM fail to do so. This illustrates that pabm and osc successfully learn the clusters without edge-density signal by using the difference in the individual vertex degree connectivity patterns. In Figure 1b, we set c = 0.8 and let ξ vary. We sampled graphs with n = 900 vertices in k = 3 clusters of same size, average edge density ρ = 0.05. In all experiments, we set τmin = 0.05 and τmax = 5. |