Modular product of graphs¶
A graph product on the Cartesian product of two vertex sets whose adjacency encodes agreement of adjacency or nonadjacency in the factor graphs.
Core Idea¶
Modular product of graphs is a graph product on the Cartesian product of two vertex sets whose adjacency encodes agreement of adjacency or nonadjacency in the factor graphs.
The vertices of the modular product are ordered pairs drawn from the two factor-graph vertex sets, typically with distinct coordinates. Two pair-vertices are adjacent when the correspondence preserves either an edge in both factors or a nonedge in both. Consequently, a clique represents a mutually consistent partial isomorphism, and a maximum clique encodes a maximum common induced subgraph.
Scope of Application¶
The abstraction recurs literally within graph comparison and algorithms that reduce mutually consistent induced vertex correspondence to clique finding. The following habitats preserve the same recognition machinery; they are not invitations to extend the name metaphorically.
- Maximum common induced subgraph. maximum cliques encode largest induced correspondences.
- Subgraph isomorphism. clique constraints represent compatible partial mappings.
- Graph similarity. clique size or structure supplies correspondence-based measures.
- Cheminformatics. labeled variants compare molecular graphs.
- Bioinformatics. common interaction or structural patterns can be formulated as graph matching.
- Exact algorithms. clique solvers exploit product structure and labels.
Clarity¶
The product's definition must state whether equal coordinates are excluded and whether nonadjacency agreement is required. Those choices determine whether cliques encode injective induced correspondences, non-induced correspondences, or a different matching problem.
A practical identification audit begins with the typed roles rather than the title: establish the factor graphs, verify the vertex-pair set, then test the remaining conditions and exclusions.
Manages Complexity¶
The construction converts a global mapping-consistency problem into a standard graph problem. Pairwise compatibility is materialized as product edges, allowing mature maximum-clique algorithms to search for a globally consistent correspondence.
The compression remains accountable because each simplification has a named failure condition. Disagreement can be localized to a missing role, an invalid assumption, an ambiguous measurement, or a neighboring abstraction instead of being hidden inside an unanalyzed label.
Abstract Reasoning¶
R1. Specify the factor-graph conventions, labels, and induced or non-induced target. R2. Create only admissible vertex pairs. R3. Add a product edge exactly when injectivity and factor relations agree. R4. Prove both directions of the clique–correspondence mapping. R5. Interpret clique optimality in the original graph problem rather than only in product size.
Knowledge Transfer¶
The construction transfers literally across graph-matching applications using the same product rule. Cartesian product and constraint satisfaction are broader parents; multiplying two datasets or forming arbitrary pair features is not the modular product of graphs.
The transfer boundary is explicit: DOMAIN-SPECIFIC PASS / PRIME FAIL: The construction recurs across graph pairs and is used to reduce common-subgraph and isomorphism questions to clique structure. Literal recognition retains the specialist vocabulary and validity conditions of graph theory; outside that setting only broader parent operations transfer.
Relationships to Other Abstractions¶
Current abstraction Modular product of graphs Domain-specific
Parents (2) — more general patterns this builds on
-
Modular product of graphs presupposes Cartesian Product Prime
Cartesian Product (
prime:cartesian_product). -
Modular product of graphs presupposes Compatibility Prime
The accepted reference-grade review places Modular product of graphs under Compatibility because the child instantiates or depends on the parent's broader structure while retaining its own constitutive identity.
Hierarchy paths (2) — routes to 2 parentless roots
- Modular product of graphs → Cartesian Product → Set and Membership
- Modular product of graphs → Compatibility
Neighborhood in Abstraction Space¶
Modular product of graphs sits in a sparse region of the domain-specific corpus (65th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (1565 abstractions)
Nearest neighbors
- Graph Sphericity — 0.87
- Matching — 0.87
- Hadwiger number — 0.86
- Uniform space — 0.85
- Probabilistic Graphical Model — 0.84
Computed from structural-signature embeddings · 2026-09-08