We investigate novel random graph embeddings that can be computed in expected
polynomial time and that are able to distinguish all non-isomorphic graphs in
expectation. Previous graph embeddings have limited expressiveness and either
cannot distinguish all graphs or cannot be computed efficiently for every
graph. To be able to approximate arbitrary functions on graphs, we are
interested in efficient alternatives that become arbitrarily expressive with
increasing resources. Our approach is based on Lov\'asz' characterisation of
graph isomorphism through an infinite dimensional vector of homomorphism
counts. Our empirical evaluation shows competitive results on several benchmark
graph learning tasks.

本文研究了新颖的随机图嵌入算法，能在预期的多项式时间内区分所有非同构图，并基于 Lovasz 的同态计数理论实现对任意图的函数逼近，结果在多个基准图学习任务上表现竞争力。

期望连通图表示与同态

Expectation-Complete Graph Representations with Homomorphisms

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.

本文提出了一种新的全局对齐图核算法，该算法利用几何节点嵌入和基于 Earth Mover's distance 的关联节点传输，得到的图嵌入称为 “随机图嵌入（RGE）”，可以通过定义在随机图上的分布自然地产生随机特征近似，实验结果表明 RGE 超越或匹配了十二个最先进的图分类算法。