How Big Data Carried Graph Theory Into New Dimensions
The mathematical language for talking about connections, which usually depends on networks — vertices (dots) and edges (lines connecting them) — has been an invaluable way to model real-world phenomena since at least the 18th century. But a few decades ago, the emergence of giant data sets forced researchers to expand their toolboxes and, at the same time, gave them sprawling sandboxes in which to apply new mathematical insights. Since then, said Josh Grochow, a computer scientist at the University of Colorado, Boulder, there’s been an exciting period of rapid growth as researchers have developed new kinds of network models that can find complex structures and signals in the noise of big data.
Grochow is among a growing chorus of researchers who point out that when it comes to finding connections in big data, graph theory has its limits. A graph represents every relationship as a dyad, or pairwise interaction. However, many complex systems can’t be represented by binary connections alone. Recent progress in the field shows how to move forward.
Consider trying to forge a network model of parenting. Clearly, each parent has a connection to a child, but the parenting relationship isn’t just the sum of the two links, as graph theory might model it. The same goes for trying to model a phenomenon like peer pressure.
“There are many intuitive models. The peer pressure effect on social dynamics is only captured if you already have groups in your data,” said Leonie Neuhäuser of RWTH Aachen University in Germany. But binary networks don’t capture group influences.
Mathematicians and computer scientists use the term “higher-order interactions” to describe these complex ways that group dynamics, rather than binary links, can influence individual behaviors. These mathematical phenomena appear in everything from entanglement interactions in quantum mechanics to the trajectory of a disease spreading through a population. If a pharmacologist wanted to model drug interactions, for example, graph theory might show how two drugs respond to each other — but what about three? Or four?
While the tools for exploring these interactions are not new, it’s only in recent years that high-dimensional data sets have become an engine for discovery, giving mathematicians and network theorists new ideas. These efforts have yielded interesting results about the limits of graphs and the possibilities of scaling up.
“Now we know that the network is just the shadow of the thing,” Grochow said. If a data set has a complex underlying structure, then modeling it as a graph may reveal only a limited projection of the whole story.
“We’ve realized that the data structures we’ve used to study things, from a mathematical perspective, aren’t quite fitting what we’re seeing in the data,” said the mathematician Emilie Purvine of the Pacific Northwest National Laboratory.
Which is why mathematicians, computer scientists and other researchers are increasingly focusing on ways to generalize graph theory — in its many guises — to explore higher-order phenomena. The last few years have brought a torrent of proposed ways to characterize these interactions, and to mathematically verify them in high-dimensional data sets.
For Purvine, the mathematical exploration of higher-order interactions is like the mapping of new dimensions. “Think about a graph as a foundation on a two-dimensional plot of land,” she said. The three-dimensional buildings that can go on top could vary significantly. “When you’re down at ground level, they look the same, but what you construct on top is different.”
The search for those higher-dimensional structures is where the math turns especially murky — and interesting. The higher-order analogue of a graph, for example, is called a hypergraph, and instead of edges, it has “hyperedges.” These can connect multiple nodes, which means it can represent multi-way (or multilinear) relationships.
