Learning to Drop: Robust Graph Neural Network via Topological Denoising

In plain words

A graph neural network learns about each node by collecting messages from its neighbours. If some of the edges in the graph are misleading for the task, for example a link between two papers on unrelated topics, those messages make the learned features worse. Most fixes for this are blind to the task: they drop edges at random or by graph structure alone.

PTDNet makes the choice of edges part of training. A small learned scorer looks at the two endpoints of each edge and decides how much that edge should count for the task. The scorer and the GNN are trained together, so the GNN is rewarded when the edges it keeps help. The method adds two nudges. One pushes the scorer to keep fewer edges. The other pushes the kept graph toward a simpler shape in which nodes form tight groups with few links between groups. The idea is to remove noise without knowing which edges are noisy in advance. The paper reports that the gains grow as the graph gets noisier.

TL;DR

• PTDNet learns, per GNN layer, which edges to keep, trained jointly with the downstream loss §4.1 §4.2.
• Edge gates use a hard-concrete relaxation, so the keep decision is differentiable eq. 3 eq. 4.
• Two regularisers: an expected-edge-count penalty eq. 5 and a nuclear-norm penalty on the kept adjacency, approximated by top-K singular values §4.3 alg. 2.
• Author-reported gains on Cora, Citeseer, Pubmed and PPI with GCN, GraphSAGE and GAT tab. 3. The public code covers GCN only and does not reproduce the PPI setting (see Paper vs code).

Problem

Message passing aggregates features along every edge, so noisy or cross-community edges can hurt node representations and deepen over-smoothing when layers are stacked §4 intro. Existing sparsification and sampling methods (for example DropEdge and NeuralSparse) either act without the task signal or restrict the subgraph in ways the authors argue limit learning §2 §5.2. On Cora, the authors count 4,418 positive edges (endpoints share a label) and 1,011 negative edges, and show that removing negative edges improves GCN tab. 1 fig. 1 §1.

Method

Overview. The model has a denoising network and a GNN. For layer l the denoiser outputs a binary mask \mathbf{Z}^l over the edges, the GNN runs on the masked adjacency \mathbf{A}^l = \mathbf{A} \odot \mathbf{Z}^l, and the whole model is trained end to end with the relaxation below §4.1 §4.2.1. Inference costs time linear in the number of edges for the denoiser §4.1. The paper says the framework works with GCN, GraphSAGE, GAT and GIN §4.1.

Step 1: edge scores. For each edge (u,v) of layer l, an MLP f^l_{\theta^l} of the endpoint representations gives a score \alpha^l_{uv} = f^l_{\theta^l}(\mathbf{h}^l_u, \mathbf{h}^l_v) §4.2.1. The paper treats \alpha as the learned task-specific quality of the edge §4.2.2. The concrete relaxation then draws a continuous gate from \alpha (eq. 3) §4.2.2.

Step 2: stretch and clip. The gate is stretched to an interval (\gamma,\zeta) with \gamma<0<1<\zeta and clipped to [0,1], so some gates become exactly zero (eq. 4) §4.2.2.

Step 3: edge-count penalty. The expected number of non-zero gates has a closed form in \alpha (eqs. 5 and 10). The regulariser is \mathcal{R}_c §4.2.2.

Step 4: low-rank penalty. The nuclear norm of each masked adjacency is the sum of its singular values (eq. 11). The paper uses its top-K approximation with a power-iteration backward pass (alg. 2). The gap to the full norm is bounded by eq. 13, and \lceil |\mathcal{V}|/K \rceil times the approximation is an upper bound on the full norm §4.3.

Training. Algorithm 1 samples a subgraph for each GNN layer from that layer's denoiser, runs the layer, predicts from the last hidden state, then updates the GNN and denoiser parameters with the task loss and the regularisers alg. 1 §4.2.

Key equations (display forms as printed in the paper):

\sum_{l=1}^L \|\mathbf{Z}^l\|_0 = \sum_{l=1}^L \sum_{(u,v)\in\mathcal{E}} \mathbb{I}[z^l_{u,v}\neq 0] eq. 1

s^l_{u,v} = \sigma\big((\log\epsilon - \log(1-\epsilon) + \alpha^l_{uv})/\tau\big), \quad \epsilon \sim \mathrm{Uniform}(0,1) eq. 3

\bar{s}^l_{u,v} = s^l_{u,v}(\zeta-\gamma)+\gamma, \quad z^l_{u,v} = \min\big(1,\max(\bar{s}^l_{u,v},0)\big) eq. 4

\mathcal{R}_c = \sum_{l=1}^L \sum_{(u,v)\in\mathcal{E}} \big(1-\mathbb{P}_{\bar{s}^l_{u,v}}(0\mid\theta^l)\big) eq. 5

\mathbb{P}_{\bar{s}^l_{u,v}}(0\mid\theta^l) = \sigma\big(\tau\log\tfrac{-\gamma}{\zeta} - \alpha^l_{uv}\big) eq. 10

\mathcal{R}_{lr} = \sum_{l=1}^L \|\mathbf{A}^l\|_* = \sum_{l=1}^L \sum_{i=1}^{|\mathcal{V}|} |\lambda^l_i| eq. 11

\mathcal{R}_{lr} - \tilde{\mathcal{R}}_{lr} \le (|\mathcal{V}|-K)\sum_{l=1}^L |\lambda^l_{K+1}| eq. 13

The paper does not write the full training objective. It names two regularisers with weights \beta_1 (for \mathcal{R}_c) and \beta_2 (for the low-rank term) only in the experiments §5.5. See Paper vs code for the objective in the released code.

Algorithm 1, as the paper gives it in outline:

# PTDNet training  [alg. 1] [§4.2]
# Input:  graph (A, X), labels Y, number of GNN layers L
# Output: predictions for the downstream task

def training_epoch(adjacency, features, labels, num_layers):
    # Start from the node features  [alg. 1]
    hidden = features                                  # (n, m)
    for layer in range(num_layers):
        # Score every edge from its endpoint states  [§4.2.1]
        alpha = denoiser[layer](hidden, adjacency)     # (|E|,)
        # Draw a relaxed keep-gate per edge  [eq. 3] [eq. 4]
        gates = hard_concrete(alpha)                   # (|E|,)
        # Masked subgraph goes into this GNN layer  [§4.2.1] [alg. 1]
        hidden = gnn_layer(hidden, adjacency, gates)   # (n, d)
    # Task loss on the last hidden state  [alg. 1]
    task_loss = cross_entropy(hidden, labels)
    # Add the edge-count and low-rank penalties  [eq. 5] [§4.3]
    loss = task_loss + beta1 * edge_penalty + beta2 * lowrank
    return loss

Algorithm 2, the top-K nuclear-norm estimate used in the penalty:

# Approximate nuclear norm of each masked adjacency  [alg. 2] [§4.3]
# Input:  masked adjacencies, K
# Output: sum of approximated top-K singular values

def approx_nuclear(adjacencies, top_k):
    total = 0.0
    for adjacency in adjacencies:
        # Exact SVD; its output receives no gradient  [alg. 2]
        singular_values, vectors = svd_no_grad(adjacency)
        gram = adjacency.T @ adjacency                 # (n, n)
        for i in range(top_k):
            # Power iteration for the dominant eigenvector  [§4.3]
            vector = power_iteration(gram)             # (n,)
            # Rayleigh quotient, then square root  [alg. 2]
            eigenvalue = vector.T @ gram @ vector
            value = sqrt(abs(eigenvalue / (vector.T @ vector)))
            total = total + value
            # Deflate so the next iteration finds the next vector  [alg. 2]
            gram = gram - gram @ outer(vector, vector)
    return total

Hyperparameters

Paper-stated values are cited to the paper. Values marked "code default" are the defaults in the released code, not in the paper. They are not the paper's numbers unless the paper says so.

Results

Author-reported. Setup: node classification on Cora, Citeseer, Pubmed and PPI with GCN, GraphSAGE and GAT backbones; baselines are the basic backbone, DropEdge, NeuralSparse and PTDNet without the low-rank term (PTDNet-wl). Mean ± std over 10 runs, on a server with 8 Tesla V100 GPUs §5.1 §5.2. Metric is accuracy for single-label sets and micro-F1 for PPI §5.1.

Node classification tab. 3 (author-reported; the table's bold marks are not carried over):

Noisy edges (Cora). With 20,000 random edges added, the paper reports relative accuracy gains over the basic backbone of 37.37% (GCN), 13.4% (GraphSAGE) and 16.1% (GAT). DropEdge is worse than the basic backbone in most cases §5.3 fig. 3.

Denoising on synthetic data. The paper reports that DropEdge does not separate negative from positive edges, while PTDNet lowers the weight of negative edges and keeps this behaviour on test nodes §5.4 fig. 4.

Regularisers. Synthetic graphs with a lower share of positive edges get larger best \beta values; the paper's values by density are in tab. 4 §5.5. The low-rank term lowered the cross-community edge ratio from 0.211 to 0.189 in the ablation tab. 5 §5.5.

Approximation factor K. Accuracy rises with K while run time also rises §5.6 fig. 7.

Over-smoothing. In the paper's dense synthetic graph, GCN with 4 or more layers falls below an MLP baseline. PTDNet is reported to stay above all baselines across the depth range §5.7 fig. 8.

Link prediction (GCN encoder) tab. 6:

Dataset statistics tab. 2:

Paper vs code

Code: official repository flyingdoog/PTDNet at commit 481c6298d2eaa0fe4ecd14952d1949c0c00b3128. Its owner is the first author, Dongsheng Luo, and the README cites this paper and its arXiv id. There is no LICENSE file, so the code is cited by path and line only, and nothing from it is quoted. The repository also contains a NeuralSparse folder, an unofficial implementation of another paper, which was not used. The repository's README notes that hyperparameters need tuning per dataset README.md.

1. Hard-concrete stretch. Paper requires \gamma < 0 §4.2.2. Code defaults to \gamma = -0.0 config.py, which is zero, and the script only rejects \gamma > 0 config.py. With \gamma = 0, stretched gates never fall below zero, so the clip never yields exact zeros models.py.
2. Edge-count penalty. Paper sums over edges eq. 5. Code averages over edges (reduce_mean) models.py. With the default \gamma = -0.0, the code computes \log(-\gamma/\zeta) = -\infty, so the sigmoid saturates at 1 and the penalty has zero gradient (inferred from the code; not run here) models.py.
3. Objective. Paper gives no combined objective. Code uses cross-entropy
   • weight decay × L2 + λ1 × edge penalty + λ3 × nuclear norm + consistency × consistency loss train_PTDNet.py. The L2 term covers all trainable variables, including the denoiser train_PTDNet.py. The consistency term is not in the paper.
4. Multiple samples. Code draws L samples per layer, averages them models.py, and runs outL = 3 forward passes per step whose logits are averaged and tied by an L2 consistency term train_PTDNet.py. The paper describes one sampled subgraph per layer alg. 1.
5. Power iteration start. Paper starts the power iteration from a random vector and iterates §4.3. Code starts from the right singular vector returned by svds and runs one matrix product per singular value models.py.
6. Nuclear-norm masks. self.maskes is reset at the start of every forward call models.py. The nuclear term therefore uses only masks from the last of the outL passes models.py, while the edge penalty uses weights from all passes models.py.
7. Temperature. Paper does not give a schedule §4.2.2. Code starts at 2.0, multiplies by 0.99 each epoch and floors at 0.05 train_PTDNet.py.
8. Test-time mask. Paper says denoisers are used at test time §5.2. Code at evaluation uses the deterministic gate (sigmoid of α, stretched and clipped) with temperature 1.0 models.py models.py.
9. Denoiser architecture. Paper uses an MLP over the two endpoint states §4.2.1. Code applies one ReLU dense layer of width 16 to the source endpoint and a separate one to the target endpoint, concatenates them, and applies a linear layer to a single score models.py models.py. The two projections are separate, so the score of (u,v) need not equal that of (v,u) models.py.
10. Masks are directed. The mask is applied to each stored adjacency entry separately models.py, so the sampled subgraph can be asymmetric. The paper's notation treats an edge as a single object.
11. GCN normalisation. Each masked graph gets self-loops and symmetric degree normalisation inside every pass models.py. The paper does not describe this step.
12. Nuclear norm on CPU. The code moves each mask to NumPy and calls scipy.sparse.linalg.svds on every pass models.py. The paper gives no cost figures for this step.
13. Backbones. Repository defines GCN, GCN with DropEdge, MLP and PTDNet variants models.py models.py models.py models.py. GraphSAGE and GAT from tab. 3 are not in the repository. The basic and DropEdge runs are in separate training scripts train.py train_dropedge.py; these were not checked in detail.
14. PPI. Paper reports micro-F1 on PPI §5.1. The released loader handles the synthetic set and the Planetoid files, and the trainer uses single-label softmax cross-entropy utils.py train_PTDNet.py. The PPI rows of tab. 3 cannot be reproduced from the repository as shipped.
15. Split and selection. Public splits match §5.1 utils.py. Test accuracy is recorded when validation accuracy reaches a new best, and early stopping uses patience 100 on validation accuracy train_PTDNet.py config.py. The paper does not state its stopping rule for the benchmark runs.
16. Defaults and tuning. The code defaults (λ1 = 0.1, λ3 = 0.01, consistency = 0.01) do not match Table 4's weights, which use different scales tab. 4 config.py.

Pitfalls

• Gamma sign decides whether the model sparsifies. The paper needs \gamma < 0 so that the clip produces exact zeros §4.2.2. The released default is \gamma = -0.0, which is zero config.py. Use a strictly negative \gamma and check the fraction of exact zeros in the kept graph. The paper never gives a value for \gamma or \zeta beyond their signs.
• Edge penalty at default gamma. With \gamma = 0 the penalty's gradient is zero in the released code models.py (item 2 above). Any implementation following the code's defaults will not get the sparsity term.
• Temperature is unstated. \tau controls how sharp the gates are §4.2.2. The code's schedule train_PTDNet.py is the only concrete value available. Its effect on the reported results is not reported.
• Unstated objective and weights. The combined loss is not written in the paper. Implementers must choose how the two penalties are scaled. The paper's β values for benchmarks are not given, only for synthetic data tab. 4.
• Cost per step. Each training step calls an exact SVD per layer and per pass, on CPU, and the top-K approximation is computed through an extra power step alg. 2 models.py. Run time for the benchmarks is not reported. The authors give only the trend in K §5.6.
• Directed masks. Each stored direction is masked separately models.py. If the graph should stay undirected, symmetrise the scores explicitly; the paper does not say whether this is needed.
• Gaps versus variance. Several gaps in tab. 3 are smaller than the reported standard deviations. Example: Cora GCN, PTDNet 0.828 ± 0.026 versus NeuralSparse 0.821 ± 0.014. Pubmed GAT: PTDNet 0.793 ± 0.015 versus Basic 0.790 ± 0.008. Treat "state-of-the-art or matched" as the authors' wording §5.2.
• Variance outlier. The PTDNet-wl Citeseer GCN standard deviation is printed as 0.170, about four times the next largest in the table (0.043). Check the original table before reusing it.
• PPI cannot be reproduced from the repository (item 14).
• Link prediction tab. 6 shows GCN (GAE) with a higher Pubmed AUC (0.964) than PTDNet (0.963); the text does not mention this.

Lineage

• Builds on: DropEdge (random edge dropping during training) §2; NeuralSparse (task-guided sparsification that keeps at most k edges per node) §5.2 §5.3; hard-concrete gates via the reparameterisation trick §4.2.2; top-K nuclear norm via power iteration and deflation §4.3. Paper bibliography keys: rong2020dropedge, zheng2020robust, louizos2017learning, jang2016categorical, wang2019backpropagation.
• Compared against: Basic backbone, DropEdge, NeuralSparse, PTDNet-wl (no low-rank term) tab. 3 tab. 6.
• Superseded by: not known from content in this wiki.