Back

Representation Learning on Graphs: Methods and Applications

William L. HamiltonRex YingJure Leskovec

article2017IEEE Data Engineering Bulletin2,178 citations

Develops a unified conceptual framework for graph representation learning that systematically categorizes node and whole-graph embedding techniques across matrix factorization, random walks, and graph neural networks for machine learning applications.

correlation analysisdeep learninggraph neural networksrepresentation learning on graphsgraph embeddingsnode embeddings
arXiv: 1709.05584
  • Paper: Semi-Supervised Classification with Graph Convolutional Networks, Thomas N. Kipf et al. (2017). This landmark paper directly builds on the 2017 review by introducing the specific graph convolutional network architecture that dominates semi-supervised node classification today.
  • Paper: How Powerful are Graph Neural Networks?, Keyulu Xu et al. (2019). Reading this work after the review provides a deeper theoretical critique of the representational limits of standard graph neural networks through the Weisfeiler-Lehman test.
  • Paper: Graph Attention Networks, Petar Veličković et al. (2018). This follow-up paper extends the review's discussion of graph neural networks by introducing self-attention mechanisms to dynamically weight neighbor importance.
Cover for Representation Learning on Graphs: Methods and Applications

Abstract

Machine learning on graphs is an important and ubiquitous task with applications ranging from drug design to friendship recommendation in social networks. The primary challenge in this domain is finding a way to represent, or encode, graph structure so that it can be easily exploited by machine learning models. Traditionally, machine learning approaches relied on user-defined heuristics to extract features encoding structural information about a graph (e.g., degree statistics or kernel functions). However, recent years have seen a surge in approaches that automatically learn to encode graph structure into low-dimensional embeddings, using techniques based on deep learning and nonlinear dimensionality reduction. Here we provide a conceptual review of key advancements in this area of representation learning on graphs, including matrix factorization-based methods, random-walk based algorithms, and graph neural networks. We review methods to embed individual nodes as well as approaches to embed entire (sub)graphs. In doing so, we develop a unified framework to describe these recent approaches, and we highlight a number of important applications and directions for future work.

Topics

correlation analysisdeep learninggraph neural networkskernel functionmatrix factorizationsnonlinear dimensionality reductionrandom walkrangingrecommendationrepresentation learning

Keywords

representation learning on graphsgraph embeddingsnode embeddingssubgraph embeddingsgraph kernelsnode classificationsubgraph classificationknowledge graphsgraph Laplacianprotein-protein interaction graphs

Table of Contents

  • 1 Introduction
  • 1.1 Notation and essential assumptions
  • 2 Embedding nodes
  • 2.1 Overview of approaches: An encoder-decoder perspective
  • 2.1.1 Notes on optimization and implementation details
  • 2.2 Shallow embedding approaches
  • 2.2.1 Factorization-based approaches
  • 2.2.2 Random walk approaches
  • 2.3 Generalized encoder-decoder architectures
  • 2.3.1 Neighborhood autoencoder methods
  • 2.3.2 Neighborhood aggregation and convolutional encoders
  • 2.4 Incorporating task-specific supervision
  • 2.5 Extensions to multi-modal graphs
  • 2.5.1 Dealing with different node and edge types
  • 2.5.2 Tying node embeddings across layers
  • 2.6 Embedding structural roles
  • 2.7 Applications of node embeddings
  • 3 Embedding subgraphs
  • 3.1 Sets of node embeddings and convolutional approaches
  • 3.1.1 Sum-based approaches
  • 3.1.2 Graph-coarsening approaches
  • 3.1.3 Further variations
  • 3.2 Graph neural networks
  • 3.3 Applications of subgraph embeddings
  • 4 Conclusion and future directions
  • 4.1 Challenges to future progress
  • 4.2 Important open problems
  • References

Knowls

  1. Knowl 1 — Encoder-Decoder Framework for Node Embedding

    model/method

    The encoder-decoder framework unifies diverse node representation learning algorithms on an undirected graph G=(V,E)\mathcal{G} = (\mathcal{V}, \mathcal{E}) with adjacency matrix A∈{0,1}∣V∣×∣V∣\mathbf{A} \in \{0, 1\}^{|\mathcal{V}| \times |\mathcal{V}|} and optional node feature matrix X∈Rm×∣V∣\mathbf{X} \in \mathbb{R}^{m \times |\mathcal{V}|}. The framework decomposes embedding algorithms into four methodological components:

    1. Pairwise graph similarity function sG:V×V→R+s_{\mathcal{G}}: \mathcal{V} \times \mathcal{V} \to \mathbb{R}^+, which quantifies the structural or semantic proximity between nodes in G\mathcal{G} (e.g., direct adjacency Ai,j\mathbf{A}_{i,j}, multi-hop transition matrices, or random-walk co-occurrence probabilities).

    2. Encoder function ENC:V→Rd\text{ENC}: \mathcal{V} \to \mathbb{R}^d, parameterized by trainable weights ΘENC\Theta_{\text{ENC}}, mapping each node vi∈Vv_i \in \mathcal{V} to a low-dimensional vector zi∈Rd\mathbf{z}_i \in \mathbb{R}^d where d≪∣V∣d \ll |\mathcal{V}|.

    3. Decoder function DEC:Rd×Rd→R+\text{DEC}: \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}^+, mapping pairs of vector embeddings (zi,zj)(\mathbf{z}_i, \mathbf{z}_j) to a reconstructed pairwise similarity score DEC(zi,zj)≈sG(vi,vj)\text{DEC}(\mathbf{z}_i, \mathbf{z}_j) \approx s_{\mathcal{G}}(v_i, v_j).

    4. Loss function ℓ:R×R→R\ell: \mathbb{R} \times \mathbb{R} \to \mathbb{R}, which quantifies the discrepancy between reconstructed and target similarity values.

    Training minimizes the empirical loss over a set of sampled node pairs D\mathcal{D}:

    L=∑(vi,vj)∈Dℓ(DEC(zi,zj),sG(vi,vj))\mathcal{L} = \sum_{(v_i, v_j) \in \mathcal{D}} \ell\left(\text{DEC}(\mathbf{z}_i, \mathbf{z}_j), s_{\mathcal{G}}(v_i, v_j)\right)

    When supervised node labels yi∈{0,1}y_i \in \{0, 1\} are available, the unsupervised reconstruction objective can be replaced or augmented by a supervised classification cross-entropy loss:

    L=∑vi∈V(yilog⁡(σ(ENC(vi)⊤θ))+(1−yi)log⁡(1−σ(ENC(vi)⊤θ)))\mathcal{L} = \sum_{v_i \in \mathcal{V}} \left( y_i \log\left(\sigma\left(\text{ENC}(v_i)^\top \boldsymbol{\theta}\right)\right) + (1 - y_i) \log\left(1 - \sigma\left(\text{ENC}(v_i)^\top \boldsymbol{\theta}\right)\right) \right)

    where θ∈Rd\boldsymbol{\theta} \in \mathbb{R}^d is a trainable parameter vector and σ(x)=11+e−x\sigma(x) = \frac{1}{1 + e^{-x}} is the sigmoid activation function.

  2. Knowl 2 — Neighborhood-Aggregation Node Encoder Algorithm

    algorithm

    The neighborhood-aggregation (or convolutional) encoding algorithm computes node embeddings zv∈Rd\mathbf{z}_v \in \mathbb{R}^d for all nodes v∈Vv \in \mathcal{V} by recursively aggregating attribute information from local graph neighborhoods up to depth KK. Unlike shallow embeddings, parameters are shared across all nodes, enabling inductive generalization to unseen nodes and graphs.

    Input : Graph G(V,E)\mathcal{G}(\mathcal{V}, \mathcal{E}); node feature vectors {xv,∀v∈V}\{\mathbf{x}_v, \forall v \in \mathcal{V}\}; depth KK; weight matrices {Wk,∀k∈[1,K]}\{\mathbf{W}^k, \forall k \in [1, K]\}; non-linearity σ\sigma; differentiable aggregator functions {AGGREGATEk,∀k∈[1,K]}\{\text{AGGREGATE}_k, \forall k \in [1, K]\}; neighborhood function N:v→2V\mathcal{N}: v \to 2^\mathcal{V}
    Output: Vector representations zv\mathbf{z}_v for all v∈Vv \in \mathcal{V}
    hv0←xv,∀v∈V\mathbf{h}_v^0 \leftarrow \mathbf{x}_v, \forall v \in \mathcal{V}
    for k=1…Kk = 1 \dots K do
        for v∈Vv \in \mathcal{V} do
            hN(v)k←AGGREGATEk({huk−1,∀u∈N(v)})\mathbf{h}_{\mathcal{N}(v)}^k \leftarrow \text{AGGREGATE}_k(\{\mathbf{h}_u^{k-1}, \forall u \in \mathcal{N}(v)\})
            hvk←σ(Wk⋅COMBINE(hvk−1,hN(v)k))\mathbf{h}_v^k \leftarrow \sigma\left(\mathbf{W}^k \cdot \text{COMBINE}\left(\mathbf{h}_v^{k-1}, \mathbf{h}_{\mathcal{N}(v)}^k\right)\right)
        end
        hvk←NORMALIZE(hvk),∀v∈V\mathbf{h}_v^k \leftarrow \text{NORMALIZE}(\mathbf{h}_v^k), \forall v \in \mathcal{V}
    end
    zv←hvK,∀v∈V\mathbf{z}_v \leftarrow \mathbf{h}_v^K, \forall v \in \mathcal{V}

    Specific variants instantiate the COMBINE\text{COMBINE} and AGGREGATE\text{AGGREGATE} operators differently:

    • GraphSAGE concatenates hvk−1\mathbf{h}_v^{k-1} and hN(v)k\mathbf{h}_{\mathcal{N}(v)}^k in COMBINE\text{COMBINE}, using aggregators such as element-wise mean, max-pooling neural networks, or LSTMs.
    • Graph Convolutional Networks (GCNs) use a weighted element-wise mean for aggregation and a weighted sum for combination.
    • Column Networks apply an interpolation step before normalization: hvk←αhvk+(1−α)hvk−1\mathbf{h}_v^k \leftarrow \alpha \mathbf{h}_v^k + (1 - \alpha) \mathbf{h}_v^{k-1}, where α\alpha is a learned gating weight computed from hvk−1\mathbf{h}_v^{k-1} and hN(v)k−1\mathbf{h}_{\mathcal{N}(v)}^{k-1}.

  3. Knowl 3 — Random Walk-Based Shallow Node Embeddings

    model/method

    Random walk methods learn node embeddings zi∈Rd\mathbf{z}_i \in \mathbb{R}^d such that embedding dot products approximate the probability pG,T(vj∣vi)p_{\mathcal{G}, T}(v_j | v_i) of visiting node vjv_j on a length-TT random walk starting at node viv_i. The decoder uses a softmax formulation:

    DEC(zi,zj)=exp⁡(zi⊤zj)∑vk∈Vexp⁡(zi⊤zk)≈pG,T(vj∣vi)\text{DEC}(\mathbf{z}_i, \mathbf{z}_j) = \frac{\exp(\mathbf{z}_i^\top \mathbf{z}_j)}{\sum_{v_k \in \mathcal{V}} \exp(\mathbf{z}_i^\top \mathbf{z}_k)} \approx p_{\mathcal{G}, T}(v_j | v_i)

    Models minimize the cross-entropy loss over random-walk co-occurrence pairs D\mathcal{D}:

    L=∑(vi,vj)∈D−log⁡(DEC(zi,zj))\mathcal{L} = \sum_{(v_i, v_j) \in \mathcal{D}} -\log\left(\text{DEC}(\mathbf{z}_i, \mathbf{z}_j)\right)

    Because exact evaluation requires O(∣D∣∣V∣)O(|\mathcal{D}||\mathcal{V}|) time, computational approximations are used:

    • DeepWalk uses unbiased random walks (pG,Tp_{\mathcal{G}, T}) and accelerates normalization via hierarchical softmax over a binary tree of vertices.
    • node2vec optimizes the objective using negative sampling and employs 2nd-order biased random walks governed by two hyperparameters:
      • pp (return parameter): controls the probability of immediately returning to the previous node; high pp discourages 2-hop loops.
      • qq (in-out parameter): controls the ratio of exploring local micro-neighborhoods (breadth-first search, reflecting structural roles) versus venturing further outward (depth-first search, reflecting macro-community structure).

  4. Knowl 4 — Matrix Factorization Formulation of Shallow Embeddings

    model/method

    Matrix factorization node embedding algorithms represent the encoder as an embedding lookup ENC(vi)=Zvi\text{ENC}(v_i) = \mathbf{Z}\mathbf{v}_i, where Z∈Rd×∣V∣\mathbf{Z} \in \mathbb{R}^{d \times |\mathcal{V}|} is the embedding parameter matrix and vi∈R∣V∣\mathbf{v}_i \in \mathbb{R}^{|\mathcal{V}|} is a one-hot indicator vector for node viv_i.

    Using an inner-product decoder DEC(zi,zj)=zi⊤zj\text{DEC}(\mathbf{z}_i, \mathbf{z}_j) = \mathbf{z}_i^\top \mathbf{z}_j and mean squared error (MSE) loss, the general objective factorizes a target similarity matrix S∈R∣V∣×∣V∣\mathbf{S} \in \mathbb{R}^{|\mathcal{V}| \times |\mathcal{V}|} where Si,j=sG(vi,vj)\mathbf{S}_{i,j} = s_{\mathcal{G}}(v_i, v_j):

    L=∑(vi,vj)∈D∥zi⊤zj−sG(vi,vj)∥22≈∥Z⊤Z−S∥22\mathcal{L} = \sum_{(v_i, v_j) \in \mathcal{D}} \|\mathbf{z}_i^\top \mathbf{z}_j - s_{\mathcal{G}}(v_i, v_j)\|_2^2 \approx \|\mathbf{Z}^\top \mathbf{Z} - \mathbf{S}\|_2^2

    Algorithms differ in their definition of sG(vi,vj)s_{\mathcal{G}}(v_i, v_j):

    • Laplacian Eigenmaps (LE) uses distance decoder DEC(zi,zj)=∥zi−zj∥22\text{DEC}(\mathbf{z}_i, \mathbf{z}_j) = \|\mathbf{z}_i - \mathbf{z}_j\|_2^2 and loss L=∑(vi,vj)∈D∥zi−zj∥22⋅sG(vi,vj)\mathcal{L} = \sum_{(v_i, v_j) \in \mathcal{D}} \|\mathbf{z}_i - \mathbf{z}_j\|_2^2 \cdot s_{\mathcal{G}}(v_i, v_j).
    • Graph Factorization (GF) sets sG(vi,vj)=Ai,js_{\mathcal{G}}(v_i, v_j) = \mathbf{A}_{i,j} (first-order similarity).
    • GraRep defines similarity across powers of the adjacency matrix Ai,j,Ai,j2,…,Ai,jk\mathbf{A}_{i,j}, \mathbf{A}^2_{i,j}, \dots, \mathbf{A}^k_{i,j} (higher-order similarity).
    • HOPE factorizes generalized neighborhood similarity matrices such as Jaccard coefficients.

  5. Knowl 5 — Methodological Comparison of Shallow Node Embedding Algorithms

    data/table

    The encoder-decoder perspective organizes shallow embedding algorithms by their pairwise decoder DEC(zi,zj)\text{DEC}(\mathbf{z}_i, \mathbf{z}_j), their graph similarity measure sG(vi,vj)s_{\mathcal{G}}(v_i, v_j), and their loss function ℓ\ell:

    Type Method Decoder Similarity measure Loss function (ℓ\ell)
    Matrix Laplacian Eigenmaps ∥zi−zj∥22\|\mathbf{z}_i - \mathbf{z}_j\|_2^2 general DEC(zi,zj)⋅sG(vi,vj)\text{DEC}(\mathbf{z}_i, \mathbf{z}_j) \cdot s_{\mathcal{G}}(v_i, v_j)
    factorization Graph Factorization zi⊤zj\mathbf{z}_i^\top \mathbf{z}_j Ai,j\mathbf{A}_{i,j} ∥DEC(zi,zj)−sG(vi,vj)∥22\|\text{DEC}(\mathbf{z}_i, \mathbf{z}_j) - s_{\mathcal{G}}(v_i, v_j)\|_2^2
    GraRep zi⊤zj\mathbf{z}_i^\top \mathbf{z}_j Ai,j,Ai,j2,…,Ai,jk\mathbf{A}_{i,j}, \mathbf{A}_{i,j}^2, \dots, \mathbf{A}_{i,j}^k ∥DEC(zi,zj)−sG(vi,vj)∥22\|\text{DEC}(\mathbf{z}_i, \mathbf{z}_j) - s_{\mathcal{G}}(v_i, v_j)\|_2^2
    HOPE zi⊤zj\mathbf{z}_i^\top \mathbf{z}_j general ∥DEC(zi,zj)−sG(vi,vj)∥22\|\text{DEC}(\mathbf{z}_i, \mathbf{z}_j) - s_{\mathcal{G}}(v_i, v_j)\|_2^2
    Random walk DeepWalk ezi⊤zj∑k∈Vezi⊤zk\frac{e^{\mathbf{z}_i^\top \mathbf{z}_j}}{\sum_{k \in \mathcal{V}} e^{\mathbf{z}_i^\top \mathbf{z}_k}} pG(vj∣vi)p_{\mathcal{G}}(v_j | v_i) −sG(vi,vj)log⁡(DEC(zi,zj))-s_{\mathcal{G}}(v_i, v_j) \log(\text{DEC}(\mathbf{z}_i, \mathbf{z}_j))
    node2vec ezi⊤zj∑k∈Vezi⊤zk\frac{e^{\mathbf{z}_i^\top \mathbf{z}_j}}{\sum_{k \in \mathcal{V}} e^{\mathbf{z}_i^\top \mathbf{z}_k}} pG(vj∣vi)p_{\mathcal{G}}(v_j | v_i) (biased) −sG(vi,vj)log⁡(DEC(zi,zj))-s_{\mathcal{G}}(v_i, v_j) \log(\text{DEC}(\mathbf{z}_i, \mathbf{z}_j))

    This comparison demonstrates that matrix factorization methods optimize symmetric, deterministic graph similarities under Euclidean or MSE penalties, whereas random-walk algorithms optimize stochastic, asymmetric visitation probabilities under cross-entropy objectives.

  6. Knowl 6 — Limitations of Shallow Graph Embedding Architectures

    limitation

    Shallow embedding methods, where the encoder is a lookup function ENC(vi)=Zvi\text{ENC}(v_i) = \mathbf{Z}\mathbf{v}_i parameterized directly by the embedding matrix Z∈Rd×∣V∣\mathbf{Z} \in \mathbb{R}^{d \times |\mathcal{V}|}, exhibit three fundamental limitations:

    1. Lack of Parameter Sharing: No parameters are shared across nodes in the encoder. The number of trainable parameters scales linearly as O(∣V∣)O(|\mathcal{V}|), which is computationally inefficient on massive graphs and eliminates regularization benefits that parameter sharing provides.
    2. Inability to Leverage Node Attributes: The encoder relies purely on arbitrary node IDs and cannot incorporate rich node attribute information X∈Rm×∣V∣\mathbf{X} \in \mathbb{R}^{m \times |\mathcal{V}|} (such as text, user profiles, or molecular features) during representation learning.
    3. Transductive Restriction: Shallow methods cannot generate embeddings for nodes that were unseen during training without re-running optimization over the entire updated graph, rendering them unsuitable for evolving graphs, streaming data, and cross-graph transfer learning.

  7. Knowl 7 — Message Passing Neural Networks and Recurrent GNN Abstractions

    model/method

    Graph Neural Networks (GNNs) generate representations by treating graphs as scaffolding for neural message passing over iterations k=1,…,Kk = 1, \dots, K:

    • Original GNNs: Nodes accumulate states via a contraction map h:Rd×Rm×Rm→Rdh: \mathbb{R}^d \times \mathbb{R}^m \times \mathbb{R}^m \to \mathbb{R}^d iterated to convergence before decoding zvi=g(hiK)\mathbf{z}_{v_i} = g(\mathbf{h}_i^K):

    hik=∑vj∈N(vi)h(hjk−1,xi,xj)\mathbf{h}_i^k = \sum_{v_j \in \mathcal{N}(v_i)} h\left(\mathbf{h}_j^{k-1}, \mathbf{x}_i, \mathbf{x}_j\right)

    • Gated Graph Neural Networks (GGNNs): Replace contraction mapping with modern gated recurrent units unrolled via backpropagation through time, initializing hi0=xi\mathbf{h}_i^0 = \mathbf{x}_i:

    hik=GRU(hik−1,∑vj∈N(vi)Whjk−1)\mathbf{h}_i^k = \text{GRU}\left(\mathbf{h}_i^{k-1}, \sum_{v_j \in \mathcal{N}(v_i)} \mathbf{W}\mathbf{h}_j^{k-1}\right)

    where W∈Rd×d\mathbf{W} \in \mathbb{R}^{d \times d} is a trainable weight matrix.

    • Message Passing Neural Networks (MPNNs): Abstract message calculation and node updates into general differentiable functions q:Rd×Rd→Rd′q: \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}^{d'} and U:Rd×Rd′→RdU: \mathbb{R}^d \times \mathbb{R}^{d'} \to \mathbb{R}^d:

    hik=U(hik−1,∑vj∈N(vi)q(hik−1,hjk−1))\mathbf{h}_i^k = U\left(\mathbf{h}_i^{k-1}, \sum_{v_j \in \mathcal{N}(v_i)} q\left(\mathbf{h}_i^{k-1}, \mathbf{h}_j^{k-1}\right)\right)

  8. Knowl 8 — Structural Role Node Embeddings: struc2vec and GraphWave

    model/method

    Structural role embedding algorithms learn representations that capture a node's local topological role (e.g., hub, bridge, or peripheral node) invariant to its global community membership or absolute position in G\mathcal{G}:

    • struc2vec: Constructs a hierarchy of weighted auxiliary graphs Gk′\mathcal{G}'_k for k=1,2,…k = 1, 2, \dots, where edge weights wk(vi,vj)w_k(v_i, v_j) capture the similarity between the ordered degree sequences Rk(vi)R_k(v_i) of nodes located at exact distance kk from viv_i and vjv_j via dynamic time warping (DTW):

    wk(vi,vj)=wk−1(vi,vj)+d(Rk(vi),Rk(vj)),w0(vi,vj)=0w_k(v_i, v_j) = w_{k-1}(v_i, v_j) + d\left(R_k(v_i), R_k(v_j)\right), \quad w_0(v_i, v_j) = 0

    Biased random walks are subsequently run over Gk′\mathcal{G}'_k and fed into a skip-gram optimizer.

    • GraphWave: Uses spectral graph wavelets with the unnormalized graph Laplacian L=D−A\mathbf{L} = \mathbf{D} - \mathbf{A}, where D\mathbf{D} is the degree diagonal matrix, U\mathbf{U} is the eigenvector matrix of L\mathbf{L}, and g(λ)=e−sλg(\lambda) = e^{-s\lambda} is a heat kernel with scale ss. For indicator vector vi\mathbf{v}_i, the structural role embedding is computed as:

    ψvi=UGU⊤vi\boldsymbol{\psi}_{v_i} = \mathbf{U} \mathbf{G} \mathbf{U}^\top \mathbf{v}_i

    where G=diag([g(λ1),…,g(λ∣V∣)])\mathbf{G} = \text{diag}\left([g(\lambda_1), \dots, g(\lambda_{|\mathcal{V}|})]\right). Structurally equivalent nodes map to identical representations in embedding space.

  9. Knowl 9 — Subgraph and Whole-Graph Embedding Methods

    model/method

    To represent an entire graph or induced subgraph G[S]\mathcal{G}[S] (S⊆VS \subseteq \mathcal{V}) as a continuous vector zS∈Rd\mathbf{z}_S \in \mathbb{R}^d, methods aggregate the embeddings of constituent nodes generated by neighborhood aggregation:

    1. Sum Pooling: Aggregates all node embeddings in SS via an element-wise sum:

    zS=∑vi∈Szi\mathbf{z}_S = \sum_{v_i \in S} \mathbf{z}_i

    1. Edge-Based Aggregation: Constructs intermediate edge embeddings ηi,jk\boldsymbol{\eta}_{i,j}^k using message passing inspired by Loopy Belief Propagation, and aggregates these to obtain node representations before final summation over SS.

    2. Graph Coarsening: Hierarchically clusters nodes into supernodes using graph clustering, performs element-wise max-pooling over cluster representations, and stacks successive graph convolutional and coarsening layers.

    3. Ordered Graph Convolutions: Imposes a deterministic canonical ordering on nodes (e.g., via graph coloring algorithms), concatenates ordered node embeddings, and applies standard 1D/2D convolutional networks.

    4. Virtual Super-Nodes: Introduces an auxiliary dummy node connected to every node in G[S]\mathcal{G}[S] and extracts its final state as zS\mathbf{z}_S.

  10. Knowl 10 — Multi-Modal and Multi-Layer Graph Embeddings

    model/method

    Graph representation learning extends to heterogeneous and multi-layer graphs through relation-specific parameters and cross-layer regularization:

    • Heterogeneous Relation Decoders: For graphs containing multiple edge types τ\tau, pairwise decoders employ relation-specific bilinear parameter matrices Aτ\mathbf{A}_\tau:

    DECτ(zi,zj)=zi⊤Aτzj\text{DEC}_\tau(\mathbf{z}_i, \mathbf{z}_j) = \mathbf{z}_i^\top \mathbf{A}_\tau \mathbf{z}_j

    • Cross-Layer Embedding Tying (OhmNet): In multi-layer networks where the same entity appears across multiple graph layers G1,G2\mathcal{G}_1, \mathcal{G}_2, representations are tied using an L2L_2 regularization penalty added to the base embedding loss L(vi)\mathcal{L}(v_i):

    L(vi)′=L(vi)+λ∥ziG1−ziG2∥2\mathcal{L}(v_i)' = \mathcal{L}(v_i) + \lambda \|\mathbf{z}_i^{\mathcal{G}_1} - \mathbf{z}_i^{\mathcal{G}_2}\|_2

    where λ\lambda controls regularization strength. For hierarchically organized layers, this penalty is applied recursively between parent and child layers.

  11. Knowl 11 — Neighborhood Autoencoder Node Embeddings

    model/method

    Neighborhood autoencoders (such as DNGR and SDNE) compress a node's high-dimensional neighborhood proximity vector si∈R∣V∣\mathbf{s}_i \in \mathbb{R}^{|\mathcal{V}|} into a low-dimensional vector zi=ENC(si)∈Rd\mathbf{z}_i = \text{ENC}(\mathbf{s}_i) \in \mathbb{R}^d using deep autoencoders with a unary reconstruction decoder:

    DEC(ENC(si))=DEC(zi)≈si\text{DEC}(\text{ENC}(\mathbf{s}_i)) = \text{DEC}(\mathbf{z}_i) \approx \mathbf{s}_i

    The autoencoder is trained using a reconstruction loss:

    L=∑vi∈V∥DEC(zi)−si∥22\mathcal{L} = \sum_{v_i \in \mathcal{V}} \|\text{DEC}(\mathbf{z}_i) - \mathbf{s}_i\|_2^2

    • DNGR defines si\mathbf{s}_i via the pointwise mutual information (PMI) of random walk co-occurrences.
    • SDNE sets si=Ai\mathbf{s}_i = \mathbf{A}_i (the ii-th row of the adjacency matrix) and adds the Laplacian Eigenmaps objective ∑(vi,vj)∥zi−zj∥22Ai,j\sum_{(v_i, v_j)} \|\mathbf{z}_i - \mathbf{z}_j\|_2^2 \mathbf{A}_{i,j} to jointly preserve 1st-order and 2nd-order proximity.

    While neighborhood autoencoders incorporate graph structure into the encoder non-linearly, their input dimension is fixed at ∣V∣|\mathcal{V}|, making them transductive and computationally expensive for graphs with millions of nodes.

Coverage note — Omitted high-level summaries of broad subfields cited by the authors as distinct or parallel paradigms (e.g., classical manifold learning, statistical relational learning, and traditional hand-crafted graph kernel functions), as well as domain-specific downstream application details, to focus entirely on the unified representation learning framework, its algorithms, and mathematical formulations.

References

  1. 1.A. Ahmed, N. Shervashidze, S. Narayanamurthy, V. Josifovski, and A.J. Smola. Distributed large-scale natural graph factorization. In WWW, 2013.
  2. 2.R. Angles and C. Gutierrez. Survey of graph database models. ACM Computing Surveys, 40(1):1, 2008.
  3. 3.L. Backstrom and J. Leskovec. Supervised random walks: predicting and recommending links in social networks. In WSDM, 2011.
  4. 4.M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In NIPS, 2002.
  5. 5.A.R. Benson, D.F. Gleich, and J. Leskovec. Higher-order organization of complex networks. Science, 353(6295):163–166, 2016.
  6. 6.S. Bhagat, G. Cormode, and S. Muthukrishnan. Node classification in social networks. In Social Network Data Analytics, pages 115–148. 2011.
  7. 7.M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst. Geometric deep learning: Going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18–42, 2017.
  8. 8.J. Bruna, W. Zaremba, and Y. Szlam, A.and LeCun. Spectral networks and locally connected networks on graphs. In ICLR, 2014.
  9. 9.S. Cao, W. Lu, and Q. Xu. Grarep: Learning graph representations with global structural information. In KDD, 2015.
  10. 10.S. Cao, W. Lu, and Q. Xu. Deep neural networks for learning graph representations. In AAAI, 2016.
  11. 11.B.P. Chamberlain, J. Clough, and M.P. Deisenroth. Neural embeddings of graphs in hyperbolic space. arXiv preprint arXiv:1705.10359, 2017.
  12. 12.S. Chang, W. Han, J. Tang, G. Qi, C.C. Aggarwal, and T.S. Huang. Heterogeneous network embedding via deep architectures. In KDD, 2015.
  13. 13.H. Chen, B. Perozzi, Y. Hu, and S. Skiena. Harp: Hierarchical representation learning for networks. arXiv preprint arXiv:1706.07845, 2017.
  14. 14.K. Cho, B. Van Merriënboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. In EMNLP, 2014.
  15. 15.Fan RK Chung. Spectral Graph Theory. Number 92. American Mathematical Soc., 1997.
  16. 16.H. Dai, B. Dai, and L. Song. Discriminative embeddings of latent variable models for structured data. In ICML, 2016.
  17. 17.M.C.F. De Oliveira and H. Levkowitz. From visual data exploration to visual data mining: a survey. IEEE Transactions on Visualization and Computer Graphics, 9(3):378–394, 2003.
  18. 18.M. Defferrard and P. Bresson, X.and Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, 2016.
  19. 19.Y. Dong, N.V. Chawla, and A. Swami. metapath2vec: Scalable representation learning for heterogeneous networks. In KDD, 2017.
  20. 20.C. Donnat, M. Zitnik, D. Hallac, and J. Leskovec. Learning structural node embeddings via diffusion wavelets. arXiv preprint arXiv:1710.10321, 2017.
  21. 21.D. Duvenaud, D. Maclaurin, J. Iparraguirre, R. Bombarell, T. Hirzel, A. Aspuru-Guzik, and R.P. Adams. Convolutional networks on graphs for learning molecular fingerprints. In NIPS, 2015.
  22. 22.M. Ester, H. Kriegel, J. Sander, X. Xu, et al. A density-based algorithm for discovering clusters in large spatial databases with noise. In KDD, 1996.
  23. 23.S. Fortunato. Community detection in graphs. Physics Reports, 486(3):75–174, 2010.
  24. 24.L. Getoor and B. Taskar. Introduction to Statistical Relational Learning. MIT press, 2007.
  25. 25.J. Gilmer, S.S. Schoenholz, P.F. Riley, O. Vinyals, G.E. Dahl. Neural Message Passing for Quantum Chemistry. In ICML, 2017.
  26. 26.M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In IEEE International Joint Conference on Neural Networks, 2005.
  27. 27.P. Goyal and E. Ferrara. Graph embedding techniques, applications, and performance: A survey. arXiv preprint arXiv:1605.09096, 2017.
  28. 28.A. Grover and J. Leskovec. node2vec: Scalable feature learning for networks. In KDD, 2016.
  29. 29.W.L. Hamilton, R. Ying, and J. Leskovec. Inductive representation learning on large graphs. arXiv preprint, arXiv:1603.04467, 2017.
  30. 30.K. Henderson, B. Gallagher, T. Eliassi-Rad, H. Tong, S. Basu, L. Akoglu, D. Koutra, C. Faloutsos, and L. Li. Rolx: structural role extraction & mining in large graphs. In KDD, 2012.
  31. 31.G. Hinton and R. Salakhutdinov. Reducing the dimensionality of data with neural networks. Science, 313(5786):504–507, 2006.
  32. 32.S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural Computation, 9(8):1735–1780, 1997.
  33. 33.P. Hoff, A.E. Raftery, and M.S. Handcock. Latent space approaches to social network analysis. JASA, 97(460):1090–1098, 2002.
  34. 34.S. Kearnes, K. McCloskey, M. Berndl, V. Pande, and P. Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of Computer-Aided Molecular Design, 30(8):595–608, 2016.
  35. 35.T.N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2016.
  36. 36.T.N. Kipf and M. Welling. Variational graph auto-encoders. In NIPS Workshop on Bayesian Deep Learning, 2016.
  37. 37.J.B. Kruskal. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika, 29(1):1–27, 1964.
  38. 38.J.A. Lee and M. Verleysen. Nonlinear dimensionality reduction. Springer Science & Business Media, 2007.
  39. 39.Y. Li, D. Tarlow, M. Brockschmidt, and R. Zemel. Gated graph sequence neural networks. In ICLR, 2015.
  40. 40.D. Liben-Nowell and J. Kleinberg. The link-prediction problem for social networks. Journal of the Association for Information Science and Technology, 58(7):1019–1031, 2007.
  41. 41.Q. Lu and L. Getoor. Link-based classification. In ICML, volume 3, pages 496–503, 2003.
  42. 42.K. Murphy, Y. Weiss, and M. Jordan. Loopy belief propagation for approximate inference: An empirical study. In UAI, 1999.
  43. 43.M. Nickel, K. Murphy, V. Tresp, and E. Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 104(1):11–33, 2016.
  44. 44.M. Niepert, M. Ahmed, and K. Kutzkov. Learning convolutional neural networks for graphs. In ICML, 2016.
  45. 45.M. Ou, P. Cui, J. Pei, Z. Zhang, and W. Zhu. Asymmetric transitivity preserving graph embedding. In KDD, 2016.
  46. 46.A. Paranjape, A. R. Benson, and J. Leskovec. Motifs in temporal networks. In WSDM, 2017.
  47. 47.B. Perozzi, R. Al-Rfou, and S. Skiena. Deepwalk: Online learning of social representations. In KDD, 2014.
  48. 48.B. Perozzi, V. Kulkarni, and S. Skiena. Walklets: Multiscale graph embeddings for interpretable network classification. arXiv preprint arXiv:1605.02115, 2016.
  49. 49.Bryan Perozzi. Local Modeling of Attributed Graphs: Algorithms and Applications. PhD thesis, Stony Brook University, 2016.
  50. 50.T. Pham, T. Tran, D.Q. Phung, and S. Venkatesh. Column networks for collective classification. In AAAI, 2017.
  51. 51.L.F.R. Ribeiro, P.H.P. Saverese, and D.R. Figueiredo. struc2vec: Learning node representations from structural identity. In KDD, 2017.
  52. 52.F. Scarselli, M. Gori, A.C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61–80, 2009.
  53. 53.M. Schlichtkrull, T.N. Kipf, P. Bloem, R. van den Berg, I. Titov, and M. Welling. Modeling relational data with graph convolutional networks. arXiv preprint arXiv:1703.06103, 2017.
  54. 54.J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei. Line: Large-scale information network embedding. In WWW, 2015.
  55. 55.J. Tenenbaum, V. De Silva, and J. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319–2323, 2000.
  56. 56.R. van den Berg, T.N. Kipf, and M. Welling. Graph convolutional matrix completion. arXiv preprint arXiv:1706.02263, 2017.
  57. 57.L. van der Maaten and G. Hinton. Visualizing data using t-sne. JMLR, 9:2579–2605, 2008.
  58. 58.S.V.N. Vishwanathan, N.N. Schraudolph, R. Kondor, and K.M. Borgwardt. Graph kernels. JMLR, 11:1201–1242, 2010.
  59. 59.D. Wang, P. Cui, and W. Zhu. Structural deep network embedding. In KDD, 2016.
  60. 60.Z. Yang, W. Cohen, and R. Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In ICML, 2016.
  61. 61.M. Zitnik and J. Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 2017.

Citation

MLA
Hamilton, W. L., et al. “Representation Learning on Graphs: Methods and Applications”. arXiv, 2017, http://arxiv.org/abs/1709.05584v3.
APA
Hamilton, W. L., Ying, R., & Leskovec, J. (2017). Representation Learning on Graphs: Methods and Applications. arXiv. http://arxiv.org/abs/1709.05584v3
Chicago
Hamilton, W. L., R. Ying, and J. Leskovec. 2017. “Representation Learning on Graphs: Methods and Applications”. arXiv. http://arxiv.org/abs/1709.05584v3.
Harvard
Hamilton, W.L., Ying, R. and Leskovec, J. (2017) “Representation Learning on Graphs: Methods and Applications”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1709.05584v3.
Vancouver
1. Hamilton WL, Ying R, Leskovec J (2017) Representation Learning on Graphs: Methods and Applications. arXiv

BibTeX

@article{hamilton2017representation,
  title = {Representation Learning on Graphs: Methods and Applications},
  author = {Hamilton, William L. and Ying, Rex and Leskovec, Jure},
  year = {2017},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1709.05584v3},
  eprint = {1709.05584}
}
Metadata:arXiv

Access the Paper

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

Open PDF