acceptodds
Desk rejected at ICLR 2027

Who Gets the Risk? Unified Multiscale Optimal Transport for Graph Anomaly Detection

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

Label-free graph anomaly detection (GAD) aims to identify anomalous nodes without annotations. Yet anomaly patterns vary across graph domains, structures, and attribute regimes, making node-level evidence difficult to remain consistent across graphs. Moreover, existing methods typically map or aggregate label-free proxies into node scores that jointly determine risk positions and node assignment, leaving the valid scope of evidence implicit. To address these challenges, we propose Multiscale Optimal Transport for Graph Anomaly Detection (LORE), a unified framework designed for label-free graph anomaly detection. LORE reformulates graph anomaly detection as an evidence-guided risk allocation problem by constructing a graph-adaptive risk prior and incorporating label-free node evidence to establish the correspondence between node evidence and risk positions. It further leverages multiscale optimal transport to reassign risks across different granularities, thereby correcting initial anomaly rankings. We evaluate LORE on over 30 graphs. LORE achieves strong performance on primary benchmarks, scales favorably to large graphs, and mechanism analyses further support its evidence-guided risk-allocation design.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Anomaly Detection, Label-free Learning, Optimal Transport, Risk Allocation, Self-supervised Learning, Multiscale Learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_e7yxOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper presents LORE, a label-free framework for graph anomaly detection that frames node anomaly detection as an evidence-guided risk-allocation problem. The method constructs a graph-adaptive prior from six hand-crafted anomaly charts and derives two self-supervised, node-level evidence signals. It applies two optimal transport procedures to refine node rankings locally and within the high-risk tail, respectively. Experiments on the evaluated datasets report improvements over the baselines.

Critical strengths
  1. Experiments show improvements on the given datasets compared to the given baselines.
  2. The risk-allocation interpretation is intuitive.
Critical weaknesses
  1. The OT component appears close to sorting, which weakens the novelty. Both OT problems use one-dimensional scalar evidence, uniformly weighted one-dimensional targets, equal source/target masses, and squared Euclidean cost. In this setting, the claim of "multiscale optimal transport" seems overstated.
  2. Most of the empirical gain appears to come from the handcrafted prior, not the proposed OT mechanism, as shown in Table 4. The six-chart prior achieves almost all of the AP, while the entire proposed risk-reallocation machinery adds only a little.
  3. The prior contains several manually chosen structural assumptions and numerical constants without a clear selection protocol.
  4. The scalability evidence is incomplete. The authors should analyze the computational cost, including memory and time, for datasets such as T-Social.
Questions for authors
  1. How are the hyperparameters, such as kappa, lamabda are selected on new datasets?
  2. Please report ablations of the six prior charts and controller.
  3. How robust is the soft-normal-reference mechanism when the initial prior is badly inverted or anomaly prevalence is very high?
2 comments

We sincerely thank the reviewer for the careful and expert reading.

W1: OT and sorting

Computationally, each stage admits an exact sorting solution within its support. Sorting is the solver, while OT is the model, which fixes which reranking is admissible: evidence only permutes existing risk positions inside a prior cell (resolution KK) or the tail (mass mm), the two scales of "multiscale", and never moves risk across supports. Conditional OT alone reaches 0.2978 macro AP on Main-10, Partial OT alone 0.3063, and both 0.3161 (Table 4). Given the same inputs, tuned fusion reaches only 0.3034 and oracle fusion 0.3116 (see our response to Reviewer NnTV).

W2: Contribution of reassignment

Reassignment improves the prior on all 50 Main-10 graph–seed pairs, by 2.3× on Enron and 38% on Disney (Table 4). Where the prior fails, OT lifts macro AP from 0.2971 to 0.5195 (Table 6). Results with SCAN, OddBall, or Radar as the prior under the same OT (AP):

GraphSCAN+OTOddBall+OTRadar+OT
Books0.02070.07540.02450.08110.02690.0522
Weibo0.06250.16380.08690.33830.26850.3784
Reddit0.02830.03460.03700.05040.04920.0544
Disney0.09560.30930.07040.21370.05470.3022
Enron0.00030.00060.00060.00120.00030.0011
Mine.0.20050.25070.19960.25620.22820.2735
Tol.0.21290.24990.29680.29880.17950.2146
Quest.0.02270.03230.05660.06260.04380.0457
Amazon0.17590.29330.14750.24630.34160.4136
Yelp0.15390.19530.15100.21870.23630.2457
Macro0.09730.16050.10710.17670.14290.1981

OT improves every prior on every graph, by 39–65% in macro AP, so the gain is not tied to our prior.

W3 and Q2: Prior design and ablation

The charts, constants, and controller were fixed on Main-10 and applied unchanged to all other graphs. Prior AP of the controller, single charts, a uniform mixture, and the label-selected oracle chart:

GraphSelectedControllerOracle chartChart 1Chart 2Uniform
Books4+60.11710.1070 (4)0.04960.01910.0413
Weibo20.84140.8414 (2)0.74470.84140.6803
Reddit60.05030.0503 (6)0.03330.02660.0314
Disney10.24980.2498 (1)0.24980.07350.0567
Tolokers50.38570.3856 (5)0.21850.26120.2412
Amazon30.54470.5449 (3)0.47250.32260.5363
Yelp60.25180.2518 (6)0.16690.16680.1917
ACM20.81190.8119 (2)0.03340.81190.1498
BlogCatalog20.34680.3468 (2)0.07480.34680.2671
BITalpha2+60.44880.4722 (2)0.07870.47220.1237
Wiki40.02580.0260 (4)0.01970.01670.0181
PubMed-SAMCL20.75270.7527 (2)0.04330.75270.1028
Cora-Syn.20.66900.6690 (2)0.03450.66900.0767
CiteSeer-Syn.20.77710.7771 (2)0.03380.77710.1035
PubMed-Syn.20.73270.7327 (2)0.06240.73270.1321

The controller closely matches the oracle chart, while no fixed chart or uniform mixture works across graphs. This includes the last eight graphs, which never entered prior development.

W4: Computational cost

One complete scoring run on one RTX 4090:

GraphPrior (s)Views (s)OT (s)Total (s)Host (GB)GPU (GB)
Elliptic29.36.90.236.42.83.1
T-Finance102.55.90.7109.16.36.7
T-Social15.752.2104.3172.27.45.0

Q1: Hyperparameters on new datasets

The prior is frozen with no per-graph tuning, so only the OT configuration is selected. λ=(λc,λf)\lambda=(\lambda_c,\lambda_f) is the direction of κlin\kappa_{\mathrm{lin}}, selected with κ\kappa, K∈[2,4096]K\in[2,4096], and m∈(0,1/2]m\in(0,1/2] by seed-1 AP and frozen for seeds 2–5. The gain is insensitive to KK and mm (Figure 12).

Q3: Robustness of the normal reference

We retrained the evidence views under three references (AP):

GraphAnomaly ratePrior(1−p)2(1-p)^2 (ours)Uniformp2p^2 (inverted)
ACM0.0360.81050.84690.81410.7847
BlogCatalog0.0580.34720.40110.37730.3569
BITalpha0.0930.44910.70990.63650.4203
Wiki0.0240.02580.02820.02760.0282
Cora-SAMCL0.0550.80000.81120.81180.8072
CiteSeer-SAMCL0.0450.86960.89550.87210.8673
PubMed-SAMCL0.0300.75270.78100.79160.7885
Cora-Syn.0.0500.66120.67230.67500.6590
CiteSeer-Syn.0.0500.77700.82090.79990.7159
PubMed-Syn.0.0500.73270.79460.80620.7936
Macro–0.62260.67620.66120.6222

Our reference improves every graph, and even an inverted reference keeps the macro AP at the prior level, since evidence cannot move risk across supports. At high prevalence, it still lowers anomaly contamination, from 20.0% to 14.6% on Minesweeper and from 21.8% to 13.4% on Tolokers, raising AP from 0.3014 to 0.3553 and matching the prior, respectively. Like every label-free detector, LORE assumes its signal ranks anomalies above normal nodes, so a globally inverted prior would be inherited. Our prior satisfies this on all 20 graphs (AUROC > 0.5).

We thank the reviewer again and would be glad to clarify anything further.

Thank you again for your feedback. we would be grateful to know whether our responses address your concerns, and we would be glad to discuss any remaining questions in the time left.

Reviewer_drcaOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes LORE, a label-free graph anomaly detection framework that combines a multi-view prior, self-supervised evidence, and support-restricted reranking. It constructs an initial anomaly ranking from graph structure and node attributes, then uses learned evidence to reassign risk positions within restricted supports. Its main contribution is a novel decision mechanism for anomaly ranking.

Critical strengths

1.The paper introduces a clear mechanism for controlling the scope within which anomaly evidence can influence rankings. The ablation results show that the initial ranking itself contributes substantially to overall performance, while the OT-based reassignment has low computational complexity. Together, these components provide a concrete approach to exploiting evidence that is locally informative but globally unreliable.

2.The experiments are relatively comprehensive and provide targeted empirical support for the proposed mechanism. In particular, the authors investigate the sources of improvement by shuffling node–evidence correspondence, matching the magnitude of ranking perturbations, and corrupting evidence outside the permitted support.

Critical weaknesses

1.Key configurations and their label-free selection procedure are insufficiently specified. The paper does not clearly report the actual values and selection criteria for the number of risk cells KK, the tail mass ratio mm, and the evidence mappings κloc\kappa_{\mathrm{loc}} and κtail\kappa_{\mathrm{tail}}. These choices directly affect node rankings and the scope of evidence application. This omission limits reproducibility and makes it difficult to assess whether the reported cross-graph results can be obtained through a fully specified label-free selection procedure.

2.The initial prior is a strong component, but its construction is complex and involves numerous handcrafted choices. Although the ablations establish improvements over the prior, the contribution of its individual design choices is not sufficiently disentangled. Consequently, it remains unclear how much of the overall advantage comes from the carefully designed prior and how much comes from a broadly transferable risk-reassignment mechanism.

Questions for authors

1.According to Equations (13) and (15), one-dimensional, equal-mass OT with squared-distance cost can be solved exactly through sorted monotone matching. Is the complete method therefore equivalent to reranking within prior-risk cells, followed by reranking within a high-risk subset? Moreover, when there are no ties, rank normalization produces an essentially fixed set of risk values. Could the authors clarify what the “graph-adaptive risk structure” specifically represents and what additional properties the OT formulation provides beyond this support-restricted reranking procedure?

2.How were the six prior charts, gating reference values, fixed coefficients, and stick-breaking order determined? Are these choices identical across all evaluation graphs, and were they frozen before evaluation? Please also clarify which components of the complete LORE framework remain fixed and which require retraining or reconfiguration on a new graph. This would help establish which reusable mechanisms account for its cross-graph performance.

2 comments

We sincerely thank the reviewer for the careful reading and constructive comments.

W1: Configurations and selection

Selected configurations on Main-10:

BooksWeiboRedditDisneyEnronMine.Tol.Quest.AmazonYelp
κloc\kappa_{\mathrm{loc}}linlinminradradlinlinlinlinmin
KK3492338432307216129294851
κtail\kappa_{\mathrm{tail}}–linopplinlinopplinlinjointjoint
mm–1/221/10241/81/20481/121/2241/641/961/42

Additional-10:

ACMBlog.BITa.WikiCora-SCite-SPub-SCora-SynCite-SynPub-Syn
κloc\kappa_{\mathrm{loc}}maxlinmaxlinlinlinmaxlinlinlin
KK484834764876484832
κtail\kappa_{\mathrm{tail}}jointmaxmaxrad––minminlinlin
mm1/401/1281/21/8––1/961/641/321/32

κ\kappa (Appendix A.3), K∈[2,4096]K\in[2,4096], and m∈(0,1/2]m\in(0,1/2] are selected by seed-1 AP and frozen for seeds 2–5, and scoring uses no labels. Per-dataset settings are common in label-free GAD (e.g., GEL, ADA-GAD, and DiffGAD release per-dataset hyperparameter files), and fusion tuned by the same protocol stays below LORE on 9/10 graphs. We further scaled KK and mm independently from 0.5× to 2× of the selected values, 25 settings per graph:

GraphSettings (of 25) improving on all seedsGain range
Minesweeper25+0.031 to +0.050
Yelp23−0.001 to +0.007
BlogCatalog25+0.008 to +0.049
BITalpha25+0.118 to +0.299

The gain holds in 98 of 100 settings on every seed, so the gain does not hinge on a finely tuned configuration.

W2: Prior versus reassignment

To disentangle the prior, we compared the controller, with its activated charts under Selected, against single charts, a uniform mixture, and the label-selected oracle chart in parentheses (prior AP):

GraphSelectedControllerOracle chartChart 1Chart 2Uniform
Books4+60.11710.1070 (4)0.04960.01910.0413
Weibo20.84140.8414 (2)0.74470.84140.6803
Reddit60.05030.0503 (6)0.03330.02660.0314
Disney10.24980.2498 (1)0.24980.07350.0567
Tolokers50.38570.3856 (5)0.21850.26120.2412
Amazon30.54470.5449 (3)0.47250.32260.5363
Yelp60.25180.2518 (6)0.16690.16680.1917
ACM20.81190.8119 (2)0.03340.81190.1498
BlogCatalog20.34680.3468 (2)0.07480.34680.2671
BITalpha2+60.44880.4722 (2)0.07870.47220.1237
Wiki40.02580.0260 (4)0.01970.01670.0181
PubMed-SAMCL20.75270.7527 (2)0.04330.75270.1028
Cora-Syn.20.66900.6690 (2)0.03450.66900.0767
CiteSeer-Syn.20.77710.7771 (2)0.03380.77710.1035
PubMed-Syn.20.73270.7327 (2)0.06240.73270.1321

Using only graph statistics, the controller closely matches the oracle chart, while no fixed chart works across graphs. The prior's strength comes from graph-adaptive chart selection, not one handcrafted chart. Reassignment, in turn, improves the prior on all 50 Main-10 graph–seed pairs (Table 4) and the same OT also improves SCAN, OddBall, and Radar used as priors on every Main-10 graph (see our response to Reviewer e7yx). Both components contribute.

Q1: Relation to sorting

Computationally, each stage admits an exact sorting solution within its support, so LORE can be implemented as reranking within prior cells and then within the tail. Sorting is the solver, while OT is the model. Since ranks fix the set of risk values, the "graph-adaptive risk structure" refers to the support structure induced by the prior, i.e., which nodes share a cell and which form the tail, not to the values themselves. The OT formulation specifies which reranking is admissible: evidence only permutes ownership of existing positions inside a support, never creating risk or moving it across supports. This constraint is what matters. At matched rank displacement, Partial OT outperforms score fusion (Figure 3), and fusion with the same inputs stays below LORE (see our response to Reviewer NnTV). The formulation also extends to unequal masses or multi-dimensional evidence, where sorting no longer applies.

Q2: Fixed and per-graph components

The six charts, reference values, coefficients, and stick-breaking order were set on Main-10 during development and then frozen. They are identical for all graphs, use no dataset identity, and were applied unchanged to Additional-10, the large graphs, and the unseen graphs. These graphs never entered prior development and thus serve as held-out tests. On them the controller still closely matches the oracle chart (W2), the frozen prior ranks first in macro AP (Table 5), and LORE is best on every graph (Tables 2 and 9). On a new graph, the prior is computed directly, the two evidence views are retrained without labels, and only the OT configuration is selected (W1).

We thank the reviewer again and would be glad to clarify anything further.

The authors' response addressed my concerns, and I have decided to keep my initial score.

Reviewer_NnTVOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes LORE, a label-free graph anomaly detection framework that reformulates anomaly ranking as evidence-guided risk allocation. It constructs a graph-adaptive risk prior and uses self-supervised anomaly evidence with Conditional and Partial Optimal Transport to reassign nodes to risk positions at different granularities. Experiments across more than 30 graph datasets compare LORE with existing methods and examine its scalability, component contributions, and behavior when the initial risk prior is unreliable. The results demonstrate strong ranking performance and provide empirical support for the proposed risk-allocation mechanism.

Critical strengths
  • A potentially useful methodological perspective. Separating the initial risk structure from evidence-guided node assignment offers a reasonable alternative to directly combining anomaly scores, particularly when evidence reliability varies across graph contexts.

  • Broad empirical evaluation and mechanism analysis. Experiments across diverse datasets, together with component ablations and analyses of prior failures and support-dependent evidence, provide substantial empirical support for the method beyond aggregate performance comparisons.

Critical weaknesses
  • The motivation and problem formulation are not sufficiently intuitive. Although the paper identifies variability in anomaly evidence as a key challenge, the subsequent argument that coupling risk positions with node assignment constitutes a fundamental limitation of existing label-free GAD methods is not developed intuitively enough. Direct score-based ranking is not inherently problematic when anomaly scores are reliable, and existing score-fusion or rank-aggregation approaches may also address heterogeneous evidence. A clearer explanation and stronger evidence are needed to establish why the proposed decoupling is necessary rather than simply an alternative formulation.

  • The practical interpretation of anomaly scores may be overstated. The paper frames its output as an anomaly-risk ranking, but the scores produced by a label-free anomaly detector do not necessarily represent calibrated estimates of actual anomaly risk. Improvements in AP and AUROC demonstrate better ranking performance against benchmark labels, but do not establish that the resulting scores can be interpreted as absolute risk levels or directly support practical risk assessment. The paper should clarify this distinction and more carefully qualify the practical implications of its results.

Questions for authors

Please check the above weaknesses.

2 comments

We sincerely thank the reviewer for the careful reading and the constructive comments.

W1: Why decoupling is necessary

Direct score-based ranking is adequate when a proxy is reliable over the whole graph. LORE targets the common case where label-free evidence is reliable only on part of a graph, while a single score can apply only one global trust level to it. We conducted two experiments to examine this.

First, we measured the AUROC of LORE's tail evidence over the full graph, inside the high-risk tail support, and inside the same support after shuffling node–evidence correspondence:

WeiboRedditDisneyEnronMine.Tol.Quest.AmazonYelp
Full graph0.1550.4700.6060.5570.4650.4360.4050.1800.388
Inside tail0.7910.9250.7850.8330.6760.7270.7760.6080.752
Shuffled0.5030.4930.5120.4860.5010.4890.4990.4980.498

The same evidence is weak or even reversed over the full graph on most graphs, yet markedly more discriminative inside the tail on every graph, and shuffling returns it to chance. On Weibo, for example, a global score must either impose the reversed ordering (0.155) on all nodes or suppress a signal reaching 0.791 inside the tail. Its reliability is therefore support-dependent, not a global property.

Second, we gave standard combiners exactly the same inputs pp, uu, and vv as LORE, without retraining or reconfiguration. Tuned fusion selects its weights on seed 1 and freezes them as LORE does, and oracle fusion re-selects them for every graph–seed pair with test labels:

MethodBooksWeiboRedditDisneyEnronMine.Tol.Quest.AmazonYelpMacro
Prior pp0.11710.84150.05030.25000.04640.30140.38570.05740.54500.25200.2847
Direct R(v)R(v)0.04620.05870.03380.29120.00050.18110.18960.02280.03900.11220.0975
Fusion (α=0.25)0.09060.43280.04230.20250.00140.36810.34370.03720.22120.18450.1924
Fusion (α=0.5)0.07200.12480.03650.18170.00090.31210.28890.02800.07090.13780.1254
Borda agg.0.07200.50390.03460.29380.00070.23800.25660.05740.04950.12170.1628
E-value agg.0.09080.60410.03980.37600.00560.22310.26110.04360.09070.14040.1875
Tuned fusion0.14480.84770.05250.31350.04640.36800.38570.05940.55690.25890.3034
Oracle fusion0.14580.84790.05280.38390.04640.36860.38570.05940.56620.25900.3116
LORE0.15260.85420.05630.34430.10640.35010.38780.07200.57760.25940.3161

Every fixed fusion or aggregation rule falls below the prior, and tuned fusion recovers only by shrinking the evidence weight to at most 0.15. LORE exceeds tuned fusion on 9/10 graphs, exceeds even the oracle in macro AP, and is the only method improving over the prior on every graph. This is consistent with the paper, where Partial OT outperforms score fusion at matched rank displacement (Figure 3) and shuffling node–evidence correspondence removes 91.4% of the gain (Figure 4). The benefit comes from where evidence may reassign risk, not from how scores are weighted.

W2: Interpretation of the outputs as "risk"

In LORE, "risk" denotes an ordinal position in the graph-derived rank measure (Section 3.1). By design, the output is an inspection-priority ranking whose value lies in the order it assigns. This is the standard output of label-free GAD and exactly what AP and AUROC assess for all methods. To examine its practical value, we measured the fraction of anomalies recovered when inspecting the top 1%, 5%, and 10% of nodes ranked by LORE, with the best of SCAN, OddBall, and Radar per graph as reference:

BudgetBooksWeiboRedditDisneyEnronMine.Tol.Quest.AmazonYelpMacro
1%0.1070.0970.0310.1670.4000.0370.0330.0670.1330.0470.112
5%0.2140.4650.1280.3330.4000.1310.1220.1640.4610.1240.254
10%0.3930.7370.1840.5000.4000.2030.2070.2530.6080.2250.371
5%, best classical0.1070.2310.1120.1670.2000.0590.0900.1490.2920.1210.153

Inspecting the top 5% of nodes recovers 25.4% of anomalies on average, five times random inspection and above the best classical detector on every graph. Since LORE keeps the risk measure separate from node assignment (Figure 10), a calibrated risk scale can be attached to the measure without changing the ranking.

We thank the reviewer again and would be glad to clarify anything further.

I appreciate the authors' constructive and comprehensive response. I am willing to maintain my original score.

Comments on the paper

1 comment

Dear Area Chair,

We sincerely thank you and all reviewers for their time and constructive feedback, and would like to briefly summarize the discussion.

Reviewers NnTV and drca have responded to our rebuttal and maintain their positive ratings. Both found that separating the risk structure from evidence-guided node assignment offers a useful perspective when evidence reliability varies across graphs, and that the experiments provide targeted mechanism evidence beyond aggregate comparisons. In our responses, we clarified for Reviewer NnTV why decoupling is necessary and how the output serves as an inspection-priority ranking, and for Reviewer drca we reported all configurations with their selection protocol, disentangled the prior from reassignment, and clarified the relation to sorting.

Reviewer e7yx found the risk-allocation interpretation intuitive but raised concerns about the novelty of OT beyond sorting, its contribution relative to the prior, prior ablations, scalability, hyperparameter selection, and robustness of the normal reference. We have addressed each of these point by point with new experiments. As the discussion period is coming to an end, we hope that Reviewer e7yx and the AC will consider our rebuttal and take these results into account in the final assessment.

Thank you again for your time and consideration.

Sincerely, The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.