Built independently by an author, for readers. Read the story and support ChapterPal
ChapterPal Logo
Log inSign up

keyword

GraRep

GraRep is a graph representation learning algorithm that maps the vertices of a weighted graph into low-dimensional continuous vector spaces while preserving both local and global network structures. It achieves this by modeling multiple orders of proximity through k-step transition probability matrices, capturing relationships between nodes across varying path distances. For each step order, the algorithm applies matrix factorization via singular value decomposition to a shifted log-probability transition matrix derived from a negative sampling objective. By independently deriving embeddings for each transition order and concatenating them into a unified vector, GraRep preserves high-order structural information across the entire graph, yielding dense node features suitable for downstream machine learning tasks such as node classification, clustering, and network visualization.

1 item

GraRep: Learning Graph Representations with Global Structural Information

GraRep: Learning Graph Representations with Global Structural Information

Shaosheng Cao, Wei Lu, Qiongkai Xu

OrganizationsAustralian National UniversityIBMSingapore University of Technology and DesignXidian University

Why you should read this

Proposes GraRep, a graph representation learning model that captures high-order relational information by directly factorizing distinct k-step probability transition matrices to preserve global graph structure across separate subspaces without sampling.

In this paper, we present GraRep, a novel model for learning vertex representations of weighted graphs. This model learns low dimensional vectors to represent vertices appearing in a graph and, unlike existing work, integrates global structural information of the graph into the learning process. We also formally analyze the connections between our work and several previous research efforts, including the DeepWalk model of Perozzi et al. [20] as well as the skip-gram model with negative sampling of Mikolov et al. [18] We conduct experiments on a language network, a social network as well as a citation network and show that our learned global representations can be effectively used as features in tasks such as clustering, classification and visualization. Empirical results demonstrate that our representation significantly outperforms other state-of-the-art methods in such tasks.

Added

2026-09-24