Towards Robust Graph Neural Networks for Noisy Graphs with Sparse Labels

1 INTRODUCTION

• Noisy edges contaminate neighborhood information, while sparse labels reduce unlabeled-node participation in training, weakening message passing.The paper identifies both issues as obstacles to GNN use in real-world applications.Source: §1 · pp. 1–2
• The framework is designed to address noisy edges and label sparsity together, a combination the paper says has received little attention.Earlier efforts separately address adversarial edges or use self-supervised tasks to alleviate sparse labels.Source: §1 · p. 2
• RS-GNN uses noisy-graph edges as supervision to learn a graph that down-weights or removes noisy edges and adds links, then trains a GNN on it.Predicted edges also regularize unlabeled-node predictions through label smoothness.Source: §1 · p. 2
• Experiments on real-world datasets demonstrate RS-GNN's robustness on noisy and clean graphs with limited labeled nodes.The authors list this as an experimental contribution.Source: §1 · p. 2

2.1 Graph Neural Networks

• GNN research includes spectral and spatial architectures, scalability and depth methods, and self-supervised tasks for learning node representations.Examples include GCN, GAT, and self-supervised methods such as SuperGAT and SE-GNN.Source: §2.1 · p. 2
• Graph construction methods build graphs from rules or learn them end-to-end, whereas RS-GNN removes or down-weights noisy edges and predicts missing edges.The stated focus is robustness with limited labels.Source: §2.1 · p. 2

2.2 Robust GNNs

• Robust-GNN work includes targeted and non-targeted attacks and defenses such as edge pruning, low-rank approximation, and Pro-GNN.Pro-GNN is described as learning a clean graph structure with a low-rank constraint, but addressing adversarial edges only.Source: §2.2 · p. 2
• RS-GNN targets noisy graphs and label sparsity together, using a link predictor to down-weight noisy edges and connect similar nodes rather than directly learning the graph.The paper presents the link-prediction approach as a way to reduce computational cost.Source: §2.2 · p. 3

3.1 Notations

• The setup represents an attributed graph as G = (V, E, X), with adjacency A, a limited labeled-node set, and potentially noisy topology.The preliminary section examines sparse-label GNN behavior and whether densification can help.Source: §3.1 · p. 3, §3 · p. 3

3.2 Basic Design and Inner Working of GNNs

• A K-layer GNN aggregates neighborhood representations to capture K-hop features and structure, letting labeled-node losses involve nearby unlabeled nodes.This is the message-passing rationale for using unlabeled nodes in semi-supervised classification.Source: §3.2 · p. 3

3.3 Analysis of GNNs with Sparse Labels

• With a small labeled set and a sparse graph, only labeled nodes and their K-hop neighbors enter training, limiting the unlabeled nodes involved.The analysis notes that K is usually 2 to 3 because deep GNNs have an over-smoothing issue.Source: §3.3 · p. 3
• As label rate falls below 0.1, the uninvolved-node rate rises significantly; above 0.1, most nodes participate and further label increases have marginal benefit.These observations are for a two-layer GNN across label rates from 0.01 to 0.25.Source: §3.3 · p. 3, Figure 2 · p. 3
• When the label rate is 0.01, tripling the raw graph's edge count drops Citeseer's uninvolved-node rate from 0.8 to around 0.3.The analysis randomly adds edges and reports similar observations on Cora and Cora-ML.Source: §3.3 · p. 3, Figure 2 · p. 3

3.4 Problem Definition

• Problem 1 jointly learns weighted adjacency S to down-weight or remove noisy edges and complete missing links, plus a GNN that predicts unlabeled-node labels.The link predictor maps node pairs to edge weights, and the GNN uses S and node attributes X.Source: §3.4 · p. 4

4.1 Link Prediction

• The MLP-based link predictor uses node features to down-weight noisy edges and predict missing links, producing a denser graph for message passing.A feature-similarity-weighted reconstruction loss trains the predictor; high-weight candidate links are retained or added.Source: §4 · p. 4, §4.1 · pp. 4–5

4.2 GNN for Node Classification

• The GNN classifier uses the learned adjacency matrix S and node features X to predict labels, with cross-entropy loss on labeled nodes.The denser graph includes more unlabeled nodes in message passing despite the limited labeled set.Source: §4.2 · p. 5

4.3 Label Smoothness on Unlabeled Nodes

• Label-smoothness regularization encourages similar predictions for unlabeled nodes and nodes connected by edges whose weights exceed a threshold.The regularizer weights prediction differences by the retained edge weights.Source: §4.3 · p. 5

4.4 Final Objective Function of RS-GNN

• RS-GNN jointly learns a link predictor and GNN classifier, using the predicted graph for node classification and label-smoothness regularization.The end-to-end objective balances adjacency reconstruction and label smoothness.Source: §4 · p. 4, §4.4 · p. 5

5 EXPERIMENTS

• The evaluation asks how RS-GNN performs across noisy graphs and label rates, and examines link prediction and label-smoothness contributions.The research questions also cover graph sparsity.Source: §5 · p. 5

5.1.1 Datasets.

• Experiments use Cora, Cora-ML, Citeseer, and Pubmed, with labeled-node rates of 1% for the first three datasets and 10% for Pubmed.Validation and test splits follow those described in the cited papers.Source: §5.1.1 · pp. 5–6

5.1.2 Noisy Graphs.

• The evaluation covers original benchmark graphs, random fake-edge additions and normal-edge removals, metattack edge perturbations, and nettack attacks targeting randomly selected 15% of nodes to induce misclassification.Source: §5.1.2 · p. 6

5.1.3 Baselines.

• RS-GNN is compared with GCN, SuperGAT, Self-Training, RGCN, GCN-Jaccard, GCN-SVD, and Pro-GNN.Baseline hyperparameters are tuned on the validation set, and experiments are conducted five times with mean and standard deviations reported.Source: §5.1.3 · p. 6, §5.1.4 · p. 6

5.2.1 Comparisons with baselines.

• RS-GNN outperforms recent robust GNNs and preprocessing baselines on noisy graphs with sparse labels, including graphs perturbed by attacks.The comparison covers raw, random-noise, non-targeted attack, and targeted attack graphs; label rates are 0.01 for Cora, Cora-ML, and Citeseer, and 0.1 for Pubmed.Source: §5.2.1 · pp. 6–7

5.2.2 Robustness Under Different Ptb Rates .

• Across 0%–25% perturbation at a 1% label rate, RS-GNN declines more stably and consistently outperforms the baselines.All baselines lose performance as perturbation increases; RS-GNN also declines, but remains more stable.Source: §5.2.2 · p. 7

5.3 Analysis of the Learned Graph

• Noisy edges receive significantly lower learned weights than normal edges, and low-weight normal edges indicate RS-GNN can also remove inherent structural noise.The weight distributions are examined on Cora and Cora-ML graphs with 30% random perturbation.Source: §5.3 · p. 7
• The learned graph enhances the involvement of unlabeled nodes.The paper reports additional details in Appendix B.Source: §5.3 · p. 7

5.4 Impacts of Label Rate and Graph Sparsity

• On Cora, RS-GNN's improvement becomes marginal as label rates rise on raw graphs, but remains significant on Metattack graphs.The label-rate sweep ranges from 0.01 to 0.06; the supplied Figure 6 presents performance on Cora across label rates.Source: §5.4.1 · p. 7, Figure 6 · p. 7

5.4.1 Impacts of Label Rate.

• On raw Citeseer graphs, sparsity was tested by retaining 20%, 60%, or 100% of edges, with average results over five runs.The experiment varies edge rate from 20% to 100% in steps of 40%.Source: §5.4.2 · p. 7

5.4.2 Impacts of Graph Sparsity.

• On Citeseer, RS-GNN's improvement over GCN grows from 6.4% at 100% Edge Rate to 9.2% at 20% Edge Rate.The supplied Table 2 reports accuracy (%) across Citeseer sparsity levels.Source: §5.4.2 · p. 8, Table 2 · p. 8

5.5 Ablation Study

• RS-GNN outperforms variants without edge addition or label smoothness, while a GCN link predictor performs much worse than the full method.The ablations use Cora with Metattack and random-noise perturbations; the gap between RS-GNN and the no-smoothness variant narrows as label rate rises.Source: §5.5 · p. 8

5.6 Parameter Sensitivity Analysis

• On Cora, large α yields stable, high accuracy on raw graphs but reduces performance on perturbed graphs; β values from 0.03 to 0.3 generally perform well.The paper attributes the difference to severe structural noise making faithful reconstruction of perturbed graphs undesirable.Source: §5.6 · p. 8, Figure 8 · p. 8

6 CONCLUSION AND FUTURE WORK

• RS-GNN uses noisy-graph edges as supervision to learn a denoised, densified graph and uses the generated graph to involve unlabeled nodes in prediction.The paper reports robustness on real-world noisy graphs with limited labeled nodes, while leaving graphs with attribute noise and noisy labels for future investigation.Source: §6 · p. 8

• The training procedure randomly initializes the link predictor and GCN classifier, then generates a graph with the link predictor.Source: A A TRAINING ALGORITHM OF RS-GNN · p. 10
• The link predictor and GCN classifier are jointly trained end-to-end using Eq. (7).Source: A A TRAINING ALGORITHM OF RS-GNN · p. 10
• Adam updates all parameters with a learning rate of 0.001.Source: A A TRAINING ALGORITHM OF RS-GNN · p. 10

• More unlabeled nodes are involved in training with generated graphs than with raw graphs.For a two-layer GNN, unlabeled nodes within two hops of labeled nodes participate; weighted edges are binarized at 0.5 for this comparison.Source: B MORE DETAILS OF THE LEARNED GRAPH · p. 10

Impacts of K

• Increasing K first improves performance substantially, then slightly reduces it as dissimilar-feature nodes enter the candidate set.Small K leaves too few candidate nodes and the learned graph sparse; very large K admits nodes dissimilar in raw-feature space.Source: C THE IMPACTS OF HYPERPARMETERS · p. 10

Impacts of Th

• An appropriate Th, such as 0.8, benefits predictions with label smoothness.The tested values were 0.6, 0.7, 0.8, and 0.9 on Metattack-perturbed graphs at perturbation rate 0.15 and label rate 0.01.Source: C THE IMPACTS OF HYPERPARMETERS · p. 10

Impacts of Tl

• Increasing Tl first improves performance and then reduces it when noisy edges remain or normal edges are likely to be deleted.Very small Tl leaves many down-weighted noisy edges; very large Tl limits assigned links.Source: C THE IMPACTS OF HYPERPARMETERS · pp. 10–11

Impacts of σ

• When σ is too large, positive and negative sample weights become similar and the link predictor is affected by noisy edges; when too small, weight variance becomes excessive.The tests vary σ across 30, 100, 300, and 1000 on Metattack-perturbed graphs at perturbation rate 0.15.Source: C THE IMPACTS OF HYPERPARMETERS · p. 11