The graph \(p\)-Laplacian eigenvalue problem

The \(p\)-Laplacian operator arises as a natural generalization of the Laplace operator (\(p = 2\)) when considering variational problems involving the \(p\)-norm of the gradient of an objective node function \(f\). The interest for these nonlinear operators is due to a surge of results, both numerical and theoretical, showing that using a suitable \(p\)-norm in place of the \(2\)-norm it is possible to achieve better results and avoid pathological situations. In particular, the spectrum of the graph \(p\)-Laplacian operator has tight relations with different topological invariants of the graph. For example, the family of the variational \(p\)-Laplacian eigenpairs, via the Cheeger inequalities, provides information about the clusters in the graph. This information is easily proved to be the more accurate the more \(p\) approaches \(1\). Furthermore, when \(p = 1\), we can characterize any \(1\)-Laplacian eigenpair in terms of the cut of some subgraph. Similar results hold for \(p = \infty\). Indeed, any \(\infty\)-eigenpair can be characterized in terms of distances between nodes and the variational \(\infty\)-eigenpairs can be related to the packing radii of the graph. Despite these interesting properties, the theoretical and numerical investigation of the nonlinear \(p\)-Laplacian eigenvalue problem presents many more difficulties with respect to the linear case \(p = 2\), and many problems are still open. In this seminar we aim to provide an overview about the \(p\)-Laplacian eigenvalue problem, pointing out the differences from the linear case and presenting some old and new results about the topological information encoded by the \(p\)-Laplacian eigenpairs.

Piero Deidda is research fellow at the Scuola Normale Superiore in Pisa (Italy) and has earned his PhD from the University of Padua (Italy).