Anti-perturbation of Online Social Networks by Graph Label Transition

Jun Zhuang, Mohammad Al HasanarXiv 2020 · OpenReview

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:

  1. GCN Training: A standard GCN is trained on the OSN data using the observed noisy labels.
  2. 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.
  3. 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.
  4. 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
  • Reddit

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

Abstract

Online social networks (OSNs) classify users into different categories based on their online activities and interests, a task which is referred as a node classification task. Such a task can be solved effectively using Graph Convolutional Networks (GCNs). However, a small number of users, so-called perturbators, may perform random activities on an OSN, which significantly deteriorate the performance of a GCN-based node classification task. Existing works in this direction defend GCNs either by adversarial training or by identifying the attacker nodes followed by their removal. However, both of these approaches require that the attack patterns or attacker nodes be identified first, which is difficult in the scenario when the number of perturbator nodes is very small. In this work, we develop a GCN defense model, namely GraphLT, which uses the concept of label transition. GraphLT assumes that perturbators' random activities deteriorate GCN's performance. To overcome this issue, GraphLT subsequently uses a novel Bayesian label transition model, which takes GCN's predicted labels and applies label transitions by Gibbs-sampling-based inference and thus repairs GCN's prediction to achieve better node classification. Extensive experiments on seven benchmark datasets show that GraphLT considerably enhances the performance of the node classifier in an unperturbed environment; furthermore, it validates that GraphLT can successfully repair a GCN-based node classifier with superior performance than several competing methods.
BibTeX
@misc{zhuang2020anti,
  author = {Jun Zhuang and Mohammad Al Hasan},
  title = {{Anti-perturbation of Online Social Networks by Graph Label Transition}},
  year = {2020},
  eprint = {2010.14121},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2010.14121},
}
Figure