Sublinear-Time Clustering Oracle for Signed Graphs
Authors: Stefan Neumann, Pan Peng
ICML 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We evaluate our algorithm for constructing such an oracle and answering membership queries on both synthetic and real-world datasets, validating its performance in practice. and We evaluate our algorithms on synthetic and on real-world datasets (Sec. 4) and show that our oracles are practical. |
| Researcher Affiliation | Academia | 1KTH Royal Institute of Technology, Stockholm, Sweden 2School of Computer Science and Technology, University of Science and Technology of China, Hefei, China. |
| Pseudocode | Yes | Algorithm 1 Estimating the dot product pt u D 1/2, pt v D 1/2, Algorithm 2 Preprocessing: Constructing a clustering oracle, Algorithm 3 Answering the community membership of a vertex v |
| Open Source Code | Yes | Our source code is available on github.2 with footnote 2https://github.com/Stefan Research/ signed-oracle |
| Open Datasets | Yes | We created three dataset. Wiki L contains all politicans and all articles linked on their pages; we included all edges that contain at least one politician... We make them available on github.2 with footnote 2https://github.com/Stefan Research/ signed-oracle. |
| Dataset Splits | No | The paper describes how seed nodes are selected (e.g., 'the seeded oracles obtained 10 (5) seeds for each Ui (Vi); the unseeded oracles sampled 5k vertices') but does not specify explicit training, validation, or test dataset splits of the overall datasets used for evaluation. |
| Hardware Specification | Yes | We experimentally evaluated our algorithms on a Mac Book Pro with 16 GB RAM and a 2 GHz Quad-Core Intel Core i5. |
| Software Dependencies | No | Our algorithms were implemented in C++11. (While a specific language version is given, no other software dependencies or libraries with version numbers are mentioned to ensure reproducibility of the environment.) |
| Experiment Setup | Yes | Unless stated otherwise, our oracles used 1000 random walks of length 20. and We ran the oracles with t = 2 random walk steps and R = 400 random walks, unless stated otherwise. |