Attributed network 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 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 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 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 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 1909.13021 §1 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 2102.07810 §3.1 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 1909.13021 §3.1 alg. 1. Its embedding is equivalent to a pooled 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 and concatenates the results, so the final vector keeps the distances apart 1909.13021 §3.2 alg. 2. Each component corresponds to one power P^r in the factorized matrix 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 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 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 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 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 2102.07810 tab. 5. Card: HDMI: High-order Deep Multiplex Infomax.

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 2102.07810 §3.2 eq. 21-23. The fused embedding is trained with the same objective as the layers 2102.07810 §3.2.2. The paper reports the best node-classification scores on all four of its datasets 2102.07810 tab. 3. Card: HDMI: High-order Deep Multiplex Infomax.

When to use which

The two papers evaluate on different datasets: eight classification and three regression sets for AE and MUSAE 1909.13021 §5.2 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 1909.13021 §3.1 1909.13021 §3.2. The HDI and HDMI family has no walk step; its loss is outlined on the HDMI card 2102.07810 §3.1.1.

# 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 1909.13021 §3.2 tab. 3. See Paper vs code 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 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 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.
• Component dimensions. The paper uses d/t dimensions per MUSAE component, with d = 128 and t = 3 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. 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 1909.13021 §4. The released code applies subsampling, so its embeddings do not match the stated limit exactly Paper vs code.
• Link prediction. The conclusion mentions link prediction 1909.13021 §6, but no numbers for it appear in the paper Paper vs code.
• 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) 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 before reproducing HDMI numbers.

Papers

• Multi-scale Attributed Node Embedding: introduces AE and MUSAE, with EGO variants, and proves which proximity matrices they factorize.
• HDMI: High-order Deep Multiplex Infomax: self-supervised node embedding for attributed multiplex networks, with HDI as the single-layer case and attention-based fusion of layers.