Enumerating Unique Computational Graphs via an Iterative Graph Invariant

By Chris Ying. 2019

10 citations recorded by the source corpus.

In this report, we describe a novel graph invariant for computational graphs (colored directed acylic graphs) and how we used it to generate all distinct computational graphs up to isomorphism for small graphs. The algorithm iteratively applies isomorphism-invariant operations, which take into account the graph structure and coloring, and outputs a fixed-length hash that is identical for all isomorphic computational graphs. While the algorithm cannot perfectly distinguish all pairs of non-isomorphic computational graphs, we suggest that it may be useful as a heuristic for comparing graphs.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Aaron Klein
2. Frank Hutter
3. Kevin P. Murphy
4. Esteban Real
5. Eric Christiansen
6. Chris Ying
7. Holger H. Hoos
8. Shuhei Watanabe

In Discrete Mathematics and Combinatorics

1. Frank Hutter
2. Aaron Klein
3. Kevin P. Murphy
4. Eric Christiansen
5. Esteban Real

Citations in the corpus

• NAS-Bench-101: Towards Reproducible Neural Architecture Search (2019, methodology): “Thus, we utilize an iterative graph hashing algorithm, described in (Ying, 2019), which quickly determines whether two cells are isomorphic.”