Spectral Clustering of graphs with the Bethe Hessian
Authors: Alaa Saade, Florent Krzakala, Lenka Zdeborová
NeurIPS 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We show numerically that our approach performs as well as the belief-propagation algorithm, without needing prior knowledge of any parameter, making it the simplest algorithmically among the best-performing clustering methods. The paper is organized as follows. In Sec. 1 we give the expression of the Bethe Hessian operator. We discuss in detail its properties and its connection with both the non-backtracking operator and an Ising spin glass in Sec. 2. In Sec. 3, we study analytically the spectrum in the case of the stochastic block model. Finally, in Sec. 4 we perform numerical tests on both the stochastic block model and on some real networks. |
| Researcher Affiliation | Academia | Alaa Saade Laboratoire de Physique Statistique, CNRS UMR 8550 Ecole Normale Superieure, 24 Rue Lhomond Paris 75005 Florent Krzakala Sorbonne Universit es, UPMC Univ Paris 06 Laboratoire de Physique Statistique, CNRS UMR 8550 Ecole Normale Superieure, 24 Rue Lhomond Paris 75005 Lenka Zdeborov a Institut de Physique Th eorique CEA Saclay and CNRS URA 2306 91191 Gif-sur-Yvette, France |
| Pseudocode | No | The paper describes the steps of the spectral algorithm in paragraph text (e.g., 'The spectral algorithm that is the main result of this paper works as follows...'), but it does not include a clearly labeled pseudocode block or algorithm section. |
| Open Source Code | Yes | A Matlab implementation to reproduce the results of the Bethe Hessian for both real and synthetic networks is provided as supplementary material. |
| Open Datasets | Yes | We illustrate the efficiency of the algorithm for graphs generated by the stochastic block model. We finally turn towards actual real graphs to illustrate the performances of our approach... In Table 1 we give the overlap and the number of groups to be identified. Polbooks (q = 3) [1] Polblogs (q = 2) [10] Karate (q = 2) [24] Football (q = 12) [6] Dolphins (q = 2) [16] Adjnoun (q = 2) [8] |
| Dataset Splits | No | The paper evaluates performance on synthetic and real networks but does not explicitly describe train/validation/test dataset splits, percentages, or methodology for partitioning the data. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware used to run the experiments, such as CPU/GPU models, memory, or cloud resources. |
| Software Dependencies | No | The paper mentions 'A Matlab implementation' is provided, but it does not specify any version numbers for Matlab or any other software libraries or dependencies, which are necessary for full reproducibility. |
| Experiment Setup | No | The paper describes properties of the graphs used (e.g., 'graph of 10^4 vertices with 2 clusters, with c=4, cin =7, cout =1') and some algorithmic choices ('For q = 2, we clustered according to the signs... For q = 3, we used k-means...'), but it does not provide explicit details about a typical experimental setup such as hyperparameters, learning rates, optimizer settings, or training schedules. |