Repelling Random Walks
Authors: Isaac Reid, Eli Berger, Krzysztof Marcin Choromanski, Adrian Weller
ICLR 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We provide detailed experimental evaluation and robust theoretical guarantees. |
| Researcher Affiliation | Collaboration | Isaac Reid1 , Eli Berger2 , Krzysztof Choromanski3,4 , Adrian Weller1,5 1University of Cambridge, 2University of Haifa, 3Google Deep Mind, 4Columbia University, 5Alan Turing Institute |
| Pseudocode | Yes | Algorithm 4.1 (Random walks for Page Rank estimation). (Fogaras et al., 2005) Simulate m N runs of a simple random walk with transition probability matrix P out of every node i N, terminating with probability p at each timestep. Evaluate the estimator bπj as the fraction of walks terminating at node j, bπj := 1 Nm P N Pm j=1 I(walker terminates at j). |
| Open Source Code | Yes | Code is available at https://github.com/isaac-reid/repelling_random_walks. |
| Open Datasets | Yes | All datasets used correspond to standard graphs and are freely available online; we give links to suitable repositories in every instance. |
| Dataset Splits | No | The paper mentions training and testing data splits (e.g., 5% test split for kernel regression) but does not specify any validation splits or percentages across its experiments. |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., GPU models, CPU types, or memory specifications) used for running the experiments. |
| Software Dependencies | No | The paper does not list specific software dependencies with version numbers (e.g., Python 3.x, PyTorch 1.x, specific library versions) that would be needed for replication. |
| Experiment Setup | Yes | We take 100 repeats to compute the variance of the kernel approximation error, using a regulariser σ = 0.1 and a termination probability p = 0.5. [...] We use m = 16 random walks with a termination probability p = 0.5 and a regulariser σ = 0.1, taking 1000 repeats for statistics. [...] The termination probability is p = 0.3 and we take 1000 trials to compute the standard deviations (10000 for eurosis since it is larger). [...] We impose a restricted sampling budget with walks of length L = 16 to highlight the benefits of repelling random walks in the transient regime, and take 2500 repeats over all starting nodes for statistics. |