Power Spectrum Signatures of Graphs
This work provides a novel tool for machine learning tasks involving graphs and point clouds, though it appears incremental as it builds on existing Laplacian-based signatures.
The authors tackled the problem of creating a point signature for graphs that is invariant under automorphisms and stable under perturbations, resulting in the power spectrum signature which is derived from the graph Fourier transform and applied to tasks like characterizing geometry and symmetries in point cloud data and graph regression.
Point signatures based on the Laplacian operators on graphs, point clouds, and manifolds have become popular tools in machine learning for graphs, clustering, and shape analysis. In this work, we propose a novel point signature, the power spectrum signature, a measure on $\mathbb{R}$ defined as the squared graph Fourier transform of a graph signal. Unlike eigenvectors of the Laplacian from which it is derived, the power spectrum signature is invariant under graph automorphisms. We show that the power spectrum signature is stable under perturbations of the input graph with respect to the Wasserstein metric. We focus on the signature applied to classes of indicator functions, and its applications to generating descriptive features for vertices of graphs. To demonstrate the practical value of our signature, we showcase several applications in characterizing geometry and symmetries in point cloud data, and graph regression problems.