  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
\emph{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
\emph{(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.
