Community features in malware graphs do not boost stability under distribution shifts
Partition-Matched Evaluation of Community Features under Distribution Shift in Android Malware Function-Call Graphs
Cryptography and Security
Summary
Detecting malware on Android devices can be done by looking at how functions call each other in the app's code. The authors checked if grouping these calls into communities helps keep detection accurate when the type of malware changes. They found that these community patterns add some signal but do not consistently improve detection stability compared to random groupings. This shows that careful testing against random controls is needed before claiming that such community patterns help with malware detection under changing conditions.
What this means in practice
- •For security analysts: Avoid relying on mesoscopic graph communities alone for malware detection stability under malware-type changes.
- •For graph algorithm engineers: Use partition-matched controls to evaluate community-based features to prevent misleading results from random graph structures.
Authors
Junru Zhu, Yixin Yang, Xiaoqing Ding, Ruoyu Qi
Abstract
Graph-based Android malware classifiers can lose accuracy under malware-type or family shifts. We test whether mesoscopic organization in function-call graphs provides shift-stable information beyond local degree profiles (LDP), global statistics, lightweight metadata, and size-matched random partitions. Using 15,000 MalNet-Tiny, Common, and Distinct graphs, six Leiden descriptors specified before evaluation, and five optimizer seeds, communities raise Tiny macro F1 from 78.7% to 81.3% but yield 29.4-point source-only Common degradation. One size-matched random partition yields 27.8-point degradation. Across five random partitions, mean degradation is 27.9 points; the 95% two-level bootstrap interval for random minus community degradation is [-4.2, 1.2] points. With metadata, the corresponding difference is -0.2 points with interval [-1.1, 0.6]. Removing modularity raises structure-only Common macro F1 from 51.9% to 53.6%. The tested signature adds IID signal but shows no repeatable shift-stability advantage, demonstrating why mesoscopic graph claims need partition-matched controls and repeated null draws.