Our paper “Towards a Unified Theory of Time-Varying Data” was accepted in the Springer journal “Applied Categorical Structures” — yay! As you might expect, the paper is all about data that — you guessed it — varies with time.
I’ve been thinking about time-varying graphs, where the vertices and edges may come and go as time hikes forward, for a while now. As part of my PhD thesis, Kitty Meeks and I defined a measure of structural complexity of temporal graphs which turned out to have lots of algorithmic applications (it even won the best paper award IWOCA!) but, despite these successes, there was something that bugged me: I still wasn’t sure what a temporal graph actually was!
So here’s the deal. In the temporal graph literature, they often speak about temporal graphs as being sequences of graphs, called snapshots, which represent how a graph might change with time. My question was: why is this a temporal graph and not just a sequence fo graphs? What part of the mathematical structure should compel me to think of this data as temporal? From my perspective this is where this whole project started. My coauthors — Wilmer Leal, James Fairbanks, Martti Karvonen & Frédéric Simard — certainly had different and complementary motivations, but I won’t speak on their behalf: get in touch with them, they’re all lovely and really smart!
The issue of making sense of what temporal data should be is rather complicated, as it turns out. I remember sitting in a little hippie tea shop in Gainesville discussing what time ought to be and what it really means for something to be temporal. We ended up agreeing with St. Augustine: what makes data temporal is that it is ‘in the memory’. By this we mean that temporal data should be all about snapshots, yes, but also about the memories between snapshots. This suggests that a key difference between temporal data and a mere indexed sequence of mathematical objects is that it is telling a story — there is a narrative arc.
So that’s what Wilmer, James, Martti, Frédéric and I did: we made the memory an explicit part of the data. We built on Schultz, Spivak and Vasilakopoulou’s sheaf-theoretic take on dynamical systems and provide a unified definition of time-varying data that works for basically any kind of mathematical object. We call these narratives — sheaves (or co-sheaves) over a category of intervals of time. When given as sheaves, we call them persistent narratives and we think of them as remembering what parts of the data persist over time. When given as co-sheaves, we call them cumulative narratives and we think of them as remembering all of the data we’ve seen so far.
One of our main contributions is to show that the way to record your temporal data really matters: although there are canonical functors \(\mathfrak{K}\) and \(\mathfrak{P}\) that let us transform persistent narratives into cumulative ones and vice-versa, these do not yield an equivalence of categories and thus information might be lost in these conversions. The good news is that the two functors \(\mathfrak{K}\) and \(\mathfrak{P}\) form an adjunction, so this loss of information is in some sense canonically trackable.
Another main contribution of ours is to distill desiderata for a theory of temporal data, which I’ll outline below.
(D1): (Categories of Temporal Data) Any theory of temporal data should define not only time-varying data, but also appropriate morphisms thereof.
(D2): (Cumulative and Persistent Perspectives) In contrast to being a mere sequence, temporal data should explicitly record whether it is to be viewed cumulatively or persistently. Furthermore there should be methods of conversion between these two viewpoints.
(D3): (Systematic ‘Temporalization’) Any theory of temporal data should come equipped with systematic ways of obtaining temporal analogues of notions relating to static data.
(D4): (Object Agnosticism) Theories of temporal data should be object agnostic and applicable to any kinds of data originating from given underlying dynamics.
(D5): (Sampling) Since temporal data naturally arises from some underlying dynamical system, any theory of temporal data should be seamlessly interoperable with theories of dynamical systems.
Our paper goes into all of these details and explains how our theory of narratives ticks the box of each desideratum. If you’re interested to learn more, you can check it out here or, as I recently found out, you can watch some videos on YouTube: our paper is now included as part of a course given by Nathaniel Osgood at the University of Saskatchewan. Thanks Nate!
That’s all for today. It’s always nice to celebrate when a paper gets accepted and to take the time to thank my wonderful coauthors and all the people who’ve helped along the way!
Abraços,
Ben