Mask-GVAE: Blind Denoising Graphs via Partition

Jia Li, Mengzhou Liu, Honglei Zhang, Pengyun Wang, Yong Wen, Lujia Pan, Hong Cheng

Abstract

Graph-structured data in real-world applications, such as social networks and biological maps, is frequently corrupted by noise in the form of missing or irrelevant edges. Blind denoising—recovering the true graph structure without access to clean training examples—remains a significant challenge due to the discrete nature of graphs and the computational complexity of spectral methods. We present Mask-GVAE, a variational generative framework that addresses these issues. Mask-GVAE utilizes the stability of graph Laplacian eigenvectors to partition the graph into clusters, which serves as a structural prior. A variational autoencoder then performs probabilistic smoothing within and between these clusters. Our evaluation shows that Mask-GVAE achieves superior denoising performance and scales effectively to large graphs, reducing processing time from hours to minutes.

Introduction

In the real world, data rarely arrives in a pristine state. Social networks contain accidental connections, and protein-protein interaction maps are riddled with experimental noise. While powerful tools exist for denoising continuous signals like images and audio, denoising graphs is significantly harder because they are large, discrete structures. Furthermore, we rarely have a "clean" version of a graph to use as a training target, necessitating "blind" denoising methods.

Presented at WWW '21, Mask-GVAE offers a novel solution: a variational generative model that recovers the true structure of a graph without ever seeing a clean example. By leveraging the mathematical stability of graph Laplacian eigenvectors, it partitions a noisy graph into clusters and uses a variational autoencoder (VAE) to probabilistically "smooth" the connections.

The Challenge of Graph Denoising

Most graph learning models assume the input graph structure is perfect. However, real-world graphs are often "degraded" by missing edges (unobserved relationships) or irrelevant edges (noise). Existing denoising methods face three major hurdles:

  1. Supervision Gap: Most deep learning models require pairs of "noisy" and "clean" data, which are rarely available for graphs.
  2. Discrete Complexity: Unlike continuous pixels in images, graph edges are discrete, making gradient-based optimization difficult.
  3. Scalability: Traditional spectral methods based on eigen-decomposition are computationally expensive and fail to scale to graphs with millions of nodes.

Methodology

Mask-GVAE operates in two main stages to overcome these hurdles:

1. The Cluster Mask (Finding the Skeleton)

The model first estimates stable clusters in an unsupervised way using a Graph Neural Network (GNN). It optimizes a "normalized cut" loss function, effectively partitioning the graph into regions that are likely to belong together despite the noise. This partitioning acts as a "Mask" that guides the subsequent generative process.

2. Denoised Graph Generation (The VAE)

Once clusters are identified, the model treats graph generation as a variational inference problem. An encoder GNN maps nodes into a latent space ($Z$), while a decoder focuses on generating "smoothed" subgraphs conditioned on the cluster mask. Instead of predicting every possible edge, the decoder learns which intra-cluster edges are likely missing and which inter-cluster edges are likely noise. Final discrete choices are made using a "budget" ($\Delta$) to add the most probable missing edges and delete the most likely noisy ones.

Key Insights: Spectral Stability

A core theoretical contribution of the paper is the proof that low-frequency components of a graph's Laplacian matrix—which represent broad community structure—are remarkably stable even when random noise is added. This stability justifies using clusters as a robust prior for denoising.

Spectral stability of graph Laplacian eigenvectors under noise.

By decomposing the large graph into subgraphs based on these clusters, Mask-GVAE avoids the $O(N^2)$ complexity of checking every possible node pair, making it significantly faster than previous spectral denoising methods.

Experimental Results

The researchers evaluated Mask-GVAE across social networks (IMDB, Reddit) and bioinformatics benchmarks (MUTAG, PTC-MR). Key findings include:

  • Superior Accuracy: Mask-GVAE outperformed competitors like DOMINANT and E-Net. On the Reddit-Binary dataset, it achieved a Peak Signal-to-Noise Ratio (PSNR) of 98.41, significantly higher than E-Net's 87.48.
  • Topological Fidelity: Using the Weisfeiler-Lehman (WL) kernel to measure structural similarity, the model consistently produced graphs more similar to the hidden ground truth than other methods.
  • Scalability: On large datasets, traditional methods often require over 24 hours of computation. Mask-GVAE completed the Reddit-Binary task in approximately 17 minutes.
  • Real-world Application: In a co-authorship network case study, the model successfully identified and removed a "noisy" edge caused by name ambiguity in Google Scholar (distinguishing between two different authors named "Wei Wang").

Conclusion

Mask-GVAE represents a significant step forward in unsupervised graph processing. By combining spectral theory with generative modeling, it provides a scalable and accurate way to clean messy graph data. Future work may address corrupted node attributes and the extension of this framework to dynamic, evolving graphs.

Summary updated

Abstract

We present Mask-GVAE, a variational generative model for blind denoising large discrete graphs, in which "blind denoising" means we don't require any supervision from clean graphs. We focus on recovering graph structures via deleting irrelevant edges and adding missing edges, which has many applications in real-world scenarios, for example, enhancing the quality of connections in a co-authorship network. Mask-GVAE makes use of the robustness in low eigenvectors of graph Laplacian against random noise and decomposes the input graph into several stable clusters. It then harnesses the huge computations by decoding probabilistic smoothed subgraphs in a variational manner. On a wide variety of benchmarks, Mask-GVAE outperforms competing approaches by a significant margin on PSNR and WL similarity.
BibTeX
@inproceedings{li2021mask,
  author = {Jia Li and Mengzhou Liu and Honglei Zhang and Pengyun Wang and Yong Wen and Lujia Pan and Hong Cheng},
  title = {{Mask-GVAE: Blind Denoising Graphs via Partition}},
  booktitle = {The Web Conference},
  year = {2021},
  doi = {10.1145/3442381.3449899},
}
Figure