# RW-NSGCN: A Robust Approach to Structural Attacks via Negative Sampling

arXiv: https://arxiv.org/abs/2408.06665 · HTML: https://mlsanity.com/paper/2408.06665/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 37 of its 69 references that are in the map.
- First posted on arXiv 13 Aug 2024.

## Builds on (most cited first, 30 of 37)

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Towards Deeper Graph Neural Networks with Differentiable Group Normalization](https://mlsanity.com/paper/2006.06972/) (2020)
- [How to Find Your Friendly Neighborhood: Graph Attention Design with Self-Supervision](https://mlsanity.com/paper/2204.04879/) (2022)
- [Understanding Negative Sampling in Graph Representation Learning](https://mlsanity.com/paper/2005.09863/) (2020)
- [Attention-Enhancing Backdoor Attacks Against BERT-based Models](https://mlsanity.com/paper/2310.14480/) (2023)
- [A Fast Transformer-based General-Purpose Lossless Compressor](https://mlsanity.com/paper/2203.16114/) (2022)
- [Credit Card Fraud Detection Using Advanced Transformer Model](https://mlsanity.com/paper/2406.03733/) (2024)
- [RAW-GNN: RAndom Walk Aggregation based Graph Neural Network](https://mlsanity.com/paper/2206.13953/) (2022)
- [CATS: Enhancing Multivariate Time Series Forecasting by Constructing Auxiliary Time Series as Exogenous Variables](https://mlsanity.com/paper/2403.01673/) (2024)
- [Adversarial Weight Perturbation Improves Generalization in Graph Neural Networks](https://mlsanity.com/paper/2212.04983/) (2022)
- [Defending Graph Convolutional Networks against Dynamic Graph Perturbations via Bayesian Self-supervision](https://mlsanity.com/paper/2203.03762/) (2022)
- [CAP: Co-Adversarial Perturbation on Weights and Features for Improving Generalization of Graph Neural Networks](https://mlsanity.com/paper/2110.14855/) (2021)
- [GNNRank: Learning Global Rankings from Pairwise Comparisons via Directed Graph Neural Networks](https://mlsanity.com/paper/2202.00211/) (2022)
- [Enhancing Healthcare through Large Language Models: A Study on Medical Question Answering](https://mlsanity.com/paper/2408.04138/) (2024)
- [Robust Node Classification on Graphs: Jointly from Bayesian Label Transition and Topology-based Label Propagation](https://mlsanity.com/paper/2208.09779/) (2022)
- [An Explainer for Temporal Graph Neural Networks](https://mlsanity.com/paper/2209.00807/) (2022)
- [Scalable Graph Neural Network-based framework for identifying critical nodes and links in Complex Networks](https://mlsanity.com/paper/2012.15725/) (2020)
- [Boosting-GNN: Boosting Algorithm for Graph Networks on Imbalanced Node Classification](https://mlsanity.com/paper/2105.11625/) (2021)
- [Learning from the Dark: Boosting Graph Convolutional Neural Networks with Diverse Negative Samples](https://mlsanity.com/paper/2210.00728/) (2022)
- [Manifold-constrained Gaussian process inference for time-varying parameters in dynamic systems](https://mlsanity.com/paper/2105.13407/) (2021)
- [Structack: Structure-based Adversarial Attacks on Graph Neural Networks](https://mlsanity.com/paper/2107.11327/) (2021)
- [Addressing Over-Smoothing in Graph Neural Networks via Deep Supervision](https://mlsanity.com/paper/2202.12508/) (2022)
- [Graph Convolutional Neural Networks with Diverse Negative Samples via Decomposed Determinant Point Processes](https://mlsanity.com/paper/2212.02055/) (2022)
- [Deperturbation of Online Social Networks via Bayesian Label Transition](https://mlsanity.com/paper/2010.14121/) (2020)

## Abstract (arXiv)

Node classification using Graph Neural Networks (GNNs) has been widely applied in various practical scenarios, such as predicting user interests and detecting communities in social networks. However, recent studies have shown that graph-structured networks often contain potential noise and attacks, in the form of topological perturbations and weight disturbances, which can lead to decreased classification performance in GNNs. To improve the robustness of the model, we propose a novel method: Random Walk Negative Sampling Graph Convolutional Network (RW-NSGCN). Specifically, RW-NSGCN integrates the Random Walk with Restart (RWR) and PageRank (PGR) algorithms for negative sampling and employs a Determinantal Point Process (DPP)-based GCN for convolution operations. RWR leverages both global and local information to manage noise and local variations, while PGR assesses node importance to stabilize the topological structure. The DPP-based GCN ensures diversity among negative samples and aggregates their features to produce robust node embeddings, thereby improving classification performance. Experimental results demonstrate that the RW-NSGCN model effectively addresses network topology attacks and weight instability, increasing the accuracy of anomaly detection and overall stability. In terms of classification accuracy, RW-NSGCN significantly outperforms existing methods, showing greater resilience across various scenarios and effectively mitigating the impact of such vulnerabilities.