Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: applied category theory

Topic: incremental computation in adhesive categories

Kris Brown (Apr 30 2025 at 01:43):

My goal for this thread is to communicate an idea that I've been working on to @John Baez (and anyone else who is interested). It's very relevant to the agent-based models that John and I will be working on in Edinburgh later this summer. I'd like to write a paper eventually about this, and it would be helpful to practice my math communication skills here, since I don't have a traditional math background and am often uncertain what level of detail to go into. Any questions/clarifications are welcome!

Kris Brown (Apr 30 2025 at 01:43):

The core problem is that we are interested in computing the elements of a hom-set, say ${\rm Hom}(X,G)$, in some (adhesive) category $\mathsf{C}$. We could call $X$ our query and the hom set the answer to our query. What's special about this problem is that we imagine $G$ is making little changes very frequently: we want an algorithm which updates our hom-set with respect to a small change rather than having to recompute the whole thing from scratch after each little change.

Kris Brown (Apr 30 2025 at 01:45):

Our formal model of a change is the application of a rewrite rule $f: L \rightarrowtail R$ (our rules right now will be purely additive via pushout, rather than the usual pushout-complement-followed-by-pushout kind of rewrite rule). Here's an example in the category of graphs:

Screenshot 2025-04-29 at 6.31.31 PM.png

In that example, $G$ got 'updated' to $H$ via applying $f: L\rightarrowtail R$ via a match morphism $m: L \rightarrowtail G$. Our incremental search problem is: suppose we already knew ${\rm Hom}(X,G)$ for some $X$: how would we figure out what ${\rm Hom}(X,H)$ is? We clearly have a subset of it, ${\rm Hom}(X,G)\cdot \Delta$, but there are a bunch of new morphisms which sprang into existence due to the stuff that got added from the rewrite rule.

Kris Brown (Apr 30 2025 at 01:46):

In order to explain this, I'll need to make some computational assumptions about $\mathsf{C}$ to make explicit what it means to "find" morphisms. The following assumptions are motivated by the category of graphs: objects can be small or large, for practical purposes. The objects which appear in rules or queries are small, whereas the objects like $G$ and $H$ could be large. The computational complexity of enumerating ${\rm Hom}(A,B)$ is assumed to be intractable for arbitrary $A$ and $B$ (see: the subgraph isomorphism problem). However, we will assume it is tractable when performed between small objects. Furthermore, we assume we can efficiently enumerate some subsets of ${\rm Hom}(A,B)$ at runtime, in particular, whenever we have a partial map $A \leftarrowtail O \rightarrow B$ where $O$ is nonempty and $A$ is small and connected. Extending such a partial map to the subset of ${\rm Hom}(A,B)$ which agrees on the overlap corresponds to a rooted subgraph isomorphism problem (which is tractable). We can think of the overlap as initializing certain assignments of parts of $A$ to parts of $B$ in a search procedure, with the remaining unassigned values determined purely by the connectivity of $A$.

Screenshot 2025-04-29 at 6.41.14 PM.png

Kris Brown (Apr 30 2025 at 01:47):

So our strategy will be to systematically transform something that seems like a subgraph isomorphism problem into something that looks like the rooted subgraph isomorphism problem, and because of this we'll be much more efficient. And with that I hope I've communicated what the problem is that I'm trying to solve! I should probably stop there before charging ahead to a solution!

Zoltan A. Kocsis (Z.A.K.) (Apr 30 2025 at 01:53):

Not my field, but to me this looks very closely related to things that the GATAS lab folks work on and could help with, so I'm going to go ahead and tag @Benjamin Merlin Bumpus (he/him).

John Baez (Apr 30 2025 at 01:56):

It'll take me at least a few hours to give a serious response... but I'm glad you're diving in and explaining this.

Kevin Carlson (Apr 30 2025 at 02:13):

@Zoltan A. Kocsis (Z.A.K.) Kris has actually collaborated a lot with GATAS, including on this subject.

Zoltan A. Kocsis (Z.A.K.) (Apr 30 2025 at 03:54):

That's good, it means the similarity wasn't all in my head :sweat_smile:

David Corfield (Apr 30 2025 at 06:07):

Looks like a very interesting project.

Kris Brown said:

whenever we have a partial map $A \leftarrowtail O \rightarrow B$ where $O$ is nonempty and $A$ is small and connected. Extending such a partial map to the subset of ${\rm Hom}(A,B)$ which agrees on the overlap corresponds to a rooted subgraph isomorphism problem (which is tractable)

Out of interest, will you be working with situations where there's a unique extension, or could there be some optimising choice to be made?

Kris Brown (Apr 30 2025 at 06:43):

Uniqueness isn't really important in this context! For example, some graph rewrite rule might apply to $\bullet_1$ and add an outgoing edge $\bullet_1\rightarrow\bullet_{\rm fresh}$ (let's call the new updated graph $B$). If our query, $A$, is a path of length two, then the solution to our incremental search problem is "look for incoming edges to $\bullet_1$: every new map in ${\rm Hom}(A,B)$ corresponds to one of those!" In that scenario, we could imagine $O\rightarrow B$ maps the second edge of $A$ to the freshly-introduced edge, and there is an extension for every incoming edge to $\bullet_1$.

David Corfield (May 02 2025 at 06:02):

Just a thought, but I was hearing recently about @Matthijs Vákár and Tom Smeding's CHAD (Combinatory Homomorphic Automatic Differentiation), and how it's possible to vary their construction to one which could work for data provenance tracking and program slicing. It seems one can apply the automatic differentation idea in a very general setting, relating, in each direction, small changes of input and small changes of output.

I wonder if there's something similar possible here.

John Baez (May 02 2025 at 07:03):

Hi, Kris, I'm back . Sorry, that took more than a few hours: I'm in Edinburgh now.

I understand the problem you're trying to solve, you explained it clearly, so I'm ready to start hearing about how you solve it!

Kris Brown (May 02 2025 at 07:45):

The key fact about adhesive categories that I rely on is that any map into the apex of a pushout (e.g. a map $h: X \rightarrow H$ into the result of the rewrite of Fig 1 above) induces what I'll call an "adhesive cube", where the side faces are all determined by taking pullbacks with $h$. Because ${\mathsf C}$ is adhesive, the top face of this cube is itself a pushout: $X\cong X_G +_{X_L} X_R$. That is, something which maps into $G +_L R$ is itself made up of the part that mapped into $G$ (i.e. $X_G$) and the part of $X$ that mapped into $R$ (i.e. $X_R$), glued together by the part which mapped into $L$ (i.e. $X_L$).

Screenshot 2025-05-02 at 12.31.18 AM.png

Kris Brown (May 02 2025 at 07:45):

So whenever we apply a rewrite rule, we have the bottom face of an adhesive cube. Any match from our pattern $X$ into the result of the rule application, $h: X\rightarrow H$, has an associated adhesive cube. The top face of the cube is a pushout of subobjects of $X$. One thing we can do is consider all the ways we can express $X$ as a pushout of two of its subobjects. Maybe this takes some time, but we only need to do it once and store the result, plus we can do it in advance of any of the rewrite rule applications. So let us have all possible top faces of an adhesive cube at our disposal (we can call these decompositions of our pattern $X$).

Kris Brown (May 02 2025 at 07:47):

One of the side faces of the adhesive cube lives above the rewrite rule (let's call it the rule face of the cube). We assume we are in a setting where we know all of the rewrite rules that might be used, and we know all possible top edges of a rule face (they are subobject morphisms, $X_L\rightarrowtail X_R$). So we can actually compute all possible rule faces for a given subobject morphism + rule (say, $f: L\rightarrowtail R$) by looking for pairs of maps $h_L: X_L\rightarrow L$ and $h_R: X_R\rightarrow R$ such that they form a pullback square. I'll call this a set of interactions between a subobject morphism $X_L\rightarrowtail X_R$ and a rewrite rule $f$.

Kris Brown (May 02 2025 at 07:52):

When it comes time to actually find maps $h: X\rightarrow H$, given that a rewrite just occurred, we can iterate over all decompositions and interactions between the $X_L\rightarrowtail X_R$ and the rewrite rule that was used:

Screenshot 2025-05-02 at 12.49.47 AM.png

In this figure, things in black are "free" (we computed and stored them a long time ago), things in red are what are provided to us (the result of the rewrite), and the remainder in green is what we'll compute: we want to find all of the ways to complete this partial adhesive cube into a full one. In doing so, we'll find all of the matches ${\rm Hom}(X,H)$.

Kris Brown (May 02 2025 at 08:05):

It looks like we need to find two morphisms, but we really just need to find all $h_G: X_G\rightarrow G$ such that the face that lives over $m$ is a pullback square. Then we get $h: X\rightarrow H$ for free via copairing $[h_G\cdot \Delta, h_R\cdot r]$. Luckily, we can efficiently find all such possible $h_G$ because we have the partial map $X_G \leftarrowtail X_L \xrightarrow{h_L\cdot m} G$. If we filter these results to just those which form a pullback square with $m$, then we will have successfully found all matches because we exhaustively checked all partial adhesive cubes.

Kris Brown (May 02 2025 at 08:06):

A couple of details: there is a particular trivial decomposition where $X_G=X$ and $X_L=X_R=0$ which we ignore: we do this because we are solving the incremental search problem, and that decomposition will lead to all of (and only) the 'old' matches which we were trying to avoid, i.e. elements of ${\rm Hom}(X,G)\cdot \Delta$.

There's a little argument I'll need to give tomorrow to convince you that, other than for the trivial decomposition, that the partial map we use to enumerate $h_G$ candidates will always meet the criteria for corresponding to a 'rooted subgraph isomorphism' problem.

Kris Brown (May 02 2025 at 08:09):

Also, here's a figure of the particular two choices of decomposition + interaction (top+side face) that lead to discovering the two new matches from $X=\boxed{\bullet \rightarrow \bullet \rightarrow \bullet}$ which spring into existence when we apply the rule from Fig 1 above.

graphex.png

Note I'm implicitly specifying graph homomorphisms by saying where the vertices go in cases where it's not simply sending vertices to those with the same name.

Kris Brown (May 04 2025 at 16:53):

also the above was the "base case", and three directions I extend it are: 1.) we can solve the incremental problem even more efficiently if we assume our category's subobjects have complements, 2.) we can relax the assumption that the match $m$ used to apply the rewrite rule is monic, 3.) we can process any finite number of simultaneous rewrites at once (e.g. for the $n=2$ case, $H$ would the colimit of $R_1 \leftarrowtail L_1 \rightarrowtail G \leftarrowtail L_2 \rightarrowtail R_2$)

John Baez (May 05 2025 at 10:29):

Kris Brown said:

It looks like we need to find two morphisms, but we really just need to find all $h_G: X_G\rightarrow G$ such that the face that lives over $m$ is a pullback square. Then we get $h: X\rightarrow H$ for free via copairing $[h_G\cdot \Delta, h_R\cdot r]$. Luckily, we can efficiently find all such possible $h_G$ because we have the partial map $X_G \leftarrowtail X_L \xrightarrow{h_L\cdot m} G$. If we filter these results to just those which form a pullback square with $m$, then we will have successfully found all matches because we exhaustively checked all partial adhesive cubes.

I get this, and it's very nice - in fact this brings me closer to grokking the definition of [[adhesive category]] than I'd ever come before, because you're using that scary 'adhesive cube' in the definition in a very intuitively natural way.

John Baez (May 05 2025 at 10:35):

Kris Brown said:

There's a little argument I'll need to give tomorrow to convince you that, other than for the trivial decomposition, that the partial map we use to enumerate $h_G$ candidates will always meet the criteria for corresponding to a 'rooted subgraph isomorphism' problem.

This sounds like the point in the paper, if I were reading the paper, that my eyes would glaze over and I'd say "okay, I get the basic idea, I should really get back to work on my own stuff".

(Sorry, that sounds mean, but I figure honest feedback about one particular reader's psychology is worthwhile even if it just shows they are annoyingly uncommitted to understanding what you are trying to explain! Perhaps if I'm not atypical you can just note that readers like me would be perfectly happy to take some things on faith, so you can organize the paper in such a way that the fun easy stuff (which is I think what you just presented) is easy to understand without requiring the reader to follow the more detailed stuff.)

Ryan Wisnesky (May 05 2025 at 13:17):

I'm not sure what you're saying is mean, it simply seems to be a statement that mathematicians may not care about computational complexity the same way computer scientists would - so maybe a paper describing reductions of a CT problem to rooted subgraph isomorphism would be better at a computer science conference than a math one.

John Baez (May 05 2025 at 13:20):

Kris' paper will, I believe, be aimed at a computer science journal on databases and/or incremental computation. If so, my taste is not very relevant! But I promised to try to understand his explanation and give feedback, so I felt it was a bit rude to announce my eyes were about to glaze over.

Anyway, I hope he continues his explanation.

Kris Brown (May 05 2025 at 17:38):

The argument I omitted is quite short! We want to show the partial map ${X_G\leftarrowtail X_L\xrightarrow{h_L\cdot m} G}$ always yields a rooted homomorphism search. This means showing $X_G$, which itself may not be connected (e.g. the top example in my most recent image), has no connected component which lies outside the image of $X_L$. First, $X_R$ is nonempty because we ruled out the trivial decomposition. Then, because we assumed $X$ is connected and $X\cong X_G+_{X_L}X_R$, if some disconnected component of $X_G$ were not in the image of $X_L$, it would remain a disconnected component in $X$.

Kris Brown (May 05 2025 at 17:41):

Actually I think I forgot to mention that I'd been assuming our pattern $X$ is connected: we can do this without loss of generality, since if we were ultimately interested in incrementally monitoring ${\rm Hom}(X+Y,-)$ then it suffices to just incrementally monitor ${\rm Hom}(X,-)$ and ${\rm Hom}(Y,-)$

Kris Brown (May 05 2025 at 17:48):

Locating the intersection of people whose eyes wouldn't glaze over from the definition of a pullback and the people who would truly be interested in the computational complexity of database queries will be a challenge for future me! For the time being I'm happy to just check John is happy with the technical persuasiveness of the argument (but who knows if there ends up being some connection to detecting cycles in graphs which originate from pushouts!).

Kris Brown (May 05 2025 at 23:28):

Let me check if my "optimized algorithm" makes sense: when we are fortunate enough that $\mathsf{C}$ has complements (terminology I get from Evan and David Jaz's blog post, whereas nlab calls them supplements) we can do something even faster. It's faster in two ways: 1.) you might be worried there are a lot of ways to express $X$ as a pushout $X_G +_{X_L} X_R$ that we have to iterate over, and 2.) it might seem wasteful that, when we were trying to turn our partial adhesive cubes into complete ones via morphisms we found by extending a partial map from $X_G$ to $G$, we had to filter all the possible extensions by ones which formed a pullback for the side face of the adhesive cube. This optimized algorithm says we'll also solve the problem if we do the same process but 1.) only consider decompositions where $X_R = {\sim}X_G$ 2.) use all of the the extensions of the partial map.

Kris Brown (May 05 2025 at 23:33):

For any match $h: X\rightarrow H$, we have not only a unique adhesive cube, but also what I'll call a unique minimal adhesive cube which one gets from composing two cubes together like in the below diagram:

Screenshot 2025-05-05 at 4.31.18 PM.png

(on the left I've drawn out the top, bottom, and front face of this composite cube)

Kris Brown (May 05 2025 at 23:40):

Note we can see this arbitrary $h$ has a unique associated interaction between $\partial X_G \rightarrowtail {\sim}X_G$ and $f$, i.e. a pair of maps $(h_\partial, h_\sim)$ that forms a pullback with $f$. We get this by precomposing $h_l$ and $h_r$ with $\partial X_G \rightarrowtail X_L$ and ${\sim}X_G \rightarrowtail X_R$ respectively.

Kris Brown (May 05 2025 at 23:44):

So the algorithm is structurally the same: each $h$ has a unique cube associated with it, so loop over all partial cubes and try to complete them. But it's nicer to loop over partial minimal adhesive cubes because the possible top faces are generally are a small subset of all possible decompositions of $X$. Also, the way to complete these cubes is simply looking for maps $h_G$ which extend the partial map $X_G \leftarrowtail \partial X_G \xrightarrow{h_\partial \cdot m} G$ (no filter step necessary). By the same argument as above, this partial map induces a rooted search problem because $X$ is connected and we are excluding the trivial decomposition.