In graph embeddings algorithms (GEA), each vertex is translated to a vector in real space. Graph embedding problems can handle both static and dynamic graphs, where vertices and edges can appear and disappear. They have multiple applications, including vertex classification, link prediction, and visualization. The cost of much current leading static and dynamic embedding algorithms (GEA and DGEA) can be prohibitive in large graphs, and they are often offline, i.e. they cannot handle streamed online information. Moreover, for dynamic graphs, they do not ensure a slow change in the projection of the vertices.

In this work, we first treat static graphs problem and propose a fast online GEA to overcome these limitations. The accuracy of existing embedding, as defined by auxiliary tests, is maximal for a core of high degree vertices. We propose to embed only this core using existing methods, and then update online the remaining vertices, based on the position of their already embedded neighbors. The position of each new vertex is a combination of its first and second neighbors' positions. We present two versions of this heuristic: a) a weighted combination (OGRE) and b) a directed regression (DOGRE). We show that OGRE is much faster than the existing GEA and is applicable to very large graphs. OGRE can be combined with a Graph Neural Network (GNN) seed to obtain higher vertex classification accuracy than the current state of the art in very large graphs. OGREs' link prediction accuracy is comparable with state-of-the-art methods.

Next, we expand the OGRE heuristic to handle dynamic graphs. We propose FODGE, a novel DGEA to gradually shift the projection of modified vertices. FODGE optimizes CPU and memory efficacy by separating the projection of the graph densest K-core and its periphery. FODGE then smoothly updates the projection of the remaining vertices, through an iterative local update rule. As such it can be applied to extremely large dynamic graphs.

We show that FODGE obtains a better performance in an auxiliary task of link prediction and ensures a limited difference in vertex positions in the following time points. FODGE is highly modular and can be combined with any static projection, including GNNs, and has a few hyperparameters to tune.