Jun 2026· 2026 IEEE Cloud Summit· pp. 192-197· 0 citations· 24 references
Abstract
Graph embeddings offer a principled way to discover coordinated attack patterns in security telemetry, but their hyperparameters are typically inherited from social-network benchmarks without validation. We conduct a systematic sensitivity analysis of Node2Vec on a heterogeneous security event graph derived from production AWS cloud telemetry (237 entities, 500+ relationships), varying six hyperparameters across 81 experimental configurations. Our central finding: the number of random walks dominates all other parameters (composite importance 1.00) through a non-monotonic relationship: clustering quality peaks sharply at r=100 (silhouette ≈0.56) then degrades to 0.27 at r=300. We attribute this to over-smoothing: in sparse, heterogeneous graphs, excessive walks cause node representations to collapse toward a mean, destroying the discriminative structure that separates attack phases. By contrast, the biased-walk parameters p and q, which receive the most practitioner attention, rank last in importance. Four recovered clusters map cleanly to MITRE ATT&CK kill chain phases. These results challenge the "more sampling is better" assumption and provide actionable, empirically-grounded configuration guidance for practitioners deploying graph-based threat detection on investigation-scale security graphs.
: Social network platforms have become primary channels for information dissemination, yet they are increasingly exploited by anomalous users such as bots, fake accounts, and coordinated disinformation spreaders. These malicious actors manipulate public opinion, spread misinformation and undermine platform integrity, posing severe threats to the security of the online ecosystem. Accurate detection of such users is challenging because they often organize into sophisticated high-order connection patterns that extend beyond local neighborhoods. Existing methods address this by either injecting predefined motifs as handcrafted features, which lack flexibility to discover unknown patterns, or employing higher-order Graph neural networks (GNNs) at prohibitive costs. Crucially, neither method treats structural information as learnable knowledge that can be automatically acquired from data and explicitly represented. To bridge this gap, we propose SparseGNN, a structural-knowledge-enhanced framework for anomalous user detection. It regards atomic subgraph patterns as fundamental, learnable units of structural knowledge. This framework is concatenated with original node features and fed into any standard GNN, without modifying the backbone architecture. Experiments on real-world datasets demonstrate that SparseGNN improves the accuracy and F1-score of standard GNNs for anomalous users detection without requiring predefined patterns, while maintaining linear complexity. Because the learned atomic patterns capture global high-order topology, the resulting structural knowledge representation is inherently less sensitive to localized edge perturbations, incidentally conferring improved stability under adversarial structural attacks.
Zehan Li, Yingyi Li, Zhiwei Tang et al.· Computers, Materials & C...· 0 citations
Post-hoc Graph Neural Network (GNN) explainers commonly follow a Perturb-Query paradigm, inferring the importance of graph elements based on queried predictions to perturbed inputs. However, such perturbations often introduce substantial distribution shift, undermining the reliability of the queried predictions used to derive explanations. While existing efforts mainly improve perturbed graphs or stabilize model predictions on them, we revisit the perturbation mechanism itself. We show that the widely used Element-wise Masking(EM) suppresses edge-induced messages toward zero, causing deterministic scale contraction that accumulates across message-passing layers, a phenomenon we term Scale Drift. Consequently, prediction changes under EM may conflate information corruption with deviations in propagation scale. As a scale-stable alternative to EM, we introduce Noise Corruption (NC), which perturbs each message through matched-norm random-direction corruption while preserving the expected squared message norm. Building on NC, we propose NICE, a Noise Corruption-based explanation framework, which learns a Stochastic Restoration Boundary (SRB) under NC-induced uncertainty, balancing target-prediction restoration against compactness. Furthermore, Boundary-Integrated Gradient (BIG) converts this boundary into edge attributions by accumulating each edge's contribution to reducing restoration risk along the restoration path. Experiments across multiple benchmarks demonstrate stronger explanation performance and model faithfulness while confirming that NC substantially reduces the Scale Drift induced by masking.
Ziluowen Luo, Jun Yin, Ruochen Liu et al.· 0 citations
This work demonstrates that an adversary can use the generator-discriminator technique to reconstruct high-quality graphs in real-world black-box attack scenarios against GNNs, and shows that GNNs are highly vulnerable to privacy attacks, varying Laplacian noise-scales.
Graph Neural Networks (GNNs) suffer from two fundamental limitations: over-smoothing, where node representations become indistinguishable with depth, and over-squashing, where long-range information is compressed through limited message-passing channels. Existing metrics such as Dirichlet energy provide global characterizations of over-smoothing but lack the resolution to analyze node-level behavior and guide architectural improvements. In this paper, we propose LEED (Local Embedding Evolution Distance), a novel local metric that quantifies over-smoothing by tracking the evolution of individual node embeddings across layers. By operating at the node level, LEED enables fine-grained analysis of representation dynamics during training, revealing heterogeneous over-smoothing patterns that are invisible to global energy-based measures. This locality induces informative node importance scores, interpreted as embedding-driven centrality measures. We leverage LEED to design a more efficient strategy for virtual node selection. Unlike existing approaches that depend on multiple heuristic centrality measures, our method uses LEED as a unique criterion to guide the construction of Local Virtual Nodes to mitigate over-squashing. Experiments show that LEED provides more informative diagnostics than Dirichlet energy while preserving global evaluation, and enables more effective virtual node integration, improving GNN performance across datasets.
With the increasing heterogeneity of social networks and online interaction systems, generalist graph anomaly detection (GAD) has become essential for identifying abnormal and fraudulent behaviors in complex environments. However, most existing GAD approaches rely heavily on domain-specific semantic alignment, which substantially restricts their ability to learn transferable node representations and often leads to poor generalization on unseen graph domains. To address this challenge, we propose HIerarchical Interaction MOdeling for zero-shot generalist GAD (termed HIMO-GAD). HIMO-GAD enables anomaly detection across diverse graph domains without retraining or access to target-domain supervision by modeling the evolutionary trajectories of node representations across hierarchical structural depths, thereby capturing interaction patterns that exhibit strong cross-domain stability. Specifically, HIMO-GAD integrates two core components: (1) a Dynamic Interaction Modeling Module that characterizes cross-layer interaction evolution to extract transferable representations, and (2) an Anomaly-Aware Regulation Mechanism that combines gradient immunity and centralization regularization to suppress overfitting and stabilize cross-domain generalization. Extensive experiments on multiple real-world graph datasets demonstrate that HIMO-GAD consistently outperforms state-of-the-art baselines in strict zero-shot settings, achieving up to a 10% improvement in key evaluation metrics and exhibiting strong generalization across heterogeneous graph domains.
Xiangping Zheng, Xuan Feng, Bo Wu et al.· Proceedings of the 32nd ACM...· 0 citations
Enterprise security demands actionable threat prioritization across heterogeneous environments. To address the limitations of siloed log analysis, we propose a multi-source, graph-based anomaly detection framework. First, our architecture seamlessly fuses network telemetry from Vectra, Security Information and Event Management (SIEM) logs from QRadar, and endpoint data from CrowdStrike into a unified graph. Second, we utilize the Louvain algorithm to segment the network, identifying functional communities and critical bridge nodes indicative of lateral movement. Third, we extract over 50 structural, behavioral, and temporal features to train an XGBoost-based ensemble classifier. Evaluated on a real-world banking dataset with 31 anomaly types, the proposed system achieves 98% precision. Crucially, empirical analysis reveals that local neighborhood connectivity and traffic dynamics significantly outperform traditional global centrality metrics in detecting complex attacks. Finally, to support operational incident response, we implement a dynamic risk-scoring mechanism that translates model predictions into actionable, IP-level severity assessments across sliding time windows. Ultimately, this framework substantially enhances comprehensive threat visibility and analyst efficiency.
Çagatay Ates, Ilgin Safak, Fatih Alagöz et al.· International Conference on...· 0 citations