Adaptive graph-based algorithms for conditional anomaly detection and semi-supervised learning

• URL: http://arxiv.org/abs/2605.03495v1
• Date: Tue, 05 May 2026 08:33:34 GMT
• Title: Adaptive graph-based algorithms for conditional anomaly detection and semi-supervised learning
• Abstract summary: We propose a fast approximate online algorithm that solves for the harmonic solution on an approximate graph.<n>We also present graph-based methods for detecting conditional anomalies and apply them to the identification of unusual clinical actions in hospitals.
• Score: 19.66115828957497
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop graph-based methods for semi-supervised learning based on label propagation on a data similarity graph. When data is abundant or arrive in a stream, the problems of computation and data storage arise for any graph-based method. We propose a fast approximate online algorithm that solves for the harmonic solution on an approximate graph. We show, both empirically and theoretically, that good behavior can be achieved by collapsing nearby points into a set of local representative points that minimize distortion. Moreover, we regularize the harmonic solution to achieve better stability properties. We also present graph-based methods for detecting conditional anomalies and apply them to the identification of unusual clinical actions in hospitals. Our hypothesis is that patient-management actions that are unusual with respect to the past patients may be due to errors and that it is worthwhile to raise an alert if such a condition is encountered. Conditional anomaly detection extends standard unconditional anomaly framework but also faces new problems known as fringe and isolated points. We devise novel nonparametric graph-based methods to tackle these problems. Our methods rely on graph connectivity analysis and soft harmonic solution. Finally, we conduct an extensive human evaluation study of our conditional anomaly methods by 15 experts in critical care.

Related papers

• Learning Feature Encoder with Synthetic Anomalies for Weakly Supervised Graph Anomaly Detection [66.0756595768692]
  We introduce a weakly supervised graph anomaly detection method that leverages a feature learning strategy tailored for graph anomalies.<n>Our approach is built upon a multi-task learning scheme that extracts robust feature representations through synthesized anomalies.<n>Experiments on public datasets demonstrate the superior performance of our method over its competitors.
  arXiv  Detail & Related papers  (2026-05-12T08:27:06Z)
• Conditional anomaly detection using soft harmonic functions: An application to clinical alerting [30.23389433948732]
  We develop a new non-parametric approach for conditional anomaly detection based on the soft harmonic solution.<n>We demonstrate the efficacy of the proposed method in detecting unusual labels on a real-world electronic health record dataset.
  arXiv  Detail & Related papers  (2026-04-23T09:18:20Z)
• Conditional anomaly detection with soft harmonic functions [30.23389433948732]
  We develop a new non-parametric approach for conditional anomaly detection based on the soft harmonic solution.<n>We demonstrate the efficacy of the proposed method on several synthetic and UCI ML datasets.<n>We also evaluate the performance of our method on a real-world electronic health record dataset.
  arXiv  Detail & Related papers  (2026-04-23T09:17:03Z)
• Robust Graph-Based Semi-Supervised Learning via $p$-Conductances [49.0776396776252]
  We study the problem of semi-supervised learning on graphs in the regime where data labels are scarce or possibly corrupted.<n>We propose an approach called $p$-conductance learning that generalizes the $p$-Laplace and Poisson learning methods.<n> Empirical results on computer vision and citation datasets demonstrate that our approach achieves state-of-the-art accuracy in low label-rate, corrupted-label, and partial-label regimes.
  arXiv  Detail & Related papers  (2025-02-13T01:11:25Z)
• Adaptive Online Experimental Design for Causal Discovery [9.447864414136905]
  Causal discovery aims to uncover cause-and-effect relationships encoded in causal graphs. We focus on data interventional efficiency and formalize causal discovery from the perspective of online learning. We propose a track-and-stop causal discovery algorithm that adaptively selects interventions from the graph separating system.
  arXiv  Detail & Related papers  (2024-05-19T13:26:33Z)
• ADA-GAD: Anomaly-Denoised Autoencoders for Graph Anomaly Detection [84.0718034981805]
  We introduce a novel framework called Anomaly-Denoised Autoencoders for Graph Anomaly Detection (ADA-GAD) In the first stage, we design a learning-free anomaly-denoised augmentation method to generate graphs with reduced anomaly levels. In the next stage, the decoders are retrained for detection on the original graph.
  arXiv  Detail & Related papers  (2023-12-22T09:02:01Z)
• 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)
• Towards Self-Interpretable Graph-Level Anomaly Detection [73.1152604947837]
  Graph-level anomaly detection (GLAD) aims to identify graphs that exhibit notable dissimilarity compared to the majority in a collection. We propose a Self-Interpretable Graph aNomaly dETection model ( SIGNET) that detects anomalous graphs as well as generates informative explanations simultaneously.
  arXiv  Detail & Related papers  (2023-10-25T10:10:07Z)
• From Unsupervised to Few-shot Graph Anomaly Detection: A Multi-scale Contrastive Learning Approach [26.973056364587766]
  Anomaly detection from graph data is an important data mining task in many applications such as social networks, finance, and e-commerce. We propose a novel framework, graph ANomaly dEtection framework with Multi-scale cONtrastive lEarning (ANEMONE in short) By using a graph neural network as a backbone to encode the information from multiple graph scales (views), we learn better representation for nodes in a graph.
  arXiv  Detail & Related papers  (2022-02-11T09:45:11Z)
• Near-optimal inference in adaptive linear regression [60.08422051718195]
  Even simple methods like least squares can exhibit non-normal behavior when data is collected in an adaptive manner. We propose a family of online debiasing estimators to correct these distributional anomalies in at least squares estimation. We demonstrate the usefulness of our theory via applications to multi-armed bandit, autoregressive time series estimation, and active learning with exploration.
  arXiv  Detail & Related papers  (2021-07-05T21:05:11Z)
• Learning Graphs from Smooth Signals under Moment Uncertainty [23.868075779606425]
  We consider the problem of inferring the graph structure from a given set of graph signals. Traditional graph learning models do not take this distributional uncertainty into account.
  arXiv  Detail & Related papers  (2021-05-12T06:47:34Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)

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.