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.

Version: v2 · 2026-09-06 · History
Domain-specific #: 2294
Origin domain: mathematics
Subdomain: graph products and common-subgraph algorithms
Aliases: Modular graph product

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. ^[1]

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.

Its operative boundary is not supplied by the name alone. Preserve this identity: A graph product on the Cartesian product of two vertex sets whose adjacency encodes agreement of adjacency or nonadjacency in the factor graphs. Validity boundary: Vertices and edges must follow the modular-product adjacency rule; other Cartesian-set graph products are distinct. The entry therefore captures a reusable specialist role structure rather than a topic label, a single historical instance, or a loose analogy.

Structural Signature¶

Sig role-phrases:

the factor graphs — the two simple graphs being compared
the vertex-pair set — candidate correspondences between factor vertices
the injectivity condition — compatible pair-vertices do not reuse a factor vertex
the adjacency-agreement rule — edges in one factor correspond to edges in the other
the nonadjacency-agreement rule — nonedges are also preserved for induced correspondence
the product graph — the graph whose edges encode pairwise compatibility
the clique — a set of mutually compatible correspondences
the common induced subgraph — the factor substructure recovered from a clique

Recognition test. A case qualifies only when the analyst can map the declared the factor graphs, the vertex-pair set, the injectivity condition, the adjacency-agreement rule, the nonadjacency-agreement rule and preserve the specialist validity conditions. Shared vocabulary, a similar output, or a generic instance of one parent relation is insufficient.

What It Is Not¶

Not the Cartesian graph product. Its adjacency rule changes one coordinate at a time rather than comparing correspondence consistency.
Not the tensor/direct graph product. Simultaneous factor adjacency alone does not preserve nonedges.
Not a graph module. Modules are vertex sets with identical external neighborhoods.
Not all possible vertex mappings. Product adjacency filters mappings for injective adjacency and nonadjacency agreement.
Not ordinary maximum common subgraph in every convention. The standard clique correspondence is for induced common subgraphs unless the product rule is modified.

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. If the case retains only the portable skeleton described below, it should be named through a parent abstraction rather than as Modular product of graphs.

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.

These moves separate definition, derivation, measurement, and interpretation. A formal consequence does not by itself prove that an observed case instantiates the abstraction, while an observed resemblance does not relax the formal or institutional recognition conditions.

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. The safe move beyond the home habitat is to carry the applicable parent relation and leave the specialist name behind unless every defining role remains literal.

Examples¶

Canonical: a clique encoding an induced match¶

Select three pair-vertices (u1,v1), (u2,v2), and (u3,v3). If no factor coordinate repeats and every pair of ui vertices is adjacent exactly when its paired vi vertices is adjacent, the three product vertices form a clique. The induced subgraphs on the two selected triples are isomorphic. ^[1]

Mapped back: the factor graphs; the vertex-pair set; the injectivity condition; the adjacency-agreement rule; the nonadjacency-agreement rule; the clique.

Applied / In Practice: maximum-clique reduction¶

An exact common-subgraph solver builds a labeled modular product, omitting vertex pairs with incompatible labels. It runs a maximum-clique algorithm, then translates the returned clique into the factor-vertex mapping. Solver certificates and bounds concern the product, but the reported scientific result is the recovered common induced structure. ^[2]

Mapped back: the product graph; the clique; the common induced subgraph; the vertex-pair set.

Structural Tensions¶

T1: Reduction clarity vs product size. The transformation simplifies constraints while creating a graph with a product-sized vertex set. Diagnostic: Does the reduction improve the practical search instance?

T2: Induced fidelity vs permissive matching. Preserving nonedges yields induced matches but rejects valid non-induced subgraphs. Diagnostic: Which common-subgraph definition is intended?

T3: Pairwise compatibility vs global optimum. Edges encode local consistency while clique search remains combinatorially hard. Diagnostic: What exact bound or heuristic supports optimality?

T4: Label pruning vs false exclusion. Labels shrink the product but erroneous incompatibility rules remove valid matches. Diagnostic: Are label constraints part of the problem definition?

T5: Symmetry vs duplicate search. Graph automorphisms create many equivalent product cliques. Diagnostic: How are symmetric correspondences controlled?

T6: Domain autonomy vs prime reduction. Cartesian product and graph coloring omit the edge/nonedge agreement that makes cliques represent isomorphisms. Diagnostic: Would an arbitrary graph product retain the common-induced-subgraph theorem?

Structural–Framed Character¶

The five-criterion aggregate is 0.15 (structural). The judgment is criterion-specific:

Vocabulary travels — low (0.25). The complete vocabulary remains tied to the typed roles in the Structural Signature.
Evaluative weight — low (0.00). Application carries the stated degree of normative or interpretive judgment beyond structural recognition.
Institutional origin — low (0.25). The abstraction depends to this degree on a scholarly, technical, legal, or social convention.
Human-practice bound — low (0.00). Recognition depends to this degree on organized practice, language, measurement, or institutional action.
Import versus recognize — low (0.25). Beyond its home habitat, use of the full name increasingly becomes analogy rather than literal recognition.

The portable skeleton is candidate pairings become nodes and pairwise compatibility becomes adjacency, so globally consistent partial correspondences become cliques. The named abstraction remains structural because that skeleton alone does not supply its specialist objects, constraints, or tests.

Structural Core vs. Domain Accent¶

Structural core: Candidate pairings become nodes and pairwise compatibility becomes adjacency, so globally consistent partial correspondences become cliques.

Domain accent: Simple factor graphs, vertex-pair products, injective mappings, adjacency and nonadjacency preservation, maximum clique, and induced subgraph isomorphism.

Why it does not clear the prime bar: Compatibility graphs travel; the modular product is fixed by graph-theoretic edge/nonedge agreement and its clique correspondence. Generalization therefore routes through parent abstractions; preserving the specialist name requires the full accent.

Cartesian Product (prime:cartesian_product). The product begins from ordered pairs in the Cartesian product of vertex sets.
Graph Coloring (prime:graph_coloring). Both are graph encodings of consistency constraints, though coloring is related rather than definitional.

These are prose placement proposals only. They create no dag_edges; endpoint, redundancy, and cycle checks are recorded separately in the bundle's placement memo.

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

Show alternative path (1)

Neighborhood in Abstraction Space¶

Modular product of graphs sits in a sparse region of the domain-specific corpus (65^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Cartesian product of graphs. adjacency changes one coordinate along a factor edge. Tell: Does adjacency encode correspondence agreement or coordinate movement?
Tensor product of graphs. vertices are adjacent when both factor coordinates are adjacent. Tell: Are nonedges also required to agree?
Strong product. a union of Cartesian and tensor adjacency rules. Tell: Is the product designed for movement or for graph matching?
Association graph. a broader compatibility-graph construction for matching. Tell: Is the exact modular edge/nonedge rule used?
Graph module. a homogeneous vertex set inside one graph. Tell: Is this a product construction or a modular decomposition object?

References¶

[1] Xiuzhen Huang, Jing Lai, and Steven F. Jennings, “Maximum common subgraph: some upper bound and lower bound results”, BMC Bioinformatics 7(Suppl 4) (2006): S6. registry ↩a ↩b

[2] Ciaran McCreesh, Patrick Prosser, and James Trimble, “A Partitioning Algorithm for Maximum Common Subgraph Problems”, IJCAI 2017, 712–719. registry ↩