Enumerating Unique Computational Graphs via an Iterative Graph Invariant

Understand

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.