AlertStar: Path-Aware Alert Prediction on Hyper-Relational Knowledge Graphs

Zahra Makki Nayeri; Mohsen Rezvani

cs.CRApr 3, 2026

AlertStar: Path-Aware Alert Prediction on Hyper-Relational Knowledge Graphs

Authors: Zahra Makki Nayeri, Mohsen Rezvani

Organizations: Faculty of Computer Engineering at Shahrood University of Technology, Shahrood, Iran.

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, Q), where h and t are source and destination IPs, r denotes the attack type, and Q encodes flow-level metadata such as timestamps, ports, protocols, and attack intensity, going beyond standard KGC binary triples (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.

Figures & tables

Fig. 1: Three representational levels: (A) triple-based facts, (B) hyper-relational facts, (C) path-based hyper-relational reasoning.

Detect Time	Flow Count	Source IP $(h)$	Target IP $(t)$	Port	Protocol	Category $(r)$
2019-03-11 00:05	17,094	185.192.59.136	142.252.135.136	22	TCP	Recon Scan
2019-03-12 00:45	5,113	78.234.46.141	142.252.32.63	443	TCP	Availability DoS
2019-03-14 00:25	15	185.192.59.136	142.252.32.63	81	TCP	Availability DDoS
2019-03-14 00:25	39	78.234.46.141	142.252.32.63	22	UDP	Anomaly Traffic
Qualified-statement mapping for row 1:
$h$ = 185.192.59.136, $r$ = Recon Scan, $t$ = 142.252.135.136

TABLE I: Example alert records and their qualified-statement representation

(h,r,t,\mathcal{Q})

. The qualifier set

\mathcal{Q}

encodes detect time, flow count, port, and protocol.

Fig. 2: HR-NBFNet combines StarE qualifier encoding [ 3 ] with NBFNet Bellman-Ford propagation [ 6 ] . Qualifier pairs are composed via

\phi_{q}

, aggregated, projected by

\mathbf{W}_{q}

, and merged with

\mathbf{h}_{r}

via

\gamma

, injecting flow-level context into the pair representation

\mathbf{h}_{uvqq^{\prime}}^{(t)}

at every layer. Inverse edges

(t,r^{-1},h)

enable bidirectional propagation for both tail and head prediction.

Fig. 3: Architecture of AlertStar. Qualifier pairs are aggregated into

\mathbf{U}_{\mathcal{Q}}

and used as key/value in MHA with

\mathbf{e}_{r}

as query, producing

\tilde{\mathbf{e}}_{r}

. Two branches — cross-attention and path-composition — are fused via a trainable gate

\alpha=\sigma(g)

into

\mathbf{z}

, scored against candidate tails via dot product.

Fig. 4: Architecture of MT-AlertStar. The masked token sequence

\mathbf{X}

is encoded by a Transformer, whose relation-token output

\mathbf{h}_{r}=\mathbf{H}[1]

serves as shared context for three MLP heads predicting tail, relation, and qualifier value jointly.

Fig. 5: Hyper-relational query templates. Qualifier pairs on each edge may vary from

0

n

Model	Complexity	Graph Traversal?
AlertStar	$O(nd+d^{2}+Nd)$	No
MT-AlertStar	$O(S^{2}d+SdF+Nd)$	No
HR-NBFNet-CQ	$O(nd+d^{2}+Nd)$	No
HR-NBFNet	$O(LEQd+Nd^{2})$	Yes
MT-HR-NBFNet	$O(LEQd+Nd^{2})$	Yes

TABLE II: Per-sample inference complexity.

N{=}|\mathcal{E}|

E{=}|\mathcal{T}|

L{=}

layers,

Q{=}Q_{\max}

n{=}|\mathcal{Q}|

S{=}3{+}2n

F{=}

FFN width.

Paradigm I: Graph Propagation
	Inductive					Transductive
Model	MR $\downarrow$	MRR $\uparrow$	H@1 $\uparrow$	H@3 $\uparrow$	H@10 $\uparrow$	MR $\downarrow$	MRR $\uparrow$	H@1 $\uparrow$	H@3 $\uparrow$	H@10 $\uparrow$
HR-NBFNet	4616.2	0.4666	0.4332	0.4791	0.5283	4182.4	0.4785	0.4408	0.4956	0.5465
MultiTask HR-NBFNet	5229.5	0.4729	0.4373	0.4849	0.5528	589.8	0.4134	0.3782	0.4171	0.4926
Paradigm II: Embedding-Based
AlertStar	2645.2	0.4280	0.3400	0.4900	0.5620	3083.1	0.4620	0.3980	0.5040	0.5640

TABLE III: KGC results on the Warden Alert dataset using statements under inductive and transductive settings.

	Inductive					Transductive
Model	MR $\downarrow$	MRR $\uparrow$	H@1 $\uparrow$	H@3 $\uparrow$	H@10 $\uparrow$	MR $\downarrow$	MRR $\uparrow$	H@1 $\uparrow$	H@3 $\uparrow$	H@10 $\uparrow$
33%
ShrinkE	2724.0	0.4665	0.4380	0.4760	0.5220	3087.2	0.5012	0.4820	0.5060	0.5400
StarE	2858.4	0.4205	0.3640	0.4520	0.5300	3262.7	0.4451	0.3940	0.4680	0.4940
AlertStar	2765.3	0.4371	0.3520	0. 5040	0.5840	3031.6	0.4627	0.3840	0.5280	0.5920
MultiTask AlertStar	2680.2	0.5860	0.5400	0.6100	0.6850	3174.2	0.5582	0.5200	0.5750	0.6350

TABLE IV: KGC results on the Warden Alert dataset using statements under the inductive and transductive settings.

	Inductive					Transductive
Model	MR $\downarrow$	MRR $\uparrow$	H@1 $\uparrow$	H@3 $\uparrow$	H@10 $\uparrow$	MR $\downarrow$	MRR $\uparrow$	H@1 $\uparrow$	H@3 $\uparrow$	H@10 $\uparrow$
33%
ShrinkE	4.2680	0.4220	0.2200	0.5000	1.000	4.2880	0.4083	0.2020	0.4800	1.000
StarE	4.1460	0.4367	0.2280	0.5480	0.996	4.1560	0.4267	0.2160	0.5080	1.000
AlertStar	3.9300	0.4497	0.2240	0.5640	1.000	4.0140	0.4394	0.2260	0.5300	1.000
MultiTask AlertStar	3.9350	0.4490	0.2350	0.5400	1.000	3.9250	0.4626	0.2600	0.5500	1.000

TABLE V: KGC results on the UNSW dataset using statements under the inductive and transductive settings.

	Q33%			Q66%			Q100%
Model	MRR	H@1	H@10	MRR	H@1	H@10	MRR	H@1	H@10
StarE	0.2783	0.0940	0.5140	0.3442	0.2180	0.5140	0.4051	0.3140	0.5340
AlertStar	0.4282	0.3380	0.5760	0.4167	0.3340	0.5440	0.4313	0.3420	0.5820
HyNT	0.5632	0.5140	0.6460	0.5726	0.5320	0.6440	0.5692	0.5280	0.6460
MultiTask AlertStar	0.5546	0.5040	0.6520	0.5663	0.5200	0.6540	0.5531	0.5060	0.6460

TABLE VI: Ablation A4: Model performance across qualifier density levels (inductive).

	Inductive					Transductive
Model	MR $\downarrow$	MRR $\uparrow$	H@1 $\uparrow$	H@3 $\uparrow$	H@10 $\uparrow$	MR $\downarrow$	MRR $\uparrow$	H@1 $\uparrow$	H@3 $\uparrow$	H@10 $\uparrow$
ShrinkE	2699.4	0.4580	0.4140	0.4840	0.5320	2889.4	0.4998	0.4680	0.5180	0.5500
StarE	2760.9	0.4098	0.3400	0.4680	0.5300	3150.9	0.4503	0.4000	0.4860	0.5460
NBFNet	3616.5	0.4853	0.4481	0.5060	0.5480	4524.8	0.4818	0.4451	0.5019	0.5511
AlertStar	2561.0	0.4565	0.3720	0.5140	0.5920	2746.2	0.4862	0.4320	0.5140	0.5840
MultiTask AlertStar (Tail+Rel)	2430.0	0.5860	0.5450	0.6000	0.6750	3138.6	0.5762	0.5450	0.5900	0.6400

TABLE VII: KGC results on the Warden Alert dataset using triples under inductive and transductive settings.

	Inductive					Transductive
Model	MR $\downarrow$	MRR $\uparrow$	H@1 $\uparrow$	H@3 $\uparrow$	H@10 $\uparrow$	MR $\downarrow$	MRR $\uparrow$	H@1 $\uparrow$	H@3 $\uparrow$	H@10 $\uparrow$
ShrinkE	4.1380	0.4405	0.2400	0.5320	1.000	4.1360	0.4305	0.2220	0.5140	1.000
StarE	4.1300	0.4445	0.2460	0.5240	0.996	4.1300	0.4163	0.1980	0.5120	1.000
NBFNet	4.2405	0.4288	0.2252	0.5120	1.000	4.2484	0.4279	0.2228	0.5142	1.000
AlertStar	4.0060	0.4469	0.2320	0.5480	1.000	4.0060	0.4355	0.2220	0.5320	1.000
MultiTask AlertStar (Tail+Rel)	3.9500	0.4409	0.2150	0.5850	1.000	3.9700	0.4519	0.2550	0.5200	1.000

TABLE VIII: KGC results on the UNSW dataset using triples under inductive and transductive settings.

StarQE
	Inductive
	33%					66%					100%
Query	MR $\downarrow$	MRR $\uparrow$	H@1 $\uparrow$	H@3 $\uparrow$	H@10 $\uparrow$	MR $\downarrow$	MRR $\uparrow$	H@1 $\uparrow$	H@3 $\uparrow$	H@10 $\uparrow$	MR $\downarrow$	MRR $\uparrow$	H@1 $\uparrow$	H@3 $\uparrow$	H@10 $\uparrow$
1p	43.810	0.4875	0.460	0.475	0.555	79.305	0.4600	0.440	0.445	0.495	53.820	0.5103	0.4950	0.5050	0.5350
2p	100.66	0.0176	0.000	0.000	0.000	51.250	0.2611	0.250	0.250	0.250	34.545	0.6694	0.6363	0.7272	0.7272
2i	26.545	0.3584	0.005	0.685	0.715	31.965	0.3454	0.010	0.655	0.700	33.575	0.6835	0.6750	0.6750	0.6900

TABLE IX: Complex query answering results on the Warden Alert dataset under the inductive and transductive settings.

StarQE
	Inductive
	33%					66%					100%
Query	MR $\downarrow$	MRR $\uparrow$	H@1 $\uparrow$	H@3 $\uparrow$	H@10 $\uparrow$	MR $\downarrow$	MRR $\uparrow$	H@1 $\uparrow$	H@3 $\uparrow$	H@10 $\uparrow$	MR $\downarrow$	MRR $\uparrow$	H@1 $\uparrow$	H@3 $\uparrow$	H@10 $\uparrow$
1p	3.125	0.5368	0.335	0.665	1.000	3.340	0.5026	0.290	0.615	1.000	3.000	0.5228	0.290	0.685	1.000
2p	1.950	0.6633	0.435	0.950	1.000	1.715	0.7399	0.560	0.960	1.000	1.775	0.7469	0.580	0.940	1.000
2i	3.385	0.5149	0.310	0.645	1.000	3.730	0.4627	0.250	0.550	1.000	3.395	0.4995	0.275	0.630	0.995

TABLE X: Complex query answering results on the UNSW dataset under the inductive and transductive settings.

Tail Prediction
	Inductive			Transductive
Metric	33%	66%	100%	33%	66%	100%
MR	2680.2	2532.5	2978.0	3174.2	3329.0	3307.0
MRR	0.5860	0.5968	0.5838	0.5582	0.5329	0.5477
H@1	0.5400	0.5600	0.5400	0.5200	0.5000	0.5150
H@3	0.6100	0.6100	0.6050	0.5750	0.5550	0.5650

TABLE XI: MT-AlertStar on Warden.

Tail Prediction
	Inductive			Transductive
Metric	33%	66%	100%	33%	66%	100%
MR	3.9	3.7	3.6	3.9	3.8	4.0
MRR	0.4491	0.5023	0.4810	0.4626	0.4753	0.4641
H@1	0.2350	0.3200	0.2700	0.2600	0.2750	0.2650
H@3	0.5400	0.5800	0.6050	0.5500	0.5750	0.5550

TABLE XII: MT-AlertStar on UNSW-NB15.

Fig. 6: Gate value

\alpha=\sigma(g)

over 20 epochs on Warden.

Variant	Qual	Path	Gate	MR	MRR	H@1	H@3	H@10
AS-NoQual	✗	✓	learned	2712.7	0.4423	0.352	0.518	0.584
AS-NoPath	✓	✗	learned	2673.1	0.4454	0.354	0.508	0.590
AS-NoGate	✓	✓	fixed=0.5	2809.9	0.4445	0.358	0.500	0.580
AS-Full	✓	✓	learned	2615.2	0.4418	0.360	0.500	0.570

TABLE XIII: Ablation A1: AlertStar component ablation.

Variant	Tasks	MR	MRR	H@1	H@3	H@10
MT-TailOnly	tail	3210.0	0.5607	0.512	0.594	0.650
MT-Tail+Rel	tail, relation	2998.3	0.5604	0.514	0.586	0.646
MT-Tail+QualVal	tail, qual_value	2881.2	0.5633	0.516	0.600	0.648
MT-Full	tail, relation, qual_val	3100.6	0.5610	0.518	0.584	0.640

TABLE XIV: Ablation A3: MultiTask auxiliary.

Zahra Makki Nayeri is a Ph.D. candidate at Shahrood University of Technology and currently a visiting researcher at the University of Stuttgart, Germany, where she conducts research on knowledge graph foundation models. Her research focuses on graph representation learning, temporal and dynamic graph neural networks, and machine learning–based modeling of computer networks, with an emphasis on data-driven analysis of large-scale, evolving interaction graphs. During her Master’s studies, she investigated machine learning techniques for fog, edge, and cloud computing environments, with a particular focus on distributed data processing, resource-aware learning, and system-level optimization.

Table 21

Mohsen Rezvani is an Associate Professor in the Faculty of Computer Engineering at the Shahrood University of Technology. He received his Ph.D. at the School of Computer Science and Engineering at the UNSW Sydney. He holds an M.Sc. in Computer Engineering from Sharif University of Technology and a B.Sc. in Computer Engineering from Amirkabir University of Technology. His research focuses on computer security, intelligent data analysis, and advanced machine learning. He is the director of the Computer Emergency Response Team (CERT) at Shahrood University of Technology.

Table 22

Explore similar work

Apr 3, 2026

BiTA: Bidirectional Gated Recurrent Unit-Transformer Aggregator in a Temporal Graph Network Framework for Alert Prediction in Computer Networks

Proactive alert prediction in computer networks is critical for mitigating evolving cyber threats and enabling timely defensive actions. Temporal Graph Neural Networks (TGNs) provide a principled framework for modeling time-evolving interactions; however, existing TGN-based methods predominantly rely on unidirectional or single-mechanism temporal aggregation, which limits their ability to capture recursive, multi-scale temporal patterns commonly observed in real-world attack behaviors. In this paper, we propose BiTA, a Bidirectional Gated Recurrent Unit-Transformer Aggregator for temporal graph learning. Rather than introducing a deeper or higher-capacity model, BiTA redesigns the temporal aggregation function within the TGN framework by jointly encoding bidirectional sequential dependencies and long-range contextual relations over each node's temporal neighborhood. This aggregation strategy enables complementary temporal reasoning at different scales while preserving the original TGN memory and message-passing structure. We evaluate BiTA on real-world alert datasets, demonstrating significant improvements in key performance metrics such as area under the curve, average precision, mean reciprocal rank, and per-category prediction accuracy when compared to state-of-the-art temporal graph models. BiTA outperforms baseline methods under both transductive and inductive settings, highlighting its robustness and generalization capabilities in dynamic network environments. BiTA is a scalable and interpretable framework for real-time cyber threat anticipation, paving the way toward more intelligent and adaptive intrusion detection systems.

Zahra Makki Nayeri, Mohsen Rezvani

Faculty of Computer Engineering, Shahrood University of Technology, Shahrood, Iran

Temporal GNNs Cybersecurity Recurrent Transformers Temporal Attention

Ask PDF

Aug 13, 2026

Operationalizing Cyber Threat Intelligence with GraphRAG

When a security researcher publishes a report on a cyberattack, detection engineers are supposed to turn it into working detection rules. In practice, most automated attempts at this only extract the simplest clues from the report --- bad IP addresses, domain names, and file hashes --- and turn them into block lists. This is a weak strategy, because attackers can change these simple clues within hours or days, so the resulting detections stop working almost as soon as they are deployed. Security teams describe this idea with the Pyramid of Pain. This project asks whether feeding a report into a knowledge-graph retrieval system, Microsoft GraphRAG, rather than a standard vector-similarity retrieval system (Naive RAG), produces detection plans that rely more on these durable, top-of-pyramid clues. Both systems are given the same report, the same generation instructions, and the same language model to write the final plan; only the retrieval step differs. In a detailed case study of one APT28 report, the GraphRAG plan kept firing at 100% of its detections after every IP address, domain, and file hash in the report was rotated, while the Naive RAG plan kept firing at only 29%. Repeating the comparison across nine real CTI reports from four vendors confirms the same pattern: GraphRAG plans consistently reach higher, harder-to-evade levels of the pyramid, even when the two systems end up close on total score. The results support treating knowledge-graph-aware retrieval as the architecturally correct foundation for automatically generating SOC-deployable hunting plans, while showing that the wording of the generation prompt matters almost as much as the retrieval back-end itself.

Atul Kabra, Prakhar Paliwal, Manjesh K. Hanawal

MLiONS, Department of IEOR, IIT Bombay Mumbai, Maharashtra, India

Cyber Threat Intelligence Graph Retrieval-Augmented Generation Cybersecurity

Ask PDF

Feb 21, 2026

HEHRGNN: A Unified Embedding Model for Knowledge Graphs with Hyperedges and Hyper-Relational Edges

Knowledge Graph(KG) has gained traction as a machine-readable organization of real-world knowledge for analytics using artificial intelligence systems. Graph Neural Network(GNN), is proven to be an effective KG embedding technique that enables various downstream tasks like link prediction, node classification, and graph classification. The focus of research in both KG embedding and GNNs has been mostly oriented towards simple graphs with binary relations. However, real-world knowledge bases have a significant share of complex and n-ary facts that cannot be represented by binary edges. More specifically, real-world knowledge bases are often a mix of two types of n-ary facts - (i) that require hyperedges and (ii) that require hyper-relational edges. Though there are research efforts catering to these n-ary fact types, they are pursued independently for each type. We propose

H

yper

E

dge

H

yper-

R

elational edge

GNN

(HEHRGNN), a unified embedding model for n-ary relational KGs with both hyperedges and hyper-relational edges. The two main components of the model are i)HEHR unified fact representation format, and ii)HEHRGNN encoder, a GNN-based encoder with a novel message propagation model capable of capturing complex graph structures comprising both hyperedges and hyper-relational edges. The experimental results of HEHRGNN on link prediction tasks show its effectiveness as a unified embedding model, with inductive prediction capability, for link prediction across real-world datasets having different types of n-ary facts. The model also shows improved link prediction performance over baseline models for hyperedge and hyper-relational datasets.

Rajesh Rajagopalamenon, Unnikrishnan Cheramangalath

Department of Computer Science and Engineering, Indian Institute of Technology Palakkad, India

KG Embedding Knowledge Graphs KG Completion Hypergraph Neural Networks

Ask PDF