The spectral theory of hypergraphs (01.05.2020)

Raffaella Mulas and Jürgen Jost

Graph theory is an ubiquitous tool in network analysis, as a graph encodes pairwise relations between elements, and many networks are abstractly modelled by such relations. Often, however, real data contain relations between more than two elements. For instance, social relations, like coauthorships between scientists, involve more than two partners. And in chemical reactions, a set of educts is transformed into a set of products, to highlight another important example. Such relations can be modelled by hypergraphs. A hypergraph consists of a collection \(V\) of vertices, and a subset \(H\) of the powerset \(2^V\), the hyperedges. Thus, a hyperedge \(h\) links a collection \(V_h\subset V\) of vertices. If we required that whenever \(V_h\) belongs to a hyperedge, then also every nonempty \(V'\subset V_h\) does, we would have a simplicial complex. In most examples that we are interested in, however, that condition is not satisfied. For instance, a subset of the educts and products of a chemical reaction need to constitute a valid reaction. And if three authors have published a paper together, they need not all have single author papers or ones authored by only two of them.

Given this importance of hypergraphs for representing relations between elements in various empirical domains, it is desirable to have mathematical tools for analyzing them. In a graph theory, much of the structure of a graph is encoded in the spectrum of its Laplacian. That operator is defined for functions \(f:V\to \mathbb{R}\),

\(\Delta_0 f(i)= f(i)-\frac{1}{\mathrm{deg} (i)}\sum_{j\sim i}f(j),\)(1)

where \(\mathrm{deg} (i)\) counts the number of vertices \(j\) connected to \(i (j\sim i)\) by an edge. Its eigenvalues \(\lambda_1\le \dots \le \lambda_n\) tell us, for instance, how easily the graph can be cut into disjoint parts or how close it is to being bipartite. More generally, this spectrum quickly detects many qualitative properties, and studying it in detail has emerged as a powerful tool in network analysis. Also, the definition of \(\Delta\) can be naturally extended to simplicial complexes.

It is then natural to define a corresponding operator on hypergraphs. Several attempts had been proposed, typically guessing some extension of (1) or treating a hypergraph as a deficient simplicial complex. We have developed a more systematic mathematical approach. The eigenvalues are also the critical points of the Rayleigh quotients

\(\frac{\sum_{i\sim j} (f(i)-f(j))^2}{\sum_i \mathrm{deg} (i) f(i)^2},\)(2)

and, in fact, \(f(i)-f(j)\) can be seen as the value of \(\Delta\) on the edge \(i\sim j\). In other words, it is also possible to define a Laplacian \(\Delta_1\) on edges, and \(\Delta_0\) and \(\Delta_1\) have the same spectrum, except possibly for the multiplicity of the eigenvalue \(0\). But \(f(i)-f(j)\) has a sign (even though this does not affect (2)), and this changes when we interchange \(i\) and \(j\). Mathematically, this means that we should assign an orientation to each edge. This suggested to us to also introduce orientations on the hyperedges of a hypergraph, leading to the definition of a chemical hypergraph. There, the vertex set \(V_h\) of a hyperedge \(h\) consists of two (not necessarily disjoint) subsets \(V_h^1,V_h^2\), as shown in Figure 1. Changing the orientation means interchanging them. As in cohomology theory, working with signs then makes an abstract definition of Laplacians on the vertices and on the hyperedges possible, and as in the graph case, the two operators turn out to be dual to each other in the sense that they share the same nonzero spectrum.

And looking at the spectrum then provides us with a powerful for analyzing empirical data when the underlying relations can be modelled as hypergraphs.

Figure 1: A chemical hypergraph with five vertices and two hyperedges. Each vertex has, for each hyperedge in which it is contained, either a plus sign, a minus sign or both.

References

[1]   J.Jost and R.Mulas, Hypergraph Laplace operators for chemical reaction networks, Advances in Mathematics 351, 870–896, 2019
[2]   R.Mulas, C.Kuehn and J.Jost, Coupled Dynamics on Hypergraphs: Master Stability of Steady States and Synchronization, arXiv:2003.13775, 2020
[3]   R.Mulas, Sharp bounds for the largest eigenvalue of the normalized hypergraph Laplace Operator, arXiv:2004.02154, 2020
[4]   R.Mulas and D.Zhang, Spectral theory of Laplace Operators on chemical hypergraphs, arXiv:2004.14671, 2020

11.05.2020, 15:14