Abstract
Graphs that evolve through edge arrivals, deletions, and node churn are increasingly common in transactional, communication, and interaction logs, yet many embedding pipelines still assume that the full graph is available and stationary. Streaming settings introduce additional constraints: updates must be processed with limited memory, the representation should remain temporally stable to preserve downstream semantics, and local updates should not cause inconsistent drift across groups of nodes that behave as coherent communities. This paper develops a streaming graph embedding method that couples temporal regularization with an explicit cluster-wide consistency mechanism. The method maintains node embeddings under a continuously arriving stream of edges by optimizing a reconstruction objective augmented with a temporal smoothness term that penalizes abrupt representation changes across successive time windows. To mitigate representation fragmentation, a cluster-level latent structure is maintained online; embeddings are encouraged to remain consistent with evolving cluster centroids, and centroid dynamics are themselves regularized to avoid instability. The resulting objective admits efficient incremental optimization using stochastic updates and lightweight cluster maintenance, including principled handling of node arrivals and disappearances. The approach is described in a unified formulation that supports both directed and undirected graphs, accommodates negative sampling for scalability, and provides explicit controls for forgetting and adaptation. Analytical discussion focuses on stability, sensitivity to nonstationarity, and computational complexity under realistic streaming constraints, alongside a detailed treatment of practical design choices.