Fifty years ago, mathematician Paul Erdős posed a problem to friends at one of his regular tea parties. The trio thought they would be able to come up with a solution the same afternoon.
It took 49 years for other mathematicians to provide an answer.
The Erdős-Faber-Lovász conjecture focused on a familiar question in mathematics, one of graph coloring. However, this was not on a conventional graph, but on another more-complex structure: a hypergraph. Unlike graphs, where the connection or edges between nodes are point-to-point links, the edges of a hypergraph can enclose any number of points. Groups can overlap and even enclose others, so factors that helped ensure the solution to any coloring problem, including the one set by Erdős, turn out to be quite different to one for conventional graphs.
The differences continue into practically all other aspects of hypergraph mathematics. There are many analogies between the two types of structure: it is entirely possible to treat a conventional graph as a special case of the richer hypergraph family. It is essentially a hypergraph for the case in which each edge is allowed to span only two vertices. The variety of hypergraphs presents much bigger challenges that mathematicians are trying to tackle on multiple fronts.
Figure. A hypergraph with seven vertices and four edges.
When trying to generalize the properties of hypergraph, “Everything is surprising,” says Raffaella Mulas, group leader at the Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany. “It’s often surprising when something can be generalized, and I’m also surprised when things that seem to be trivial can’t be generalized.”
Mulas’ current area of research focuses on the spectra of hypergraphs. These spectra, like the spectra of graphs, are generated from transpositions and other manipulations of the matrix that describes how the vertices are connected. However, that is where most of the similarities end.
In a graph, the edges are represented by non-zero weights on either side of the matrix diagonal: the rows and columns both represent vertices.
When represented by a matrix, the hypergraph has a quite different structure. Typically, vertices are listed in the rows and each edge grouping has its own column. That, in turn, leads to different mechanisms not just for constructing the spectra, but also for determining what derived properties such as eigenvalues mean.
Spectra are important tools for applications such as clustering in machine learning because, in principle, they provide computationally cheap ways of finding natural groupings in the data. By focusing on the connectivity between vertices judged by the number of shared edges, spectral clustering can prove far more effective at finding partitions than simpler methods such as k-means clustering.
“The most basic thing that a spectrum can do for a graph is count the connected components,” Mulas says, but this does not work for hypergraphs. “The situations where you can recover the connectivity spectra for hypergraphs are only for very structured cases.”
Such differences have slowed acceptance of the hypergraph as a tool for analyzing data, though there are many situations that have emerged where a hypergraph is the most natural representation. For example, in the early 1990s, Richard Shi, then a post-doctoral researcher at Canada’s University of Waterloo and now a professor of electrical engineering at the University of Washington in Seattle, proposed using directed hypergraphs to build layout tools for integrated circuits that would keep related components closer together.
The hypergraphs Shi conceived later evolved into what are now known as oriented hypergraphs, which have been joined by chemical hypergraphs, so named because they readily represent reactions using catalysts, and a further variant, the hypergraph with real weights. Mulas has collaborated with other groups to develop tools for modeling biological interactions using the real-weight variants.
In recent years, hypergraphs have become the focus of attention for interpreting behavior and connections in social networks because they can show many more types of group activity than simple pair-wise relationships. Yet the available tools for analyzing groups and simplifying the structures to cut processing time when dealing with large amounts of data have been found wanting. Because of the mathematical differences between graphs and hypergraphs, applied research in the past has often had to fall back on the more established tools from graph theory, often with the help of extensions such as clique and star expansions.
The hypergraphs Shi conceived later evolved into oriented hypergraphs, which have been joined by chemical hypergraphs, and the hypergraph with real weights.
In 2006, Sameer Agarwal and colleagues at the University of California at San Diego showed that several algorithms that had been proposed for handling the higher-order structure of a hypergraph in effect used the same techniques as regular graph theory, so there was little practical benefit in using them. They argued the techniques available for machine learning in particular mostly reduced to graph-based techniques, though they might use extensions such as cliques to try to represent group connections.
Nate Veldt, assistant professor of computer science and engineering at Texas A&M University, argues the techniques identified in the 2006 paper should still be regarded as useful hypergraph techniques. “Explicitly treating higher-order relationships as hyperedges can often lead to techniques that you might not come up with if you jump directly to using pairwise relationships in graphs, and I think this can be said for these previous methods,” he notes, adding that the landscape has changed over the intervening 15 years.
“Many recent results in hypergraph analysis do not simply amount to applying graph methods after applying a simple clique or star expansion,” Veldt says. “These simple reduction techniques do perform well in some applications, but we are also seeing a growing number of examples and applications where more sophisticated methods for analyzing hypergraphs are yielding better results.”
Veldt and colleagues working at Cornell University developed clustering methods based on hypergraphs that, he says, outperformed simpler graph-reduction methods at tasks such as identifying groups of primary and high school students in experiments that used wearable devices to collect proximity data.
While he says it is hard to quantify, Veldt believes there has been an acceleration in hypergraph research over the past five years. Different groups are working on a variety of core and applied mathematical aspects. Expecting big-data applications to benefit, the National Science Foundation last year awarded grants to several researchers to look at methods for the analysis of partial hypergraphs: this would allow them to be processed as they are streamed from storage, instead of requiring the entire structure be loaded into memory first.
A more traditional method for reducing the computational load for large graphs is sparsification. The current focus of Luca Trevisan, professor of computer science at Milan’s Bocconi University, sparsification is a method for simplifying graphs by removing vertices or edges so their structures can be analyzed with fewer computations. As with the older clustering algorithms, hypergraph sparsification has needed to rely on reductions to graph methods, he says. Trevisan’s aim is to move towards techniques that leverage tensors that can yield better results and match the performance of existing graph sparsifiers.
Though a single matrix can represent a hypergraph’s connections, transforming it into a multidimensional tensor should provide the opportunity to probe the structure more fully. Mulas says staying in the domain of matrices can lead to a loss of useful information.
The National Science Foundation last year awarded grants to several researchers to look at methods for the analysis of partial hypergraphs.
The big problem with moving the mathematics of hypergraphs into tensors is that the tools of linear algebra developed using matrices often break down. In a 2013 paper, Christopher Hillar of the Mathematical Sciences Research Institute in Berkeley and Lek-Heng Lim of the University of Chicago concluded that many operations that are relatively simple and efficient in performance in the domain of matrices, such as computing eigenvalues, become NP-hard even if applied to tensors with just three dimensions.
“I personally view my study of hypergraph sparsification as a scouting expedition, a way to explore what to do when you have higher-dimensional data for which conventional linear-algebraic techniques break down,” Trevisan says. “I like the problem of hypergraph sparsification because it lets me conduct this exploration into a very narrow and clean special case.”
As well as possibly leading to fundamental advances in tensor mathematics, the use of hypergraph analysis for applications such as social groupings is revealing novel insights into the structure of data. Veldt points to the concept of homophily: the tendency of nodes with similar properties to be connected. Various definitions of homophily appear in graph theory that seem to connect well with the way people think of social groups. However, Veldt and colleagues at Cornell University found it is impossible for different types of homophily to co-exist in the same hypergraph: men and women seem to be unable to simultaneously exhibit preferences for groups where their gender is the majority, for example.
“Intuitive notions of homophily that have been applied to graphs don’t really work in a hypergraph,” Veldt says.
Different constructions may be needed to analyze homophily in a hypergraph setting. “Homophily in hypergraphs just may not be what you think it is at first. It’s important to be aware of these underlying mathematical inevitabilities and not necessarily because of social phenomena. Our results are similar in spirit to the Friendship Paradox: the principle that ‘your friends typically have more friends than you do’. This seems like it would have something to do with an underlying social phenomenon, but it turns out it can be explained by combinatorial facts in graphs.”
Further work will be needed to probe the theoretical basis for the clear differences between the two representations not just for homophily, but many of the other properties of hypergraphs and how they affect application. “The theory brings the applications. And applications bring forward the theory. Both inspire each other,” says Mulas.
What is not clear is how long it might take to develop a body of knowledge similar to that of graphs, as Erdős and friends found.
Further Reading
Agarwal, S., Branson, K., and Belongie, S.
Higher-Order Learning with Graphs Proceedings of the 23rd International Conference on Machine Learning (ICML 2006), pages 17–24
Jost, J. and Mulas, R.
Normalized Laplace Operators for Hypergraphs with Real Coefficients Journal of Complex Networks, Volume 9, Issue 1, February 2021, cnab009
Hillar, C.J., and Lim, L.-H.
Most Tensor Problems are NP-Hard Journal of the ACM, 60, 6, Article 45, November 2013
Veldt, N., Benson, A.R., and Kleinberg, J.
Higher-order Homophily is Combinatorially Impossible arXiv: 2103.11818 (2021), https://arxiv.org/abs/2103.11818
Join the Discussion (0)
Become a Member or Sign In to Post a Comment