Learning to Drop: Robust Graph Neural Network via Topological Denoising

Dongsheng Luo; Wei Cheng; Wenchao Yu; Bo Zong; Jingchao Ni; Haifeng Chen; Xiang Zhang

Source-linked AI summary

Learning to Drop: Robust Graph Neural Network via Topological Denoising

Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong, Jingchao Ni, Haifeng Chen, Xiang Zhang

arXiv:2011.07057v1Nov 13, 2020cs.LGcs.AI

TL;DR

GNNs are vulnerable to noisy, task-irrelevant edges because message passing aggregates information across the input graph. PTDNet learns to sparsify graphs with parameterized denoising networks and a nuclear-norm low-rank constraint, and experiments report improved performance and robustness on synthetic and benchmark datasets. The low-rank optimization can be computationally unstable or inaccurate when based on SVD or approximate power iteration.

Problem
Noisy, task-irrelevant edges can cause over-smoothing and over-fitting, weakening GNN robustness and generalization.
Method
PTDNet learns to drop task-irrelevant edges with parameterized networks, jointly optimizes denoising and GNN components, and imposes a nuclear-norm low-rank constraint.
Results
Experiments on synthetic and benchmark datasets demonstrate improved GNN performance and robustness, with effectiveness across various GNN models and tasks.
Takeaways & Limitations
PTDNet provides a supervised topological-denoising component compatible with GCN, GraphSage, GAT, and other GNN models.
Takeaways & Limitations
Nuclear-norm optimization can be unstable during backpropagation, while power iteration may be inaccurate when eigenvalues are close and adds computation.

Abstract

from arXiv · show

Graph Neural Networks (GNNs) have shown to be powerful tools for graph analytics. The key idea is to recursively propagate and aggregate information along edges of the given graph. Despite their success, however, the existing GNNs are usually sensitive to the quality of the input graph. Real-world graphs are often noisy and contain task-irrelevant edges, which may lead to suboptimal generalization performance in the learned GNN models. In this paper, we propose PTDNet, a parameterized topological denoising network, to improve the robustness and generalization performance of GNNs by learning to drop task-irrelevant edges. PTDNet prunes task-irrelevant edges by penalizing the number of edges in the sparsified graph with parameterized networks. To take into consideration of the topology of the entire graph, the nuclear norm regularization is applied to impose the low-rank constraint on the resulting sparsified graph for better generalization. PTDNet can be used as a key component in GNN models to improve their performances on various tasks, such as node classification and link prediction. Experimental studies on both synthetic and benchmark datasets show that PTDNet can improve the performance of GNNs significantly and the performance gain becomes larger for more noisy datasets.

1 INTRODUCTION

GNNs can over-aggregate task-irrelevant information from noisy graph edges, harming robustness and generalization. PTDNet learns to remove such edges while using sparsity and low-rank regularization to improve GNN performance.

GNNs recursively propagate and aggregate node-feature messages along input-graph edges for tasks including node classification and link prediction.
Noisy, task-irrelevant edges can cause over-smoothing and over-fitting, making GNN performance sensitive to input-graph quality.
On Cora, GCN performance increases as more negative edges are removed, supporting topological denoising as a way to improve message quality.
PTDNet uses parameterized networks with structural and content information to learn which task-irrelevant edges to drop, then feeds denoised graphs into GNNs.
PTDNet penalizes the number of edges in sparsified graphs and applies nuclear norm regularization to impose a low-rank constraint from the global topology perspective.
Experiments on synthetic and benchmark datasets show that PTDNet enhances GNN performance and robustness, especially by removing edges connecting multiple communities.

2 RELATED WORK

Prior graph sparsification and sampling methods often rely only on structure or random edge removal. PTDNet instead uses downstream supervision to actively filter task-specific noisy edges.

Graph sparsification methods approximate large graphs with sparse subgraphs while preserving properties such as distances, cuts, degree distributions, or spectral characteristics.
Structural-only sparsification can be limited for GNNs because it lacks supervised feedback from downstream tasks.
GNN graph-sampling methods include neighbor-level, node-level, and edge-level approaches for computational efficiency and generalization.
Unlike random edge sampling, PTDNet uses parameterized networks and downstream supervision to actively remove task-specific noisy edges.
The generated subgraphs are reported to benefit robustness, accuracy, interpretability, and inductive inference.

3 NOTATIONS AND PRELIMINARIES

The paper defines graph, adjacency, feature, and label notation before describing GNN message passing and PTDNet’s denoising architecture. PTDNet addresses noisy-edge aggregation through a differentiable, parameterized subgraph-selection process.

Notations: The input graph is G=(V, E), with adjacency matrix A ∈ R^n×n, node-feature matrix X ∈ R^n×m, and downstream labels Y.
GNN layer: A GNN layer propagates edge messages from neighboring node representations and then updates each node’s hidden representation.
Motivation: Noisy-edge aggregation can reduce embedding quality and cause over-smoothing, while existing sparsification and random-sampling methods are generally unsupervised.
PTDNet: PTDNet actively filters task-specific noisy edges with a parameterized denoising network alongside a general GNN under inductive or transductive settings.

4 THE PTDNET

PTDNet combines learned edge denoising with GNN layers, using parameterized networks to filter task-irrelevant edges and regularization to control sparsity and global topology.

4.1 The overall architecture: PTDNet consists of denoising networks and GNNs, and can be jointly optimized using supervised downstream signals.The denoising network samples subgraphs from learned edge distributions and is compatible with GCN, GraphSage, GAT, and GIN.
4.2.1 Graph edge sparsification.: Each GNN layer receives a subgraph generated by a denoising network, filtering task-irrelevant edges before message passing.The binary matrix Z_l indicates which edges remain, with zero representing a noisy edge.
4.2.1 Graph edge sparsification.: PTDNet forms each sparsified adjacency matrix as A_l = A ⊙ Z_l and penalizes nonzero entries in Z_l to reduce noisy edges.Because direct ℓ0 optimization is nondifferentiable and combinatorial, edge indicators are modeled through Bernoulli distributions parameterized by Π_l.
4.2.2 Continuous relaxation with parameterized networks.: Parameterized networks estimate edge-removal controls from node contents and topology, enabling denoising during both training and testing.The learned edge-quality parameters are optimized jointly with the downstream GNN and support inductive use on input graphs.
4.3 The low-rank constraint: The low-rank regularizer encourages sparsified graphs with dense within-community connections and sparse connections between communities.PTDNet relaxes rank minimization with the nuclear norm, the sum of singular values, while SVD and power iteration address its optimization.

5 EXPERIMENTAL STUDY

The study evaluates PTDNet with synthetic and benchmark datasets across node classification, robustness to injected noise, denoising behavior, regularizers, and link prediction.

Experimental design: The experiments assess benchmark performance, robustness under injected noise, removed edges, regularizer effects, parameter sensitivity, over-smoothing, and link prediction.The evaluation includes both effectiveness and robustness analyses.
Experimental setup: Experiments use synthetic data and four benchmark datasets, including citation graphs and protein-protein interaction graphs.The benchmark datasets are Cora, Citeseer, Pubmed, and PPI.
Experimental setup: PTDNet is evaluated with GCN, GraphSage, and GAT backbones and compared with DropEdge and NeuralSparse.The framework is designed to be compatible with diverse GNN models.
Experimental setup: Each experimental setting is run 10 times with average results, using random hyper-parameter search and cross-validation for tuning.An ablation variant removes the low-rank constraint.

5.2 Effectiveness evaluation

PTDNet improves GNN effectiveness and robustness by learning to remove task-irrelevant edges, with larger gains as noise increases and evidence of selective denoising.

Effectiveness evaluation: PTDNet achieves state-of-the-art or matched node-classification performance across benchmark datasets.The denoising component improves basic GNN performance and generalization capacity.
Robustness evaluation: 37.37% relative accuracy improvement for GCN, 13.4% for GraphSage, and 16.1% for GAT occur with 20,000 noisy edges in Cora.PTDNet consistently outperforms DropEdge, NeuralSparse, and basic backbones across noise levels.
On denoising process: PTDNet detects negative edges and removes them or assigns them lower weights, whereas DropEdge cannot actively target task-irrelevant edges.Negative edges connect nodes with different labels in the synthetic analysis.
On denoising process: PTDNet’s denoising process produces higher accuracy over more iterations and maintains consistent performance on testing nodes.The testing-phase behavior supports use of the learned denoising networks beyond training.
On denoising process: PTDNet and DropEdge preserve the input graph’s degree distribution property while producing different positive- and negative-edge selections.The comparison examines distributions for the input graph and sampled subgraphs.

5.5 Effects of regularizers

Regularizer settings affect PTDNet’s accuracy and denoising behavior: stronger regularization helps poorer topologies, while the low-rank term removes more cross-community edges.

Regularizer effects: Regularizer-weighted accuracy generally first increases and then decreases as coefficient values grow.The coefficients are evaluated through accuracy experiments using GCN as the backbone.
Regularizer effects: Datasets with poorer topological quality require higher regularizer weights so PTDNet can denoise more task-irrelevant edges.The synthetic datasets contain positive-edge percentages ranging from 0.5 to 0.85.
Low-rank constraint: The low-rank constraint is designed to enhance generalization by constraining edges connecting nodes from different communities.It is implemented as a smoothed nuclear-norm relaxation of rank minimization.
Low-rank constraint: The cross-community edge ratio falls from 0.211 in the original graph to 0.189 with the low-rank constraint, versus 0.206 without it.The comparison uses β1 = 0.05, β2 = 0 and β1 = 0, β2 = 0.05 settings, respectively.

5.6 Impacts of approximate factor 𝐾

The approximate factor K trades accuracy against running time: larger values improve accuracy but increase computation, while small values can still perform relatively well.

Impact of approximate factor K: Larger K increases accuracy and running time, consistent with its tighter bound in the low-rank constraint.The study varies K from 1 to 32 with a two-layer GCN.
Impact of approximate factor K: PTDNet achieves relatively high performance even when K is small.This indicates that the method does not require the largest tested approximation factor for strong performance.

5.7 On over-smoothing

PTDNet addresses over-smoothing in deep GNNs by learning parameterized edge-dropping strategies usable during both training and testing. On dense synthetic graphs, it consistently outperforms GCN, MLP, and DropEdge baselines as depth increases.

Baseline comparison: DropEdge alleviates over-smoothing only partially because its random edge dropping is unavailable during testing.PTDNet instead learns parameterized edge-dropping strategies that can be applied in both training and testing phases.
Experimental setup: The study evaluates over-smoothing on synthetic datasets made denser by adding more edges.Results are presented in Figure 8 while varying the number of GCN layers from 2 to 16.
Results: PTDNet consistently outperforms all baselines across the evaluated GNN depths.The comparison uses GCN as the backbone, DropEdge with rates 0.1, 0.8, and 0.99, and MLP as an additional baseline.

5.8 Link prediction

PTDNet is evaluated for link prediction on Cora, Citeseer, and Pubmed using GAE-style settings with GCN. The reported results show that PTDNet improves link-prediction accuracy by removing task-irrelevant edges under downstream-task supervision.

Results: PTDNet improves link-prediction accuracy on Cora, Citeseer, and Pubmed.The evaluation randomly removes 10% of positive test edges and 5% of positive validation edges.
Method: The PTDNet denoising networks are optimized by downstream task loss to remove task-irrelevant edges.The remaining edges and all node features are used for training.

6 CONCLUSION

The paper concludes that PTDNet filters task-specific noisy edges to improve GNN robustness and generalization. Its compatibility with multiple GNN architectures and effectiveness across synthetic and benchmark datasets support its broad application across tasks.

Contribution: PTDNet limits input-graph edges with parameterized networks to filter task-specific noisy edges.The stated goals are improving GNN robustness and generalization power.
Contribution: Nuclear norm regularization imposes a low-rank constraint on sparsified graphs to further improve generalization capacity.PTDNet uses this regularization to account for the topology of the resulting graph.
Scope and evidence: PTDNet is compatible with GCN, GraphSage, and GAT and improves performance on various tasks.The conclusion reports effectiveness on both synthetic and benchmark datasets.