Hypergraph Category

definition example theorem proof

A hypergraph category is a Symmetric Monoidal Category $(\mathcal{C},I,\otimes )$ in which every object $X$ carries a Frobenius structure $(X,{\mu }_X,{\eta }_X,{\delta }_X,{\epsilon }_X)$, coherently with the monoidal product: the Frobenius maps of $X\otimes Y$ are built from those of $X$ and $Y$ (with a swap in the middle for ${\mu }_{X\otimes Y}$ and ${\delta }_{X\otimes Y}$), and ${\eta }_I={\mathrm{id}}_I={\epsilon }_I$. A hypergraph prop is a hypergraph category that is a Prop. Its wiring diagrams are network diagrams: labelled boxes, wires that may bend (as in compact closed categories), and wires that may split, join, terminate and initialize — the spiders. Spiders of the same “species” (object) fuse when they share a leg; spiders of different species cannot.

Sources: 7 Sketches §6.1, §6.3 (Definition 6.60, Examples 6.61, 6.64, 6.65, Proposition 6.66, Exercises 6.59, 6.62, 6.63, 6.67), §6.4 (Theorem 6.77), §6.5 (Proposition 6.101), §6.6; [CW87] (“well-supported compact closed category”), [Fon15; Fon16; Fon18; FS18a; FS18b]; Kittenlab Lecture 15 (cospans, undirected wiring diagrams); Catlab ThHypergraphCategory, @relation, oapply; Fong & Spivak, Hypergraph Categories arXiv:1806.08304 (notes) Definitions 2.5, 2.12, Proposition 3.1, Theorem 3.14; Stein & Samuelson arXiv:2204.14024 (notes) Theorem 14.

Examples

• ${\mathbf{Cospan}}_{\mathcal{C}}$ for any $\mathcal{C}$ with finite colimits (Example 6.61) — the prototype; ${\mathbf{Cospan}}_{\mathbf{FinSet}}$ is equivalent to the hypergraph prop presented by the Frobenius axioms (Theorem 6.58). Its wiring diagrams are undirected wiring diagrams.
• $\mathbf{Corel}$ (Example 6.64), ${\mathbf{LinRel}}_R$ in two ways (Example 6.65), $\mathbf{Rel}$.
• Decorated cospans ${\mathbf{Cospan}}_F$ (Theorem 6.77) — e.g. open electric circuits, open Petri nets, Markov processes; structured cospans and open graphs.
• Every hypergraph prop is a $\mathbf{Cospan}$-algebra and conversely (Proposition 6.101).

Hypergraph categories are self-dual compact closed (Proposition 6.66)

Define the cup ${\eta }_X;{\delta }_X:I\to X\otimes X$ and the cap ${\mu }_X;{\epsilon }_X:X\otimes X\to I$. The snake equation follows: (id ⊗ cup) ; (cap ⊗ id) $=$ (id ⊗ (η ; δ)) ; ((μ ; ε) ⊗ id) $=$ by the Frobenius law $(\mathrm{id}\otimes \eta );\mu ;\delta ;(\epsilon \otimes \mathrm{id})$ $=$ by unitality and counitality ${\mathrm{id}}_X$ (7S Exercise 6.67 fills in the middle step). Hence $X^{\ast }=X$ and wires may be bent freely — the “well-supported compact closed” of Carboni–Walters. Compare Theorem 5.87.

Why hypergraph categories

“Network-type interconnection can be described using a hypergraph category” (§6.1): the domain/codomain split of a morphism is an artifact (circuits have one boundary), but the Frobenius structure lets one move ports freely between the two sides; the Operad $\mathbf{Cospan}$ removes the artifact entirely (§6.5.1). 7S Exercise 6.59 infers wire labels in a hypergraph-category diagram.

Factor graphs, and why probabilistic wiring needs unnormalised morphisms

A factor graph is a network diagram in a hypergraph category: factors are boxes, and a variable node of degree $d$ is a $d$-legged spider — “a variable is a wire with no content of its own” is the spider theorem (Frobenius Monoid). Two consequences for probabilistic models:

	Markov Category	hypergraph category
copy $\delta$	yes	yes
delete $\epsilon$	yes, natural (everything normalised)	yes, not natural
merge $\mu$	no	yes
morphisms are	normalised kernels	relations, unnormalised densities
models	directed generative models	acausal equations, circuits, factor graphs

Merging two probability wires (“these are equal”) multiplies densities and produces an unnormalised result, so normalisation obstructs the Frobenius multiplication. The standard fix is to enlarge the category with improper objects: Gaussian Relations (Gaussians plus linear relations, with uninformative priors as the unit of merging) form a hypergraph category containing Gaussian probability. Every hypergraph category is self-dual compact closed (Fong & Spivak, Proposition 3.1), and ${\mathbf{Cospan}}_{\Lambda }$ is the free hypergraph category on a set of labels (Theorem 3.14) — which is why decorated cospans are the standard way to build such models. See also Partial Markov Category for the other route to conditioning.

Lenticulum.jl identifies its message pooling combine with the Frobenius multiplication and its uninformative Gaussian belief with the unit; see Acausal Composition is a Hypergraph Category.

JuliaHaskell

Docs: Relational programs / UWDs · Theories & presentations — Kittenlab Lecture 15

using Catlab, Catlab.WiringDiagrams, Catlab.Programs
# undirected wiring diagrams are the string diagrams of hypergraph categories; @relation builds them
uwd = @relation (x, z) begin
  R(x, y)            # a box with ports x, y
  S(y, z)            # a box with ports y, z: the junction y is a spider joining two legs
end
# `oapply` evaluates a hypergraph-category algebra (e.g. finite relations, Petri nets, circuits) on a UWD
# Catlab's theory ThHypergraphCategory has mcopy (δ), delete (ε), mmerge (μ), create (η):
@present H(FreeHypergraphCategory) begin X::Ob end
X = H[:X]
mmerge(X) ⋅ mcopy(X) ⋅ (mcopy(X) ⊗ id(X))      # the spider s_{2,3}

-- a hypergraph category as an SMC with a coherent Frobenius structure on every object (schematic)
class SymMonoidal cat => Hypergraph cat where
  merge  :: cat (x, x) x
  unitH  :: cat () x
  split  :: cat x (x, x)
  counitH :: cat x ()
-- cup = unitH >>> split ; cap = merge >>> counitH  (Proposition 6.66)