Edge weight concentration overcomes node degree blindness in graph based network intrusion detection

Abstract

Graph-based network intrusion detection almost universally represents attacker behavior through node-centric structural features – degree, centrality, embeddings from graph neural networks – which implicitly assume that an attacker’s identity is visible as a distinct node in the host-communication graph. We show that this assumption breaks under a common, realistic condition: network address translation (NAT) or perimeter aggregation, which collapses many real hosts onto a small number of gateway addresses. Using real, labeled flow data from the CICIDS2017 benchmark (Friday afternoon distributed denial-of-service capture, 225,745 flows), we construct time-windowed directed host-communication graphs and show that, at the observed collapse ratio, node-degree features are statistically indistinguishable from benign traffic (Mann-Whitney \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p=0.12$$\end{document}–0.83 across four window sizes, which are nested aggregations of one underlying one-minute-resolution timestamp field rather than independent replications) while edge-weight concentration separates attack from benign windows with p ranging from \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$3.9\times 10^{-12}$$\end{document} at 60 seconds to 0.017 at 10 minutes (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n=3$$\end{document} attack windows at that resolution). Rather than inferring causation from one fixed collapse ratio, we directly test it with a controlled semi-synthetic sweep that redistributes the real attack’s flow volume across a varying number k of synthetic source identities: node-degree separation rises monotonically from chance (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {AUC}=0.61$$\end{document}) to perfect (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {AUC}=1.00$$\end{document}) as k grows from 1 to 128, while edge-weight separation is perfect only near full collapse (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k\le 2$$\end{document}) and falls to near-chance once attacker identity becomes even partially visible (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k\ge 4$$\end{document}) – direct evidence that the two feature families are complementary along the collapse axis rather than one uniformly dominating the other. At the flow level, a compact graph-context feature set – with a near-tautological heaviest-edge indicator removed and evaluated under window-grouped cross-validation to prevent information leakage between flows sharing a time window – reaches F1 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$=0.981$$\end{document} at 9 dimensions against a 78-dimensional CICFlowMeter baseline’s F1 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$=0.998$$\end{document}, at roughly one-tenth the training cost. We report this as a single-attack-type case study in which the identity-collapse mechanism is now measured directly rather than asserted, and we state explicitly what further validation against other attack archetypes would require.