# Space-Invariant Projection in Streaming Network Embedding

arXiv: https://arxiv.org/abs/2303.06293 · HTML: https://mlsanity.com/paper/2303.06293/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 76 references that are in the map.
- First posted on arXiv 11 Mar 2023.

## Builds on (most cited first, 29 of 29)

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [SimplE Embedding for Link Prediction in Knowledge Graphs](https://mlsanity.com/paper/1802.04868/) (2018)
- [DynGEM: Deep Embedding Method for Dynamic Graphs](https://mlsanity.com/paper/1805.11273/) (2018)
- [PTE: Predictive Text Embedding through Large-scale Heterogeneous Text Networks](https://mlsanity.com/paper/1508.00200/) (2015)
- [dyngraph2vec: Capturing Network Dynamics using Dynamic Graph Representation Learning](https://mlsanity.com/paper/1809.02657/) (2018)
- [Knowledge Graph Embedding for Link Prediction: A Comparative Analysis](https://mlsanity.com/paper/2002.00819/) (2020)
- [Streaming Graph Neural Networks via Continual Learning](https://mlsanity.com/paper/2009.10951/) (2020)
- [A Survey on Embedding Dynamic Graphs](https://mlsanity.com/paper/2101.01229/) (2021)
- [Dynamic Network Embedding Survey](https://mlsanity.com/paper/2103.15447/) (2021)
- [Attributed Network Embedding for Learning in a Dynamic Environment](https://mlsanity.com/paper/1706.01860/) (2017)
- [dynnode2vec: Scalable Dynamic Network Embedding](https://mlsanity.com/paper/1812.02356/) (2018)
- [Billion-scale Network Embedding with Iterative Random Projection](https://mlsanity.com/paper/1805.02396/) (2018)
- [Scalable Link Prediction in Dynamic Networks via Non-Negative Matrix Factorization](https://mlsanity.com/paper/1411.3675/) (2014)
- [TIMERS: Error-Bounded SVD Restart on Dynamic Networks](https://mlsanity.com/paper/1711.09541/) (2017)
- [Network Representation Learning: From Preprocessing, Feature Extraction to Node Embedding](https://mlsanity.com/paper/2110.07582/) (2021)
- [SVD-GCN: A Simplified Graph Convolution Paradigm for Recommendation](https://mlsanity.com/paper/2208.12689/) (2022)
- [Efficient Representation Learning Using Random Walks for Dynamic Graphs](https://mlsanity.com/paper/1901.01346/) (2019)
- [Robust Knowledge Adaptation for Dynamic Graph Neural Networks](https://mlsanity.com/paper/2207.10839/) (2022)
- [Out-of-sample extension of graph adjacency spectral embedding](https://mlsanity.com/paper/1802.06307/) (2018)
- [GloDyNE: Global Topology Preserving Dynamic Network Embedding](https://mlsanity.com/paper/2008.01935/) (2020)
- [Time-aware Graph Embedding: A temporal smoothness and task-oriented approach](https://mlsanity.com/paper/2007.11164/) (2020)
- [Dynamic Network Embedding via Incremental Skip-gram with Negative Sampling](https://mlsanity.com/paper/1906.03586/) (2019)
- [Neural graph embeddings as explicit low-rank matrix factorization for link prediction](https://mlsanity.com/paper/2011.09907/) (2020)
- [A Semi-Supervised and Inductive Embedding Model for Churn Prediction of Large-Scale Mobile Games](https://mlsanity.com/paper/1808.06573/) (2018)

## Abstract (arXiv)

Newly arriving nodes in dynamics networks would gradually make the node embedding space drifted and the retraining of node embedding and downstream models indispensable. An exact threshold size of these new nodes, below which the node embedding space will be predicatively maintained, however, is rarely considered in either theory or experiment. From the view of matrix perturbation theory, a threshold of the maximum number of new nodes that keep the node embedding space approximately equivalent is analytically provided and empirically validated. It is therefore theoretically guaranteed that as the size of newly arriving nodes is below this threshold, embeddings of these new nodes can be quickly derived from embeddings of original nodes. A generation framework, Space-Invariant Projection (SIP), is accordingly proposed to enables arbitrary static MF-based embedding schemes to embed new nodes in dynamics networks fast. The time complexity of SIP is linear with the network size. By combining SIP with four state-of-the-art MF-based schemes, we show that SIP exhibits not only wide adaptability but also strong empirical performance in terms of efficiency and efficacy on the node classification task in three real datasets.