Community detection using fast low-cardinality semidefinite programming
Authors: Po-Wei Wang, J. Zico Kolter
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We demonstrate in the experiments that our proposed low-cardinality algorithm is far less likely to get stuck at local optima than the greedy local move procedure. On small datasets that are solvable with a traditional SDP solver, our proposed solver empirically reaches the globally optimal solution of the semidefinite relaxation given enough cardinality and is orders of magnitude faster than traditional SDP solvers. Our method uniformly improves over both the standard Louvain and Leiden methods, which are the state-of-the-art algorithms for community detection, with 2.2x time cost. |
| Researcher Affiliation | Collaboration | Po-Wei Wang Machine Learning Department Carnegie-Mellon University Pittsburgh, PA poweiw@cs.cmu.edu J. Zico Kolter Department of Computer Science Carnegie-Mellon University & Bosch Center for Artificial Intelligence Pittsburgh, PA zkolter@cs.cmu.edu |
| Pseudocode | Yes | Algorithm 1 The Leiden-Locale method 1: procedure LEIDEN-LOCALE(Graph G, Partition P) 2: do 3: E Locale Embeddings(G, P) Replace the Local Move(G, P) in Leiden 4: P Locale Rounding(G, P, E) 5: G, P, done Leiden Refine Aggregate(G, P) [43, Algorithm A.2, line 5-9] 6: while not done 7: return P 8: end procedure |
| Open Source Code | Yes | Source code for our implementation is available at https://github.com/locuslab/sdp_clustering. |
| Open Datasets | Yes | We use 3 standard toy networks that are small enough to be solvable via an SDP solver, including zachary [50], polbook [34], and football [21]. We compare to 5 large-scale networks, including DBLP, Amazon, Youtube [47], IMDB[46],and Live Journal [3, 29]. |
| Dataset Splits | No | The paper mentions various datasets but does not specify any training, validation, or test splits in terms of percentages, counts, or references to predefined splits. |
| Hardware Specification | No | The paper does not provide any specific hardware details such as GPU models, CPU types, or cloud instance specifications used for running the experiments. |
| Software Dependencies | No | The paper mentions using "SCS [35], a splitting conic solver" and the "leidenalg package" but does not provide specific version numbers for these or any other software dependencies. |
| Experiment Setup | Yes | For the greedy local move procedure, we run it iteratively till convergence (or till the function increment is less than 10 8 after n consecutive changes to avoid floating-point errors). For the Locale algorithm, we test two different settings: running only two rounds of updates or running it till convergence, followed by the rounding procedure. ... We found that two inner iterations followed by the rounding procedure is more efficient in the overall multi-level algorithm over multiple iterations, while substantially improving over past works. |