LoReTTA: A Low Resource Framework To Poison Continuous Time Dynamic Graphs

AI summary

Overview

• Research area: Adversarial machine learning and graph security, specifically poisoning attacks against Temporal Graph Neural Networks (TGNNs) operating on Continuous-Time Dynamic Graphs (CTDGs).
• Technical level: Advanced. The paper assumes familiarity with temporal graph learning, PageRank-style random walks, negative sampling, and adversarial attack threat models.
• Scope: The paper introduces LoReTTA, a surrogate-free, two-stage poisoning framework that sparsifies a CTDG and replaces the removed edges with constraint-respecting adversarial negatives, and evaluates it against 11 baselines, 4 anomaly detectors, and 4 defenses. Code is released at https://github.com/ansh997/LoReTTA, and the authors are affiliated with the International Institute of Information Technology, Hyderabad.

What This Paper Is About

TGNNs are used in high-stakes settings such as financial forecasting, recommendation, and fraud detection, but small carefully crafted changes to their training graph can severely degrade them. Prior work (T-SPEAR, the state of the art) requires training an expensive surrogate model, assumes access to the entire dataset including validation and test splits, and only inserts edges. LoReTTA instead attacks using only the training portion of the graph, without any surrogate model, by first deleting the most temporally influential edges and then reinserting replacement edges that preserve graph density, temporal rhythm, and node activity patterns.

Key Contributions

1. A new poisoning framework for CTDGs: LoReTTA operates in two stages — sparsification of high-influence edges followed by replacement with adversarial negatives generated by a novel degree-preserving negative sampling algorithm — and requires no surrogate model or model gradients.
2. Four enforced unnoticeability constraints: perturbation budget, temporal feasibility (timestamps drawn from the original timestamp distribution), node activity windows, and degree preservation, where the degree constraint is described as a stronger variant than in prior work.
3. Demonstrated attack effectiveness: an average 29.47% degradation across 4 benchmark datasets and 4 state-of-the-art TGNN models, outperforming 11 baselines, with up to 42.0% degradation on MOOC, 31.5% on Wikipedia, 28.8% on UCI, and 15.6% on Enron.
4. Demonstrated stealth and robustness: the attack evades 4 leading anomaly detection systems and remains effective against 4 state-of-the-art adversarial defense methods, while achieving up to a 10x speedup over T-SPEAR.

Main Findings

• Attack effectiveness: LoReTTA degrades TGNN performance by an average of 29.47% across 4 datasets (Wikipedia, MOOC, UCI, Enron) and 4 models (TGN, JODIE, TGAT, DySAT) at a perturbation rate of 0.3.
• Per-dataset degradation: up to 42.0% on MOOC, 31.5% on Wikipedia, 28.8% on UCI, and 15.6% on Enron.
• Baseline comparison: LoReTTA consistently beats 11 baselines (T-SPEAR plus 5 ADD edge-addition and 5 REM edge-removal baselines) in the majority of cases, and across all 5 tested sparsification strategies, showing the attack is not tied to one heuristic.
• One noted exception: on Wikipedia, REM baselines achieve comparable or slightly better results. The authors attribute this to Wikipedia's highly modular semantic clusters, where sparsification alone is very damaging, and to the fact that REM baselines respect only the budget constraint (C1) rather than both C1 and C2. The paper notes that on Enron, several REM results in the tabular appendix (for example Jaccard REM with TGN at 53.83% ± 0.82%) sit above the reported clean TGN baseline of 27.9%.
• Missing results: DySAT and TGAT results on MOOC could not be reported due to out-of-memory errors, and the naive Jaccard variant is omitted for the bipartite datasets (MOOC and UCI).
• Defense robustness: against 2 static defenses (SVD-based reconstruction and cosine similarity filtering) and 2 T-shield variants (T-shield and T-shield-F) on TGN for Wikipedia and UCI, no defense restores the clean levels of 80.50% ± 0.50% (Wikipedia) and 44.2% ± 0.4% (UCI). Cosine filtering, T-shield, and T-shield-F actually cause additional degradation because they remove true edges when they misidentify adversarial ones.
• Why defenses fail: the authors report that only approximately 30% of the edges filtered by these defenses correspond to actual adversarial modifications.
• Anomaly detection evasion: against MIDAS, F-FADE, AnoEdge-L, and AnoEdge-G, no dataset–attack–detector combination achieves both precision and recall above 0.7 simultaneously, using Youden's thresholding method.
• Adversary knowledge is not monotonically helpful: in the ablation on Wikipedia and UCI (perturbing up to 30% of edges at knowledge levels 0.2, 0.4, 0.6, and 0.8), PageRank and Degree strategies do not consistently improve with more knowledge and can even degrade attack impact, while random removal stays stable across knowledge levels. The authors argue vulnerabilities are concentrated in a small set of influential nodes.
• Perturbation rate behavior: performance degrades steadily as the perturbation rate increases before plateauing, consistent with the deterministic sparsification targeting the most influential edges first; LoReTTA keeps outperforming T-SPEAR across all tested rates.
• Efficiency: complexity analysis gives Temporal PageRank time of O(|E| + |V|), space of O(|V|·|T|), and a Timestamp Selector cost of O(|V|(log|V| + d_max·k·log k) + |E|·log|E|) time with O(|V| + |E|·W) space, yielding up to a 10x speedup over T-SPEAR.

Methodology in Plain English

The attacker is assumed to be black-box: no knowledge of the model's architecture, loss, or gradients, and access only to the training portion of the graph — not validation or test splits. The attack must respect a budget Δ = ⌊p·|E|⌋ on the total number of modified edges, where p is the perturbation rate.

Stage 1 — Sparsification. The framework offers 16 ways to score edges or timestamps. Edge-level strategies build a static aggregated graph at each timestamp and rank edges with a graph heuristic (Degree, Jaccard, PageRank, Preference, or Random). Timestamp-level strategies track how node importance (measured by Temporal PageRank) changes from one timestamp to the next using 11 different distance or divergence measures (including mean shift variants, cosine, Jaccard, Euclidean, Jensen–Shannon, Kullback–Leibler, Chebyshev, Wasserstein, and Temporal EdgeRank-based scores). The highest-ranked edges or the edges inside the highest-drift timestamps are removed.

Stage 2 — Adversarial negative sampling. Each removed edge is replaced so the graph's density and structure look natural. Timestamps for new edges are sampled from the empirical distribution of real edge times using kernel density estimation, satisfying the temporal feasibility constraint. Candidate endpoints are drawn from nodes active within a time window W around that timestamp (the same W used by T-SPEAR), with endpoints drawn from disjoint node sets for bipartite datasets, and only node pairs with no prior interaction in either direction are allowed. A running tally of deletions and insertions per node keeps each node's in-degree and out-degree statistically unchanged. If constraints block further sampling, the algorithm reinitializes the kernel density estimate and samples fresh candidate times rather than relaxing any constraint.

The paper contrasts this with random sampling (no strategic impact) and Havel–Hakimi (preserves degrees but ignores temporal dynamics and unnoticeability).

Why This Matters

Impact on research: The work challenges the assumption that effective poisoning of temporal graphs requires a surrogate model and full data access, and it shows that even combining removal with insertion — something the previous state of the art did not do — remains hard for current defenses and anomaly detectors to catch. It also motivates a stronger threat model for CTDG robustness research.

Real-world applications at risk (as named in the paper):

• Financial forecasting and fraud detection, where TGNN reliability is critical.
• Recommendation systems built on evolving user-item interaction streams.
• Social media analysis and transportation modeling on time-stamped interaction networks.
• Outbreak tracking and temporal knowledge graph reasoning.

Industry relevance: The attack is cheap, plug-and-play, and requires only the training graph, which means realistic adversaries do not need privileged access or heavy compute. Because the poisoned graph preserves degree distributions, temporal rhythms, and node activity windows, standard monitoring tooling has limited signal for flagging it, and the reported failure of four anomaly detectors to achieve both high precision and recall underscores an operational gap for teams deploying TGNNs in production.

Future Directions

• Stronger defenses: Since SVD, cosine filtering, and both T-shield variants fail to restore clean performance, and misclassify roughly 70% of the edges they filter, the paper explicitly calls for more robust defense methods.
• Closing the Wikipedia gap: Understanding why pure sparsification (REM baselines, which respect only C1) can match or beat the full two-stage attack on modular, semantically clustered graphs, and whether negative sampling can be adapted to avoid the implicit regularization effect the authors describe.
• Scaling to larger graphs and models: The DySAT and TGAT out-of-memory failures on MOOC point to open questions about evaluating temporal attacks when model memory footprint restricts the experimental grid.
• Refining the relationship between adversary knowledge and attack success: The ablation shows more knowledge does not monotonically help; identifying which small set of influential nodes actually drives degradation remains an open question.

Target Audience

Researchers and graduate students working on graph neural network security, adversarial robustness, and temporal graph learning; practitioners building or auditing TGNN-based systems in finance, fraud detection, or recommendation; and defense-oriented engineers who need to understand what structural and temporal signatures current anomaly detectors miss. The paper is written at an advanced level, with formal problem definition, complexity analysis, and an extensive appendix, so readers without a background in adversarial graph learning will need to consult the cited prior work first.

Authors’ abstract

Temporal Graph Neural Networks (TGNNs) are increasingly used in high-stakes domains, such as financial forecasting, recommendation systems, and fraud detection. However, their susceptibility to poisoning attacks poses a critical security risk. We introduce LoReTTA (Low Resource Two-phase Temporal Attack), a novel adversarial framework on Continuous-Time Dynamic Graphs, which degrades TGNN performance by an average of 29.47% across 4 widely benchmark datasets and 4 State-of-the-Art (SotA) models. LoReTTA operates through a two-stage approach: (1) sparsify the graph by removing high-impact edges using any of the 16 tested temporal importance metrics, (2) strategically replace removed edges with adversarial negatives via LoReTTA's novel degree-preserving negative sampling algorithm. Our plug-and-play design eliminates the need for expensive surrogate models while adhering to realistic unnoticeability constraints. LoReTTA degrades performance by upto 42.0% on MOOC, 31.5% on Wikipedia, 28.8% on UCI, and 15.6% on Enron. LoReTTA outperforms 11 attack baselines, remains undetectable to 4 leading anomaly detection systems, and is robust to 4 SotA adversarial defense training methods, establishing its effectiveness, unnoticeability, and robustness.