AsymGAD: Label-Free Lateral-Movement Pivot Ranking via Asymmetric Graph Anomaly Detection

Enterprise authentication activities naturally form graph-structured data that capture interactions among machines, users, and administrative services. Correspondingly, graph anomaly detection (GAD) provides a promising paradigm for identifying compromised machines involved in lateral movement, where attackers expand access by reusing legitimate credentials and services. However, detecting the intermediate stepping stones, or pivots, remains challenging because malicious authentication behavior often resembles routine activity, while the underlying interaction patterns continuously evolve over time. To address these challenges, we propose AsymGAD, a label-free GAD framework for ranking suspicious pivot machines in continuous authentication streams. AsymGAD first constructs evidence-sufficient observation graphs directly from the event stream, allowing graph boundaries to adapt to changing activity rather than relying on externally specified snapshots. It then introduces directional expansion as an explicit structural prior to capture machines whose outgoing behavior is disproportionately strong relative to their incoming activity, providing an interpretable signal of pivot behavior. Furthermore, AsymGAD incorporates causal information across consecutive observation graphs to distinguish persistent benign infrastructure from transient suspicious behavior, while a lightweight directed graph neural network captures complementary relational patterns beyond node-level statistics. By integrating adaptive graph construction, asymmetric structural cues, temporal context, and learned graph representations, AsymGAD enables label-free and interpretable pivot prioritization in large-scale authentication networks. Extensive experiments on a billion-event enterprise authentication stream demonstrate the effectiveness and scalability of AsymGAD for identifying compromised pivot machines under realistic large-scale conditions.