  Despite being very successful within the pattern recognition and machine
learning community, graph-based methods are often unusable because of the lack
of mathematical operations defined in graph domain. Graph embedding, which maps
graphs to a vectorial space, has been proposed as a way to tackle these
difficulties enabling the use of standard machine learning techniques. However,
it is well known that graph embedding functions usually suffer from the loss of
structural information. In this paper, we consider the hierarchical structure
of a graph as a way to mitigate this loss of information. The hierarchical
structure is constructed by topologically clustering the graph nodes, and
considering each cluster as a node in the upper hierarchical level. Once this
hierarchical structure is constructed, we consider several configurations to
define the mapping into a vector space given a classical graph embedding, in
particular, we propose to make use of the Stochastic Graphlet Embedding (SGE).
Broadly speaking, SGE produces a distribution of uniformly sampled low to high
order graphlets as a way to embed graphs into the vector space. In what
follows, the coarse-to-fine structure of a graph hierarchy and the statistics
fetched by the SGE complements each other and includes important structural
information with varied contexts. Altogether, these two techniques
substantially cope with the usual information loss involved in graph embedding
techniques, obtaining a more robust graph representation. This fact has been
corroborated through a detailed experimental evaluation on various benchmark
graph datasets, where we outperform the state-of-the-art methods.
