Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community Mining
Authors: Aritra Konar, Nicholas D. Sidiropoulos
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We corroborate these findings on real-world graphs by applying the simple greedy algorithm for OQC with improved hyperparameter tuning, to quickly generate high-quality approximations of the size-density frontier. Our findings indicate that OQC not only extracts high quality (near)-cliques, but also large and loosely-connected subgraphs that exhibit well defined local community structure. The latter discovery is particularly intriguing, since OQC is not explicitly geared towards community detection. |
| Researcher Affiliation | Academia | Aritra Konar1, Nicholas D. Sidiropoulos2 1KU Leuven, Leuven, Belgium 2University of Virginia, Charlottesville, USA aritra.konar@kuleuven.be, nikos@virginia.edu. |
| Pseudocode | No | The paper describes algorithms like 'greedy vertex-peeling algorithm' and 'Alternating Direction Method of Multipliers (ADMM)' but does not include any formal pseudocode blocks or algorithm listings. |
| Open Source Code | No | The paper states: 'The code for the ADMM algorithm for solving Dk S was the same employed in (Konar and Sidiropoulos 2021).' This refers to code from a previous publication, implying its existence and prior availability, but this paper itself does not provide a new specific link or explicitly state that its *own* implementations or analysis code are open-source or available with this publication. |
| Open Datasets | Yes | We used a collection of datasets (summarized in Table ??) obtained from standard repositories (Leskovec and Krevl 2014) to test the performance of all methods. |
| Dataset Splits | No | The paper describes evaluating algorithms on real-world graphs and generating size-density frontiers but does not specify any train/validation/test splits for the datasets used in its experimental evaluation. |
| Hardware Specification | Yes | All our experiments were performed in Matlab on a Macbook equipped with 16GB RAM and an M2 processor. |
| Software Dependencies | No | The paper states that experiments were performed 'in Matlab', but it does not specify the version of Matlab or any other specific software libraries or their versions used in the implementation. |
| Experiment Setup | Yes | After running the GREEDYOQC algorithm on a dataset, we perform a grid search on α in the range [0.01, 0.99], in increments of 0.01. Each value of α defines a different edge-surplus function, using which the subgraph with the largest edge surplus amongst the family of nested subgraphs generated by GREEDYOQC is selected. |