A Comparison of Graph Neural Networks for Malware Classification
Managing the threat posed by malware requires accurate detection and
classification techniques. Traditional detection strategies, such as signature
scanning, rely on manual analysis of malware to extract relevant features,
which is labor intensive and requires expert knowledge. Function call graphs
consist of a set of program functions and their inter-procedural calls,
providing a rich source of information that can be leveraged to classify
malware without the labor intensive feature extraction step of traditional
techniques. In this research, we treat malware classification as a graph
classification problem. Based on Local Degree Profile features, we train a wide
range of Graph Neural Network (GNN) architectures to generate embeddings which
we then classify. We find that our best GNN models outperform previous
comparable research involving the well-known MalNet-Tiny Android malware
dataset. In addition, our GNN models do not suffer from the overfitting issues
that commonly afflict non-GNN techniques, although GNN models require longer
training times.
Vrinda Malhotra, Katerina Potika, Mark Stamp
# A Comparison of Graph Neural Networks for Malware Classification

###### Abstract

Managing the threat posed by malware requires accurate detection and classification techniques. Traditional detection strategies, such as signature scanning, rely on manual analysis of malware to extract relevant features, which is labor intensive and requires expert knowledge. Function call graphs consist of a set of program functions and their inter-procedural calls, providing a rich source of information that can be leveraged to classify malware without the labor intensive feature extraction step of traditional techniques. In this research, we treat malware classification as a graph classification problem. Based on Local Degree Profile features, we train a wide range of Graph Neural Network (GNN) architectures to generate embeddings which we then classify. We find that our best GNN models outperform previous comparable research involving the well-known MalNet-Tiny Android malware dataset. In addition, our GNN models do not suffer from the overfitting issues that commonly afflict non-GNN techniques, although GNN models require longer training times.

## 1 Introduction

Android malware is a common problem on mobile devices and poses a serious challenge due to its volume and diversity. According to AV-TEST [3], in 2021 some 9.09 million new mobile malware samples were intercepted, which is an average of nearly 25,000 new samples per day. Of these mobile malware samples, about 3.5 million were Android-based.

Since Android is an open-source platform, it provides flexibility for mobile developers to create custom applications (apps). However, this same flexibility can be exploited by bad actors to create malicious apps that users install. Therefore, solutions that detect and classify malware are crucial for the safety of Android devices.
Previous studies such as [2] have illustrated that new malware apps tend to be variants of pre-existing malware families, and therefore showcase similar behavioral traits. For example, the GinMaster malware family sends confidential information to a remote server, while the DroidKungFu family allows a hacker to control an infected device from a remote location and access confidential information. We can classify malware samples into broad families based on their differing characteristics [13].

Signature-based malware detection methods have been popular for creating endpoint protection systems because they are comparatively fast and effective on "traditional" malware. However, generating classic signatures requires expert knowledge to reverse engineer malware instances and produce the necessary features, and hence reverse engineering cannot scale with malware production. Signature-based techniques also fail to identify zero-day malware, whereas machine learning-based methods have the potential to identify and classify previously unseen malware [20].

Static malware analysis relies on features that can be extracted without executing or emulating code, in contrast to dynamic analysis, where execution or emulation is required [10]. In general, static analysis is more vulnerable to code obfuscation techniques employed by modern polymorphic and metamorphic malware [52], while dynamic malware analysis is more resistant to such obfuscations [43]. However, collecting dynamic features is more resource and time intensive [4].

Studies such as [2] perform broad static analysis to generate features (e.g., user permissions, suspicious API calls, network addresses, etc.) and then use machine learning algorithms to classify malware. However, these machine-learning algorithms generally do not adequately model interactions between function calls. Such interactions can most naturally be taken into account using a graph-like data structure. Graph-based methods do not assume that the features of a particular instance are independent of each other, and the models themselves can learn relationships between features. This provides us with an additional layer of information that is inherent in the input data and can be best utilized by graph models. Moreover, labor-intensive manual analysis of code is not required to generate feature sets for our graph-based models, giving them a significant advantage over traditional techniques, such as signature analysis. The goal of this research is to explore malware classification techniques using graph-based learning that relies solely on graphs generated from code.

The remainder of this paper is organized as follows. In Section 2, we discuss relevant related work. In Section 3, we introduce several learning techniques that are based on different principles, ranging from standard machine learning models to current state-of-the-art Graph Neural Networks (GNN). Section 4 includes implementation details related to the experiments that we perform. In Section 4.3, we analyze and discuss our experimental results. Finally, in Section 5, we provide a summary of our main results and discuss potential directions for future work.
Related Works

In this section, we highlight some of the learning-based methods that have been previously used for malware classification and detection. We divide this selective survey between traditional learning-based classifiers and graph-based classification. Under the heading of "traditional" learning techniques, we include both classic statistical-based machine learning and neural networking-based deep learning.

### Traditional Learning-Based Classification

In the paper [50] from 2013, a Bayesian classifier was trained to detect malware using 58 code-based attributes. In the 2014 paper that introduced the popular Drebin dataset [2], features (e.g., permissions and API calls) were extracted from Android apk files and the samples were then classified using Support Vector Machines (SVM). A later method, which its authors referred to as Significant Permission Identification for Android Malware Detection (SIGPID) [28], mined the permissions data of each malware app using three levels of pruning to identify the 22 most significant permissions. These features were then used to train an SVM classifier.

With the rise in popularity of deep learning models, papers such as [42] appeared, where permission sequences were extracted as word embeddings and used as features in a Long Short-Term Memory Network (LSTM) model. Similarly, in [20], API features were selected based on their frequency and then mapped to an image-like structure, with Convolutional Neural Networks (CNN) used as the classifier. The results indicate API calls and permissions are strong features for Android malware detection, but that the optimal choice of these features depends on the dataset used.

Opcode-sequence \(n\)-gram features have also been successfully used to detect malware [21]. In addition, the paper [33] used raw opcode sequences encoded as one-hot vectors, which served to classified samples via a CNN model. Techniques based on opcode features can be defeated, since opcode sequences can be directly altered via elementary obfuscation techniques. Another popular approach for malware classification is to convert files into grayscale images and then take advantage of the strength of CNNs for malware detection and classification [18, 24]. Additional work on malware classification includes a range of novel approaches, such as that in [45], where patterns based on inter-component communication were extracted from the code.

### Graph Learning-Based Classification

While traditional learning techniques are based on the type of feature and classifier, graph-based learning relies on the type of graph structure and how the node features are embedded. For example, the papers [14, 19, 36] use API call graphs. Specifically, in [19], apps are represented in relation to APIs, and API
relationships are mapped as a structured Heterogeneous Information Network (HIN). Then a meta-path-based approach is used to characterize the semantic relatedness of apps and APIs, aggregating similarities using multi-kernel learning. Heterogeneous graphs are those that use more than one type of relationship to make connections between nodes.

In [36], API call sequence graphs learn multiple embedding representations that are successfully used for malware detection and classification. The authors use a recurrent neural network to decode the deep semantic information and to independently extract features, with a version of a Graph Convolutional Network (GCN) used to model high-level graphical semantics. In [14], a skip-gram model is used to extract features for graph nodes based on API sequences. These features rely on both app-API relationships and API-API relationships to form a heterogeneous graph.

Another popular type of graph used for malware analysis is an opcode-level function call graphs [16; 23; 34]. The research in [16] uses opcode-sequences as text features, with traditional machine learning methods (Random Forest, SVM, etc.) for classification. In contrast, the paper [34] relies on an LSTM-based neural network for classification. The authors of [23] utilize a novel graph structure that they call a co-opcode graph, which is constructed by extracting metamorphic engine-specific opcode patterns. A method related to Hidden Markov Models (HMM) is then used to classify the malware samples.

Opcode-level graphs can also be treated like text features rather than graphical data. For example, in [5] dynamically-generated network flow graphs are used to create a new model that its authors call Network Flow Graph Neural Network (NF-GNN). This NF-GNN model relies on a novel edge feature-based GNN for classification.

The graph methods mentioned above are all transductive, which implies that they cannot be expected to generalize to zero-day malware. One goal of our research is to analyze graph-based models that are inductive, that is, models that can be used to predict zero-day malware. We will base our models on Control Flow Graphs (CFG). In a CFG, nodes represent program statements, including called subroutines and conditionals, while edges represent the flow of the program. CFGs intra-procedural mappings may be well-suited to classify zero-day malware [49], since they only rely on characteristics of the code of an apk. In [49], a Deep Graph Convolutional Neural Network (DGCNN) is used to embed structural information inherent in CFGs for effective and efficient malware classification.

The inter-procedural counterpart to CFGs are Function Call Graphs (FCG), where nodes represent subroutines and edges represent the caller-called relationships between subroutines. In [34], opcode level function call graphs are obtained from the static analysis of malware, while [48] uses a Natural Language Processing (NLP)-inspired graph embedding to convert the graph structure of an Android app into a vector. On a related note, the paper [12] introduced the MalNet dataset, a large Android malware dataset, where FCG data has
been extracted from apk files. The authors considered state-of-the-art graph representation learning approaches, including GraphSAGE [17] and Graph Isomorphism Networks (GIN) [46]. Among the methods considered, they found that FEATHER and GIN achieved the highest classification performance. Using this same MalNet dataset, the authors of [29] employ Jumping Knowledge GNNs (JK-GNN) with node features set to page rank, degree nodes, etc. They conclude that JK-GraphSAGE performs best.

### Datasets

In our research, we want to focus on graphs that do not require handcrafted features, graphs that will enable us to deal with zero-day malware, and graphs that are straightforward to generate and analyze. Network flow graphs and control flow graphs are difficult to generate and can require significant resources to store, while heterogeneous graphs are difficult to interpret and encode. In contrast, a Function Call Graph (FCG) is easy to interpret since it consists of all possible execution paths called during runtime. For example, if an app is making a sequence of function calls to gather sensitive information and send it to a server, all of these function calls are in the FCG, and we should be able to gain insight into this malicious behavior from the FCG. Henceforth, we focus on FCGs in this research.

A comparison between popular Android malware datasets is provided in Table 1. Not mentioned in Table 1 is the AndroZoo dataset [1], which is an ongoing project of that at the time of this writing consists of more than 21,000,000 apk files. The MalNet-Tiny dataset is derived from AndroZoo.

All of the datasets in Table 1 consist of malware apk files or hexadecimal representations of the binary content, along with manifests that contain metadata, such as function calls, strings, etc.

For our experiments, we use the MalNet-Tiny dataset. As noted in Table 1, MalNet-Tiny is comprised of five families, with 5000 samples in total. This dataset has a sufficient number of samples to train the graph-based learning models that we consider and, furthermore, each sample is provided in the form of an FCG [12]. Also, MalNet-Tiny has been used in previous studies, enabling a direct comparison of our research to previous work.

\begin{table}
\begin{tabular}{c|r|r|r} \hline \hline Dataset & Families & Samples & Papers \\ \hline Android Malware Dataset (AMD) & 42 & 5000 & [14, 36, 48] \\ Android Malware Genome (AMG) & 72 & 1260 & [48] \\ Drebin Dataset & 179 & 5560 & [14, 36, 48] \\ MalNet & 696 & 1,262,024 & [31] \\ MalNet-Tiny & 5 & 5000 & [1, 12] \\ \hline \hline \end{tabular}
\end{table}
Table 1: Popular datasets for Android malware classification
### Related Work

Table 2 summarizes a selection of previous work where either traditional learning techniques or graph-based learning has been applied to the Android malware detection or classification problems. Note that two of the research papers in Table 2 use the MalNet-Tiny dataset, and hence these two are the most directly relevant for comparison to the results that we provide in Sections 4 and 4.3, below.

## 3 Background

A graph is a data structure consisting of two components, namely, nodes (or vertices) and edges. A graph \(G\) is defined as \(G=(V,E)\), where \(V\) is the set of nodes, and \(E\) is the edges between them. These edges can be directed or undirected.

Conventional machine learning and deep learning techniques can be viewed as dealing with relatively simple types of graphs. For example, images can be viewed grid graphs while text and speech are sequential and can be viewed as line graphs. However, in general, graphs can be far more varied and complex, with arbitrary connections between nodes.

Recently, analyzing graphs with machine learning has become popular. Traditional feedforward machine learning algorithms, such as Multi-Layer Perceptrons (MLP) and CNNs, treat the features of a particular instance as if they are independent of other instances. While Recurrent Neural Networks (RNN) can deal with sequential data, Graph Neural Networks (GNN) allow us to model arbitrary interactions that are beyond the scope of RNNs.

\begin{table}
\begin{tabular}{c|c c c c c} \hline \hline Paper & \begin{tabular}{c} Learning \\ technique(s) \\ \end{tabular} & \begin{tabular}{c} Feature(s) \\ \end{tabular} & \begin{tabular}{c} Classification \\ or detection \\ \end{tabular} & \begin{tabular}{c} Dataset(s) \\ \end{tabular} & 
\begin{tabular}{c} Accuracy \\ or F1-score \\ \end{tabular} \\ \hline Arp, et al. [2] & SVM & Multiple & Classification & Drebin & 0.9400 \\ Busch, et al. [5] & NF-GNN & Network flows & Classification & Custom dataset & 0.9614 \\ Freitas and Dong [12] & GIN & FCG & Classification & MalNet-Tiny & 0.9000 \\ Gao, et al. [14] & GCN & API calls & Both & AMG, Drebin, AMD & 0.9504 \\ Gülmez and Sougkumar [16] & RF and SVM & Opcodes & Detection & Custom dataset & 0.9700 \\ He, et al. [18] & ResNet & Images & Detection & Andro-dumpsys & 0.9500 \\ Hou, et al. [19] & HIN & API calls & Detection & Comodo Cloud & — \\ Huang, et al. [20] & CNN & API calls & Detection & Custom dataset & 0.9430 \\ Jerome, et al. [21] & SVM & Opcode \(n\)-grams & Classification & AMG plus & 0.8931 \\ Kakisim, et al. [23] & Custom & Co-opcode graph & Detection & Custom dataset & 0.9930 \\ Khan, et al. [24] & ResNet/GoogleNet & Opcodes & Detection & MMC & 0.8836 \\ Li, et al. [28] & Custom & Permissions & Detection & Custom dataset & 0.9362 \\ Lo, et al. [29] & JK & FCG & Classification & MalNet-Tiny & 0.9440 \\ McLaughlin, et al. [33] & CNN & Opcodes & Classification & AMG plus & 0.8600 \\ Niu, et al. [34] & LSTM & Opcodes & Classification & Custom dataset & 0.9700 \\ Pei, et al. [36] & Graphs & API/permissions & Detection & Drebin, AMD & 0.9967 \\ Vinayakumar, et al. [42] & LSTM & API calls & Classification & AMG plus & 0.8970 \\ Xu, et al. [45] & Custom & ICC & Detection & Custom dataset & 0.9740 \\ Xu, et al. [48] & GNN & FCG & Classification & AndroZoo, Drebin, AMD & 0.9933 \\ Yan, et al. [49] & DGCNN & CFG & Classification & MMC & 0.9942 \\ Yerima, et al. [50] & Bayesian & Multiple & Classification & Custom dataset & 0.8450 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Summary of selected previous work
Graph Neural Networks (GNN) are neural networks that directly operate on graphs [55]. GNNs can be viewed as generalizations of CNNs that allow for a richer neighborhood structure. Thus GNNs can model more complex input and output relationships.

### LDP Features

In our GNN models, we use the Local Degree Profile (LDP) [6] for node features. LDP is a relatively simple representation scheme that is based on a node and its one-hop neighborhood. Specifically, for a graph \(G=(V,E)\), let \(d(v)\) be the degree of \(v\), that is, the number of vertices that are adjacent to \(v\) in the graph \(G\). The LDP of a given node \(v\in V\) is defined as the vector of length five given by

\[\text{LDP}(v)=\Big{(}d(v),\min\big{(}N(v)\big{)},\max\big{(}N(v)\big{)},\mu \big{(}N(v)\big{)},\sigma\big{(}N(v)\big{)}\Big{)} \tag{1}\]

where \(N(v)=\{d(u)\,|\,(v,u)\in E\}\), \(\mu\) is the mean, and \(\sigma\) is the standard deviation [6]. Thus the LDP of \(v\) is a statistical profile of the neighborhood structure of \(v\) within the graph \(G\). LDP features have been shown to perform well with the graph neural networks that we discuss in Section 3.3, below. For our purposes, one potential advantage of the LDP in (1) is that standard deep learning techniques can also be trained using this feature. We note in passing that graph kernel methods reduce dimensionality of the graph data, resulting in different features from LDP, while random walk and spectral distance-based methods also learn representations of the graph data that differ from the LDP.

Next, we outline each of the learning methods that we consider in this research. We divide the models into two groups, namely, non-GNN and GNN models.

### Non-GNN Learning Methods

The learning methods in this section use graph data for classification, but are not considered GNNs. These five architectures provide a baseline for comparing more costly--with respect to training--GNN architectures.

#### 3.2.1 Multi-Layer Perceptron

Multi-Layer Perceptron (MLP) is a standard feedforward deep learning technique. MLPs have proven extremely useful in a wide range of applications. Here, we train an MLP on the LDP features in (1), which serves as a baseline for comparison of the effectiveness of our graph-based models.

#### 3.2.2 Weisfeiler-Lehman Kernel

Graph kernels methods are a form of supervised learning that use kernel functions to reduce dimensionality. In contrast to traditional kernel-based machine
learning models, such as Support Vector Machines (SVM), graph kernel methods are designed specifically to deal with graph-based features.

In our experiments, we use the Python GraKel library to test the Weisfeiler-Lehman Subtree Kernel (WL-Kernel) technique [22]. Such models can be used, for example, to find isomorphisms between graphs [39].

#### 3.2.3 Feather

FEATHER [38] is a complex representation scheme that uses characteristic functions of node features with random walk weights to describe node neighborhoods and to create node embeddings. FEATHER introduces a generalization of characteristic functions to node neighborhoods, where the probability weights of the characteristic function are defined by a measure known as "tie strength." The so-called \(r\)-scale random walk weighted characteristic function is then used to generate the embeddings. Random Forest is used to classify based on the resulting embeddings.

#### 3.2.4 Slaq-VNGE and Slaq-LSD

We experiment with Slaq-VNGE and Slaq-LSD, both of which approximate the spectral distances between graphs, but are based on different functions. Whereas Slaq-VNGE uses Von Neumann Graph Entropy (VNGE), which measures information divergence and distance between graphs [41], Slaq-LSD approximates NetLSD, which measures the spectral distance between graphs based on the heat kernel [40].

### GNN Architectures

In this section, we consider GNN architectures. In this section, we consider networks that attempt to improve on the basic GNN architectures of the previous section. These models are more complex and costly to train, as compared to the GNNs discussed above.

#### 3.3.1 Graph Convolutional Networks

Convolutional Neural Networks (CNN) have been extremely successful for image classification. However, CNNs are limited to simple grid-like graph structures. GNNs can be viewed as generalizations of CNNs to more general graph structures. GNNs aim to generate node embeddings that transform the graph nodes into a low-dimensional embedding space. The mean of all node embeddings is taken to form the whole graph embedding, which encodes the whole graph into low-dimensional space for graph classification [7].

Graph Convolutional Networks (GCN) compute node embeddings by aggregating neighborhood node features. Let \(A\) be the adjacency matrix of the graph \(G=(V,E)\). Then \(A=\{a_{ij}\}\) is an \(N\times N\) matrix, where \(N=|V|\) and
is 1 if \((v_{i},v_{j})\in E\); otherwise \(a_{ij}=0\). Each node has a \(k\)-dimensional feature vector, with \(X\in R^{N\times k}\) representing the feature matrix for all \(N\) nodes. An \(L\)-layer GCN consists of \(L\) graph convolution layers, with each layer constructing embeddings for every node by mixing the embeddings of the neighboring nodes in the graph from the previous layer [25].

#### 3.3.2 GraphSAGE

The Graph Sample and Aggregate (GraphSAGE) algorithm was developed in [17]. Unlike GCNs, GraphSAGE randomly samples a fixed-size subset of node neighbors. This serves to limit the space and time complexity of the algorithm, irrespective of the graph structure and batch size. Similar to the convolution operation in CNNs, information relating to the local neighborhood of a node is collected and used to compute the node embedding.

At each iteration, the neighborhood of a node is initially sampled, and the information from the sampled nodes is "aggregated" into a single vector. The neighborhood of node \(v\) is denoted as \(\mathcal{N}(v)\), where \(\mathcal{N}(v)=\{u\,|\,(v,u)\in E\}\) for the graph \(G=(V,E)\). At layer \(k\), the aggregated information for node \(v\) is based on its neighborhood \(\mathcal{N}(v)\); see [17] for more details. The aggregation operation can be implemented as a mean, pooling, or LSTM function. We use the Pytorch mean as our aggregator.

After applying the model trainable parameters and passing the result through a non-linear activation function such as ReLU, the layer \(k\) node \(v\) embedding is concatenated. The final representation (embedding) of node \(v\) is essentially the node embedding at the final layer. For node classification, this node embedding is passed through a sigmoid neuron or softmax layer.

#### 3.3.3 Graph Isomorphism Network

The crucial difference between Graph Isomorphism Network (GIN) [17] and other GNNs is the message aggregation function. For GINs, this function is based on Multi-layer Perceptrons (MLP) at each layer. Message aggregation methods are related to the Weisfeiler-Lehman algorithm mentioned above.

#### 3.3.4 Simple Graph Convolution

GCNs inherit considerable complexity from their deep learning lineage, which can be burdensome for less demanding applications. Simple Graph Convolution (SGC) [44] reduces the excess complexity of GCNs by repeatedly removing the nonlinearities between GCN layers and collapsing the resulting function into a single linear transformation. In contrast, a GCN transforms the feature vectors repeatedly throughout its layers and then applies a linear classifier on the final representation, SGC reduces the GCN procedure to a simple feature propagation step followed by standard logistic regression.
#### 3.3.5 Jumping Knowledge Networks

Similar to convolutional neural networks, GNN models of increasing depth can perform worse. While the message-passing mechanism helps us harness the information encapsulated in the graph structure, it may introduce some limitations if combined with GNN depth. In other words, our quest for a model that is more expressive and aware of the graph structure by adding more layers so that nodes can have a large receptive field can revert to a model that treats nodes all the same. This is called the over-smoothing problem [26]. To mitigate over-smoothing, we can apply the Jumping Knowledge [47] technique, which uses a concatenation layer.

The key idea behind Jumping Knowledge is to select from all of those intermediate node representations and jump to the last layer, which serves to combine the intermediate node representations and to generate the final node representation. We apply layer aggregation concatenation to combine all intermediate node representations for a linear transformation to compute the final node embeddings. The result then undergoes global pooling, with element-wise pooling over the final node embeddings. We apply Jumping Knowledge to the GCN, GraphSAGE, and GIN models, and we abbreviate these models as JK-GCN, JK-GraphSAGE, and JK-GIN, respectively.

#### 3.3.6 UnetGraph

In [15], U-Nets are used to correlate graph data to images by considering images as a special case of graphs, in which nodes lie on regular 2-D lattices. This structure enables us to use convolution and pooling operations on images. Therefore, node classification and embedding tasks have a natural correspondence with pixel-wise prediction tasks such as image segmentation [35]. In particular, both tasks aim to make predictions for each input unit, corresponding to a pixel on images or a node in graphs. In computer vision, pixel-wise prediction tasks have achieved major advances.

Originally introduced in [37], U-Nets [8], which are based on an encoder-decoder architecture, are popular for 3-D image segmentation tasks. In addition to convolutions, pooling and up-sampling operations are essential building blocks in these architectures. However, extending these operations to graph data is challenging, because unlike grid-based data such as images and texts, nodes in graphs have no spatial locality and order information as required by regular pooling operations. To bridge this gap, the paper [15] introduces graph pooling (gPool) and unpooling (gUnpool) operations. We use the GraphUNet implementation of this architecture from the Torch Geometric library.

#### 3.3.7 Deep Graph Convolutional Neural Network

Deep Graph Convolutional Neural Networks (DGCNN) [54] have three sequential stages. First, graph convolution layers extract the local substructure of vertices
features and define a consistent vertex ordering. Second, a SortPooling layer sorts the vertex features under the previously defined order and unifies the input sizes. Third, traditional convolutional and dense layers read the sorted graph representations and make predictions.

DGCNN has a number of advantages over other graph neural networks. For one, it directly accepts graph data as input without the need to first transform graphs into tensors, making end-to-end gradient-based training possible. Another potential advantage of DGCNN is that it enables learning from the global graph topology by sorting vertex features instead of summing them, which is supported by a novel SortPooling layer. DGCNN is the only sorting-based method that we consider. DGCNN was previously used in [54] for malware family classification using API call graphs.

### MalNet-Tiny Dataset

As mentioned in Section 2.3, we use the MalNet-Tiny dataset, which consists of 5000 Function Call Graphs derived form Android apk files. This is a balanced dataset, with each of the five families having 1000 samples. We highlight some basic features of these graphs in Table 3, where \(\sigma\) is the standard deviation. From this data, we can clearly see that Downloader family should be relatively easy to distinguish from the other families.

## 4 Experiments and Results

In this section, we first consider results for non-GNN learning methods, including MLP, which provide a baseline for comparison to GNN techniques. Then we consider extensive experiments with each of the GNN and JK models discussed above.

### Results for Non-GNN Models

Here, we provide experimental results for five methods, namely, MLP, WL-Kernel, FEATHER, Slaq-LSD, and Slaq-VNGE. Each model requires a different

\begin{table}
\begin{tabular}{c|r|r|r||r||r|r|r||r} \hline \hline \multicolumn{1}{c|}{Malware} & \multicolumn{4}{c||}{Number of vertices} & \multicolumn{4}{c||}{Number of edges} & \multicolumn{1}{c}{Average} \\ \multicolumn{1}{c|}{type} & \multicolumn{1}{c|}{min} & \multicolumn{1}{c|}{max} & \multicolumn{1}{c|}{median} & \multicolumn{1}{c||}{\(\sigma\)} & \multicolumn{1}{c||}{min} & \multicolumn{1}{c|}{max} & \multicolumn{1}{c|}{median} & \multicolumn{1}{c||}{\(\sigma\)} & \multicolumn{1}{c}{degree} \\ \hline AdDisplay & 122 & 4923 & 1248 & 1213.1 & 165 & 12,324 & 1895 & 2374.5 & 2.094 \\ Adware & 211 & 4983 & 2317 & 1339.5 & 473 & 20,096 & 5381 & 3013.1 & 2.232 \\ Benign & 5 & 4994 & 1791 & 1510.5 & 4 & 14,070 & 3591 & 2922.8 & 2.172 \\ Downloader & 40 & 117 & 51 & 4.9 & 44 & 143 & 58 & 6.1 & 1.140 \\ Trojan & 9 & 4993 & 144 & 1313.5 & 7 & 16,404 & 173 & 3275.2 & 2.156 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Overview of graph features
set of hyperparameters, which we have determined via a grid search in each case. For each model, the hyperparameters tested are specified in Table 4, where the selected values are given in boldface.

#### 4.1.1 MLP Results

We use MLP as a benchmark for comparison to traditional deep learning models. In this case, the LDP features are used for classification. As can be observed from Table 4, our best result with accuracy of 0.8054 was obtained using 5-layers trained for 50 epochs, with the dropout rate set to 0.5.

#### 4.1.2 WL-Kernel Results

We use node degree and page ranks and concatenated them into feature vectors for each node to generate features for the kernel-based method, WL-Kernel. The WL-Kernel method is used to compute a kernel matrix and then we apply Random Forest for classification, as discussed in Section 3.2.2, above. The model was tuned using the hyperparameters mentioned in Table 4, and the best accuracy attained was 0.7053. The accuracy and runtime metrics are summarized in Table 5.

\begin{table}
\begin{tabular}{c|c|c|c} \hline \hline Model & Hyperparameters & Tested values & Validation accuracy \\ \hline \multirow{3}{*}{MLP} & Number of layers & (**5**, 6) & \multirow{3}{*}{0.8054} \\  & Hidden dimensions & (**64**, 128) & \\  & Learning rate & (**0.001**, 0.0001) & \\ \hline WL-Kernel & Number of iterations & (5, **6**) & 0.7053 \\ \hline FEATHER & Order & (**2**, 5, 10) & 0.8488 \\ \hline \multirow{2}{*}{Slaq-LSD} & Number of vectors & (**10**, 15, 20) & \multirow{2}{*}{0.7799} \\  & Number of steps & (**10**, 15, 20) & \\ \hline \multirow{2}{*}{Slaq-VNGE} & Number of vectors & (10, 15, **20**) & \multirow{2}{*}{0.5499} \\  & Number of steps & (10, 15, **20**) & \\ \hline \hline \end{tabular}
\end{table}
Table 4: Hyperparameters and accuracy for non-GNN models

\begin{table}
\begin{tabular}{c|c|c|c|c} \hline \hline Iterations & Accuracy & Macro-F1 & Runtime (in seconds) & CPU cores \\ \hline
2 & 0.714 & 0.705 & 138.15 & 2 \\
5 & 0.682 & 0.674 & 182.01 & 2 \\
10 & 0.621 & 0.606 & 262.50 & 2 \\ \hline \hline \end{tabular}
\end{table}
Table 5: Accuracy and runtime for WL-Kernel
#### 4.1.3 FEATHER Results

Using FEATHER, we perform a grid search over the order hyperparameter, which controls how much information is seen from higher-order neighborhoods. The accuracy and runtime metrics for these experiments are given in Table 6.

#### 4.1.4 Slaq-LSD and Slaq-VNGE Results

For Slaq-LSD and Slaq-VNGE, we perform a grid search over two hyperparameters, namely, the number of random vectors and the number of Lanczos steps. The accuracy and runtime metrics for these models are given in Table 7.

### Results for GNN Architectures

In this section, we experiment with each of the basic GNN models introduced in Section 3.3. The input graph for each is a batched graph produced by GraphDataLoader. Each model is trained for 200 epochs. Each of the convolutional layers computes new node representations using a convolutional operator from the Pytorch Torch Geometric library, and we use the Adam optimizer.

Each model was tuned using the hyperparameters listed in Table 8, where the best hyperparameters are given in boldface. Initial experiments were also conducted with a 7-layered GCN but virtually no improvement was observed while training time increased considerably, and hence, the 7-layered model was abandoned.

\begin{table}
\begin{tabular}{c|c|c|c} \hline \hline \multirow{2}{*}{Order} & \multirow{2}{*}{Accuracy} & Runtime & CPU \\  & & (in seconds) & cores \\ \hline
4 & 0.839 & 672.78 & 2 \\
5 & 0.849 & 667.18 & 2 \\
6 & 0.847 & 680.34 & 2 \\ \hline \hline \end{tabular}
\end{table}
Table 6: Accuracy and runtime for FEATHER model

\begin{table}
\begin{tabular}{c|c|c|c|c} \hline \hline \multirow{2}{*}{Model} & \multirow{2}{*}{Vectors} & \multirow{2}{*}{Accuracy} & Runtime & CPU \\  & & & (in seconds) & cores \\ \hline \multirow{3}{*}{Slaq-LSD} & 10 & 0.775 & 314.40 & 2 \\  & 15 & 0.776 & 352.35 & 2 \\  & 20 & 0.780 & 401.01 & 2 \\ \hline \multirow{3}{*}{Slaq-VNGE} & 10 & 0.549 & 300.85 & 2 \\  & 15 & 0.547 & 322.41 & 2 \\ \cline{1-1}  & 20 & 0.544 & 361.35 & 2 \\ \hline \hline \end{tabular}
\end{table}
Table 7: Accuracy and runtime for Slaq-LSD and Slaq-VNGE
#### 4.2.1 GCN, GraphSAGE, GIN, and SGC Results

GCN uses the convolutional operator GCNConv and a global pooling layer to generate embeddings. GraphSAGE uses the convolutional operator SAGEConv, a batch normalization layer, and a global pooling layer to generate embeddings. GIN uses the convolutional operator GINConv and a global pooling layer to generate embeddings. SGC uses the convolutional operator SGConv and a global pooling layer to generate embeddings.

From Table 8, we see that GCN performed the best of these models, with an accuracy of 0.9582. In contrast, GraphSAGE performed the worst of these four models, with an accuracy of 0.7913.

\begin{table}
\begin{tabular}{c|c|c|c} \hline \hline Model & Hyperparameters & Tested values & Validation accuracy \\ \hline \multirow{3}{*}{GCN} & Number of layers & (5, **6**) & \multirow{3}{*}{0.9582} \\  & Hidden dimensions & (64, **128**) & \\  & Learning Rate & (**0.001**, 0.0001) & \\ \hline \multirow{3}{*}{GraphSAGE} & Number of layers & (5, **6**) & \multirow{3}{*}{0.7913} \\  & Hidden dimensions & (**64**, 128) & \\  & Learning rate & (**0.001**, 0.0001) & \\ \hline \multirow{3}{*}{GIN} & Number of layers & (5, **6**) & \multirow{3}{*}{0.9407} \\  & Hidden dimensions & (**64**, 128) & \\  & Learning rate & (**0.001**, 0.0001) & \\ \hline \multirow{3}{*}{SGC} & Number of layers & (5, 6) & \multirow{3}{*}{0.9079} \\  & Hidden dimensions & (64, **128**) & \\  & Learning rate & (**0.001**, 0.0001) & \\ \hline \multirow{3}{*}{JK-GCN} & Number of layers & (5, **6**) & \multirow{3}{*}{0.8941} \\  & Hidden dimensions & (64, **128**) & \\  & Learning rate & (**0.001**, 0.0001) & \\ \hline \multirow{3}{*}{JK-GraphSAGE} & Number of layers & (5, **6**) & \multirow{3}{*}{0.9291} \\  & Hidden dimensions & (64, **128**) & \\  & Learning rate & (**0.001**, 0.0001) & \\ \hline \multirow{3}{*}{JK-GIN} & Number of layers & (5, **6**) & \multirow{3}{*}{0.9769} \\  & Hidden dimensions & (64, **128**) & \\  & Learning rate & (**0.001**, 0.0001) & \\ \hline \multirow{3}{*}{UnetGraph} & Weight decay & (**0.001**, 0.0001) & \multirow{3}{*}{0.9581} \\  & Hidden dimensions & (**64**, 128) & \\  & Learning rate & (**0.001**, 0.0001) & \\ \hline \multirow{3}{*}{DGCNN} & Weight decay & (**0.001**, 0.0001) & \multirow{3}{*}{0.9218} \\  & Learning rate & (**0.001**, 0.0001) & \\ \hline \hline \end{tabular}
\end{table}
Table 8: Hyperparameters and accuracy for GNN models
#### 4.2.2 Jumping Knowledge Model Results

For JK-GCN, we use an extension of the PyTorch torch.nn.Sequential container to define a sequential GNN model. Since GNN operators take multiple input arguments, torch_geometric.nn.Sequential expects both global input arguments and function header definitions of individual operators. If omitted, an intermediate module operates on the output of its preceding module. This allows us to create more sophisticated models, such as Jumping Knowledge models. The hyperparameters tested for each GNN model are listed in Table 8, where the best hyperparameters for each model are in boldface.

Similar to the GCN model, JK-GCN also uses GCNConv layers and implements them on a Jumping Knowledge model. The model was tuned using the hyperparameters mentioned in Table 8, and the best accuracy was 0.8941

Our JK-GraphSAGE implementation uses SAGEConv layers and implements them on a Jumping Knowledge model. The model was tuned using the hyperparameters mentioned in Table 8, and the best accuracy obtained was 0.9291.

Our JK-GIN model uses GINConv layers and implements them on a Jumping Knowledge model. The best accuracy in this case was 0.9769.

#### 4.2.3 UnetGraph and DGCNN Results

We create this model using Pytorch UnetGraph, with a depth of 3 and pooling ratios set to 1 and 0.5. We also set the dropout rate to 0.5. The model was tuned using the hyperparameters in Table 8, and we trained for 100 epochs instead of the 200 used for previous models due to over-fitting at larger numbers of epochs. The best accuracy achieved by our UnetGraph models was 0.9581.

Our DGCNN model consists of 4 layers of GCNConv, a pair of 1-D convolutional layers, and a max pooling layer. Two linear classifiers are used to concatenate these layers, with a dropout rate of 0.5. The model was tuned using the hyperparameters mentioned in Table 8, and the best accuracy was found to be 0.9218. With additional hyperparameter tuning, it is likely that this model can be significantly improved, since we only varied the learning rate and weight decay.

### Discussion

In this section, we provide additional context for the results in the previous section. Specifically, we summarize the accuracies, classwise accuracies, and training efficiencies for each of the various models. We also provide UMAP embeddings, which allow us to visualize the models.

For clarity, in each case we split the analysis into two categories, namely, graph learning methods as introduced in Section 3.2 (that is, MLP, WL-Kernel, FEATHER, Slaq-VNGE, and Slaq-LSD) and the GNN models introduced in Section 3.3 (i.e., GCN, GraphSAGE, GIN, SGC, JK-GCN, JK-GraphSAGE,
JK-GIN, UnetGraph, and DGCNN). Here, we refer to the former as non-GNN models, while the latter are GNN models.

#### 4.3.1 Accuracy Comparison

In Figure 1(a) we compare the accuracies of our non-GNN models, while Figure 1(b) is an analogous comparison of the GNN-based models that we tested. Most of the GNN-based models far outperform the best of the non-GNN models. We observe that, overall, JK-GIN has the highest accuracy at 0.9769, with UnetGraph having an accuracy of 0.9581, while GIN (0.9407), JK-GraphSAGE (0.9291), DGCNN (0.9218) and SGC (0.9079) also outperform the best of the non-GNN models. While GCN has a high accuracy of 0.9582, we believe it may be due to over-smoothing. As mentioned above, we believe that further tuning of the hyperparameters might yield significant improvement for DGCNN.

As can be seen in Figure 1(b), among the non-GNN-based models, FEATHER was the best at 0.8488, with MLP being second best at 0.8054. These results are not unexpected, as these models were shown to work well (along with GIN) in the paper [12]. The bottom line is that our best GNN-based models outperform all models that were applied to the MalNet-Tiny dataset in the papers [12, 29]; see also Table 2, above.

#### 4.3.2 Classwise Comparison

To further analyze our results, we generate heat maps of the accuracy of each class for every model corresponding to its best parameters. In Figure 2(a), we observe that our worst-performing GNN-based models, namely, GraphSAGE and JK-GCN, underperform primarily because they badly fail on the benign class. We also note that all of the GNN-based models classify the Downloader class with ease.

Figure 1: Accuracy comparison
Classwise comparison of our non-GNN models is given in Figure 2(b). Qualitatively, the results for these models are similar to those of the GNN-based models, with Downloader being the easiest to classify, and Benign being the most challenging. However, as noted above, the non-GNN models perform poorly, in comparison to the best of our GNN-based models.

Overall, we see that Downloader is the easiest class to classify, while the Benign class is the most difficult. Even our worst model, Slaq-VNGE, identifies Downloader class with a 0.93 accuracy, while our best classifiers attain a similar accuracy for the Benign class. These results are not surprising in light of our initial analysis of the node and edge features, as given in Table 3, above.

We also provide confusion matrices for each of the non-GNN models and for the GNN models in Figures A.1 and A.2, which can be found in the Appendix. From these confusion matrices, we observe that the Benign class is most often misclassified as belonging to the Adware or AdDisplay class. Interestingly, we do not find a large percentage of misclassifications of Benign as Trojan (or vice-versa) which, intuitively, would seem to be difficult to distinguish, as Trojans are designed to mimic benign applications.

Figure 2: Classwise accuracies
#### 4.3.3 Runtime Comparison

We define the runtime to be the total time taken to train, test, and validate a model using its corresponding best set of hyperparameters. The runtime results for our GNN-based models are given in Figure 3(a). We observe that both GraphSAGE and JK-GraphSAGE run for longer durations than other models. The convolution operator, SAGEConv, is the most complex operator used in any of the GNNs, so this result is expected. Among the GNN-based models, GIN and GCN models require the least time for classification, as they use the least complex convolutional operators.

The runtime results for our non-GNN models are given in Figure 3(b). These models require significantly less time than GNN-based models, with the longest runtime among this collection of models being only about two-thirds that of the shortest runtime among the GNN-based models. Note that the best performing non-GNN models, FEATHER and MLP, have the longest runtimes.

#### 4.3.4 UMAP Embeddings for GNN Models

Finally, we provide a visualization of the graph embeddings for nine of our models. In each case, we apply the UMAP dimensionality reduction technique [32] to the dense layer. These results are given in Figure A.3 in the Appendix, where we have labeled the classes as

\[(\texttt{AdDisplay},\texttt{Adware},\texttt{Benign},\texttt{Downloader}, \texttt{Trojan})=(0,1,2,3,4).\]

In Figure A.3 we observe that there is generally the most class separability between Downloader, and other classes, which is supported by our observation that Downloader is the easiest to classify. We also note that several of the models provide good class separability. In particular, the jumping knowledge models, JK-GCN, JK-GraphSAGE, and JK-GIN, which appear in Figures A.3(e), (f), and (g), respectively, are among the best from this perspective.

Figure 3: Runtime comparison
Overall, these UMAP embeddings support some of our major observations. They also show that our better models tend to form numerous small clusters, which likely correspond to identifiable sub-classes within each class. This would be an interesting topic for further research.

## 5 Conclusion and Future Work

In this extensive study, we classified five different types of Android samples from the the MalNet-Tiny dataset graph-based learning methods. We considered the graph representation schemes FEATHER, WL-Kernel, Slaq-VNGE, and Slaq-LSD, and applied a Random Forest classifier to each. We found that FEATHER works best among these methods.

We then used the Local Degree Profile (LDP) to encode node features and trained a wide variety of GNN-based models on these features. Specifically, we experimented with GCN, GrahSAGE, GIN, SGC, JK-GCN, JK-GraphSAGE, JK-GIN, UnetGraph, and DGCNN models. We experimented with hyperparameters and found that these GNN-based models generally performed well, with JK-GIN, JK-GraphSAGE, UnetGraph, and DGCNN giving us the best results. We provided extensive analysis of our results, including classwise accuracies, confusion matrices, UMAP embeddings, and runtime comparisons. Our best models exceeded the results obtained in comparable previous work.

In future work, we intend to extend this promising research to a larger subset of the MalNet dataset. A more diverse dataset, with samples drawn from a larger number of families, would provide additional scope for tuning hyperparameters and analyzing the resulting models, so as to better understand their relative strengths and weaknesses.

It would be interesting to explore other graph classification architectures, including DeeperGCN [11], EdgePool [27], and Kernel Graph-based CNN (KG-CNN) [9]. It would also be worth exploring edge-based graph neural approaches such as E-GraphSAGE [30], which would enable us to include network flows as features.

Another area of future research would be to analyze the effectiveness of GNN-based models for zero-day malware detection. In a similar vein, it would also be interesting to explore malware GNN models from the perspective of explainable AI (XAI), that is, we would like to better understand how the models are actually making decisions. For this explainability problem, we could use GNNExplainer [51], which is designed to derive insights from the hidden layers of GNNs, and SubgraphX [53].

Finally, it is worth noting that the models considered in this paper are based solely on graph structure. Combining such graph-based models with more traditional features might result in models that are stronger than either the GNN-based models considered here, or learning models that are based only on more traditional features.
## 6 Declarations

The authors have no relevant financial or non-financial interests to disclose.
