Fourier-based and Rational Graph Filters for Spectral Processing
This work addresses the need for efficient and stable spectral processing methods in graph-based applications like computer vision and network analysis, representing an incremental improvement over existing polynomial filters.
The paper tackles the problem of graph processing in non-Euclidean domains by introducing novel Fourier-based and rational graph filters, which generalize polynomial filters and the Fourier transform, and proposes a spectrum-free approach for efficient evaluation. Results show that rational polynomials provide more accurate and numerically stable approximations of arbitrary graph filters compared to polynomials, with advantages including generality across input data and applications, and low computational cost and storage overhead.
Data are represented as graphs in a wide range of applications, such as Computer Vision (e.g., images) and Graphics (e.g., 3D meshes), network analysis (e.g., social networks), and bio-informatics (e.g., molecules). In this context, our overall goal is the definition of novel Fourier-based and graph filters induced by rational polynomials for graph processing, which generalise polynomial filters and the Fourier transform to non-Euclidean domains. For the efficient evaluation of discrete spectral Fourier-based and wavelet operators, we introduce a spectrum-free approach, which requires the solution of a small set of sparse, symmetric, well-conditioned linear systems and is oblivious of the evaluation of the Laplacian or kernel spectrum. Approximating arbitrary graph filters with rational polynomials provides a more accurate and numerically stable alternative with respect to polynomials. To achieve these goals, we also study the link between spectral operators, wavelets, and filtered convolution with integral operators induced by spectral kernels. According to our tests, main advantages of the proposed approach are (i) its generality with respect to the input data (e.g., graphs, 3D shapes), applications (e.g., signal reconstruction and smoothing, shape correspondence), and filters (e.g., polynomial, rational polynomial), and (ii) a spectrum-free computation with a generally low computational cost and storage overhead.