Toward Robust Signed Graph Learning through Joint Input-Target Denoising

Junran Wu, Beng Chin Ooi, Ke Xu

Introduction

Signed graphs—networks characterized by both positive (e.g., trust, friendship) and negative (e.g., distrust, enmity) links—are vital for modeling complex social and economic interactions. However, real-world signed graphs are inherently noisy due to data collection errors or malicious manipulation, such as incentivized reviews.

Existing Robust Signed Graph Neural Networks (SGNNs) often rely on Balance Theory, a social psychological framework assuming "the friend of my friend is my friend" and "the enemy of my enemy is my friend." This paper argues that such assumptions are overly idealistic, as real-world networks are frequently unbalanced. Furthermore, most current methods focus solely on denoising graph structure, neglecting the fact that training labels (targets) are often just as corrupted as the inputs.

The RIDGE Framework

To address these challenges, the authors introduce RIDGE (Robust sIgned graph learning through joint Denoising of Graph inputs and supervision targEts). RIDGE is a backbone-agnostic framework designed to enhance the resilience of existing SGNN architectures like SGCN or SNEA.

The RIDGE framework architecture, illustrating the joint denoising of features, graph topology, and supervision targets via GIB-TD.

The framework is built on three primary pillars:

  1. GIB-TD (Graph Information Bottleneck with Target Denoising): An extension of standard Graph Information Bottleneck theory that adds a mathematical objective to simultaneously cleanse target labels while compressing input data to remove task-irrelevant noise.
  2. Joint Denoising Mechanism: This includes Feature Masking to drop irrelevant or corrupted node features and Substructure Sampling to identify a clean subset of the graph topology and labels.
  3. Tractable Optimization: By utilizing the reparameterization trick and variational approximation, the authors transform complex mutual information calculations into a training objective optimizable via standard gradient descent.

Key Insights: Moving Beyond Balance Theory

A core contribution of this work is identifying the "Balance Theory Trap." Traditional models that force a graph to adhere to social balance can inadvertently distort the true data distribution, especially in naturally unbalanced real-world networks. RIDGE avoids this by prioritizing information flow over rigid social heuristics.

Comparison of graph structures where Case 1 follows balance theory and Case 2 represents a more complex, unbalanced real-world scenario.

By treating labels as potentially noisy rather than absolute ground truth, RIDGE achieves superior robustness. The joint denoising of inputs and targets serves as the "secret sauce" for maintaining performance in messy environments.

Experimental Results

RIDGE was evaluated on several benchmarks, including Bitcoin_OTC, Bitcoin_Alpha, Epinions, and Slashdot, as well as large-scale datasets like MovieLens-1M and Amazon-Book.

  • Superior Robustness: RIDGE consistently outperformed state-of-the-art robust models (e.g., RSGNN, LRWSB), achieving up to a 5.45% gain in Binary-F1 score.
  • Resilience to Noise: As random sign-flipping noise increased from 10% to 25%, the performance gap between RIDGE and its competitors widened.
  • Scalability: RIDGE scales linearly with the number of edges. On the MovieLens-1M dataset, it completed training efficiently, whereas competitors like LRWSB required over 54 hours for preprocessing.
  • Adversarial Defense: The model demonstrated strong resistance to "Balance Attacks"—adversarial perturbations specifically designed to exploit the weaknesses of signed graph models.

Conclusion and Future Work

While RIDGE shows a slight performance trade-off in perfectly noise-free conditions—a common occurrence in robust machine learning—its advantages in real-world, noisy scenarios are significant. Future research may explore combining RIDGE with other noise-tolerant techniques, such as contrastive learning, or developing even more lightweight denoising heuristics to further optimize large-scale graph representation.

Summary updated

BibTeX
@inproceedings{wu2025toward,
  author = {Junran Wu and Beng Chin Ooi and Ke Xu},
  title = {{Toward Robust Signed Graph Learning through Joint Input-Target Denoising}},
  booktitle = {ACM Multimedia},
  year = {2025},
  doi = {10.1145/3746027.3755645},
}
Figure