cicyt UNIZAR
Full-text links:

Download:

Current browse context:

cs.SI

Change to browse by:

References & Citations

DBLP - CS Bibliography

Bookmark

(what is this?)
CiteULike logo BibSonomy logo Mendeley logo del.icio.us logo Digg logo Reddit logo ScienceWISE logo

Computer Science > Social and Information Networks

Title: VERSE: Versatile Graph Embeddings from Similarity Measures

Abstract: 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 results as the non-scalable full variant.
Comments: In WWW 2018: The Web Conference. 10 pages, 5 figures
Subjects: Social and Information Networks (cs.SI); Learning (cs.LG)
DOI: 10.1145/3178876.3186120
Cite as: arXiv:1803.04742 [cs.SI]
  (or arXiv:1803.04742v1 [cs.SI] for this version)

Submission history

From: Anton Tsitsulin [view email]
[v1] Tue, 13 Mar 2018 12:05:58 GMT (188kb,D)