Fraud rings, money-mule chains and coordinated bot campaigns leave two kinds of traces in transaction data. One is structural: a specific small pattern of timestamped interactions, such as a four-account cycle completed within an hour. The other is attribute-level: the accounts in that pattern look like they do not belong together, for example a dormant retail profile wired into a cluster of high-volume institutional accounts. Current detectors see only one trace at a time. Detectors built on temporal motifs (small recurring patterns of edges that must occur in time order within a window) count patterns exactly and ignore who the participants are, and they stop at three-node patterns because exact listing explodes beyond that. Detectors for attributed graphs judge whether a node's features fit its neighborhood, but on static graphs with no time order.
We propose to estimate, for every node, a statistic we call attribute-weighted temporal motif counts. For each four-vertex temporal motif type, we sum over the motif's occurrences around the node and weight each occurrence by how inconsistent its participants' attributes are. The estimate comes from randomized path sampling with inverse-probability weights, so it is unbiased and does not require enumerating every motif. The sampler is tilted toward attribute-inconsistent regions, and a correction keeps it unbiased. The resulting per-node features are passed to a lightweight non-aggregating scorer. The claim is that this statistic exposes coordinated, camouflaged anomalies that neither exact three-node motif counts nor edge-level attribute residuals reveal, at a cost that scales to graphs with hundreds of millions of edges.
Core Claim and What Is New
Take a node $v$ and a temporal motif type $M$ that must complete within a time window $\delta$. Let $\mathcal{I}_v(M)$ be the set of time-respecting occurrences of $M$ that contain $v$. Let $g(I)\ge 0$ be a discordance score of occurrence $I$ computed from its participants' attribute vectors, for instance the largest distance between $v$'s normalized feature vector and those of its motif partners. The target quantity and its estimator are
$$ S_v(M)=\sum_{I\in\mathcal{I}_v(M)} g(I), \qquad \hat S_v(M)=\sum_{I\in\mathcal{D}} \frac{\mathbf{1}[v\in I]\,g(I)}{\pi(I)}, $$
where $\mathcal{D}$ is the set of occurrences discovered by sampling and $\pi(I)$ is the probability that the sampler discovers $I$. This is a Horvitz-Thompson estimator, which reweights each sampled item by the inverse of its inclusion probability. It is unbiased whenever $\pi(I)>0$ for every occurrence with $g(I)>0$, which is the same argument behind the inverse-probability motif estimators in Tang et al..
The closest prior systems each have one ingredient and lack the others.
ATM-GAD learns a per-node time window and exactly lists 3-node/3-edge temporal motifs for financial fraud. It is our main motivation and our main competitor. We differ in three ways: we replace exact listing with estimation, we move to four-vertex motifs, and we weight occurrences by attributes.
TEACUPS samples $\delta$-centered temporal 3-paths and completes four-vertex motif counts by dynamic programming, with under 10% error and up to 2000x speedups. It supplies our sampling machinery. However, it produces global, purely topological counts. It has no per-node attribution, no attribute weights and no anomaly objective. Its authors also leave adaptive anchor selection open.
ALDENTE estimates how often each vertex participates in temporal motifs in order to find dense subnetworks. Its Venmo case study shows that motif density separates gambling rings from merchant bursts, which motivates going beyond edge counts. It does not use attributes and does not score individual nodes.
ARISE checks attribute similarity inside dense $k$-cores on static graphs. Our discordance weight is a temporal, motif-level version of that idea.
Research Program
The first component is a per-node estimator. TEACUPS samples anchor paths with probability proportional to precomputed path weights. We keep that construction and add two changes. First, every completed occurrence credits each of its participants, so the estimator returns $\hat S_v(M)$ for all $v$ in a single pass. Second, the anchor proposal mixes the TEACUPS weights with an attribute term: the probability of a path is proportional to $w(P)\,(\epsilon + h(P))$, where $w(P)$ is the TEACUPS weight, $h(P)$ is a cheap discordance score over the path's three edges, and $\epsilon>0$ guarantees that every occurrence keeps positive inclusion probability. The inclusion probabilities are recomputed under this proposal, so the estimator remains unbiased.
Per-node estimates are noisy for low-degree nodes. Following the heavy/light vertex split of Miller et al., we count exactly around nodes below a degree threshold, where listing is cheap, and sample only around heavy nodes. We will derive and empirically check a variance expression for $\hat S_v$ under the tilted proposal. The goal is to identify when tilting lowers variance on anomalous nodes, namely when $h$ correlates with $g$, and when it raises variance on normal ones.
The second component is the scorer. The estimates $\hat S_v(M)$ for each motif type, the plain unweighted motif counts, and raw node features feed an MLP or gradient-boosted scorer with no neighborhood aggregation. In the unsupervised setting the scorer is a density model instead. This choice follows the evidence in MI-GAD that aggregating message passing smooths away anomaly signal and that non-aggregating backbones can win. Here the structural context arrives as unsmoothed sufficient statistics rather than through averaging. The discordance function $g$ starts fixed, either cosine distance or a feature residual against a domain center in the spirit of DR-GGAD. A learned $g$ is a later step, because a learned $g$ makes the sampler's tilt depend on training.
Baselines
The naive reference point is a gradient-boosted classifier, or an MLP in the unsupervised case, trained on raw node features alone. It will receive the same tuning budget as our scorer. If our features do not improve on it, the structural signal is not earning its cost.
The strongest supervised competitor on attributed dynamic data is the temporal graph attention network from DGraph, which reports AUC 0.792 on DGraph and was the best performer there. We will rerun it on the paper's splits, with background nodes retained as that paper recommends. Beating it means a higher AUC on the same split, with the margin exceeding the standard deviation across five seeds.
The strongest motif-based competitor is ATM-GAD, which reports AUC 0.911 on ETH-200 against 0.875 for the best motif baseline. We will run it on ETH, Elliptic, Bitcoin-Alpha and Bitcoin-OTC with its own window learner and the same hyperparameter search budget as ours. Beating it means a higher AUC on ETH-200 at equal or lower wall-clock time.
For generalist dynamic detection, GeneralDyG reports AP 24.00 on Bitcoin-Alpha in the 1% anomaly setting, and we will compare in that same setting.
For structure-only streams, MIDAS reports AUC 0.977 on DARPA. SubAnom reports F1 0.6679 on DARPA, against 0.5677 for DynAnom. DARPA lacks rich node attributes, so there we run only the unweighted estimator. The aim is to show that we do not lose ground; we do not expect to win on volumetric attacks.
On Elliptic we found no reported result on Lacuna for any of these methods, so all numbers there will come from our own reruns.
Three ablations isolate the key ingredients. The first replaces the attribute weights with $g\equiv 1$, leaving plain estimated four-vertex counts. The second replaces four-vertex motifs with exact three-node motifs carrying the same attribute weights. The third replaces the tilted proposal with the untilted TEACUPS proposal at the same sample budget.
Why not just…?
Why not just concatenate node features with exact three-node motif counts? This is the most serious threat. If four-vertex structure adds nothing for fraud, the cheap exact version wins on simplicity. The second ablation settles the question directly. We also plan an injection study on the SNAP temporal graphs TEACUPS used, inserting four-cycles and chordal four-cycles that contain no unusual triangles. If the three-node version matches ours on real fraud labels, we will report that four-vertex motifs only help on synthetic coordination patterns, and we will narrow the claim accordingly.
Why not just compute attribute residuals over each node's temporal one-hop neighbors? Edge-level discordance, in the style of DR-GGAD applied to temporal neighbors, is cheap. It also captures any account that interacts with dissimilar partners, which is common for legitimate hubs. Our hypothesis is that coordination shows up when dissimilar parties close a time-ordered pattern together, not when they merely touch. The experiment that tests this is a baseline in which the discordance score is summed over incident edges rather than over motif occurrences, run with the same scorer.
Why not just use a streaming sketch like MIDAS? MIDAS is in constant memory and is excellent when volume is the signature, as its DARPA result shows. It sees only edge frequencies, however, and so cannot distinguish a burst shaped like a star from one shaped like a cycle, nor relate either to attributes. We include it and expect it to lose on the financial datasets. Where it ties, we will report the tie.
Why not use plain uniform edge sampling? Under uniform edge sampling, a four-edge motif survives with probability $p^4$, which makes per-node variance very large. Uniformly sampled edges also do not preserve time order. Path anchors avoid both problems, as argued in Colorful Triangle Counting and TEACUPS. We will nonetheless report the variance of uniform edge sampling at an equal budget.
Proposed Experiments
The main datasets are DGraph, with its 3.7M nodes, directed timestamped edges and 1.3% fraud rate; Elliptic; ETH; and Bitcoin-Alpha and Bitcoin-OTC. Edge direction is kept, because four-vertex directed cycles are exactly what undirected conversion destroys. DGraph's high feature missingness is handled with missingness indicators inside $g$. Metrics are AUC and AUPRC, plus precision at the true anomaly count, and every result is averaged over five seeds.
On the scale side, we will measure per-node relative error against exact counts on wiki-talk and on a bitcoin subgraph. We will also measure end-to-end runtime and memory up to reddit-reply and stackoverflow, against exact listing.
The decisive checks are these. On DGraph and ETH, attribute-weighted four-vertex estimates must beat both the second ablation (exact three-node, weighted) and the edge-level discordance baseline. At a fixed sample budget, the tilted proposal must reduce mean squared error on labeled anomalous nodes without increasing error on normal nodes by more than a reported factor. End-to-end runtime must stay below that of the ATM-GAD reproduction. If the first check fails, the project reduces to a faster and more scalable ATM-GAD, which is a narrower contribution, and we will state it that way.
References
- StructInf: Mining Structural Influence from Social Streams
- ATM-GAD: Adaptive Temporal Motif Graph Anomaly Detection for Financial Transaction Networks
- Accurate and Fast Estimation of Temporal Motifs Using Path Sampling
- Scalable Temporal Motif Densest Subnetwork Discovery
- ARISE: Graph Anomaly Detection on Attributed Networks via Substructure Awareness
- Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning
- Beyond Local Patterns: Multiscale Inconsistency Learning for Graph Anomaly Detection
- DR-GGAD: Dual Residual Centering for Mitigating Anomaly Non‑Discriminativity in Generalist Graph Anomaly Detection
- DGraph: A Large-Scale Financial Dataset for Graph Anomaly Detection
- A Generalizable Anomaly Detection Method in Dynamic Graphs
- Midas: Microcluster-Based Detector of Anomalies in Edge Streams
- SubAnom: Efficient Subgraph Anomaly Detection Framework over Dynamic Graphs
- Colorful triangle counting and a MapReduce implementation