Commuting projections on graphs

Motivated by the increasing importance of large-scale networks typically modeled by graphs, this paper is concerned with the development of mathematical tools for solving problems associated with the popular graph Laplacian. We exploit its mixed formulation based on its natural factorization as product of two operators. The goal is to construct a coarse version of the mixed graph Laplacian operator with the purpose to construct two-level, and by recursion, a multilevel hierarchy of graphs and associated operators. In many situations in practice, having a coarse (i.e., reduced dimension) model that maintains some inherent features of the original large-scale graph and respective graph Laplacian offers potential to develop efficient algorithms to analyze the underlined network modeled by this large-scale graph. One possible application of such a hierarchy is to develop multilevel methods that have the potential to be of optimal complexity. In this paper, we consider general (connected) graphs and function spaces defined on its edges and its vertices. These two spaces are related by a discrete gradient operator, 'Grad' and its adjoint, '-Div', referred to as (negative) discrete divergence. We also consider a coarse graph obtained by aggregation of vertices of the original one. Then, a coarse vertex space is identified with the subspace of piecewise constant functions over the aggregates. We consider the ℓ₂-projection Q_H onto the space of these piecewise constants. In the present paper, our main result is the construction of a projection π_H from the original edge-space onto a properly constructed coarse edge-space associated with the edges of the coarse graph. The projections π_H and Q_H commute with the discrete divergence operator, that is, we have Div π_H=Q_H div. The respective pair of coarse edge-space and coarse vertex-space offer the potential to construct two-level, and by recursion, multilevel methods for the mixed formulation of the graph Laplacian, which utilizes the discrete divergence operator. The performance of one two-level method with overlapping Schwarz smoothing and correction based on the constructed coarse spaces for solving such mixed graph Laplacian systems is illustrated on a number of graph examples.