Constructing Hard Examples for Graph Isomorphism

Anuj Dawar, Kashif Khan
9/21/2018
cs.CCcs.DM

No confident code implementation found for this paper.

Abstract

We describe a method for generating graphs that provide difficult examples for practical Graph Isomorphism testers. We first give the theoretical construction, showing that we can have a family of graphs without any non-trivial automorphisms which also have high Weisfeiler-Leman dimension. The construction is based on properties of random 3XOR-formulas. We describe how to convert such a formula into a graph which has the desired properties with high probability. We validate the method by an experimental implementation. We construct random formulas and validate them with a SAT solver to filter through suitable ones, and then convert them into graphs. Experimental results demonstrate that the resulting graphs do provide hard examples that match the hardest known benchmarks for graph isomorphism.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Expectation-Complete Graph Representations with Homomorphisms

82% match1 repo32023

SAT-Based Algorithms for Regular Graph Pattern Matching

80% match2023

$O(p \log d)$ Subgraph Isomorphism using Stigmergic Swarming Agents

79% match2025

Is 3-(F)WL Enough to Distinguish All 3D Graphs?

79% match2024

On the Expressivity and Sample Complexity of Node-Individualized Graph Neural Networks

78% match1 repo12024

On Structural Expressive Power of Graph Transformers

78% match2023

Cite this paper

@article{dawar2018constructing,
  title  = {Constructing Hard Examples for Graph Isomorphism},
  author = {Anuj Dawar and Kashif Khan},
  year   = {2018},
  eprint = {1809.08154},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/1809.08154}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/1809.08154.svg)](https://codeofpaper.com/paper/1809.08154)

Discussion