Classical spectral graph theory is centered around the study of the quadratic forms of the graph Laplacian operator, through its structural relation to isoperimetric properties of the graph and his algorithmic connection with the heat diffusion process over the graph. In this talk, I will describe a generalization of this theory that focuses instead on bilinear forms of incidence operators and allows for more general structural results and novel algorithmic primitives. In particular, I will showcase a simple, efficiently computable nonlinear analogue of the heat diffusion process that allows us to detect sparse vertex-based separators and hypergraph separators. I will also describe its connection to the fastest-mixing markov chain over an unweighted undirected graph. This is joint work with Antares Chen and Erasmo Tani.
17/03/2022