Out-of-sample Node Representation Learning for Heterogeneous Graph in Real-time Android Malware Detection

Yanfang Ye, Shifu Hou, Lingwei Chen, Jingwei Lei, Wenqiang Wan, Jiabin Wang, Qi Xiong, Fudong ShaoIJCAI 2019 · OpenReview

Abstract

The increasingly sophisticated Android malware calls for new defensive techniques that are capable of protecting mobile users against novel threats. In this paper, we first extract the runtime Application Programming Interface (API) call sequences from Android apps, and then analyze higher-level semantic relations within the ecosystem to comprehensively characterize the apps. To model different types of entities (i.e., app, API, device, signature, affiliation) and rich relations among them, we present a structured heterogeneous graph (HG) for modeling. To efficiently classify nodes (e.g., apps) in the constructed HG, we propose the HG-Learning method to first obtain in-sample node embeddings and then learn representations of out-of-sample nodes without rerunning/adjusting HG embeddings at the first attempt. We later design a deep neural network classifier taking the learned HG representations as inputs for real-time Android malware detection. Comprehensive experiments on large-scale and real sample collections from Tencent Security Lab are performed to compare various baselines. Promising results demonstrate that our developed system AiDroid which integrates our proposed method outperforms others in real-time Android malware detection.

Introduction

Android malware has evolved significantly, adopting complex "Command and Control" (C&C) tactics to evade traditional detection. These malicious applications often remain dormant until specific conditions are met, making static analysis insufficient. Heterogeneous Graphs (HGs) have emerged as a powerful tool to model the intricate relationships within the Android ecosystem—connecting apps through shared developers, device identifiers (IMEI), signatures, and API call sequences.

However, a significant bottleneck exists: the out-of-sample problem. Most graph embedding techniques are transductive, meaning they can only represent nodes present during the initial training phase. In a production environment where thousands of new apps are released daily, rerunning graph embeddings for every new sample is computationally prohibitive. This paper introduces AiDroid, a framework designed to solve this problem by enabling real-time classification of new nodes without retraining the entire graph.

The AiDroid Framework

AiDroid operates by first constructing a comprehensive HG that captures the semantic richness of the Android environment. It models five entity types: Apps, APIs, IMEIs, Signatures, and Affiliations. To ensure the graph captures meaningful behavioral patterns, the system utilizes six expert-defined meta-paths (PID1-PID6), such as App → API → App or App → Signature → App.

Overview of the AiDroid framework architecture, from feature extraction to DNN classification.

HG-Learning: Solving the Out-of-Sample Problem

The core innovation of AiDroid is the HG-Learning method, which consists of two distinct phases:

  1. HGiNE (In-sample Embedding): For known apps, the system performs meta-path guided random walks. These walks capture high-level semantic relationships and are processed via a skip-gram model to generate $d$-dimensional embedding vectors for each node.
  2. HG2Img (Out-of-sample Representation): To handle a new, unknown app, AiDroid avoids recalculating the entire graph. Instead, it constructs a $t \times d$ matrix that represents the app's "neighborhood." This matrix stacks the pre-calculated embeddings of the app's $k$-order neighbors (e.g., the APIs it invokes or its developer's signature). By treating the app as the sum of its connections, the system creates a robust representation for nodes that were not part of the original training set.
Detailed HG-Learning process illustrating the transition from graph nodes to matrix representations (HG2Img).

These neighborhood matrices are then fed into a Deep Neural Network (DNN) Classifier. The classifier uses a CNN-based architecture with Inception modules to identify local patterns within the neighborhood matrix, effectively determining the maliciousness of the app based on the "company it keeps."

Experimental Evaluation

The system was evaluated using a massive dataset from Tencent Security Lab, comprising over 190,000 training apps and 17,000 newly arriving test apps. The resulting graph contained over 4.1 million edges.

  • Accuracy: AiDroid achieved an Accuracy (ACC) of 0.9908 and an F1 score of 0.9817, significantly outperforming traditional graph methods like DeepWalk and metapath2vec.
  • Efficiency: The average detection time was a mere 4.3 ms per app, meeting the requirements for real-time mobile security scanning.
  • Robustness: Interestingly, the HG2Img approach outperformed a baseline that completely reran the graph embedding for new nodes (0.9843 ACC), suggesting that the matrix-based neighborhood representation is more resilient to the noise of new samples.

Conclusion

AiDroid successfully bridges the gap between complex graph-based modeling and the requirements of real-time malware detection. By representing out-of-sample nodes through their latent neighborhood space, the system eliminates the need for costly retraining while maintaining state-of-the-art accuracy. Future work will explore the "cold start" problem for apps with no known neighbors and the optimization of dynamic analysis overhead.

Summary updated

Abstract

The increasingly sophisticated Android malware calls for new defensive techniques that are capable of protecting mobile users against novel threats. In this paper, we first extract the runtime Application Programming Interface (API) call sequences from Android apps, and then analyze higher-level semantic relations within the ecosystem to comprehensively characterize the apps. To model different types of entities (i.e., app, API, device, signature, affiliation) and rich relations among them, we present a structured heterogeneous graph (HG) for modeling. To efficiently classify nodes (e.g., apps) in the constructed HG, we propose the HG-Learning method to first obtain in-sample node embeddings and then learn representations of out-of-sample nodes without rerunning/adjusting HG embeddings at the first attempt. We later design a deep neural network classifier taking the learned HG representations as inputs for real-time Android malware detection. Comprehensive experiments on large-scale and real sample collections from Tencent Security Lab are performed to compare various baselines. Promising results demonstrate that our developed system AiDroid which integrates our proposed method outperforms others in real-time Android malware detection.
BibTeX
@inproceedings{ye2019out,
  author = {Yanfang Ye and Shifu Hou and Lingwei Chen and Jingwei Lei and Wenqiang Wan and Jiabin Wang and Qi Xiong and Fudong Shao},
  title = {{Out-of-sample Node Representation Learning for Heterogeneous Graph in Real-time Android Malware Detection}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=NLBaRiZtkj},
}
Figure