On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters
Authors: Matthias Lanzinger, Pablo Barcelo
ICLR 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we provide a precise characterization of the WL-dimension of labeled graph motif parameters. We finally delve into the challenge of recognizing the WL-dimension of various graph parameters. We give a polynomial time algorithm for determining the WL-dimension of the subgraph counting problem for given pattern P, answering an open question from previous work. Our main contributions are summarized below. It is worth noting that all such results are derived within the framework established in Chen et al. (2020), which focuses on labeled graphs. This introduces an additional level of intricacy into all the proofs presented in this paper. |
| Researcher Affiliation | Academia | Matthias Lanzinger TU Wien & University of Oxford matthias.lanzinger@tuwien.ac.at Pablo Barceló PUC Chile & IMFD & CENIA pbarcelo@uc.cl |
| Pseudocode | No | The paper does not contain a structured pseudocode or algorithm block. |
| Open Source Code | No | The paper does not provide any statement or link indicating the availability of open-source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not report on empirical studies involving datasets, thus no information about public dataset availability is provided. |
| Dataset Splits | No | The paper focuses on theoretical contributions and does not involve experimental training, validation, or testing, so no dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not involve computational experiments that would require specific hardware, so no hardware specifications are provided. |
| Software Dependencies | No | The paper focuses on theoretical concepts and does not describe implementation details that would require listing specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training configurations. |