HDMI: High-order Deep Multiplex Infomax

In plain words

A network can connect the same objects in several ways at once. In a paper database, two papers may share an author, or one may cite the other. Each kind of link is a separate layer. The goal is to give every node a short list of numbers, an embedding, that captures its place in all the layers together, without anyone labelling the nodes first.

The method learns these numbers by a guessing game. The model is shown the real network, and a shuffled copy in which every node's text or features is moved to a different node. It has to tell which node embeddings belong with the real features and which do not. The training signal is meant to capture the dependence between a node's embedding and its own features, and between the embedding and the wider network.

Each layer gets its own small network. A learned attention step then decides, node by node, how much to trust each layer when they are combined. The authors report that the resulting embeddings give better classification than the compared baselines on four benchmark networks.

TL;DR

HDMI is a self-supervised node-embedding method for attributed multiplex networks. Each layer is encoded by a one-layer GCN and trained with three mutual-information terms: node vs global summary, node vs its own attributes, and a joint term that uses corrupted attributes. A semantic-attention module fuses the layers. The authors report the best node-classification scores on all four datasets and competitive but not uniformly best clustering scores. Its official code is a PyTorch repository with no license file.

Problem

Deep Graph Infomax (DGI) trains a GCN by maximising mutual information between node embeddings and a global summary of the graph §2.3 eq. 3. The paper argues that DGI uses only this extrinsic signal, and ignores the dependence between a node's embedding and its attributes §1. Reconstruction-based attribute losses are also rejected, since the authors cite evidence that reconstruction error does not track embedding quality §1.

DGI assumes a single relation type. Real networks have several, and the simplest fix, averaging embeddings learned per layer, ignores how layers relate to each other §1. Earlier attention-based fusion needs labels to train its attention, which defeats the self-supervised goal §1.

Assumptions: all layers share one node set and one attribute matrix §2.1.

Method

HDMI has two parts. HDI (High-order Deep Infomax) trains one attributed layer with a three-variable mutual-information signal §3.1. HDMI runs HDI on every layer and fuses the layer embeddings with an attention module that is trained by the same signal §3.2.

1. High-order mutual information as the signal. For node n, with embedding h_n, summary s and attributes f_n, the three-variable interaction information expands to a sum of pairwise terms eq. 4 eq. 5:

I(h; s; f) = I(h; s) + I(h; f) - I(h; s, f)            [eq. 6]

The paper maximises the three pairwise terms, not the interaction term itself. Maximising the interaction term would force the joint term to be minimised, which the authors avoid §3.1.1. The final objective weights the three terms eq. 8:

L = λ_E I(h; s) + λ_I I(h; f) + λ_J I(h; s, f)        [eq. 8]

2. Estimating each term with a discriminator. Each term is estimated with the DGI-style binary task: real pairs against corrupted pairs §3.1.1.

• Extrinsic: node embedding against summary, with negatives from the corrupted graph eq. 9.
• Intrinsic: node embedding against its own attributes, with negatives from the corrupted graph eq. 10.
• Joint: triples (h_n, s, f_n) against (h_n, s, f̃_n), where f̃_n are attributes of a different node. The embedding and summary are kept and only the attributes are swapped eq. 11. The authors argue that a new discriminator between h_n and h̃_n given (s, f_n) would add little §3.1.1.

The HDI objective is the weighted sum of the three terms eq. 12.

3. Architecture of HDI.

• Encoder: one-layer GCN, H = ReLU(D^-1/2  D^-1/2 F W), with  = A + wI and w the self-connection weight eq. 13 §3.1.2.
• Readout: s is the mean of the node embeddings eq. 14 §3.1.2.
• Discriminators: bilinear scores for extrinsic and intrinsic terms eq. 15 eq. 16. The joint discriminator first projects attributes and summary into a common space with sigmoid-activated linear maps eq. 17 eq. 18, concatenates them, applies one more linear map and sigmoid eq. 19, then scores with a bilinear form eq. 20.
• Corruption: random row permutation of the attribute matrix, graph unchanged §3.1.2.

4. HDMI: one encoder per layer, fused by attention. Each layer r is encoded separately by HDI's encoder §3.2. Node scores come from a layer-specific projection followed by tanh eq. 21. A softmax over layers gives the weights eq. 22. The fused embedding is the weighted sum over layers eq. 23.

5. Training the fusion module. The fused embedding h_n is trained with the same HDI objective. Its summary s is the mean over fused embeddings. Its negative embeddings are the fusion applied to the corrupted layer embeddings §3.2.2. The final objective sums the per-layer HDI losses, each with its own weight, and the fusion HDI loss with another weight eq. 24 §3.2.2.

The algorithm is not given as a numbered box, so the pseudocode below is written from the equations and the official code.

# HDMI loss for one training step  [eq. 8-12] [eq. 21-24]
# Input:  adj[r] (N, N): normalised adjacency per layer, self-loop weight 3
#         features (N, dF): attribute matrix
# Output: loss (scalar), to be minimised

def hdmi_loss(adj, features):
    # Corruption: shuffle attribute rows, keep the graph  [§3.1.2]
    features_neg = features[random_permutation(num_nodes)]
    # Encode every layer on clean and corrupted attributes  [eq. 13]
    emb_pos = [encode(adj[r], features) for r in layers]
    emb_neg = [encode(adj[r], features_neg) for r in layers]
    # Fuse layers per node with semantic attention  [eq. 21-23]
    fused_pos = fuse(emb_pos)                # (N, d)
    fused_neg = fuse(emb_neg)                # (N, d)
    loss = 0
    for r in layers:
        # Per-layer HDI loss, each layer with its own summary  [eq. 9-12]
        loss += lam_layer[r] * hdi_loss(emb_pos[r], emb_neg[r], features,
                                        features_neg)
    # Fusion HDI loss on fused embeddings  [eq. 24]
    loss += lam_fusion * hdi_loss(fused_pos, fused_neg, features,
                                  features_neg)
    return loss

def encode(adj, features):
    # One-layer GCN: ReLU(adj @ features @ W)  [eq. 13]
    return relu(adj @ (features @ W))        # (N, d)

def hdi_loss(emb_pos, emb_neg, features, features_neg):
    # Readout: mean of the positive embeddings  [eq. 14]
    summary = mean(emb_pos, axis=0)          # (d,)
    # Extrinsic: node vs summary, real pairs against corrupted pairs  [eq. 9]
    loss_e = bce(extrinsic(emb_pos, summary), 1)
    loss_e += bce(extrinsic(emb_neg, summary), 0)
    # Intrinsic: node vs its own attributes  [eq. 10]
    loss_i = bce(intrinsic(emb_pos, features), 1)
    loss_i += bce(intrinsic(emb_neg, features), 0)
    # Joint: attributes of the same node vs attributes of another node  [eq. 11]
    loss_j = bce(joint(emb_pos, summary, features), 1)
    loss_j += bce(joint(emb_pos, summary, features_neg), 0)
    # Weighted sum of the three signals  [eq. 12]
    return lam_e * loss_e + lam_i * loss_i + lam_j * loss_j

def fuse(layer_embs):
    # Per node and layer: tanh(y_r . V_r h_r), the semantic score  [eq. 21]
    scores = [tanh(dot(y[r], V[r] @ layer_embs[r])) for r in layers]
    # Softmax over layers, separately for each node  [eq. 22]
    weights = softmax(stack(scores), axis=layers)       # (N, R)
    # Weighted sum over layers  [eq. 23]
    return sum(weights[:, r, None] * layer_embs[r] for r in layers)

Hyperparameters

Values not stated in the paper are marked. Code defaults come from the official repository (see Paper vs code).

Results

Author-reported, with the paper's setup §4.1. Datasets: ACM (3,025 papers, two layers), IMDB (3,550 movies, two layers), DBLP (7,907 papers, three layers), Amazon (7,621 items, three layers) §4.1.1 tab. 2. Baselines: DeepWalk, node2vec, GCN/GAT, DGI, ANRL, CAN, DGCN, CMNA, MNE, mGCN, HAN, DMGI and DMGI_attn §4.1.2. Hardware is not stated.

Node classification, Macro-F1 and Micro-F1 tab. 3. Bold in the paper is marked on HDMI in every column.

Node clustering (NMI, K-means) and similarity search (Sim@5) tab. 4. The paper's bold marks DMGI_attn in ACM NMI and ACM Sim@5, and HDMI in the other columns.

Ablation, per layer tab. 5 tab. 6. Rows are E. (extrinsic only), E. + R. (reconstruction in place of intrinsic), E. + I. and E. + I. + J. Averaging per-layer embeddings is compared with the fusion module through HDI and HDMI rows. The paper's own summary is: intrinsic is better than reconstruction, the joint term adds a further gain, and combining layers helps. Example from tab. 5, Amazon IOI layer, Macro-F1: E. 0.569, E. + I. 0.792, E. + I. + J. 0.796. Multiplex HDMI reaches 0.808 on Amazon.

Qualitative results are t-SNE plots of the Amazon IOI layer and ACM layers fig. 4 fig. 5 and attention weights against Micro-F1 per layer fig. 6. The paper says the layers with higher Micro-F1 receive higher attention §4.3.2.

Non-headline numbers: HDMI does not win every column. On ACM it is below DMGI_attn on clustering NMI (0.695 against 0.702) and on Sim@5 (0.898 against 0.901) tab. 4. The abstract's "state-of-the-art" claim should be read with that in mind.

Paper vs code

Official code: https://github.com/baoyujing/HDMI at commit 00b1bbdf37a530e2ec5e1e836f25eb25ef1cd94e. The repository owner is the first author's GitHub account, and the README links the arXiv paper. It has no LICENSE file. No code is quoted here; every reference is a citation.

Discrepancies, each with both sources:

• GCN bias. Eq. 13 has no bias term eq. 13; the code adds a learnable bias before ReLU gcn.py.
• Bilinear biases. The bilinear discriminators have a bias by default, which the paper's formulas eq. 15 eq. 20 do not show discriminator.py.
• Summary in extrinsic and intrinsic terms. The paper's D_E is σ(hᵀ M_E s) with s unactivated eq. 15. The code applies a sigmoid to the summary first discriminator.py discriminator.py.
• Joint discriminator. Eq. 18 has one sigmoid on the summary, z_s = σ(W_s s). The code applies a sigmoid to s, then a second one after the linear map discriminator.py.
• Loss scale. The paper writes the expectations as sums of positive and negative terms eq. 9. The code uses BCEWithLogitsLoss on the stacked positive and negative logits, which averages over 2N entries, so each term is half the expectation sum hdmi.py. This halving is folded into the λ values.
• Sign of the objective. The paper maximises L §3.1.1. The code minimises the sum of BCE losses with positive weights hdmi.py. This is the same optimisation with the sign flipped.
• Layer weights. The paper uses one λ_r per layer eq. 24. The code uses one shared triple (λ_E, λ_I, λ_J) for all layers main.py hdmi.py.
• Fusion discriminator. The paper does not say whether fusion has its own discriminator. The code's default is a separate one main.py hdmi.py.
• Attention bias and dimension. Eq. 21 has no bias. The code's score layer has one hdmi.py, and its projection size d' is 128 hdmi.py. The paper does not state d'.
• Early stopping. The paper names the patience (100) but not the monitored quantity §4.1.4. The code monitors the training loss, not the validation score, and keeps the checkpoint with the lowest training loss hdmi.py.
• Feature normalisation. The code row-normalises attributes before training embedder.py process.py. The paper does not mention it.
• Self-connection. Both use w = 3 §4.1.4. The code adds it to the diagonal of the adjacency as stored in the data files process.py, before symmetric normalisation process.py.
• Layer names. The paper names layers PSP, PAP, MDM, MAM, PAP, PPP, PATAP, IVI, IBI, IOI tab. 5. The code's data keys are PLP and PAP for ACM, MDM and MAM for IMDB, PAP, PPrefP and PATAP for DBLP, and IVI, IBI and IOI for Amazon process.py process.py. The mapping of PSP to PLP and PPP to PPrefP is inferred from the names and not stated.
• Evaluation scope. Clustering and similarity search run only on the test nodes evaluate.py. The paper does not say which nodes are used.
• Evaluation details. The code takes the test score at the epoch with the best validation score, separately for Macro-F1 and Micro-F1 evaluate.py. The paper does not describe this selection.
• Downstream training. Logistic regression uses Adam with lr 0.1 for 100 iterations, repeated 50 times evaluate.py. The paper gives no classifier training settings.
• Data. The README points to an external archive for the pre-processed datasets, which is not in the repository. Its licence is not stated [README].
• Seed. The code sets no random seed hdmi.py. Results depend on this.

Discrepancies that do not change the method: the code's HDI class is a separate per-layer model, while HDMI trains all layers jointly hdi.py hdmi.py.

Pitfalls

• Equation numbers in this card were counted from the LaTeX source, in order of appearance, with align rows numbered individually. They are not checked against the published PDF. Where a number is doubtful, the section is also cited.
• The λ values are not in the paper. The code defaults put almost all of the joint-term weight at 0.001 for layers and 0.001 for fusion main.py. Ablation results show the joint term helps, but the default weight is small, so a faithful reproduction may need a grid search.
• Early stopping on the training loss can stop or select a checkpoint that does not give the best downstream result. The paper's 10,000-epoch cap is a code default only.
• Joint term. Negatives for the joint term are attributes of a different node eq. 11. A corruption that shuffles rows must be applied to the attribute matrix, not to the adjacency §3.1.2.
• Attention scores pass through tanh before softmax eq. 21 eq. 22. Scores therefore lie in (-1, 1), and the softmax weight for one layer can exceed another's by at most a factor of e² ≈ 7.4. Fused embeddings stay close to an average unless learned scores move them. This follows from the formulas, not from a stated result.
• Memory. Features are densified for training process.py (todense). Attribute dimensions run from 1,007 (IMDB) to 2,000 (DBLP, Amazon) tab. 2. The DBLP PATAP layer has 57,137,515 edges tab. 2. Expect the adjacency to dominate memory on DBLP.
• Full-graph training. Each step encodes all nodes for every layer, twice (clean and corrupted). Training cost grows with the number of layers and edges.
• Results are single-configuration. The paper says it reports the best results of its grid search §4.1.4 and gives no variance across runs.

Lineage

• Builds on: Deep Graph Infomax (arXiv:1809.10341), which HDI extends from one signal to three §2.3 §3.1. Graph Convolutional Network (arXiv:1609.02907) is the encoder eq. 13.
• Extends to multiplex graphs: DMGI, "Unsupervised Attributed Multiplex Network Embedding" (AAAI 2020, no arXiv id in the source). The paper uses DMGI's datasets and its consensus-based comparison §4.1.1 §4.1.2.
• Compared against: DeepWalk, node2vec, GCN/GAT, DGI, ANRL, CAN, DGCN, CMNA, MNE, mGCN, HAN, DMGI, DMGI_attn §4.1.2.
• Attention in fusion is a semantic attention cited to You et al., 2016 §3.2.1.
• High-order mutual information estimation follows a difference-based approach cited to Mukherjee et al., 2020 (bib key mukherjee2020ccmi) §3.1.1.
• Superseded by: not stated in this wiki.