Mitigating the Impact of Noisy Edges on Graph-Based Algorithms via Adversarial Robustness Evaluation

• URL: http://arxiv.org/abs/2401.15615v2
• Date: Tue, 26 Nov 2024 14:55:03 GMT
• Title: Mitigating the Impact of Noisy Edges on Graph-Based Algorithms via Adversarial Robustness Evaluation
• Authors: Yongyu Wang, Xiaotian Zhuang,
• Abstract summary: We propose to use a spectral adversarial evaluation method to mitigate the impact of noisy edges on the performance of graph-based algorithms. Our method identifies the points that are less vulnerable to noisy edges and leverages only these robust points to perform graph-based algorithms.
• Score: 1.8569481432894677
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given that no existing graph construction method can generate a perfect graph for a given dataset, graph-based algorithms are often affected by redundant and erroneous edges present within the constructed graphs. In this paper, we view these noisy edges as adversarial attack and propose to use a spectral adversarial robustness evaluation method to mitigate the impact of noisy edges on the performance of graph-based algorithms. Our method identifies the points that are less vulnerable to noisy edges and leverages only these robust points to perform graph-based algorithms. Our experiments demonstrate that our methodology is highly effective and outperforms state-of-the-art denoising methods by a large margin.

Related papers

• Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification [81.06278257153835]
  We propose a graph rewiring method that balances structural bottleneck reduction and graph property preservation.<n>Our method generates graphs with enhanced connectivity while maintaining sparsity and largely preserving the original graph spectrum.
  arXiv  Detail & Related papers  (2025-06-19T08:01:00Z)
• Rethinking Contrastive Learning in Graph Anomaly Detection: A Clean-View Perspective [54.605073936695575]
  Graph anomaly detection aims to identify unusual patterns in graph-based data, with wide applications in fields such as web security and financial fraud detection.<n>Existing methods rely on contrastive learning, assuming that a lower similarity between a node and its local subgraph indicates abnormality.<n>The presence of interfering edges invalidates this assumption, since it introduces disruptive noise that compromises the contrastive learning process.<n>We propose a Clean-View Enhanced Graph Anomaly Detection framework (CVGAD), which includes a multi-scale anomaly awareness module to identify key sources of interference in the contrastive learning process.
  arXiv  Detail & Related papers  (2025-05-23T15:05:56Z)
• Oversmoothing as Loss of Sign: Towards Structural Balance in Graph Neural Networks [54.62268052283014]
  Oversmoothing is a common issue in graph neural networks (GNNs) Three major classes of anti-oversmoothing techniques can be mathematically interpreted as message passing over signed graphs. Negative edges can repel nodes to a certain extent, providing deeper insights into how these methods mitigate oversmoothing.
  arXiv  Detail & Related papers  (2025-02-17T03:25:36Z)
• Topograph: An efficient Graph-Based Framework for Strictly Topology Preserving Image Segmentation [78.54656076915565]
  Topological correctness plays a critical role in many image segmentation tasks. Most networks are trained using pixel-wise loss functions, such as Dice, neglecting topological accuracy. We propose a novel, graph-based framework for topologically accurate image segmentation.
  arXiv  Detail & Related papers  (2024-11-05T16:20:14Z)
• Integer Programming for Learning Directed Acyclic Graphs from Non-identifiable Gaussian Models [6.54203362045253]
  We study the problem of learning directed acyclic graphs from continuous observational data. We develop a mixed-integer programming framework for learning medium-sized problems. Our method outperforms state-of-the-art algorithms and is robust to noise heteroscedasticity.
  arXiv  Detail & Related papers  (2024-04-19T02:42:13Z)
• GRAM: An Interpretable Approach for Graph Anomaly Detection using Gradient Attention Maps [26.011499804523808]
  We propose a novel approach to graph anomaly detection that leverages the power of interpretability to enhance performance. Our method extracts an attention map derived from gradients of graph neural networks, which serves as a basis for scoring anomalies. We extensively evaluate our approach against state-of-the-art graph anomaly detection techniques on real-world graph classification and wireless network datasets.
  arXiv  Detail & Related papers  (2023-11-10T16:14:21Z)
• GraphCloak: Safeguarding Task-specific Knowledge within Graph-structured Data from Unauthorized Exploitation [61.80017550099027]
  Graph Neural Networks (GNNs) are increasingly prevalent in a variety of fields. Growing concerns have emerged regarding the unauthorized utilization of personal data. Recent studies have shown that imperceptible poisoning attacks are an effective method of protecting image data from such misuse. This paper introduces GraphCloak to safeguard against the unauthorized usage of graph data.
  arXiv  Detail & Related papers  (2023-10-11T00:50:55Z)
• Uncertainty-Aware Robust Learning on Noisy Graphs [16.66112191539017]
  This paper proposes a novel uncertainty-aware graph learning framework motivated by distributionally robust optimization. Specifically, we use a graph neural network-based encoder to embed the node features and find the optimal node embeddings. Such an uncertainty-aware learning process leads to improved node representations and a more robust graph predictive model.
  arXiv  Detail & Related papers  (2023-06-14T02:45:14Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Score matching enables causal discovery of nonlinear additive noise models [63.93669924730725]
  We show how to design a new generation of scalable causal discovery methods. We propose a new efficient method for approximating the score's Jacobian, enabling to recover the causal graph.
  arXiv  Detail & Related papers  (2022-03-08T21:34:46Z)
• Bayesian Graph Contrastive Learning [55.36652660268726]
  We propose a novel perspective of graph contrastive learning methods showing random augmentations leads to encoders. Our proposed method represents each node by a distribution in the latent space in contrast to existing techniques which embed each node to a deterministic vector. We show a considerable improvement in performance compared to existing state-of-the-art methods on several benchmark datasets.
  arXiv  Detail & Related papers  (2021-12-15T01:45:32Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.