Random-Walk Laplacian for Frequency Analysis in Periodic Graphs

Abstract

This paper presents the benefits of using the random-walk normalized Laplacian matrix as a graph-shift operator and defines the frequencies of a graph by the eigenvalues of this matrix. A criterion to order these frequencies is proposed based on the Euclidean distance between a graph signal and its shifted version with the transition matrix as shift operator. Further, the frequencies of a periodic graph built through the repeated concatenation of a basic graph are studied. We show that when a graph is replicated, the graph frequency domain is interpolated by an upsampling factor equal to the number of replicas of the basic graph, similarly to the effect of zero-padding in digital signal processing.

Keywords

• graph Fourier transform
• frequency ordering
• random-walk Laplacian
• periodic graph