SIAM News Blog
SIAM News
Print

Higher-order Network Analysis Takes Off, Fueled by Old Ideas and New Data

By Austin R. Benson, David F. Gleich, and Desmond J. Higham

In 2004, the theme of Mathematics Awareness Month was “the mathematics of networks.” A corresponding SIAM News article dubbed 2004 “The Year of the Network” and predicted that graphs would soon be everywhere. Now, networks and graphs were not new at the time. The first use of graphs in mathematics dates back to “chemicographs” in the 1800s [19], and one can trace the origins of PageRank-style linear algebra to ideas for ranking chess players [11]. Graph algorithms were common in the 1950s and served as a fascinating and fertile area in the new discipline of computer science. By 2004, their time had arrived. Innovative systems with network and graph structures—notably from biological and internet settings—suggested novel questions. In an archived SIAM News article, Fan Chung Graham made the following observation: “Many of the information networks that surround us today provide interesting motivation and suggest new and challenging research directions that will engage researchers for years to come.”

Since 2004, opportunities in what we would now call network science and data science have grown tremendously due to the power of computational techniques to tease subtle insights out of networked data. This led to more data and more questions, just as Fan Chung Graham predicted. However, researchers have been unable to easily address some of these questions with the standard representations of a complex system as a graph.

Making a distinction between the terms “network” and “graph” clarifies this point. The following framing captures the essential difference: a network is a graph that represents a complex system. Therefore, all networks are graphs, but certain graphs—such as the Petersen graph, which was constructed as a counterexample to a mathematical conjecture—are not networks. A graph consists of vertices and edges, and each edge is comprised of a pair of vertices. The fields of network analysis and network science grew around the use of graph formalism to simplify and study more complicated systems from the internet, social science, biology, neuroscience, and many other applications.

This framing offers opportunities for other, richer representations of complex systems (see Figure 1). For instance, the community quickly pointed out that the pairwise relationships modeled by edges did not sufficiently capture relevant properties. Researchers’ trendsetting work on network motifs in biological signaling systems in 2002 identified and attempted to interpret small circuits of nodes that appear as statistically significant subgraphs [15]. Likewise, triangles, transitivity, and triadic completion—i.e., friends-of-friends—play a key role in scientists’ understanding of social network data; Anatol Rapoport, James Davis, Mark Granovetter, and others pointed this out in work during the 1950s through the 1970s that pre-dates the rapid growth of social network analysis.

Higher-order network analysis involves richer representations of complex systems to gain deeper insight into data.

The concept of multinode interactions is also not entirely new. In the 1960s and 1970s, researchers discussed hypergraphs — those where edges represent a multiway connection. This formalism was later important in the layout of very large-scale integration circuits and the partitioning of computations for the emerging class of parallel distributed computers based on the Message Passing Interface (MPI).

In defense of networks as graphs, one must also appreciate that a graph is a wonderfully flexible concept. A weighted graph may simultaneously represent a Markov chain, sparse matrix, diffusion operator, and many other objects, depending on its exact use. Even problems that are posed on hypergraphs may reduce to graph computations; for instance, one can find a hypergraph’s connected components by computing the connected components of a related bipartite graph.

But not all problems reduce to graphs. For example, traditional memoryless Markov chains are inappropriate for understanding traffic patterns in transportation systems like subways and airplanes [17]. A similar scenario emerged when scientists at Yahoo and Google wanted to understand web browsing behavior and found that a straightforward Markov chain is too crude [5]. To address issues that arose from this data, each reached for new types of higher-order stochastic processes with more memory — namely higher-order and variable-order Markov chains.

As the number of these scenarios and questions grew within the community, a multitude of rich and higher-order representations emerged. These representations include tensors, simplicial complexes, and hypergraphs. Such variations occur because the appropriate representation depends crucially on the research problem in question. Consider the following illustration on disease propagation, which is adapted from [20]:

  1. Has this pair of individuals ever been close enough to infect each other? In this case, a simple undirected graph—the traditional setting, wherein each edge records a possible route of infection—is appropriate.
  2. Has this set of individuals ever formed all or part of a group whose members came close enough to infect each other? In this case, a simplicial complex is appropriate. This structure allows for downward closure; any subset of nodes within a simplex also forms a simplex. Each simplex identifies a set of people who might be infected simultaneously.
  3. Has this set of individuals ever comprised an entire group whose members came close enough to infect each other? In this case, a hypergraph is appropriate. A proper subset of those individuals will not appear as a hyperedge unless the individuals have gathered as a complete group. This is perhaps the most natural and informative structure, wherein we record only entire groups of individuals who might be infected simultaneously.

These new modeling methodologies can also feature the behavior of processes, such as random walks, on top of the data. The following example pertains to the behavior of a random walk-like process on a hypergraph [14]:

  1. Consider a random walk that visits a hypergraph’s nodes by selecting a random hyperedge that involves the current node, then picks a random node in that hyperedge. This process is equivalent to a random walk on the bipartite network that represents the hypergraph where we “ignore” or “censor” the nodes that signify the hyperedges. This in turn corresponds to a random walk on a weighted graph with the same node set as the hypergraph; the process is Markovian on the state space of nodes. In this case, one can then answer questions about the process via existing graph-based and matrix-based techniques.
  2. To motivate our generalization, ponder the following equivalent description of the above process. Given a starting node, the process defines a sequence of hyperedges where adjacent edges in the sequence share a single node. Suppose, however, that we make a tiny modification such that adjacent edges must share two nodes. This new procedure defines an edge process that one cannot easily represent with traditional graph and matrix techniques, as there is no notion of “where” the walk is that admits a simplification. The process is no longer Markovian on the state space of nodes, but more complex machinery can compute probabilities that are associated with the process via a related Markov chain.

New developments in higher-order analysis thus begin to appear when studies become increasingly specialized and focused.


Higher-order Machinery

Although higher-order network analysis is still an active area of research and development, a number of its technical tools and ideas are becoming commonplace.  Here we will summarize some key examples and explore how they work in terms of PageRank generalizations.

Hypergraphs

A hypergraph is simply a generalization of a graph structure wherein edges can represent relationships among more than two entities. They are perhaps the most general representation of higher-order relationships. Mathematical functions can be associated with each hyperedge to make the setting extremely general.

Motifs

Motifs were among the first formalizations to accommodate the idea that small patterns could be more important than edges alone. Identifying all instances of a motif or set of motifs thus serves as a means of extracting or finding higher-order structure within simple graph data. This action can also provide a pathway for simplifying a collection of complex data into a more concretely specified problem. A collection of motifs that are the same size may be stored as a uniform hypergraph (where all hyperedges are the same size).

Higher-order Markov Chains

Markov chains and random walks are canonical stochastic processes on a graph wherein the process’ ongoing behavior is independent of its past behavior. Generalizations are therefore natural. Higher-order Markov chains are stochastic processes that depend on a limited space of past behavior. Many computations on these processes reduce to a standard Markov chain on a Cartesian product state space. However, the mathematically interesting relationships begin to appear when one considers approximations and variable-order chains. Non-backtracking random walks and their generalizations—which are higher-order Markov chains where the process does not immediately return to its previous state—are now considered to be a standard analysis tool, which raises new questions and algorithmic possibilities [1].

Tensors and Hypermatrices

A tensor, or hypermatrix, is a multidimensional generalization of a matrix. Researchers have long studied rectangular tensors in terms of low-parameter structure. The adjacency tensor of a \(k\)-element uniform hypergraph is an equal-sided (or cubical) array, in which all entries associated with a hyperedge (and all of its permutations) have value \(1\) and all other entries have value \(0\). Tensor eigenpairs arise in generalizations of graph centrality measures to uniform hypergraphs and in generalizations of PageRank. A downside to tensors is that most tensor problems are NP-hard. This issue is currently motivating scientists to identify structures in the tensors that could enable polynomial-time algorithms, such as spacey random walks and new types of ergodicity coefficients [3, 6].

Simplicial Complexes

A simplicial complex is a collection of sets (simplices) that is closed with respect to taking subsets; for any \(X\) in the complex, any nonempty subset \(Y\) of \(X\) is also in the complex. Researchers can think of a graph as a simplicial complex, where each edge and vertex is mapped to a set. Alternatively, one could encode a richer graph structure in a simplicial complex by mapping each clique of size at most \(k\) to a set. Similarly, it is possible to induce a simplicial complex from a hypergraph by treating the edges as sets of nodes and including all edges and their subsets. Modeling interactions with simplicial complexes naturally results in the use of topology-related tools. For example, scientists have utilized homology, cohomology, and Hodge theory to find topological holes or cavities that are important in brain networks, identify voting “islands” within elections, and estimate traffic in road systems. Matrix computations that involve generalizations of the graph Laplacian to Hodge Laplacians often underlie these methods [13].

Examples of These Tools with PageRank

PageRank is a central algorithm in network science. The elegance of the mathematics behind PageRank enables many possible derivations; the classic derivation occurs via Markov chains, random walks, and the random surfer on the web. Alternative derivations arise in social theory, smooth functions on graphs, biased and localized spectral clustering, maximum likelihood estimates of blockmodels, mincut minorants, and edge-based walks. These various derivations all correspond to the same mathematical expression involving a linear system on a graph.

Higher-order generalizations of many of these ideas also exist. However, these generalizations typically lead us in different directions; some are nonlinear and some are extremely specific to the data representation.

For instance, one can employ any higher-order Markov chain to study a random surfer. This produces a related higher-order Markov chain. However, use of a spacey random walk on that same higher-order Markov chain yields a tensor eigenvector [3]. Related notions of PageRank on hypergraphs [12] and motif-derived hypergraphs [2] utilize the ability of hypergraph edges to associate with functions that model complex cuts. An additional example is the application of PageRank to a simplicial complex, which uses random walks that are derived from a normalization of a Hodge Laplacian matrix — just as one can derive PageRank by normalizing a graph Laplacian matrix to obtain a random walk matrix [18].

Each generalization comes with different modeling and computational tradeoffs. PageRank as a tensor eigenvector does not have a clear algorithmic standing, and we have conjectured that it is Polynomial Parity Arguments on Directed graphs (PPAD) complete. If one uses the Lovász extension of a submodular function that is associated with the hyperedge, hypergraph PageRank then becomes a convex problem. This reduces to a simple matrix computation for 3-uniform hyperedges. The simplicial complex PageRank vector orthogonally decomposes into three components with different topological meanings.

The nature of the question determines which generalization is most appropriate. While higher-order tools enable richer and more nuanced insights into data, they also demand a keen appreciation of the methods’ implicit assumptions and applied semantics, as illustrated in the aforementioned contact-infection example.


Impacts and Open Possibilities

In addition to posing fascinating mathematical and computational problems, higher-order methods are becoming increasingly important to many fields.

  1. Research into ecological systems has shown that multiway interactions among species are necessary to resolve paradoxes between real-world ecological outcomes and simple synthetic pairwise competition models [8].
  2. Studies of neuroscience conjecture that higher-order methods are essential to unravel the fundamental mysteries of cognition [7]. 
  3. Accurate models for certain networks flows, such as passenger airport traversal, require higher-order structure [17]. Researchers can even use such flows to define the meaning of “higher-order” [10]. 
  4. For the broad field of dynamical systems, higher-order interaction models yield markedly new behavior in many settings, including opinion dynamics [16], synchronization [4], and disease spread [9].

Numerous interesting questions pertaining to these methods remain. For example, there appears to be something special in three-node patterns that simplifies models on hypergraphs involving cuts down to a simple matrix case. Showing that this is true is relatively straightforward [2, 12], but we presently lack a clear appreciation of whether this is a simple artifact of the mathematics, or if one could employ some more general theory in new scenarios. Many of the most important challenges in network science and higher-order network science are matters of statistical or causal relevance. These matters are not yet standardized, and rigorous methods are required to assess significant findings in networks — although excellent research in the community offers a number of paths forward. Finally, a pressing need exists for efficient and rigorously justified algorithms that can accommodate and enable the possibilities of higher-order analysis, including the overriding challenge of optimizing the computation of higher-order quantities as problems get larger.


References
[1] Arrigo, F., Tudisco, F., & Higham, D.J. (2020). Beyond non-backtracking: Non-cycling network centrality measures. Proc. R. Soc. A, 476(2235), 20190653.
[2] Benson, A.R., Gleich, D.F., & Leskovec, J. (2016). Higher-order organization of complex networks. Science, 353(6295), 163-166.
[3] Benson, A.R., Gleich, D.F., & Lim, L.-H. (2017). The spacey random walk: A stochastic process for higher-order data. SIAM Rev., 59(2), 321-345.
[4] Carletti, T., Fanelli, D., & Nicoletti, S. (2020). Dynamical systems on hypergraphs. J. Phys. Complex., 1(3), 035006.
[5] Chierichetti, F., Kumar, R., Raghavan, P., & Sarlos, T. (2012). Are web users really markovian? In WWW '12: Proceedings of the 21st International Conference on World Wide Web (pp. 609-618). Lyon, France: Association for Computing Machinery.
[6] Fasino, D., & Tudisco, F. (2020). Ergodicity coefficients for higher-order stochastic processes. SIAM J. Math. Data Sci., 2(3), 740-769.
[7] Giusti, C., Ghrist, R., & Bassett, D.S. (2016). Two’s company, three (or more) is a simplex. J. Comput. Neurosci., 41(1), 1-14.
[8] Grilli, J., Barab´as, G., Michalska-Smith, M.J., & Allesina, S. (2017). Higher-order interactions stabilize dynamics in competitive network models. Nature, 548(7666), 210-213.
[9] Iacopini, I., Petri, G., Barrat, A., & Latora, V. (2019). Simplicial models of social contagion. Nat. Comm., 10, 2485.
[10] Lambiotte, R., Rosvall, M., & Scholtes, I. (2019). From networks to optimal higher-order models of complex systems. Nat. Phys., 15(4), 313-320.
[11] Landau, E. (1895). Zur relativen Wertbemessung der Turnierresultate. Deutsch. Wochenschach, 11, 366-369.
[12] Li, P., He, N., & Milenkovic, O. (2020). Quadratic decomposable submodular function minimization: Theory and practice. J. Mach. Learn. Res., 21(106), 1-49.
[13] Lim, L.-H. (2020). Hodge Laplacians on graphs. SIAM Rev., 62(3), 685-715.
[14] Lu, L., & Peng, X. (2011). High-ordered random walks and generalized Laplacians on hypergraphs. In A. Frieze, P. Horn, & P. Prałat (Eds.), Algorithms and Models for the Web Graph (pp. 14-25). Atlanta, GA: Springer.
[15] Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., & Alon, U. (2002). Network motifs: Simple building blocks of complex networks. Science, 298(5594), 824-827.
[16] Neuhäuser, L., Mellor, A., & Lambiotte, R. (2020). Multibody interactions and nonlinear consensus dynamics on networked systems. Phys. Rev. E, 101(3), 032310.
[17] Rosvall, M., Esquivel, A.V., Lancichinetti, A., West, J.D., & Lambiotte, R. (2014). Memory in network flows and its effects on spreading dynamics and community detection. Nat. Comm., 5, 4630.
[18] Schaub, M.T., Benson, A.R., Horn, P., Lippner, G., & Jadbabaie, A. (2020). Random walks on simplicial complexes and the normalized Hodge 1-Laplacian. SIAM Rev., 62(2), 353-391.
[19] Sylvester, J.J. (1878). On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, with three appendices. Amer. J. Math., 1(1), 64.
[20] Torres, L., Blevins, A.S., Bassett, D.S., & Eliassi- Rad, T. (2020). The why, how, and when of representations for complex systems. Preprint, arXiv:2006.02870

Austin R. Benson is an assistant professor of computer science at Cornell University, where he is also a field member of the Center for Applied Mathematics. David F. Gleich is the Jyoti and Aditya Mathur Associate Professor of Computer Science at Purdue University with a courtesy appointment in mathematics. He is an associate editor for SIAM Review and the SIAM Journal on Mathematics of Data Science. Desmond J. Higham is a professor of numerical analysis at the University of Edinburgh. He is a SIAM Fellow and editor-in-chief of SIAM Review.

blog comments powered by Disqus