Automated Symmetry Discovery via Graph Automorphism

31 concepts23 papers

Many combinatorial problems—ranging from planning and model checking to probabilistic inference and mixed-integer programming—suffer from the curse of dimensionality. As the number of variables grows, the state space explodes exponentially. Yet, many of these massive state spaces contain latent structural redundancies. For example, in a network routing problem, two identical servers can be swapped without changing the system's underlying behavior. If an algorithm treats these symmetric states as entirely distinct, it wastes immense computational effort re-solving identical subproblems.

Historically, exploiting these symmetries required human experts to manually specify rules or write models in high-level relational languages (like first-order logic) that explicitly preserve structure. However, when a problem is presented in a low-level, "grounded," or propositional format, its symmetries become hidden.

The core insight of graph-based symmetry discovery is that we can automatically detect these hidden redundancies by translating the low-level problem into a structured, vertex-colored graph. If two components of a problem are structurally identical, they will manifest as a graph automorphism—a structural self-isomorphism that preserves edge connections and vertex colors. By leveraging highly optimized, off-the-shelf graph isomorphism solvers, algorithms can discover global problem symmetries in a completely black-box manner, bypassing the need for manual domain knowledge.

Mapping Problems to Colored Graphs

To find symmetries automatically, we must first translate an abstract problem into a graph without losing its semantic meaning. This is achieved through vertex coloring. By assigning unique colors to different types of entities (such as variables, values, operators, or constraints), we ensure that the graph automorphism solver only permutes elements that are truly interchangeable.

[Problem Representation] ───> [Vertex-Colored Graph] ───> [Automorphism Solver] ───> [Symmetry Groups (Orbits)]

Different domains implement this mapping based on their specific structural rules:

  • Model Checking: To mitigate state explosion when verifying complex circuits, Clarke et al. mapped the topology of shared variables and concurrent processes to a colored hypergraph. The automorphisms of this hypergraph correspond directly to the structural symmetries of the underlying state space.
  • Automated Planning: In state-based planning, Pochter et al. constructed graphs where variables, values, and operators are represented as distinct nodes. Permutations that leave this graph invariant reveal actions and objects that behave identically, allowing planners to recognize equivalent paths before initiating a search.
  • Decision-Making Under Uncertainty: For Partially Observable Markov Decision Processes (POMDPs), Kim transformed transition and reward functions into sparse, vertex-colored graphs. This encoding captures internal reflections and rotations within the state-action space, even when individual states are not strictly identical.
  • Discrete Optimization: In mixed-integer nonlinear programming (MINLP), constraints can be highly heterogeneous. Hojny demonstrated that complex algebraic operations (like sums and products) can be represented using specialized subgraph structures, or "gadgets." This allows a global symmetry framework to detect automorphisms across linear, nonlinear, and boolean constraints simultaneously.
  • Constraint Satisfaction: To distinguish between the rules of a problem and its actual solutions, Cohen et al. mapped variable-value pairs to vertices in a hypergraph where edges represent disallowed assignments, formalizing constraint symmetries as automorphisms of the resulting microstructure complement graph.

Collapsing the State Space into Orbits

Once a graph automorphism tool identifies the symmetry group of a problem, the next question is how to use it to accelerate computation. The fundamental mechanism is the partitioning of the state space into equivalence classes called orbits.

If two states belong to the same orbit, they are structurally identical. Consequently, an algorithm only needs to compute a value, verify a property, or expand a path for a single representative element of each orbit. The rest of the orbit can simply inherit the result.

In state-based planning, searching directly within this "orbit space" avoids expanding redundant paths, yielding massive speedups in highly symmetric domains (Pochter et al.). Taking this further, Abdulaziz et al. showed that one can decompose a large planning problem into a single "descriptive quotient" problem, solve it once, and then stitch the resulting plan together to solve the original task.

In probabilistic graphical models (PGMs), operating over orbits enables "lifted" inference directly on low-level representations. Niepert introduced Orbital Markov Chains, which allow Markov Chain Monte Carlo (MCMC) algorithms to "jump" between equivalent states across orbits, dramatically accelerating convergence to the true distribution. Similarly, Holtzen et al. encoded variable assignments as node colorings in low-level factor graphs, designing exact and approximate solvers whose computational complexity scales with the number of unique orbits rather than the total size of the state space.

Bypassing High-Level Symbolic Logic

A major historical bottleneck of lifted inference and symmetry reduction was the requirement that models be specified in high-level relational languages (like first-order logic or Markov Logic Networks). Graph-based symmetry discovery completely removes this barrier by extracting structure directly from raw, propositional representations.

As Kersting et al. demonstrated with Counting Belief Propagation, significant structural symmetries exist within traditional propositional factor graphs even when they are not explicitly defined. By discovering these redundancies directly from the graph topology, standard graphical models can be compressed automatically. To scale this to massive models, Niepert focused on identifying model symmetries purely through the underlying mathematical graph structure, ensuring the approach remains applicable to complex dependencies like transitivity without relying on specific logical syntax.

[Propositional Factor Graph] ───> [Topology Analysis] ───> [Compressed Lifted Graph]

When exact symmetries are rare, the graph-based framework can be relaxed to find approximate or conditional redundancies:

  • Approximate Symmetries: Sen et al. utilized approximate bisimulation and factor binning on raw variable-dependency graphs, allowing users to trade a small amount of accuracy for orders-of-magnitude speedups.
  • Value Permutations: Anand et al. shifted the mapping focus from variables to variable-value (VV) pairs. This allows graph solvers to find "non-count" symmetries, where variables might have different domain sizes or where values have been renamed.
  • Contextual Symmetries: Symmetries are often conditional, holding true only when certain variables take specific values. Grover et al. extended graph-based discovery to contextual symmetries by transforming conditional models into colored graphs, capturing localized structural invariants that global methods miss.

Broader Applications

The utility of discovering symmetries via canonical graph representations extends beyond search and inference into visualization, generative modeling, and machine learning.

In data visualization, traditional layout algorithms often rely on arbitrary binary decomposition trees that obscure a graph's inherent hierarchy. Hong et al. showed that using a unique, canonical structure tree groups identical composition operations at the same level, allowing layout algorithms to mathematically guarantee the visual display of all latent geometric symmetries in series-parallel digraphs.

In generative modeling, Generative Flow Networks (GFlowNets) often struggle to sample symmetric objects (like molecules) accurately because multiple distinct sequences of construction actions can lead to identical final graphs—a challenge known as the "equivalent action problem." Kim et al. resolved this systematic bias by calculating the sizes of the state automorphism groups and scaling the generative rewards accordingly, ensuring mathematically exact and unbiased flow training.

Finally, in deep learning, group-theoretic graph structures can replace hand-engineered heuristics entirely. For complex permutation puzzles like the Rubik's Cube, Chervov et al. demonstrated that training neural networks to estimate distances on the puzzle's underlying Cayley graph creates a generalized solving framework. Because it exploits the fundamental algebraic symmetry of the state space, a single model architecture can generalize across entirely different combinatorial puzzles without modification.

Key Foundational Work

Exploiting Symmetry in Lifted CSPs (1997) — contributed 2 concept elements to this direction.
Drawing Algorithms for Series-Parallel Digraphs in Two and Three Dimensions (1998) — contributed 2 concept elements to this direction.
Symmetry Reductions in Model Checking (1998) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_graph_based_symmetry_discovery_59348c4a,
  title = {graph-based symmetry discovery},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-symmetry-discovery/rdr_59348c4af7bb4043a9c827983d115a46},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_graph_based_symmetry_discovery_59348c4a_v1,
  title = {graph-based symmetry discovery},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-symmetry-discovery/rdr_59348c4af7bb4043a9c827983d115a46/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}

See something wrong? Report a mistake