Node embedding

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 1909.13021 §1. The survey states the same goal as keeping similar nodes close in the vector space 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 1909.13021 §1 2204.01855 §3.1. Their vectors for one graph cannot be related to those of another graph 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) 1909.13021 §3.1. Detail is on 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 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 2105.02605 §3.1 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 2105.00696 §2.3.1 2105.00696 §2.2.

Graphs that change over time form a fifth setting, covered under 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 2104.04883 §2. Its examples are protein, gene, drug and patient networks. It reports no numbers 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 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 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 2204.01855 §3.1 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 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 1909.13021 §3.1 alg. 1. Its embedding corresponds to an average of the matrix powers P^1 … P^t 1909.13021 §4.2, thm. 2. Card: Multi-scale Attributed Node Embedding.

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 1909.13021 §3.2 alg. 2. Each component corresponds to one power P^r 1909.13021 §4.1, thm. 1. Card: Multi-scale Attributed Node Embedding.

EGO variants

AE-EGO and MUSAE-EGO add one unique identity feature per node, so the embedding also encodes each node itself 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 1909.13021 §5.2 fig. 3. Identity features tie the model to the nodes seen in training, so EGO variants are not inductive 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 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 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 2102.07810 tab. 5. Card: HDMI: High-order Deep Multiplex Infomax.

Text-attributed nodes: GraphFormers

GraphFormers nests a graph-attention step inside each layer of a language model (UniLM-base) 2105.02605 §3.1 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 2105.02605 §3.1. Training uses link prediction with in-batch negatives 2105.02605 §3.3 eq. 6. It starts from a warm-up on masked inputs and then fine-tunes on clean data 2105.02605 §3.3. The unidirectional variant lets neighbour states be cached 2105.02605 §3.2.

Each vector is computed from the node's text and its sampled neighbours, with at most five neighbours per node 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 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.

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 2204.01855 §3.2 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 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 2104.04883 §2.1. Its GNN family is a stack of message, aggregate and update steps 2104.04883 §2.2. Its generative family learns a distribution over graphs and samples new ones 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 2104.04883 §4–§7. They are described in words, with no metrics 2104.04883 §1. Card: Graph Representation Learning in Biomedicine.

When to use which

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 1909.13021 §5.2 1909.13021 §5.3. HDMI reports Macro-F1 and Micro-F1 on ACM, IMDB, DBLP and Amazon 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 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 2102.07810 §3.1.1 and GraphFormers 2105.02605 §3.3.

# 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 1909.13021 §3.2 tab. 3. See Paper vs code 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% 1909.13021 §5.2. The HDMI card reports HDMI above its GCN/GAT row on all four datasets 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 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 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.
• 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

• Multi-scale Attributed Node Embedding: 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: self-supervised GCN embeddings for attributed multiplex networks, with the layers fused by attention.
• GraphFormers: GNN-nested Transformers for Representation Learning on Textual Graph: graph attention inside every layer of a language model, trained for link prediction on textual graphs.
• Graph Representation Learning in Biomedicine: review of shallow, GNN and generative graph methods for biomedical networks; no experiments.
• Graph Learning: A Survey: taxonomy of graph learning into signal processing, matrix factorization, random walks and deep learning; no experiments.
• A Survey on Graph Representation Learning Methods: taxonomy of static and dynamic graph embedding methods; no experiments.