# Scalable Global Alignment Graph Kernel Using Random Features: From Node Embedding to Graph Embedding

arXiv: https://arxiv.org/abs/1911.11119 · HTML: https://mlsanity.com/paper/1911.11119/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Nov 2019.

## Built on by (most cited first, 8 of 8)

- [Taming graph kernels with random features](https://mlsanity.com/paper/2305.00156/) (2023)
- [Distance-wise Prototypical Graph Neural Network in Node Imbalance Classification](https://mlsanity.com/paper/2110.12035/) (2021)
- [Expectation-Complete Graph Representations with Homomorphisms](https://mlsanity.com/paper/2306.05838/) (2023)
- [Quasi-Monte Carlo Graph Random Features](https://mlsanity.com/paper/2305.12470/) (2023)
- [Sublinear Time Approximation of Text Similarity Matrices](https://mlsanity.com/paper/2112.09631/) (2021)
- [Computationally-efficient Graph Modeling with Refined Graph Random Features](https://mlsanity.com/paper/2510.07716/) (2025)
- [Probability Passing for Graph Neural Networks: Graph Structure and Representations Joint Learning](https://mlsanity.com/paper/2407.10688/) (2024)
- [Lipschitz bounds for integral kernels](https://mlsanity.com/paper/2604.02887/) (2026)

## Abstract (arXiv)

Graph kernels are widely used for measuring the similarity between graphs. Many existing graph kernels, which focus on local patterns within graphs rather than their global properties, suffer from significant structure information loss when representing graphs. Some recent global graph kernels, which utilizes the alignment of geometric node embeddings of graphs, yield state-of-the-art performance. However, these graph kernels are not necessarily positive-definite. More importantly, computing the graph kernel matrix will have at least quadratic time complexity in terms of the number and the size of the graphs. In this paper, we propose a new family of global alignment graph kernels, which take into account the global properties of graphs by using geometric node embeddings and an associated node transportation based on earth mover's distance. Compared to existing global kernels, the proposed kernel is positive-definite. Our graph kernel is obtained by defining a distribution over random graphs, which can naturally yield random feature approximations. The random feature approximations lead to our graph embeddings, which is named as "random graph embeddings" (RGE). In particular, RGE is shown to achieve (quasi-)linear scalability with respect to the number and the size of the graphs. The experimental results on nine benchmark datasets demonstrate that RGE outperforms or matches twelve state-of-the-art graph classification algorithms.