Efficient Near-Optimal Testing of Community Changes in Balanced Stochastic Block Models
Authors: Aditya Gangrade, Praveen Venkatesh, Bobak Nazer, Venkatesh Saligrama
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We validate these phenomena numerically on SBMs and on real-world datasets as well as Markov Random Fields where we only observe node data rather than the existence of links. We complement the above theoretical study by three experiments: the first implements the above tests on synthetic SBMs, and the second on the political blogs dataset a popular real world dataset for community detection [AG05]. Both of these experiments show excellent agreement with the theoretical predictions. |
| Researcher Affiliation | Academia | Aditya Gangrade Boston University gangrade@bu.edu Praveen Venkatesh Carnegie Mellon University vpraveen@cmu.edu Bobak Nazer Boston University bobak@bu.edu Venkatesh Saligrama Boston University srv@bu.edu |
| Pseudocode | Yes | Algorithm 1: Two Sample Tester(G, H, δ) |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code or provide links to a code repository for the methodology described. |
| Open Datasets | Yes | Next, we demonstrate that our tests perform similarly for a real dataset, specifically the Political Blogs dataset [AG05]. |
| Dataset Splits | No | The paper does not provide specific details on training, validation, or test dataset splits (e.g., exact percentages or sample counts). |
| Hardware Specification | No | The paper does not explicitly describe the specific hardware (e.g., GPU/CPU models, memory) used to run its experiments. |
| Software Dependencies | No | The paper mentions using Python libraries such as SciPy, NumPy, Matplotlib, and Scikit-learn, but it does not specify their version numbers. |
| Experiment Setup | Yes | Recovery is performed by regularised spectral clustering, for which a detailed description is given in Appendix C.1. In Appendix C.1, it states: 'Spectral clustering requires a choice of k. In all experiments we set k = 2. It also requires a normalisation for the adjacency matrix. For the SBM experiments, we use the normalised adjacency matrix A = D−1/2AD−1/2. The regularised spectral clustering for sparse graphs is described in [JY16]. It involves adding µnI to the adjacency matrix prior to computing the eigenvalues. We set µn = p log n/(n(a + b)).' |