Spatio-Temporal Graphs Beyond Grids: Benchmark for Maritime Anomaly Detection

AI summary

Overview

• Research area: Spatio-temporal graph neural networks (ST-GNNs), graph-based anomaly detection, maritime traffic analysis, and LLM-assisted benchmark construction.
• Technical level: Intermediate — readers should be comfortable with graph neural networks, anomaly detection terminology (node/edge/graph level), and basic AIS vessel-tracking concepts, but the paper's framing is accessible.
• Scope (one sentence): The paper proposes (and partially prototypes) a benchmark dataset built by extending the Open Maritime Traffic Analysis Dataset (OMTAD) into a multi-granularity anomaly detection testbed for non-grid maritime environments, using two LLM-based agents to synthesize companion trajectories and inject anomalies.

What This Paper Is About

Most spatio-temporal graph learning works because the world can be discretized into fixed nodes — road intersections, bus stops, subway stations. The open sea has no such anchors, so building a meaningful spatio-temporal graph of vessels is fundamentally hard, and detecting anomalies in that setting is harder still. This paper's goal is to create a systematic benchmark for maritime anomaly detection that spans three levels of granularity (node, edge, graph), built on top of an existing open AIS dataset.

Key Contributions

1. A multi-granularity benchmark design. The authors define a benchmark supporting node-level anomalies (abnormal single-vessel behavior), edge-level anomalies (irregular vessel-to-vessel interactions), and graph-level anomalies (collective abnormal events), framed as a unified testbed for comparing methods across anomaly detection settings.

2. Extension of OMTAD to support graph-based anomaly detection. They identify two limitations of OMTAD — many trajectories are spatially isolated and therefore hard to turn into graphs, and the dataset contains only normal trajectories with no anomaly labels — and address both by adding a trajectory synthesis step for sparse regions and an anomaly injection step.

3. A two-agent LLM pipeline for dataset construction. A Trajectory Synthesizer enriches inter-vessel context (using real nearby vessels where available and generating perturbed "virtual neighbors" where they are not), while an Anomaly Injector generates anomalies from high-level text prompts rather than fixed rules. Both operate under a shared Coordinator that manages data flow, enforces constraints, and validates outputs.

4. Early empirical justification for the graph framing. A preliminary graph-level experiment shows that models with GNN modules outperform purely temporal baselines, supporting the claim that repurposing OMTAD into a graph benchmark captures meaningful structural signal.

Main Findings

• Base dataset composition: The benchmark builds on OMTAD, which covers the West Australian offshore region (105–116°E, 36–15°S) from 2018 to 2020 and contains 19,124 trajectories across four vessel categories: Cargo (14,384), Tanker (4,020), Fishing (466), and Passenger (254). Each AIS record includes vessel identifiers, geolocation, course over ground (COG), speed over ground (SOG), and UTC timestamps.
• GNN-integrated models beat temporal-only models: In the preliminary graph-level anomaly detection study, models combining time-series architectures with GNN modules consistently outperformed their purely temporal counterparts (LSTM and Transformer) across all tested anomaly ratios.
• Preliminary setting details: The preliminary experiment varied the trajectory anomaly ratio r_traj ∈ {0.1, 0.5} with the node anomaly ratio fixed at r_node = 0.5. Graph inputs were built by applying OPTICS clustering to spatial snapshots at each timestamp, sampling a fixed number k of vessel trajectories per cluster, and constructing a directed temporal graph over a w-hour observation window, yielding exactly k × w nodes per graph.
• Anomaly injection method (preliminary): For a trajectory of length w, a contiguous anomaly block of size m = r_node·w was selected at a random start index, with r_node ∈ {r1, r2, r3}. SOG and COG values inside the block were perturbed using rate-of-change values with k > 3, placing perturbed values outside the 99.7% confidence interval of normal behavior. A trajectory was labeled anomalous if at least one node was perturbed.
• Two levels of anomaly control: The node anomaly ratio r_node ∈ (0,1] controls intra-trajectory anomaly density, while the trajectory anomaly ratio r_traj ∈ (0,1] controls the fraction of trajectories labeled anomalous at the graph level.
• Acknowledged scope limit: The authors explicitly state that the injection strategy perturbed only the simplest navigational features, and that real maritime anomalies (illegal rendezvous, loitering, spoofed AIS signals, environmental deviations) are far more diverse. No quantitative performance scores (e.g., F1, AUC) are reported in the paper content; results appear only as figures.
• Dataset release status: A finalized version of the dataset is described as a future step, not yet curated or released.

Methodology in Plain English

The starting point is OMTAD, an openly licensed collection of vessel tracks derived from AIS signals. The authors point out that you cannot use it as-is for graph-based anomaly detection: too many vessels sail alone (so there is nothing to connect them to), and everything in it is normal (so there is nothing to detect).

Their fix has two parts. First, they densify the data. Where a focal vessel has real neighbors nearby, those tracks are included directly to form edges. Where it has none, an LLM-based Trajectory Synthesizer invents plausible "virtual neighbors" by perturbing SOG, COG, latitude, and longitude within bounded ranges.

Second, they inject anomalies. Rather than hard-coding perturbation rules, an LLM-based Anomaly Injector reads high-level natural language descriptions of anomalies (unusual speed changes, risky encounters, group loitering), parses them into structured intent, maps that intent onto edits of the spatio-temporal graph, and attaches labels with rationale text. A Coordinator orchestrates the loop: build a standard "perception bundle" from AIS and environmental metadata, dispatch it to the synthesizer, pass the augmented graph and context to the injector, then collect provenance and validation logs.

Both agents consume a shared slot-filled schema covering AIS fields (MMSI, timestamp, latitude, longitude, SOG, COG), derived rates of change (ΔSOG/Δt, ΔCOG/Δt), environmental context (wind/wave/current bins, visibility proxy), and provenance (source trajectory IDs).

To check this was worth doing at all, the authors ran a preliminary graph-level experiment injecting kinematic anomalies and comparing LSTM and Transformer baselines against their GNN-augmented versions. The GNN versions won, which they take as evidence the structural signal is real.

Why This Matters

• Impact on research: Non-grid spatio-temporal systems lack the standardized benchmarks that road traffic and public transit enjoy. This work positions itself as a first step toward filling that gap, with an emphasis on reproducibility and on anomaly evaluation that spans multiple granularities rather than a single binary label.
• Novel use of LLMs as data-construction tools: Instead of using LLMs as detectors, the paper uses them as dataset generators — synthesizing plausible neighbors and prompt-driven, semantically meaningful anomalies. This is a different pattern than benchmarks such as AD-LLM, which the paper notes remain at a more abstract level.
• Real-world applications:
  • Maritime domain awareness and coastal surveillance, where flagging a single vessel behaving oddly, a pair of vessels meeting suspiciously, or a whole group loitering requires different detection logic.
  • Illegal rendezvous and smuggling detection, which the authors list among more semantically complex anomalies they want to model.
  • AIS spoofing and signal integrity monitoring, also named as a target anomaly class.
  • Drone swarms and aerial traffic management, which the authors explicitly identify as emerging non-grid domains that will face the same graph-construction problem.
• Industry relevance: Shipping, port authorities, defense and maritime security organizations, and fisheries monitoring all depend on AIS-derived analytics. A public benchmark with open licensing (the paper is published under CC BY-NC-ND 4.0 and commits to releasing the dataset openly) lowers the barrier for vendors and researchers to compare detection methods on common ground.

Future Directions

1. Consolidate and release the pipeline. The authors plan to package the construction process into a reproducible framework with scripts that let researchers deterministically regenerate augmented or injected dataset variants, and to publish the finalized dataset under an open license.
2. Benchmark baselines. They intend to evaluate purely temporal sequence models (LSTM, Transformer), hybrid spatio-temporal GNNs, and recent graph anomaly detection architectures across node-, edge-, and graph-level tasks, and across different anomaly ratios and scenarios.
3. Expand beyond kinematic anomalies. The stated goal is to move toward illegal encounters, coordinated group behaviors, and procedural violations near ports and restricted areas, combining LLM agents with domain rules.
4. Refine labeling strategy. The authors acknowledge that defining consistent, interpretable labels across node-, edge-, and graph-level tasks is non-trivial and requires principled, task-aware labeling that captures both local anomalies and their broader contextual implications.

Target Audience

This paper is most useful to researchers building spatio-temporal graph models for domains without fixed spatial anchors, to maritime surveillance and AIS analytics practitioners who need a labeled testbed, and to anyone interested in using LLM agents for domain-grounded data synthesis and anomaly injection. Because it is a benchmark-and-positioning paper with preliminary rather than final results, it is best read as a roadmap and an invitation to collaborate rather than as a source of established detection performance numbers.

Authors’ abstract

Spatio-temporal graph neural networks (ST-GNNs) have achieved notable success in structured domains such as road traffic and public transportation, where spatial entities can be naturally represented as fixed nodes. In contrast, many real-world systems including maritime traffic lack such fixed anchors, making the construction of spatio-temporal graphs a fundamental challenge. Anomaly detection in these non-grid environments is particularly difficult due to the absence of canonical reference points, the sparsity and irregularity of trajectories, and the fact that anomalies may manifest at multiple granularities. In this work, we introduce a novel benchmark dataset for anomaly detection in the maritime domain, extending the Open Maritime Traffic Analysis Dataset (OMTAD) into a benchmark tailored for graph-based anomaly detection. Our dataset enables systematic evaluation across three different granularities: node-level, edge-level, and graph-level anomalies. We plan to employ two specialized LLM-based agents: \emph{Trajectory Synthesizer} and \emph{Anomaly Injector} to construct richer interaction contexts and generate semantically meaningful anomalies. We expect this benchmark to promote reproducibility and to foster methodological advances in anomaly detection for non-grid spatio-temporal systems.