A Survey on Malware Detection with Graph Representation Learning

• Traditional signatures and heuristics generalize poorly to unknown malware and can be evaded through obfuscation, while behavior-based methods are time-consuming.Source: §1 · p. 2
• Graph representation learning is presented as a promising alternative because graph structures encode semantic relations and connectivity in malware programs.Source: §1 · p. 2
• The survey addresses an emerging literature gap by reviewing graph-based learning methods specifically for malware detection.Source: §1 · p. 2
• It organizes prior work around graph representations, common architectures, adversarial attacks against GNN-based detectors, challenges, and future research directions.Source: §1 · pp. 2–3

• Prior reviews cover traditional malware detection, including signatures, behaviors, heuristics, and some machine-learning methods.Source: §2 · p. 3
• Several surveys examine deep-learning methods for Android malware, including features, models, datasets, performance, and limited graph-based approaches [7].Source: §2 · p. 3
• Other work reviews traditional executable-file methods, cybersecurity representation learning, and deep learning across mobile, Windows, IoT, APT, and ransomware malware.Source: §2 · p. 3
• GNN surveys emphasize explainability or non-malware applications, leaving graph machine learning and graph representation learning for malware detection without a dedicated review [19] [20].Source: §2 · p. 3

3.1 Graph Structures

• Graphs model complex-system interactions using nodes and edges, with attributed and heterogeneous variants adding element features and type information.Source: §3.1 · p. 4
• Current graph-based malware-detection methods predominantly use the graph representations introduced in this section.Source: §3.1 · p. 4

3.2 Learning on Graphs

• Because graph nodes are interconnected rather than independent and uniformly distributed, conventional machine-learning operations cannot be directly applied.Source: §3.2 · p. 4, §3.2.2 · p. 4
• Representation learning maps malware input features into embeddings that retain essential information for downstream binary or multi-class classification.Source: §3.2.1 · p. 4

3.2.2 Graph Representation Learning.

• Graph representation learning handles non-Euclidean data by learning node, edge, or graph embeddings; graph classification is widely used to label malware binaries represented as graphs.Source: §3.2.2 · p. 5
• Early embedding methods use random walks and neighborhood-preserving objectives, while node2vec captures local and global structure through biased BFS- and DFS-like walks.Source: §3.2.2 · p. 5
• Walk-based methods can scale poorly with graph size, depend on hyperparameters, favor proximity over structure, and are often transductive rather than inductive.Source: §3.2.2 · p. 5

3.2.3 Graph Neural Networks.

• GNNs use spectral or spatial convolutions to exploit graph structure; spatial models include GCN, GraphSAGE, DGCNN, and GAT, with message passing, sampling, or attention mechanisms.Source: §3.2.3 · pp. 5–6

4 MALWARE DETECTION WITH GRAPHS

• Graph-based malware detection transforms extracted binary features into graph structures that are subsequently processed by downstream classifiers.The graph adds a representation-learning stage between feature extraction and classification.Source: §4 · p. 6

4.1 Modeling Malware as Graphs

• Effective malware representations should preserve program semantics, resist obfuscation, and remain independent of programming language and platform.Constructing representations satisfying all three conditions remains difficult because attacker techniques continually evolve.Source: §4.1 · p. 6
• Static analysis is relatively inexpensive and comprehensive, dynamic analysis captures runtime behavior and resists obfuscation better, and hybrid analysis combines their advantages.Dynamic analysis is resource-intensive and may miss parts of a program, whereas static analysis may miss runtime-only issues.Source: §4.1.1 · p. 6

4.1.2 Common Graph Structures for Malware Detection.

• Common graph structures include CFGs, FCGs, PDGs, system call graphs, system entity graphs, and network flow graphs, each encoding different program or execution relationships.CFGs model intra-procedural control flow, FCGs model inter-procedural calls, and PDGs capture data and control dependencies.Source: §4.1.2 · p. 7
• The survey covers graph-learning malware detection on Android, Windows, and Web platforms and organizes the literature by input graph structure.The categorization is summarized in Fig. 1.Source: §4.1.2 · pp. 7–8, Figure 1 · p. 8

4.2 Methodology of Malware Detection with Graph Representation Learning

• The general architecture extracts or observes code behavior, builds and optionally attributes a graph, learns node embeddings, pools them into a graph embedding, and classifies that vector.GNNs commonly learn embeddings from instructions, functions, or API calls, while some methods incorporate opcode or API word embeddings.Source: §4.2 · p. 8, Figure 2 · p. 9

5 GRAPH-BASED ANDROID MALWARE DETECTION

• The Android-focused review covers methods for constructing graphs from disassembled applications and applying graph representation learning to malware detection.The section proceeds from the general graph-building methodology to existing detection studies.Source: §5 · p. 9
• Android graph-based detection begins with graph construction from application code before reviewing downstream malware-detection approaches.Source: §5 · p. 9
• The scope is specifically the Android platform and its disassembled applications.Source: §5 · p. 9

5.1 Android-based Graph Structures

• APK packages contain code, resources, manifests, and assets, but graph-based approaches mainly use compiled code to represent application logic.Manifest metadata and media resources are relatively flat, whereas code can expose structured program behavior.Source: §5.1 · p. 9
• Static Android analysis disassembles Dalvik bytecode into smali code, enabling extraction of CFGs, FCGs, PDGs, and API-based representations.The compilation and disassembling pipeline is illustrated in Fig. 3.Source: §5.1 · p. 9, Figure 3 · p. 10
• Dynamic analysis records API-call and system-call sequences in a sandbox and can monitor network traffic by observing packets.Source: §5.1 · p. 10

5.2.1 CFG Approaches for Android Malware Detection.

• 97.09% F1-score was achieved by hybrid-Falcon on CICAndMal2017, improving on Hybroid’s 97% by representing network flows as images for bi-directional LSTM processing.Hybroid combines opcode, basic-block, CFG/FCG, and network-flow representations before gradient-boosting classification.Source: §5.2.1 · p. 10
• 92.7% F1-score was obtained for locating MITRE ATT&CK TTPs from CFG subgraphs using Inferential SIR-GN, random forest classification, and SHAP attribution.The approach identifies the subgraph responsible for each prediction.Source: §5.2.1 · p. 11

5.2.2 FCG Approaches for Android Malware Detection.

• 99.68% F1-score was reported on Drebin for a GCN-based FCG method using normalized adjacency with self-loops.The cited formulation uses node features, trainable weights, activation functions, and a normalized adjacency matrix.Source: §5.2.2 · p. 12

5.2.3 PDG Approaches for Android Malware Detection.

• PDG and FCG embeddings combined through an ensemble reached 99.88% F1-score on samples from Drebin, AMD, and AndroZoo.Android-COCO constructs PDGs from native libraries and bytecode, then combines predictions from PDG and FCG representations.Source: §5.2.3 · p. 14

5.2.4 System Call Approaches for Android Malware Detection.

• System-call graphs model runtime interactions with centrality features and GCN pooling, achieving 92.3% accuracy and a lower false-positive rate than other methods.The survey notes that system-call graphs remain scarcely used in graph representation learning literature.Source: §5.2.4 · pp. 14–15
• Network-flow models use IP-based graph structure and message passing, with NF-GNN outperforming seven baselines and NT-GNN reaching 97% F1-score on two datasets.NF-GNN supports supervised, graph-autoencoder, and one-class classification variants; NT-GNN updates node representations with GRU-based aggregation.Source: §5.2.5 · p. 15

5.3 Android Malware Datasets

• CICAndMal2017 contains 10,854 APKs, including 6,500 benign apps and 4,354 malware across five classes, with network packets converted into 80-feature flows.The dataset covers APKs published between 2015 and 2017.Source: §5.3 · p. 15
• CICMalDroid contains 17,341 APK samples across benign, adware, banking, SMS, and riskware classes, with static, dynamic, and network-traffic features.Its supplied features include system calls, binder calls, composite behaviors, and pcap network traffic.Source: §5.3 · pp. 15–16
• AndroZoo contained more than 21M APKs in 2022 and is often combined with other datasets to obtain balanced benign and malware samples.The collection is continually updated and includes apps from Google Play Store, VirusShare, and other APK stores.Source: §5.3 · p. 16

5.3 Android Malware Datasets.

• Drebin contains 5,560 APKs from 179 malware families but no benign examples, so another dataset such as AndroZoo is needed for benignware.Most multiclass studies use the largest classes, while all examples can support binary classification.Source: §5.3 · pp. 16–17

5.3 Android Malware Datasets

• MalNet provides 1,262,024 function-call graphs across 47 types, averaging over 15k nodes and 35k edges per graph, with MalNet-Tiny offering 5,000 smaller balanced graphs.MalNet Explorer was also released to inspect the dataset’s malware graph structures.Source: §5.3 · p. 17

6.1 Windows-based Program Graph Structures

• Windows PE files are analyzed statically through disassembly or decompilation, or dynamically in sandboxes that monitor system interactions, calls, network flows, and APIs.These representations support CFGs, FCGs, PDGs, and behavioral or entity graphs.Source: §6.1 · p. 17

6.2.1 CFG Approaches for Windows Malware Detection.

• 99.25% accuracy was achieved by MAGIC’s DGCNN on the Microsoft Malware Classification Challenge dataset using CFGs extracted from PE assembly.MAGIC models basic blocks as nodes and program flow as edges, using adaptive pooling for graph classification.Source: §6.2.1 · pp. 17–18
• HawkEye achieved 96.82% accuracy on Linux, 93.39% on Windows, and 99.6% on Android with static and dynamic CFGs across platforms.Instruction embeddings are computed with word2vec and combined by a custom GNN.Source: §6.2.1 · p. 18
• CFG-based approaches combine graph architectures and semantic features, including DGCNNs, attention, word2vec, BERT, GraphSAGE, and joint CFG–FCG modeling.Wang et al. achieved 90.88% and 72.44% F1-score on two private datasets, while MalGraph combines intra- and inter-procedural embeddings.Source: §6.2.1 · pp. 17, 19
• CFGExplainer identifies prediction-relevant CFG subgraphs and outperforms GNNExplainer, SubgraphX, and PGExplainer for malware-classification explanations.The framework addresses the limited insight that detection models otherwise provide into graph patterns behind predictions.Source: §6.2.1 · p. 19

6.2.2 FCG Approaches for Windows Malware Detection.

• More than 99% F1-score was obtained by a DGCNN using behavioral API-call graphs from a public dataset containing 42,797 malware and 1,079 benignware sequences.The graphs were constructed from API-call sequences monitored during sandbox execution.Source: §6.2.2 · pp. 19–20

6.2.3 Entity Graph Approaches for Windows Malware Detection.

• Windows entity-graph studies model interactions among processes, files, registry keys, sockets, APIs, and other heterogeneous entities using GCNs, GraphSAGE, GATs, Siamese networks, and contrastive learning.Reported accuracies range from 85.73% to 98.65% for FewM-HGCL across multiple datasets, while other studies use benign-only training or private datasets.Source: §6.2.3 · pp. 20–21

6.3 Windows Malware Datasets

• Comparisons across Windows studies are limited because most use private datasets built from VirusShare or VirusTotal, although the MMCC enables more comparable evaluation.The MMCC contains more than 20,000 samples from nine malware families with bytecode and disassembly representations.Source: §6.3 · p. 21

7.1 Web-based Graph Structures

• Web pages, DNS communications, and network flows are represented as hierarchical, heterogeneous, or endpoint graphs to expose malicious code, domain associations, and network attacks.HTML and JavaScript can form hierarchical graphs; DNS graphs connect domains with hosts or IP addresses; network-flow graphs represent client communications and attack traffic.Source: §7.1 · p. 22, Figure 5 · p. 22

7.2.1 Code-based Approaches for Web Malware Detection.

• 95.5% accuracy was achieved by a TAGCN-based phishing detector trained on DOM graphs with RNN-encoded node features and multi-hop neighborhood aggregation.The model uses max-pooling and end-to-end cross-entropy training on a private dataset.Source: §7.2.1 · pp. 22–23
• More than 99% accuracy was achieved by PhishGNN, which combines random-forest URL predictions with GCN message passing over crawled hyperlink graphs.The graph represents URLs using features extracted from URL text, DOM content, and domains.Source: §7.2.1 · p. 23
• Code-based approaches also use word2vec-GCN embeddings for XSS payloads and Gated GNN or GAT embeddings over AST, CFG, PDG, and ODG representations of JavaScript.The XSS model reports 99.6% accuracy, while JStrong achieves its best performance on a pruned PDG because it captures data flow and statement execution order.Source: §7.2.1 · p. 23

7.2.2 Domain-based Approaches for Web Malware Detection.

• Domain-based methods construct relationship or heterogeneous information networks from domains, DNS records, hosts, IPs, and relations, using DeepWalk, custom GCNs, or edge-level attention.Deepdom supports inductive embeddings for unseen DNS nodes, while another method detects malicious-domain embeddings with a downstream fully connected layer.Source: §7.2.2 · p. 24

7.2.3 Network Flow Approaches for Web Malware Detection.

• Network-flow methods apply GCN, SIR_GN, heterogeneous-graph GCN, or GIN models to botnet and DDoS detection, with C&C and P2P botnet accuracies of 99.03% and 99.51%.The approaches target malicious nodes or attack graphs and use private or synthetic traffic settings; GraphDDoS models relationships among flows and packets.Source: §7.2.3 · p. 24

7.3 Web Malware Datasets.

• Web-based graph-representation studies use malicious-URL, benign-URL, XSS, JavaScript-malware, and passive-network-trace datasets, including PhishTank, OpenPhish, TrancoTop1M, AlexaTop1M, XSSed, Petrak, GeeksOnSecurity, and CAIDA.Source: §7.3 · p. 25

8.1 Background

• Adversarial attacks are categorized by feature-space versus problem-space manipulation and by white-box, gray-box, or black-box attacker knowledge.Feature-space attacks modify representations, whereas problem-space attacks modify inputs such as source code.Source: §8.1 · p. 26

8.2 Adversarial Attacks and Malware Detection

• Malware adversarial examples must remain malicious and executable while preserving formats such as PE or APK, making inverse mapping from graph or feature space substantially difficult.Black-box settings further complicate attacks because the attacker may not know the detector’s input representation.Source: §8.2 · pp. 26–27
• Existing malware attacks append bytes, modify PE headers, insert API calls, or use reinforcement learning, but their effectiveness depends on the detector’s representation.Byte-level methods do not transfer directly to higher-level API-call representations.Source: §8.2 · p. 27

8.3 Adversarial Attacks on Graph-based Malware Detection

• Graph-based attacks modify node or edge features or graph structure, but removing CFG or FCG elements can violate program functionality and graph-classification constraints.The survey emphasizes that malware-specific attacks must preserve executable behavior while manipulating the graph used by the detector.Source: §8.3 · p. 27
• MANIS achieved 72.2% misclassification with strongest-node insertion and 33.4% with gradient-guided insertion on Drebin under white-box conditions, while preserving valid binaries.Similar results were obtained in gray-box settings.Source: §8.3 · p. 27
• Reinforcement-learning graph attacks achieved over 90% feature-space and up to 100% problem-space success on 30k Androzoo APKs, while semantic-NOP insertion approached 100% black-box success on CFGs.These attacks use graph rewiring or semantic-preserving insertions to maintain valid malware formats and behavior.Source: §8.3 · p. 27

9 CHALLENGES AND DIRECTIONS

• Studies use distinct malware examples, making cross-paper performance comparisons inefficient and motivating a large, diversified baseline dataset.Different training and testing samples lead to different performance evaluations even when popular datasets are used.Source: §9 · p. 28
• GNN robustness remains uncertain because static APK code struggles with obfuscated malware, adversarial defenses are underexplored, and existing attacks can fool classifiers even in black-box settings.The survey suggests hybrid graph approaches and stronger defenses as underexplored directions.Source: §9 · p. 28
• Deep GNN models are difficult to interpret, although explainability techniques exist and few works apply them to malware predictions.The survey identifies malware-specific explanation methods as a useful research direction for cybersecurity analysis.Source: §9 · p. 28
• Widely used GNN architectures may not be optimized for malware detection, motivating the development of models specifically designed for malware representation.The survey presents this as an open research opportunity rather than an established limitation of every current model.Source: §9 · p. 28

10 CONCLUSION

• The survey provides an in-depth review of graph representation learning methods, graph structures, state-of-the-art studies, and datasets for Android, Windows, and Web malware detection.It organizes many existing techniques around a common graph-classification architecture.Source: §10 · p. 28
• Many recent works combine GNNs with word embeddings to learn both disassembled-code semantics and malware structural patterns.The survey also reports effective adversarial attacks against graph-based detection systems and derives future directions from current challenges.Source: §10 · p. 29