Fast Bidirectional Probability Estimation in Markov Models
Authors: Siddhartha Banerjee, Peter Lofgren
NeurIPS 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | To demonstrate the efficiency of our algorithm on large Markov chains, we use heat kernel estimation (cf. Section 3) as an example application. In Figure 2, we compare the runtime of different algorithms for heat kernel computation on four real-world graphs, ranging from millions to billions of edges. |
| Researcher Affiliation | Academia | Siddhartha Banerjee sbanerjee@cornell.edu Peter Lofgren plofgren@cs.stanford.edu [...] Siddhartha Banerjee is an assistant professor at the School of Operations Research and Information Engineering at Cornell [...] Peter Lofgren is a graduate student in the Computer Science Department at Stanford |
| Pseudocode | Yes | Algorithm 1 REVERSE-PUSH(v, i) [...] Algorithm 2 Bidirectional-MSTP(P, σ, t, ℓmax, δ) |
| Open Source Code | No | For reproducibility, our source code is available on our website (cf. [8]). |
| Open Datasets | Yes | Pokec [19], Live Journal [20], and Orkut [20] datasets are from the SNAP [21]; Twitter-2010 [22] was downloaded from the Laboratory for Web Algorithmics [23]. |
| Dataset Splits | No | The paper does not provide specific dataset split information (exact percentages, sample counts, citations to predefined splits, or detailed splitting methodology) needed to reproduce the data partitioning. |
| Hardware Specification | No | The paper does not provide specific hardware details (exact GPU/CPU models, processor types with speeds, memory amounts, or detailed computer specifications) used for running its experiments. |
| Software Dependencies | No | All three algorithms were implemented in Scala for the forward push algorithm, our implementation follows the code linked from [5]). (Only mentions Scala as the implementation language, without specific library versions or self-contained solver versions.) |
| Experiment Setup | Yes | We set average walk-length ℓ= 5 (since longer walks will mix into the stationary distribution), and set the maximum length to ℓ+10 √ℓ ≈ 27; the probability of a walk being longer than this is 10^-12, which is negligible. |