Laplacians for structure recovery on directed and higher-order graphs

Abstract

The spectral properties of Laplacian matrices offer valuable insights into the structure of graphs. One significant application is the embedding of nodes into a low-dimensional Euclidean space using the eigenvectors of a suitable Laplacian matrix, enabling the recovery of the underlying connection pattern. Such embedding proves relevant for various subsequent learning tasks, including node reordering, clustering, and visualization. Despite extensive research on undirected graph Laplacians, there remains a gap in analyzing more complex graph structures.

This includes situations where relationships are asymmetrical and represented by directed edges, as well as scenarios involving interactions among more than two agents, effectively captured using hypergraphs or simplicial complexes. To address this research gap, we investigate mathematical frameworks utilizing graph Laplacians for directed networks, hypergraphs, and directed simplicial complexes. For directed graphs, we examine two existing Laplacian matrices associated with periodic and linear structures and developed corresponding generative models. Specifically, we establish and exploit connections between node reordering techniques, achieved through minimizing an objective function, and maximizing the likelihood of a random graph model. Leveraging this random graph framework, we compare the likelihood of each structure. Numerical experiments are conducted using synthetic graphs and graphs from social sciences, biology, and ecology. Furthermore, we extend this framework to hypergraphs and demonstrate its efficacy in quantifying structure strength, performing clustering, and predicting hyperedges on synthetic hypergraphs and social networks. Additionally, we define and analyze a new first-order Magnetic Hodge Laplacian for directed simplicial complexes, capturing directional flows on triangles. Through the analysis of triangle and torus examples, we showcase its ability to discover direction-related patterns.