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

Matthieu Latapy, Stephany Rajeh · 2026

Read Trivial Graph Features and Classical Learning are Enough to Detect Random Anomalies by Matthieu Latapy, Stephany Rajeh (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-01841.txt.

Introduction

Matthieu Latapy and Stephany Rajeh show that simple tools catch injected fake links in interaction streams extremely well. Their 2026 work studies link streams, timed records of contacts in finance, security, and social media. With no ground truth for real anomalies, the field tests detectors on randomly injected links.

Against complex rivals, the pair use trivial graph features plus classical learning methods only. Their basic approach costs very little compute and yields results that stay easy to interpret. Wide experiments probe many other desirable traits of the simple detector, beyond raw scores. The authors conclude the field should now aim at harder anomaly types, not random fakes. Code and data are public, so the claim can be checked and the bar for new methods rises.

Catalog record

CREATORMatthieu Latapy, Stephany Rajeh
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50514
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.01841

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Trivial Graph Features and Classical Learning are Enough to Detect Random Anomalies Matthieu Latapy, Stephany Rajeh 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. Reproducibility. We provide our code and data at [ 21 ] . I Introduction Detecting anomalies is crucial in many domains such as finance, security, and social media. In many cases, detection relies on the analysis of interaction traces modeled as link streams [ 22 ] : ordered sequences of timestamped links (t_{i},u_{i},v_{i}) meaning that an interaction occurred between items u_{i} and v_{i} at time t_{i} . Items may represent bank accounts and links may represent payments, for instance; or they may represent digital devices and data transfers; or individuals and contacts between them. Then, anomalous links typically reveal credit card frauds, forged packets or identity thefts. Most detection methods need labeled data in which anomalies are known, either for training (supervised learning) or for evaluation (does the method succeed in detecting known anomalies?), or both. However, labeled data are rarely available. Then, researchers commonly rely on anomalous link injection [ 2 ] : they add random links into real-world data and detection methods are designed for these links [ 27 , 31 , 10 , 4 , 32 , 33 , 11 , 28 , 25 , 17 ] . We propose here a graph-based approach that favors simplicity. For each link, we consider history graphs composed of the most recent interactions. We then compute trivial features of each link within its history graphs, and we use them to train classical machine learning methods on real-world data with randomly injected anomalies. We call this method TGF, to emphasize the fact that it needs trivial graph features only. Experiments show that this simple method detects injected links extremely well, better than the profusion of more complex state-of-the-art methods. In addition, it has the following important strengths, summarized in Table I . High flexibility. All methods have some flexibility, but TGF has a clear advantage to this regard. In addition to a very flexible history management (details below), it is able to deal with various kinds of graphs (classical, bipartite, directed, etc) and it may use additional application-dependent features (a payment amount or location, for instance). Efficiency. TGF is very fast, both theoretically with algorithmic complexity in \mathcal{O}(1) for all feature computations, and in practice with up to millions of links processed per second on a standard laptop. TGF space costs are also in \mathcal{O}(1) and very small in practice. Importantly, space requirements are under control, as they may be tuned using history size and type to ensure they stay under any user-defined bound. Advanced history. TGF uses past data at various resolutions, and it actually combines several resolutions very easily. It also uses several kinds of history graphs, and combines them. Other approaches for building history graphs may easily be added and combined. For instance one may use the graph of interactions that occurred during the same day one week ago. This ability to integrate different notions of history and time resolutions is quite unique. Interpretability. Last but not least, trivial graph features have natural interpretations in terms of graphs. More importantly, they also have interpretation in terms of what they mean in the application area. As TGF readily identifies the features that play the most important role in anomaly detection, this leads to an interpretable description of what makes links anomalous in each practical case. Having all these strengths combined in a simple method that detects randomly injected links so well leads us to the following conclusion: trivial graph features and classical machine learning are enough to detect anomalies, as long as they are similar to randomly injected links. This is not a statement of important theoretical interest only: in many practical cases, it is reasonable to model anomalies by random links. Indeed, it is often impossible for fraudsters to mimic the real behavior of the legitimate user they pretend to be [ 7 , 30 , 3 , 19 ] . In addition, most research work in anomaly detection is evaluated on random link injections, and therefore much effort is devoted to the optimization of detection in such cases. We believe that TGF puts an end to this line of research. II Related work Link streams, also called edge streams, temporal graphs, temporal networks, or dynamic graphs by various authors, model a wide variety of interaction traces. Detecting anomalous links in such streams is an important fundamental and applied research topic. Many recent approaches leverage deep learning methods [ 16 , 26 , 32 , 33 , 10 , 34 , 12 ] . For instance, Node2Vec [ 16 ] , DeepWalk [ 26 ] , and others use embeddings based on random walks (with the goal that similar neighborhoods lead to similar embeddings) and then apply classical clustering methods. NetWalk [ 32 ] learns dynamic latent node representations and uses auto-encoder reconstruction error. AddGraph [ 33 ] , StrGNN [ 10 ] and others use graph convolutional networks (GCN) and graph neural network to extract local structural and temporal features. TADDY [ 25 ] proposes a transformer-based method, while RustGraph [ 17 ] combines variational autoencoding and contrastive learning. Using two self-supervised tasks, SLADE [ 24 ] learns dynamic node representations by updating memory vectors for short-term stability and reconstructing them from recent interactions. DAGMM [ 34 ] provides an unsupervised solution that uses a deep autoencoder and a Gaussian mixture model. GraphSAGE [ 18 ] leverages node embeddings to perform semi-supervised representation learning. BEA [ 12 ] deals with bipartite networks; it detects burstiness and models dynamic connectivity patterns using embeddings. All these methods reach very good detection scores, but they often raise serious interpretability and scalability issues. Direct graph-based approaches also exist [ 1 , 14 , 27 , 8 ] . For instance, SedanSpot [ 14 ] samples the whole graph and uses random walks to assess the impact of new links on the distance between sampled nodes. CM-Sketch [ 27 ] is a sketch-based method that leverages local structural information and historical behavior in the vicinity of links to classify them as anomalous or not. These methods often provide better interpretability, but they generally use strong assumptions on anomaly features that weaken their flexibility. Because of the lack of publicly available data with known anomalies that would provide ground truth, evaluation of proposed methods generally relies on injected anomalies [ 2 ] . Then, many detection methods focus on the detection of randomly injected links [ 27

Read the complete text