A Broader Picture of Random-walk Based Graph Embedding
Graph embedding based on random-walks supports effective solutions for many graph-related downstream tasks. However, the abundance of embedding literature has made it increasingly difficult to compare existing methods and to identify opportunities to advance the state-of-the-art. Meanwhile, existing work has left several fundamental questions -- such as how embeddings capture different structural scales and how they should be applied for effective link prediction -- unanswered. This paper addresses these challenges with an analytical framework for random-walk based graph embedding that consists of three components: a random-walk process, a similarity function, and an embedding algorithm. Our framework not only categorizes many existing approaches but naturally motivates new ones. With it, we illustrate novel ways to incorporate embeddings at multiple scales to improve downstream task performance. We also show that embeddings based on autocovariance similarity, when paired with dot product ranking for link prediction, outperform state-of-the-art methods based on Pointwise Mutual Information similarity by up to 100%.
Code (1)
Tasks
Graph EmbeddingLink PredictionSimilar Papers 제목 키워드 기반
Residual2Vec: Debiasing graph embedding with random graphs
Graph embedding maps a graph into a convenient vector-space representation for graph analysis and machine learning applications. Many graph embedding methods hinge on a sampling of context nodes based on random walks. Ho…
Graph EmbeddingGraph Representation LearningLink PredictionRepresentation LearningInvestigating Extensions to Random Walk Based Graph Embedding
Graph embedding has recently gained momentum in the research community, in particular after the introduction of random walk and neural network based approaches. However, most of the embedding approaches focus on represen…
Graph EmbeddingLink PredictionNode ClassificationGlobalWalk: Learning Global-aware Node Embeddings via Biased Sampling
Popular node embedding methods such as DeepWalk follow the paradigm of performing random walks on the graph, and then requiring each node to be proximate to those appearing along with it. Though proved to be successful i…
Delving Into Deep Walkers: A Convergence Analysis of Random-Walk-Based Vertex Embeddings
Graph vertex embeddings based on random walks have become increasingly influential in recent years, showing good performance in several tasks as they efficiently transform a graph into a more computationally digestible f…
Node Embedding for Homophilous Graphs with ARGEW: Augmentation of Random walks by Graph Edge Weights
Representing nodes in a network as dense vectors node embeddings is important for understanding a given network and solving many downstream tasks. In particular, for weighted homophilous graphs where similar nodes are co…
Node Classification