pith. sign in

arxiv: 2605.03495 · v1 · submitted 2026-05-05 · 💻 cs.LG · stat.ML

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

Michal Valko This is my paper

Pith reviewed 2026-05-07 17:15 UTC · model grok-4.3

classification 💻 cs.LG stat.ML
keywords semi-supervised learninglabel propagationharmonic solutionconditional anomaly detectiononline algorithmsgraph-based methodsclinical decision support
0
0 comments X

The pith

Graph-based methods using approximate similarity graphs enable efficient semi-supervised learning and conditional anomaly detection for streaming data.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper develops graph-based methods for semi-supervised learning via label propagation on data similarity graphs. To handle large or streaming data, it proposes an approximate online algorithm that solves the harmonic solution by collapsing nearby points into a set of local representative points minimizing distortion, and regularizes the solution for stability. It extends this to conditional anomaly detection by analyzing graph connectivity and using soft harmonic solutions to identify unusual clinical actions that may indicate errors, addressing issues like fringe and isolated points. The approach is tested with an extensive human evaluation by critical care experts.

Core claim

The central claim is that good behavior for label propagation can be achieved with an approximate graph from local representatives minimizing distortion, combined with regularization of the harmonic solution for stability, and that graph connectivity analysis with soft harmonic solutions can detect conditional anomalies such as unusual patient management actions relative to past cases, which may warrant alerts as potential errors.

What carries the argument

The approximate graph obtained by collapsing nearby points into distortion-minimizing local representatives, together with the regularized harmonic solution and soft harmonic solution for anomaly detection.

If this is right

  • The algorithm allows fast online processing without storing all data points.
  • Regularization improves stability of the harmonic solution.
  • Conditional anomalies like fringe and isolated points can be handled nonparametrically.
  • Unusual clinical actions can be flagged for expert review based on graph structure.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The collapsing technique might generalize to other graph construction methods in machine learning.
  • Applying this to non-clinical domains could reveal broader uses for conditional anomaly detection.
  • Further theoretical analysis of the distortion minimization could lead to better approximation guarantees.

Load-bearing premise

A similarity graph built from the data accurately captures the underlying structure needed for both label propagation and identifying deviations as anomalies in clinical actions.

What would settle it

Observing that the approximate algorithm produces significantly different label assignments or anomaly detections compared to the exact harmonic solution on a benchmark dataset with known ground truth would falsify the approximation's reliability.

Figures

Figures reproduced from arXiv: 2605.03495 by Michal Valko.

Figure 1
Figure 1. Figure 1: Conditional vs. unconditional anomalies Our ability to detect unusual events in clinical data may have a tremendous impact on health care and its quality. First, the identification of an action that differs from an expected or usual pattern of care can aid in detection and prevention of the potential medical errors. According to the HealthGrades study (Wall Street Journal on July 27, 2004), medical errors … view at source ↗
Figure 2
Figure 2. Figure 2: Disadvantages of nearest neighbor approach for conditional anomaly detection view at source ↗
Figure 3
Figure 3. Figure 3: a. Similarity graph b. Three regularized harmonic solutions creasing all eigenvalues of the Laplacian L by γg [Smola and Kondor, 2003]. In Section 5.2 we use this property to bound the generalization error of our solutions. 3.3 MAX-MARGIN GRAPH CUTS In this part we present our algorithm that combines the harmonic solution with max-margin learning to learn a classifier f from some reproducing kernel Hilbert… view at source ↗
Figure 4
Figure 4. Figure 4: Running time for different methods on the SecStr dataset view at source ↗
Figure 5
Figure 5. Figure 5: Challenges for CAD: 1) fringe and 2) isolated points anomalies with respect to its class label and ignores the examples from the other classes. This may not work well for those examples for which x is away from all of the classes and hence x is an anomaly itself. To illustrate this, let us assume we have two classes (−1 and +1) and an example (x,−1), such that x is an anomaly in My=−1. The class-outlier ap… view at source ↗
Figure 6
Figure 6. Figure 6: Estimating class-conditional probabilities from two similarity graphs view at source ↗
Figure 7
Figure 7. Figure 7: Linear, cubic, and RBF decision boundaries for different methods view at source ↗
Figure 8
Figure 8. Figure 8: The thresholded empirical risk of training examples such that ¯ ¯ℓ ∗ i ¯ ¯ ≥ ε, on 3 letter recognition problems from the UCI ML repository. The plots are shown as functions of the parameter γg and correspond to the thresholds ε = 0 (light gray lines), ε = 10−6 (dark gray lines), and ε = 10−3 (black lines). All results are averaged over 50 random choices of 1 percent of labeled examples. Note that the para… view at source ↗
Figure 9
Figure 9. Figure 9: Estimating the likelihood ratio from a single graph view at source ↗
Figure 10
Figure 10. Figure 10: Snapshots from the environment adaptation and office space datasets view at source ↗
Figure 11
Figure 11. Figure 11: Face-based authentication dataset (left) and examples of labeled faces (right) view at source ↗
Figure 12
Figure 12. Figure 12: Comparison of SVMs, GC and MR on 3 datasets from the UCI ML repository view at source ↗
Figure 13
Figure 13. Figure 13: Coil and Car datasets from UCI ML Repository view at source ↗
Figure 14
Figure 14. Figure 14: UCI ML: Quality of approximation as a function of time view at source ↗
Figure 15
Figure 15. Figure 15: UCI ML: Quality of approximation as a function of number of centroids view at source ↗
Figure 16
Figure 16. Figure 16: Comparison of 3 face recognizers on 2 face recognition datasets view at source ↗
Figure 17
Figure 17. Figure 17: Speedups in the total, inference, and similarity computation times view at source ↗
Figure 18
Figure 18. Figure 18: The three synthetic datasets with known underlying distributions view at source ↗
Figure 19
Figure 19. Figure 19: Processing of data in the electronic health record view at source ↗
Figure 20
Figure 20. Figure 20: Examples of temporal features for continuous lab values view at source ↗
Figure 21
Figure 21. Figure 21: The weight matrix for 100 negative and 100 positive cases of HPF4 order view at source ↗
Figure 22
Figure 22. Figure 22: Computation time comparison for the three graph-based methods view at source ↗
Figure 23
Figure 23. Figure 23: Conditional anomaly detection on a synthetic view at source ↗
Figure 24
Figure 24. Figure 24: Histogram of alert examples in the study according to their alert score view at source ↗
Figure 25
Figure 25. Figure 25: The relationship between the alert score and the true alert rate view at source ↗
Figure 26
Figure 26. Figure 26: Histogram of anomaly scores for 2 different tasks view at source ↗
Figure 27
Figure 27. Figure 27: Medical Dataset: Varying graph size 1000 100 10 1 0.1 0.01 0.001 0.0001 1e−005 0.58 0.6 0.62 0.64 0.66 0.68 0.7 regularization (γg for Soft Harmonic and cost c for SVM) AUC of multi-task CAD SoftHAD SoftHAD with scaling SVM (RBF) SVM (RBF) with scaling view at source ↗
Figure 28
Figure 28. Figure 28: Medical Dataset: Varying regularization 95 view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper develops graph-based methods for semi-supervised learning via label propagation on data similarity graphs, proposing a fast approximate online algorithm that solves the harmonic solution on a collapsed graph using local representative points chosen to minimize distortion, along with regularization of the harmonic solution for improved stability. It further introduces nonparametric graph-based techniques for conditional anomaly detection that address fringe and isolated points via graph connectivity analysis and soft harmonic solutions, applies these to identifying unusual clinical actions in hospital data under the hypothesis that such actions may indicate errors, and validates the anomaly methods through a human evaluation study involving 15 critical care experts.

Significance. If the distortion-minimizing collapse is shown to yield a provably close approximation to the full-graph harmonic solution and the conditional anomaly methods reliably flag actionable errors in clinical settings, the work would offer computationally scalable extensions to standard graph-based SSL and a practical framework for conditional anomaly detection with direct relevance to healthcare quality improvement.

major comments (3)
  1. The central claim that collapsing nearby points into representative points that minimize distortion achieves good behavior both empirically and theoretically (abstract) requires an explicit error bound or convergence result showing that the approximate graph Laplacian solution remains close to the exact harmonic function; without this, the theoretical support for the online algorithm is unsubstantiated and load-bearing for the scalability contribution.
  2. The conditional anomaly detection methods (abstract and methods sections) rest on the assumption that the data similarity graph accurately captures underlying clinical structure such that deviations indicate errors rather than valid variation; this needs targeted sensitivity analysis or ablation on graph construction choices (e.g., kernel bandwidth or distance metric), as failure here would undermine both the fringe/isolated-point handling and the expert-validated alerts.
  3. The regularization added to the harmonic solution for stability (abstract) is presented as improving properties, but its interaction with the representative-point approximation must be analyzed to confirm it does not amplify distortion or degrade anomaly detection precision; a direct comparison of regularized vs. unregularized performance on the clinical task is needed.
minor comments (2)
  1. The term 'soft harmonic solution' is introduced without a precise definition or equation relating it to the standard harmonic function; add a brief formalization in the methods section.
  2. The human evaluation study description would benefit from explicit details on the alert presentation format, the exact questions posed to the 15 experts, and any inter-rater reliability statistics.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. The comments highlight important areas for strengthening the theoretical guarantees, empirical robustness, and comparisons in our graph-based methods for semi-supervised learning and conditional anomaly detection. We address each major comment point-by-point below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: The central claim that collapsing nearby points into representative points that minimize distortion achieves good behavior both empirically and theoretically (abstract) requires an explicit error bound or convergence result showing that the approximate graph Laplacian solution remains close to the exact harmonic function; without this, the theoretical support for the online algorithm is unsubstantiated and load-bearing for the scalability contribution.

    Authors: We agree that an explicit error bound would provide stronger theoretical support for the approximation. While our current analysis links distortion minimization to empirical closeness of the harmonic solutions, we will derive and include a formal bound in the revised manuscript showing that the difference between the approximate and exact solutions is controlled by the distortion measure and properties of the graph Laplacian. revision: yes

  2. Referee: The conditional anomaly detection methods (abstract and methods sections) rest on the assumption that the data similarity graph accurately captures underlying clinical structure such that deviations indicate errors rather than valid variation; this needs targeted sensitivity analysis or ablation on graph construction choices (e.g., kernel bandwidth or distance metric), as failure here would undermine both the fringe/isolated-point handling and the expert-validated alerts.

    Authors: We concur that sensitivity to graph construction parameters is critical for the reliability of the anomaly detection results in the clinical setting. In the revision, we will add a targeted ablation study varying the kernel bandwidth and comparing alternative distance metrics, evaluating their impact on fringe/isolated point handling and alignment with expert judgments. revision: yes

  3. Referee: The regularization added to the harmonic solution for stability (abstract) is presented as improving properties, but its interaction with the representative-point approximation must be analyzed to confirm it does not amplify distortion or degrade anomaly detection precision; a direct comparison of regularized vs. unregularized performance on the clinical task is needed.

    Authors: We will incorporate a direct empirical comparison of the regularized and unregularized harmonic solutions applied to the representative-point approximation on the hospital clinical data. This will include quantitative metrics on stability, precision of anomaly alerts, and any effects on approximation quality to confirm the benefits of regularization. revision: yes

Circularity Check

0 steps flagged

No circularity: derivations build on standard harmonic functions with independent approximations

full rationale

The paper extends established graph-based semi-supervised learning via harmonic solutions on similarity graphs, proposing an online approximation by collapsing points to minimize distortion and adding regularization for stability. It also introduces graph-connectivity and soft-harmonic methods for conditional anomaly detection. No equations or steps in the abstract or described claims reduce a prediction to a fitted input by construction, nor do they rely on self-definitional loops, load-bearing self-citations, or imported uniqueness theorems. The theoretical and empirical support for the approximations is presented as independent analysis rather than tautological renaming or ansatz smuggling. The derivation chain remains self-contained against external benchmarks like standard label propagation.

Axiom & Free-Parameter Ledger

2 free parameters · 2 axioms · 0 invented entities

The work rests on standard graph-based SSL assumptions plus new elements for approximation and anomaly handling; free parameters are implied but not quantified in the abstract.

free parameters (2)
  • regularization strength
    Regularization is added to the harmonic solution for stability, implying a tunable parameter.
  • number of representative points
    Collapsing points to minimize distortion requires choosing how many representatives to use.
axioms (2)
  • domain assumption A similarity graph on data points accurately reflects the structure needed for label propagation and anomaly detection.
    Fundamental to all graph-based methods described.
  • domain assumption Unusual actions relative to similar past cases indicate potential errors.
    Core hypothesis for the clinical anomaly application.

pith-pipeline@v0.9.0 · 5495 in / 1484 out tokens · 69421 ms · 2026-05-07T17:15:25.970903+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    C., Han, J., Wang, J., and Yu, P

    [Aggarwal et al., 2003] Aggarwal, C. C., Han, J., Wang, J., and Yu, P. S. (2003). A framework for clustering evolving data streams. InProceedings of the 29th international conference on Very large data bases - Volume 29, VLDB ’2003, pages 81–92. VLDB Endowment. [Aggarwal and Yu, 2001] Aggarwal, C. C. and Yu, P. S. (2001). Outlier detection for high dimens...

    work page 2003

  2. [1]

    C., Han, J., Wang, J., and Yu, P

    [Aggarwal et al., 2003] Aggarwal, C. C., Han, J., Wang, J., and Yu, P. S. (2003). A framework for clustering evolving data streams. InProceedings of the 29th international conference on Very large data bases - Volume 29, VLDB ’2003, pages 81–92. VLDB Endowment. [Aggarwal and Yu, 2001] Aggarwal, C. C. and Yu, P. S. (2001). Outlier detection for high dimens...

    work page 2003

  3. [2]

    Spurr, C., Khorasani, R., Tanasijevic, M., and Middleton, B. (2003). Ten commandments for effective clinical decision support: making the practice of evidence-based medicine a reality.J Am Med Inform Assoc, 10(6):523–530. [Belkin et al., 2004] Belkin, M., Matveeva, I., and Niyogi, P. (2004). Regularization and semi-supervised learning on large graphs. InP...

    work page 2003

  4. [2]

    Part II, pages 410–421

    Pro- ceedings. Part II, pages 410–421. [Aktolga et al., 2010] Aktolga, E., Ros, I., and Assogba, Y. (2010). Detecting outlier sections in us congressional legislation. InProceedings of SIGIR. [Asuncion and Newman, 2011] Asuncion, A. and Newman, D. (2011). UCI machine learning repository. [Bates et al., 2003] Bates, D. W., Kuperman, G. J., Wang, S., Gandhi...

    work page 2010

  5. [3]

    Ouimet, M. (2004). Out-of-sample extensions for LLE, isomap, MDS, eigenmaps, and spectral clustering. In Thrun, S., Saul, L., and Schölkopf, B., editors,Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA. 100 [Bennett and Demiriz, 1999] Bennett, K. and Demiriz, A. (1999). Semi-supervised support vector machines. InAdvances in N...

    work page 2004

  6. [3]

    100 [Bennett and Demiriz, 1999] Bennett, K

    MIT Press, Cambridge, MA. 100 [Bennett and Demiriz, 1999] Bennett, K. and Demiriz, A. (1999). Semi-supervised support vector machines. InAdvances in Neural Information Processing Systems 11, pages 368–

    work page 1999

  7. [4]

    Cooper, G. (2007). Evidence-based anomaly detection. InAnnual American Medical In- formatics Association Symposium, pages 319–324. [Haykin, 1994] Haykin, S. (1994).Neural Networks: A Comprehensive Foundation. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1st edition. [He and Carbonell, 2008] He, J. and Carbonell, J. (2008). Nearest-neighbor-based active...

    work page 2007

  8. [4]

    [Bezdek and Hathaway, 2002] Bezdek, J. C. and Hathaway, R. J. (2002). Some notes on alternating optimization. InProceedings of the 2002 AFSS International Conference on Fuzzy Systems. Calcutta: Advances in Soft Computing, AFSS ’02, pages 288–300, London, UK. Springer-Verlag. [Bousquet and Elisseeff, 2002] Bousquet, O. and Elisseeff, A. (2002). Stability a...

    work page 2002

  9. [5]

    [He et al., 2007] He, J., Carbonell, J., and Liu, Y

    Cambridge, MA. [He et al., 2007] He, J., Carbonell, J., and Liu, Y. (2007). Graph-based semi-supervised learning as a generative model. InProceedings of the 20th international joint conference on Artifical intelligence, pages 2492–2497, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc. 103 [Heard et al., 2010] Heard, N. A., Weston, D. J., Platanioti...

    work page 2007

  10. [5]

    (1997).Spectral Graph Theory

    [Chung, 1997] Chung, F. (1997).Spectral Graph Theory. American Mathematical Society. [Cortes et al., 2008] Cortes, C., Mohri, M., Pechyony, D., and Rastogi, A. (2008). Stability of transductive regression algorithms. InProceedings of the 25th International Conference on Machine Learning, pages 176–183. 101 [Cramér, 1999] Cramér, H. (1999).Mathematical met...

    work page 1997

  11. [6]

    Ridgeway, G. (2002). Likelihood-based data squashing: a modeling approach to instance construction.Data Mining and Knowledge Discovery, 6(2):173–190. [Manevitz and Yousef, 2002] Manevitz, L. M. and Yousef, M. (2002). One-class svms for document classification.J. Mach. Learn. Res., 2:139–154. [Markou and Singh, 2003a] Markou, M. and Singh, S. (2003a). Nove...

    work page 2002

  12. [6]

    [Eskin, 2000] Eskin, E. (2000). Anomaly detection over noisy data using learned probability distributions. InProc. 17th International Conf. on Machine Learning, pages 255–262. Morgan Kaufmann, San Francisco, CA. [Fergus et al., 2009] Fergus, R., Weiss, Y., and Torralba, A. (2009). Semi-supervised learn- ing in gigantic image collections. In Bengio, Y., Sc...

    work page 2000

  13. [7]

    Wang, H., and Kidd, N. (2005). An auctioning reputation system based on anomaly de- tection. InProceedings of the 12th ACM conference on Computer and communications security, CCS ’05, pages 270–279, New York, NY, USA. ACM. 105 [Sanchez et al., 2003] Sanchez, J., Barandela, R., Marques, A. I., Alejo, R., and J., B. (2003). Analysis of new techniques to obt...

    work page 2005

  14. [7]

    T., Hinton, G

    102 [Goldberger et al., 2004] Goldberger, J., Roweis, S. T., Hinton, G. E., and Salakhutdinov, R. (2004). Neighbourhood components analysis. InNeural Information Processing Systems (NeurIPS). [Gorban and Zinovyev, 2009] Gorban, A. and Zinovyev, A. (2009). Principal graphs and manifolds. InHandbook of Research on Machine Learning Applications and Trends: A...

    work page 2004

  15. [8]

    Williamson, R. C. (1999). Estimating the support of a high-dimensional distribution. Neural Computation, 13:2001. [Smola and Kondor, 2003] Smola, A. and Kondor, R. (2003). Kernels and regularization on graphs. In Schölkopf, B. and Warmuth, M., editors,Proceedings of the Annual Conference on Computational Learning Theory and Kernel Workshop, Lecture Notes ...

    work page 1999

  16. [8]

    [Grabner et al., 2008] Grabner, H., Leistner, C., and Bischof, H

    Information Science Reference. [Grabner et al., 2008] Grabner, H., Leistner, C., and Bischof, H. (2008). Semi-supervised on-line boosting for robust tracking. InProceedings of the 10th European Conference on Computer Vision, pages 234–247. [Gray and Neuhoff, 1998] Gray, R. and Neuhoff, D. (1998). Quantization.IEEE Transac- tions on Information Theory, 44(...

    work page 2008

  17. [9]

    Hauskrecht, M. (2008). Conditional anomaly detection methods for patient-management alert systems. InWorkshop on Machine Learning in Health Care Applications in The 25th International Conference on Machine Learning. [Valko and Hauskrecht, 2008] Valko, M. and Hauskrecht, M. (2008). Distance metric learn- ing for conditional anomaly detection. InTwenty-Firs...

    work page 2008

  18. [9]

    and Leland, R

    [Hendrickson and Leland, 1995] Hendrickson, B. and Leland, R. (1995). A multilevel algo- rithm for partitioning graphs. InProceedings of Supercomputing. [Jiang and Zhou, 2004] Jiang, Y. and Zhou, Z.-H. (2004). Editing training data for knn clas- sifiers with neural network ensemble. InLecture Notes in Computer Science 3173, pages 356–361. [Karypis and Kum...

    work page 1995

  19. [10]

    and Tan, P.-N

    [Valizadegan and Tan, 2007] Valizadegan, H. and Tan, P.-N. (2007). Kernel based detec- tion of mislabeled training examples. InProceedings of the Seventh SIAM International Conference on Data Mining, April 26-28, 2007, Minneapolis, Minnesota, USA. [Valko et al., 2008] Valko, M., Cooper, G., Seybert, A., Visweswaran, S., Saul, M., and Hauskrecht, M. (2008)...

    work page 2007

  20. [11]

    106 [Valko et al., 2010] Valko, M., Kveton, B., Huang, L., and Ting, D. (2010). Online semi- supervised learning on quantized graphs. InProceedings of the 26th Conference on Un- certainty in Artificial Intelligence. [Valko et al., 2011] Valko, M., Valizadegan, H., Kveton, B., Cooper, G. F., and Hauskrecht, M. (2011). Conditional anomaly detection using so...

    work page 2010

  21. [12]

    [Yan et al., 2009] Yan, D., Huang, L., and Jordan, M. (2009). Fast approximate spectral clustering. InProceedings of the 15th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. [Zhou et al., 2004] Zhou, D., Bousquet, O., Lal, T. N., Weston, J., and Scholkopf, B. (2004). Learning with local and global consistency.Advances in Neural Information P...

    work page 2009