Graph Anomaly Detection as Finite-Horizon Control: Training-Free Scoring via Empirical Bayes

Fred Xu; Thomas Markovich; Florence Regol; Yizhou Sun

cs.LGSep 29, 2026

Graph Anomaly Detection as Finite-Horizon Control: Training-Free Scoring via Empirical Bayes

Authors: Fred Xu, Thomas Markovich, Florence Regol, Yizhou Sun

Organizations: University of California, Los Angeles · Block · Mila – Quebec AI Institute

Abstract

Node-level graph anomaly detection (GAD) identifies nodes whose attributes and interactions deviate from dominant graph regularities. Existing GAD models encode normality and anomaly scoring indirectly through architectures, message passing, reconstruction or contrastive objectives, and tuned score families. This entangles graph trust (how strongly graph structure should define normality), graph-spectral weighting, and anomaly-score choice, yielding scores that are costly, opaque, and unstable across graph regimes. We propose EB-GAD (Empirical-Bayes GAD), a training-free framework that models normality as graph-aware generalized Ornstein-Uhlenbeck (GOU) relaxation toward a graph-filtered template. Empirical Bayes fits the graph precision from the residual-field likelihood; the GOU then turns scoring into a closed-form finite-horizon control energy, the minimum effort to steer a feature-neutral node to its observed endpoint along graph-spectral relaxation. Sweeping relaxation horizon and endpoint tolerance yields a bank of scores that share one fitted prior: equilibrium Mahalanobis scoring is one limit, while finite-horizon control-energy and scale-normalized ratio scores reveal anomalies that static equilibrium scoring can mask. A label-free selector chooses the score family from feature homophily, edge density, and feature dimension, then ranks candidates by fitted-null deviation and rank stability. On 11 benchmarks and without labels at any step, EB-GAD has the best or tied-best AUROC on 9: the four financial fraud networks (up to 3.7M nodes), the YelpChi and Amazon review graphs, Weibo, Reddit and Facebook, with margins of up to 21.7 points. It is second on BlogCatalog and ACM.

Figures & tables

Figure 1 : EB-GAD overview. (a) A graph-aware GOU around template $\mathbf{m}$ defines finite-horizon Gaussian transitions from a feature-neutral start. (b) Residual-space empirical Bayes fits $(\rho,\kappa)$ for each template bandwidth $\gamma$ without labels ( $d$ in (b) is the feature dimension $D$ ). (c) The fitted dynamics produce control-energy scores $C_{\Gamma,\lambda_{c}}$ , $CR_{\Gamma,\lambda_{c}}$ and equilibrium scores $J^{\star},R$ ; a fixed selector routes each dataset to one of four score families.

Dataset	LOF	DIF	ANOM.	DOMINANT	AnomDAE	CONAD	CoLA	DiffGAD	TAM	EB-GAD
Weibo	$57.9$	$38.2\,{\scriptstyle\pm\,1.8}$	$\underline{94.5}\,{\scriptstyle\pm\,0.0}$	$85.0\,{\scriptstyle\pm\,14.6}$	$91.5\,{\scriptstyle\pm\,1.2}$	$85.4\,{\scriptstyle\pm\,14.3}$	$28.1\,{\scriptstyle\pm\,0.0}$	$93.4\,{\scriptstyle\pm\,0.3}$	$70.9\,{\scriptstyle\pm\,0.0}$	$\mathbf{95.1}$
Reddit	$57.2$	$53.5\,{\scriptstyle\pm\,1.4}$	$54.9\,{\scriptstyle\pm\,5.6}$	$56.0\,{\scriptstyle\pm\,0.2}$	$55.7\,{\scriptstyle\pm\,0.4}$	$56.1\,{\scriptstyle\pm\,0.1}$	$\underline{60.3}\,{\scriptstyle\pm\,0.7}$ ∗	$56.3\,{\scriptstyle\pm\,0.1}$	$60.2\,{\scriptstyle\pm\,0.4}$ ∗	$\mathbf{60.6}$
Amazon	$47.4$	$\underline{77.1}\,{\scriptstyle\pm\,2.5}$	$44.6\,{\scriptstyle\pm\,0.3}$ ∗	$60.0\,{\scriptstyle\pm\,0.4}$ ∗	$64.6\,{\scriptstyle\pm\,7.1}$	$55.5\,{\scriptstyle\pm\,1.6}$	$59.0\,{\scriptstyle\pm\,0.8}$ ∗	$55.9\,{\scriptstyle\pm\,0.1}$	$70.6\,{\scriptstyle\pm\,1.0}$ ∗	$\mathbf{78.0}$
YelpChi	$\underline{57.2}$	$56.0\,{\scriptstyle\pm\,0.9}$	$49.6\,{\scriptstyle\pm\,0.3}$ ∗	$41.3\,{\scriptstyle\pm\,1.0}$ ∗	$56.6\,{\scriptstyle\pm\,2.6}$	$28.7\,{\scriptstyle\pm\,0.2}$	$46.4\,{\scriptstyle\pm\,0.1}$ ∗	$29.1\,{\scriptstyle\pm\,0.0}$	$56.4\,{\scriptstyle\pm\,0.7}$ ∗	$\mathbf{71.7}\,{\scriptstyle\pm\,0.6}$
BlogCatalog	$68.6$	$57.4\,{\scriptstyle\pm\,2.1}$	$56.5\,{\scriptstyle\pm\,2.5}$ ∗	$75.9\,{\scriptstyle\pm\,1.0}$ ∗	$74.7\,{\scriptstyle\pm\,0.0}$	$68.7\,{\scriptstyle\pm\,0.0}$	$77.5\,{\scriptstyle\pm\,0.9}$ ∗	$76.6\,{\scriptstyle\pm\,0.0}$	$\mathbf{82.5}\,{\scriptstyle\pm\,0.3}$ ∗	$\underline{78.6}$
Facebook	$47.7$	$37.8\,{\scriptstyle\pm\,2.8}$	$90.2\,{\scriptstyle\pm\,0.5}$ ∗	$56.8\,{\scriptstyle\pm\,0.2}$ ∗	$54.7\,{\scriptstyle\pm\,0.6}$	$14.2\,{\scriptstyle\pm\,1.5}$	$84.3\,{\scriptstyle\pm\,1.1}$ ∗	$28.0\,{\scriptstyle\pm\,4.7}$	$\mathbf{91.4}\,{\scriptstyle\pm\,0.8}$ ∗	$\mathbf{91.4}$

Table 1 : AUROC (%) on 11 GAD benchmarks. Bold : best; underline : second; OOM = out of memory. Baselines use their native anomaly-score direction (Appendix Table 4 ). Cell sources: ∗ published in the TAM benchmark [ 25 ] ; † published by the baseline’s authors (out of memory on our hardware); unmarked baseline cells are our runs with published hyperparameters. For truncated spectra (YelpChi, Elliptic, Elliptic++, DGraph, T-Finance) EB-GAD is the mean

\pm

standard deviation over five node orders (Appendix C.1 ).

	Weibo	Reddit	Amazon	YelpChi	BlogCat.	Facebook	ACM	Elliptic	Ell.++	DGraph	T-Fin.
Family	anchor	anchor	energy	anchor	energy	profile	ratio	anchor	anchor	anchor	profile
Equilibrium	95.1	60.6	77.9	71.7	78.4	87.8	81.3	74.5	72.5	66.8	80.1
Selected	95.1	60.6	78.0	71.7	78.6	91.4	86.0	74.5	72.5	66.8	84.8
$\Delta$	$0.0$	$0.0$	$+0.1$	$0.0$	$+0.2$	$+3.6$	$+4.7$	$0.0$	$0.0$	$0.0$	$+4.7$

Table 2 : Contribution of the finite horizon: AUROC (%) of the selected score against the equilibrium score (

J^{\star}

R

, by NullKS) of the same configuration (operator, template, bandwidth, PCA, truncation, EB fit). Family : the family the selector routes to; for an anchor the two rows coincide.

Appendix figures & tables24 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	#Nodes	#Edges	#Feat	Anom.%
Standard benchmarks (Table 1 )
Weibo	8,405	407,963	400	4.1
Reddit	10,984	168,016	64	3.3
Amazon	11,944	4,398,392	25	6.9
YelpChi	45,954	3,846,979	32	4.9
BlogCatalog	5,196	171,743	8,189	5.8

Appendix

Table 3 : Raw benchmark statistics for graph datasets used in Table 1 . #Feat = feature dimension; Anom.% = anomaly rate (%).

Dataset	Baseline	Native AUROC	Oracle-flipped AUROC	Mean score normal/anomaly
Elliptic	DIF	$22.1{\pm}0.9$	$77.9{\pm}0.9$	$0.335/0.303$
Elliptic++	DIF	$22.6{\pm}0.5$	$77.4{\pm}0.5$	$0.334/0.303$
Elliptic	DiffGAD	$27.1{\pm}0.4$	$72.9{\pm}0.4$	$20.90/13.31$
Elliptic++	DiffGAD	$27.9{\pm}7.8$	$72.1{\pm}7.8$	$967.09/417.67$

Appendix

Table 4 : Score-orientation audit for sub-50 baselines whose oracle sign reversal could affect the fraud-dataset comparison. Native AUROC uses the method’s fixed label-free anomaly-score direction and is the only value used in Table 1 . Oracle-flipped AUROC is computed from the negated score after labels are known and is diagnostic only.

Dataset	Template	$k$	$\rho$	$\kappa$	$\gamma$	PCA	Rule	Selected family (score)
Weibo	low-pass	all	1.000	1	0.5	64	7	equilibrium anchor ( $J^{\star}$ )
Reddit	low-pass	all	1.000	1	2	no	5	equilibrium anchor ( $R$ )
Amazon	low-pass	all	0.458	0.5	5	no	5	control energy (top-2 $C_{\Gamma,\lambda_{c}}$ fusion)
YelpChi	low-pass	500	1.000	20	1	no	5	equilibrium anchor ( $J^{\star}$ )
BlogCatalog	affinity	all	1.000	1	0.18	48	2	control energy (stability-ranked $C_{\Gamma,\lambda_{c}}$ fusion)
Facebook	low-pass	all	0.727	3	0.7	64	6	profile aggregation (scale-entropy)

Appendix

Table 5 : Label-free EB-GAD configuration behind each cell of Table 1 . Template : low-pass Matérn or feature-affinity-weighted (§ B.4 ).

k

: number of retained low-frequency Laplacian eigenpairs (“all” = full spectrum).

\rho,\kappa,\gamma

: EB-fitted graph trust and Matérn inverse length-scale, and the template bandwidth of the selected score (the anchor bandwidth

\gamma_{a}

for an anchor, the likelihood-selected bandwidth for a profile, the pool rule for control energy and ratio). PCA : retained PCA dimensions. Rule : the ordered rule of § B.4 that fires.

Dataset	$h$	$d_{e}$	$D_{x}$	$k/n$	NullKS( $J^{\star}$ )	NullKS( $R$ )	BJ	NullKS(profile)	$\pi$
Weibo	0.068	24.27	400	all	0.663	0.156	78.5	0.258	0.786
Reddit	0.993	7.65	64	all	0.945	0.138	57.6	0.206	0.878
Amazon	0.644	17.18	25	all	0.277	0.071	236.2	0.208	0.740
YelpChi	0.876	2.07	32	$2.10{\times}10^{-2}$	0.000	0.000	1225.2	0.334	0.024
BlogCatalog	0.009	33.25	8189	all	0.673	0.089	169.9	0.246	0.077
Facebook	0.375	25.49	576	all	0.036	0.044	8.3	0.227	0.811

Appendix

Table 6 : Unlabeled quantities read by the selector.

h

: cosine feature homophily over a fixed sample of edges,

d_{e}

: edges per node of the graph operator,

D_{x}

: raw feature dimension,

k/n

: truncation ratio. Diagnostics of the EB-fitted run: NullKS of its two equilibrium scores, Berk–Jones statistic (BJ) and NullKS of the profile score, and the two-groups mixture mass

\pi

Quantity	Class	Source or tested range
$(\rho,\kappa)$ ; $\gamma$ within its grid	model-derived	maximum of the residual-space likelihood (Alg. 1 )
$J^{\star}$ , $R$ , $C_{\Gamma,\lambda_{c}}$ , $CR_{\Gamma,\lambda_{c}}$	model-derived	closed forms of § 3.3
plug-in nulls of the scores	model-derived	chi-squared laws under the fitted prior
Kolmogorov–Smirnov, Berk–Jones	canonical	[ 2 ]
ACAT, minimum- $p$ , mean $-\log p$ combiners	canonical	[ 20 ] ; Fisher’s method
two-groups mixture of $p$ -values	canonical	[ 8 ]

Appendix

Table 7 : Provenance of every quantity that enters a score or the selection. Model-derived : follows from the fitted model. Canonical : a standard statistic or combiner, with citation. Default : an implementation default, fixed once and identical on all datasets, with the sensitivity study that covers it.

Figure 2 : Top: residual-space log-likelihood over

(\rho,\kappa)

of the EB-fitted run (likelihood-selected bandwidth

\gamma^{\star}=0.7

) for Weibo and Facebook (values below the 35th percentile are clipped for display). Dashed curve: profile path

\rho^{\star}(\kappa)

; star: selected optimum on the

\kappa

grid. The likelihood is concave in

\rho

(Remark 1 ) with dataset-dependent structure in

\kappa

. Bottom: Newton iterates for

\rho

at the selected

\kappa^{\star}

Figure 3 : Density of the selected EB-GAD score for normal and anomalous nodes on four datasets (original node order). Scores are shown on their rank scale, so a method at chance would give two flat densities.

	Weibo	Reddit	Amazon	YelpChi	BlogCat.	Facebook	ACM	Elliptic	Ell.++	DGraph	T-Fin.
$\gamma_{a}$	0.5	2	1	1	0.2	0.5	0.7	1	2	1	0.2
$J^{\star}$	95.1	62.0	75.8	71.7	54.0	47.4	75.6	58.3	30.2	60.5	81.6
$R$	47.3	60.6	48.2	64.6	61.0	89.7	72.1	74.5	72.5	66.8	80.1
Table 1	95.1	60.6	78.0	71.7	78.6	91.4	86.0	74.5	72.5	66.8	84.8

Appendix

Table 8 : Equilibrium anchor: AUROC (%) of

J^{\star}

and

R

at the anchor bandwidth

\gamma_{a}

(the grid value nearest to

\gamma_{0}

) with the EB fit of

(\rho,\kappa)

at that bandwidth. Bold : the score chosen without labels (larger NullKS; ties go to

J^{\star}

; rule 1 of § B.4 fixes

R

on sparse truncated graphs). Last row: the score selected in Table 1 .

Dataset	ANOM.	DOMINANT	AnomDAE	CONAD	CoLA	DiffGAD	TAM	EB-GAD (CPU)
Weibo	78	63	1	95	130	134	858	84
Reddit	38	35	2	57	8	110	5,467	136
Amazon	25	37	153	308	14	106	10,739	708
YelpChi	170	185	1,152	1,359	5	118	5,106	27
BlogCatalog	447	430	92	3,047	18	3,272	8,764	675
Facebook	3	20	9	56	3	118	479	8

Appendix

Table 9 : Wall-clock time (seconds). Baselines: training and inference on one NVIDIA A100 GPU, as measured for the submitted version. EB-GAD: the complete run behind its cell of Table 1 on 16 CPU threads, from loading the data to the selected score: eigendecompositions in double precision for every template bandwidth of the grid, EB fits, all score families of the run and the label-free selection. The two columns use different hardware and are not a controlled comparison. OOM = out of memory.

Dataset	Training-free	Best trained encoder	Gap
Weibo	95.1	95.7 (MLP)	$-0.6$
Reddit	60.6	58.9 (MLP)	$+1.7$
Amazon	78.0	60.3 (MLP)	$+17.7$
YelpChi	71.7	68.0 (SAGE)	$+3.7$
BlogCatalog	78.6	77.6 (MLP)	$+1.0$
Facebook	91.4	95.4 (MLP)	$-4.0$

Appendix

Table 10 : Training-free EB-GAD (Table 1 ) against the better of two trained encoders (MLP, GraphSAGE), chosen per dataset by AUROC, followed by the same score formula. AUROC (%); gap = training-free minus trained.

Dataset	Spectrum	Orders	min	max	std	Spearman
Weibo	full	2	95.12	95.12	0.00	1.0000
Reddit	full	2	60.56	60.56	0.00	0.9995
Amazon	full	2	78.05	78.05	0.00	1.0000
YelpChi	truncated	5	70.72	72.65	0.62	0.8368
BlogCatalog	full	2	78.62	78.62	0.00	1.0000
Facebook	full	2	91.40	91.40	0.00	1.0000

Appendix

Table 11 : Relabeling gate for the scores of Table 1 . The model is equivariant to node relabeling, so the selected score must not depend on the node order. Orders : number of node orders run (the original and random relabelings). AUROC (%): smallest, largest and standard deviation over the orders. Spearman: rank correlation of the selected score between the original order and one relabeling.

		ties by node index		averaged ties
Dataset	Score	released	relabeled	released	relabeled	node index
YelpChi	profile, mixture posterior	93.7	60.3	67.3	66.8	94.4
	profile, mean $-\log p$	93.5	60.6	68.7	68.3
	profile, ACAT	92.8	61.9	69.3	69.8
	$J^{\star}$	70.9	70.7	70.9	70.7
	$R$	64.2	64.0	64.2	64.0

Appendix

Table 12 : The ordering artifact. AUROC (%) of the profile scores and of the equilibrium scores on YelpChi and Facebook, in the released node order and after a random relabeling, with the tie-breaking of the submitted version (ties ordered by node index) and with averaged ties. The equilibrium scores involve no rank step. Last column: AUROC of the node index itself.

Dataset	Protocol	Anchor, likelihood	Anchor, averaged	Nullspace dropped	Jacobian
Weibo	95.1	92.5	95.3	95.2	92.5
Reddit	60.6	48.5	60.7	60.4	61.9
Amazon	78.0	=	=	76.5	=
YelpChi	70.7	=	64.0	–	69.1
BlogCatalog	78.6	=	=	72.0	=
Facebook	91.4	=	=	90.8	85.8

Appendix

Table 13 : Sensitivity of Table 1 to four conventions (original node order, AUROC %; “=”: same score and value; “–”: not applicable, truncated spectra keep all computed modes; n/a: not run). Anchor, likelihood : the anchor uses the bandwidth with the largest residual-space likelihood, as in the submitted Algorithm 1 . Anchor, averaged : the anchor is the mean percentile rank of the equilibrium score over the three bandwidths of the grid. Nullspace dropped : Laplacian null modes are excluded from the modeled subspace on the full-spectrum datasets. Jacobian : every bandwidth, including the anchor’s, maximizes the likelihood with the term

D\sum_{j}\log\max(t_{j},10^{-12})

of the residual map

t_{j}=1-(\gamma^{2}+\lambda_{j})^{-1}

, which excludes bandwidths whose map is negative on a computed mode. The ordered rules and the within-family scores are unchanged.

Dataset	$\gamma_{0}$	$\gamma$ : AUROC (removed share), in increasing $\gamma$
Weibo	0.36	0.2: 95.6 (0)	0.5: 95.1 (59)	0.7: 92.5 ℓ (86)
Reddit	1.49	0.7: 48.5 ℓ (89)	1: 51.8 (87)	2: 60.6 (39)
Amazon	0.87	0.5: 53.5 (12)	0.7: 63.8 ℓ (79)	1: 75.8 (77)
YelpChi	1.38	0.7: 63.3 (0)	1: 70.9 ℓ (3)	2: 69.1 (1)
BlogCatalog	0.28	0.1: 44.9 (22)	0.2: 61.0 (92)	0.5: 74.8 ℓ (95)
Facebook	0.55	0.5: 47.4 (67)	0.7: 87.8 ℓ (86)	1: 85.9 (77)

Appendix

Table 14 : Template bandwidth.

\gamma_{0}

: graph-statistic center of the grid. For every bandwidth

\gamma

of a dataset’s grid: AUROC (%) of the equilibrium score chosen by NullKS after the EB fit at that bandwidth (low-pass template;

R

on Elliptic, Elliptic++ and DGraph, where rule 1 fixes it) and, in parentheses, the share (%) of the feature energy that the residual map removes (0 when the residual has more energy than the features; the shares are small on truncated spectra, where the map acts on the computed modes only). Bold : the anchor bandwidth

\gamma_{a}

(grid value nearest to

\gamma_{0}

on the log scale). ℓ : the bandwidth with the largest residual-space likelihood, used by the finite-horizon families. The AUROC values are diagnostics; no rule reads them. Original node order.

Method	Weibo	Reddit	Amazon	YelpChi	BlogCat.	Facebook	ACM	Elliptic	Ell.++	DGraph	T-Fin.
LOF	$7.0$	$4.1$	$6.7$	$7.0$	$24.7$	$2.1$	$14.6$	$10.2$	$8.5$	$0.9$	$3.2$
DIF	$3.9$	$3.7$	$15.4$	$6.4$	$7.4$	$1.8$	$3.5$	$6.0$	$6.1$	$\underline{1.9}$	$3.2$
ANOMALOUS	$\underline{34.6}$	$3.9$	$5.6$ ∗	$5.2$ ∗	$6.5$ ∗	$19.0$ ∗	$6.4$ ∗	OOM	OOM	OOM	$4.8$
DOMINANT	$22.0$	$3.7$	$14.2$ ∗	$4.0$ ∗	$31.0$ ∗	$3.1$ ∗	$\underline{44.0}$ ∗	$5.3$	$7.4$	OOM	$\underline{6.6}$
AnomalyDAE	$30.9$	$3.1$	$10.5$	$6.7$	$\underline{36.7}$	$2.7$	$27.0$	$5.4$	$6.0$	OOM	$3.1$
CONAD	$22.8$	$3.7$	$10.8$	$3.3$	$11.1$	$1.3$	$11.3$	$5.3$	$7.3$	n/a	$\underline{6.6}$

Appendix

Table 15 : AUPRC (%) for the comparison of Table 1 . Bold : best; underline : second. ∗ : published in the TAM benchmark [ 25 ] , used exactly where Table 1 follows that benchmark; other baseline cells are our runs. OOM = out of memory; n/a = out of memory and the published report gives AUROC only. EB-GAD cells are the AUPRC of the score selected without labels in Table 1 .

Dataset	GOU-EB	GOU fixed	heat	polynomial	identity
Weibo	92.5 (92.7)	92.0 (92.7)	85.9 (92.5)	80.1 (91.4)	92.7 (92.7)
Reddit	48.2 (55.8)	48.3 (55.9)	48.6 (57.4)	51.5 (56.3)	48.2 (48.2)
Amazon	62.9 (67.7)	62.9 (67.8)	50.8 (67.4)	69.7 (70.1)	62.8 (62.8)
YelpChi	69.1 (71.3)	69.1 (71.3)	66.1 (70.5)	68.7 (70.5)	68.7 (70.5)
BlogCatalog	78.2 (78.5)	78.2 (78.5)	78.3 (78.3)	77.6 (77.6)	78.5 (78.5)
Facebook	80.0 (88.0)	79.8 (88.0)	91.6 (92.8)	80.9 (87.7)	48.1 (62.0)

Appendix

Table 16 : Isolation of the spectral precision family. Operator, template, PCA, truncation, residuals and the label-free selection (largest NullKS) are fixed per dataset; only the precision changes. AUROC (%) of the selected score, with the best member of the family by AUROC in parentheses (a diagnostic, not a result). Bold : best selected score of the row. GOU-EB: EB-fitted GOU precision with its finite-horizon members; GOU fixed:

\rho=0.5

\kappa=1

; heat:

\exp(t\lambda/\lambda_{\max})

, 8 scales; polynomial:

(c+\lambda)^{p}

, 6 configurations; identity: graph-free residual energy.

Dataset (type)	Equilibrium	Finite, selected	Finite, best	$\Delta$ selected	$\Delta$ best
Weibo ( $J^{\star}$ )	95.1	95.1	95.1	$+0.0$	$+0.0$
Reddit ( $R$ )	60.6	60.6	60.6	$+0.0$	$+0.0$
Amazon ( $J^{\star}$ )	77.9	78.0	78.1	$+0.1$	$+0.2$
YelpChi ( $J^{\star}$ )	70.7	70.7	70.7	$+0.0$	$+0.0$
BlogCatalog ( $J^{\star}$ )	78.4	78.4	78.6	$+0.0$	$+0.2$
Facebook ( $R$ )	87.8	87.8	88.0	$+0.0$	$+0.2$

Appendix

Table 17 : Matched single-score comparison at the configuration and EB fit of Table 5 , shared by both sides. Equilibrium :

J^{\star}

R

, whichever has the larger NullKS (

R

where rule 1 fixes it). Finite : a single hard-endpoint score of the same type (

C_{\Gamma,\infty}

against

J^{\star}

CR_{\Gamma,\infty}

against

R

) at one finite horizon

\Gamma\in\{0.02,\dots,50\}

, with no tolerance grid, fusion or aggregation; NullKS picks the horizon, and the best horizon by AUROC is reported as a diagnostic. AUROC (%).

Cutoff	Factor	Dataset	Selection	before	after	change
$d_{e}<1$ (rule 1)	$\times 0.5$	Elliptic++	anchor ( $R$ ) $\to$ anchor ( $J^{\star}$ )	72.5	30.3	$-42.2$
$d_{e}<1$ (rule 1)	$\times 0.5$	DGraph	anchor ( $R$ ) $\to$ anchor ( $J^{\star}$ )	66.8	60.5	$-6.3$
$D_{x}\leq 256$ (rule 1)	$\times 0.5$	Elliptic++	anchor ( $R$ ) $\to$ anchor ( $J^{\star}$ )	72.5	30.3	$-42.2$
$D_{x}>1000$	$\times 0.5$	Facebook	profile ( entropy ) $\to$ anchor ( $J^{\star}$ )	91.4	47.4	$-44.0$
$d_{e}\geq 20$	$\times 1.5$	Facebook	profile ( entropy ) $\to$ anchor ( $J^{\star}$ )	91.4	47.4	$-44.0$
$h<0.25$	$\times 0.5$	ACM	ratio ( aff. ) $\to$ anchor ( $J^{\star}$ )	86.0	75.6	$-10.4$

Appendix

Table 18 : Cutoff sensitivity of the ordered rules. Each of the 21 cutoffs is multiplied by

0.5

0.75

1.25

and

1.5

, one at a time, and the rules are re-evaluated on the 11 datasets (231 evaluations per factor). The table lists every evaluation in which the selected family or branch changes, with the AUROC (%) before and after (original node order).

Dataset	Bank	NullKS	stability	tail-stab.	corr-stab.	rule	best
Weibo	equilibrium	95.1	74.7	90.8	89.6	95.1	95.1
Reddit	equilibrium	60.6	62.9	62.8	62.9	60.6	62.9
YelpChi	equilibrium	68.7	67.9	70.7	70.7	70.7	70.7
Facebook	two-groups	17.6	25.5	91.4	69.4	91.4	91.4
Elliptic	equilibrium	74.4	67.2	58.4	67.4	74.4	74.4
Elliptic++	equilibrium	30.3	52.3	30.3	54.5	72.5	72.5

Appendix

Table 19 : Ingredients of the within-family rule

A(r)

on the datasets routed to an equilibrium or profile bank (original node order). AUROC (%) of the member picked by quality only (NullKS), by stability only, by the two combined variants (tail-stability, correlation-stability), by the rule used in Table 1 , and the best member of the bank by AUROC (a diagnostic). The equilibrium bank contains

J^{\star}

R

and their rank aggregates; the rule restricts it to

J^{\star}

and

R

Dataset	Scores	Selector	Best single	Stacked (CV)	Gap
Weibo	224	95.1	95.1	95.2	$+0.1$
Reddit	224	60.6	62.0	64.9	$+4.3$
Amazon	887	78.0	78.1	78.3	$+0.3$
YelpChi	158	70.7	73.0	74.9	$+4.2$
BlogCatalog	4391	78.6	78.7	79.5	$+0.9$
Facebook	224	91.4	91.4	92.3	$+0.9$

Appendix

Table 20 : Supervised bound on combining the scores. Every score of a dataset’s pool is rank-transformed and a logistic regression is fitted on the labels with 5-fold cross-validation; the out-of-fold AUROC (%) bounds what a label-driven linear combination of our scores could reach. Selector : the label-free pick of Table 1 (original node order). Best single : best member of the pool by AUROC.

Dataset	Injected	Total contamination	Fitted $(\rho,\kappa)$	Original anomalies	Injected anomalies
Weibo	$+0\%$	4.1%	(0.697, 3)	92.5	–
Weibo	$+5\%$	9.1%	(0.710, 3)	92.0	57.1
Weibo	$+10\%$	14.1%	(0.720, 3)	92.1	57.2
Weibo	$+20\%$	24.1%	(0.737, 3)	91.4	56.1
Reddit	$+0\%$	3.3%	(0.910, 3)	48.3	–
Reddit	$+5\%$	8.3%	(0.997, 3)	48.3	79.9

Appendix

Table 21 : Contamination. Contextual anomalies (feature swaps with random nodes) are injected on top of the real anomalies, EB is refitted on the contaminated graph and the score is selected without labels (largest NullKS over the finite-horizon bank). AUROC (%) on the original anomalies and on the injected ones (against untouched normal nodes).

Residual distribution	Selected	Best member	Fitted $\rho$
Gaussian (control)	96.3 / 95.7 / 95.5	98.8 / 98.1 / 97.6	0.05 / 0.05 / 0.05
Student- $t$ , 3 d.o.f.	95.6 / 95.7 / 95.3	97.4 / 97.5 / 96.8	0.05 / 0.05 / 0.05
two-component mixture	80.2 / 86.7 / 76.2	87.0 / 91.6 / 82.7	0.05 / 0.05 / 0.05
binarized	59.3 / 56.1 / 56.4	60.8 / 58.1 / 61.1	0.05 / 0.05 / 0.05
binarized, bit-flip anomalies	59.1 / 60.5 / 59.4	63.4 / 60.9 / 63.7	0.05 / 0.05 / 0.05

Appendix

Table 22 : Misspecification stress test on stochastic block model graphs (

n=3000

, four blocks, edge probabilities

0.02

within and

0.002

between blocks,

D=16

5\%

injected attribute anomalies, three seeds). The normal signal is a low-pass graph signal plus noise whose distribution is varied; the pipeline, grids and label-free selection are identical in every column. AUROC (%) of the selected score and of the best member of the bank (a diagnostic), and the fitted graph trust, per seed.

Placement	Selected, seeds 0–4	Range	Best member, range
scattered	79.9 / 81.3 / 82.7 / 80.5 / 83.0	79.9–83.0	79.9–83.0
connected groups of at most 10	92.8 / 92.2 / 93.6 / 92.9 / 92.0	92.0–93.6	92.0–93.6

Appendix

Table 23 : Neighboring anomalies on Reddit.

5\%

of the nodes receive a feature swap, either scattered over the graph or as connected groups of at most 10 neighbors; EB is refitted on each contaminated graph and the score is selected without labels. AUROC (%) of the injected nodes against untouched normal nodes, per seed.

Edge score	Seeds 0–4	Range
smaller endpoint energy	95.9 / 96.0 / 94.4 / 96.7 / 94.4	94.4–96.7
standardized cross-term	83.0 / 84.0 / 77.5 / 83.4 / 80.2	77.5–84.0

Appendix

Table 24 : Pairwise readout on the connected-group runs of Table 23 . Every undirected edge is scored and edges that join two injected nodes are ranked against edges that join two untouched normal nodes. AUROC (%) per seed.

Explore similar work

May 8, 2026cs.LG

GAD in the Wild: Benchmarking Graph Anomaly Detection under Realistic Deployment Challenges

Graph Anomaly Detection (GAD) is a critical task in graph machine learning with vital applications in financial fraud detection and social platform governance. However, existing GAD benchmarks are often restricted to small-scale, curated graphs with relatively balanced anomaly ratios, leaving a substantial gap between academic evaluation and real-world deployment. To bridge this gap, we present a multi-dimensional benchmark that systematically evaluates GAD models under three deployment-relevant challenges: million-scale graphs, extreme anomaly scarcity, and missing node attributes. We derive a family of controlled benchmark variants from five diverse graphs, including two native industrial-scale datasets with over 3.7 million nodes. Our extensive evaluation of nine representative GAD models reveals three major limitations: (1) most GNN-based methods fail to scale to million-node graphs due to prohibitive memory requirements; (2) detection performance drops sharply under realistic anomaly ratios (e.g., 0.1%), often resulting in zero recall; and (3) reconstruction-based models are highly sensitive to attribute imputation strategies. Our findings suggest that strong performance in laboratory settings does not guarantee robustness in production environments. We release this benchmark and empirical evaluation as a diagnostic testbed to promote the development of robust and scalable GAD systems for large-scale, imperfect graphs encountered in practice. Code is available at https://anonymous.4open.science/r/Benchmark_GAD-E7A3.

Jingjing Zhou, Shiyu Huang, Qing Qing +7

Zhejiang Gongshang University · Jilin University · Adelaide University +2

Generalist Graph Anomaly Detection Graph Anomaly Detection Acyclic Graphs

Ask PDF

Apr 17, 2026cs.LG

NK-GAD: Neighbor Knowledge-Enhanced Unsupervised Graph Anomaly Detection

Graph anomaly detection aims to identify irregular patterns in graph-structured data. Most unsupervised GNN-based methods rely on the homophily assumption that connected nodes share similar attributes. However, real-world graphs often exhibit attribute-level heterophily, where connected nodes have dissimilar attributes. Our analysis of attribute-level heterophily graphs reveals two phenomena indicating that current approaches are not practical for unsupervised graph anomaly detection: 1) attribute similarities between connected nodes show nearly identical distributions across different connected node pair types, and 2) anomalies cause consistent variation trends between the graph with and without anomalous edges in the low- and high-frequency components of the spectral energy distributions, while the mid-part exhibits more erratic variations. Based on these observations, we propose NK-GAD, a neighbor knowledge-enhanced unsupervised graph anomaly detection framework. NK-GAD integrates a joint encoder capturing both similar and dissimilar neighbor features, a neighbor reconstruction module modeling normal distributions, a center aggregation module refining node features, and dual decoders for reconstructing attributes and structures. Experiments on seven datasets show NK-GAD achieves an average 3.29% AUC improvement.

Zehao Wang, Lanjun Wang

College of Intelligence and Computing, Tianjin University, Tianjin, China · School of New Media and Communication, Tianjin University, Tianjin, China

Generalist Graph Anomaly Detection Graph Anomaly Detection Text-Attributed Graph Gnn-Based Detectors Unsupervised Neighbors

Ask PDF

May 26, 2026cs.LG

DDGAD: Disagreement-Driven Graph Anomaly Detection via Adapt-Then-Combine

Graph anomaly detection (GAD) commonly relies on message passing to jointly encode node attributes and neighborhood context. However, once the two are mixed, an abnormal post-encoding state may reflect either an intrinsic node deviation or incompatible contextual influence, making its source ambiguous. We propose Disagreement-Driven Graph Anomaly Detection (DDGAD), which treats persistent incompatibility between node-wise and contextual estimates as anomaly evidence. Inspired by Adapt-Then-Combine (ATC), DDGAD reverses its consensus objective: Adapt produces a node-wise estimate without new same-step neighbor aggregation, while Combine forms a neighborhood-dependent contextual estimate, and their pre-consensus disagreement is accumulated across ATC steps for detection. We further characterize this signal from graph-spectral and source-response perspectives and derive sufficient conditions for anomaly--normal separation under contextual mixing. Experiments on six benchmarks show the highest average AUROC among the evaluated methods, while controlled interventions and Adapt-operator controls further support persistent disagreement as an effective detection signal.

Yuxin Yang, Limei Hu, Feng Chen

College of Artificial Intelligence Southwest University Chongqing, China

Generalist Graph Anomaly Detection Graph Anomaly Detection Trajectory Generation

Ask PDF