Robust Node Representation Learning via Graph Variational Diffusion Networks

Jun Zhuang, Mohammad Al HasanarXiv 2023 · OpenReview

TL;DR

This paper introduces the Graph Variational Diffusion Network (GVDN), a novel approach to make Graph Neural Networks (GNNs) more robust against adversarial perturbations in graph data. GVDN uses a combination of Gaussian diffusion and node embedding propagation to learn resilient node representations, and a retraining mechanism to recover performance on noisy graphs.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) are powerful tools for learning from graph-structured data, like social networks or citation networks. However, their performance can be significantly degraded by even small, carefully crafted changes to the graph structure (perturbations). This is a major concern for real-world applications where data can be noisy or intentionally manipulated. Existing methods to improve GNN robustness often struggle with issues like requiring well-defined prior distributions or suffering from "over-smoothing," where node representations become too similar, hindering their distinctiveness. This paper aims to develop a GNN that is robust to these perturbations without succumbing to over-smoothing.

Methods

The core of the proposed solution is the Graph Variational Diffusion Network (GVDN), a new node encoder designed to learn robust node embeddings. GVDN incorporates two key mechanisms:

  • Gaussian Diffusion: Inspired by variational diffusion models used in image generation, this technique applies Gaussian noise to the mean and log standard deviation of node embeddings. Crucially, the magnitude of this noise is gradually decreased during training. This allows the model to leverage noise for robustness early on, while reducing its impact as the model becomes more confident, thus mitigating over-smoothing.
  • Node Embedding Propagation: This mechanism leverages the principle of homophily (nodes with similar labels tend to connect to each other). It propagates node embeddings from neighbors that have been identified as inaccurately predicted. This helps to reinforce the representations of potentially misclassified nodes.

Additionally, the paper introduces a retraining mechanism. After an initial training phase, the model generates pseudo-labels on perturbed graphs using the learned embeddings. It then retrains the GNN classifier using these pseudo-labels to further recover performance on the noisy data.

Datasets

The proposed GVDN model was evaluated on six public node-labeled graph datasets:

  • Cora
  • Citeseer
  • Pubmed
  • AMZcobuy
  • Coauthor
  • Flickr

These datasets represent various types of graph data, including citation networks, co-purchase networks, and co-authorship graphs. The authors used standard splits for training, validation, and testing.

Key Insights and Ideas

  • Noise is a double-edged sword: While injecting Gaussian noise can improve robustness, simply increasing its proportion leads to over-smoothing and degraded performance. The key is to dynamically regulate the noise.
  • Diffusion as a training aid: Gradually reducing Gaussian noise during training (Gaussian diffusion) is an effective way to balance robustness gains with the avoidance of over-smoothing.
  • Propagation for correction: Propagating embeddings from neighbors of misclassified nodes can help correct and strengthen their representations, especially in the presence of noise.
  • Retraining for recovery: A simple retraining step using pseudo-labels generated by the robust embeddings can significantly recover classification performance on perturbed graphs.
  • Efficiency matters: The proposed retraining mechanism is significantly faster than existing MCMC-based post-processing methods, making it more suitable for streaming applications.

Key Results

  • GVDN demonstrates strong performance in recovering node classification accuracy on perturbed graphs across six public datasets.
  • The paper shows that simply increasing Gaussian noise in GNNs deteriorates performance, highlighting the need for more sophisticated noise management.
  • The ablation studies confirm the effectiveness of both Gaussian diffusion and node embedding propagation mechanisms.
  • The retraining mechanism significantly improves accuracy on perturbed graphs, outperforming competing methods.
  • GVDN achieves a much lower inference runtime compared to MCMC-based methods like GraphSS and LInDT, making it more practical for real-time applications. For instance, on the Flickr dataset, GVDN's inference time is 21.35 seconds, while LInDT takes 318.33 seconds.

Limitations and Future Work

  • Sparsity challenges: The paper acknowledges that GVDN may struggle on extremely sparse graphs due to limited information for aggregation and propagation.
  • Heterogeneous graphs: The node embedding propagation mechanism relies on the homophily assumption, which might not hold for heterogeneous graphs.

Future work suggested includes exploring inverse diffusion processes to complete graph structures and adapting the methods for heterogeneous graph scenarios.

Summary updated

Abstract

Node representation learning by using Graph Neural Networks (GNNs) has been widely explored. However, in recent years, compelling evidence has revealed that GNN-based node representation learning can be substantially deteriorated by delicately-crafted perturbations in a graph structure. To learn robust node representation in the presence of perturbations, various works have been proposed to safeguard GNNs. Within these existing works, Bayesian label transition has been proven to be more effective, but this method is extensively reliant on a well-built prior distribution. The variational inference could address this limitation by sampling the latent node embedding from a Gaussian prior distribution. Besides, leveraging the Gaussian distribution (noise) in hidden layers is an appealing strategy to strengthen the robustness of GNNs. However, our experiments indicate that such a strategy can cause over-smoothing issues during node aggregation. In this work, we propose the Graph Variational Diffusion Network (GVDN), a new node encoder that effectively manipulates Gaussian noise to safeguard robustness on perturbed graphs while alleviating over-smoothing issues through two mechanisms: Gaussian diffusion and node embedding propagation. Thanks to these two mechanisms, our model can generate robust node embeddings for recovery. Specifically, we design a retraining mechanism using the generated node embedding to recover the performance of node classifications in the presence of perturbations. The experiments verify the effectiveness of our proposed model across six public datasets.
BibTeX
@misc{zhuang2023robust,
  author = {Jun Zhuang and Mohammad Al Hasan},
  title = {{Robust Node Representation Learning via Graph Variational Diffusion Networks}},
  year = {2023},
  eprint = {2312.10903},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2312.10903},
}
Figure