Generative and Contrastive Self-Supervised Learning for Graph Anomaly Detection

In plain words

Imagine a social network where most users behave like their friends, and a few behave very differently from everyone around them. This paper looks for those odd ones out without anyone labelling them in advance. For each user, it looks at a small neighbourhood around that user, hides the user's own profile, and asks the model to rebuild that profile from the neighbourhood alone. If the rebuilt profile does not match the real one, the user is suspicious. A second test checks whether the user's own profile agrees better with its neighbourhood than with the neighbourhood of some unrelated user.

Both tests run on the same small neural network, and the two scores are added together. The method is trained only on the graph itself, so it needs no anomaly labels. Its quality is judged by planting fake anomalies into real benchmark graphs and checking whether they are ranked high.

TL;DR

• Unsupervised node-level anomaly detection on attributed graphs, scored by ROC-AUC §1 §5.2.
• Two random-walk-with-restart views of fixed size K around each target node; the target's features are zeroed in the views §4.1.
• Generative term: a one-layer GCN autoencoder reconstructs the target's features from its views §4.2 eq. 4–7.
• Contrastive term: a bilinear discriminator separates the target from its own views and from a negative subgraph §4.3 eq. 10–15.
• Author-reported AUC on injected anomalies beats six baselines on all six datasets, with the largest margins on citation graphs tab. 3 §5.3.
• The arXiv v2 text (LaTeX dated 2022-01-23) is the source used here. The arXiv comment says the work was published in IEEE Transactions on Knowledge and Data Engineering.

Problem

The paper addresses unsupervised anomaly detection on an attributed graph G = (X, A): no labels are used, and the output is a score for every node, ranked in descending order §3. The authors argue that existing graph autoencoders reconstruct each node from its own attributes and the whole structure, and so ignore the local context that defines normal behaviour §1. Existing contrastive methods (CoLA) use one subgraph view and leave generative supervision unused §2.1.

Evaluation uses benchmark graphs with anomalies injected synthetically, because the datasets have no ground-truth anomalies §5.1.

Method

Overview: the model has two losses and one score. Both losses use the same GCN encoder fig. 2 §4. Anomalies are scored by the reconstruction error (generative) and by the contrastive discrimination gap (contrastive) §4.4.

1. Target node sampling. Target nodes are drawn uniformly without replacement, one batch at a time §4.1, item 1. Batch size is not stated in the text (see Hyperparameters).
2. View sampling. For each target, two views are sampled by random walk with restart. Each view has a fixed size K, which sets the radius of the context §4.1, item 2. The restart probability is not stated.
3. Anonymisation. The target node's features are zeroed inside each view, so the target's own attributes cannot help rebuild it §4.1, item 3. The paper indexes the target as the last row of each view, written [-1,:] eq. 6.
4. Encoder. A one-layer GCN with weights W_enc and a non-linearity σ (ReLU given as an example) embeds each view with its normalised adjacency eq. 4. A target embedding is also computed from the target's own features with no adjacency, using the same W_enc eq. 8.
5. Decoder. A one-layer GCN with weights W_dec reconstructs the features of each view from the view embeddings eq. 5.
6. Generative loss. The squared error between the reconstructed and original target features, computed in each view, is averaged over the two views and the nodes eq. 6 eq. 7.
7. Readout. Average pooling of the view's node embeddings gives one subgraph vector per view eq. 9.
8. Bilinear discriminator. Scores are s = σ(h_t W_s g^T) for a positive pair (target, its own view) and s̃ for a negative pair (target, a subgraph from elsewhere in the graph) eq. 10–13. W_s is learnable. The paper says negatives are randomly cropped subgraphs that differ from the two views §4.3. The sampling procedure is not otherwise described.
9. Contrastive loss. Per view, a binary cross-entropy style loss over positive and negative scores with a factor of 1/(2N) eq. 14. The two views are averaged with a factor of 1/2 eq. 15.
10. Training objective. L = α·L_con + β·L_gen eq. 19. α and β weight the two losses. The same α and β reappear in the score below §4.5.
11. Anomaly score. Per node, the generative score is the mean over views of a scaled squared reconstruction error eq. 16. The contrastive score is the mean over views of a scaled (negative score − positive score) gap eq. 17. The final score is α·f_con + β·f_gen eq. 18.
12. Repetition. Views are re-sampled and the score is recomputed R times, then averaged, because two views are only partial evidence of the context §4.4 alg. 1.

Pseudocode for one training step, following alg. 1 and eq. 4–19. Shapes are per batch of B targets with K nodes per view.

# One training step over a batch of target nodes  [alg. 1] [§4.5]
# Input:  X (N, D) features, A (N, N) adjacency, batch (B,) node ids
# Output: scalar training loss  [eq. 19]

def training_step(X, A, batch, K, alpha, beta):
    # 1. Two random-walk-with-restart views per target, size K  [§4.1]
    # The target is the last row of each view  [§4.2] [eq. 6]
    views_1 = sample_rwr_views(A, X, batch, K)
    views_2 = sample_rwr_views(A, X, batch, K)
    # 2. Zero the target row of each view (anonymisation)  [§4.1]
    anon_1 = zero_last_row(views_1.features)    # (B, K, D)
    anon_2 = zero_last_row(views_2.features)    # (B, K, D)
    # 3. One-layer GCN encoder on each view, shared W_enc  [eq. 4]
    h_1 = act(norm(views_1.adj) @ anon_1 @ W_enc)   # (B, K, D')
    h_2 = act(norm(views_2.adj) @ anon_2 @ W_enc)
    # 4. Target embedding from its own features, no adjacency  [eq. 8]
    h_t = act(X[batch] @ W_enc)                      # (B, D')
    # 5. One-layer GCN decoder on each view, weights W_dec  [eq. 5]
    x_hat_1 = act(norm(views_1.adj) @ h_1 @ W_dec)   # (B, K, D)
    x_hat_2 = act(norm(views_2.adj) @ h_2 @ W_dec)
    # 6. Generative loss: squared error on the target row  [eq. 6] [eq. 7]
    # Sum vs mean over features is not stated; see Pitfalls
    err_1 = squared_error(x_hat_1[:, -1], X[batch])
    err_2 = squared_error(x_hat_2[:, -1], X[batch])
    loss_gen = 0.5 * (err_1 + err_2)
    # 7. Readout: average over the K rows of each view  [eq. 9]
    g_1 = mean(h_1, axis=1)                          # (B, D')
    g_2 = mean(h_2, axis=1)
    # 8. Bilinear scores: positive pair and negative pair  [eq. 10-13]
    # Negative subgraphs are not specified beyond "cropped, other" [§4.3]
    neg_1 = sample_negative_views(A, X, batch, K)    # (B, D') readout
    neg_2 = sample_negative_views(A, X, batch, K)
    pos_1 = sigmoid(h_t @ W_s @ g_1.T)               # (B, B) diagonal
    pos_2 = sigmoid(h_t @ W_s @ g_2.T)
    neg_s1 = sigmoid(h_t @ W_s @ neg_1.T)
    neg_s2 = sigmoid(h_t @ W_s @ neg_2.T)
    # 9. Contrastive loss per view, then averaged  [eq. 14] [eq. 15]
    loss_con_1 = -0.5 * mean(log(pos_1) + log(1 - neg_s1))
    loss_con_2 = -0.5 * mean(log(pos_2) + log(1 - neg_s2))
    loss_con = 0.5 * (loss_con_1 + loss_con_2)
    # 10. Weighted sum of the two losses  [eq. 19]
    return alpha * loss_con + beta * loss_gen

Inference: scores for every node, averaged over R rounds of fresh views.

# Anomaly score per node, averaged over R sampling rounds  [§4.4] [alg. 1]
# Input:  trained model, X (N, D), A (N, N), rounds R, alpha, beta
# Output: score (N,), higher means more anomalous

def score_nodes(model, X, A, R, alpha, beta):
    # 1. Accumulate one score per node per round  [§4.4]
    total = zeros(N)
    for each round in range(R):
        # 2. Fresh views and their embeddings  [§4.1]
        views_1, views_2 = sample_views(A, X, round)
        # 3. Generative score: scaled squared error of the target
        # row, averaged over the two views  [eq. 16]
        f_gen = 0.5 * sum_j delta_1(squared_error(x_hat_j, X))
        # 4. Contrastive score: scaled (negative minus positive)
        # gap, averaged over the two views  [eq. 17]
        f_con = 0.5 * sum_j delta_2(neg_j - pos_j)
        # 5. Weighted sum of the two scores  [eq. 18]
        total += alpha * f_con + beta * f_gen
    # 6. Mean over the R rounds  [alg. 1]
    return total / R

The paper's Equation 16 and 17 scale-factors δ¹ and δ² are called "scalers" that map to [0, 1] §4.4. Their exact form is not stated.

Complexity, as stated by the authors §4.5.1: sampling costs O(ηK) per target (η is the mean degree). Each step costs O(K²). Training is O(N·K(η+K)) and inference adds a factor R.

Figures, described in words: fig. 1 is the introductory workflow. fig. 2 is the framework with graph view sampling, self-supervised discrimination and anomaly scoring. fig. 3 shows ROC curves on the six datasets. fig. 4 shows AUC over a grid of α and β on Cora, BlogCatalog and Flickr. fig. 5 shows AUC against R, K, D' and the negative ratio.

Hyperparameters

Dataset statistics as published tab. 2. The anomaly counts are the injected numbers; the paper does not say how the node and edge counts were derived.

Results

Author-reported. Setup: six benchmark graphs with synthetic injected anomalies §5.1. Metric: ROC-AUC §5.2. Baselines: AMEN, Radar, ANOMALOUS, DOMINANT, DGI and CoLA §5.2. The baseline runs are not described as re-runs or copied numbers. Model size: a one-layer GCN with D'=64 §5.2. Hardware: not stated.

AUC by method and dataset tab. 3. Best per column is the paper's bold entry:

Ablation tab. 4: "Gen" removes the contrastive module, "Con" removes the generative module, "Unweighted" sets α = β = 1 in eq. 18, and "Unscaled" removes the scalers in eq. 16 and 17.

Headline comparison as stated: the method beats all six baselines on all six datasets §5.3. Gains are larger on citation graphs than on the two social graphs, which the authors link to the higher mean degree of the social graphs (32.35, against 2.51 for citation graphs) and to information lost when sampling fixed-size views §5.3.

Paper vs code

No official code. Searches: the arXiv abstract page lists no code repository. The paper links no repository; its only code footnotes are commented out in the LaTeX and point to baseline code §5.2. A GitHub repository search for "SL-GAD" returned KimMeen/SL-GAD (MIT, a user account, described as a PyTorch implementation of the TKDE 2021 paper). Its owner is not one of the six authors and the paper does not link it, so it was not used. Its contents were not checked against the paper.

Pitfalls

• Evaluation rounds conflict. §5.2 sets R = 256, while §5.5.2 says R is fixed at 160, chosen as a compromise between stability and runtime. Which value produced tab. 3 is not stated.
• β grid conflict. §5.2 lists β ∈ {0.2, 0.4, 0.6, 0.8, 1}; §5.5.1 tunes over {0.2, 0.4, 0.6, 0.8}. The β chosen for each dataset is not listed.
• Batch size and random-walk restart are missing. Algorithm 1 uses a batch size B and a random walk with restart, but neither has a value alg. 1 §4.1.
• Anomaly scalers are unspecified. δ¹ and δ² are said to map to [0, 1] §4.4, but the functional form is not given. The ablation shows that removing them lowers AUC by up to about 0.05 on CiteSeer (Unscaled vs full, tab. 4).
• Squared error normalisation is ambiguous. Eq. 6 writes a sum over nodes with a 1/N factor, but the feature-dimension reduction (sum or mean over the D features) is not stated.
• Loss scale has two halves. Eq. 14 has a factor 1/(2N) per view and eq. 15 adds a further 1/2 over views. The overall scale of L_con is therefore smaller than a plain mean, and this interacts with β and the learning rate.
• Negatives are underspecified. The text says negatives are "randomly cropped subgraphs from G ... different from" the two views §4.3. It does not say how many nodes they have, how they are chosen, or how they are de-duplicated. Only the count of one negative per target is given §5.5.5.
• Contrastive anchor is not anonymised. The text says raw target attributes do not contribute to the view embeddings §4.1, item 3. Eq. 8, however, embeds the target's unmasked features as the contrastive anchor. The separation is between the anchor and the views, not between masked and unmasked information for the whole model.
• Numerically sensitive terms. log(1 − s̃) and log(s) in eq. 14 diverge when sigmoid outputs approach 0 or 1. No epsilon or clipping is mentioned.
• Injected anomalies, not real ones. Anomalies are created by replacing features with those of distant nodes and by making groups fully connected §5.1. The number of groups and the value of q are not stated. Results on real anomaly labels are not reported.
• Fixed-size views lose information on dense graphs. The authors note this for the social graphs §5.3 and leave an efficient sampling strategy for high-degree graphs as future work.
• Inference cost. Scores are averaged over R rounds for every node. §4.5.1 gives inference cost as a factor R of the training cost. The R values in this paper (160 or 256) make inference the dominant cost.
• Ablation interpretation. Removing the weights (α = β = 1) lowers AUC by up to about 0.06 on ACM tab. 4. The authors attribute the gap to a mismatch between training (α, β ≠ 1) and inference §5.4, which is an explanation, not a test.

Lineage

• Builds on: CoLA, a contrastive node-versus-subgraph detector. SL-GAD uses its bilinear discriminator, its subgraph-based scoring and repeated rounds §2.1 §4.3 §4.4. Also builds on DOMINANT, a graph autoencoder with reconstruction-error scoring §2.1 §4.2.
• Compared against: AMEN, Radar, ANOMALOUS, DOMINANT, DGI and CoLA tab. 3.
• Superseded by: not stated in this wiki.