word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data
Open accessThe DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index.
Abstract
Vector representations of graphs and relational structures, whether hand-crafted feature vectors or learned representations, enable us to apply standard data analysis and machine learning techniques to the structures. A wide range of methods for generating such embeddings have been studied in the machine learning and knowledge representation literature. However, vector embeddings have received relatively little attention from a theoretical point of view. Starting with a survey of embedding techniques that have been used in practice, in this paper we propose two theoretical approaches that we see as central for understanding the foundations of vector embeddings. We draw connections between the various approaches and suggest directions for future research.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Hochreiter, S., & Schmidhuber, J. (1997) · Neural Computation · doi:10.1162/neco.1997.9.8.1735 · Cited by 102,318
Cortes, C., & Vapnik, V. (1995) · Machine Learning · doi:10.1007/bf00994018 · Cited by 59,421
Semi-supervised classification with graph convolutional networks
Kipf, T. N., & Welling, M. (2016) · arXiv · doi:10.48550/arxiv.1609.02907 · Cited by 24,853
Distributed Representations of Words and Phrases and their Compositionality
Mikolov, T., Sutskever, I., Chen, K., Corrado, G., & Dean, J. (2013) · arXiv · doi:10.48550/arxiv.1310.4546 · Cited by 24,533
A Global Geometric Framework for Nonlinear Dimensionality Reduction
Tenenbaum, J. B., Silva, V. D., & Langford, J. C. (2000) · Science · doi:10.1126/science.290.5500.2319 · Cited by 13,585
A Comprehensive Survey on Graph Neural Networks
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. S. (2021) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2020.2978386 · Cited by 11,000
node2vec: Scalable Feature Learning for Networks
Grover, A., & Leskovec, J. (2016) · Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2939672.2939754 · Cited by 10,926 · cited 2×
“ree node embeddings of a graph using (a) singular value decomposition of adjacency matrix, (b) singular value decomposition of the similarity matrix with entries S vw = exp( 2dist(v;w)), (c) node2vec [48] kXX> Sk F with respect to the Frobenius norm kk F (or any other matrix norm, see Section 5). In the basic versi…”
BackgroundMethodInductive Representation Learning on Large Graphs
Hamilton, W. L., Ying, R., & Leskovec, J. (2017) · arXiv · doi:10.48550/arxiv.1706.02216 · Cited by 10,639
DeepWalk: online learning of social representations
Perozzi, B., Al-Rfou, R., & Skiena, S. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623732 · Cited by 10,123 · cited 1×
“These ideas also inspired new approaches to node embeddings like DeepWalk [87] and node2vec [48] based on taking short random walks in a graph and interpreting the sequence of nodes seen on such random walks as if they were words appearing together in a sentence.”
BackgroundThe graph neural network model
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., & Monfardini, G. (2009) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2008.2005605 · Cited by 9,582 · cited 1×
“al networks (GNNs) are a deep learning framework for graphs that avoids both of these diculties, albeit at the price of limited expressiveness (see Section 3). Early forms of GNNs were introduced in [90, 36]; the version we present here is based on [58, 49, 88]. Intuitively, a GNN model can be thought of as a message…”
Modeling Relational Data with Graph Convolutional Networks
Schlichtkrull, M., Kipf, T. N., Bloem, P., van den Berg, R., Titov, I., & Welling, M. (2018) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-93417-4_38 · Cited by 5,570
LINE: Large-scale Information Network Embedding
Tang, J., Qu, M., Wang, M., Zhang, M., Yan, J., & Mei, Q. (2015) · Proceedings of the 24th International Conference on World Wide Web · doi:10.1145/2736277.2741093 · Cited by 5,416 · cited 1×
“More recent related approaches are [1, 25, 85, 97].”
Understanding Machine Learning: From Theory to Algorithms
Shalev-Shwartz, S., & Ben-David, S. (2014) · doi:10.1017/cbo9781107298019 · Cited by 3,115
Structural Deep Network Embedding
Wang, D., Cui, P., & Zhu, W. (2016) · Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2939672.2939753 · Cited by 2,845
Knowledge Graph Embedding: A Survey of Approaches and Applications
Wang, Q., Mao, Z., Wang, B., & Guo, L. (2017) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2017.2754499 · Cited by 2,654 · cited 1×
“More thorough recent surveys are [50] (on node embeddings), [104] (on graph neural networks), [102] (on knowledge graph embeddings), and [62] (on graph kernels).”
BackgroundAdversarially Regularized Graph Autoencoder for Graph Embedding
Pan, S., Hu, R., Long, G., Jiang, J., Yao, L., & Zhang, C. (2018) · Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2018/362 · Cited by 929
Gallicchio, C., & Micheli, A. (2010) · The 2010 International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn.2010.5596796 · Cited by 210 · cited 1×
“al networks (GNNs) are a deep learning framework for graphs that avoids both of these diculties, albeit at the price of limited expressiveness (see Section 3). Early forms of GNNs were introduced in [90, 36]; the version we present here is based on [58, 49, 88]. Intuitively, a GNN model can be thought of as a message…”
Chen, T., Wang, Z., Li, L., Li, D., Li, Z., Chang, X., Bian, P., Liang, G., Wang, Q., & Xie, T. (2025) · Schloss Dagstuhl – Leibniz-Zentrum für Informatik · doi:10.4230/lipics.ecoop.2025.6
Cited by
(2021) · doi:10.1145/3448016.3457550 · Cited by 416
“In particular, a recent popular approach in recommender systems is called vector embedding that converts an item to a feature vector (such as item2vec [11], word2vec [52], doc2vec [37], graph2vec [26]) and provides recommendations via finding similar vectors [13, 15, 25, 51].”
BackgroundBig graphs: challenges and opportunities
Fan, W. (2022) · Proceedings of the VLDB Endowment · doi:10.14778/3554821.3554899 · Cited by 19
Metadata
- Authors
- Grohe, M.
- Venue
- Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
- Publisher
- ACM
- Published
- 2020-06-14
- Pages
- 1-16
- OpenAlex
- W3013030064
- Cited by
- 176
- References
- 18
- FWCI
- 8.77
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.