TL;DR
This paper introduces GraphLT, a novel method to defend Graph Convolutional Networks (GCNs) against "perturbators" in online social networks (OSNs). GraphLT uses a Bayesian label transition model to repair noisy labels, improving GCN performance even when perturbators are hard to detect.
What Problem Does This Paper Address?
Online social networks (OSNs) are often analyzed using Graph Convolutional Networks (GCNs) for tasks like user profiling (node classification). However, a small group of users, termed "perturbators," can disrupt this process by engaging in random or arbitrary activities. These perturbators aren't necessarily malicious attackers but can still significantly degrade GCN performance. Existing defense mechanisms, like adversarial training or node removal, struggle when perturbators are few and their actions are subtle, as they often require identifying the attackers or their patterns first. This paper addresses the challenge of defending GCNs in OSNs from these subtle, non-malicious perturbations when perturbators are difficult to detect.
Methods
The core of GraphLT is a novel Bayesian label transition model. Instead of directly identifying perturbators, GraphLT assumes that the observed noisy labels (due to perturbators) are inaccurate. It then uses a Gibbs sampling-based inference approach to learn a label transition matrix. This matrix essentially models how the noisy labels might have originated from the true, unobserved "latent" labels.
Here's a breakdown of the process:
- GCN Training: A standard GCN is trained on the OSN data using the observed noisy labels.
- Label Transition Inference: GraphLT takes the GCN's predicted labels and applies the learned label transition matrix. This process iteratively refines the labels by sampling new inferred labels based on the GCN's predictions and the current estimate of the transition matrix.
- Dynamic Update: The label transition matrix is dynamically updated in each iteration, allowing the model to adapt and improve its approximation of the true latent labels. This iterative refinement helps to "repair" the GCN's predictions.
- Warm-up Stage: A crucial aspect is a "warm-up" phase where an initial label transition matrix is computed on the training data. This helps to establish a baseline before applying the dynamic updates on the test data.
The key novelty lies in using Bayesian inference and Gibbs sampling to learn a dynamic label transition matrix, which implicitly corrects for the impact of perturbators without needing to explicitly identify them.
Datasets
The paper evaluates GraphLT on seven benchmark datasets:
- KDD20(S1) and KDD20(S2) (from the KDD Cup 2020 competition)
- Cora
- Citeseer
- AMZcobuy
- Coauthor
These datasets vary in size, from small citation networks (Cora, Citeseer) to large graphs (KDD20, Reddit), allowing for a comprehensive evaluation of GraphLT's generalization capabilities.
Key Insights and Ideas
- Implicit Perturbator Handling: The most significant insight is that GraphLT can effectively mitigate the impact of perturbators without explicitly identifying them. By focusing on repairing noisy labels, it bypasses the difficulty of detecting subtle perturbations.
- Bayesian Label Transition as a Repair Mechanism: The paper demonstrates that a Bayesian approach to label transition can serve as a powerful tool for "deperturbing" GCNs, essentially correcting for label noise introduced by perturbators.
- Dynamic Matrix Adaptation: The dynamic updating of the label transition matrix is key to GraphLT's success. This allows the model to adapt to the specific characteristics of the noise and progressively improve its accuracy.
- Generalization Across GCN Variants: GraphLT is shown to be effective when applied on top of different GCN architectures (GCN, SGC, GraphSAGE), highlighting its broad applicability.
- Performance on Large Graphs: The effectiveness of GraphLT's warm-up stage appears to be more pronounced on larger graphs, suggesting that it can better leverage the structure of larger datasets to learn a robust initial transition matrix.
Key Results
- Performance Improvement: GraphLT consistently improves the performance of GCN-based node classifiers, both in unperturbed and perturbed environments.
- Repairing Noisy Labels: For GCNs trained with noisy labels (up to 30% noise ratio), GraphLT significantly boosts accuracy. For example, on Citeseer with a 0.3 noise ratio, accuracy increased from 66.47% to 76.78%.
- Outperforming Competitors: In defending against non-malicious perturbations, GraphLT achieved superior performance compared to several state-of-the-art defending methods (RGCN, GRAND, ProGNN, GNNGUARD) across most of the seven benchmark datasets. For instance, on Reddit, GraphLT achieved 95.87% accuracy, outperforming the next best method (GRAND) by over 9%.
- Generalization: The benefits of GraphLT were observed across different GCN variants (GCN, SGC, GraphSAGE) and dataset sizes.
Limitations and Future Work
- Dependence on Training Graph: The current inference of GraphLT relies on the warm-up label transition matrix derived from the training graph. This means it primarily handles perturbations on the test graph.
- Future Work: The authors suggest extending GraphLT to defend against poisoning perturbations by iteratively updating noisy labels. They also propose adapting the model to detect anomaly perturbators in dynamic graphs.
Summary updated