Canonical Adjacency Encoding¶
Encoding scheme — instantiates Network Motif and Pattern Discovery
Rewrites each subgraph into a relabeling-invariant key so structurally identical motifs collapse to one canonical form that can be indexed and matched.
The same three-node pattern can be drawn a dozen ways — relabel the vertices, reorder the rows of its adjacency matrix, and the picture changes while the structure does not. Canonical Adjacency Encoding removes that ambiguity by computing, for any subgraph, a single deterministic key that is invariant to how the nodes happen to be numbered. Two subgraphs receive the same key if and only if they are structurally the same pattern (isomorphic under the chosen grammar); they receive different keys the moment direction, sign, or label distinguishes them. Its whole reason to exist is identity: it is the scheme that lets everything downstream say "these are the same motif" without arguing about vertex names. It does not go looking for subgraphs and it does not count them — it is the rulebook for what a subgraph's name is once you already hold one.
Example¶
A cheminformatics team is de-duplicating a library of small molecular fragments pulled from millions of compounds. Each fragment is a little graph — atoms as nodes, bonds as edges, with element and bond-order labels. The raw extraction hands them the "same" carboxyl fragment written thousands of ways, because the atom-numbering came out differently every time. Canonical Adjacency Encoding fixes this: it applies a canonical atom ranking so that every drawing of that fragment collapses to one identical string, the way a canonical SMILES does. The team runs each fragment through the encoder; isomorphic fragments now hash to the same key and stack into one library entry, while a fragment that differs only by a double bond instead of a single bond lands under a different key — because bond order is part of the grammar the encoder was told to honor.
The payoff is prosaic but decisive. A frequency tally that previously reported forty near-duplicate "motifs" now reports one, with a correct count. And when a new compound arrives, matching its fragments against the library is a key lookup rather than a graph-isomorphism search per entry. The encoder produced no chemistry insight of its own; it made every later step trustworthy by giving each shape exactly one name.
How it works¶
The scheme's distinctive move is choosing a canonical ordering of a subgraph's vertices and then serializing the adjacency structure under that order:
- Refine by invariants. Assign each node an initial signature from properties that cannot depend on labeling — degree, in/out-degree, edge labels, neighbor signatures — then iteratively refine, in the spirit of color refinement, until the ordering is as discriminating as the grammar allows.
- Break ties deterministically. Where the refinement leaves symmetric nodes indistinguishable, branch and pick the lexicographically smallest resulting string, so genuinely symmetric graphs still land on one representative.
- Serialize to a key. Emit the ordered adjacency (matrix row-concatenation, edge list, or a certificate string) plus the label vocabulary; that string is the canonical key.
- Index by key. Store keys in a hash-addressable table so "have we seen this shape?" is a constant-time lookup and each shape owns one library slot.
The grammar it is handed decides what counts as "the same": drop direction and two opposite arrows merge; keep sign and a promoting edge stays distinct from an inhibiting one.
Tuning parameters¶
- Label granularity — how many node/edge attributes enter the key. Richer labels separate semantically distinct shapes but shrink each key's population toward singletons.
- Directionality and sign — whether arrows and signs are canonicalized or flattened. Flattening finds broader structural families; keeping them finds functional ones.
- Exactness vs. speed — a guaranteed-canonical certificate versus a fast near-canonical hash (a Weisfeiler–Lehman–style color hash) that is almost always right and occasionally collides.
- Automorphism handling — whether the key also records the subgraph's symmetry group, which downstream counting needs to avoid over- or under-counting symmetric instances.
- Key form — human-readable certificate versus compact binary hash; readability aids audit, compactness aids scale.
When it helps, and when it misleads¶
Its strength is that it makes every later claim about "the same motif" mean one precise thing. Enumeration, counting, and cross-study comparison all rest on a stable notion of identity, and this is the mechanism that supplies it — cheaply and deterministically. Where a full graph-isomorphism test between every pair would be intractable, a canonical key turns equivalence into string equality.[n1]
It misleads in two ways. First, a fast hash trades certainty for speed: a color-refinement hash can assign two genuinely different graphs the same key on adversarial inputs, so a hashed census can silently merge distinct motifs unless collisions are checked. Second, and more insidious, the key is only as meaningful as the grammar it encodes — flatten away edge direction and you will confidently declare a feed-forward loop and a feedback loop "the same motif," a semantic flattening no amount of canonicalization repairs. The guarding discipline is to fix the grammar to the domain's real distinctions before encoding, and, when using a fast hash, to confirm suspected matches with an exact check on a sample.
How it implements the components¶
Canonical Adjacency Encoding fills the identity layer of the archetype and nothing more:
isomorphism_and_canonical_labeling— its core act: computing a labeling-invariant canonical form so structurally equivalent subgraphs are provably grouped and non-equivalent ones kept apart.motif_library_or_index— the canonical keys become the addressable entries of the motif library, giving each shape exactly one slot and making recall a lookup.
It does not search the graph for instances (subgraph_enumeration_process) or tally how often each appears (recurrence_measurement) — that is Subgraph Census; and it does not configure or run the automated search itself (motif_scope_and_grammar) — that is Graph Motif Mining Algorithm, the sibling nearest to it, which consumes this encoding as its notion of "same shape."
Related¶
- Instantiates: Network Motif and Pattern Discovery — supplies the canonical-identity substrate every other step relies on.
- Sibling mechanisms: Subgraph Census · Graph Motif Mining Algorithm · Random Graph Null Ensemble · Degree-Preserving Edge Swap · Motif Enrichment Table · Motif Role Hypothesis Card · Network Perturbation or Ablation Test · Domain Expert Motif Review · Temporal Sliding-Window Motif Scan
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: Rewrites each subgraph into a relabeling-invariant key so structurally identical motifs collapse to one canonical form that can be indexed and matched, making its operative form a computation, comparison, model, or analytic representation used to infer, estimate, or choose.
Independent corroboration: The frozen evidence defines Canonical Adjacency Encoding as 'Rewrites each subgraph into a relabeling-invariant key so structurally identical motifs collapse to one canonical form that can be indexed and matched', so its operative form is Analysis, Modeling & Optimization.
Review outcome: Independent reviewer agreement; high confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Single lineage
Present-day reach: Specialized
Rationale: Graph algorithms developed canonical labeling and adjacency encodings so isomorphic subgraphs receive the same invariant key.
Related originating lineages:
- Mathematics — Graph theory defines isomorphism, automorphisms, and the equivalence relation the encoding must respect.
Review resolution: Computer science is primary through graph isomorphism algorithms, canonical labeling, and deterministic serialization. Mathematics supplies graph-theoretic foundations, but the executable encoding scheme is a specialized single lineage in algorithmic graph processing.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
[n1] Deciding whether two graphs are isomorphic has no known efficient general algorithm, but practical canonical-labeling tools — Brendan McKay's nauty being the best-known — compute a canonical form fast for the small graphs motif work uses, which is exactly why reducing equivalence to key comparison is worthwhile. ↩