Hypergraphs Examined

Always interested in better ways to use visuals to come to useful conclusions in contexts.  Is this one?  Has anyone some good concrete examples?

A Group Effort   By Chris Edwards  in the ACM

Communications of the ACM, March 2022, Vol. 65 No. 3, Pages 12-14  10.1145/3510550

(more graphic examples at the link) 

Fifty years ago, mathematician Paul Erds 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 Erds-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 Erds, 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.

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.  ... '  (more and visuals at the link above)