AIResearchGraphsAnomaly Detection

Graph Anomaly Detection as Finite-Horizon Control

EB-GAD scores graph anomalies with no labels and no training: empirical Bayes fits a graph-aware Gaussian model of normal in closed form, and each node is scored by the finite-horizon control energy needed to steer a neutral start to it under a graph Ornstein–Uhlenbeck process. Best or tied-best AUROC on 9 of 11 benchmarks.

Paper Code

A three-panel diagram: a network with three red nodes among blue ones and the equation of a graph-aware relaxation process; a heat map of a likelihood over two parameters with a star at its maximum, above a plot of Newton iterations converging; and the network again above two separated score distributions for normal nodes and anomalies
The EB-GAD pipeline, from the paper: (a) a graph-aware Ornstein–Uhlenbeck process relaxes toward a template; (b) empirical Bayes fits its precision without labels; (c) the fitted dynamics produce a bank of anomaly scores, from which a fixed selector picks one family per dataset.

This post is a tour of our NeurIPS 2026 paper, “Graph Anomaly Detection as Finite-Horizon Control: Training-Free Scoring via Empirical Bayes,” written with Thomas Markovich of Block, Florence Regol of Mila and Yizhou Sun of UCLA. Its aim is to find the unusual nodes in a network, such as fraudulent accounts, fake reviewers or suspicious transactions, without labels and without training a neural network. We write down an explicit statistical picture of what “normal” looks like on a graph, let the unlabeled data fit its three knobs, and score each node by how much effort it takes to steer a neutral starting point to that node under a simple graph-aware dynamics. On 11 benchmarks the method, which we call EB-GAD, has the best or tied-best AUROC on 9, with its largest margins on financial fraud networks of up to 3.7 million nodes.

Why anomalies in networks are hard

Many of the systems we care about are networks, in which a payment platform connects accounts by transactions, a review site connects users to products, and a social platform connects people to people. Each node, an account or a user, comes with features such as transaction sizes, account age or statistics of its review text, while the edges say who interacts with whom, and graph anomaly detection asks which nodes look abnormal. Two things make the question hard in practice.

The first difficulty is that there are almost no labels, because fraud is rare, confirmed cases are scarce and arrive late, and fraudsters change their tactics, so we want an unsupervised method, one that gives every node a suspicion score using only the network itself. The second is that context matters, since a node can look perfectly ordinary on its own and still be odd for where it sits in the network, as the toy example below shows.

A histogram of feature values in which one orange bar sits among many blue ones, beside a network of two communities, blue on the left and red on the right, with one red node circled inside the blue community
A toy network with two communities. (a) On feature values alone, the odd node (orange) sits inside a crowd of similar values. (b) On the network it is clearly out of place: its value is typical of the right-hand community, but every one of its neighbors is low.

A detector therefore has to decide how much the network should define what counts as normal. In some networks the edges connect similar nodes and are a reliable guide, but in fraud they can mislead, since fraudsters deliberately connect to ordinary accounts in order to blend in, and we call this question graph trust. Most existing methods answer it implicitly, through the design of a neural network, a training loss that reconstructs the graph or contrasts views of it, and a sweep of hyperparameters, and the resulting scores are expensive to obtain, hard to interpret and unstable from one network to the next. In our benchmark several published methods even score below chance on some datasets. Our goal was the opposite: to make every choice explicit, to fit it from unlabeled data in closed form, and to train nothing.

An anomaly is a surprise

A classic way to define an anomaly score is surprise, which means building a model p(x)p(x) of normal data and scoring a point by how unlikely it is,

s(x)=−log⁡p(x). s(x) = -\log p(x).

If the model of normal is a Gaussian with mean μ\mu and covariance Σ\Sigma, surprise becomes a weighted squared distance, the Mahalanobis distance,

s(x)=12 (x−μ)⊤Q (x−μ)+const. s(x) = \tfrac{1}{2}\,(x-\mu)^\top Q\,(x-\mu) + \text{const}.

The matrix Q=Σ−1Q = \Sigma^{-1} is called the precision, and a useful way to read it is as a price list for deviations: moving in a direction where normal data varies a lot is cheap, while moving against the grain of the data is expensive.

A scatter of normal points forming a tilted ellipse, with two marked points A and B at the same distance from the center, A along the long axis of the ellipse and B across it
Points A and B are the same straight-line distance from the center, but B goes against the shape of the normal data, so its surprise is about 15 times larger.

The whole game therefore comes down to two choices, what normal looks like, which is the mean, and which deviations are cheap or expensive, which is the precision, and EB-GAD builds both from the graph.

Patterns on a graph have frequencies

To use the graph, we need a way to say whether a pattern of values over the nodes is smooth, with neighbors agreeing, or rough, with neighbors disagreeing. The tool is the graph Laplacian L=D−AL = D - A, where AA is the adjacency matrix and DD holds the node degrees, and for a pattern xx that assigns one number to each node,

x⊤L x=∑(i,j) ∈ edges(xi−xj)2, x^\top L\, x = \sum_{(i,j)\,\in\,\text{edges}} (x_i - x_j)^2 ,

which is small when connected nodes have similar values and large when they do not. In practice EB-GAD uses the symmetric-normalized Laplacian I−D−1/2AD−1/2I - D^{-1/2} A D^{-1/2}, whose eigenvalues lie between 0 and 2, so that high-degree nodes do not dominate, but the intuition is the same. The eigenvectors of LL play the role of frequencies on the graph, as sines and cosines do for sound: each eigenvector vjv_j is a pattern over the nodes, and its eigenvalue λj\lambda_j measures how rough that pattern is, so that a small λ\lambda means a smooth, slowly varying pattern and a large one a pattern that flips sign across many edges.

Four panels of red and blue dots: three grids showing Laplacian eigenvectors from smooth to rough, and a social network in which the smoothest pattern splits the nodes into two groups
Laplacian eigenvectors from smooth to rough. On a grid they look like familiar waves, and on a real social network, Zachary’s karate club, the smoothest non-constant pattern splits the club into its two historical factions.

Any feature pattern can be written as a mix of these modes, and we write SjS_j for how much energy a pattern puts into mode jj, which lets us speak of the smooth and the rough parts of the data, exactly what a model of normal on a graph needs.

EB-GAD’s picture of normal

EB-GAD’s model of normal has two ingredients, a template, which says what each node should look like, and a precision, which says how much each kind of deviation costs, and three interpretable knobs control them.

The template

The template is a smoothed version of the features,

m=(γ2I+L)−1 x, m = (\gamma^2 I + L)^{-1}\, x ,

which in frequency terms multiplies mode jj by 1/(γ2+λj)1/(\gamma^2 + \lambda_j), keeping smooth patterns and filtering out rough ones, with the bandwidth γ\gamma setting how aggressive the smoothing is. It is the graph version of ridge or Tikhonov smoothing, since up to a constant factor it is the pattern that stays closest to xx while paying a penalty m⊤L mm^\top L\, m for roughness, and each node’s template value is, in effect, a prediction from its neighborhood, and what we actually score is the residual, the part of each node that its neighborhood does not explain,

Δ=x−m. \Delta = x - m .
Three views of the toy network: the raw feature values, the smoothed template, and the residual, in which only the odd node stands out
The toy network from the start of this post, with template bandwidth γ=1\gamma = 1. (b) The template pulls each node toward its neighbors, so the odd node’s prediction is low. (c) Its residual is large (+1.52, against a typical size of 0.41), while ordinary nodes have small residuals.

The precision

Next we need a price list for residuals, and EB-GAD uses

Qρ=ρ (κ2I+L)+(1−ρ) I, Q_\rho = \rho\,(\kappa^2 I + L) + (1-\rho)\, I ,

which charges each mode jj the price

qj=ρ (κ2+λj)+(1−ρ). q_j = \rho\,(\kappa^2 + \lambda_j) + (1-\rho).

Both knobs have plain meanings, for graph trust ρ\rho, a number between 0 and 1, decides how much the graph counts: at ρ=0\rho = 0 the graph is ignored and every residual pattern costs the same, while at ρ=1\rho = 1 rough residual patterns, in which neighbors disagree, are much more expensive than smooth ones. The length-scale κ\kappa sets the frequency below which all patterns cost about the same and above which the cost grows with roughness. The form is borrowed from Matérn Gaussian processes on graphs, whose precision (κ2I+L)ν(\kappa^2 I + L)^{\nu} is the graph counterpart of the Matérn family that machine learning uses for smooth functions in space; EB-GAD takes ν=1\nu = 1, which keeps QρQ_\rho as sparse as the graph itself, a Gaussian Markov random field, and mixes it with the identity through ρ\rho, so that a single number moves the model from ignoring the graph to trusting it fully and the data can choose the point on that path.

Two line plots against graph frequency: on the left, template filters that fall from one toward zero, falling faster for smaller bandwidths; on the right, residual costs that rise with frequency, rising more steeply for higher graph trust
(a) The template keeps smooth patterns and removes rough ones; the curves are normalized to 1 at λ=0\lambda = 0, and a smaller γ\gamma smooths more. (b) Graph trust ρ\rho, shown here with κ=1\kappa = 1, decides how steeply the cost of a residual grows with its roughness.

With the template and the precision in place, the simplest anomaly score is each node’s share of the Gaussian surprise of the residual,

Ji⋆=12 ∥[ Qρ1/2 Δ ]i∥2. J^\star_i = \tfrac{1}{2}\,\big\|\big[\,Q_\rho^{1/2}\,\Delta\,\big]_{i}\big\|^2 .

When nodes have many features, each feature column is treated as its own signal on the graph, all of them sharing the same QρQ_\rho. This equilibrium score is EB-GAD’s starting point, and the reason for its name, and for going beyond it, will become clear once we add time.

Empirical Bayes: letting the unlabeled data set the knobs

We now have three knobs, graph trust ρ\rho, length-scale κ\kappa and template bandwidth γ\gamma, and the question is where their values come from when there are no labels. Empirical Bayes is the classical answer to exactly this situation, in which many units share a few unknown parameters of a prior and nothing outside the data fixes them. A fully Bayesian analysis would put a further prior on those parameters, whereas empirical Bayes estimates them from the data themselves, by maximizing the marginal likelihood, the probability of the observations once the latent quantities have been integrated out. Herbert Robbins introduced the approach in the 1950s, Bradley Efron and Carl Morris showed in the 1970s that it explains the power of the James–Stein estimator, which shrinks many means toward a common value and beats estimating each of them separately, and machine learning knows it as type-II maximum likelihood or evidence maximization, the standard way of fitting the hyperparameters of a Gaussian process.

It suits graph anomaly detection for two reasons, the first being that every node is a unit and all of them share the same three knobs, so thousands or millions of nodes inform three numbers and the fit is stable even though no single node says much, and the second that the quantity being maximized is the probability of the whole unlabeled graph, which is dominated by normal nodes because anomalies are rare. In EB-GAD the latent quantity is the residual field: each feature column of the residual is modeled as Δd∼N(0,Qρ−1)\Delta_d \sim \mathcal{N}(0, Q_\rho^{-1}), independently across the DD features, so its log-likelihood is a sum of quadratic forms −12Δd⊤QρΔd-\tfrac{1}{2}\Delta_d^\top Q_\rho \Delta_d and log-determinants 12log⁡det⁡Qρ\tfrac{1}{2}\log\det Q_\rho. In the eigenbasis of the Laplacian both separate by mode, the quadratic forms into qjq_j times the residual energy Sj=∑d(vj⊤Δd)2S_j = \sum_d (v_j^\top \Delta_d)^2 and the log-determinant into ∑jlog⁡qj\sum_j \log q_j, and because everything is linear and Gaussian the whole likelihood has a closed form,

log⁡p(data∣ρ,κ,γ)=−12∑jqjSj⏟fit+D2∑jlog⁡qj⏟confidence+const, \begin{aligned} &\log p(\text{data} \mid \rho,\kappa,\gamma) \\ &= \underbrace{-\tfrac{1}{2}\textstyle\sum_j q_j S_j}_{\text{fit}} + \underbrace{\tfrac{D}{2}\textstyle\sum_j \log q_j}_{\text{confidence}} + \text{const}, \end{aligned}

where the constant does not depend on the knobs. The two terms pull in opposite directions, since the second rewards high precision, a confident and concentrated model, while the first penalizes high precision wherever the data actually has energy, and the balance between them is a built-in Occam’s razor, in which the fitted price list is as strict as the data allows.

Because the likelihood is dominated by normal nodes, the fitted model approximately describes normal behavior even though no label is used. In our robustness study, contaminating a dataset with up to 24% anomalies barely moved the fit, and detection of the original anomalies dropped by 1.1 AUROC points on Weibo. The fit itself is cheap, a few Newton steps for ρ\rho, in which the likelihood is concave, and small grids for κ\kappa and γ\gamma.

Two heat maps of the likelihood over graph trust and length-scale, each with a star at the fitted values, above plots of Newton iterations whose error falls steeply to machine precision
The empirical-Bayes likelihood over graph trust ρ\rho and length-scale κ\kappa on two real datasets, from the paper, with the fitted values starred. Below, the Newton iterations for ρ\rho converge to machine precision in about five steps.

This is what we mean by training-free: no neural network, no gradient descent, no epochs, no labels and no validation set. EB-GAD does fit three numbers, by maximizing a closed-form likelihood on the unlabeled graph, so “training-free” does not mean “hyperparameter-free.”

Adding time: normal data as a relaxation process

So far the model is static, a Gaussian with mean mm and precision QρQ_\rho, and the equilibrium score weighs each graph mode by its stationary variance and nothing else. Any other weighting of the modes would be an ad hoc spectral filter with no tie to the fitted model, so the key idea of the paper is to view the Gaussian as the end point of a simple process, because that process gives a whole family of weightings, all derived from the same model. Picture a ball attached by a spring to the template and jiggled by random noise: started anywhere, it drifts toward the template and then keeps jiggling around it. This is an Ornstein–Uhlenbeck process, and our graph-aware version is

dXt=− Qρ (Xt−m) dt+2 dWt, dX_t = -\,Q_\rho\,(X_t - m)\,dt + \sqrt{2}\,dW_t ,

where WtW_t is a Brownian motion. Leonard Ornstein and George Uhlenbeck introduced the process in 1930 as a model of the velocity of a Brownian particle slowed by friction, and it has a special place among random processes, since by a theorem of Doob it is, up to rescaling, the only process that is at once stationary, Gaussian and Markov. It is also the Langevin diffusion of a Gaussian: for any energy U(x)U(x) the dynamics dXt=−∇U(Xt) dt+2 dWtdX_t = -\nabla U(X_t)\,dt + \sqrt{2}\,dW_t settle into the distribution proportional to e−U(x)e^{-U(x)}, and when UU is the quadratic surprise 12(x−m)⊤Qρ(x−m)\tfrac{1}{2}(x-m)^\top Q_\rho (x-m), its gradient is linear and the Langevin diffusion is exactly the process above. Readers who work on generative models will recognize it as the forward process of score-based diffusion models, which relaxes data toward white noise; here the process starts from a neutral point and relaxes toward the fitted graph Gaussian instead.

These properties are what make the formulation natural rather than decorative, for the process is the canonical dynamics whose resting state is our fitted Gaussian, and its drift is the fitted precision itself, so no new parameter is needed to describe it; it is linear, so every quantity we need has a closed form in the Laplacian’s eigenbasis; and it relaxes each mode at its own rate, so time becomes a principled knob for weighting smooth against rough deviations. The paper writes the process with a rate α(t)\alpha(t) that may vary in time, as in the cover figure, but only the integrated horizon matters for the scores, so we keep the rate constant here. Run long enough, the process settles into exactly our Gaussian N(m, Qρ−1)\mathcal{N}(m,\,Q_\rho^{-1}), but before it settles something interesting happens, for each graph mode relaxes at its own speed qjq_j: rough modes, with large qjq_j, settle almost at once, while smooth modes take their time.

Two panels: on the left, random paths of a rough mode and a smooth mode relaxing toward the template over time, the rough one arriving quickly; on the right, curves showing what fraction of its final spread each mode has reached as the horizon grows
(a) A rough mode (orange) snaps to the template quickly, while a smooth mode (blue) is still on its way; thin lines are random paths and thick lines their averages. (b) The fraction of its final spread each mode has reached after time Γ\Gamma.

Started from a neutral point X0=0X_0 = 0, which means “average” because the features are standardized, the state after a time horizon Γ\Gamma is Gaussian, with

μΓ=(I−e−ΓQρ) m,σj2(Γ)=1−e−2Γqjqj, \begin{gathered} \mu_\Gamma = \big(I - e^{-\Gamma Q_\rho}\big)\, m , \\ \sigma_j^2(\Gamma) = \frac{1 - e^{-2\Gamma q_j}}{q_j}, \end{gathered}

the second being the spread of mode jj. We do not claim that real fraud data evolved by this process, for the dynamics are a modeling device: they are the canonical process whose resting state is the Gaussian we fitted, so every score derived from them shares the same fitted model of normal.

The score: how hard is it to steer to this node?

Now imagine that we could push the process with a steering input utu_t, and ask what is the least total effort needed to start at the neutral point and land exactly on the observed node at time Γ\Gamma. For a normal node the process drifts there almost by itself, while for an anomaly we have to push hard, and for this linear system the minimum steering energy has a closed form, which equals the surprise of the observation under the time-Γ\Gamma Gaussian,

E(0→x;Γ)=12(x−μΓ)⊤ΣΓ−1(x−μΓ)=−log⁡p(x∣X0=0,Γ)+const. \begin{aligned} &\mathcal{E}(0 \to x; \Gamma) \\ &\quad = \tfrac{1}{2}(x - \mu_\Gamma)^\top \Sigma_\Gamma^{-1}(x - \mu_\Gamma) \\ &\quad = -\log p(x \mid X_0{=}0, \Gamma) + \text{const}. \end{aligned}

The equality between effort and surprise is a classical fact of linear control theory rather than a coincidence. For a linear system x˙=Ax+Bu\dot x = Ax + Bu, the least energy ∫0Γ∥ut∥2 dt\int_0^\Gamma \|u_t\|^2\,dt needed to move between two states in time Γ\Gamma is a quadratic form in the inverse of the controllability Gramian WΓ=∫0ΓeAtBB⊤eA⊤t dtW_\Gamma = \int_0^\Gamma e^{At} B B^\top e^{A^\top t}\,dt, a result that goes back to Kalman, and for our process, with A=−QρA = -Q_\rho and B=2 IB = \sqrt{2}\,I, this Gramian is exactly the covariance ΣΓ\Sigma_\Gamma of the noise-driven state. The cheapest way to reach a point and the probability of reaching it by chance are two readings of the same matrix, so the score has both a statistical meaning, surprise under the fitted model, and a mechanical one, how hard the graph dynamics resist arriving at this node.

We call this the finite-horizon control energy, and on mode jj the cost per unit of residual is

q~j(Γ)=qj1−e−2Γqj  ≥  qj. \tilde q_j(\Gamma) = \frac{q_j}{1 - e^{-2\Gamma q_j}} \;\ge\; q_j .
Two panels: on the left, the unsteered process drifting from a neutral start toward the template within a shaded band, with a small nudge to reach a normal node and a large push to reach an anomalous one; on the right, curves of the relative cost of a deviation across graph frequencies for several horizons, highest for smooth deviations at short horizons
(a) For one mode, the unsteered process drifts from the neutral start toward the template, and the shaded band is where it usually ends up, so a normal node needs a gentle nudge and an anomalous one a large push. (b) The cost of a deviation relative to equilibrium across graph frequencies, with ρ=0.7\rho = 0.7 and κ=0.5\kappa = 0.5. Short horizons make smooth deviations much more expensive, and as Γ→∞\Gamma \to \infty the equilibrium score J⋆J^\star returns.

The right-hand panel is the heart of the idea, for at a long horizon every mode has settled and the score is the equilibrium surprise J⋆J^\star, but at a short horizon the smooth modes have not had time to wander, so that any deviation in a smooth direction is expensive. A short horizon therefore asks a different question, whether a node is surprising before its neighborhood’s pattern has fully settled, and since different networks reveal their anomalies at different horizons, we keep the whole range.

Two more dials complete the family, the first of which is an endpoint tolerance λc\lambda_c that allows a little slack instead of landing exactly on the node, so that the per-mode cost becomes cj=(λc−1+σj2(Γ))−1c_j = \big(\lambda_c^{-1} + \sigma_j^2(\Gamma)\big)^{-1} and the score checks whether the evidence survives softer matching. The second is a ratio score, needed because some normal nodes simply have large residuals overall: dividing a node’s control energy by the size of its residual, CRi=Ci/∥Δi∥2CR_i = C_i / \|\Delta_i\|^2, asks a scale-free question, how much of this node’s deviation is of the kind the graph says is expensive.

A bank of scores, and choosing one without labels

Sweeping the horizon Γ\Gamma and the tolerance λc\lambda_c gives a bank of scores, all of which share one fitted model of normal, so that they are comparable and calibrated against the same baseline. EB-GAD uses them through four families. The equilibrium anchor, J⋆J^\star or its ratio, is the classic Gaussian surprise of the residual and the default whenever the finite-horizon diagnostics are not stable enough to justify leaving it; the control energy CΓ,λcC_{\Gamma,\lambda_c} measures the absolute effort to reach a node at a finite horizon and is used when the size of the residual is itself informative; the control ratio CRΓ,λcCR_{\Gamma,\lambda_c} measures the share of the residual that the graph makes expensive and is used when raw residual size would otherwise dominate; and profile aggregation combines the evidence across horizons and tolerances when the signal is spread over many of them.

For a new network, with no labels, EB-GAD chooses among these with a fixed, label-free selector that is the same on every dataset. Simple graph statistics pick the family, namely how similar the features of connected nodes are, which is feature homophily, how dense the graph is, and how many features each node has, and within the family the selector prefers a score that departs clearly from the fitted model of normal and whose ranking stays stable when the horizon or the tolerance is nudged, favoring robust scores over one lucky configuration. The selector’s cutoffs are engineering defaults developed on these benchmarks rather than derived from a single principle, but they are robust, since perturbing each of its 21 cutoffs by ±25% leaves the selection unchanged in 99.4% of cases. The figure at the top of this post shows the whole pipeline, from the graph-aware process around the template, through the empirical-Bayes fit of the precision, to the bank of scores and the selector.

A worked example: the karate club

Zachary’s karate club is a classic social network of 34 members, recorded just before the club split in two. As features we use each member’s connection profile, the row of the adjacency matrix, and we run the paper’s pipeline as it is.

The karate club network with nodes shaded by anomaly score, three of them circled and labeled: member 1, the instructor, member 34, the club president, and member 33
EB-GAD’s equilibrium score on the karate club. The three most anomalous members are the two faction leaders, member 34, the club president, and member 1, the instructor, followed by member 33.

The leaders stand out, as they should, since their connection profiles are unlike anyone else’s, and the fitted knobs are interpretable: empirical Bayes sets graph trust to ρ≈0.008\rho \approx 0.008, because when the features are the connections themselves, the graph’s information is already in the template, and the fit correctly declines to count it a second time in the precision. Zachary’s published data is also inconsistent about one edge, between members 23 and 34, and toggling it changes the scores only locally, with 98.8% of the change falling on the two endpoints and their neighbors, while the overall ranking barely moves, at a rank correlation of 0.989.

Results

We compared EB-GAD with 9 baselines on 11 benchmarks, 7 standard anomaly-detection graphs drawn from social, review and citation networks and 4 financial fraud networks with up to 3.7 million nodes. EB-GAD runs with one fixed procedure everywhere, and no label enters any step before evaluation.

A dot plot comparing, for each of eleven datasets, the AUROC of EB-GAD (orange) with that of the best of nine baselines (blue), with the margin labeled beside each pair
EB-GAD (orange) against the strongest competitor on each dataset (blue). AUROC is the probability that a random anomaly is ranked above a random normal node, so 50 is chance and 100 is perfect.

EB-GAD has the best or tied-best AUROC on 9 of the 11 datasets, with large margins on financial fraud, 21.7 points on T-Finance, 9.2 on Elliptic, 9.6 on Elliptic++ and 2.6 on DGraph, and 14.5 points on the YelpChi review-fraud graph. It is second on BlogCatalog and ACM, behind TAM, a strong method built on local neighbor affinity, and on several datasets its scores separate the two groups cleanly.

Four density plots, for T-Finance, Elliptic, Facebook and Weibo, each showing the distribution of scores for normal nodes in blue and anomalies in red, the red curves concentrated at higher ranks
The distribution of EB-GAD’s score, on a rank scale, for normal nodes (blue) and anomalies (red), from the paper. A method at chance would show two flat, overlapping curves.

The time dimension earns its place: holding the fitted model fixed, the finite-horizon families improve on the equilibrium score by 3.6 points on Facebook, 4.7 on T-Finance and 4.7 on ACM, and are at parity elsewhere, a gain that comes from aggregating and normalizing a family of scores that share one fitted model rather than from one lucky horizon. The method is also fast, for on 16 CPU threads a full run takes from 8 seconds on Facebook to 33 minutes on DGraph, with its 3.7 million nodes, 30 minutes of which go to computing the graph’s smoothest modes, while the two trained graph baselines that fit in memory on DGraph need 65 and 69 minutes on a GPU.

Limitations

The method has limits, which the paper reports in full, and the first is that one selection rule was chosen after seeing results. The Weibo and Reddit numbers depend on how the bandwidth γ\gamma of the equilibrium anchor is chosen, and we adopted the current rule after evaluating the first one, under which these two datasets score 92.5 and 48.5 and the count falls to 7 of 11; the paper reports both. The model is also Gaussian, and while heavy-tailed residuals cost at most 0.7 points in a controlled test, a normal population made of two distinct groups costs 9 to 19 points, and binary (0/1) features fall outside the model altogether. Heterophilic graphs remain hard, for on BlogCatalog and ACM EB-GAD trails TAM, and alternative templates did not close the gap. Finally, on networks of users the scores can encode biases of degree or activity, since very active or very connected users may look unusual, so they should be audited across groups of users before they are used for real decisions.

Takeaways

What is usually hidden inside a neural architecture can be written down explicitly, as a template, which says what a node’s neighborhood predicts, and a precision, which says what deviations cost, with knobs whose meanings are plain. Because anomalies are rare, empirical Bayes can set those knobs from unlabeled data and recover a model of normal behavior in closed form, with no training at all, and viewing the fitted Gaussian as the resting state of a relaxation process turns anomaly scoring into a question of steering effort, which yields a whole bank of scores that share the same fitted model and from which simple graph statistics and a preference for stable scores choose, conservatively and without labels. If you work with networks where labels are scarce and decisions need to be explained, we hope EB-GAD is a useful and transparent starting point, and the code is on GitHub.

We thank Block for supporting this work, part of which was carried out while Fred Xu was an intern at Block. This work was partially supported by NSF 2303037, NSF 2312501, NSF 2531008, NSF 2553619, SRC JUMP 2.0 Center, CDSC Industry Partners, Amazon Research Awards, Snapchat, and Google Gifts. The cover figure, the likelihood landscape and the score densities are from the paper; the other figures were made for this post, and the karate-club scores come from the paper’s own pipeline.