Deep Neural Networks for Learning Graph Representations

TLDR

The paper proposes a novel model that learns low‑dimensional vertex representations by capturing graph structure, with both theoretical and empirical validation. The model uses a random‑surfing approach to directly encode graph structure, interprets the PMI matrix as the analytical solution of a skip‑gram objective, replaces SVD with a stacked denoising autoencoder to capture non‑linearities, and evaluates the representations on clustering and visualization tasks. Experiments on datasets of varying sizes demonstrate that the proposed method outperforms state‑of‑the‑art models in clustering and visualization. Citations include (2014) and (2013).

Abstract

In this paper, we propose a novel model for learning graph representations, which generates a low-dimensional vector representation for each vertex by capturing the graph structural information. Different from other previous research efforts, we adopt a random surfing model to capture graph structural information directly, instead of using the sampling-based method for generating linear sequences proposed by Perozzi et al. (2014). The advantages of our approach will be illustrated from both theorical and empirical perspectives. We also give a new perspective for the matrix factorization method proposed by Levy and Goldberg (2014), in which the pointwise mutual information (PMI) matrix is considered as an analytical solution to the objective function of the skip-gram model with negative sampling proposed by Mikolov et al. (2013). Unlike their approach which involves the use of the SVD for finding the low-dimensitonal projections from the PMI matrix, however, the stacked denoising autoencoder is introduced in our model to extract complex features and model non-linearities. To demonstrate the effectiveness of our model, we conduct experiments on clustering and visualization tasks, employing the learned vertex representations as features. Empirical results on datasets of varying sizes show that our model outperforms other stat-of-the-art models in such tasks.