Graph-based methods are known to be successful for pattern description and comparison purpose. However, a lot of mathematical tools are unavailable in graph domain, thus restricting the generic graph-based techniques to be applicable within the machine learning framework. A way to tackle this problem is graph embedding into high dimensional space in either an explicit or implicit manner. In this paper, we propose high order stochastic graphlet embedding (SGE) that explicitly embed a graph into a real vector space. Our main contribution includes a new stochastic search procedure that allows one to efficiently parse a given graph and extract or sample unlimitedly high order graphlets. We consider these graphlets with increasing size in order to model local features, as well as, their complex interactions. We also introduce or design graph hash functions with very low probability of collision to hash those sampled graphlets for partitioning them into sets of isomorphic ones and measure their distribution in large graph collections, which results in accurate graph descriptions. When combined with support vector machines, these high order graphlet-based descriptions have positive impact on the performance of graph-based pattern comparison and classification as corroborated through experiments on different standard benchmark databases.

本文提出了一种新的高阶随机图嵌入方法（SGE），主要通过一种新的随机搜索过程来提取/采样无限高阶图小区域，并将其分布映射到一个给定的图，然后结合最大间隔分类器，能够对数据进行图像识别，并在标准基准数据库上得到了积极的影响。

随机图集嵌入