papers and preprints
-
Neural networks operating on inputs associated to the nodes of a graph are often constructed using traditional graph operators like the adjacency matrix and Laplacian. This paper is a brief exploration of the use of sheaf Laplacians as building blocks for graph neural networks. This is particularly suited to situations where edges of the graph carry extra relational information, as with signed graphs. Our test case is a synthetic node-classification problem, where some edges imply a negative relationship between the classes of the nodes they join. The sheaf neural network handily outperforms a standard graph neural network, suggesting that in settings where information about the relationships represented by edges is available, sheaf operators are a good way to enforce those relationships in a neural network.
Convolutional neural networks are very useful, and depend on the translational structure of Euclidean space induced by its structure as an abelian group. Other notions of convolution exist for signals defined over different sorts of algebraic spaces. In this paper, we consider convolution of signals over lattices, partially ordered sets with a meet operation \(\wedge\) and a join operation \(\vee\) that find the greatest lower bound and least upper bound of a pair of elements. We can “translate” signals defined on a lattice using these operators, and so convolve them with kernel functions.
One setting where signals naturally indexed by a lattice arise is multiparameter persistent homology: the filtration parameters form a partially-ordered set, and at each filtration level there are various features (like the dimension of the degree-\(k\) homology) that can be extracted. Thus, these are a natural setting to apply lattice convolutional networks. This brief paper explains the framework and runs some preliminary tests.
-
A matrix-weighted graph is an undirected graph with a \(d \times d\) positive semidefinite weight matrix assigned to each edge. These are a very simple example of weighted cellular sheaves, where the weight matrices define (possibly degenerate) inner products on edge stalks. In this paper, I explore the properties of these graphs from a graph theoretic perspective. This paper has two main results, and a definition:
- There is an expander mixing lemma for matrix weighted graphs. This gives matrix-theoretic bounds on the total weight between two sets of vertices in terms of the size of the sets and the spectrum of the adjacency matrix.
- Only one half of a Cheeger-type inequality holds for matrix-weighted graphs. A large Laplacian spectral gap ensures that weights over cut sets are large, but the converse is not true.
- A matrix-weighted expander graph has orthogonal projections as edge weights and a constant matrix-valued degree proportional to the identity matrix. Constructing nontrivial examples of these graphs is tricky, but there is the tantalizing possibility of obtaining better spectral expansion constants than are possible with standard unweighted graphs.
-
The distribution of opinions in a social network can be described as a 0-cochain of a cellular sheaf associated with the network. This discourse sheaf gives information about when the individuals in the network perceive their opinions as being in agreement. Sheaf Laplacians then are a tool for describing dynamics of opinions in these social networks. The modeling power of cellular sheaves allows these dynamics to implement many sophisticated features, including selective communication, lying, and antagonistic interactions. The dynamics constructed to describe the evolution of opinions and communication are, of course, not limited in their applicability to opinion dynamics, and one could take this paper as an initial exploration into the possibilities for sheaf dynamics with opinion evolution as a running example.
-
This paper contains the theoretical foundations of what one might call “spectral sheaf theory,” an extension of spectral graph theory to sheaves on graphs and complexes. Introducing an inner product structure on the stalks of a cellular sheaf allows us to construct Hodge Laplacians, which behave analogously to the discrete Hodge Laplacians first introduced by Eckmann. A number of constructions in spectral graph theory and network engineering turn out to be examples of cellular sheaves, and we suggest further directions for applications of the theory.
- ICASSP
How do we learn a network structure from data? That is, suppose we have a number of signals supported on the vertices of an unknown network and we wish to discover the network. Under the assumption that these signals are smooth, i.e., they have small variation over edges, this is a convex optimization problem. However, the smoothness assumption privileges constant signals on the graph, while the structure of the signals might come from more complicated interactions over edges. This paper shows that we can learn a sheaf Laplacian instead of a graph Laplacian, allowing us to extract networks with more complex behaviors.
Consider a network of independent agents with indices \(i\), each with a locally computable real-valued function \(f_i\). Can the agents collaborate via connections in the network to find the minimum of \(\sum f_i(x)\)? The answer is yes; one approach involves converting the global optimization problem to a collection of local problems \(\sum f_i(x_i)\) subject to an equality constraint represented by the graph Laplacian. Standard optimization techniques then produce an algorithm that only requires communication between neighboring agents in the graph. We generalize this method to optimization over the space of 0-cochains of a cellular sheaf subject to the constraint \(x \in H^0(G;\mathcal{F})\). Examples with connections to engineering problems are included.
-
Carlsson and Mémoli showed that there exists a unique hierarchical clustering functor satisfying certain natural constraints. In this paper, we consider a generalization of clustering where we allow clusters to overlap, and show that this allows for a significantly greater variety of clustering functors.
other resources
-
A Julia package for learning sheaves from data. Based largely on the optimization problems considered in Learning Sheaf Laplacians from Smooth Signals.
-
A Gentle Introduction to Sheaves on Graphs
updated March 2021An expository introduction to sheaves on graphs, oriented toward applications in engineering and network science. This is a work in progress and will be updated sporadically.
-
My PhD thesis. Much of it is an expanded and refined version of material contained in various papers above.
-
A translation of a short paper by Hermann Weyl about the relationship between algebraic topology and electrical circuits. The Spanish-language original is available on John Baez’s website. This might be the earliest observation that topology has something to say about circuits, but the antiquated terminology and notation make it a much harder read than it has to be.