Counting and Sampling Markov Equivalent Directed Acyclic Graphs
Authors: Topi Talvitie, Mikko Koivisto7984-7991
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Empirical results indicate that our algorithms are superior to previously presented algorithms over a range of inputs; graphs with hundreds of vertices and thousands of edges are processed in a second on a desktop computer. In Section 5 we report on empirical results and draw conclusions as to which algorithm is the fastest for what type of instances. |
| Researcher Affiliation | Academia | Topi Talvitie Department of Computer Science University of Helsinki topi.talvitie@helsinki.fi; Mikko Koivisto Department of Computer Science University of Helsinki mikko.koivisto@helsinki.fi |
| Pseudocode | Yes | Algorithm Orient: (C, s) 7 Cs O1 Create C by orienting each line u v of C as u v if s is closer to u than v in C (in the shortest-path distance). O2 As long as C has a flag u v w as an induced subgraph, update C by orienting v w as v w. O3 Output C . and Algorithm Memo Mao: C 7 µ(C) M1 Let a[ ] be a storage indexed by S V ; initially a[S] returns 1 if S is a singleton, and NULL otherwise. M2 Output Sum-Product(V ). Function Sum-Product(S) S1 If a[S] = NULL, return a[S]; else let a[S] 0. S2 For each vertex s S: Run Orient to get C , the s-orientation of C[S]. Let (Si)c i=1 be the vertex sets of the CCs of C . Let a[S] a[S] + Qc i=1 Sum-Product(Si). S3 Return a[S]. |
| Open Source Code | Yes | We implemented all four algorithms in C++2, using only a single thread of execution and exact integer computations. [Footnote 2: github.com/ttalvitie/count-mao] |
| Open Datasets | No | We run all the algorithms on randomly generated UCCGs with n vertices and rn edges, where 16 n 1024 and 2 r 12. The random generation works in two phases: First we generate a tree by starting from a single vertex and repeatedly adding a vertex as a neighbor of a randomly chosen vertex in the current tree until the tree has n vertices. After this, we add edges between pairs of vertices chosen uniformly at random, while on each step maintaining the chordality of the graph, until the graph has rn edges. The paper describes a random generation process for the dataset but does not provide concrete access information (link, DOI, formal citation) to a publicly available version of the generated datasets. |
| Dataset Splits | No | We run all the algorithms on randomly generated UCCGs with n vertices and rn edges, where 16 n 1024 and 2 r 12. For each r and n, we generated 1000 UCCGs and ran each algorithm for every UCCG with time limit of 10 minutes and memory limit of 4 GB. The paper describes the generation of instances for evaluation but does not specify a training/validation/test split for a machine learning model, as the work is on algorithms for counting and sampling. |
| Hardware Specification | No | graphs with hundreds of vertices and thousands of edges are processed in a second on a desktop computer. The paper mentions running experiments on a 'desktop computer' but provides no specific hardware details such as CPU/GPU models, memory, or other specifications. |
| Software Dependencies | No | We implemented all four algorithms in C++2, using only a single thread of execution and exact integer computations. The paper mentions C++ but does not provide specific version numbers for the language or any libraries/solvers used. |
| Experiment Setup | Yes | For each r and n, we generated 1000 UCCGs and ran each algorithm for every UCCG with time limit of 10 minutes and memory limit of 4 GB. |