---
kind: concept
slug: node-embedding
title: Node embedding
summary: >-
  Maps every node of a graph to a fixed-length vector so that ordinary classifiers and regressors can predict node properties. Four families in the sources, from random-walk skip-gram to a GNN inside a language model. Evidence is four author-reported papers on different tasks, plus a survey with no numbers, so the families cannot be ranked against each other.
tags: [graphs, node-embedding, unsupervised, self-supervised, random-walk, multiplex-networks, textual-graph]
papers: ["1909.13021", "2102.07810", "2104.04883", "2105.00696", "2105.02605", "2204.01855"]
related: [attributed-network-embedding, graph-neural-network, self-supervised-learning, skip-gram-negative-sampling, dynamic-graph-embedding, contrastive-learning, knowledge-graph-embedding]
status: draft
updated_at: 2026-11-01
---

## Overview

A node embedding maps each node of a graph to a short vector, so that a plain
classifier or regressor can predict node properties from it [arxiv:1909.13021 §1].
The survey states the same goal as keeping similar nodes close in the vector
space [arxiv:2204.01855 §2.1]. Four families appear in the cited sources. They
differ in their inputs and in what they optimise:

- **Structure-only proximity.** Uses only the links. DeepWalk, Node2Vec and
  Walklets are the structure-only methods in the comparison, and the survey's
  static traditional methods (factorization, random walks) also work from the
  graph structure [arxiv:1909.13021 §1] [arxiv:2204.01855 §3.1]. Their vectors
  for one graph cannot be related to those of another graph [arxiv:1909.13021 §1].
- **Attributed random-walk skip-gram.** Also takes a feature set per node. Random
  walks yield (node, feature) pairs, which are trained with skip-gram with
  negative sampling (SGNS) [arxiv:1909.13021 §3.1]. Detail is on
  [Attributed network embedding](/concepts/attributed-network-embedding).
- **Self-supervised GCN.** Takes attributes per node and trains a one-layer
  graph convolution without labels, using mutual-information terms that relate
  each embedding to a global summary and to the node's own attributes
  [arxiv:2102.07810 §3.1].
- **Text-attributed graphs.** Each node carries a text. A graph-attention step
  sits inside every layer of a language model, and the model is trained to
  predict links [arxiv:2105.02605 §3.1] [arxiv:2105.02605 §3.3].

A graph-learning survey places the same goal in a wider field. Its random-walk
family feeds walks to a word-embedding model, and its matrix-factorization
family uses the factors of a similarity matrix as embeddings
[arxiv:2105.00696 §2.3.1] [arxiv:2105.00696 §2.2].

Graphs that change over time form a fifth setting, covered under
[Dynamic graph embedding](/concepts/dynamic-graph-embedding) and in the variants
below.

A biomedical review uses the same term for shallow embeddings, and adds graph
neural networks and generative graph models as the other two families
[arxiv:2104.04883 §2]. Its examples are protein, gene, drug and patient networks.
It reports no numbers [arxiv:2104.04883 §1].

## Variants

### Structure-only proximity

DeepWalk, Node2Vec and Walklets are named as the baselines of the comparison and
as the structure-only family [arxiv:1909.13021 §1]. The 1909 card does not
describe their internals. The attributed methods below show that DeepWalk and
Walklets are the special cases in which each node's only feature is its own
identity [arxiv:1909.13021 §4.2, remarks 1-2]. The survey defines first-order
proximity (linked nodes) and second-order proximity (shared neighbours) for
these methods, and says Node2Vec biases its walk steps with two parameters
[arxiv:2204.01855 §3.1] [arxiv:2204.01855 §3.1.2]. The graph-learning survey
describes Node2vec as biasing walks between breadth-first and depth-first
moves, and it treats the walk-plus-word-embedding recipe as one family
[arxiv:2105.00696 §2.3.1].

### AE: pooled neighbourhood

AE samples first-order random walks. For every pair of positions up to `t`
steps apart, it pairs each node with the features of the other node. All
distances go into one corpus, and one SGNS model is trained on it
[arxiv:1909.13021 §3.1] [alg. 1]. Its embedding corresponds to an average of the
matrix powers `P^1 … P^t` [arxiv:1909.13021 §4.2, thm. 2]. Card:
[Multi-scale Attributed Node Embedding](/papers/1909.13021).

### MUSAE: one component per distance

MUSAE uses the same walks but keeps a separate corpus for each distance `r`. It
trains one SGNS model per distance, with `d/t` dimensions each, and concatenates
the results. The final vector therefore keeps the distances apart
[arxiv:1909.13021 §3.2] [alg. 2]. Each component corresponds to one power `P^r`
[arxiv:1909.13021 §4.1, thm. 1]. Card:
[Multi-scale Attributed Node Embedding](/papers/1909.13021).

### EGO variants

AE-EGO and MUSAE-EGO add one unique identity feature per node, so the embedding
also encodes each node itself [arxiv:1909.13021 §4.2, remark 3]. The authors
report that this makes little difference for classification with full labels,
and a little more when labels are scarce [arxiv:1909.13021 §5.2] [fig. 3].
Identity features tie the model to the nodes seen in training, so EGO variants
are not inductive [arxiv:1909.13021 tab. 1].

### Self-supervised GCN: HDI and HDMI

HDI encodes one graph with a one-layer GCN and trains it on three terms. The
extrinsic term relates each node embedding to a global summary. The intrinsic
term relates it to the node's own attributes. The joint term keeps the
embedding and summary but swaps in the attributes of another node
[arxiv:2102.07810 §3.1.1] [eq. 9-12]. HDMI runs an encoder on each relation
layer over the same nodes and fuses the layer embeddings with semantic attention.
The fused embedding is trained with the same objective [arxiv:2102.07810 §3.2].
On the Amazon IOI layer, the ablation's Macro-F1 rises from 0.569 with the
extrinsic term alone, to 0.792 with the intrinsic term, to 0.796 with the joint
term [arxiv:2102.07810 tab. 5]. Card:
[HDMI: High-order Deep Multiplex Infomax](/papers/2102.07810).

### Text-attributed nodes: GraphFormers

GraphFormers nests a graph-attention step inside each layer of a language model
(UniLM-base) [arxiv:2105.02605 §3.1] [arxiv:2105.02605 §4.2]. Layer 0 encodes
each node's text on its own. Later layers mix in a node-level vector built from
the centre node and its neighbours. The node's representation is the centre
node's [CLS] state after the last layer [arxiv:2105.02605 §3.1]. Training uses
link prediction with in-batch negatives [arxiv:2105.02605 §3.3] [eq. 6]. It
starts from a warm-up on masked inputs and then fine-tunes on clean data
[arxiv:2105.02605 §3.3]. The unidirectional variant lets neighbour states be
cached [arxiv:2105.02605 §3.2].

Each vector is computed from the node's text and its sampled neighbours, with at
most five neighbours per node [arxiv:2105.02605 §4.1]. It is therefore a
function of the neighbourhood, not a row in a lookup table. The evaluation is
link prediction, so its numbers do not transfer to the classification tables of
the other cards. Against the cascaded baseline PLM+Max, P@1 is higher on all
three datasets [arxiv:2105.02605 tab. 2]. Removing progressive learning lowers
P@1 by 0.98, 1.71 and 1.18 points on Product, DBLP and Wiki [arxiv:2105.02605
tab. 4]. Card:
[GraphFormers: GNN-nested Transformers for Representation Learning on Textual Graph](/papers/2105.02605).

### Dynamic graphs

The survey groups traditional dynamic methods into aggregation over snapshots,
temporal random walks (CTDNE and others), warm-started autoencoders (DynGEM and
others), and temporal point processes (HTNE and others). It also lists dynamic
GNNs such as TGAT and CAW-N [arxiv:2204.01855 §3.2] [arxiv:2204.01855 §4.4].
The survey runs no experiments, so this wiki has no performance ranking for
these methods. None of the named methods has a card here. The graph-learning
survey also covers time-varying network embedding methods in its random-walk
family [arxiv:2105.00696 §2.3.4], again without numbers.

### Biomedical networks (survey only)

The biomedical review describes shallow embeddings as a table of learnable
vectors, trained so that a similarity in the graph matches a similarity of the
vectors. The graph similarity can be shortest-path distance, or co-occurrence on
random walks. Node2vec mixes depth-first and breadth-first walk moves
[arxiv:2104.04883 §2.1]. Its GNN family is a stack of message, aggregate and
update steps [arxiv:2104.04883 §2.2]. Its generative family learns a
distribution over graphs and samples new ones [arxiv:2104.04883 §2.3]. The
review gives the generic forms only and does not rank the choices. Its case
studies cover cell-type gene labels, disease subgraphs from the Human Phenotype
Ontology, drug-drug interaction per cell line, and patient-to-disease edge
regression [arxiv:2104.04883 §4]–[§7]. They are described in words, with no
metrics [arxiv:2104.04883 §1]. Card:
[Graph Representation Learning in Biomedicine](/papers/2104.04883).

## When to use which

| Situation | Use | Why |
|---|---|---|
| Nodes carry no features | Structure-only proximity (DeepWalk, Node2Vec, Walklets) | Attributed methods need a feature set per node; the 1909 comparison uses these as its structure-only baselines [arxiv:1909.13021 §1] |
| Features are informative and one distance is enough | AE | One corpus and one model; the authors report it as strong on most classification datasets [arxiv:1909.13021 §5.2] [tab. 4] |
| Features matter at several distances, e.g. direct versus friends-of-friends | MUSAE | Separate components keep distances apart; the authors report it best on the Wikipedia traffic regression tasks [arxiv:1909.13021 §3.2] [tab. 5] |
| Labels are scarce and a small gain is worth the cost | AE-EGO or MUSAE-EGO | Gains reported in the few-label setting [arxiv:1909.13021 §5.2] [fig. 3] |
| Embeddings must apply to new nodes | AE or MUSAE, not EGO | Identity features are tied to training nodes [arxiv:1909.13021 tab. 1] |
| Feature vectors must carry over to a second graph with the same features | AE or MUSAE, with feature vectors held fixed | Zero-shot transfer is shown on Twitch graphs, and only works with the source feature vectors frozen [arxiv:1909.13021 §5.4] [fig. 4] |
| Several relation types over one node set, same attributes, no labels | HDMI; HDI for a single layer | Attention weights the layers per node [arxiv:2102.07810 §3.2]. Needs one shared node set and one attribute matrix [arxiv:2102.07810 §2.1]. Best Macro-F1 on its four datasets [arxiv:2102.07810 tab. 3] |
| Clustering or similarity search is the target, not classification | Compare baselines before choosing HDMI | HDMI is not best everywhere: DMGI_attn is higher on ACM clustering NMI and Sim@5 [arxiv:2102.07810 tab. 4] |
| Nodes have text, the target is link prediction, and training budget is large | GraphFormers | Reported P@1 gains over the cascaded baseline [arxiv:2105.02605 tab. 2] [§4.3]; training took 58.8 to 151.2 hours on 8 V100 GPUs per dataset [arxiv:2105.02605 app. B] |
| Graph changes over time | Dynamic methods from the survey | The survey lists families and names without benchmark numbers [arxiv:2204.01855 §1] [§3.2] |
| Accuracy is the only goal and labels are plentiful | A supervised GNN | The authors' supervised baselines are typically about 4% better, sometimes within 1% [arxiv:1909.13021 §5.2] |
| Large graph | Budget for corpus size (AE, MUSAE) or full-graph steps (HDMI) | AE and MUSAE cost grows linearly with nodes and with features per node [arxiv:1909.13021 §4.3] [fig. 5]. HDMI encodes every layer on clean and corrupted attributes at each step; see [its card](/papers/2102.07810) |
| Deep stacks of GNN layers | Expect over-smoothing and use a fix from the survey | Deep stacks make node vectors hard to tell apart; the survey lists fixes [arxiv:2204.01855 §4.6.2] |
| Need a map of the whole graph-learning field before choosing a method | The graph-learning survey, then the cited originals | It sorts the field into four families and lists applications, but gives no ranking [arxiv:2105.00696 §1.3] [§3] |
| Network data from biology or medicine (proteins, genes, drugs, patient codes) | The biomedical review, then the cited originals | It maps shallow, GNN and generative methods to biomedical tasks, with no numbers [arxiv:2104.04883 §2] [§4]–[§7] |

The four papers use different datasets, metrics and tasks. AE and MUSAE report
micro-F1 for classification and R² for regression on eight and three datasets
[arxiv:1909.13021 §5.2] [arxiv:1909.13021 §5.3]. HDMI reports Macro-F1 and
Micro-F1 on ACM, IMDB, DBLP and Amazon [arxiv:2102.07810 tab. 3]. GraphFormers
reports P@1 for link prediction on Product, DBLP and Wiki [arxiv:2105.02605
tab. 2]. The name DBLP is shared by two different datasets: 7,907 papers in HDMI
[arxiv:2102.07810 §4.1.1], and 4,894,081 items in GraphFormers [arxiv:2105.02605
tab. 1]. All results are author-reported. Treat the rows above as a starting
point, not a ranking.

## Implementation sketch

The sketch shows the walk-based core of AE and MUSAE, which is the only family
here that builds its training pairs from walks. The self-supervised GCN and
text-attributed families have no walk step. Their losses are outlined on their
cards: HDMI [arxiv:2102.07810 §3.1.1] and GraphFormers [arxiv:2105.02605 §3.3].

```pseudocode
# Build (node, feature) pairs from first-order walks  [alg. 1]
# Input: graph, features[v], walk length l, max distance t
# Output: pairs grouped by distance r = 1..t

def collect_pairs(graph, features, s, l, t):
    pairs_by_distance = {r: [] for r in 1..t}
    for _ in 1..s:
        # start node drawn in proportion to its degree  [alg. 1, line 2]
        start = sample_by_degree(graph)
        walk = uniform_random_walk(graph, start, l)
        for j in 1..(l - t):
            for r in 1..t:
                a, b = walk[j], walk[j + r]
                # pair each node with the features of the other  [alg. 1]
                for f in features[b]:
                    pairs_by_distance[r].append((a, f))
                for f in features[a]:
                    pairs_by_distance[r].append((b, f))
    return pairs_by_distance

# AE: pool all distances, one SGNS model  [§3.1]
# MUSAE: one SGNS model per distance, d/t dims each  [§3.2]
def embed(pairs_by_distance, d, b, t, variant):
    if variant == "AE":
        return sgns(concat(pairs_by_distance.values()), dim=d, negatives=b)
    parts = [
        sgns(pairs_by_distance[r], dim=d // t, negatives=b)
        for r in 1..t
    ]
    # concatenate the t components into d dims  [§3.2]
    return concat_columns(parts)
```

Points where implementations differ, and where the paper leaves choices open:
whether walk starts are sampled by degree or made from every node; the number
of dimensions per component, which must divide evenly into `d`; whether
frequent features are subsampled; and the negative-sampling exponent. The
paper's own configuration (`d = 128`, `t = 3`) does not divide evenly
[arxiv:1909.13021 §3.2] [tab. 3]. See [Paper vs code](/papers/1909.13021) for
how the released code handles these.

## Contradictions

- **Supervised versus self-supervised.** The AE and MUSAE card reports that its
  supervised GNN baselines are typically about 4% better than its unsupervised
  methods, sometimes within 1% [arxiv:1909.13021 §5.2]. The HDMI card reports
  HDMI above its GCN/GAT row on all four datasets [arxiv:2102.07810 tab. 3]. The
  HDMI card does not say how the GCN/GAT row was trained or how many labels it
  used, and the datasets differ. The two statements therefore do not directly
  conflict, but they cannot be merged into one ranking. Not resolved here.
- **Lemma versus theorem in the AE derivation.** The §4.2 lemma, as printed,
  gives a different constant factor for the AE limit than theorem 2 does
  [arxiv:1909.13021 §4.2, thm. 2] [app. A]. Check the derivation before
  building an explicit matrix from either statement.
- **Walks and dimensions, text against released code (AE, MUSAE).** The
  algorithms start walks from degree-sampled nodes, and table 3 lists 10 walks
  per node [arxiv:1909.13021 §3.1] [tab. 3]. The released code starts walks from
  every node, and its component size and feature subsampling differ from the
  text [Paper vs code](/papers/1909.13021).
- **Evaluation negatives, text against released code (GraphFormers).** The paper
  ranks each query against 299 randomly sampled negatives [arxiv:2105.02605
  §4.1]. The released code ranks against the other keys in its evaluation batch
  [Paper vs code](/papers/2105.02605).

## Papers

- [Multi-scale Attributed Node Embedding](/papers/1909.13021): AE and MUSAE, SGNS over random-walk (node, feature) pairs at several distances, with EGO variants and a transfer setting.
- [HDMI: High-order Deep Multiplex Infomax](/papers/2102.07810): self-supervised GCN embeddings for attributed multiplex networks, with the layers fused by attention.
- [GraphFormers: GNN-nested Transformers for Representation Learning on Textual Graph](/papers/2105.02605): graph attention inside every layer of a language model, trained for link prediction on textual graphs.
- [Graph Representation Learning in Biomedicine](/papers/2104.04883): review of shallow, GNN and generative graph methods for biomedical networks; no experiments.
- [Graph Learning: A Survey](/papers/2105.00696): taxonomy of graph learning into signal processing, matrix factorization, random walks and deep learning; no experiments.
- [A Survey on Graph Representation Learning Methods](/papers/2204.01855): taxonomy of static and dynamic graph embedding methods; no experiments.