Full Bibliography

A general theory of data that changes over time, built as sheaves on posets of time intervals – categories of narratives. It defines both temporal objects and their morphisms, distinguishes cumulative from persistent readings and moves between them, lifts static notions to temporal ones systematically, works for any category with limits and colimits, and connects to dynamical systems. Time-varying graphs have been reinvented repeatedly with incompatible definitions. This is the lab’s answer to what all of them are instances of, and the sheaf-theoretic machinery is the same as the rest of the project.

Read it for The five desiderata in the introduction, then the definition of a narrative. The comparisons to existing temporal graph formalisms can be sampled.

A system of partial differential equations can be written as a diagram, the diagrams can be composed with an operad of wiring diagrams, and the result compiles to a solver by categorical data migration, graph traversal and the discrete exterior calculus. Benchmarked against SU2, the generated solvers agree with an established tool. This is the Decapodes project’s own paper: it is where the representation, the composition operation and the compiler are stated together, and where the claim that generated code is competitive is actually tested.

Read it for The compilation pipeline and the SU2 comparison. The introduction to the discrete exterior calculus is better read from the CombinatorialSpaces documentation.

Read first A diagrammatic view of differential equations in physics

Regulatory networks as signed graphs, with signed functors describing when one network occurs inside another – which is what a network motif is. From there, functors relate regulatory networks to reaction networks, making precise when a reaction network is a mechanism for a regulatory one, and to Lotka-Volterra dynamics, for open systems as well as closed ones. It is the project’s biochemistry arm, and its clearest example of the same pattern used three ways: motifs, mechanisms and dynamics all become functors out of one category of networks.

Read it for The motif-as-functor definition, then the Lotka-Volterra functor. The open systems extension is the technical heart.

Physicists have long drawn systems of differential equations as diagrams; this puts that practice on a categorical footing, with diagrams as the syntax and morphisms of diagrams – the less appreciated half – as the way one system is built from another. Worked examples run through electromagnetism, transport, and fluid mechanics. It is the mathematics Decapodes implements. Read it if you want to know why a Decapode is a legitimate presentation of a physical system rather than a picture of one.

Read it for The examples, first. The general theory reads much more easily once you have seen a diagram for a physical law you already know.

A compositional framework for epidemiological modeling in which the structure of a model – its submodels and how they interact – is explicit and algebraic rather than implicit in code. Stratification, composition, analysis and calibration all become operations on that structure, so a local change to a component no longer means a global edit to a codebase. It is the modeling project’s flagship paper, and the clearest statement of the whole lab’s motivation: the gap between how a scientist thinks about a model and the program that implements it is the thing being closed.

Read it for The stratification example. It is the operation that makes the case on its own.

Target tracking, which is not a cooperative problem, is also a harmonic extension on a coordination sheaf. Because a sheaf can carry a different stalk over each agent, the formulation takes agents whose state spaces have different dimensions, and it survives nonlinear dynamics and disturbances. The controller built from the sheaf Laplacian is decentralized and comes with a Lyapunov proof that the tracking error converges. It is the paper that took the coordination sheaf out of consensus and formation problems, where every agent wants the same thing, and into a problem where the agents are chasing something that does not cooperate. It is also the lab’s closest joint work with the Nonlinear Controls and Robotics group.

Read it for The construction of the tracking sheaf, and the stability argument in section 4. The simulation study is a check, not the contribution.

Read first Distributed Multi-agent Coordination over Cellular Sheaves

Sheaf diffusion still converges when the agents are not in step. Under bounded communication and computation delays, nonlinear sheaf diffusion reaches a minimizer of the coordination sheaf’s Dirichlet energy at a linear rate set by the delay bound, from any starting configuration. Every earlier result in this line assumes agents update synchronously, which a real fleet does not. This is the paper that says what the framework still guarantees once that assumption is dropped.

Read it for The delay model and the convergence rate. If you only need the result, the statement of the main theorem is enough.

Read first Distributed Multi-agent Coordination over Cellular Sheaves

Control barrier functions built from Whitney forms, so that a safety constraint is a discrete differential form living on a mesh rather than a smooth function on the state space, with the discrete exterior calculus supplying the operators that enforce it. It is where the coordination project and Decapodes meet: the safety machinery of control theory posed in the same discrete exterior calculus the simulation work is built on, so a constraint and the physics it constrains are written over one mesh.

Read it for The construction of the barrier function from Whitney forms.

Generalized gradient descent, taken with respect to a cartesian reverse derivative category, is a hypergraph functor from a category of open objective functions to a category of open dynamical systems. Composite problems in the domain therefore induce distributed algorithms in the codomain, and parameter-sharing multitask models are one example of a problem the framework covers. It is the sharpest form of the claim the optimization project keeps making: the algorithm is not designed to match the problem’s structure, it is the image of that structure under a functor.

Read it for The functor and its proof. The multitask learning example shows what the generality buys you.

Read first A Compositional Framework for First-Order Optimization

Coordination of a multi-agent system can be posed as a cellular sheaf over the communication graph, making the coordinated state the harmonic extension of the sheaf Laplacian rather than the output of a purpose-built controller: the coordinated state solves $H q^\star = -B p$, where $H$ is the agent block of the Laplacian and $p$ the current targets. It is the problem statement the rest of our coordination work refines: every later paper either solves that linear system faster or relaxes an assumption it makes.

Read it for The sheaf construction and the Laplacian. The experiments can wait.

Model predictive control problems compose. The paper builds a monoidal category whose objects are Euclidean spaces and whose morphisms are constrained convex optimization problems, then shows that the multistage structure of an MPC problem is sequential composition in that category, and constraints tying stages together are parallel composition. The syntax is diagrammatic, and it maps onto existing Julia mathematical programming libraries. It is the project’s founding paper: the first place the lab treated a control problem as something assembled from parts with a syntax, rather than as a monolith handed to a solver.

Read it for The construction of the category and the worked MPC diagram. The software section is short and worth the detour.

A way to ask how badly a functor fails to be compositional, and what can be done about it. The paper introduces lavish presheaves – presheaves satisfying the existence half of the sheaf condition but not uniqueness – as the setting in which such failures can be measured rather than merely observed. Compositionality is usually presented as a property a construction either has or lacks. The sheaves project needs it to be a quantity, because the interesting structures are the ones that almost have it.

Read it for The definition of a lavish presheaf and the two squares of the title.

Designing an optimal controller for a whole system and composing optimal controllers designed for its parts are not the same thing. Using resource sharing machines, the paper gives sufficient conditions under which the LQR for a composite system does equal the composite of the subsystems’ LQRs, and reduces checking them to the controllability and observability of one linear time-invariant system. Compositional design is only useful if you know when it is exact. This is the negative-result-and-its-boundary paper the rest of the optimization work leans on.

Read it for The counterexample and the sufficient conditions. Skim the LQR background if you have seen it before.

Deterministic dynamical systems, discrete and continuous, compose hierarchically: the paper reformulates existing operads of wiring diagrams and introduces new ones in the language of C-sets, establishes dynamical systems as algebras of those operads, and shows Euler’s method is functorial for undirected systems as well as directed ones. It is where the lab’s dynamical systems machinery is defined, and the functoriality of Euler’s method is the reason a composite system’s simulator can be assembled from its parts’ simulators.

Read it for The operads and the functoriality result. The AlgebraicDynamics code follows the paper closely enough to read alongside it.

A space of models is represented as a diagram over a category of models, and limits and colimits of those diagrams build larger model spaces out of smaller ones. The paper implements the computer algebra of finitely presented categories and diagram categories needed to do this, with strategies for picking a model out of the space, demonstrated on mass-action kinetic models fitted to data. Composition builds one model; this is the lab’s answer to searching the space of models you could have built, which is what a modeler actually does.

Read it for The model space construction and the epidemiology case study.

Model augmentation, combination and comparison are treated as metamodeling tasks, and static and dynamic program analysis is used to extract enough semantics from executable scientific models to perform them – metamodeling as metaprogramming, with a categorical account of what the tasks are. It is where the lab first tried to recover a model’s meaning from its code. The later work inverts the problem, specifying structure up front instead, and this paper is the reason why.

Read it for The definition of the metamodeling tasks, and the case study.

An early statement of the programme: applied category theory supplies reusable software components for scientific computing, with Catlab.jl as the categorical infrastructure and SemanticModels.jl as the modeling layer on top, composing systems as cospan algebras. It is the origin point for Catlab and, through it, for most of what the lab has built since. Read it as history rather than as current practice.

Read it for The framing in the introduction. The software described has been superseded.

The software half of the SemanticModels work: a Julia package that automates model augmentation and creation by metamodeling and metaprogramming. The argument for Julia is the substance – its type system, its reachable syntax tree, and the embedded domain-specific languages that multiple dispatch makes possible let a model be manipulated at run time and still compile to efficient code. It is the implementation the rest of the SemanticModels papers describe, and the lab’s first attempt to treat model manipulation as a programming-language problem rather than a modeling one.

Read it for The argument for Julia as the host language. The package itself has been superseded by AlgebraicPetri.jl.

Read first A Compositional Framework for Scientific Model Augmentation

SemanticModels.jl builds a knowledge graph linking elements of scientific code – variables, values, functions, expressions – to elements of scientific understanding, and reasons over it to augment, synthesize and validate epidemiological models. The earliest paper in the project, and the clearest statement of the extraction approach the lab later moved away from.

Read it for The knowledge graph construction. Historical interest unless you work on model extraction.

A problem becomes a presheaf assigning certificates to instances, and Cech cohomology of that presheaf measures exactly how local solutions fail to patch into global ones. Applied to Vertex Cover, Cycle Cover and Odd Cycle Transversal, the obstructions show up as concrete phenomena – hidden cycles, local solutions that inflate – and classical results such as Koenig’s theorem are recovered in cohomological terms. The compositional algorithms only work when local answers glue. This is the project’s account of what is happening when they do not, which is the more common case.

Read it for The cohomological reading of Koenig’s theorem, which is where the machinery first pays for itself.

Read first Compositional Algorithms on Compositional Data: Deciding Sheaves on Presheaves

Treewidth is monotone under subgraphs and contractions; the paper shows that contractions are, up to isomorphism, the only surjective graph homomorphisms that preserve tree decompositions and the shape of the decomposition tree. It proves this by introducing the lasso, which is what a contraction becomes in an arbitrary category with pushouts of monomorphisms, so that the same question can be asked of directed multigraphs, hypergraphs, Petri nets, databases, simplicial sets and the rest. Decompositions are the lab’s tool for turning a hard global problem into local ones, and this settles which maps between structures a decomposition can be carried along.

Read it for The characterization theorem, then the lasso, which the authors flag as of independent interest and which is what carries the result beyond graphs.

An algebraic account of optimization problems composed on a hypergraph: operads for syntax, operad algebras for semantics, algebra morphisms for the transformations that preserve structure. Classes of optimization problems form operad algebras, and first-order methods – gradient descent, Uzawa’s algorithm, their subgradient variants – are algebra morphisms into algebras of dynamical systems, so a distributed solver falls out of the way the problem was assembled. It is the general statement the lab’s optimization software implements: the reason AlgebraicOptimization.jl can generate a distributed algorithm from the structure of a problem rather than from a hand-written decomposition.

Read it for Sections 3 and 4, where the problem algebra and the solver morphism are defined. The rest can wait for a second pass.

When is one diagram a presentation of the same system of equations as another? Reading a lift of a diagram against a discrete opfibration as a solution, the paper gives an equivalence of diagrams that holds exactly when the two have the same solutions, and identifies the localisation it generates with a localisation of a slice category along initial functors. The result is then lifted to the 2-categorical setting. Decapodes rewrites diagrams constantly – composing, stratifying, and simplifying them – and this is the result that says which of those rewrites are allowed to change the answer and which are not.

Read it for The definition of diagram equivalence and the statement of the localisation theorem. The 2-categorical extension is for readers who want the general form.

The folklore that dynamic programming is the right approach on compositionally structured graphs, made general and made precise. Structured decompositions define Grothendieck topologies on adhesive categories of data, and any problem expressible as a sheaf for one of those topologies can be decided in linear time on inputs of bounded decomposition width whose decomposition shapes have bounded feedback vertex number. This is the theorem the sheaves project is organized around: it says which problems the compositional algorithms apply to, and it applies to any C-set category, so the same statement covers graphs, hypergraphs, databases and simplicial complexes at once.

Read it for The topology construction and the main theorem. The catalogue of structures it specializes to is worth a skim to see how wide the result is.