Conditional anomaly detection with soft harmonic functions

In plain words

Imagine a dataset where every record has a set of inputs and a label, and the question is: which records have a label that looks wrong for their context? This paper treats that as "conditional anomaly detection". A record is only unusual relative to similar records, so a label that is common among its neighbours is fine and one that clashes with them is suspicious.

The method links every record to similar records in a graph, then lets each label spread through the graph, so a point's label is pulled toward the labels of the points around it. The amount each record's spread label agrees with its own given label becomes its anomaly score. Two safeguards stop the score from being fooled: records that sit alone far from the crowd, and records at the edge of a class, get a pull toward zero, so they are not reported just for being lonely or on the border.

The paper also shrinks the graph by replacing many records with a smaller set of representative points that carry weights, so the computation stays manageable for larger data. It is aimed at settings such as clinical records, where flagging an unusual decision for a human to review is the goal.

TL;DR

• Scores each labelled instance by how strongly its label disagrees with a soft label propagated over a similarity graph §3.1 eq. 4.
• A diagonal regularisation term (a sink) reduces confidence for isolated and fringe points §3.1.
• A quantised backbone graph with per-centroid multiplicities makes the solve cheaper; the multiplicity form is given without a worked example §3.2.
• Author-reported: highest agreement (AUC-style score) on all three synthetic datasets and on Housing and Auto MPG; on Wine Quality it is slightly below QDA and SVM. On the EHR set the text reports it outperforms SVM, with no numbers tab. 1 tab. 2 fig. 6.

Problem

Given n past labelled examples (with possible label noise) and m recent ones, rank the recent instances whose label is unusual given their input §1. The authors do not assume the labels are clean. The problem is set for binary labels, y in {-1, +1} §2.2.

Existing approaches are either unconditional outlier detectors or classifiers that flag disagreement with a predicted label. The first ignores the label; the second is weak near isolated points (no support for alternative responses) and fringe points (low likelihood at the boundary of the class support) §1. The authors also note that k-NN-style local methods miss clusters of anomalous instances §1. The paper's target is a non-parametric score that uses the manifold structure of the data §1 §2.1.

Method

Setup. Build a similarity graph G on all n+m instances, with weights W and unnormalised Laplacian L = D - W, where D is the diagonal of row sums §2.2. Use the unconstrained regularisation

min over l of (l - y)^T C (l - y) + l^T K l eq. 1

with closed-form solution l* = (C^{-1} K + I)^{-1} y eq. 2 §2.3. The hard harmonic solution corresponds to K = L with infinite label weight, and the consistency method to a normalised Laplacian §2.3.

Step 1: propagate soft labels (all examples treated as labelled). Every instance counts as labelled, so the paper uses a finite constant c_l on the diagonal of C, C = c_l I, instead of infinity. This lets labels spread past other labelled points and keeps the solution "soft" §3.1.

Step 2: regularise against isolated and fringe points. Set K = L + gamma_g I, where gamma_g is a scalar. The authors interpret this as adding an extra sink node of label 0, joined to every instance with weight gamma_g. Isolated points, which have small total similarity, are affected most §3.1.

Step 3: closed form as a linear system. Substituting gives l* = (c_l^{-1} L + (1 + gamma_g / c_l) I)^{-1} y eq. 5–6. The authors solve the linear system rather than form the inverse, citing numerical instability §3.1, footnote eq. 7.

Step 4: anomaly score. s_i = |l*_i - y_i| eq. 4. A large score means the label disagrees with the propagated soft label. The authors state that a high confidence with sign(l*_i) different from y_i is the intended case for a conditional anomaly §3.1.

Step 5: backbone graph (for large n). Sample nodes from the training data and quantise them to k << n centroids, so that the solve costs O(k^3) instead of O(n^3) §3.2. Each centroid i gets a multiplicity v_i, the number of nodes it represents, set from the empirical prior §3.2. With V = diag(v), the multiplicity-aware quantities are W^V = V W V, L^V = L(W^V), K^V = L^V + gamma_g V and C^V = V^{1/2} C V^{1/2} §3.2. The regularised problem eq. 8 then has solution l^{V*} = (V^{-1} L^V / c_l + (1 + gamma_g / c_l) I)^{-1} y (derived from the intermediate steps in §3.2; see Pitfalls for the printed form). The score is |l^{V*} - y| §3.2.

# Conditional anomaly score, full-graph form  [§3.1] [eq. 4] [eq. 6–7]
# Input:  features (N, d), labels y in {-1, +1} (N,), gamma, c_l
# Output: anomaly score (N,)

def soft_harmonic_scores(features, labels, gamma, c_l):
    # Pairwise similarity weights; weighting metric is in [§4.3.3]
    weights = similarity(features)              # (N, N), symmetric
    # Unnormalised graph Laplacian  [§2.2]
    laplacian = diag(weights.sum(axis=1)) - weights
    # Linear system (L / c_l + (1 + gamma / c_l) I) soft = y  [eq. 7]
    system = laplacian / c_l + (1.0 + gamma / c_l) * eye(N)
    # Solve the system; do not form the inverse  [§3.1, footnote]
    soft_labels = solve(system, labels)
    # Anomaly score: distance from the given label  [eq. 4]
    return abs(soft_labels - labels)

# Backbone-graph form  [§3.2]  (equations there are unnumbered)
# Input:  centroids (k, d), multiplicities (k,), centroid labels (k,)
# Output: anomaly score (k,)

def backbone_scores(centroids, multiplicities, labels, gamma, c_l):
    # Similarity among centroids  [§3.2]
    weights = similarity(centroids)              # (k, k)
    # Scale by multiplicities: W^V = V W V  [§3.2]
    weights_v = (multiplicities[:, None] * weights
                 * multiplicities[None, :])
    # Laplacian of the scaled graph  [§3.2]
    laplacian_v = diag(weights_v.sum(axis=1)) - weights_v
    # System (V^{-1} L^V / c_l + (1 + gamma / c_l) I) soft = y  [§3.2]
    system = (laplacian_v / (c_l * multiplicities[:, None])
              + (1.0 + gamma / c_l) * eye(k))
    soft_labels = solve(system, labels)
    return abs(soft_labels - labels)

Hyperparameters

Results

Author-reported. Setup: three synthetic Gaussian-mixture datasets (D1–D3), three UCI datasets (Wine Quality, Housing, Auto MPG), and a private EHR dataset §4. The metric is an agreement score with the true anomaly ordering, counted as the Wilcoxon / AUC of swapped pairs §4.1. Entries are mean (variance) over 100 runs, as stated in the table captions.

Synthetic data §4.1 tab. 1

UCI datasets §4.2 tab. 2

The text says SoftHAD "either performed the best or was close to the best" on UCI §4.2. On Wine Quality it is below QDA and SVM, by about 0.5 to 0.6 points.

Medical (EHR) data §4.3.5 fig. 5 fig. 6

No numeric AUC appears in the text or in a table; the results are only in figures. Stated qualitatively: SoftHAD is less sensitive to graph size than w-kNN on the same graph, which the authors attribute to the multiplicity adjustment §4.3.5 fig. 5. SoftHAD outperforms SVM with RBF kernel across the regularisation range tested, and scaling improves both methods §4.3.5 fig. 6. Expert agreement on 222 pairs is the evaluation basis §4.3.2.

Paper vs code

No official code.

Searched: the paper's LaTeX source (no code or project URL; the arXiv metadata has no comments field); GitHub repository search for "SoftHAD", "soft harmonic anomaly" and "hauskrecht anomaly", all returning zero results; GitHub search for "conditional anomaly detection", which returned unrelated repositories with no link to the authors. A web search was not permitted in this run.

Pitfalls

• Equation numbers in §3.1. The two-row align block that gives the closed form is numbered by row in the source (no visible numbers), so this card cites it as eq. 5–6, with the labelled row being eq. 6. Cite the section if the numbering matters.
• Printed backbone formula has a typo. The final line of the multiplicity derivation in §3.2 writes the constant term as c_l gamma_g. The preceding steps give gamma_g / c_l, since (c_l V)^{-1} gamma_g V = (gamma_g / c_l) I. The card uses gamma_g / c_l. No code is available to settle it.
• Centroid construction and labels are unspecified. The paper says nodes are sampled and quantised to k centroids with multiplicities §3.2, but not how centroids are computed, how many there are, or what label each centroid gets (majority, mean, or a single class). This is the largest gap for reimplementation.
• Out-of-sample scoring is not described. The method is transductive: each instance is part of the graph. How to score a new instance (rebuild the graph, or extend it) is not stated.
• sigma is ambiguous. "10% of the empirical variance of the Euclidean distances" §4.3.3 could mean sigma = 0.1 x variance or sigma² = 0.1 x variance, and the variance could be over all pairs or per point. The authors say the method is not sensitive to small changes, but the graph must stay connected.
• Score scaling leaves range questions open. The min and max come from training scores §4.3.4. It is not stated whether those training scores are computed in-sample (the instance is its own labelled neighbour) or how test scores outside [0, 1] are handled.
• Raw scores are unbounded. Before scaling, s_i = |l*_i - y_i| has no fixed range; l* is not constrained to ±1 §3.1.
• Label coding in UCI. Labels are y = (y_r ≥ 0) on a response scaled to [-1, +1]. The mapping to ±1 used by the method, and the ground-truth score |y_r - label| with a label in {0, 1} or {-1, +1}, are not stated §4.2.
• Evaluation split is unclear. For synthetic data, whether agreement is measured on train or test is not stated §4.1. For the EHR data, the 222 pairs are not tied to a split §4.3.2.
• Hidden costs. The solve is O(n^3) on the full graph §3.1; the backbone form makes it O(k^3) at the cost of quantisation §3.2. The graph is dense (Gaussian weights, no sparsification) and the unnormalised Laplacian is used.
• Numerical stability. The authors avoid the explicit inverse because of numerical instability §3.1, footnote. Use a linear solver with a positive-definite system check; gamma_g > 0 and c_l > 0 are required for the matrix to be well-posed in the form given.
• Expert labels are majority-vote. Each of 222 pairs was judged by three experts on whether the action is anomalous and clinically relevant; the 2-of-3 majority is the ground truth §4.3.2. The paper does not report agreement between experts.

Lineage

• Builds on: the harmonic solution of Zhu et al. (2003) and the unconstrained regularisation view of Cortes et al. (2008) §2.3. Plain-text references, no cards in this wiki.
• Related methods: cross-outlier detection of Papadimitriou and Faloutsos §2.1 and mislabel detection by Brodley et al. §2.1; the paper says its score is more robust to fringe points than cross-outlier detection §2.1.
• Compared against: 1-class SVM, QDA, RBF SVM and weighted k-NN on the same graph §4.
• Superseded by: not known.