PaperlayerView exact revision on arXiv

Source-linked AI summary

NRGNN: Learning a Label Noise-Resistant Graph Neural Network on Sparsely and Noisily Labeled Graphs

Enyan Dai, Charu Aggarwal, Suhang Wang

arXiv:2106.04714v1cs.LG

TL;DR

NRGNN addresses semi-supervised node classification when graph labels are sparse and noisy, a setting where corrupted information can propagate through message passing. It adds similarity-based links and pseudo labels to improve supervision, and experiments report stronger performance and noise resistance than baselines across tested settings.

  • Problem

    Sparse, noisy graph labels can degrade GNN node classification because corrupted information propagates to unlabeled nodes, while i.i.d. noisy-label methods assume more labels and do not directly fit GNNs.

  • Method

    NRGNN uses an edge predictor to connect unlabeled nodes with similar noisy or pseudo-labeled nodes, then expands the label set with accurate pseudo labels for robust classification.

  • Results

    NRGNN achieves higher performance than Self-Training and CP across tested scenarios and becomes more advantageous as label noise increases.

  • Takeaways & Limitations

    Extending the label set with accurate pseudo labels and adding links to labeled nodes supports more robust GNN learning under noisy and limited supervision.

  • Takeaways & Limitations

    The theoretical analysis assumes conditions on class-label probabilities and neighborhood structure, including that correctly class-labeled nodes are more likely than incorrectly class-labeled nodes.

Abstract

from arXiv · show

Graph Neural Networks (GNNs) have achieved promising results for semi-supervised learning tasks on graphs such as node classification. Despite the great success of GNNs, many real-world graphs are often sparsely and noisily labeled, which could significantly degrade the performance of GNNs, as the noisy information could propagate to unlabeled nodes via graph structure. Thus, it is important to develop a label noise-resistant GNN for semi-supervised node classification. Though extensive studies have been conducted to learn neural networks with noisy labels, they mostly focus on independent and identically distributed data and assume a large number of noisy labels are available, which are not directly applicable for GNNs. Thus, we investigate a novel problem of learning a robust GNN with noisy and limited labels. To alleviate the negative effects of label noise, we propose to link the unlabeled nodes with labeled nodes of high feature similarity to bring more clean label information. Furthermore, accurate pseudo labels could be obtained by this strategy to provide more supervision and further reduce the effects of label noise. Our theoretical and empirical analysis verify the effectiveness of these two strategies under mild conditions. Extensive experiments on real-world datasets demonstrate the effectiveness of the proposed method in learning a robust GNN with noisy and limited labels.

1 INTRODUCTION

GNNs support semi-supervised node classification through message passing, but sparse and noisy labels can degrade predictions as incorrect information propagates through graph neighborhoods. NRGNN addresses this by adding similarity-based links and accurate pseudo labels to provide more reliable supervision.

  • GNN message passing propagates labeled-node information to unlabeled nodes for semi-supervised node classification.
  • Sparse, noisy labels arise in applications such as geolocation prediction and bot detection, where labels may be limited, incorrect, or costly to collect.
  • Noisy labels can cause poor generalization and spread incorrect information to unlabeled neighbors, while sparse supervision limits correction by correctly labeled nodes.
  • NRGNN links unlabeled nodes to labeled nodes with high feature similarity, relying on the possibility that similar nodes share labels and thereby bringing more correct label information.
  • NRGNN uses a GNN-based edge predictor to add links and a densified graph to obtain pseudo labels, extending supervision for robust node classification.

2 RELATED WORK

Prior work studies GNNs and noisy-label learning separately, but methods designed for i.i.d. data do not directly address label-noise propagation through graph message passing. NRGNN targets noisy and limited labels in graph-structured data.

  • GNN research includes spectral- and spatial-based architectures for modeling graph-structured data in applications such as social, financial, and traffic networks.
  • GNNs are vulnerable to noisy labels because message passing can transmit corrupted label information to unlabeled nodes.
  • Noisy-label methods for i.i.d. data commonly use loss correction or sample selection, including approaches that identify or exploit presumed clean samples.
  • These i.i.d. approaches may not directly apply to GNNs because graph message passing propagates noise and graph labels are often both noisy and limited.

3 PRELIMINARIES

The paper formulates robust node classification with a small noisy labeled set and analyzes how graph links and pseudo labels affect GNN predictions. Its framework uses similarity-based connections and confidence-based pseudo-label generation to strengthen supervision.

  • 3.2 Preliminaries about GNN: GNN layers update node representations by aggregating neighborhood information, allowing representations to capture multi-hop network neighborhoods.
  • 3.3 Problem Definition: The task is to predict true labels for unlabeled nodes from a graph whose small labeled set contains corrupted labels.
  • 3.4 How the Size of Noisily Labeled Neighbors Affect the Node Classification: The analysis models an unlabeled node alongside unlabeled neighbors, correctly class-labeled neighbors, and incorrectly class-labeled neighbors to study message-passing effects.
  • 3.4 How the Size of Noisily Labeled Neighbors Affect the Node Classification: Linking an unlabeled node with more similar noisily labeled nodes can improve its predicted probability for the correct class under the stated assumptions.
  • 3.4 How the Size of Noisily Labeled Neighbors Affect the Node Classification: Similarity-based links are evaluated by training GCNs on an initial graph, a graph linking unlabeled to labeled nodes, or a graph linking unlabeled nodes to one another.
  • 3.5 A Strategy On Graphs with Small Amount of Noisy Labels: When noisy labels are scarce or node similarity to labeled nodes is weak, accurate pseudo labels can expand supervision and make the linking strategy more useful.
  • 3.5 A Strategy On Graphs with Small Amount of Noisy Labels: The framework caption describes connecting an unlabeled node to a pseudo-labeled node when its expected class score exceeds competing neighborhood-based scores.

4 METHODOLOGY

NRGNN combines GNN-based edge prediction, pseudo-label mining, and final classification to improve learning on sparsely and noisily labeled graphs. It adds predicted links to labeled or accurate pseudo-labeled nodes, then uses the expanded supervision and graph structure for robust prediction.

  • Edge Prediction: NRGNN uses a GNN-based edge predictor to identify missing links between unlabeled nodes and similar labeled nodes.The predictor is motivated by the value of structural information beyond feature similarity and is trained with negative sampling to avoid domination by absent edges.
  • Accurate Pseudo Label Prediction: The edge predictor constructs a densified graph by adding links from unlabeled nodes to labeled nodes whose predicted edge weights exceed threshold t.Existing links are retained, while low-weight candidate links are filtered out.
  • Accurate Pseudo Label Prediction: A GNN classifier trained on the densified labeled graph serves as a pseudo-label miner for selecting high-confidence labels on unlabeled nodes.The pseudo-label process uses prediction confidence and threshold T_p to retain accurate pseudo labels.
  • Robust Classification with Edge Predictor and Accurate Pseudo Labels: Accurate pseudo labels provide additional supervision and enable links from unlabeled nodes to an expanded labeled set V_A = V_L ∪ V_P.The same edge-prediction mechanism adds links to pseudo-labeled nodes, facilitating information propagation to unlabeled nodes.
  • Robust Classification with Edge Predictor and Accurate Pseudo Labels: The final GNN classifier uses noisy labels and accurate pseudo labels jointly on the augmented graph for robust label prediction.The edge predictor, pseudo-label miner, and final classifier are jointly trained, with hyperparameters α and β balancing their loss contributions.

5 EXPERIMENTS

Experiments evaluate NRGNN on real-world graphs with sparse training labels and corrupted labels, comparing it with GNN and noisy-label baselines. Across noise settings, NRGNN is reported to be more robust and effective, particularly through pseudo-label mining and added links.

  • Research Questions: The experiments address robustness to noise type and level, noisy-label size and graph sparsity, backbone flexibility, and component contributions.The ablation questions specifically examine the edge predictor and pseudo-label miner.
  • Experimental Setup: NRGNN is evaluated on four benchmark datasets with 5% training nodes for Cora and Citeseer and 1% for Pubmed and DBLP.Training labels are corrupted using uniform and pair noise, and results are averaged over five runs.
  • Comparisons with Baselines: Pseudo-label methods outperform plain GCN and GIN, while NRGNN achieves higher performance than Self-Training and CP across various scenarios.The authors attribute this to adding links between unlabeled nodes and noisy or pseudo-labeled nodes.
  • Noise Robustness: As label noise increases, all baselines deteriorate sharply, but NRGNN is more resistant and its performance gap increases relative to the baselines.The authors connect this robustness to accurate pseudo labels and links between unlabeled and extended labeled nodes.
  • Noise Robustness: NRGNN also outperforms GCN and pseudo-label baselines when label noise is little or absent.The reported explanation is that high-quality added edges facilitate GNN message passing.

5.3 Impacts of Noisy Label Size

The study varies the training-label rate under fixed uniform and pair noise to assess how noisy-label size affects NRGNN. NRGNN shows its largest improvement with the smallest label rate and retains a substantial advantage as label size grows.

  • Noisy Label Size: NRGNN brings its most significant performance improvement when the label rate is 2.5%.The experiments vary the training size across 2.5%, 5%, 7.5%, and 10% with both noise rates fixed at 0.2.
  • Noisy Label Size: As label size increases, NRGNN’s gap over the baselines decreases only slightly and remains large.The authors report that NRGNN still outperforms the baselines when labeled-node size is large.

5.4 Impacts of the Graph Sparsity

This section examines NRGNN’s edge predictor, backbone flexibility, and component contributions through sparsity experiments and ablations. The results support the roles of learned links and pseudo-label mining in robust classification.

  • Graph Sparsity: NRGNN uses an edge predictor trained with adjacency supervision to predict missing links between unlabeled and labeled nodes.The sparsity experiment tests whether this predictor can learn useful links when the original graph is randomly sparsified.
  • Ablation Study: NRGNN_GIN achieves comparable results with NRGNN, indicating flexibility across GNN backbones.The GIN classifier is trained on a graph densified with links to extended labeled nodes and accurate pseudo labels.
  • Ablation Study: Removing the edge predictor substantially worsens performance, supporting the necessity of learning high-quality links.The comparison is between NRGNN and the NRGNN\E variant.
  • Ablation Study: NRGNN outperforms both NRGNN\A and NRGNN\P, indicating that pseudo-label mining and high-quality pseudo labels contribute to robustness.NRGNN\P still outperforms GCN, showing that linking unlabeled nodes with labeled nodes can mitigate label-noise effects.

6 CONCLUSION

The paper studies semi-supervised node classification on sparsely and noisily labeled graphs and proposes NRGNN to improve robustness through graph augmentation and pseudo-label expansion.

  • NRGNN addresses semi-supervised node classification when graph labels are both sparse and noisy.
  • The framework predicts missing links to connect unlabeled nodes with labeled nodes and mines pseudo labels to expand supervision.
  • Experiments on real-world datasets evaluate NRGNN across varied noise types and levels, label and graph sparsity, and parameter settings.

Algorithm 1: Training Algorithm of NRGNN.

Algorithm 1 takes a graph, labels, and training parameters, then returns the graph classifier, pseudo-label miner, and edge predictor after joint optimization.

  • The algorithm accepts G, labels Y, K, t, T_p, α, and β, and outputs f_G, f_P, and f_E.
  • It obtains the graph S_L using the edge predictor f_E through Eq. (7).
  • The parameters of f_G, f_P, and f_E are jointly optimized using Eq. (14).

A TRAINING ALGORITHM

NRGNN pretrains its edge predictor and pseudo-label miner, constructs augmented graphs and pseudo labels, and jointly trains the three components.

  • The edge predictor f_E and pseudo-label miner f_P are pretrained with Eqs. (6) and (9).
  • The edge predictor generates S_P, enabling the pseudo-label miner to obtain accurate pseudo labels.
  • The graph S_A links nodes with similar extended labeled nodes so f_G can make robust predictions.
  • Finally, f_G, f_E, and f_P are jointly trained with Adam using learning rate 0.001.

B PROOF OF THEOREM 3.1

The proof shows that linking an unlabeled node to additional correctly class-associated labeled nodes increases its expected predicted probability for that class.

  • The proof analyzes the predicted probability that an unlabeled node v_u belongs to class c.
  • V_a denotes unlabeled neighbors, while V_n denotes linked nodes with noisy labels.
  • The proof distinguishes p_t, the probability of assigning the correct class label, from p_f, the probability of assigning class c to another class.
  • Because p_t exceeds p_f and the relevant similarity expectations are ordered, the expected predicted probability increases after adding these links.
  • When v_u is linked to k labeled nodes belonging to class c, the resulting expected probability is compared with the original expectation.
  • The expected probability that v_u belongs to class c increases as k increases.

C PROOF OF THEOREM 3.2

The proof shows that linking unlabeled nodes with pseudo labels raises the expected class-related quantity when the pseudo-label expectation exceeds the original unlabeled expectation. As the number of linked nodes increases, the expected quantity correspondingly improves.

  • The pseudo-label expectation E(s_pc) exceeds the original unlabeled expectation E(y_uc).
  • After linking k nodes with pseudo labels, E(y_uc) is expressed as a weighted combination of the original expectation and E(s_pc).
  • As k increases, E(y^k_uc) becomes higher because E(s_pc) exceeds E(y_uc).
Loading 2106.04714v1…