Trivial Graph Features and Classical Learning are Enough to Detect Random Anomalies

Matthieu Latapy; Stephany Rajeh

cs.LGMar 2, 2026

Trivial Graph Features and Classical Learning are Enough to Detect Random Anomalies

Authors: Matthieu Latapy, Stephany Rajeh

Organizations: CNRS, LIP6 Sorbonne Universit´e Paris, France · Efrei Research Lab Efrei Paris Panth´eon-Assas Universit´e Villejuif, France

Abstract

Detecting anomalies in link streams that represent various kinds of interactions is an important research topic with crucial applications. Because of the lack of ground truth data, proposed methods are mostly evaluated through their ability to detect randomly injected links. In contrast with most proposed methods, that rely on complex approaches raising computational and/or interpretability issues, we show here that trivial graph features and classical learning techniques are sufficient to detect such anomalies extremely well. This basic approach has very low computational costs and it leads to easily interpretable results. It also has many other desirable properties that we study through an extensive set of experiments. We conclude that detection methods should now target more complex kinds of anomalies.

Figures & tables

Panel of Table 1 — TABLE I : Comparison of TGF with state-of-the-art methods.

Panel of Figure 2 — Fig. 1 : Examples of $G$ -type and $H$ -type history graphs. Top: a link stream between 4 nodes $a$ , $b$ , $c$ , and $d$ , from time $0$ to $10$ . We consider the latest link $(10,b,c)$ , meaning that an interaction occurred between $b$ and $c$ at time $10$ . We display two $G$ -type ( $G_{3}$ and $G_{8}$ , bottom-left) and two $H$ -type ( $H_{3}$ and $H_{8}$ , bottom-right) history graphs for this link. The integers on the links of these graphs indicate their number of occurrences within the considered history. For instance, $H_{3}$ is the graph obtained from the $3$ last interactions. They involve $c$ and $d$ twice and $a$ and $b$ once.

Dataset	$n$	$m$	$\ell$
Bitcoin-Alpha	3,783	14,124	24,186
Bitcoin-OTC	5,881	21,492	35,592
DNC Emails	1,866	5,517	37,421
UCI Messages	1,899	13,838	59,835
Digg	30,360	85,151	86,199
Internet Topo.	34,761	107,720	171,403

TABLE II : Basic characteristics of datasets used in this paper, ordered with respect to their total number of timestamped links

\ell

(last column). The other columns indicate the number of nodes

n

, and the number of distinct links

m

	UCI Messages			Digg			DNC Emails			Bitcoin-Alpha			Bitcoin-OTC			Internet Topology
	1%	5%	10%	1%	5%	10%	1%	5%	10%	1%	5%	10%	1%	5%	10%	1%	5%	10%
SedanSpot	0.7342	0.7156	0.7061	0.6976	0.6784	0.6396	0.7427	0.7362	0.7235	0.7380	0.7264	0.7085	0.7346	0.7284	0.7156	0.6873	0.6742	0.6672
CM-Sketch	0.7320	0.6968	0.6835	0.6884	0.6675	0.6358	0.7053	0.6946	0.6876	0.7146	0.7015	0.6887	0.7412	0.7338	0.7242	0.6687	0.6605	0.6558
Node2Vec	0.7371	0.7433	0.6960	0.7364	0.7081	0.6508	0.7391	0.7284	0.7103	0.6910	0.6802	0.6785	0.6951	0.6883	0.6745	0.6821	0.6752	0.6668
DeepWalk	0.7514	0.7391	0.6979	0.7080	0.6881	0.6396	0.7481	0.7303	0.7197	0.6985	0.6874	0.6793	0.7423	0.7356	0.7287	0.6844	0.6793	0.6682
NetWalk	0.7758	0.7647	0.7226	0.7563	0.7176	0.6837	0.8105	0.8371	0.8305	0.8385	0.8357	0.8350	0.7785	0.7694	0.7534	0.8018	0.8066	0.8058

TABLE III : AUC performances of state-of-the-art methods and TGF in two configurations: with

H

-type history graphs of size

1000

, and with combined history graphs. All methods are applied to public reference datasets with

1

5

% and

10

% anomaly injection. The two best results are in bold, the best one is underlined.

Fig. 2 : The impact of size

s

and duration

d

(horizontal axis) of the

H

-type (left) and

G

-type (right) history graphs on AUC scores. We consider here

5

% anomaly injection and learning with

r=0.7

Fig. 3 : AUC scores obtained with various history resolutions and combinations. For each dataset, we display the best score obtained with, from left to right: a

H

-type history graph, a

G

-type history graph, the combination of all

H

-type history graphs, the combination of all

G

-type history graphs, and the combination of all these history graphs. We consider 5% anomaly injection and learning with

r=0.7

Fig. 4 : AUC scores for TGF with sliding windows containing

50\%

of all links, using

H

-type history graphs of size

1000

, with

5

% anomaly injection and learning rate

r=0.7

in each window. The inset shows results for sliding windows containing only

1\%

of all links in the largest datasets.

Fig. 5 : The impact of size

s

and duration

d

(horizontal axis) of the

H

-type (top) and

G

-type (bottom) history graphs on AUC scores in the Digg dataset. We also show the impact of the usage of different machine learning algorithms on

H

-type history graphs. We consider here

5

% anomaly injection and learning with

r=0.7

Fig. 6 : Feature permutation analysis for Digg with

5

% anomaly injection, when features are computed on

H

-type history graphs with size

15\,000

(top) and

G

-type history graphs with duration

6

days (bottom). We display only the ten features (vertical axis) with maximal AUC score decrease (horizontal axis). In order to display box plots, we repeat the permutation ten times for each feature.

Fig. 7 : Distributions of values of the two most important features for the Digg dataset with 5% injection, in

H

-type history graphs of size

15\,000

(top) and

G

-type history graphs of duration

6

days (bottom). The distribution for normal links is in blue, and the one for anomalous links is in red. The vertical axis is in logarithmic scale.

Fig. 8 : Average computation time (in microseconds) per link as a function of history size for

H

-type history graphs (left) and duration for

G

-type history graphs (right), for all datasets with 5% anomaly injection.

		1%	5%	10%
Bitcoin-Alpha	SLADE	0 $h$ 2 $m$ 21 $s$	0 $h$ 2 $m$ 35 $s$	0 $h$ 2 $m$ 39 $s$
Bitcoin-Alpha	TGF	0 $h$ 0 $m$ 5.56 $s$	0 $h$ 0 $m$ 5.55 $s$	0 $h$ 0 $m$ 5.53 $s$
Bitcoin-OTC	SLADE	0 $h$ 5 $m$ 30 $s$	0 $h$ 6 $m$ 3 $s$	0 $h$ 6 $m$ 29 $s$
Bitcoin-OTC	TGF	0 $h$ 0 $m$ 11.82 $s$	0 $h$ 0 $m$ 12.89 $s$	0 $h$ 0 $m$ 16.71 $s$
Digg	SLADE	0 $h$ 41 $m$ 38 $s$	0 $h$ 44 $m$ 55 $s$	0 $h$ 47 $m$ 56 $s$
Digg	TGF	0 $h$ 0 $m$ 19.89 $s$	0 $h$ 0 $m$ 24.76 $s$	0 $h$ 0 $m$ 27.37 $s$

TABLE IV : End-to-end computation time of SLADE and TGF

H_{1000}

across all reference datasets, with 1%, 5%, and 10% anomaly injections. Time is in hours (

h

), minutes (

m

), and seconds (

s

Anomaly Detection

Anomaly detection finds rare or unexpected patterns in data, from defective products and system faults to fraud and security threats.

See all 631 papers

RagGAD: Rationale-Aware Conditional Gaussian Mixture Normalizing Flow for Unsupervised Graph Anomaly Detection
Aug 17, 2026Junxin Lu, Jing Zhao, Shiliang SunGraph-Based Anomaly Detection Unsupervised Anomaly Detection
School of Computer Science and Technology, East China Normal University, Shanghai 200062, China · State Key Laboratory of Submarine Geoscience, School of Automation and Intelligent Sensing, Shanghai Jiao Tong University, 800 Dongchuan Road, Shanghai 200240, China
Unsupervised Symbolic Anomaly Detection
Mar 18, 2026Md Maruf Hossain, Tim Katzke, Simon Klüttermann +1Unsupervised Anomaly Detection Anomaly Detection
TU Dortmund University, Dortmund, Germany · Research Center Trustworthy Data Science and Security, UA Ruhr, Germany
Beat the Counter First: A Baseline for Temporal-Graph Anomaly Detectors
Aug 16, 2026Omair Shafi Ahmed, Zohair ShafiGraph-Based Anomaly Detection Anomaly Detection
Microsoft · Northeastern University

Aug 17, 2026J/K move · Enter open · S save

RagGAD: Rationale-Aware Conditional Gaussian Mixture Normalizing Flow for Unsupervised Graph Anomaly Detection

Junxin Lu, Jing Zhao, Shiliang Sun

School of Computer Science and Technology, East China Normal University, Shanghai 200062, China · State Key Laboratory of Submarine Geoscience, School of Automation and Intelligent Sensing, Shanghai Jiao Tong University, 800 Dongchuan Road, Shanghai 200240, China

Graph-Based Anomaly Detection Unsupervised Anomaly Detection Anomaly Detection Gaussian Mixture Models

Open paper AskPDF arXiv

Graph anomaly detection aims to identify nodes that deviate from normal behavioral patterns within graphs. However, existing methods largely rely on the homophily assumption, which makes it difficult to distinguish spurious affinities and to capture the diverse behaviors of normal nodes,limiting their robustness in complex real-world scenarios. To address this problem, we propose RagGAD, an unsupervised graph anomaly detection framework based on rationale-aware conditional Gaussian mixture normalizing flow. RagGAD introduces an adaptive rationale disentangler to disentangle stable rationales from spurious correlations within node interrelationships, and further decomposes stable rationales into robust and fragile components. The learned rationales capture underlying interaction patterns that characterize normal behaviors under varying conditions, while anomalies emerge as deviations associated with unstable or spurious correlations. To model the intricate distributions of normal and abnormal nodes, RagGAD integrates rationale-non-rationale Gaussian mixture modeling with a robust-fragile rationale mixture learning strategy. By mitigating spurious homophilic correlations and embracing the heterogeneity of normal patterns, RagGAD identifies anomalies as low-density regions within a structure-aware distribution space. Extensive experiments on multiple benchmark datasets demonstrate that RagGAD outperforms state-of-the-art methods.

Abstract

Anomaly Detection

Explore similar work

RagGAD: Rationale-Aware Conditional Gaussian Mixture Normalizing Flow for Unsupervised Graph Anomaly Detection

Unsupervised Symbolic Anomaly Detection

Beat the Counter First: A Baseline for Temporal-Graph Anomaly Detectors