GraRep: Learning Graph Representations with Global Structural Information

Shaosheng CaoWei LuQiongkai Xu

article2015CIKM1,745 citations

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.

Listen

Real-world data in social networks, citation databases, and language corpora are naturally structured as graphs. Extracting compact, numerical representations of individual nodes within these networks is essential for critical downstream applications like user profiling, automated classification, and search. However, existing embedding methods rely on random sampling techniques that collapse multi-step relationships into a single space or restrict relationships to immediate local neighbors, thereby failing to capture distinct, long-range global structures accurately.

The article introduces and evaluates GraRep, a graph representation learning model designed to capture exact global structural information across weighted and unweighted networks without relying on sampling processes. The objective is to demonstrate that preserving distinct step-by-step transition probabilities in separate subspaces produces higher-quality, feature-rich representations for complex graph analysis.

To evaluate this framework, the authors derived an exact mathematical objective that directly links network transition probabilities across multiple steps to matrix factorization. They tested GraRep against leading graph embedding baselines across three real-world datasets: a language network clustering task on 20-Newsgroup, a multi-label social network classification task on Blogcatalog with over 10,000 nodes, and a visualization task on the DBLP author citation network.

The experimental findings show that GraRep consistently outperformed all existing baseline methods across all tasks. In social network classification, GraRep achieved superior accuracy, particularly under data scarcity where only 10% of nodes were labeled, reaching a Macro-F1 score of 23.20 compared to 19.26–21.02 for baselines. In language clustering, it achieved the highest mutual information scores across various group sizes, and in network visualization, it generated the lowest error score and the clearest visual separation of research fields. Performance improved significantly when capturing up to six transition steps, after which returns plateaued.

These results demonstrate that explicitly separating multi-step relational information provides richer feature representations than traditional averaging or sampling approaches. This architectural separation enhances model robustness and diagnostic clarity in network analysis tasks without introducing stochastic sampling noise.

Organizations handling network-structured data should consider integrating exact transition-based embedding frameworks into their graph processing pipelines, balancing the maximum step parameter between five and six steps for optimal predictive accuracy. However, practitioners should be aware of a key computational limitation: matrix multiplication and singular value decomposition require substantial processing time as graph sizes increase. For extremely large networks, future deployment should explore scalable matrix approximation methods or deep learning architectures before full operational rollout.

Australian National University IBM Singapore University of Technology and Design Xidian University classification clustering algorithms directed graphs GraRep graph representations global structural information

ShelsonCao/GraRep Cao et al (2015).pdf

Paper: DeepWalk: online learning of social representations, Bryan Perozzi et al. (2014). DeepWalk provides the foundational random-walk and skip-gram graph embedding formulation that GraRep directly analyzes, builds upon, and extends with explicit k-step transition matrices.
Paper: Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering, Mikhail Belkin et al. (2001). This seminal work establishes the foundational principles of spectral graph embedding and Laplacian-based dimensionality reduction that underpin matrix factorization approaches to network representation.
Paper: Graph Embedding and Extensions: A General Framework for Dimensionality Reduction, Shuicheng Yan et al. (2007). It provides a general unifying graph embedding framework for dimensionality reduction, establishing the theoretical relationship between graph construction and matrix-based representation learning.

Paper: node2vec: Scalable Feature Learning for Networks, Aditya Grover et al. (2016). Node2vec extends random-walk representation learning by introducing parameterized, biased walks to flexibly balance local and global structural information explored by GraRep.
Paper: Structural Deep Network Embedding, Daixin Wang et al. (2016). SDNE advances the goal of capturing multi-order network structure by replacing explicit matrix factorization with deep autoencoder architectures.
Paper: metapath2vec: Scalable Representation Learning for Heterogeneous Networks, Yuxiao Dong et al. (2017). Metapath2vec generalizes homogeneous high-order structural embedding paradigms to heterogeneous information networks containing multiple entity and relation types.
Paper: A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications, Hongyun Cai et al. (2017). This comprehensive survey contextualizes GraRep within the broader taxonomy of matrix factorization, random walk, and deep graph embedding algorithms.
Paper: Graph Embedding Techniques, Applications, and Performance: A Survey, Palash Goyal et al. (2017). This survey systematically benchmarks high-order proximity and factorization-based graph representation models, including GraRep and its successors.
Paper: Representation Learning on Graphs: Methods and Applications, William L. Hamilton et al. (2017). This review provides a unified framework contrasting shallow matrix-factorization embeddings like GraRep with neighborhood-aggregation neural architectures.
Paper: Revisiting Semi-Supervised Learning with Graph Embeddings, Zhilin Yang et al. (2016). Planetoid extends graph-based representation learning into semi-supervised inductive settings combining graph structure with instance features.

Cover for GraRep: Learning Graph Representations with Global Structural Information

Abstract

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.

Topics

classification clustering algorithms directed graphs social networks visualization weighted graph bipartite graphs graph structures vertex set

Keywords

GraRep graph representations global structural information vertex representations graph factorization large-scale information network spectral clustering hierarchical softmax nonlinear dimensionality reduction

Categories and Subject Descriptors
General Terms
Keywords
1. INTRODUCTION
2. RELATED WORK
2.1 Linear Sequence Representation Methods
2.2 Graph Representation Approaches
3. GRAREP MODEL
3.1 Graphs and Their Representations
3.2 Loss Function On Graph
3.3 Optimization with Matrix Factorization
4. ALGORITHM
5. SKIP-GRAM MODEL AS A SPECIAL CASE OF GRAREP
5.1 Explicit Loss of Skip-gram Model on Graph
5.2 Intrinsic Relation Between Sampling and Transition Probabilities
6. EXPERIMENTAL DESIGN
6.1 Datasets and Tasks
6.2 Baseline Algorithms
6.3 Parameter Settings
6.4 Experimental Results
6.4.1 20-Newsgroup Network
6.4.2 Blogcatalog Network
6.4.3 DBLP Network
6.5 Parameter Sensitivity
7. CONCLUSIONS
8. ACKNOWLEDGMENTS
9. REFERENCES

Knowls

Knowl 1 — GraRep: Graph Representation Learning with Global Structural Information
model/method
GraRep is a framework for learning low-dimensional vertex representations for weighted or unweighted graphs $G = (V, E)$ that explicitly preserves $k$ -step global relational information across multiple distinct transition steps $k ag{1, 2, \dots, K}$ .

Given an adjacency matrix $S \in \mathbb{R}^{|V| \times |V|}$ where $S_{i,j} \ge 0$ represents the edge weight between vertex $v_i$ and vertex $v_j$ , the diagonal degree matrix $D$ is defined by $D_{i,i} = \sum_j S_{i,j}$ and $D_{i,j} = 0$ for $i \ne j$ . The 1-step probability transition matrix is:

$A = D^{-1} S$

The $k$ -step probability transition matrix is the $k$ -th power of $A$ :

$A^k = \underbrace{A \cdot A \cdots A}_{k}$

where $A^k_{i,j} = p_k(v_j | v_i)$ denotes the exact probability of transitioning from vertex $v_i$ to vertex $v_j$ in exactly $k$ steps.

For each step $k \in \{1, \dots, K\}$ , GraRep solves a matrix factorization problem derived from noise contrastive estimation to obtain a vertex representation matrix $W^k \in \mathbb{R}^{|V| \times d}$ for the $k$ -step subspace. The complete global vertex representation matrix $W \in \mathbb{R}^{|V| \times (K \cdot d)}$ is constructed by concatenating all $k$ -step representation matrices:

$W = [W^1, W^2, \dots, W^K]$

By retaining $k$ -step relational information in separate subspace representations rather than projecting all steps into a single shared space, GraRep preserves distinct structural roles of paths of different lengths.
Knowl 2 — Positive Shifted Log Probabilistic Matrix Formulation for Step k
equation
For a fixed transition step $k$ , GraRep defines an objective function over the graph using Noise Contrastive Estimation (NCE):

$L_k = \sum_{w \in V} L_k(w)$

$L_k(w) = \sum_{c \in V} p_k(c|w) \log \sigma(\vec{w} \cdot \vec{c}) + \lambda \mathbb{E}_{c' \sim p_k(V)} [\log \sigma(-\vec{w} \cdot \vec{c}')]$

where $\vec{w} \in \mathbb{R}^d$ and $\vec{c} \in \mathbb{R}^d$ are low-dimensional vector representations of vertex $w$ and context vertex $c$ , $\sigma(x) = (1 + e^{-x})^{-1}$ is the sigmoid function, $\lambda$ is the number of negative samples, and $p_k(c) = \frac{1}{|V|} \sum_{w'} A^k_{w',c}$ is the context vertex distribution under a uniform initial vertex prior $q(w') = 1/|V|$ .

Optimizing the local loss $L_k(w, c)$ by setting $\frac{\partial L_k}{\partial (\vec{w} \cdot \vec{c})} = 0$ yields the exact dot product relation:

$\vec{w} \cdot \vec{c} = \log \left( \frac{A^k_{w,c}}{\sum_{w'} A^k_{w',c}} \right) - \log(\beta)$

where $\beta = \frac{\lambda}{|V|}$ .

To eliminate negative values and reduce noise, GraRep constructs the positive $k$ -step log probability matrix $X^k \in \mathbb{R}^{|V| \times |V|}$ :

$X^k_{i,j} = \max \left( \log \left( \frac{A^k_{i,j}}{\sum_{t=1}^{|V|} A^k_{t,j}} \right) - \log(\beta), 0 \right)$

Singular Value Decomposition (SVD) on $X^k \approx U^k_d \Sigma^k_d (V^k_d)^T$ yields the $k$ -step vertex representation matrix:

$W^k = U^k_d (\Sigma^k_d)^{\frac{1}{2}}$
Knowl 3 — GraRep Algorithm for Global Graph Representation Learning
algorithm
The GraRep algorithm takes an adjacency matrix $S$ , maximum transition step $K$ , log-shifted factor $\beta = \lambda / |V|$ , and embedding dimension $d$ per step, and outputs the concatenated graph representation matrix $W \in \mathbb{R}^{|V| \times (K \cdot d)}$ .
Input: Graph adjacency matrix $S \in \mathbb{R}^{|V| \times |V|}$ , maximum transition step $K$ , log shifted factor $\beta$ , dimension of representation vector $d$
Output: Matrix of graph representations $W \in \mathbb{R}^{|V| \times (K \cdot d)}$
1. Compute 1-step transition probability matrix:
   Compute degree matrix $D$ with $D_{i,i} \leftarrow \sum_{j=1}^{|V|} S_{i,j}$ and $D_{i,j} \leftarrow 0$ for $i \ne j$
   Compute $A \leftarrow D^{-1} S$
   Compute transition probability matrices $A^1, A^2, \dots, A^K$ via successive matrix multiplication
2. Compute $k$ -step representation matrices:
   for $k = 1$ to $K$ do:
       for $j = 1$ to $|V|$ do:
            $\Gamma^k_j \leftarrow \sum_{p=1}^{|V|} A^k_{p,j}$
       for $i = 1$ to $|V|$ do:
           for $j = 1$ to $|V|$ do:
                $X^k_{i,j} \leftarrow \log \left( \frac{A^k_{i,j}}{\Gamma^k_j} \right) - \log(\beta)$
               if $X^k_{i,j} < 0$ then:
                    $X^k_{i,j} \leftarrow 0$
       Compute truncated SVD: $[U^k, \Sigma^k, (V^k)^T] \leftarrow \text{SVD}(X^k)$
       Select top $d$ components: $U^k_d \leftarrow U^k[:, 1:d]$ , $\Sigma^k_d \leftarrow \Sigma^k[1:d, 1:d]$
        $W^k \leftarrow U^k_d (\Sigma^k_d)^{\frac{1}{2}}$
3. Concatenate representations:
    $W \leftarrow [W^1, W^2, \dots, W^K]$
   return $W$
Knowl 4 — Relationship Between Graph Skip-Gram with Negative Sampling and GraRep
theoretical result
The Skip-Gram model with Negative Sampling (SGNS) applied to graph random walks (e.g., DeepWalk) is a special constrained case of GraRep that forces all transition steps into an equal-weight linear combination within a single shared subspace.

In random walk sequences of total length $\gamma$ generated with context window size $K$ , the expected co-occurrence count between vertex $w$ and context vertex $c$ across all $K$ steps is:

$\#(w, c) = \alpha_w \gamma \sum_{k=1}^K p_k(c|w) = \alpha_w \gamma M_{w,c}$

where $M = \sum_{k=1}^K A^k$ is the cumulative $K$ -step transition matrix, and $\alpha_w$ is the probability of observing vertex $w$ as the start vertex. Assuming a uniform start vertex prior $\alpha_w = 1/|V|$ , the expected individual context count is $\#(c) = \sum_w \alpha_w \gamma M_{w,c}$ .

Substituting these expectations into the Pointwise Mutual Information matrix implicitly factorized by SGNS yields:

$Y^{\text{E-SGNS}}_{w,c} = \log \left( \frac{\#(w, c) \cdot |D|}{\#(w) \cdot \#(c)} \right) - \log(\lambda) = \log \left( \frac{M_{w,c}}{\sum_t M_{t,c}} \right) - \log(\beta)$

where $|D| = \gamma K$ and $\beta = \lambda / |V|$ .

This demonstrates that Enhanced SGNS (E-SGNS) factorizes a single matrix representing an unweighted sum of $k$ -step transition probabilities $M = A^1 + A^2 + \dots + A^K$ . In contrast, GraRep factorizes each $A^k$ independently into distinct subspaces $W^k$ , allowing non-linear combinations and distinct weighting of different path lengths.

Knowl 5 — Document Clustering Performance on 20-Newsgroups Network

data/table

Document clustering is evaluated on language networks built from the 20-Newsgroups dataset using cosine similarity of tf-idf vectors as edge weights. Graphs are constructed with 3, 6, and 9 newsgroup subsets (3NG, 6NG, 9NG), evaluated on both 200 sampled documents per group and all documents using $k$ -means clustering. Performance is measured by averaged Normalized Mutual Information (NMI) over 10 runs.

Algorithm	3NG(200)	6NG(200)	9NG(200)	3NG(all)	6NG(all)	9NG(all)
GraRep	81.12	67.53	59.43	81.44	71.54	60.38
LINE ( $k$ -max=0)	80.36	64.88	51.58	80.58	68.35	52.30
LINE ( $k$ -max=200)	78.69	66.06	54.14	80.68	68.83	53.53
DeepWalk	65.58	63.66	48.86	65.67	68.38	49.19
DeepWalk (192dim)	60.89	59.89	47.16	59.93	65.68	48.61
E-SGNS	69.98	65.06	48.47	69.04	67.65	50.59
E-SGNS (192dim)	63.55	64.85	48.65	66.64	66.57	49.78
Spectral Clustering	49.04	51.02	46.92	62.41	59.32	51.91
Spectral Clustering (192dim)	28.44	27.80	36.05	44.47	36.98	47.36
Spectral Clustering (16dim)	69.91	60.54	47.39	78.12	68.78	57.87

GraRep achieves the highest NMI across all configurations. Increasing embedding dimensionality from 64 to 192 for DeepWalk, E-SGNS, and Spectral Clustering does not improve clustering accuracy, indicating that higher dimensions without distinct step-level structural separation do not provide useful complementary information.

Knowl 6 — Multi-Label Classification Performance on BlogCatalog Network

data/table

Multi-label vertex classification is evaluated on the unweighted BlogCatalog network (10,312 vertices, 333,983 edges, 39 topic labels) by training one-vs-rest logistic regression models via LibLinear. Training vertex proportions range from 10% to 90%, averaged over 10 runs, reporting Micro-F1 and Macro-F1 percentages.

Metric	Algorithm	10%	20%	30%	40%	50%	60%	70%	80%	90%
Micro-F1	GraRep	38.24	40.31	41.34	41.87	42.60	43.02	43.43	43.55	44.24
	LINE	37.19	39.82	40.88	41.47	42.19	42.72	43.15	43.36	43.88
	DeepWalk	35.93	38.38	39.50	40.39	40.79	41.28	41.60	41.93	42.17
	E-SGNS	35.71	38.34	39.64	40.39	41.23	41.66	42.01	42.16	42.25
	Spectral Clustering	37.16	39.45	40.22	40.87	41.27	41.50	41.48	41.62	42.12
Macro-F1	GraRep	23.20	25.55	26.69	27.53	28.35	28.78	29.67	29.96	30.93
	LINE	19.63	23.04	24.52	25.70	26.65	27.26	27.94	28.68	29.38
	DeepWalk	21.02	23.81	25.39	26.27	26.85	27.36	27.67	27.96	28.41
	E-SGNS	21.01	24.09	25.61	26.59	27.64	28.08	28.33	28.34	29.26
	Spectral Clustering	19.26	22.24	23.51	24.33	24.83	25.19	25.36	25.52	26.21

GraRep outperforms all baselines across all training ratios. The performance margin is largest in data-scarce settings (10% training data: Macro-F1 of 23.20 for GraRep vs. 19.63 for LINE and 21.02 for DeepWalk), showing that combining multi-step structural representations provides stronger regularization when labeled data is limited.

Knowl 7 — Visualization and KL Divergence on DBLP Citation Network

data/table

The quality of learned vertex embeddings for 2D visualization is evaluated on the DBLP author citation network (7,314 authors, 72,927 edges across data mining, machine learning, and computer vision conferences). Vertex representations are mapped to 2D using t-SNE, and representation fidelity is quantified using the final t-SNE Kullback-Leibler (KL) divergence, where lower values indicate better preservation of pairwise graph similarities.

GraRep achieves the lowest KL divergence (1.0070), producing visualizations with distinctly separated clusters and clear decision boundaries among research fields, outperforming LINE (1.0816) and random-walk methods.

Knowl 8 — Effect of Maximum Step Size K on Representation Accuracy
empirical result
On the BlogCatalog network, evaluating GraRep across maximum step sizes $K \in \{1, 2, 3, 4, 5, 6, 7\}$ demonstrates the complementary utility of higher-order transition steps:
- Moving from $K = 1$ (1-step transitions only) to $K = 2$ provides a large increase in both Micro-F1 and Macro-F1 across all training ratios (1% to 9%).
- Setting $K = 3$ significantly outperforms $K = 2$ , and $K = 4$ offers modest improvements over $K = 3$ .
- Performance continues to increase up to $K = 6$ , where optimal classification accuracy is reached.
- Setting $K = 7$ yields no improvement over $K = 6$ , as high-order transition probabilities $A^k$ approach the stationary distribution of the random walk, providing diminishing unique structural signal.
Knowl 9 — Embedding Dimension Sensitivity and Runtime Scaling
empirical result
Empirical analysis of GraRep hyperparameters reveals distinct dimensionality and execution time properties:
- Dimension sensitivity ( $d$ ): On 3NG and 9NG datasets evaluated over $d \in \{32, 64, 128, 256\}$ , all evaluated graph representation algorithms (GraRep, DeepWalk, E-SGNS, LINE) achieve optimal NMI clustering performance at $d = 64$ per subspace, with performance degrading as $d$ increases further.
- Runtime scaling with dimension: On BlogCatalog (~10,000 vertices), execution time increases linearly as the number of concatenated feature steps $K$ increases from 1 to 7 (for a fixed per-step dimension $d = 128$ ).
- Runtime scaling with graph size: On 20-Newsgroups graphs varying from 600 to 5,141 vertices, execution time grows steeply with graph size $|V|$ due to the computational cost of dense matrix powers $A^k$ and truncated Singular Value Decomposition on $|V| \times |V|$ matrices.
Knowl 10 — Computational Bottlenecks of Matrix Power and SVD in GraRep
limitation
GraRep exhibits a computational limitation on large-scale graphs due to two operations:
1. Matrix Powers: Computing explicit high-order transition matrices $A^k = A \cdots A$ for $k = 1, \dots, K$ produces dense matrices on connected graphs, requiring significant memory and $O(|V|^3)$ or $O(K |V|^2)$ operations unless sparse approximation methods are used.
2. Singular Value Decomposition: Performing truncated SVD on positive log-probability matrices $X^k \in \mathbb{R}^{|V| \times |V|}$ for each step $k$ scales poorly with increasing vertex count $|V|$ .
Scalability to very large graphs requires future investigation into online matrix approximation algorithms or replacing SVD with deep neural architectures.

Coverage note — None was omitted; all primary contributions, models, derivations, algorithms, benchmark tables, sensitivity findings, and limitations from the paper are represented.

References

1.A. Ahmed, N. Shervashidze, S. Narayanamurthy, V. Josifovski, and A. J. Smola. Distributed large-scale natural graph factorization. In WWW, pages 37–48. International World Wide Web Conferences Steering Committee, 2013.
2.D. Arthur and S. Vassilvitskii. k-means++: The advantages of careful seeding. In SODA, pages 1027–1035. Society for Industrial and Applied Mathematics, 2007.
3.M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In NIPS, volume 14, pages 585–591, 2001.
4.J. A. Bullinaria and J. P. Levy. Extracting semantic representations from word co-occurrence statistics: A computational study. BRM, 39(3):510–526, 2007.
5.J. A. Bullinaria and J. P. Levy. Extracting semantic representations from word co-occurrence statistics: stop-lists, stemming, and svd. BRM, 44(3):890–907, 2012.
6.J. Caron. Experiments with lsa scoring: Optimal rank and basis. In CIR, pages 157–169, 2001.
7.P. Comon. Independent component analysis, a new concept? Signal processing, 36(3):287–314, 1994.
8.T. F. Cox and M. A. Cox. Multidimensional scaling. CRC Press, 2000.
9.C. Eckart and G. Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):211–218, 1936.
10.R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin. Liblinear: A library for large linear classification. JMLR, 9:1871–1874, 2008.
11.M. U. Gutmann and A. Hyv¨arinen. Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics. JMLR, 13(1):307–361, 2012.
12.G. E. Hinton and R. R. Salakhutdinov. Reducing the dimensionality of data with neural networks. Science, 313(5786):504–507, 2006.
13.C. Jutten and J. Herault. Blind separation of sources, part i: An adaptive algorithm based on neuromimetic architecture. Signal processing, 24(1):1–10, 1991.
14.V. Klema and A. J. Laub. The singular value decomposition: Its computation and some applications. Automatic Control, 25(2):164–176, 1980.
15.T. K. Landauer, P. W. Foltz, and D. Laham. An introduction to latent semantic analysis. Discourse processes, 25(2-3):259–284, 1998.
16.O. Levy and Y. Goldberg. Neural word embedding as implicit matrix factorization. In NIPS, pages 2177–2185, 2014.
17.K. Lund and C. Burgess. Producing high-dimensional semantic spaces from lexical co-occurrence. BRMIC, 28(2):203–208, 1996.
18.T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean. Distributed representations of words and phrases and their compositionality. In NIPS, pages 3111–3119, 2013.
19.J. Pennington, R. Socher, and C. D. Manning. Glove: Global vectors for word representation. EMNLP, 12, 2014.
20.B. Perozzi, R. Al-Rfou, and S. Skiena. Deepwalk: Online learning of social representations. In SIGKDD, pages 701–710. ACM, 2014.
21.S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323–2326, 2000.
22.B. Sarwar, G. Karypis, J. Konstan, and J. Riedl. Incremental singular value decomposition algorithms for highly scalable recommender systems. In ICIS, pages 27–28. Citeseer, 2002.
23.J. Shi and J. Malik. Normalized cuts and image segmentation. PAMI, 22(8):888–905, 2000.
24.A. Strehl, J. Ghosh, and R. Mooney. Impact of similarity measures on web-page clustering. In Workshop on Artificial Intelligence for Web Search (AAAI 2000), pages 58–64, 2000.
25.J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei. Line: Large-scale information network embedding. In WWW. ACM, 2015.
26.J. Tang, J. Zhang, L. Yao, J. Li, L. Zhang, and Z. Su. Arnetminer: extraction and mining of academic social networks. In SIGKDD, pages 990–998. ACM, 2008.
27.L. Tang and H. Liu. Relational learning via latent social dimensions. In SIGKDD, pages 817–826. ACM, 2009.
28.J. B. Tenenbaum, V. De Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319–2323, 2000.
29.F. Tian, B. Gao, Q. Cui, E. Chen, and T.-Y. Liu. Learning deep representations for graph clustering. In AAAI, 2014.
30.P. D. Turney. Domain and function: A dual-space model of semantic relations and compositions. JAIR, pages 533–585, 2012.
31.L. Van der Maaten and G. Hinton. Visualizing data using t-sne. JMLR, 9(2579-2605):85, 2008.

Citation

MLA

Cao, S., et al. “GraRep”. Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, 2015, pp. 891–900, https://doi.org/10.1145/2806416.2806512.

APA

Cao, S., Lu, W., & Xu, Q. (2015). GraRep. Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, 891–900. https://doi.org/10.1145/2806416.2806512

Chicago

Cao, S., W. Lu, and Q. Xu. 2015. “GraRep”. Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, 891–900. https://doi.org/10.1145/2806416.2806512.

Harvard

Cao, S., Lu, W. and Xu, Q. (2015) “GraRep”, Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. ACM, pp. 891–900. Available at: https://doi.org/10.1145/2806416.2806512.

Vancouver

1. Cao S, Lu W, Xu Q (2015) GraRep. In: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. ACM, pp 891–900

BibTeX

@inproceedings{Cao_2015, series={CIKM′15}, title={GraRep: Learning Graph Representations with Global Structural Information}, url={http://dx.doi.org/10.1145/2806416.2806512}, DOI={10.1145/2806416.2806512}, booktitle={Proceedings of the 24th ACM International on Conference on Information and Knowledge Management}, publisher={ACM}, author={Cao, Shaosheng and Lu, Wei and Xu, Qiongkai}, year={2015}, month=Oct, pages={891–900}, collection={CIKM′15} }

Metadata:Crossref

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Algorithm	GraRep	LINE	DeepWalk	E-SGNS
KL divergence	1.0070	1.0816	1.1115	1.1009

GraRep: Learning Graph Representations with Global Structural Information

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — GraRep: Graph Representation Learning with Global Structural Information

Knowl 2 — Positive Shifted Log Probabilistic Matrix Formulation for Step k

Knowl 3 — GraRep Algorithm for Global Graph Representation Learning

Knowl 4 — Relationship Between Graph Skip-Gram with Negative Sampling and GraRep

Knowl 5 — Document Clustering Performance on 20-Newsgroups Network

Knowl 6 — Multi-Label Classification Performance on BlogCatalog Network

Knowl 7 — Visualization and KL Divergence on DBLP Citation Network

Knowl 8 — Effect of Maximum Step Size K on Representation Accuracy

Knowl 9 — Embedding Dimension Sensitivity and Runtime Scaling

Knowl 10 — Computational Bottlenecks of Matrix Power and SVD in GraRep

References

Citation

BibTeX

Source Code

Access the Paper