Graph Isomorphism

Two graphs G = (V_G, E_G) and H = (V_H, E_H) are isomorphic if there exists a bijection f: V_G → V_H such that for any two vertices u, v in V_G, the edge (u, v) is in E_G if and only if the edge (f(u), f(v)) is in E_H. This mapping f is called an isomorphism. The condition preserves not just connections, but also non-connections, meaning the entire adjacency structure is identical under relabeling.

A graph invariant is a property that must be equal for two isomorphic graphs. If any invariant differs, the graphs are non-isomorphic. Key invariants provide fast negative tests:

• Number of vertices and edges
• Degree sequence (sorted list of vertex degrees)
• Cycle structure and girth (length of the shortest cycle)
• Connectivity and chromatic number
• Eigenvalues of the adjacency matrix (the graph spectrum)

Crucially, matching invariants is necessary but not sufficient to prove isomorphism.

The Graph Isomorphism (GI) Problem—determining whether two finite graphs are isomorphic—has a unique and famous computational status. It is in NP, but is not known to be NP-complete, nor is it known to be solvable in polynomial time (P). For decades, it was a primary candidate for an NP-intermediate problem. In 2015, László Babai presented a quasi-polynomial time algorithm, a major theoretical breakthrough, though practical algorithms for general graphs often use heuristics and backtracking.

The Weisfeiler-Lehman (WL) test is a powerful, polynomial-time heuristic for graph isomorphism. It is an iterative color refinement algorithm:

1. Initially, all vertices get the same color.
2. Iteratively, each vertex's color is updated to a hash of its multiset of neighbors' colors.
3. If at any step the histograms of colors for the two graphs differ, they are non-isomorphic.

The 1-WL test is as powerful as certain Graph Neural Networks (GNNs). However, some non-isomorphic graphs (e.g., certain strongly regular graphs) are WL-indistinguishable, showing its limits.

In agentic observability, graph isomorphism helps identify structurally identical interaction patterns across different system instances or time windows. For example:

• Detecting that the communication topology between agents in a staging environment is isomorphic to production, validating a test.
• Recognizing that an anomalous event triggered the same cascade pattern (isomorphic subgraph) as a past incident.
• Canonical labeling (computing a unique string representation for an isomorphism class) allows for efficient hashing and lookup of recurring interaction motifs in telemetry data.

• Graph Automorphism: An isomorphism from a graph to itself. The set of all automorphisms forms the automorphism group, which captures the graph's symmetries. A highly symmetric graph has many automorphisms.
• Canonical Form/Certificate: A unique representation (e.g., a string or relabeled adjacency matrix) for an entire isomorphism class. Computing a canonical form is as hard as solving GI, but it allows for O(1) isomorphism checks via string comparison after it is computed for both graphs.
• Subgraph Isomorphism: A harder (NP-complete) problem of finding if one graph is isomorphic to a subgraph of another.

A graph automorphism is a special case of isomorphism where a graph is mapped onto itself. Formally, it is an isomorphism from a graph to itself, representing a symmetry of the graph structure. In agent systems, automorphisms reveal inherent symmetries where agents or sub-groups are structurally interchangeable, which can inform load balancing and redundancy planning.

• Key Property: The set of all automorphisms of a graph forms its automorphism group, a mathematical group under composition.
• Application: Detecting automorphisms can simplify the analysis of large interaction graphs by identifying equivalent nodes, reducing the effective state space for algorithms.

Subgraph isomorphism is the decision problem of determining whether a given graph contains a subgraph that is isomorphic to another (smaller) graph. This is a more general and computationally harder problem than graph isomorphism. It is crucial for pattern matching within larger agent networks.

• NP-Completeness: The subgraph isomorphism problem is NP-complete, meaning no known polynomial-time algorithm solves all instances.
• Use Case: Identifying specific, pre-defined interaction patterns (e.g., a particular negotiation sequence or error cascade) within a sprawling multi-agent system's interaction history.

Graph canonical labeling (or canonical form) is a computational technique to assign a unique, deterministic string or numerical representation (a canonical label) to a graph such that any two isomorphic graphs receive the identical label. This transforms the isomorphism problem into a string comparison problem.

• Core Mechanism: Algorithms like nauty (by Brendan McKay) generate a canonical form by finding a canonical ordering of the graph's vertices.
• Practical Benefit: Enables efficient graph deduplication and indexing in databases storing millions of agent interaction traces, as isomorphism checks become O(1) hash comparisons.

The Weisfeiler-Lehman (WL) test is a classical, efficient heuristic algorithm for graph isomorphism. It operates through iterative color refinement, where nodes are colored based on the multiset of their neighbors' colors. If, after refinement, the multisets of colors differ between two graphs, they are non-isomorphic.

• Limitation: The WL test is a necessary but not sufficient condition for isomorphism; some non-isomorphic graphs (e.g., certain strongly regular graphs) cannot be distinguished by it.
• Modern Link: The WL test provides the theoretical upper bound on the expressive power of many Graph Neural Networks (GNNs); GNNs are at most as powerful as the WL test in distinguishing graph structures.

GI-completeness refers to a class of computational problems that are polynomial-time equivalent to the Graph Isomorphism (GI) problem. If a problem is GI-complete, solving it efficiently would imply an efficient solution for all problems in GI, and vice-versa. This places GI in its own potential complexity class, possibly between P and NP-complete.

• Example Problems: Determining isomorphism for directed graphs, bipartite graphs, and graphs of bounded degree are all GI-complete.
• Significance: The unique status of GI means that while it is not known to be in P, it is also not believed to be NP-complete, making it a central problem in theoretical computer science.

A graph invariant is a property of a graph that is preserved under isomorphism. If two graphs are isomorphic, they must share the same value for every graph invariant. Invariants are used as fast, necessary filters to rule out isomorphism.

• Common Invariants:
  • Degree Sequence: The sorted list of node degrees.
  • Spectrum: The eigenvalues of the graph's adjacency or Laplacian matrix.
  • Number of cycles of a specific length.
• Application in Observability: Computing invariants for agent interaction graphs provides a fast checksum for detecting significant structural changes or for grouping similar behavioral sessions.