Node Similarity Preserving Graph Convolutional Networks

In plain words

Graph neural networks learn about a node by averaging information from its neighbours. That averaging makes connected nodes look alike. It helps when neighbours really are similar, but it hurts when they are not, for example on a web of pages where linked pages often cover different topics.

This paper keeps the averaging but also gives each node a second opinion. It builds a second graph that links each node to the nodes whose features look most like its own. For every node, the model decides how much to trust the real links and how much to trust the feature-similar links. It also lets each node decide how much of its own features to keep. A side task asks the model to predict how similar two nodes' features are, which pushes similar nodes together and dissimilar nodes apart.

The authors report that this helps on both kinds of graph and under graph attacks. These are their own numbers on seven datasets.

TL;DR

SimP-GCN is a two-layer graph convolutional network. Its propagation matrix blends the normalised graph with a normalised cosine kNN graph built from node features, using a per-node score, and adds a per-node learnable self-loop term §4.1. The loss adds a regression on pairwise feature similarity, weighted by λ §4.2 §4.3. Author-reported: it beats GCN and most baselines on seven datasets, including the disassortative ones, and is more robust to the meta attack §5.2 §5.3. Official PyTorch code is linked; it has no license file.

Problem

The authors show that one GCN layer is one step of gradient descent on a Laplacian smoothing objective §3. So each layer pulls neighbouring feature vectors together, which the authors argue destroys the node similarity of the original features §3.

They measure this with the overlap OL(A1, A2) = |A1 ∩ A2| / |A1|, the share of edges two graphs have in common §3. The overlap between the feature kNN graph A_f and the original graph A is 0.03% on Actor and 0.91% on Cornell, against 3.88% on Cora tab. 1. The effect is strongest on disassortative graphs, where linked nodes often differ in label and features §3.

Method

Overview. The framework has two parts: node similarity preserving aggregation, which changes the propagation matrix, and a self-supervised loss on pairwise feature similarity §4 fig. 1.

Step 1. Feature kNN graph. For each node pair, compute the cosine similarity of their feature vectors §4.1. For each node keep the k = 20 most similar nodes, which gives the adjacency A_f and its degree matrix D_f §4.1. The normalised matrix D_f^{-1/2} A_f D_f^{-1/2} is the kNN propagation matrix §4.1.

Step 2. Node-wise balance between the two graphs. Compute a score s^(l) in (0, 1) per node from the layer's input H^(l-1) with a sigmoid, using one weight vector and one bias. For layer 1 the input is the raw features X §4.1. The layer-l propagation matrix is s^(l) times the normalised original graph plus (1 − s^(l)) times the normalised kNN graph §4.1.

Step 3. Learnable self-loops. For each node compute K_i = H_i W_K + b_K, a scalar from the input of layer l §4.1. Add γ · diag(K) to the propagation matrix, with γ a fixed hyperparameter §4.1. The result is interpreted as the node adding K_i self-loops, scaled by γ §4.1.

Step 4. Layer output. The layer output is σ(P̃ H^(l-1) W^(l)), with σ the activation (ReLU in hidden layers) §4.1. The last layer's output Ĥ is fed to softmax and cross-entropy §4.1 §4.3. The paper does not say whether σ is applied to the last layer too (see Pitfalls).

Step 5. Self-supervised pair regression. For each node, sample its m most similar and m most dissimilar nodes, with m = 5 §4.2. For each sampled pair (v_i, v_j), take the cosine similarity S_ij of their features as the target §4.2. Feed the difference of their first-layer hidden states H^(1) through a linear map f_w, and fit the output to S_ij with a squared error §4.2. The aim is to keep similar nodes close and dissimilar nodes apart in the hidden space §4.2. The regression is used instead of a classification of similar/dissimilar pairs §4.2.

Step 6. Joint objective. Minimise the cross-entropy on labelled nodes plus λ times the mean self-supervised loss §4.3. Both terms are averaged, so λ sets the relative weight §4.3.

Complexity. Computing all pairwise similarities is O(n²) when done naively. The authors point to parallel and approximate kNN methods as options §4.3. The extra parameters are O(d) per layer, where d is the input dimension §4.3.

The pseudocode below follows the paper's equations. The official code differs in several places; see Paper vs code.

# Node-wise propagation of one SimP-GCN layer  [§4.1]
# Input:  hidden (N, d); adj (N, N) normalised with self-loops;
#         adj_knn (N, N) normalised kNN graph, no self-loops
# Output: hidden (N, d')

def simp_gcn_layer(hidden, adj, adj_knn, weight, params, gamma, activate):
    # Per-node score that balances graph and feature kNN  [§4.1]
    scores = sigmoid(hidden @ params.w_score + params.b_score)      # (N, 1)
    # Per-node learnable self-loop count K_i  [§4.1]
    loops = hidden @ params.w_loop + params.b_loop                  # (N, 1)
    # Project the hidden states once  [§4.1]
    projected = hidden @ weight                                     # (N, d')
    # Blend the two propagation matrices row by row  [§4.1]
    mixed = (scores * (adj @ projected)
             + (1 - scores) * (adj_knn @ projected))                # (N, d')
    # Add gamma * K_i times the projected node  [§4.1]
    mixed = mixed + gamma * loops * projected                       # (N, d')
    # Activation once, after the combined propagation  [§4.1]
    if activate:
        return relu(mixed)
    return mixed

# Two-layer SimP-GCN forward pass  [§4.1] [§5.1]
# Input:  features (N, d); adj and adj_knn as above
# Output: logits (N, C)

def simp_gcn(features, adj, adj_knn, layer1, layer2, gamma):
    # First layer on the raw features  [§4.1]
    hidden = simp_gcn_layer(features, adj, adj_knn, layer1.weight,
                            layer1.params, gamma, activate=True)    # (N, d')
    # Dropout between the layers; the paper does not say where  [§5.1]
    hidden = dropout(hidden, rate=0.5)                              # (N, d')
    # Output layer without activation, as the code does; the paper is unclear
    logits = simp_gcn_layer(hidden, adj, adj_knn, layer2.weight,
                            layer2.params, gamma, activate=False)   # (N, C)
    return logits

# Sample pairs and targets for the self-supervised loss  [§4.2]
# Input:  features (N, d) as cosine input; m = 5
# Output: pairs (P, 2) of node indices; targets (P,) cosine similarities

def sample_pairs(features, m):
    # Pairwise cosine similarity of the features  [§4.1] [§4.2]
    sims = cosine_similarity(features)                              # (N, N)
    pairs = set()
    for node in range(N):
        # Ascending ranking of other nodes by similarity  [§4.2]
        ranked = argsort(sims[node])                                # (N,)
        # m most dissimilar and m most similar, excluding the node  [§4.2]
        for other in concat(ranked[:m], ranked[-(m + 1):]):
            if other != node:
                pairs.add(sorted((node, other)))
    pairs = array(sorted(pairs))                                    # (P, 2)
    targets = sims[pairs[:, 0], pairs[:, 1]]                        # (P,)
    return pairs, targets

# Joint objective  [§4.2] [§4.3]
# Input:  logits (N, C); labels for training nodes; hidden (N, d') from
#         layer 1 after dropout; pairs and targets from sample_pairs
# Output: scalar loss

def total_loss(logits, labels, train_idx, hidden, pairs, targets, lam):
    # Cross-entropy averaged over labelled nodes  [§4.3]
    loss_class = cross_entropy(logits[train_idx], labels[train_idx])
    # Linear map of the first-layer difference, paper form  [§4.2]
    # (the official code takes the absolute difference; see Paper vs code)
    diffs = hidden[pairs[:, 0]] - hidden[pairs[:, 1]]               # (P, d')
    predicted = diffs @ w_f                                         # (P,)
    # Squared error to the cosine targets, averaged over pairs  [§4.2]
    loss_self = mean((predicted - targets) ** 2)
    # Weighted sum; lam is searched on the validation set  [§4.3] [§5.1]
    return loss_class + lam * loss_self

Hyperparameters

Paper values come from the setup section §5.1 unless noted. Code values come from the scripts in the repository, which give one fixed configuration per dataset.

Values chosen in the official scripts :

All scripts also use k = 20, dropout 0.5, weight decay 5e-4, and no edge sampling cora.sh.

Results

Author-reported. Setup: seven datasets (Table 2 in the paper) §5.1 tab. 2. Assortative: Cora, Citeseer, Pubmed with the standard 20 nodes per class for training, 500 for validation and 1000 for testing, averaged over 10 runs §5.2. Disassortative: Actor, Cornell, Texas, Wisconsin with random 60/20/20 splits per class, averaged over 10 splits §5.2. The GCN, GAT and Geom-GCN numbers on the disassortative datasets are reused from the GCNII paper, not rerun §5.2. Robustness: Metattack at 0% to 25% perturbation, 10% training, 10% validation and 80% test nodes, 10 repeats §5.3.

Assortative graphs, accuracy (%) tab. 3.

Disassortative graphs, accuracy (%) tab. 4.

Ablation on disassortative graphs, accuracy (%) tab. 5.

Robustness. Under Metattack, SimP-GCN consistently improves on GCN at each perturbation rate on Cora, Citeseer and Pubmed, and the gap is larger at higher rates §5.3 fig. 2. The text reports over 20 points on Cora at 25% §5.3. The curves are in the figure only; no table gives the values fig. 2. The authors say SimP-GCN beats GCN-Jaccard and is comparable to Pro-GNN §5.3 fig. 2.

Feature-similarity preservation. On all datasets SimP-GCN raises OL(A_f, A_h), the overlap of the feature graph with the learned hidden graph §5.4 fig. 3. The text gives roughly 10% on Actor §5.4.

Paper vs code

Official code: https://github.com/ChandlerBang/SimP-GCN, cloned at 0aa4b8950db0d6a385e5b716164b545fa931800a (repository root: raw/code/2011.09643/). The paper's abstract links it. The repository has no LICENSE file, so its code cannot be quoted here; all citations below point to it without copying code. Discrepancies, each with both citations:

1. SSL head input. Paper: f_w(H_i − H_j) §4.2. Code: f_w(|H_i − H_j|), using the absolute value selfsl.py selfsl.py.
2. Binarised features for similarity. Paper: cosine similarity of X §4.1 §4.2. Code sets every nonzero feature to 1 before computing cosine similarity, both for the kNN graph and for the SSL targets [code: raw/code/2011.09643/src/selfsl.py#L151-L153] [code: raw/code/2011.09643/src/distance.py#L22] [code: raw/code/2011.09643/src/distance.py#L33].
3. kNN graph weights and symmetry. Paper: a kNN adjacency, unweighted and with no mention of symmetry §4.1. Code: keeps the top-k cosine values per row as edge weights, not symmetrised, with the node itself excluded selfsl.py. The normalisation uses row sums on both sides, with no self-loops [code: raw/code/2011.09643/src/selfsl.py#L372-L380].
4. Activation placement. Paper: σ applied once to the combined propagation §4.1. Code: ReLU is applied to each of the three propagated branches (graph, kNN graph, identity for self-loops) separately, then they are combined models_simp.py [code: raw/code/2011.09643/src/layers.py#L69-L87]. Summing separately ReLU'd branches is not the same as ReLU of the sum, so results will differ.
5. Self-loop term. Paper: γ · diag(K) times H W §4.1. Code: the self-loop term is applied to the output of the identity-branch layer, which already includes bias and ReLU [code: raw/code/2011.09643/src/models_simp.py#L173-L174].
6. Output activation. Paper's general layer formula has σ on every layer §4.1. Code uses no activation on the output layer [code: raw/code/2011.09643/src/models_simp.py#L86] [code: raw/code/2011.09643/src/models_simp.py#L111-L112].
7. Dropout placement. Not stated in the paper §5.1. Code applies dropout once, after the first layer, and not to the input features [code: raw/code/2011.09643/src/models_simp.py#L181].
8. SSL embedding. Paper: H^(1) §4.2. Code uses the first-layer output after dropout, in training mode [code: raw/code/2011.09643/src/models_simp.py#L178-L183] [code: raw/code/2011.09643/src/train_simp.py#L206].
9. Pair subsampling. Not stated in the paper. Code keeps all sampled pairs up to 10,000, then draws 10,000 without replacement each epoch [code: raw/code/2011.09643/src/selfsl.py#L78-L82].
10. Sampling rule. Paper: m most similar and m most dissimilar §4.2. Code takes the m + 1 most similar in the ranking, which includes the node itself, and the m most dissimilar, then drops self-pairs and merges duplicates distance.py.
11. Texas λ. Paper searches λ in {0.1, 1, 10} for disassortative graphs §5.1. The Texas script uses λ = 0.5 [code: raw/code/2011.09643/scripts/disassortative/texas.sh].
12. Weight decay. Paper tunes L2 in {5e-4, 5e-5} for disassortative graphs §5.1. All disassortative scripts use 5e-4 [code: raw/code/2011.09643/scripts/disassortative/actor.sh].
13. Splits and attack setup. Paper: random 60/20/20 splits §5.2 and 10/10/80 for the attack §5.3. Code loads one of ten pre-generated 60/20/20 split files, chosen by seed mod 10 [code: raw/code/2011.09643/src/geom_data_utils.py#L170]. For the attack it uses DeepRobust's nettack setting and pre-perturbed Metattack graphs [code: raw/code/2011.09643/src/sample.py#L26-L37]. The README says the attack runs use the largest connected component [code: raw/code/2011.09643/README.md#L45]. The 10/10/80 split is not in the code path shown here.
14. Attack hyperparameters. Paper: one setting for all perturbation rates §5.3. The repository ships only the 20% configuration for Cora [code: raw/code/2011.09643/scripts/adversarial/cora.sh].
15. Batch normalisation and self-loop weights. Both options exist in the code but are off by default train_simp.py; no reported script turns them on. The paper does not mention either.
16. Early stopping. Paper gives patience 100 for disassortative graphs only §5.1. Code monitors validation accuracy, not loss, and restores the best checkpoint train_simp.py earlystopping.py.
17. Initialisation. Not stated in the paper. Code draws score and self-loop weight vectors from uniform(−1, 1), sets the score bias to bias_init, and sets the self-loop bias to 0 models_simp.py models_simp.py.
18. Latent bug in layer init. The optional self-weight matrix is initialised by calling glorot on the main weight again, not on itself [code: raw/code/2011.09643/src/layers.py#L63-L65]. This only matters if self-weights are enabled, which the reported scripts do not do.

Pitfalls

• Per-branch activation. Implementing the paper's formula exactly and the code's per-branch ReLU give different models (Paper vs code, item 4). An agent must choose one and say which. The paper's text is the spec; the code is the only released implementation.
• Unstated output activation. It is not clear from the paper whether the last layer has σ. The code uses none [code: raw/code/2011.09643/src/models_simp.py#L86].
• Self-loop counts can be negative. K_i is an unbounded linear output, so γ·K_i can be negative; the score s_i is bounded by the sigmoid. The paper does not discuss the sign. The authors report that γD_n is very small on Cora and larger on Actor and Wisconsin §5.4. Learned ranges are shown for Cora, Actor and Wisconsin only §5.4 fig. 4.
• Initialisation of the self-loop bias. The paper's K_i = H_i W_K + b_K does not state b_K. The code uses 0 [code: raw/code/2011.09643/src/models_simp.py#L149-L154].
• Dense similarity matrix. Both the kNN graph and the SSL pairs need the full N × N cosine matrix, with a per-row sort [code: raw/code/2011.09643/src/selfsl.py#L152-L157] [code: raw/code/2011.09643/src/distance.py#L33-L40]. The paper's O(n²) remark §4.3 is a time bound; the code also holds the full N × N matrix in memory. It caches the results to disk selfsl.py.
• Binarised features change the graph. For non-binary features, binarising changes which nodes count as similar. The paper's cosine target is on X §4.2, so results will not match if X is used.
• Disassortative baselines are copied. The GCN, GAT and Geom-GCN numbers come from the GCNII paper, not from new runs §5.2. Compare SimP-GCN with new runs of the same baselines before claiming a gap.
• Selection criterion not stated. The paper does not say how λ, γ and b_s were picked, or on which split. The code's early stopping uses validation accuracy train_simp.py.
• Reported configuration is one hidden layer. With --nhiddenlayer 1 the middle block is an identity layers.py. The model is then exactly input layer, dropout, output layer.
• Attack setup is not fully portable. It depends on DeepRobust's nettack-setting data and on pre-perturbed Metattack graphs [code: raw/code/2011.09643/src/sample.py#L26-L37]. A reimplementation needs the same graphs and splits to compare.
• Single split per seed. For disassortative graphs, seed mod 10 picks the split, so the ten runs use ten different splits [code: raw/code/2011.09643/src/geom_data_utils.py#L170]. Report that choice, because averages over ten splits hide the spread between them.
• No variance reported. Tables give averages only §5.2 tab. 3 tab. 4.

Lineage

• Builds on: GCN, Kipf and Welling, arXiv:1609.02907 §2 §3. Its self-supervised joint training follows the style of jin2020selfsupervised and you2020does §4.2. No card for these is in this wiki.
• Compared against: LP, kNN-GCN, (A+kNN)-GCN, GAT, JK-Net, GCNII, GCNII*, Geom-GCN §5.1 tab. 3 tab. 4. On the attack: GCN-Jaccard and Pro-GNN (arXiv:2005.10203) §5.3 fig. 2. None of these has a card in this wiki.
• Superseded by: not stated in this wiki.