AlertStar: Path-Aware Alert Prediction on Hyper-Relational Knowledge Graphs
Zahra Makki Nayeri, Mohsen Rezvani · 2026
Read AlertStar: Path-Aware Alert Prediction on Hyper-Relational Knowledge Graphs by Zahra Makki Nayeri, Mohsen Rezvani (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-2604-03104.txt.
Introduction
Nayeri and Rezvani turn network alerts into a knowledge graph so that attacks can be predicted from paths between attackers and victims. Each alert becomes a rich statement carrying source and destination addresses, attack type, and flow details such as ports and timing. Their AlertStar models fuse that context with path structure in embedding space, beating global propagation methods on two benchmarks while running leaner.
Catalog record
| CREATOR | Zahra Makki Nayeri, Mohsen Rezvani |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71612 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.03104
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
AlertStar: Path-Aware Alert Prediction on Hyper-Relational Knowledge Graphs Zahra Makki Nayeri, Mohsen Rezvani Abstract Cyber-attacks continue to grow in scale and sophistication, yet existing network intrusion detection approaches lack the semantic depth required for path reasoning over attacker–victim interactions. We address this by first modelling network alerts as a knowledge graph, then formulating hyper-relational alert prediction as a hyper-relational knowledge graph completion (HR-KGC) problem, representing each network alert as a qualified statement ( h , r , t , 𝒬 ) (h,r,t,\mathcal{Q}) , where h h and t t are source and destination IPs, r r denotes the attack type, and 𝒬 \mathcal{Q} encodes flow-level metadata such as timestamps, ports, protocols, and attack intensity, going beyond standard KGC binary triples ( h , r , t ) (h,r,t) that would discard this contextual richness. We introduce five models across three contributions: first, Hyper-relational Neural Bellman–Ford (HR-NBFNet) extends Neural Bellman–Ford Networks to the hyper-relational setting with qualifier-aware multi-hop path reasoning, while its multi-task variant MT-HR-NBFNet jointly predicts tail, relation, and qualifier-value within a single traversal pass; second, AlertStar fuses qualifier context and structural path information entirely in embedding space via cross-attention and learned path composition, and its multi-task extension MT-AlertStar eliminates the overhead of full knowledge graph propagation; third, HR-NBFNet-CQ extends qualifier-aware representations to answer complex first-order logic queries, including one-hop, two-hop chain, two-anchor intersection, and union, enabling multi-condition threat reasoning over the alert knowledge graph. Evaluated inductively on the Warden and UNSW-NB15 benchmarks across three qualifier-density regimes, AlertStar and MT-AlertStar achieve superior MR, MRR, and Hits@k, demonstrating that local qualifier fusion is both sufficient and more efficient than global path propagation for hyper-relational alert prediction. \justify I Introduction Cyber-attacks continue to grow in scale and sophistication, rendering purely reactive defences insufficient for modern network security. Operational intrusion detection systems (IDSs) are highly sensitive by design, routinely generating tens of thousands of alerts per day [ 5 ] , yet the most dangerous threats — advanced persistent threat (APT) campaigns — are rarely revealed by any single alert. APT actors deliberately decompose their campaigns into individually innocuous steps: reconnaissance, initial compromise, lateral movement, and data exfiltration, each generating only a low-priority alert that may be dismissed in isolation [ 5 ] . The central challenge facing Security Operations Centers (SOCs) and Computer Emergency Response Teams (CERTs) is reasoning across sequences of alerts distributed over time and across different host pairs to reconstruct the underlying campaign [ 6 ] . Consider a representative scenario: a denial-of-service alert at 02:14, a reconnaissance alert on a different source IP at 03:47, and a data exfiltration alert on a third IP pair at 06:22 — each assessed as medium priority in isolation, yet collectively the signature of a coordinated lateral-movement campaign. A CERT team that could have predicted the second and third alerts from the first could have intervened before exfiltration. This is the problem of alert prediction : given the observed alert history, infer which IP will be targeted next, under which attack type, and via which propagation path. Knowledge graphs (KGs) offer a principled solution by representing attacker–victim interactions as relational triples (h,r,t) , enabling heterogeneous, semantically rich reasoning over unseen entities — a critical capability for inductive alert prediction. However, standard KGC models are limited to binary triples, which cannot encode the auxiliary flow-level metadata that distinguishes network alerts of the same type. Two alerts sharing the same source IP, attack type, and destination IP may represent fundamentally different threat scenarios depending on their timestamp, port, protocol, and flow intensity. This motivates hyper-relational knowledge graphs, where each alert is represented as a qualified statement (h,r,t,\mathcal{Q}) with \mathcal{Q} encoding auxiliary key–value pairs beyond the core triple. Existing hyper-relational KGC models (StarE [ 4 ] , StarQE [ 1 ] , HyNT [ 3 ] ) are predominantly transductive, limiting their applicability when new IP addresses unseen during training must be reasoned about at inference time. Neural Bellman–Ford Networks (NBFNet) [ 12 ] address inductive link prediction via path-based message passing, but operate on binary triples with no mechanism for qualifier context. In this work, we model network alerts as a hyper-relational knowledge graph and formulate alert prediction as an HR-KGC problem. We introduce five models across three paradigms: qualifier-aware path propagation, embedding-based fusion, and complex query answering over alert graphs. The main contributions are: • HR-KGC alert benchmarks. We formulate alert prediction as HR-KGC and construct inductive benchmarks from Warden and UNSW-NB15 across three qualifier-density regimes (Q33, Q66, Q100), retaining 33%, 66%, and 100% of qualifier pairs respectively, to study robustness to metadata availability. • HR-NBFNet and MT-HR-NBFNet. HR-NBFNet extends NBFNet to the hyper-relational setting by injecting qualifier context at every message-passing step. MT-HR-NBFNet augments this backbone with joint prediction of tail, relation, and qualifier-value objectives within a single Bellman–Ford pass at no additional graph-traversal cost. • AlertStar and MT-AlertStar. AlertStar fuses qualifier-aware multi-head cross-attention with a learned path-composition branch via a trainable scalar gate, operating entirely in embedding space without graph traversal, yielding more stable optimisation on sparse, inductive alert graphs than HR-NBFNet. MT-AlertStar extends this with joint prediction from a shared Transformer encoder, completing a symmetric multi-task design across paradigms with stronger qualifier supervision than graph-propagation alternatives. • HR-NBFNet-CQ. HR-NBFNet-CQ extends qualifier-aware representations to answer four first-order logic query types — one-hop (1p), two-hop chain (2p), two-anchor intersection (2i), and two-anchor union (2u) — enabling complex multi-condition threat investigations directly over the alert knowledge graph. • Comprehensive evaluation. We evaluate all five models against state-of-the-art HR-KGC baselines under inductive settings, with complexity analysis showing AlertStar achieves up to 50\times per-epoch speedup over HR-NBFNet, and four ablation studies (A1–A4) dissecting component contributions and qualifier-density sensitivity. The remainder of this paper is organised as follows. Section II introduces background on hyper-relational KGs and the threat model. Section III formalises the problem and presents the five models. Section IV describes experiments and evaluation. Section V reviews related work. Section VI analyses results. Section VII concludes and outlines future work. II Preliminaries and Threat Model This section introduces the formal background required for the remainder of the paper, and defines the operational threat model and assumptions under which the proposed models are evaluated. II-A Knowledge Graphs Definition II.1 (Knowledge Graph) . A knowledge graph is a directed, labeled multigraph \mathcal{G}=(\mathcal{E},\mathcal{R},\mathcal{T}) , where \mathcal{E} is a finite set of entities, \mathcal{R} is a finite set of relation types, and \mathcal{T}\subseteq\mathcal{E}\times\mathcal{R}\times\mathcal{E} is a set of facts, each represented as a triple (h,r,t) with head entity h\in\mathcal{E} , relation r\in\mathcal{R} , and tail entity t\in\mathcal{E} . In the network alert setting, \mathcal{E} is the set of observed IP addresses, \mathcal{R} is the set of attack categories (e.g., Recon, DoS, DDoS, Anomaly), and each triple (h,r,t)\in\mathcal{T} records that source IP h launched an attack of type r against destination IP t . Definition II.2 (Knowledge Graph Completion) . Given a knowledge graph \mathcal{G} , the knowledge graph completion (KGC) task is to score and rank candidate tail entities t^{\prime} for an incomplete query (h,r,?) , or equivalently candidate head entities h^{\prime} for a query (?,r,t) , using a scoring function f:\mathcal{E}\times\mathcal{R}\times\mathcal{E}\rightarrow\mathbb{R} . Applied to alert prediction, the KGC task answers: given that source IP h is conducting an attack