The Selection Rule Decides the Winner: A Pre-Registered Audit of Open-Set Graph Anomaly Detection

Farhan Shahriyar Hossain; Taufikur Rahman Fuad; Md Abrar Jahin; Md Rizwan Parvez

cs.LGSep 27, 2026

The Selection Rule Decides the Winner: A Pre-Registered Audit of Open-Set Graph Anomaly Detection

Authors: Farhan Shahriyar Hossain, Taufikur Rahman Fuad, Md Abrar Jahin, Md Rizwan Parvez

Organizations: Islamic University of Technology · University of Southern California · Qatar Computing Research Institute (QCRI)

Abstract

Open-set graph anomaly detection trains on a few labeled anomalies from one class and must also find anomaly classes that were never labeled. Published results share three conventions: the test score is read at the best epoch on the test set, baseline numbers are copied from earlier papers, and most anomalies are minority classes relabeled as anomalous. We ask how much of the reported ranking these conventions decide. We re-run two recent methods, DEMO and NSReg, together with OUTPOST, a small first-order detector built for this study. All three use one protocol with identical seeds and splits on eight graphs (seven for the baselines, which cannot run on ogbn-mag), ten seeds each, and every run is scored under both the best-epoch rule and a deployable validation rule. Before the runs that test them, we registered 40 predictions. Three findings hold. First, the rule changes the leader: under the best-epoch rule, OUTPOST and NSReg each lead three of seven graphs, while under the validation rule, NSReg leads five. Second, the best-epoch bonus depends on how the benchmark was built: 0.045--0.080 AUC-ROC on the three small relabeled-class graphs and 0.002--0.014 on the three real fraud graphs. Third, pseudo-labeling in OUTPOST is worth 0.038--0.065 AUC-ROC on the same three graphs but gives no benefit on any real fraud graph. We also show that a 0.002 tie band for hyperparameter selection lies below the paired standard error on all six graphs tested, even at ten seeds. Twelve of our 40 predictions were falsified, and we report them. We close with a short reporting checklist.

Figures & tables

Semi-synthetic
	Best	Best epoch on test			Best epoch on validation
Graph	published	DEMO	NSReg	OUTPOST	DEMO	NSReg	OUTPOST
Photo	0.902	0.888 $\pm$ .015	0.876 $\pm$ .041	0.870 $\pm$ .024	0.774 $\pm$ .060	0.793 $\pm$ .063	0.791 $\pm$ .048
Computers	0.844	0.778 $\pm$ .015	0.837 $\pm$ .023	0.851 $\pm$ .010	0.727 $\pm$ .013	0.785 $\pm$ .022	0.771 $\pm$ .017
CS	0.945	0.965 $\pm$ .004	0.970 $\pm$ .004	0.984 $\pm$ .002	0.901 $\pm$ .019	0.929 $\pm$ .017	0.939 $\pm$ .014
OGB

Table 1: AUC-ROC over all test anomalies, as mean and standard deviation over ten seeds. Each run is scored at the best epoch on the test set (oracle rule) and at the epoch with the highest validation AUC-ROC (validation rule). On each graph and under each rule, the best of the three methods is bold and the runner-up underlined; the leader changes with the rule on Photo and Computers. The published column, in gray, is the best of sixteen earlier methods as reported by Yu et al. (2026) , from other splits and budgets, and is shown for reference only. Neither baseline runs on ogbn-mag, so its row is unmarked (Appendix C ). AUC-PR is in Table 8 .

	Best epoch on test		Best epoch on valid.
Graph	$-$ DEMO	$-$ NSReg	$-$ DEMO	$-$ NSReg
Photo	$-0.018$	$-0.006$	$+0.017$	$-0.002$
Computers	$+0.073^{*}$	$+0.014^{*}$	$+0.044^{*}$	$-0.014$
CS	$+0.020^{*}$	$+0.014^{*}$	$+0.038^{*}$	$+0.010^{*}$
Yelp	$+0.014^{*}$	$+0.006$	$+0.018^{*}$	$+0.018^{*}$
Amazon	$-0.002$	$-0.005$	$-0.009^{*}$	$-0.012^{*}$

Table 2: OUTPOST minus each baseline in AUC-ROC, paired by seed over ten seeds, under both rules. A star marks a Wilcoxon

p

below 0.05. OUTPOST is significantly ahead of both baselines under both rules on CS, and of DEMO on Computers and Yelp. Win counts and AUC-PR are in Tables 9 and 10 .

	Best epoch on test		Best epoch on valid.
Graph	$-$ DEMO	$-$ NSReg	$-$ DEMO	$-$ NSReg
Photo	$-0.018$	$-0.006$	$+0.017$	$-0.002$
Computers	$+0.073^{*}$	$+0.014^{*}$	$+0.044^{*}$	$-0.014$
CS	$+0.020^{*}$	$+0.014^{*}$	$+0.038^{*}$	$+0.010^{*}$
Yelp	$+0.014^{*}$	$+0.006$	$+0.018^{*}$	$+0.018^{*}$
Amazon	$-0.002$	$-0.005$	$-0.009^{*}$	$-0.012^{*}$

Table 2: OUTPOST minus each baseline in AUC-ROC, paired by seed over ten seeds, under both rules. A star marks a Wilcoxon

p

below 0.05. OUTPOST is significantly ahead of both baselines under both rules on CS, and of DEMO on Computers and Yelp. Win counts and AUC-PR are in Tables 9 and 10 .

Semi-synthetic
Graph	Gate	Conformal	Pseudo-lab.
Photo	$+0.000$	$-0.004$	$-0.038^{\dagger}$
Computers	$-0.001$	$-0.037^{\dagger}$	$-0.065^{\dagger}$
CS	$+0.000$	$-0.005^{\dagger}$	$-0.065^{\dagger}$
Real
Yelp	$+0.001$	$-0.000$	$+0.006^{*}$

Table 3: Change in AUC-ROC when one component of OUTPOST is removed, at the best epoch on test and the development budget (200 epochs on semi-synthetic graphs, 400 elsewhere). A star marks

p<0.05

; a dagger marks a unanimous result at five seeds, where the smallest attainable

p

is 0.0625. Pseudo-labeling carries the semi-synthetic gains, and removing it improves Yelp and T-Finance.

Appendix figures & tables24 assets

Supplementary material from the paper’s appendix.

Appendix

Graph	Nodes	Features	Median deg.	Rotations	Unseen classes	Same-class frac.
Semi-synthetic: classes holding at most 5% of the nodes relabeled as anomalous
Photo	7,650	745	22	2	yes	0.56–0.94
Computers	13,752	767	22	5	yes	0.55–0.94
CS	18,333	6,805	6	8	yes	0.64–1.00
OGB: classes relabeled within a size band, 3–5% for ogbn-arxiv and at most 0.03% for ogbn-mag
ogbn-arxiv	169,343	128	1	4	yes	0.46–0.82

Appendix

Table 4: The eight graphs, grouped by how their anomaly labels were produced. Same-class fraction is the median share of a class node’s neighbors with the same label, given as a range over the graph’s anomaly classes; it uses true labels and serves only as a diagnostic. The median degree of ogbn-mag was not recorded.

			Re-run by us
Method	Graph	Published	Released budget	400 epochs	Difference
DEMO, released budget 200 epochs
DEMO	Photo	0.9023	0.8403	0.8879	$-0.0144$
DEMO	Computers	0.8439	0.7685	0.7782	$-0.0657$
DEMO	CS	0.9448	0.9603	0.9646	$+0.0198$
NSReg, released budget 201 epochs

Appendix

Table 5: Published AUC-ROC against our re-runs of the released code, scored at the best epoch on test, at each method’s released budget and at the 400 epochs used for every method in this study. At 400 epochs, five of seven re-runs exceed the published value: NSReg on all four graphs and DEMO on CS. Most of DEMO’s Photo gap closes with the longer budget.

Unsupervised
	Photo		Computers		CS
Method	AUC-ROC	AUC-PR	AUC-ROC	AUC-PR	AUC-ROC	AUC-PR
ANOMALOUS	0.5574	0.0879	0.5737	0.1693	0.2997	0.1634
DOMINANT	0.4716	0.0837	0.5450	0.1644	0.4029	0.1886
AnomalyDAE	0.4179	0.0770	0.5658	0.1723	0.3978	0.1864
GAAN	0.4346	0.0710	0.5595	0.1796	0.4646	0.2111

Appendix

Table 6: The published field on the three semi-synthetic graphs, transcribed from Yu et al. (2026) , with our three re-run rows below the rule. Transcribed rows come from other splits, budgets, and seed counts, so the two blocks are not comparable with each other; the best and runner-up are therefore marked within each block separately, in bold and underlined.

As published
	Yelp		ogbn-arxiv		ogbn-mag
Method	AUC-ROC	AUC-PR	AUC-ROC	AUC-PR	AUC-ROC	AUC-PR
ConsisGAD	0.6988	0.2970	0.6216	0.3148	0.4909	0.0043
GGAD	0.6613	0.2549	0.6007	0.2843	–	–
TAM	0.5319	0.0977	–	–	–	–
OCGNN	0.6410	0.1118	–	–	–	–

Appendix

Table 7: The published field on the three large graphs, transcribed from Yu et al. (2026) , with our three re-run rows below the rule. As in Table 6 , the best and runner-up are marked within each block separately, because transcribed and re-run values are not comparable with each other. Amazon and T-Finance carry no published open-set values and are omitted. A dash is a value the source does not report, or a run that cannot be made on ogbn-mag (Appendix C ).

Semi-synthetic
	Best	Best epoch on test			Best epoch on validation
Graph	published	DEMO	NSReg	OUTPOST	DEMO	NSReg	OUTPOST
Photo	0.633	0.585 $\pm$ .020	0.590 $\pm$ .059	0.556 $\pm$ .036	0.487 $\pm$ .042	0.506 $\pm$ .058	0.498 $\pm$ .037
Computers	0.646	0.529 $\pm$ .025	0.606 $\pm$ .020	0.652 $\pm$ .009	0.458 $\pm$ .029	0.526 $\pm$ .033	0.532 $\pm$ .034
CS	0.886	0.915 $\pm$ .011	0.934 $\pm$ .007	0.958 $\pm$ .004	0.795 $\pm$ .036	0.855 $\pm$ .034	0.868 $\pm$ .025
OGB

Appendix

Table 8: AUC-PR under the same protocol as Table 1 , as mean and standard deviation over ten seeds. On each graph and under each rule, the best of the three methods is bold and the runner-up underlined. The published column, in gray, is the highest transcribed value; it is DEMO’s on every graph except Yelp, where it is NSReg’s.

	Best epoch on test				Best epoch on validation
	AUC-ROC		AUC-PR		AUC-ROC		AUC-PR
Graph	$\Delta$	Wins, $p$	$\Delta$	Wins, $p$	$\Delta$	Wins, $p$	$\Delta$	Wins, $p$
Photo	$-0.0176$	3, .065	$-0.0291$	1, .037	$+0.0170$	7, .193	$+0.0107$	8, .105
Computers	$+0.0728$	10, .002	$+0.1232$	10, .002	$+0.0441$	10, .002	$+0.0747$	10, .002
CS	$+0.0196$	10, .002	$+0.0419$	10, .002	$+0.0381$	10, .002	$+0.0732$	10, .002
Yelp	$+0.0138$	9, .019	$+0.0320$	10, .002	$+0.0180$	9, .027	$+0.0334$	9, .004

Appendix

Table 9: OUTPOST minus DEMO on every graph both methods run, paired by seed over ten seeds and scored under both rules. Wins are seeds on which OUTPOST is ahead; there were no ties. At ten paired seeds, the smallest attainable Wilcoxon

p

is 0.002.

	Best epoch on test				Best epoch on validation
	AUC-ROC		AUC-PR		AUC-ROC		AUC-PR
Graph	$\Delta$	Wins, $p$	$\Delta$	Wins, $p$	$\Delta$	Wins, $p$	$\Delta$	Wins, $p$
Photo	$-0.0057$	5, .769	$-0.0346$	5, .232	$-0.0015$	6, .922	$-0.0081$	5, .846
Computers	$+0.0140$	9, .014	$+0.0466$	10, .002	$-0.0140$	2, .065	$+0.0065$	6, .492
CS	$+0.0141$	10, .002	$+0.0238$	10, .002	$+0.0095$	8, .027	$+0.0131$	6, .232
Yelp	$+0.0060$	8, .105	$+0.0214$	8, .019	$+0.0178$	9, .027	$+0.0328$	8, .019

Appendix

Table 10: OUTPOST minus NSReg, on the same seeds and in the same form as Table 9 . NSReg is the stronger of the two baselines under the validation rule, and CS and Yelp are the only graphs on which OUTPOST leads it under both rules.

Graph	Against	$\Delta$	Wins, $p$	$\Delta$	Wins, $p$	$\Delta$	Wins, $p$	$\Delta$	Wins, $p$
		Best epoch on test				Best epoch on validation
		AUC-ROC		AUC-PR		AUC-ROC		AUC-PR
Photo	DEMO	$-0.0126$	3, .232	$-0.0035$	4, .625	$+0.0291$	7, .193	$+0.0031$	6, .275
	NSReg	$-0.0044$	5, .625	$-0.0496$	3, .105	$-0.0036$	6, 1.00	$-0.0146$	5, .557
Computers	DEMO	$+0.0873$	10, .002	$+0.1681$	10, .002	$+0.0537$	10, .002	$+0.0979$	10, .002
	NSReg	$+0.0183$	9, .014	$+0.0716$	10, .002	$-0.0173$	2, .065	$+0.0110$	6, .432

Appendix

Table 11: The same paired comparison restricted to anomalies of classes never seen in training. The three real graphs are binary and have no unseen class, so they do not appear. Wins are out of ten seeds.

	Best epoch on test			Best epoch on validation
Graph	DEMO	NSReg	OUTPOST	DEMO	NSReg	OUTPOST	Order changes?
Photo	1	2	3	3	1	2	yes
Computers	3	2	1	3	1	2	yes
CS	3	2	1	3	2	1	no
Yelp	3	2	1	3	2	1	no
Amazon	2	1	3	2	1	3	no

Appendix

Table 12: Where each method is placed on each graph by mean AUC-ROC over all test anomalies, under each rule: 1 is best, 3 is worst. The underlying means are in Table 1 ; only the order is given here, because the order is what the selection rule changes. It changes on Photo and on Computers, and nowhere else.

	Best epoch on test			Best epoch on validation
Graph	DEMO	NSReg	OUTPOST	DEMO	NSReg	OUTPOST	Order changes?
Photo	1	2	3	3	1	2	yes
Computers	3	2	1	3	1	2	yes
CS	3	2	1	3	2	1	no
ogbn-arxiv	3	1	2	3	1	2	no

Appendix

Table 13: The same placings computed over unseen classes only, on the four graphs that have unseen classes and on which all three methods run. The rule decides the order on two of the four, the same two as in Table 12 .

Semi-synthetic
	All anomalies		Unseen classes only
Graph	AUC-ROC	AUC-PR	AUC-ROC	AUC-PR
Photo	$+0.0789$ $\pm$ .0374	$+0.0580$ $\pm$ .0270	$+0.1779$ $\pm$ .0769	$+0.0844$ $\pm$ .0301
Computers	$+0.0795$ $\pm$ .0168	$+0.1197$ $\pm$ .0360	$+0.0972$ $\pm$ .0195	$+0.1617$ $\pm$ .0435
CS	$+0.0453$ $\pm$ .0144	$+0.0895$ $\pm$ .0250	$+0.0506$ $\pm$ .0155	$+0.1113$ $\pm$ .0276
OGB

Appendix

Table 14: The oracle bonus of OUTPOST on each graph, the gain from reading the test metric at the best epoch on test rather than at the best epoch on validation, as mean and standard deviation over ten seeds. Over all anomalies, the bonus is 3 to 35 times larger on the semi-synthetic graphs than on the real ones, and in AUC-ROC it is larger still on unseen classes.

Graph	Seeds	Total advantage	Survives validation	Collected by the oracle	Share	$p$
Photo	10	$+0.0382$	$+0.0147$	$+0.0235$	62%	0.193
Computers	5	$+0.0645$	$+0.0365$	$+0.0280$	43%	0.062
CS	5	$+0.0648$	$+0.0362$	$+0.0285$	44%	0.062
Yelp	10	$-0.0058$	$-0.0067$	$+0.0008$	–	0.027
Amazon	10	$+0.0023$	$+0.0024$	$-0.0001$	–	0.770

Appendix

Table 15: The advantage of full OUTPOST over the variant with pseudo-labeling and the gate removed, split into the part that survives the validation rule and the part only the oracle rule collects. On the semi-synthetic graphs, 43 to 62 percent of the apparent benefit is of the second kind. Runs are at each graph’s development budget (200 epochs on Photo, Computers, and CS; 400 elsewhere).

Graph	Epochs	Seeds	OUTPOST	DEMO	$\Delta$	Wins, $p$	$\Delta$	Wins, $p$
					AUC-ROC		AUC-PR
Photo	200	10	0.8374	0.8403	$-0.0029$	3, .557	$-0.0022$	3, .557
Photo	400	10	0.8703	0.8879	$-0.0176$	3, .065	$-0.0291$	1, .037
Computers	200	5	0.8214	0.7685	$+0.0529$	5, .062	$+0.0880$	5, .062
Computers	400	10	0.8510	0.7782	$+0.0728$	10, .002	$+0.1232$	10, .002
CS	200	5	0.9832	0.9603	$+0.0228$	5, .062	$+0.0469$	5, .062

Appendix

Table 16: OUTPOST against DEMO at DEMO’s released budget of 200 epochs and at the 400 epochs used throughout, scored at the best epoch on test and paired by seed. On Photo, the two tie at 200 epochs, and DEMO is ahead at 400.

Graph	Epochs	Arms	kept	validation	the test set	Difference
			Default	Test AUC-ROC of the arm chosen by
Photo	200	14	yes	0.8367	0.8532	$+0.0166$
Photo	400	14	yes	0.8703	0.8867	$+0.0164$
Computers	200	11	yes	0.8193	0.8261	$+0.0068$
Computers	400	11	yes	0.8485	0.8527	$+0.0042$
CS	200	11	yes	0.9838	0.9841	$+0.0003$

Appendix

Table 17: Validation-only tuning of OUTPOST, using three selection seeds and a tie band of 0.002. All arms are averaged over the same three selection seeds, so values differ from the ten-seed means in Table 1 . The last column is what choosing the best arm on the test set instead would have added; contrary to registered prediction P30, it does not grow with the training budget.

Graph	kept	the tie band	spread	released	selected	oracle	validation
	Released	Arms inside	Validation	Validation AUC-ROC		Change on test
Photo	no	1 of 4	0.0037	0.8573	0.8679	$+0.0106$	$+0.0118$
Computers	yes	4 of 4	0.0008	0.8339	0.8339	$+0.0000$	$+0.0000$
Yelp	yes	1 of 4	0.0058	0.7488	0.7488	$+0.0000$	$+0.0000$
Amazon	no	2 of 4	0.0044	0.9553	0.9600	$+0.0047$	$+0.0225$

Appendix

Table 18: The same tuning rule applied to NSReg over a grid of learning rate against weight decay, at three seeds. CS is excluded because the sweep was too expensive there. Where the rule leaves the released configuration, it makes the baseline stronger at three seeds; Table 19 re-tests these selections at ten.

Method	Graph	Validation margin		Test	Wins, $p$	Outcome
		3 seeds	10 seeds	difference
OUTPOST	Amazon	$+0.0057$	$-0.0004$	$-0.0040$	1, .004	reverses
NSReg	Photo	$+0.0037$	$+0.0008$	$-0.0009$	4, .625	falls inside the tie band
NSReg	Amazon	$+0.0044$	$+0.0057$	$+0.0054$	9, .006	holds, and was adopted

Appendix

Table 19: The three tuning decisions that departed from the default and were then re-tested at ten seeds. A margin is a difference in validation AUC-ROC between the selected and the default arm; the test column is the same difference measured on test, paired by seed. Wins are seeds, out of ten, on which the selected arm is ahead. Two of the three reverse or vanish once the seed count is raised.

Graph	Arm pairs	of the difference	3 seeds	10 seeds	for 0.002
		Standard deviation	Standard error at		Seeds needed
Photo	1,076	0.0073	0.0042	0.0023	14
Computers	371	0.0077	0.0044	0.0024	15
CS	140	0.0094	0.0054	0.0030	23
Yelp	633	0.0134	0.0077	0.0042	45
Amazon	217	0.0066	0.0038	0.0021	11

Appendix

Table 20: Noise in the statistic that the tuning rule reads. For each graph, we take every pair of arms of one method that share seeds, and report the spread of their paired difference in validation AUC-ROC. The last column is the number of seeds at which that spread would fall inside the 0.002 tie band. T-Finance rests on 15 pairs and is an order-of-magnitude estimate only.

Graph	Variant	Seeds	$\Delta$	Wins, $p$	$\Delta$	Wins, $p$
			AUC-ROC		AUC-PR
Photo	atlas gate off	5	$+0.0003$	2, 1.00	$-0.0002$	2, 1.00
Photo	pseudo-labeling off	5	$-0.0377$	0, .062	$-0.0192$	0, .062
Photo	conformal $\to$ fixed 0.95	5	$-0.0037$	2, .312	$+0.0028$	3, .438
Photo	gate and pseudo-labeling off	10	$-0.0381$	0, .002	$-0.0223$	1, .004
Photo	anomaly synthesis off	5	$+0.0183$	5, .062	$+0.0074$	4, .188

Appendix

Table 21: Every ablation we ran, paired by seed against the full model at each graph’s development budget (200 epochs on Photo, Computers, and CS; 400 elsewhere), as the variant minus the full model. A row that says “on” switches on a component that is off by default; HopMix and the spectral gate are the two components we tested and rejected. Wins are seeds on which the variant is ahead, out of the stated number; the only ties are two Yelp conformal cells. At five paired seeds, the smallest attainable

p

is 0.062.

		Best epoch on test			Best epoch on validation
Graph	Seeds	on	off	$\Delta$ , wins, $p$	on	off	$\Delta$ , wins, $p$
Photo	10	0.8703	0.8701	$-0.0002$ , 6, .769	0.7914	0.7860	$-0.0053$ , 4, .492
Computers	10	0.8510	0.8495	$-0.0016$ , 5, .625	0.7715	0.7709	$-0.0006$ , 3, .492
CS	10	0.9842	0.9842	$+0.0001$ , 6, .375	0.9389	0.9374	$-0.0014$ , 1, .037
Yelp	10	0.7448	0.7454	$+0.0005$ , 5, .625	0.7425	0.7418	$-0.0007$ , 3, .322
Amazon	10	0.9534	0.9532	$-0.0002$ , 3, .322	0.9420	0.9464	$+0.0043$ , 7, .105

Appendix

Table 22: The atlas gate removed, at the 400-epoch protocol of the main results;

\Delta

is off minus on. At the best epoch on test, nothing approaches significance, and the largest movement is 0.0016. Under the validation rule, removing the gate costs 0.0014 on CS (

p=0.037

); no other cell is significant.

	Median	Nodes above		AUC-ROC		AUC-PR
Graph	degree	the budget	Seeds	$\Delta$	Wins	$\Delta$	Wins
ogbn-arxiv	1	4.3%	5	$-0.0004$	2	$+0.0008$	3
CS	6	5.1%	5	$+0.0005$	4	$+0.0025$	5
Photo	22	43.8%	5	$-0.0586$	0	$-0.0321$	0
Computers	22	45.0%	5	$+0.0053$	3	$-0.0131$	0
Yelp	168	95.2%	10	$+0.0263$	10	$+0.0504$	10

Appendix

Table 23: SimSample switched on minus switched off, by graph, ordered by median degree; wins are out of the stated seeds. We had registered that it would help where node degree exceeds the first-hop budget of 25 and hurt below it. Photo, Yelp, and T-Finance fit that account; CS and ogbn-arxiv, which are below the budget but unaffected, and Amazon, the densest graph, which is harmed, do not.

Graph	Class	Frac.	Best AUC	Gain	Graph	Class	Frac.	Best AUC	Gain
Photo	0	0.938	0.912	$+0.268$	ogbn-arxiv	8	0.750	0.684	$+0.192$
Photo	7	0.556	0.556	$-0.095$	ogbn-arxiv	10	0.462	0.617	$+0.066$
Computers	0	0.800	0.793	$+0.310$	ogbn-arxiv	34	0.737	0.665	$+0.105$
Computers	3	0.597	0.759	$+0.271$	ogbn-mag	2	0.000	0.580	$+0.177$
Computers	5	0.940	0.924	$+0.482$	ogbn-mag	39	0.143	0.629	$+0.135$
Computers	6	0.550	0.384	$+0.053$	ogbn-mag	143	1.000	0.874	$+0.076$

Appendix

Table 24: The training-free diagnostic on all 37 anomaly classes. Same-class fraction is the median share of a class node’s neighbors carrying the same label. Best AUC is the highest AUC-ROC, the diagnostic reaches over propagation depths zero to three, and gain is the AUC at depth three minus the AUC at depth zero, so a negative value means propagation made the class harder to find. The 37 classes are split into two columns to fit the page.

Held-out graph	Classes	fitted line	training mean	Lower error
		Mean absolute error
Photo	1	0.0763	0.2184	line
Computers	5	0.1011	0.1770	line
CS	2	0.1433	0.2850	line
ogbn-arxiv	4	0.1181	0.0475	training mean
ogbn-mag	9	0.4084	0.1809	training mean

Appendix

Table 25: Leaving one graph out and predicting its classes from the line fitted to the rest, against the alternative of predicting the training mean. The line wins on the three semi-synthetic graphs and loses on both OGB graphs and on the pooled error, so it describes the classes it was fitted to rather than predicting new ones. The 16 classes that propagation does not help are excluded: for 13 of them, the best AUC equals the AUC without propagation by construction, so that the branch carries no predictive content.

	Trainable parameters			OUTPOST relative to		Peak memory
Graph	OUTPOST	DEMO	NSReg	DEMO	NSReg	vs. DEMO
Semi-synthetic
Photo	114,113	725,819	118,274	0.157 $\times$	0.965 $\times$	0.872 $\times$
Computers	116,929	763,329	121,090	0.153 $\times$	0.966 $\times$	0.811 $\times$
CS	889,793	47,648,399	893,954	0.019 $\times$	0.995 $\times$	0.655 $\times$
OGB

Appendix

Table 26: Trainable parameters counted on the trained models, and peak GPU memory of OUTPOST against DEMO measured in the same process setting. OUTPOST is the smallest of the three on every graph. Against DEMO, the margin is large throughout; against NSReg, it is large only on the three graphs with observed fraud labels, where the input dimension is small.

ID	Prediction	Outcome
P1	Anomaly classes differ in same-class fraction, feature dissimilarity, and Dirichlet energy	superseded
P2	Within a class, same-class fraction correlates with the detection score at the best depth	superseded
P3	Propagation gain is positive for clustered classes and negative for scattered ones	superseded
P4	Real fraud (Yelp) has a lower same-class fraction than every relabeled class	corrected: false with ogbn-mag
P5	ogbn-mag: OUTPOST stays below 0.60 AUC-ROC and does not clearly exceed the published field	split
P6	ogbn-arxiv: competitive with the published field, not above it by more than seed noise	confirmed

Appendix

Table 27: All 40 predictions, each committed to version control before the runs that test it, with the outcome. Seventeen were confirmed, twelve falsified, three split, and one null; the remaining seven were superseded, corrected, or hold only in part. Several of the falsified ones concern our own method or our own explanations, and each changed the text of this paper.

Explore similar work

Graph Anomaly Detection as Finite-Horizon Control: Training-Free Scoring via Empirical Bayes
Sep 29, 2026Fred Xu, Thomas Markovich, Florence Regol +1Generalist Graph Anomaly Detection Anomaly Score
University of California, Los Angeles · Block · Mila – Quebec AI Institute
Can We Predict Anomaly Detection Performance from Embedding-Space Geometry?
Sep 22, 2026Kevin Wilkinghoff, Zheng-Hua TanArea Under The Receiver Operating Characteristic Curve Detection Performance
Department of Electronic Systems, Aalborg University, Denmark · Pioneer Centre for Artificial Intelligence, Denmark
Dual Spatial-Temporal Attribution: Architecture-Aligned Post-Hoc Explainability for Recurrent Graph Anomaly Detection
Aug 12, 2026Iyad Assaad Nekka, Hamida Seba, Khaled Walid Hidouci +1Generalist Graph Anomaly Detection Graph Representations
LCSI Laboratory, National Higher School of Computer Science (ESI), Algiers, Algeria · Université Claude Bernard Lyon 1, Lyon, France

Sep 29, 2026, cs.LGJ/K move · Enter open · S save

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

Fred Xu, Thomas Markovich, Florence Regol, Yizhou Sun

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

Generalist Graph Anomaly Detection Anomaly Score Graph Anomaly Detection Log-Ratio-Based Gaussian Trust Weight Empirical Bayes Training-Free

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

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

Can We Predict Anomaly Detection Performance from Embedding-Space Geometry?

Dual Spatial-Temporal Attribution: Architecture-Aligned Post-Hoc Explainability for Recurrent Graph Anomaly Detection