Power Iterated Color Refinement
Authors: Kristian Kersting, Martin Mladenov, Roman Garnett, Martin Grohe
AAAI 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We support our theoretical results with experiments on real-world graphs with millions of edges. |
| Researcher Affiliation | Academia | Kristian Kersting TU Dortmund University {fn.ln}@cs.tu-dortmund.de Martin Mladenov TU Dortmund University {fn.ln}@cs.tu-dortmund.de Roman Garnett University of Bonn garnett@uni-bonn.de Martin Grohe RWTH Aachen grohe@informatik.rwth-aachen.de |
| Pseudocode | Yes | Algorithm 1: CGCR(A): CG for Color Refinement; Algorithm 2: COLORS(M); Algorithm 3: CHARACTMAT(M); Algorithm 4: CGCR(A): CG for Color Refinement; Algorithm 5: HCGCR(A): Hashed CGCR; Algorithm 6: PICGCR(A): Power Iterated CGCR |
| Open Source Code | Yes | we implemented naive versions of CGCR, HCGCR (denoted as Hashing and available at https://github.com/rmgarnett/fast_wl/) and PICGCR in Matlab |
| Open Datasets | Yes | Table 1: Scaling results on graphs generated from http://www.cise.ufl.edu/research/sparse/matrices/index.html (matrices were turned into graphs using A := A + AT and thresholding |A| > 0). |
| Dataset Splits | No | The paper does not specify validation splits or detailed train/validation/test partitioning for the datasets used in experiments. |
| Hardware Specification | Yes | on a single Linux machine( 4 3.4 GHz cores, 32 GB main memory) |
| Software Dependencies | No | we implemented naive versions of CGCR, HCGCR (...) and PICGCR in Matlab. Matlab version number is not specified. |
| Experiment Setup | Yes | The convergence threshold ϵ for PI was set to 10 8 and the damping factor α to 0.95. The maximum number of PI iterations was set to 500 (denoted as PIfix) resp. to min(2k, τ) (PIflex). |