--- kind: concept slug: attributed-network-embedding title: Attributed network embedding summary: >- Learns a vector per graph node from its links and its node features, so each vector reflects the attributes around it. Two families so far: random-walk skip-gram (linear cost, feature vectors reusable on a second graph) and a GCN trained with mutual-information terms for multiplex graphs. Evidence is two papers, author-reported; both released codes differ from their methods in places. tags: [graphs, node-embedding, unsupervised, self-supervised, random-walk, multiplex-networks] papers: ["1909.13021", "2102.07810"] related: [node-embedding, graph-neural-network, self-supervised-learning, skip-gram-negative-sampling] status: draft updated_at: 2026-10-19 --- ## Overview A node embedding maps each node of a graph to a short vector, so that a plain classifier or regressor can predict node labels from it. Structure-only methods such as DeepWalk, Node2Vec and Walklets use just the links. Attributed methods also take a feature set per node, such as the words on a web page or the interests listed by a user [arxiv:1909.13021 §1]. The problem with structure-only embeddings is twofold. They ignore attributes, and the vectors they produce for one graph cannot be related to those of another graph [arxiv:1909.13021 §1]. Earlier attributed methods usually look only at direct neighbours, do not work at several distances, or factorize dense matrices at quadratic or cubic cost in the number of nodes [arxiv:1909.13021 §2] [tab. 1]. Two families appear in the cited papers. Both learn vectors without labels from links and node attributes together: - **Random-walk skip-gram** (AE, MUSAE). Node and feature vectors are learned together with skip-gram with negative sampling (SGNS) over (node, feature) pairs taken from random walks. The cost grows linearly with the graph, and a feature vector learned on one graph can be reused on another graph with the same feature set [arxiv:1909.13021 §1] [arxiv:1909.13021 §4.3]. - **Mutual-information GCN** (HDI, HDMI). A one-layer graph convolutional encoder is trained to tell real node embeddings from corrupted ones, using three mutual-information terms. HDMI applies this to several relation layers over the same nodes and fuses them with attention [arxiv:2102.07810 §3.1] [arxiv:2102.07810 §3.2]. This family uses no random walks or SGNS. Neither the linear-cost nor the feature-transfer property is claimed for it. ## Variants ### AE: pooled neighbourhood AE samples first-order random walks and, for every pair of positions up to `t` steps apart, 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 is equivalent to a pooled 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 and concatenates the results, so the final vector keeps the distances apart [arxiv:1909.13021 §3.2] [alg. 2]. Each component corresponds to one power `P^r` in the factorized matrix [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 to the feature matrix. The model then also learns a vector for each node itself. The authors report that EGO helps little for classification with full labels, but a little more with few labels [arxiv:1909.13021 §4.2, remark 3] [arxiv:1909.13021 §5.2]. Identity features tie the embedding to the nodes seen in training, so EGO variants are not inductive [tab. 1] [arxiv:1909.13021 §4.2]. ### Special cases With every node's feature set reduced to its own identity, AE becomes DeepWalk and MUSAE becomes Walklets. Both are structure-only methods, so attributed variants generalize them [arxiv:1909.13021 §4.2, remarks 1-2]. ### HDI: one attributed layer HDI encodes a single graph with a one-layer GCN and trains it on the sum of three terms. The first pulls node embeddings towards a global summary. The second relates each embedding to its own attributes. The third is a joint term: the embedding and summary are kept, and the node's attributes are swapped for those of another node [arxiv:2102.07810 §3.1] [eq. 9-12]. In the author's ablation on the Amazon IOI layer, the extrinsic term alone reaches Macro-F1 0.569, adding the attribute term gives 0.792, and adding the joint term gives 0.796 [arxiv:2102.07810 tab. 5]. Card: [HDMI: High-order Deep Multiplex Infomax](/papers/2102.07810). ### HDMI: one encoder per layer, fused by attention HDMI runs HDI's encoder on each layer. A layer-specific score per node, passed through tanh, is normalised with a softmax over layers, and the layer embeddings are summed with those weights [arxiv:2102.07810 §3.2] [eq. 21-23]. The fused embedding is trained with the same objective as the layers [arxiv:2102.07810 §3.2.2]. The paper reports the best node-classification scores on all four of its datasets [arxiv:2102.07810 tab. 3]. Card: [HDMI: High-order Deep Multiplex Infomax](/papers/2102.07810). ## When to use which | Situation | Use | Why | |---|---|---| | Node features are informative and a single distance is enough | AE | One corpus and one model; the paper reports the simplest setup as strong on most 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; best on the Wikipedia traffic regression tasks [arxiv:1909.13021 §3.2] [tab. 5] | | Few labels per class and you want a small edge | MUSAE-EGO or AE-EGO | Authors report the largest gains from EGO when labels are scarce [arxiv:1909.13021 §5.2] [fig. 3] | | Embeddings must apply to new nodes or to unseen graphs | AE or MUSAE, not EGO | EGO features are tied to training nodes [tab. 1]. Whether HDMI applies to unseen nodes is not stated [arxiv:2102.07810 §3.2] | | Need to transfer feature vectors to a second graph with the same features | AE or MUSAE, with frozen feature vectors | Shown on Twitch graphs; zero-shot transfer requires keeping the source feature vectors fixed [arxiv:1909.13021 §5.4] [fig. 4] | | Several relation types over the same nodes, same attributes in every layer, no labels for pretraining | HDMI; HDI for a single layer | Attention weights the layers per node. Requires one shared node set and one attribute matrix [arxiv:2102.07810 §2.1]. Best node-classification scores 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 NMI and Sim@5 [arxiv:2102.07810 tab. 4] | | Large graph with many edges per relation | AE or MUSAE | Cost grows linearly with the graph [arxiv:1909.13021 §4.3]. HDMI encodes every layer on clean and corrupted attributes at each step [arxiv:2102.07810 §3.1.2]; one DBLP layer has 57,137,515 edges [arxiv:2102.07810 tab. 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] | | Many features per node, or a large node count | Budget for corpus size | Corpus size and time grow with the features per node; MUSAE trains `t` models [arxiv:1909.13021 §4.3] [fig. 5] | | Reusing the official code | Write from the paper | The HDMI repository has no licence file, so no reuse is granted [Card](/papers/2102.07810). The MUSAE repository is GPL-3.0 [Card](/papers/1909.13021) | The two papers evaluate on different datasets: eight classification and three regression sets for AE and MUSAE [arxiv:1909.13021 §5.2] [arxiv:1909.13021 §5.3], and four multiplex networks for HDMI [arxiv:2102.07810 §4.1.1]. Every result is author-reported. Treat the advice above as a starting point for those data types, not a general ranking. ## Implementation sketch Random-walk family only. AE and MUSAE share this core and differ only in how the pairs are grouped before SGNS [arxiv:1909.13021 §3.1] [arxiv:1909.13021 §3.2]. The HDI and HDMI family has no walk step; its loss is outlined on the HDMI card [arxiv:2102.07810 §3.1.1]. ```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] # each node is paired with the features of the other [alg. 1, lines 6-10] 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, then concatenate [§3.2] [alg. 2] def embed(pairs_by_distance, d, b, 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] 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 - **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. Taking the lemma at face value and combining it with the per-distance corpus sizes does not reproduce the theorem's scaling [arxiv:1909.13021 §4.2, thm. 2] [app. A]. This is a conflict inside the paper; it is not resolved here. Check the derivation before building an explicit matrix from either statement. - **Walk starts and sample counts.** The algorithms start walks from degree-sampled nodes, and table 3 lists 10 walks per node [arxiv:1909.13021 §3.1] [alg. 1] [tab. 3]. The released code starts walks from every node and defaults to 5, which conflicts with both [Paper vs code](/papers/1909.13021). - **Component dimensions.** The paper uses `d/t` dimensions per MUSAE component, with `d = 128` and `t = 3` [arxiv:1909.13021 §3.2] [tab. 3]. The released code uses 32 dimensions per component and adds a base component on the node's own features, which yields 128 dimensions only with that extra component [Paper vs code](/papers/1909.13021). Whether the reported experiments used the extra component is not stated in the paper. - **Subsampling and theory.** The limit results assume plain SGNS with no frequent-feature subsampling [arxiv:1909.13021 §4]. The released code applies subsampling, so its embeddings do not match the stated limit exactly [Paper vs code](/papers/1909.13021). - **Link prediction.** The conclusion mentions link prediction [arxiv:1909.13021 §6], but no numbers for it appear in the paper [Paper vs code](/papers/1909.13021). - **Headline claim versus table.** HDMI's "state-of-the-art" wording is broader than its own tables. On ACM, DMGI_attn scores higher on clustering NMI (0.702 against 0.695) and on Sim@5 (0.901 against 0.898) [arxiv:2102.07810 tab. 4]. The HDMI card advises reading the claim with that in mind. - **Official code against paper, HDMI.** The released code differs from the stated equations in several places, for example a GCN bias that equation 13 omits, and it uses a separate fusion discriminator that the paper does not specify. See [Paper vs code](/papers/2102.07810) before reproducing HDMI numbers. ## Papers - [Multi-scale Attributed Node Embedding](/papers/1909.13021): introduces AE and MUSAE, with EGO variants, and proves which proximity matrices they factorize. - [HDMI: High-order Deep Multiplex Infomax](/papers/2102.07810): self-supervised node embedding for attributed multiplex networks, with HDI as the single-layer case and attention-based fusion of layers.