Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

July 27, 2022

Learning to Lie with Sheaves

Posted by Emily Riehl

guest post by Sean O’Connor and Ana Luiza Tenorio

Social networks are frequently represented by graphs: each agent/person is a vertex and the interactions between pairs of individuals are the edges. A starting point to think about the evolution of opinions over time is to associate to each vertex vv a real number x vx_v that represents the agreement of vv to respect a certain topic. For instance, fix the topic “category theory is cool”. In a social network of nn mathematicians, we will have some high positive x vx_v \in \mathbb{R} representing a strong agreement with this assertion, some high negative x vx_{v'}\in \mathbb{R} for a strong disagreement, and some neutral opinions. Those mathematicians interact and may change their original opinion. What is the group’s opinion about category theory after a period of time? Clearly, eventually, everyone will agree that category theory is cool. Jokes (or not) aside, a standard way to try to answer this is to study the dynamical system generated by the heat equation

(1)dxdt=αLxforsomeα>0 \frac{d x}{d t} = -\alpha L x \; for \; some \; \alpha \gt 0

where x=(x v 1,...,v v n) nx = (x_{v_1},...,v_{v_n})\in \mathbb{R}^n and LL is the graph Laplacian, a matrix that represents a graph defined by the difference L=DAL = D - A, with DD the degree matrix and AA the adjacency matrix of the graph. In this approach, originally proposed in Towards a mathematical theory of influence and attitude change, we study the evolution of opinion distributions without considering that expressed opinions may be different from personal opinions. In the paper Opinion Dynamics on Discourse Sheaves, Jakob Hansen and Robert Ghrist introduced a functor that addresses this distinction, and leads to a flexible model. We briefly present it here.

Opinion Dynamics on Cellular Sheaves

Consider a poset category GG using the structure of a given undirected graph. The objects are the vertices/agents vv and the edges/interactions ee, while the morphisms are the unique arrows induced by the incidence pair vev \unlhd e, that is, when vv is an endpoint of ee. The incident pair provides a partial order relation by xyx \unlhd y if and only if x=yx=y or xx is a vertex incident to an edge yy. Then the discourse sheaf is a functor F:GVectF: G \to Vect defined by specifying the associated data as follows

In the objects:

  • F(v)F(v) is the space of opinions (the private opinions), for each vertex vv;
  • F(e)F(e) is the space of discourse (the public opinions), for each edge ee.

In the morphism:

  • F ve:F(v)F(e)F_{v\unlhd e}: F(v) \to F(e) linear maps, for each incident pair vev\unlhd e.


Remark: The base of the space of opinions F(v)F(v) is formed by the topics that the agent vv has an opinion on and talks about. Given e=uve = u \to v, the base of the space of discourse F(e)F(e) is formed by common topics which the two agents uu and vv may talk about. The bases of F(v)F(v), F(u)F(u), and F(e)F(e) do not have to be equal.

More generally, replacing VectVect by any other category and GG by any cell category — a poset category where the faces of a cell complex induce the order relation — we have a cellular sheaf. For a reader familiar with sheaves on topological spaces, cellular sheaves may not look like a sheaf at all, but in Sheaves, Cosheaves, and Applications (at II.4), Justin Curry gives a detailed description of how to construct a categorical equivalence between cellular sheaves and sheaves on topological spaces — with an Erratum of one of the arguments. Such equivalence motivates the reuse of standard sheaf theory terminology. For instance, the vector spaces F(v)F(v) and F(e)F(e) are called stalks and the linear maps F veF_{v\unlhd e} are the restriction maps.

Now, choose an orientation e=uve = u \to v and consider the linear map δ: vGF(v) eGF(e)\delta: \bigoplus_{v \in G} F(v) \to \bigoplus_{e \in G} F(e) defined by (δx)e=F vex vF uex u.(\delta x)e = F_{v\unlhd e} x_v - F_{u\unlhd e} x_u. In the general context of cellular sheaf cohomology, the domain and contra-domain of the cochain complex δ\delta are, respectively, 00-cochains and 11-cochains. We do not have other nn-cochains because they are related to the nn-cell structure. Then we only have the 00-cohomology given by H 0(G,F)=KerδH^0(G,F) = \mathrm{Ker} \delta but this already is highly expressive for the model: given an opinion distribution x vGF(v),x \in \bigoplus_{v \in G} F(v), the linear map δ\delta calculates the signed difference between the expressed opinions of agents vv and uu. In other words, the cohomology detects how far the social network is to achieve an apparent consensus.

We also use the cochain complex to define the sheaf Laplacian by L F=δ Tδ:C 0(G,F)C 0(G,F)L_F = \delta^T\delta : C^0(G,F) \to C^0(G,F), which actually generalizes the graph Laplacian. When FF is the constant sheaf ̲\underline{ \mathbb{R}}, with stalks { \mathbb{R}} and identity maps, δ\delta is the transpose of the incidence matrix BB of the graph (so L ̲=BB TL_{\underline{ \mathbb{R}}} = BB^T).

Thus, the idea is to study the dynamical system generated by an equation similar to the first one we presented but replacing the graph Laplacian by the sheaf Laplacian and xx \in \mathbb{R} by x vGF(v).x \in \bigoplus_{v \in G} F(v). The first result we have is:

Solutions x(t)x(t) to dxdt=αL Fx\frac{d x}{d t} = -\alpha L_F x converge to the orthogonal projection of x(0)x(0) onto H 0(G;F)H^0(G; F), as tt \to \infty.

Here we highlight two points regarding the above theorem:

  • The proof only relies on techniques from linear algebra and calculus; no advanced knowledge in category theory or homological theory is required to study the dynamics. This is true for all the proofs in the paper;

  • The interpretation of this result is that the social network eventually arrives at the apparent consensus (with properties of the sheaf Laplacian influencing the rate of convergence).

Example: If FF is the constant sheaf n\mathbb{R}^n, then the base of nn topics is the same for every agent vv, all the restriction maps are identities, and so all agents are expressing their true opinion. Therefore, opinion dynamics by the analyses of (1)(1) may be seen as a particular case of opinion dynamics on sheaves.

Note that in the case of the constant sheaf ̲\underline{\mathbb{R}}, we get that the private opinions of all agents in communication will converge to the same value, which is not as intriguing (or realistic) of a result as might have been hoped. So using cellular sheaves to model a social network and using the sheaf Laplacian to evolve the opinions of each agent over time is quite interesting, but by itself unfortunately limited considering what we presented so far. In the following, we summarize how Jakob Hansen and Robert Ghrist modify this framework by not only evolving the private opinions of each agent over time, but also the expressions of opinions of each agent (in the form of the restriction maps).

Learning to Lie

As a simple example of this idea, we can keep the private opinions of each agent fixed while allowing the restriction maps to vary with time. Here we model the change in the restriction maps by ddtF ve=β(F vex vF uex u)x v T,forsomeβ>0\frac{d}{dt}F_{v\unlhd e} = -\beta(F_{v\unlhd e}x_v - F_{u\unlhd e}x_u)x^T_v, \, for some \beta \gt 0 The result is that over time each agent modifies each of their expressed opinions to minimize disagreement with their neighbors. However, one interesting behavior that emerges from this system is that agents can “learn to lie” in the sense that their restriction maps change to instead express the opposite of the private opinion they hold. In other words, negative real numbers in the matrix that represents the restriction maps witness what we call a lie, while non-negative real numbers in the matrix witness an exaggeration or a reduction of the personal opinion.

This emergent behavior is more realistic than having all agents’ private opinions reach a consensus, but this comes at the cost of all the private opinions being kept fixed. Thankfully, we can actually vary both the restriction maps and the private opinions of each agent with time!

Indeed, defining a differential equation where both ddtF ve=β(F vex vF uex u)x v T\frac{d}{dt}F_{v\unlhd e} = -\beta(F_{v\unlhd e}x_v - F_{u\unlhd e}x_u)x^T_v and dxdt=αL Fx\frac{dx}{dt} = -\alpha L_F x hold gives us exactly this model! This has the pleasant corollary that by setting β=0\beta = 0 or α=0\alpha = 0 we can recover the cases where the restriction maps or the private opinions are kept fixed, respectively.

From this, we can observe these joint-dynamical systems where agents will both change their private opinions and how they express their opinions to minimize expressed disagreement. Agents in these models thus learn to exaggerate, soften, or lie about their private opinions depending on the expressed opinions of other agents they are in communication with, while at the same time modifying their own private opinions to minimize overall expressed disagreement.

Finally, one phenomenon that these types of linear models do not capture is how two agents expressing significantly different opinions will cease communication (in the sense that their private opinions will be unaffected by this communication). Note that while this is certainly a mechanism of polarization, the joint-dynamic models can still produce polarization due to the restriction maps not being fixed. In Jakob Hansen and Robert Ghrist’s paper, the solution for this arises by introducing a nonlinear term in the sheaf Laplacian, which can be used to ignore communications where there is significant expressed disagreement. While this does come at the cost of linearity, the cellular sheaf framework is still applicable with minimal changes to the differential equations.

A Simple Simulation

Suppose we have an agent v 0v_0 that is not a big fan of category theory, such preference is represented by the value x v 0=1x_{v_0} = - 1; another agent appreciates category theory with intensity x v 1=3x_{v_1} = 3, and a third one likes it a bit, with x v 1=1 x_{v_1} = 1. All of them start the communication with each other being totally honest, that is, all restriction maps are represented by [1][1]. We then simulate the mixed situation where private and public opinion may change, and that the agents are interested in minimizing expressed disagreement. Taking α=0.1\alpha = 0.1 and β=1\beta = 1, we find the following:


Aiming for a better visualization, in the above picture we put the values x v ix_{v_i} instead of the vector spaces F(v i)=F(v_i) = \mathbb{R} and e je_j to abstractly represent the values in F(e j)F(e_j) associated with the application of F v ie jF_{v_i \unlhd e_j}. Note that the two category theory supporters do not lie to each other (they exaggerate or soften their opinion) but they do have to lie to the first agent. On the other hand, the first agent did not have to lie to anyone, they only softened their opinion to achieve the apparent consensus. It is also interesting to note that the agent with the strongest opinion in the beginning was the one forced to “lie more”, the same happened in Example 8.2 of Opinion Dynamics on Discourse Sheaves. One final note is that the communication between the first and last agents has effectively ceased, as both restriction maps are quite close to the zero map, which can be interpreted as the respective agent expressing no opinion whatsoever.

If you want to play with more complicated graphs, test other constants or different initial values, look at Sean’s Python code available in Github.


Cellular sheaves provide a framework to develop opinion dynamics: the calculations are relatively simple, and we obtain a flexible model. We focused on the ability to model agents that learn to lie, but the paper also explores, for instance, when we have agents that never change their (expressed) opinion; which additional hypothesis one should have to control the evolution of the group’s opinion; and the dynamics assuming a “bounded confidence” i.e., when the agents only take into consideration opinions that are similar to their own.

However, there still is much to be developed. The nonlinear case may lead to the study of the discourse sheaf with a contra-domain category different from VectVect (for example, the category of lattices). We also may change the category into the domain: since graphs only consider pairwise communication we may want to replace them by hypergraphs to study the multi-body interactions. Note that cellular sheaf theory provides a general setting that allows higher nn-cells. Such a framework should be useful to discuss simultaneous interactions in larger groups, but would require interpretation for the cohomology in higher degrees. Those are just a few examples of what we have to explore!

Finally, observe that we require just a few category theory notions, which were used to model the problem but the calculations are not from category theory. This is great to call attention to non-category theorists and apply analogous ideas in different contexts, with techniques already known from dynamical systems, for example. Certainly, it will be interesting to follow the next steps of applied cellular sheaf theory.

Posted at July 27, 2022 4:22 PM UTC

TrackBack URL for this Entry:

4 Comments & 0 Trackbacks

Re: Learning to Lie with Sheaves

This is extremely interesting. It seems to fit very comfortably with

MR1635735 (99h:92027) Hofbauer, Josef; Sigmund, Karl Evolutionary games and population dynamics,

see perhaps also

Posted by: jackjohnson on July 27, 2022 9:18 PM | Permalink | Reply to this

Re: Learning to Lie with Sheaves

I like how the blog post is an even more inviting taste of an already approachable paper. The simulation is really interesting. I wonder if “learning to lie” is useful in other contexts besides opinion dynamics. I had graph signal processing in mind, but there may be other interesting applications. I would be interesting to see the graphs (versus time) for each component of the “graph signals” as well as the constant for each of the neighboring restriction maps. I wonder if there are “phase transitions” here???

Posted by: Hans on July 31, 2022 5:48 PM | Permalink | Reply to this

Re: Learning to Lie with Sheaves

Maybe it could help explain mimesis and mimicry in biology?

Posted by: Madeleine Birchfield on July 31, 2022 8:47 PM | Permalink | Reply to this

Re: Learning to Lie with Sheaves

And I thought this was going to be about doing higher Lie theory with sheaves, like Urs Schreiber does.

Posted by: John Baez on August 1, 2022 9:37 PM | Permalink | Reply to this

Post a New Comment