Search papers, labs, and topics across Lattice.
The paper introduces a novel randomized spectral node embedding method to approximate graph kernels, addressing the computational challenges of direct kernel computation on large graphs. By leveraging random wavelet features, the method constructs low-dimensional node embeddings whose dot products efficiently estimate a low-rank approximation of a target graph kernel. Theoretical and empirical evaluations demonstrate that the proposed embeddings achieve more accurate kernel approximations, especially for spectrally localized kernels, compared to existing approaches.
Random wavelet features offer a surprisingly effective and scalable way to approximate graph kernels, outperforming existing methods in accuracy, particularly for spectrally localized kernels.
Node embeddings map graph vertices into low-dimensional Euclidean spaces while preserving structural information. They are central to tasks such as node classification, link prediction, and signal reconstruction. A key goal is to design node embeddings whose dot products capture meaningful notions of node similarity induced by the graph. Graph kernels offer a principled way to define such similarities, but their direct computation is often prohibitive for large networks. Inspired by random feature methods for kernel approximation in Euclidean spaces, we introduce randomized spectral node embeddings whose dot products estimate a low-rank approximation of any specific graph kernel. We provide theoretical and empirical results showing that our embeddings achieve more accurate kernel approximations than existing methods, particularly for spectrally localized kernels. These results demonstrate the effectiveness of randomized spectral constructions for scalable and principled graph representation learning.
