A class of doubly stochastic shift operators for random graph signals and their boundedness

Abstract

A class of doubly stochastic graph shift operators (GSO) is proposed, which is shown to exhibit: (i) lower and upper L₂-boundedness for locally stationary random graph signals, (ii) L₂-isometry for i.i.d. random graph signals with the asymptotic increase in the incoming neighbourhood size of vertices, and (iii) preservation of the mean of any graph signal - all prerequisites for reliable graph neural networks. These properties are obtained through a statistical consistency analysis of the proposed graph shift operator, and by exploiting the dual role of the doubly stochastic GSO as a Markov (diffusion) matrix and as an unbiased expectation operator. For generality, we consider directed graphs which exhibit asymmetric connectivity matrices. The proposed approach is validated through an example on the estimation of a vector field.

Keywords: Boundedness analysis; Doubly stochastic matrix; Graph neural networks; Graph signal processing; Shift operator; Statistical consistency.