Improving embedding of graphs with missing data by soft manifolds
Andrea Marinoni Pietro Lio' Alessandro Barp Christian Jutten Mark Girolami
Embedding graphs in continous spaces is a key factor in designing and
developing algorithms for automatic information extraction to be applied in
diverse tasks (e.g., learning, inferring, predicting). The reliability of graph
embeddings directly depends on how much the geometry of the continuous space
matches the graph structure. Manifolds are mathematical structure that can
enable to incorporate in their topological spaces the graph characteristics,
and in particular nodes distances. State-of-the-art of manifold-based graph
embedding algorithms take advantage of the assumption that the projection on a
tangential space of each point in the manifold (corresponding to a node in the
graph) would locally resemble a Euclidean space. Although this condition helps
in achieving efficient analytical solutions to the embedding problem, it does
not represent an adequate set-up to work with modern real life graphs, that are
characterized by weighted connections across nodes often computed over sparse
datasets with missing records. In this work, we introduce a new class of
manifold, named soft manifold, that can solve this situation. In particular,
soft manifolds are mathematical structures with spherical symmetry where the
tangent spaces to each point are hypocycloids whose shape is defined according
to the velocity of information propagation across the data points. Using soft
manifolds for graph embedding, we can provide continuous spaces to pursue any
task in data analysis over complex datasets. Experimental results on
reconstruction tasks on synthetic and real datasets show how the proposed
approach enable more accurate and reliable characterization of graphs in
continuous spaces with respect to the state-of-the-art.