The DOI matches its Crossref record; 54 of the 54 references it cites were found in a registry or an index.
VERSE: Versatile Graph Embeddings from Similarity Measures
Open accessAbstract
Embedding a web-scale information network into a low-dimensional vector space facilitates tasks such as link prediction, classification, and visualization. Past research has addressed the problem of extracting such embeddings by adopting methods from words to graphs, without defining a clearly comprehensible graph-related objective. Yet, as we show, the objectives used in past works implicitly utilize similarity measures among graph nodes. In this paper, we carry the similarity orientation of previous works to its logical conclusion; we propose VERtex Similarity Embeddings (VERSE), a simple, versatile, and memory-efficient method that derives graph embeddings explicitly calibrated to preserve the distributions of a selected vertex-to-vertex similarity measure. VERSE learns such embeddings by training a single-layer neural network. While its default, scalable version does so via sampling similarity information, we also develop a variant using the full information per vertex. Our experimental study on standard benchmarks and real-world datasets demonstrates that VERSE, instantiated with diverse similarity measures, outperforms state-of-the-art methods in terms of precision and recall in major data mining tasks and supersedes them in time and space efficiency, while the scalable sampling-based variant achieves equally good result as the non-scalable full variant.
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
ImageNet classification with deep convolutional neural networks
Krizhevsky, A., Sutskever, I., & Hinton, G. E. (2017) · Communications of the ACM · doi:10.1145/3065386 · Cited by 112,155
Collective dynamics of ‘small-world’ networks
Watts, D. J., & Strogatz, S. H. (1998) · Nature · doi:10.1038/30918 · Cited by 43,060
Glove: Global Vectors for Word Representation
Pennington, J., Socher, R., & Manning, C. (2014) · Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.3115/v1/d14-1162 · Cited by 34,071
(2008) · Journal of Machine Learning Research · Cited by 33,051
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
Fast unfolding of communities in large networks
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E. (2008) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2008/10/p10008 · Cited by 21,424
The anatomy of a large-scale hypertextual Web search engine
Brin, S., & Page, L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00110-x · Cited by 16,004
Nonlinear Dimensionality Reduction by Locally Linear Embedding
Roweis, S. T., & Saul, L. K. (2000) · Science · doi:10.1126/science.290.5500.2323 · Cited by 14,965
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
Representation Learning: A Review and New Perspectives
Bengio, Y., Courville, A., & Vincent, P. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2013.50 · Cited by 13,001
(1999) · Cited by 12,854
Modularity and community structure in networks
Newman, M. E. J. (2006) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0601602103 · Cited by 12,256
(2016) · Cited by 11,679
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 7×
“It is visible that the nonlinear minimization of KL divergence between distributions preserves most of the information in the original matrix, while the linear SVD-based reconstruction fails to differentiate some nodes.”
BackgroundMethodInfluentialDeepWalk: 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
(2007) · doi:10.5555/1283383.1283494 · Cited by 7,364
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 4×
“HOPE is the first to support diverse similarity measures; however, it still requires the entire graph matrix as input and views the problem as one of linear dimensionality reduction rather than as one of nonlinear learning.”
BackgroundMethodInfluentialAn Information Flow Model for Conflict and Fission in Small Groups
Zachary, W. W. (1977) · Journal of Anthropological Research · doi:10.1086/jar.33.4.3629752 · Cited by 4,704
Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering
Belkin, M., & Niyogi, P. (2002) · Advances in Neural Information Processing Systems 14 · doi:10.7551/mitpress/1120.003.0080 · Cited by 4,412
A New Status Index Derived from Sociometric Analysis
Katz, L. (1953) · Psychometrika · doi:10.1007/bf02289026 · Cited by 3,866
A Neural Probabilistic Language Model
Bengio, Y., Ducharme, R., Vincent, P., Jauvin, C., Jaz, K., Hofmann, T., Poggio, T., & Shawe-Taylor, J. S. (2000) · Cited by 3,479
Graph Embedding and Extensions: A General Framework for Dimensionality Reduction
Yan, S., Xu, D., Zhang, B., Zhang, H.-J., Yang, Q., & Lin, S. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.250598 · Cited by 3,031
Noise-contrastive estimation: A new estimation principle for unnormalized statistical models
Gutmann, M. U., & Hyvärinen, A. (2010) · Edinburgh Research Explorer (University of Edinburgh) · Cited by 2,992
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
Link prediction in complex networks: A survey
Lü, L., & Zhou, T. (2011) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2010.11.027 · Cited by 2,819
Multi-Label Classification: An Overview
Tsoumakas, G., & Katakis, I. (2007) · International Journal of Data Warehousing and Mining · doi:10.4018/jdwm.2007070101 · Cited by 2,508
SimRank: a measure of structural-context similarity
Jeh, G., & Widom, J. (2002) · Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/775047.775126 · Cited by 1,925
GraRep: Learning Graph Representations with Global Structural Information
Cao, S., Lu, W., & Xu, Q. (2015) · Proceedings of the 24th ACM International on Conference on Information and Knowledge Management · doi:10.1145/2806416.2806512 · Cited by 1,571
Nonlinear Dimensionality Reduction
(2007) · Information Science and Statistics · doi:10.1007/978-0-387-39351-3 · Cited by 1,517
Defining and evaluating network communities based on ground-truth
Yang, J., & Leskovec, J. (2015) · Knowledge and Information Systems · doi:10.1007/s10115-013-0693-z · Cited by 1,411
Asymmetric Transitivity Preserving Graph Embedding
Ou, M., Cui, P., Pei, J., Zhang, Z., & Zhu, W. (2016) · Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2939672.2939751 · Cited by 1,248
Cooperative Game Theory Approaches for Network Partitioning
Avrachenkov, K. E., Kondratev, A. Y., & Mazalov, V. V. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-62389-4_49 · Cited by 1,073
Deep Neural Networks for Learning Graph Representations
Cao, S., Lu, W., & Xu, Q. (2016) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v30i1.10179 · Cited by 1,014
struc2vec: Learning Node Representations from Structural Identity
Ribeiro, L. F. R., Saverese, P. H. P., & Figueiredo, D. R. (2017) · Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/3097983.3098061 · Cited by 1,011
Relational learning via latent social dimensions
Tang, L., & Liu, H. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557109 · Cited by 799 · cited 2×
“In its learning core, VERSE stands between deep learning approaches [12, 48] on the one hand and the direct decomposition of the similarity matrix [11, 42] on the other hand.”
BackgroundMethodNew perspectives and methods in link prediction
Lichtenwalter, R. N., Lussier, J. T., & Chawla, N. V. (2010) · Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1835804.1835837 · Cited by 664
Distributed large-scale natural graph factorization
Ahmed, A., Shervashidze, N., Narayanamurthy, S., Josifovski, V., & Smola, A. J. (2013) · Proceedings of the 22nd international conference on World Wide Web · doi:10.1145/2488388.2488393 · Cited by 648
Gutmann, M. U., & Hyvärinen, A. (2012) · Edinburgh Research Explorer (University of Edinburgh) · doi:10.5555/2503308.2188396 · Cited by 581
oddball: Spotting Anomalies in Weighted Graphs
Akoglu, L., McGlohon, M., & Faloutsos, C. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-13672-6_40 · Cited by 533
Label Informed Attributed Network Embedding
Huang, X., Li, J., & Hu, X. (2017) · Proceedings of the Tenth ACM International Conference on Web Search and Data Mining · doi:10.1145/3018661.3018667 · Cited by 487
LIBLINEAR: A Library for Large Linear Classification
FanRong-En, ChangKai-Wei, HsiehCho-Jui, WangXiang-Rui, & LinChih-Jen (2008) · Journal of Machine Learning Research · doi:10.5555/1390681.1442794 · Cited by 328
A Fast and Simple Algorithm for Training Neural Probabilistic Language Models
Mnih, A., & Teh, Y. W. (2012) · arXiv · doi:10.48550/arxiv.1206.6426 · Cited by 315
Max-margin deepwalk: discriminative learning of network representation
Tu, C., Zhang, W., Liu, Z., & Sun, M. (2016) · International Joint Conference on Artificial Intelligence · Cited by 293
Scalable learning of collective behavior based on sparse social dimensions
Tang, L., & Liu, H. (2009) · Proceedings of the 18th ACM conference on Information and knowledge management · doi:10.1145/1645953.1646094 · Cited by 233 · cited 1×
“Besides, the hyperparameter-supervised hsVERSE variant outruns Node2vec on all datasets.”
MethodFocused clustering and outlier detection in large attributed graphs
Perozzi, B., Akoglu, L., Iglesias Sánchez, P., & Müller, E. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623682 · Cited by 228
Self-citationIt's who you know: graph mining using recursive structural features
Henderson, K., Gallagher, B., Li, L., Akoglu, L., Eliassi-Rad, T., Tong, H., & Faloutsos, C. (2011) · Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2020408.2020512 · Cited by 223 · cited 2×
“Traditional feature learning learns features by compressing representations such as the Laplacian or adjacency matrix to a low-dimensional space.”
BackgroundUnsupervised feature selection for linked social media data
Tang, J., & Liu, H. (2012) · Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2339530.2339673 · Cited by 195
subgraph2vec: Learning Distributed Representations of Rooted Sub-graphs from Large GraphsPreprint
Narayanan, A. S., Chandramohan, M., Chen, L., Liu, Y., & Saminathan, S. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1606.08928 · Cited by 188
Feature Selection with Linked Data in Social Media
Tang, J., & Liu, H. (2012) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972825.11 · Cited by 138
Attributed Signed Network Embedding
Wang, S., Aggarwal, C. C., Tang, J., & Liu, H. (2017) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/3132847.3132905 · Cited by 125
User Profile Preserving Social Network Embedding
Zhang, D., Yin, J., Xingquan Zhu, A., & Chengqi Zhang, B. (2017) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2017/472 · Cited by 104
Learning Edge Representations via Low-Rank Asymmetric Projections
Abu-El-Haija, S., Perozzi, B., & Al-Rfou, R. (2017) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/3132847.3132959 · Cited by 95
Hu, J., Cheng, R. C. K., Huang, Z., Fang, Y., & Luo, S. (2017) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/3132847.3132885 · Cited by 66
An experimental analysis of Noise-Contrastive Estimation: the noise distribution matters
Labeau, M., & Allauzen, A. (2017) · Conference of the European Chapter of the Association for Computational Linguistics · doi:10.18653/v1/e17-2003 · Cited by 7
Cited by
Contrastive Multi-View Representation Learning on Graphs
Hassani, K., & Khasahmadi, A. H. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.05582 · Cited by 423
Revisiting User Mobility and Social Relationships in LBSNs: A Hypergraph Embedding Approach
Yang, D., Qu, B., Yang, J., & Cudre-Mauroux, P. (2019) · The World Wide Web Conference · doi:10.1145/3308558.3313635 · Cited by 299
Metadata
- Authors
- Tsitsulin, A., Mottin, D., Karras, P., & Müller, E.
- Venue
- Proceedings of the 2018 World Wide Web Conference on World Wide Web - WWW '18
- Publisher
- ACM Press
- Published
- 2018
- Pages
- 539-548
- OpenAlex
- W2788614083
- Cited by
- 277
- References
- 54
- FWCI
- 15.40
- Type
- conference paper
- Language
- en
- Open access
- gold
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.