Multi-scale Attributed Node Embedding

In plain words

Many networks have information on their nodes as well as links: people in a social network list the bands they like, web pages contain words. A node embedding turns every node into a short vector of numbers so that a simple classifier can predict things about it, such as a user's nationality or a page's traffic.

The idea here is to describe a node by the features of the nodes around it. Take short random walks through the graph and, whenever two nodes appear a few steps apart, record "this node was seen near that feature". Then train the same model word2vec uses for words, where nodes play the role of words and neighbours' features play the role of context. Nodes whose surroundings look alike end up with similar vectors, even if they sit far apart in the graph or in different graphs.

There are two variants. AE throws the features seen 1, 2 or 3 steps away into one bag. MUSAE keeps a separate bag per distance, learns a separate small vector for each, and glues them together, so "my friends like jazz" and "my friends' friends like jazz" stay distinguishable. The authors also show which statistics table the method is secretly compressing, and that DeepWalk and Walklets, two well-known methods, are the special case where every node's only feature is its own identity.

TL;DR

AE and MUSAE build a corpus of (node, feature) pairs from first-order random walks: a node is paired with every feature of each node within t steps on either side. Skip-gram with negative sampling (SGNS) on this corpus learns node and feature vectors in one space; AE pools all distances into one corpus, MUSAE trains one model per distance r and concatenates the parts. The paper proves the embeddings factorize log(c P^r F E^{-1}) - log b (MUSAE) or its average over r (AE). The EGO variants add a one-hot identity feature per node. Author-reported results: best unsupervised micro-F1 on 6 of 8 node classification datasets and best R² on all 3 Wikipedia traffic regression datasets. The official code (GPL-3.0) is Doc2Vec PV-DBOW, and its defaults do not match the paper's description in several places (see Paper vs code).

Problem

Proximity-based embeddings (DeepWalk, Node2Vec, Walklets) only see the graph structure, so they ignore node attributes and give no way to relate the embeddings of two different graphs §1. Existing attributed embeddings either look only at first-order neighbours, are not multi-scale, or factorize dense matrices with quadratic or cubic cost in the number of nodes §2 tab. 1. The authors want a Skip-gram style method that (i) uses the distribution of attributes in a node's neighbourhood at several scales, (ii) learns feature embeddings too, so a model trained on one graph can be reused on another graph with the same features, and (iii) scales linearly §1 §4.3.

Assumptions: undirected graph, binary node features F_v ⊆ F §3; the theory additionally assumes the graph is ergodic (connected, non-bipartite) and walks of length l → ∞ §4.

Method

Notation §3 §4: graph G = (V, E), n = |V|, binary feature matrix F ∈ {0,1}^{n×|F|} with F[v,f] = 1 iff f ∈ F_v. Adjacency A, degree matrix D, volume c = Σ A[v,w], transition matrix P = D^{-1} A, and E = diag(1ᵀ D F) (diagonal, E[f,f] = Σ_{v: f ∈ F_v} deg(v)). Node embedding G ∈ R^{n×d}, feature embedding H ∈ R^{|F|×d}.

Steps (AE) §3.1 alg. 1:

1. Sample s start nodes with probability proportional to degree.
2. From each start node, sample a first-order (uniform-neighbour) random walk of length l.
3. For each source position j in 1..l−t and each offset r in 1..t: add (v_j, f) for every feature f of v_{j+r} (forward), and (v_{j+r}, f) for every feature f of v_j (backward), to one multiset D.
4. Run SGNS with b negative samples and d dimensions on D; nodes are the "words", features are the "contexts". Output g_v and h_f.

MUSAE §3.2 alg. 2 uses the same walks and loops, but sends forward pairs at offset r to sub-corpus D_r→ and backward pairs to D_r←. For each r, SGNS is run separately on D_r = D_r→ ∪ D_r← with d/t dimensions (the paper requires t to divide d), and the final node (and feature) embedding is the concatenation of the t components g^1_v … g^t_v.

EGO variants §4.2, remark 3: append the identity matrix to the features, [F; I], i.e. every node additionally carries a unique feature for itself. This yields AE-EGO and MUSAE-EGO.

# AE and MUSAE corpus construction and training  [alg. 1] [alg. 2]
# Input:  graph, node_features[v] (set of feature ids), s, l, t, d, b
# Output: node embeddings (n, d), feature embeddings (|F|, d)

def build_corpora(graph, node_features, s, l, t):
    # one multiset of (node, feature) pairs per offset r  [alg. 2]
    corpus_by_offset = {r: [] for r in 1..t}
    for i in 1..s:
        # start node with probability deg(v) / vol(G)  [alg. 1, line 2]
        start = sample_node_by_degree(graph)
        # first-order random walk of length l  [alg. 1, line 3]
        walk = uniform_random_walk(graph, start, l)
        # only the first l - t positions act as sources  [alg. 1, line 4]
        for j in 1..(l - t):
            for r in 1..t:
                source = walk[j]
                target = walk[j + r]
                # forward: source node paired with target's features
                # [alg. 1, lines 6-7]
                for f in node_features[target]:
                    corpus_by_offset[r].append((source, f))
                # backward: target node paired with source's features
                # [alg. 1, lines 9-10]
                for f in node_features[source]:
                    corpus_by_offset[r].append((target, f))
    return corpus_by_offset

def train_ae(graph, node_features, s, l, t, d, b):
    corpora = build_corpora(graph, node_features, s, l, t)
    # AE pools every offset into a single corpus  [§3.1]
    pooled = concatenate(corpora[r] for r in 1..t)
    # SGNS: node = word, feature = context  [alg. 1, line 15]
    node_vectors, feature_vectors = sgns(pooled, dim=d, negatives=b)
    return node_vectors, feature_vectors

def train_musae(graph, node_features, s, l, t, d, b):
    corpora = build_corpora(graph, node_features, s, l, t)
    node_parts = []
    feature_parts = []
    for r in 1..t:
        # one independent SGNS model per offset, d / t dims each  [alg. 2]
        nodes_r, features_r = sgns(corpora[r], dim=d // t, negatives=b)
        node_parts.append(nodes_r)
        feature_parts.append(features_r)
    # concatenate the t scale components into d dims  [§3.2]
    return concat_columns(node_parts), concat_columns(feature_parts)

def add_ego_features(node_features):
    # EGO: every node also carries a unique identity feature  [remark 3]
    for v in node_features:
        node_features[v].add(("ego", v))
    return node_features

What the embeddings factorize §4. Using the SGNS result of Levy and Goldberg, SGNS embeddings satisfy

\mathbf{w}_w^\top \mathbf{c}_c \approx \log\frac{\#(w,c)\,|\mathcal{D}|}{\#(w)\,\#(c)} - \log b §4

Lemma 1: as l → ∞, #(v,f)_{r→}/|D_{r→}| → c^{-1}(D P^r F)[v,f] and #(v,f)_{r←}/|D_{r←}| → c^{-1}(Fᵀ D P^r)[f,v] §4.1, lemma 1 app. A. Lemma 2: for undirected graphs both directions agree, so #(v,f)_r/|D_r| → c^{-1}(D P^r F)[v,f] §4.1, lemma 2 app. A. Marginals converge to deg(v)/c for nodes and E[f,f]/c for features §4.1.

Theorem 1 (MUSAE), for each r = 1..t §4.1, thm. 1:

\mathbf{G}^{r}\,{\mathbf{H}^{r}}^{\top} \approx \log\big(c\,\mathbf{P}^r\mathbf{F}\mathbf{E}^{-1}\big) - \log b

Theorem 2 (AE) §4.2, thm. 2:

\mathbf{G}\,\mathbf{H}^{\top} \approx \log\Big(\frac{c}{t}\Big(\sum_{r=1}^{t}\mathbf{P}^r\Big)\mathbf{F}\mathbf{E}^{-1}\Big) - \log b

(log is element-wise.) With F = I, E = D and these reduce to the matrices known for DeepWalk (AE) and Walklets (MUSAE) §4.2, remarks 1-2. With [F; I] they give the EGO matrices §4.2, remark 3.

Complexity §4.3: with m = Σ_v |F_v|, corpus generation from s degree-sampled walks is O(s l t m/n) time and memory; one SGNS epoch is O(b d s l t m/n). With p walks per node it is O(p n l t m) for the corpus and O(b d p n l t m) for optimization. Parameters take O((n + |F|) d).

Transfer learning §5.4: (i) learn node and feature embeddings on a source graph; (ii) fit a classifier for a held-out attribute on the source node embeddings; (iii) re-run the embedding on a target graph with the same feature set while keeping the feature embeddings fixed; (iv) apply the source classifier to the target node embeddings.

Hyperparameters

Embedding hyperparameters for AE and MUSAE in the experiments §5.1 tab. 3:

Downstream models (scikit-learn defaults otherwise) §5.1 tab. 3:

Baselines app. B: DeepWalk with negative sampling and tab. 3 settings; LINE₂ as 64 + 64 dims (1st and 2nd order) concatenated; Node2Vec p, q tuned over {4, 2, 1, 0.5, 0.25} on an 80/20 split inside the training set; Walklets and GraRep with window 4 and 32 dims per scale; NetMF 128 dims, window 5; HOPE with normalized neighbourhood overlap; AANE, ASNE, BANE, TADW, TENE with their papers' settings at 128 dims. Embedding baselines come from the Karate Club library app. B.

Supervised GNN baselines app. C tab. 6: Adam, 200 epochs, learning rate 0.01, dropout 0.5, l2 weight 0.001, depth 2, 32 filters per layer. GraphSAGE samples 40 neighbours; GAT uses one head and leaky-ReLU slope 0.2; MixHop uses adjacency powers 0, 1, 2 with 32-dim filters; ClusterGCN uses METIS with as many clusters as classes; APPNP has 32 hidden units, teleport 0.2 and 20 propagation steps; SGConv uses the 2nd adjacency power app. C.

Results

Author-reported. Datasets tab. 2: Cora, Citeseer, Pubmed, Facebook page-page (22,470 nodes, 4 classes), GitHub (37,700, 2), LastFM Asia (7,624, 18), Deezer Europe (28,281, 2), Wikipedia Chameleons / Crocodiles / Squirrels (regression), and six Twitch networks sharing 3,169 features.

Node classification, test micro-F1 ± standard error over 100 seeded 80/20 splits §5.2 tab. 4:

Bold marks the best unsupervised result per column as in the paper; the last seven rows are supervised GNNs, which the authors treat as an upper bound (typically about 4% better, sometimes within 1%) §5.2. The AANE Deezer entry is printed as "622±.001" in the source and read here as .622. Observations by the authors: multi-scale beats pooled more often than not, EGO features make little difference for classification, and first-order-only attributed methods are weak §5.2.

Node regression on Wikipedia, log average monthly traffic, test R² ± standard error over 100 seeded 80/20 splits, elastic net §5.3 tab. 5:

The authors summarize this as MUSAE-EGO beating the best baseline on each dataset by 2-10% §5.3.

Other results, described from figures:

• Few-shot classification with k ∈ {3, …, 30} labelled nodes per class: the attributed embeddings beat the other unsupervised methods by a clear margin, most of all on Facebook and GitHub, and the EGO variants help a little when labels are scarce §5.2 fig. 3.
• Transfer learning between Twitch graphs (targets Portugal and Russia, each other country as source, 10 runs): AE and MUSAE always score above random guessing and sometimes come close to retraining on the target graph §5.4 fig. 4.
• Runtime on Erdős–Rényi graphs (8 edges per node, features drawn from a pool of 2^11, 100 runs each, one asynchronous epoch): linear in the number of nodes and in features per node; more cores stop helping as features per node approach the size of the feature pool §5.5 fig. 5.

Paper vs code

The repository is GPL-3.0, so nothing is quoted from it here.

• Embedding size. The paper says MUSAE components have d/t dimensions with t | d and d = 128, t = 3 §3.2 tab. 3. The code instead gives every component --dimensions = 32 dims parser.py musae.py and concatenates whatever was learned musae.py.
• Extra "base" component. With the default --base-model null, the code also trains an embedding on each node's own features and puts it in front musae.py parser.py. Defaults therefore give MUSAE 32 × (1 + 3) = 128 dims and AE 32 + 32 = 64 dims. This own-feature component appears in the paper only in the caption of fig. 2, as g^0_v fig. 2, not in alg. 1-2 or the theory. Whether the reported experiments used it is not stated.
• Walk sampling. The algorithms sample s start nodes by degree [alg. 1, line 2]; the code starts --walk-number walks from every node walkers.py, default 5 parser.py, while tab. 3 says 10 walks per node.
• SGNS implementation. The code uses gensim Doc2Vec in PV-DBOW mode (dm=0, window=0): each node is a "document" tagged by its id, and its "words" are the neighbourhood features musae.py utils.py. This is SGNS between node vectors and feature vectors, but it also applies frequent-word subsampling (sample=0.001) and a 0.75 unigram exponent for negatives parser.py, neither of which the paper mentions. Subsampling changes the counts that the PMI theorems in §4 rely on.
• Source positions. AE in code iterates over len(walk) − t sources as in alg. 1 musae.py, but MUSAE at offset r iterates over len(walk) − r sources musae.py, so smaller offsets get slightly more pairs than in alg. 2.
• Feature embeddings and EGO. The code saves only node embeddings musae.py; feature vectors h_f are never written out, and there is no transfer-learning (frozen feature embedding) code and no EGO switch. EGO has to be done by adding identity features to the input JSON (inferred; not shown in the repo).
• Second-order walks. The code also offers Node2Vec walks (--sampling second) walkers.py; the paper uses only first-order walks §3.1.

Pitfalls

• d/t with the published settings. 128 is not divisible by 3, so the paper's own configuration cannot follow §3.2 literally. Pick per-component dims explicitly (the code's 32 × 4 with a base component is one way to get 128) and report what you chose.
• Typo in the AE lemma. The lemma in §4.2 states #(v,f)/|D| → (c/t)(D Σ_r P^r F)[v,f]. Combining lemma 2 with |D_r| = |D|/t, as the proof does, gives the factor 1/(c t), not c/t. Theorem 2 (with c/t after dividing by the marginals) is consistent with 1/(c t) in the lemma. Use the theorem, not the lemma, if you build the explicit matrix.
• Theory vs practice. The PMI results hold as walk length → ∞, for ergodic undirected graphs, and for plain SGNS. Disconnected graphs, walks of length 80, frequent-feature subsampling, and degree-proportional versus every-node starts all change the counts. Isolated nodes stop walks early in the code walkers.py.
• Node ids. The code assumes nodes are integers 0..n−1: walks start from range(number_of_nodes) and embeddings are read back in that order walkers.py musae.py. Self-loops are removed on load utils.py.
• Cost hides in the features. The corpus size scales with features per node: each (source, target) pair emits |F_target| + |F_source| tuples. LastFM has about 395 features per node tab. 2, so its corpus is about 20 times larger than for a graph with about 20 features per node. MUSAE also trains t separate models (plus the base model in code).
• Transfer needs frozen feature vectors. Zero-shot transfer only works if the target graph's node embeddings are trained against the source feature embeddings held fixed §5.4; separately trained models live in unrelated spaces. The released code does not implement this.
• EGO trades away inductiveness. Identity features tie the embedding to the training graph's nodes; tab. 1 marks AE and MUSAE as inductive and the EGO variants as not tab. 1.
• Link prediction is claimed but not shown. The conclusion talks about link prediction results §6, but that experiment and its table are commented out of the published source; no link prediction numbers appear in the paper.
• Downstream regularization. λ = 0.01 and γ = 0.5 tab. 3 do not say how they map to scikit-learn's C for logistic regression or alpha / l1_ratio for elastic net.

Lineage

• Builds on: Skip-gram with negative sampling (word2vec) and its implicit PMI factorization (Levy and Goldberg); DeepWalk, which is AE with F = I; Walklets, which is MUSAE with F = I; and the NetMF analysis of random-walk embeddings (Qiu et al.) §4 §4.2.
• Compared against: DeepWalk, LINE, Node2Vec, Walklets, NetMF, HOPE, GraRep, TADW, AANE, ASNE, BANE, TENE (unsupervised), and GCN, GraphSAGE, GAT, MixHop, ClusterGCN, APPNP, SGConv (supervised) tab. 4.
• Superseded by: not known from content in this wiki.