Variational graph p-Laplacian eigendecomposition under p-orthogonality constraints

The p-Laplacian is a non-linear generalization of the Laplace operator. In the graph context, its eigenfunctions are used for data clustering, spectral graph theory, dimensionality reduction and other problems, as non-linearity better captures the underlying geometry of the data. We formulate the graph p-Laplacian nonlinear eigenproblem as an optimization problem under p-orthogonality constraints. The problem of computing multiple eigenpairs of the graph p-Laplacian is then approached incrementally by minimizing the graph Rayleigh quotient under nonlinear constraints. A simple reformulation allows us to take advantage of linear constraints. We propose two different optimization algorithms to solve the variational problem. The first is a projected gradient descent on manifold, and the second is an Alternate Direction Method of Multipliers which leverages the scaling invariance of the graph Rayleigh quotient to solve a constrained minimization under p-orthogonality constraints. We demonstrate the effectiveness and accuracy of the proposed algorithms and compare them in terms of efficiency.