Back

Asymmetric Transitivity Preserving Graph Embedding

Mingdong OuPeng CuiJ. PeiZiwei ZhangWenwu Zhu

article2016KDD1,327 citations

Presents a scalable directed graph embedding algorithm that captures asymmetric transitivity by approximating high-order proximity measures via generalized singular value decomposition, providing theoretical error bounds and superior performance in link prediction and graph reconstruction.

Listen

Modern data applications increasingly rely on massive, directed networks such as social platforms, the web, and academic citation graphs. To analyze these graphs efficiently, practitioners embed nodes into low-dimensional vector spaces, enabling standard machine learning tools and parallel processing. However, most existing embedding techniques focus on undirected networks and fail to capture asymmetric transitivity—the principle that a directed path from node A to B implies an edge from A to B is likely, but not necessarily in reverse. Previous directed graph methods either relied on non-transitive metrics or evaluated only partial network blocks, limiting analytical accuracy and scalability.

The article evaluates and demonstrates a scalable embedding method called High-Order Proximity preserved Embedding (HOPE) to properly preserve asymmetric transitivity in directed graphs. The goal is to provide a unified, computationally efficient framework that learns vector representations capable of accurately predicting links, reconstructing graphs, and generating node recommendations across large-scale networks.

To achieve this, the article establishes a general formulation that unifies several common high-order proximity metrics, including Katz index, Rooted PageRank, Common Neighbors, and Adamic-Adar. Instead of directly computing expensive, dense proximity matrices—which traditionally require cubic time complexity—HOPE uses an iterative generalized singular value decomposition technique that scales linearly with the number of edges. Nodes are represented by two distinct vectors (a source vector and a target vector) to maintain edge directionality. The methodology was validated through extensive experiments on synthetic power-law graphs and three real-world datasets: the Cora citation network (over 23,000 nodes), a Twitter subnetwork (over 465,000 nodes), and a Tencent Weibo subnetwork (nearly 2 million nodes and over 50 million edges).

The evaluation produced four key findings. First, HOPE significantly outperformed existing methods in approximating high-order proximities, achieving an approximation error roughly an order of magnitude smaller than the nearest benchmark across testing dimensions. Second, in recommendation accuracy, HOPE demonstrated dramatic improvements over all baselines, achieving at least an 88.5% gain in top-10 mean average precision and over an 81.2% gain in top-50 precision on the large-scale social networks. Third, HOPE consistently achieved superior precision in full-graph reconstruction and link prediction tasks compared to competitive models like LINE and DeepWalk. Fourth, the empirical results confirmed the theoretical error bound, showing that lower-rank proximity matrices yield significantly smaller relative approximation errors.

These findings indicate that preserving high-order asymmetric transitivity is essential for capturing true network topology. For organizations deploying graph-based machine learning, HOPE offers substantial performance and scalability benefits. It eliminates the computational bottleneck of evaluating dense matrix operations on large graphs, reducing processing time and infrastructure costs while delivering higher accuracy in downstream tasks such as friend suggestions, citation forecasting, and fraud detection.

Organizations analyzing massive directed network data should consider adopting dual-vector embedding frameworks that approximate high-order proximities rather than simple first- or second-order connections. To optimize performance, practitioners can tune target proximity metrics (such as Katz or Rooted PageRank) to match the structural characteristics of their specific datasets. The article's authors also identify the exploration of non-linear models as an important next step to capture even more intricate network structures.

Confidence in these findings is supported by theoretical error bounds and multi-dataset empirical validation. However, decision-makers should note that evaluations relied on linear approximations and sampled subgraphs of online networks. Performance in real-time dynamic networks with rapidly shifting connections may require additional validation before full-scale operational deployment.

Simon Fraser UniversityTsinghua Universitybipartite graphsdirected graphsgraph embeddingsasymmetric transitivity preserving graph embeddingasymmetric transitivitygraph reconstruction
ZW-ZHANG/HOPEOu et al (2016).pdf
Cover for Asymmetric Transitivity Preserving Graph Embedding

Abstract

Graph embedding algorithms embed a graph into a vector space where the structure and the inherent properties of the graph are preserved. The existing graph embedding methods cannot preserve the asymmetric transitivity well, which is a critical property of directed graphs. Asymmetric transitivity depicts the correlation among directed edges, that is, if there is a directed path from u to v, then there is likely a directed edge from u to v. Asymmetric transitivity can help in capturing structures of graphs and recovering from partially observed graphs. To tackle this challenge, we propose the idea of preserving asymmetric transitivity by approximating high-order proximity which are based on asymmetric transitivity. In particular, we develop a novel graph embedding algorithm, High-Order Proximity preserved Embedding (HOPE for short), which is scalable to preserve high-order proximities of large scale graphs and capable of capturing the asymmetric transitivity. More specifically, we first derive a general formulation that cover multiple popular high-order proximity measurements, then propose a scalable embedding algorithm to approximate the high-order proximity measurements based on their general formulation. Moreover, we provide a theoretical upper bound on the RMSE (Root Mean Squared Error) of the approximation. Our empirical experiments on a synthetic dataset and three real-world datasets demonstrate that HOPE can approximate the high-order proximities significantly better than the state-of-art algorithms and outperform the state-of-art algorithms in tasks of reconstruction, link prediction and vertex recommendation.

Topics

bipartite graphsdirected graphsgraph embeddingslink predictionmean squarerecommendationreconstructionweighted graph

Keywords

asymmetric transitivity preserving graph embeddingasymmetric transitivitygraph reconstructionlink predictionvertex recommendationhigh-order proximitynonlinear dimensionality reductionLaplacian Eigenmapsproximity matrixcitation network

Table of Contents

  • 1. INTRODUCTION
  • 2. RELATED WORK
  • 2.1 Graph Embedding
  • 2.2 Directed Graph
  • 3. High-Order Proximity Preserved Embedding
  • 3.1 Notations
  • 3.2 Problem Definition
  • 3.3 High order proximities
  • 3.4 Approximation of High-Order Proximity
  • 3.4.1 Complexity Analysis
  • 3.4.2 Approximation Error
  • 4. EXPERIMENTS
  • 4.1 Experiment Setting
  • 4.1.1 Datasets
  • 4.1.2 Baseline Methods
  • 4.1.3 Evaluation Metrics
  • 4.2 High-order Proximity Approximation
  • 4.3 Graph Reconstruction
  • 4.4 Link Prediction
  • 4.5 Vertex Recommendation
  • 5. CONCLUSION
  • 6. REFERENCES

Knowls

  1. Knowl 1 — Asymmetric Transitivity Preserved Graph Embedding Formulation

    model/method

    To preserve asymmetric transitivity in a directed graph G=(V,E)G = (V, E) with adjacency matrix A∈RN×NA \in \mathbb{R}^{N \times N} (where directed paths from viv_i to vjv_j indicate a high likelihood of a directed link vi→vjv_i \to v_j but not vj→viv_j \to v_i), the High-Order Proximity preserved Embedding (HOPE) model represents each vertex vi∈Vv_i \in V by two separate KK-dimensional vectors: a source embedding vector uis∈RKu_i^s \in \mathbb{R}^K and a target embedding vector uit∈RKu_i^t \in \mathbb{R}^K. These form the source embedding matrix Us∈RN×KU^s \in \mathbb{R}^{N \times K} and target embedding matrix Ut∈RN×KU^t \in \mathbb{R}^{N \times K}. The approximated directed proximity from viv_i to vjv_j is defined by the inner product uis(ujt)⊤u_i^s (u_j^t)^\top.

    Given an asymmetric high-order proximity matrix S∈RN×NS \in \mathbb{R}^{N \times N}, the embedding objective minimizes the Frobenius norm reconstruction loss:

    min⁡Us,Ut∥S−Us(Ut)⊤∥F2\min_{U^s, U^t} \|S - U^s (U^t)^\top\|_F^2

    For an optimal rank-KK approximation obtained via the Singular Value Decomposition (SVD) of S=∑i=1Nσivis(vit)⊤S = \sum_{i=1}^N \sigma_i v_i^s (v_i^t)^\top with singular values σ1≥σ2≥⋯≥σN≥0\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_N \ge 0 and orthogonal singular vectors vis,vit∈RNv_i^s, v_i^t \in \mathbb{R}^N, the optimal source and target embedding matrices are given by:

    Us=[σ1v1s,…,σKvKs]U^s = [\sqrt{\sigma_1} v_1^s, \dots, \sqrt{\sigma_K} v_K^s]

    Ut=[σ1v1t,…,σKvKt]U^t = [\sqrt{\sigma_1} v_1^t, \dots, \sqrt{\sigma_K} v_K^t]

  2. Knowl 2 — General Matrix Formulation for Graph High-Order Proximity Measures

    model/method

    Multiple high-order proximity measurements in directed graphs share a unified general matrix formulation:

    S=Mg−1⋅MlS = M_g^{-1} \cdot M_l

    where Mg∈RN×NM_g \in \mathbb{R}^{N \times N} and Ml∈RN×NM_l \in \mathbb{R}^{N \times N} are matrix polynomials of the graph adjacency matrix AA (or the transition matrix PP):

    1. Katz Index: SKatz=∑l=1∞βlAl=(I−βA)−1βAS^{\text{Katz}} = \sum_{l=1}^\infty \beta^l A^l = (I - \beta A)^{-1} \beta A, with Mg=I−βAM_g = I - \beta A and Ml=βAM_l = \beta A, where β>0\beta > 0 is a decay parameter smaller than the spectral radius of AA.

    2. Rooted PageRank (RPR): SRPR=(1−α)(I−αP)−1S^{\text{RPR}} = (1 - \alpha)(I - \alpha P)^{-1}, with Mg=I−αPM_g = I - \alpha P and Ml=(1−α)IM_l = (1 - \alpha)I, where α∈[0,1)\alpha \in [0, 1) is the random walk continuation probability and PP is the transition probability matrix satisfying ∑i=1NPij=1\sum_{i=1}^N P_{ij} = 1.

    3. Common Neighbors (CN): SCN=A2S^{\text{CN}} = A^2, with Mg=IM_g = I and Ml=A2M_l = A^2.

    4. Adamic-Adar (AA): SAA=ADAS^{\text{AA}} = A D A, with Mg=IM_g = I and Ml=ADAM_l = A D A, where D∈RN×ND \in \mathbb{R}^{N \times N} is a diagonal matrix with diagonal entries Dii=1/∑j(Aij+Aji)D_{ii} = 1 / \sum_j (A_{ij} + A_{ji}).

    Global proximities (Katz, RPR) feature Mg=I−αBM_g = I - \alpha B (where BB is a transition matrix) to propagate paths globally across the graph, while local proximities (CN, AA) have Mg=IM_g = I, confining transitivity within local neighborhoods.

  3. Knowl 3 — Generalized SVD Representation for High-Order Proximity Matrix Factorization

    theoretical result

    Given a proximity matrix S=Mg−1Ml∈RN×NS = M_g^{-1} M_l \in \mathbb{R}^{N \times N} with singular value decomposition Mg−1Ml=VsΣ(Vt)⊤M_g^{-1} M_l = V^s \Sigma (V^t)^\top, where Vs,Vt∈RN×NV^s, V^t \in \mathbb{R}^{N \times N} are orthogonal matrices and Σ=diag(σ1,…,σN)\Sigma = \text{diag}(\sigma_1, \dots, \sigma_N) with σ1≥⋯≥σN≥0\sigma_1 \ge \dots \ge \sigma_N \ge 0, there exists a nonsingular matrix X∈RN×NX \in \mathbb{R}^{N \times N} and two diagonal matrices Σl=diag(σ1l,…,σNl)\Sigma^l = \text{diag}(\sigma_1^l, \dots, \sigma_N^l) and Σg=diag(σ1g,…,σNg)\Sigma^g = \text{diag}(\sigma_1^g, \dots, \sigma_N^g) such that:

    (Vt)⊤Ml⊤X=Σl(V^t)^\top M_l^\top X = \Sigma^l

    (Vs)⊤Mg⊤X=Σg(V^s)^\top M_g^\top X = \Sigma^g

    where σ1l≥⋯≥σKl≥0\sigma_1^l \ge \dots \ge \sigma_K^l \ge 0, 0≤σ1g≤⋯≤σKg0 \le \sigma_1^g \le \dots \le \sigma_K^g, and for all i∈{1,…,N}i \in \{1, \dots, N\}:

    (σil)2+(σig)2=1(\sigma_i^l)^2 + (\sigma_i^g)^2 = 1

    σi=σilσig\sigma_i = \frac{\sigma_i^l}{\sigma_i^g}

    This generalized SVD formulation allows computing the leading singular vectors Vs,VtV^s, V^t and singular values Σ\Sigma directly from the matrix pair (Ml⊤,Mg⊤)(M_l^\top, M_g^\top), avoiding explicit inversion of MgM_g and the dense matrix multiplication Mg−1MlM_g^{-1} M_l.

  4. Knowl 4 — High-Order Proximity Preserved Embedding (HOPE) Algorithm

    algorithm

    The HOPE algorithm computes the top-KK source and target embedding vectors by solving a partial Generalized SVD on (Ml⊤,Mg⊤)(M_l^\top, M_g^\top) using an iterative Jacobi-Davidson type method (JDGSVD), avoiding explicit matrix inversion and dense proximity matrix construction.

    Input: Adjacency matrix A∈RN×NA \in \mathbb{R}^{N \times N}, embedding dimension KK, proximity measure parameters θ\theta
    Output: Source embedding matrix Us∈RN×KU^s \in \mathbb{R}^{N \times K}, target embedding matrix Ut∈RN×KU^t \in \mathbb{R}^{N \times K}
    1: Construct matrix polynomials MgM_g and MlM_l from AA using parameters θ\theta
    2: Run JDGSVD on (Ml⊤,Mg⊤)(M_l^\top, M_g^\top) to obtain generalized singular values {σ1l,…,σKl}\{\sigma_1^l, \dots, \sigma_K^l\} and {σ1g,…,σKg}\{\sigma_1^g, \dots, \sigma_K^g\}, and singular vector sets {v1s,…,vKs}\{v_1^s, \dots, v_K^s\} and {v1t,…,vKt}\{v_1^t, \dots, v_K^t\}
    3: for i=1i = 1 to KK do
    4: σi←σil/σig\sigma_i \leftarrow \sigma_i^l / \sigma_i^g
    5: end for
    6: Us←[σ1v1s,…,σKvKs]U^s \leftarrow [\sqrt{\sigma_1} v_1^s, \dots, \sqrt{\sigma_K} v_K^s]
    7: Ut←[σ1v1t,…,σKvKt]U^t \leftarrow [\sqrt{\sigma_1} v_1^t, \dots, \sqrt{\sigma_K} v_K^t]
    8: return Us,UtU^s, U^t

    By multiplying MgM_g and MlM_l directly with thin N×KN \times K intermediate matrices in JDGSVD, the multiplication cost is O(m⋅K)O(m \cdot K), where m=∣E∣m = |E| is the number of nonzero elements in AA. The total time complexity is O(m⋅K2⋅L)O(m \cdot K^2 \cdot L), where LL is the number of JDGSVD iterations, scaling linearly with the number of edges.

  5. Knowl 5 — Approximation Error Bound of HOPE

    theoretical result

    Given the target high-order proximity matrix S∈RN×NS \in \mathbb{R}^{N \times N} of a directed graph and the rank-KK source and target embedding matrices Us,Ut∈RN×KU^s, U^t \in \mathbb{R}^{N \times K} learned by HOPE, the Frobenius norm approximation error is:

    ∥S−Us(Ut)⊤∥F2=∑i=K+1Nσi2\|S - U^s (U^t)^\top\|_F^2 = \sum_{i=K+1}^N \sigma_i^2

    and the normalized relative approximation error (NRMSE squared) is:

    ∥S−Us(Ut)⊤∥F2∥S∥F2=∑i=K+1Nσi2∑i=1Nσi2\frac{\|S - U^s (U^t)^\top\|_F^2}{\|S\|_F^2} = \frac{\sum_{i=K+1}^N \sigma_i^2}{\sum_{i=1}^N \sigma_i^2}

    where {σ1,…,σN}\{\sigma_1, \dots, \sigma_N\} are the singular values of SS in descending order. When SS has a lower effective rank, the tail singular values {σK+1,…,σN}\{\sigma_{K+1}, \dots, \sigma_N\} are closer to zero, resulting in a lower approximation error.

  6. Knowl 6 — Proximity Approximation Error Across Proximity Metrics and Matrix Ranks

    empirical result

    When evaluated across embedding dimensions K∈[10,100]K \in [10, 100] on synthetic power-law graphs (N=10,000N = 10{,}000, ∣E∣=144,555|E| = 144{,}555) and the Cora citation network (N=23,166N = 23{,}166, ∣E∣=91,500|E| = 91{,}500):

    1. HOPE consistently achieves lower Root Mean Squared Error (RMSE) than Partial Proximity Embedding (PPE) across all four proximity metrics (Katz with β=0.1\beta = 0.1, Rooted PageRank with α=0.5\alpha = 0.5, Common Neighbors, and Adamic-Adar).
    2. On Katz proximity, HOPE's approximation error is approximately one order of magnitude lower than that of PPE (e.g., RMSE <0.001< 0.001 for HOPE vs ≈0.010\approx 0.010 for PPE at K=100K = 100 on Synthetic Data; RMSE <0.001< 0.001 vs ≈0.020\approx 0.020 on Cora).
    3. In Rooted PageRank approximation (K=100K = 100), the normalized relative approximation error (NRMSE) decreases monotonically as α\alpha increases from 0.10.1 to 0.90.9 (Synthetic: dropping from ≈9.7×10−6\approx 9.7 \times 10^{-6} to ≈6.2×10−6\approx 6.2 \times 10^{-6}; Cora: dropping from ≈4.3×10−5\approx 4.3 \times 10^{-5} to ≈0.5×10−5\approx 0.5 \times 10^{-5}), confirming that lower-rank target proximity matrices yield lower relative embedding error.

  7. Knowl 7 — Graph Reconstruction and Directed Link Prediction Performance

    empirical result

    Evaluated on large-scale social networks Tencent Weibo (SN-TWeibo: N=1,944,589N = 1{,}944{,}589, ∣E∣=50,655,143|E| = 50{,}655{,}143) and Twitter (SN-Twitter: N=465,017N = 465{,}017, ∣E∣=834,797|E| = 834{,}797) by sampling 0.1% of vertex pairs:

    1. Graph Reconstruction: Ranking vertex pairs by reconstructed proximity uis(ujt)⊤u_i^s (u_j^t)^\top (using Katz proximity approximation), HOPE achieves significantly higher Precision@k than baselines (LINE1, LINE2, DeepWalk, PPE, Common Neighbors, Adamic-Adar). On SN-TWeibo, HOPE achieves Precision@k near 0.870.87 at k=102k = 10^2 and remains above 0.850.85 up to k=103k = 10^3, whereas LINE2 is below 0.200.20 and PPE is below 0.600.60.
    2. Directed Link Prediction (training on 80% edges, predicting remaining 20%): HOPE achieves Precision@k exceeding 0.850.85 on SN-TWeibo and ≈0.15\approx 0.15 on SN-Twitter at k=102k = 10^2, outperforming all baselines across small-to-medium kk. PPE's prediction performance drops sharply compared to its reconstruction performance due to overfitting on landmark sub-blocks.

  8. Knowl 8 — Vertex Recommendation Performance on Large Directed Social Networks

    data/table

    Vertex recommendation was evaluated by randomly hiding 20% of outgoing edges for 1,000 sampled test vertices and ranking the top candidate vertices by predicted proximity. Mean Average Precision (MAP@10, MAP@50, MAP@100) was measured on SN-TWeibo and SN-Twitter using Katz index as the target high-order proximity for HOPE and PPE.

    Method SN-TWeibo SN-Twitter
    MAP@10 MAP@50 MAP@100 MAP@10 MAP@50 MAP@100
    HOPE 0.2295 0.1869 0.1690 0.1000 0.0881 0.0766
    PPE 0.0928 0.0845 0.0770 0.0061 0.0077 0.0081
    LINE1 0.0000 0.0000 0.0050 0.0209 0.0221 0.0221
    LINE2 0.0510 0.0510 0.0480 0.0044 0.0043 0.0035
    DeepWalk 0.0635 0.0583 0.0040 0.0006 0.0008 0.0010
    Common Neighbors 0.1217 0.1031 0.1550 0.0394 0.0379 0.0369
    Adamic-Adar 0.1173 0.0990 0.1560 0.0455 0.0442 0.0423

    HOPE achieves at least an 88.5% relative improvement in MAP@10 and at least an 81.2% relative improvement in MAP@50 over all baseline methods on both datasets. Methods capturing directed high-order relationships (HOPE, Common Neighbors, Adamic-Adar, PPE) consistently outperform first-order proximity methods (LINE1, LINE2).

Coverage note — None was omitted; all key theoretical formulations, matrix derivations, algorithm steps, complexity results, approximation error bounds, and experimental evaluations across reconstruction, link prediction, and vertex recommendation were extracted.

References

  1. 1.M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In NIPS, volume 14, pages 585–591, 2001.
  2. 2.S. Cao, W. Lu, and Q. Xu. Grarep: Learning graph representations with global structural information. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pages 891–900. ACM, 2015.
  3. 3.S. Chang, G.-J. Qi, C. C. Aggarwal, J. Zhou, M. Wang, and T. S. Huang. Factorized similarity learning in networks. In Data Mining (ICDM), 2014 IEEE International Conference on, pages 60–69. IEEE, 2014.
  4. 4.M. Chen, Q. Yang, and X. Tang. Directed graph embedding. In IJCAI, pages 2707–2712, 2007.
  5. 5.M. De Choudhury, Y.-R. Lin, H. Sundaram, K. S. Candan, L. Xie, A. Kelliher, et al. How does the data sampling strategy impact the discovery of information diffusion in social media? ICWSM, 10:34–41, 2010.
  6. 6.R. A. Fisher. The use of multiple measurements in taxonomic problems. Annals of eugenics, 7(2):179–188, 1936.
  7. 7.M. S. Handcock, A. E. Raftery, and J. M. Tantrum. Model-based clustering for social networks. Journal of the Royal Statistical Society: Series A (Statistics in Society), 170(2):301–354, 2007.
  8. 8.X. He, S. Yan, Y. Hu, P. Niyogi, and H.-J. Zhang. Face recognition using laplacianfaces. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 27(3):328–340, 2005.
  9. 9.M. Hochstenbach. A jacobi–davidson type method for the generalized singular value problem. Linear Algebra and its Applications, 431(3):471–487, 2009.
  10. 10.P. D. Hoff. Multiplicative latent factor models for description and prediction of social networks. Computational and Mathematical Organization Theory, 15(4):261–272, 2009.
  11. 11.P. D. Hoff, A. E. Raftery, and M. S. Handcock. Latent space approaches to social network analysis. Journal of the american Statistical association, 97(460):1090–1098, 2002.
  12. 12.P. W. Holland and S. Leinhardt. An exponential family of probability distributions for directed graphs. Journal of the american Statistical association, 76(373):33–50, 1981.
  13. 13.J. Hopcroft and R. Kannan. Foundations of data science. 2014.
  14. 14.G. Jeh and J. Widom. Simrank: a measure of structural-context similarity. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 538–543. ACM, 2002.
  15. 15.I. Jolliffe. Principal component analysis. Wiley Online Library, 2002.
  16. 16.L. Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39–43, 1953.
  17. 17.J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pages 177–187. ACM, 2005.
  18. 18.O. Levy and Y. Goldberg. Neural word embedding as implicit matrix factorization. In Advances in Neural Information Processing Systems, pages 2177–2185, 2014.
  19. 19.T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems, pages 3111–3119, 2013.
  20. 20.K. Miller, M. I. Jordan, and T. L. Griffiths. Nonparametric latent feature models for link prediction. In Advances in neural information processing systems, pages 1276–1284, 2009.
  21. 21.S. Mousazadeh and I. Cohen. Embedding and function extension on directed graph. Signal Processing, 111:137–149, 2015.
  22. 22.C. C. Paige and M. A. Saunders. Towards a generalized singular value decomposition. SIAM Journal on Numerical Analysis, 18(3):398–405, 1981.
  23. 23.J. Pennington, R. Socher, and C. D. Manning. Glove: Global vectors for word representation. Proceedings of the Empiricial Methods in Natural Language Processing (EMNLP 2014), 12:1532–1543, 2014.
  24. 24.B. Perozzi, R. Al-Rfou, and S. Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701–710. ACM, 2014.
  25. 25.D. Perrault-Joncas and M. Meila. Estimating vector fields on manifolds and the embedding of directed graphs. arXiv preprint arXiv:1406.0013, 2014.
  26. 26.D. C. Perrault-Joncas and M. Meila. Directed graph embedding: an algorithm based on continuous limits of laplacian-type operators. In Advances in Neural Information Processing Systems, pages 990–998, 2011.
  27. 27.S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323–2326, 2000.
  28. 28.B. Scholkopft and K.-R. Mullert. Fisher discriminant analysis with kernels. Neural networks for signal processing IX, 1:1, 1999.
  29. 29.T. A. Snijders, P. E. Pattison, G. L. Robins, and M. S. Handcock. New specifications for exponential random graph models. Sociological methodology, 36(1):99–153, 2006.
  30. 30.H. H. Song, T. W. Cho, V. Dave, Y. Zhang, and L. Qiu. Scalable proximity estimation and link prediction in online social networks. In Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference, pages 322–335. ACM, 2009.
  31. 31.L. Šubelj and M. Bajec. Model of complex networks based on citation dynamics. In Proceedings of the 22nd international conference on World Wide Web companion, pages 527–530. International World Wide Web Conferences Steering Committee, 2013.
  32. 32.J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei. Line: Large-scale information network embedding. In Proceedings of the 24th International Conference on World Wide Web, pages 1067–1077. International World Wide Web Conferences Steering Committee, 2015.
  33. 33.J. B. Tenenbaum, V. De Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319–2323, 2000.
  34. 34.Y. J. Wang and G. Y. Wong. Stochastic blockmodels for directed graphs. Journal of the American Statistical Association, 82(397):8–19, 1987.
  35. 35.S. Yan, D. Xu, B. Zhang, H.-J. Zhang, Q. Yang, and S. Lin. Graph embedding and extensions: a general framework for dimensionality reduction. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 29(1):40–51, 2007.
  36. 36.J. Ye, R. Janardan, and Q. Li. Two-dimensional linear discriminant analysis. In Advances in neural information processing systems, pages 1569–1576, 2004.
  37. 37.S. Zhu, K. Yu, Y. Chi, and Y. Gong. Combining content and link for classification using matrix factorization. In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 487–494. ACM, 2007.

Citation

MLA
Ou, M., et al. “Asymmetric Transitivity Preserving Graph Embedding”. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016, pp. 1105–14, https://doi.org/10.1145/2939672.2939751.
APA
Ou, M., Cui, P., Pei, J., Zhang, Z., & Zhu, W. (2016). Asymmetric Transitivity Preserving Graph Embedding. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1105–1114. https://doi.org/10.1145/2939672.2939751
Chicago
Ou, M., P. Cui, J. Pei, Z. Zhang, and W. Zhu. 2016. “Asymmetric Transitivity Preserving Graph Embedding”. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1105–14. https://doi.org/10.1145/2939672.2939751.
Harvard
Ou, M. et al. (2016) “Asymmetric Transitivity Preserving Graph Embedding”, Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, pp. 1105–1114. Available at: https://doi.org/10.1145/2939672.2939751.
Vancouver
1. Ou M, Cui P, Pei J, Zhang Z, Zhu W (2016) Asymmetric Transitivity Preserving Graph Embedding. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, pp 1105–1114

BibTeX

@inproceedings{Ou_2016, series={KDD ’16}, title={Asymmetric Transitivity Preserving Graph Embedding}, url={http://dx.doi.org/10.1145/2939672.2939751}, DOI={10.1145/2939672.2939751}, booktitle={Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining}, publisher={ACM}, author={Ou, Mingdong and Cui, Peng and Pei, Jian and Zhang, Ziwei and Zhu, Wenwu}, year={2016}, month=Aug, pages={1105–1114}, collection={KDD ’16} }
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