Flow Graph Neural Networks

## Abstract

Abstract. Malicious software (malware) poses an increasing threat to the security of communication systems as the number of interconnected mobile devices increases exponentially.
While some existing malware detection and classification approaches successfully leverage network traffic data, they treat network flows between pairs of endpoints independently and thus fail to leverage rich communication patterns present in the complete network.
Our approach first extracts flow graphs and subsequently classifies them using a novel edge feature-based graph neural network model. We present three variants of our base model, which support malware detection and classification in supervised and unsupervised settings.
We evaluate our approach on flow graphs that we extract from a recently published dataset for mobile malware detection that addresses several issues with previously available datasets.
Experiments on four different prediction tasks
consistently demonstrate the advantages of our approach and show that our graph neural network model can boost detection performance by a significant margin.

## 1. Introduction

Malicious software (malware) poses a significant threat to the security of information technology (IT) and operational technology (OT) in private and corporate environments. Along with an increasing degree of digitalization and the rise of new technologies such as the Internet of Things (IoT), an increasing number of devices, including mobile devices, such as smartphones, and Industrial Control Systems (ICS), become connected and thus are potential targets for attacks. Accurate detection and classification of malware is thus a vital task to ensure the security of such systems.

In this work, we focus on dynamic malware detection and classification. In contrast to static methods, which analyze a candidate application’s source code or the structure of its executable, dynamic methods execute the application in a controlled environment and analyze dynamic behavior that can usually not be extrapolated from static data.
More specifically, we consider network traffic data generated during the execution of the application, which provides valuable insights into the dynamic and potentially malicious behavior affecting that application. However, in contrast to existing works, which classify individual network flows between two endpoints, i.e., aggregated communication between the two endpoints during some time frame, we construct a communication graph from all recorded network flows between any two endpoints during that time frame to obtain a rich representation of communication in the network. To the best of our knowledge, no existing work has considered this setting so far.

While classical machine learning methods have proven successful for malware detection and classification (Gibert
et al., ), deep learning approaches have not been studied as extensively. Deep learning methods offer an additional advantage of automatically learning suitable feature representations of the input data optimized for the task at hand, in contrast to traditional feature engineering approaches. Our novel edge feature-based graph neural network model learns suitable representations from extracted network flow graphs. Along with a base model for learning graph representations, we propose three derived model variants, a graph classifier, a graph autoencoder, and a one-class graph neural network, which are able to perform supervised malware detection and classification and unsupervised malware detection, respectively.

We evaluate our approach on a graph dataset that we extract from network flow features obtained from traffic generated by android applications executed on real mobile devices. The original flow features are provided by (Lashkari et al., ). The data was collected in a carefully designed environment to account for several common defects observed in previously used datasets.
Instead of classifying individual network flows, as the original work proposes, we follow our graph-based approach and construct a flow graph
for each execution of a candidate application.
Experiments on four different prediction tasks, including supervised binary, category and family classification, and unsupervised detection, consistently demonstrate the significantly superior detection performance of our approach. Our neural network model additionally boosts performance compared to baseline models, even in settings with unlabeled data and small amounts of available training data.

We summarize our contributions as follows:

- •
We propose, to the best of our knowledge, the first graph-based approach to network traffic-based malware detection and classification.
- •
We propose a novel method for extracting directed edge-attributed flow graphs from sets of network flows recorded in a monitored network.
- •
We propose a novel graph neural network model that effectively learns representations from these graphs, utilizing the graph topology and edge attributes.
- •
We provide an extensive experimental evaluation on a novel flow graph dataset considering four different supervised and unsupervised detection tasks.

## 2. Related Work

While static malware detection and classification methods analyze a candidate application’s source code or the structure of its executable file, dynamic methods execute the application in a controlled environment and analyze its behavior. Such behavior is difficult and often impossible to extrapolate from static data. Further, static methods are commonly vulnerable to obfuscation techniques modifying the code or structure of the executable.
Our approach is a dynamic one, focusing on network traffic data generated by a particular candidate application during execution.

A comprehensive overview of existing machine learning methods for static and dynamic malware detection and classification is provided by a recent survey (Gibert
et al., ).
Methods relying on network traffic data mainly differ by which specific features are extracted and which machine learning algorithm is used.
To the best of our knowledge, all existing approaches focus on classifying individual network traffic between two endpoints in a network, possibly at different resolutions. For instance, (Bekerman
et al., ) describes different resolution levels, ranging from single transactions over sessions to flows and conversations. Thereby, a flow describes traffic associated with a specific (Source-IP, Source-Port, Destination-IP, Destination-Port, Protocol)-tuple within a particular time frame and a conversation aggregates flows with the same Source- and Destination-IP endpoints.
Instead of focusing on bilateral flows or conversations between two endpoints, our approach extracts a graph from flows between any two endpoints in a monitored network during a specific time frame to obtain a richer representation of communication in the network.

Existing methods
typically report high performance on datasets that exhibit various common defects. The recently published CICAndMal2017 dataset (Lashkari et al., ) has addressed these issues by providing a sufficient number of malware samples from diverse malware categories and families with a realistic distribution of benign and malicious applications. Additionally, each application is executed on an actual physical device instead of an emulator or a virtual machine to accurately capture its actual behavior.
Instead of classifying network flows individually as proposed by the authors, we instead extract network flow graphs from the given network traffic features.

The results reported in (Lashkari et al., ) have been improved by adding new dynamic API-call features and combining a dynamic prediction model with a static prediction model (Taheri
et al., ). Our model could be combined with a static prediction model in a similar fashion.
Improved accuracy could also be achieved by predicting labels for conversations instead of individual flows (Abuthawabeh and
Mahmoud, ), further mitigating the effect of port randomization techniques. Our approach takes an additional step ahead by classifying flow graphs modeling the communication between all endpoints instead of only pairs of endpoints.
Two further works (Bibi
et al., ; Chen
et al., ) reported malware detection results only for a subset of the whole dataset.

Existing graph-based approaches to malware detection and classification mostly focus on static analysis, considering function call graphs (Kinable and
Kostakis, ; Hassen and Chan, ; Jiang
et al., ) or control graphs (Faruki
et al., ; Bazrafshan et al., ).
Dynamic graph-based approaches include (Anderson et al., ), where graphs are constructed from instruction traces collected during execution, and (John
et al., ), where system call graphs are considered.
The latter work is most related to our approach since a *Graph Convolutional Neural Network (GCN)* (Kipf and Welling, ) is used to learn node features.
To the best of our knowledge, no existing work has considered graph-based approaches based on dynamically generated network traffic data.

Deep learning methods have not been investigated as extensively as classical machine learning methods for network traffic-based approaches.
Existing methods consider detection of endpoints generating malicious traffic (Prasse et al., ), intrusion detection (Muna
et al., ), or ransomware detection (Bibi
et al., ).
To the best of our knowledge, no existing deep learning-based malware detection and classification method considers network flow graphs.

While our proposed approach includes a novel graph neural network model for malware detection and classification, it could be more generally employed to solve other graph classification and graph anomaly detection tasks.
Graph neural networks (Bronstein et al., ; Gilmer et al., ; Battaglia et al., ; Wu
et al., ; Kipf and Welling, ; Veličković et al., ; Xu
et al., ; Wu et al., ; Busch
et al., )
have recently become a de-facto standard for machine learning on graphs.
The majority of these methods can be described in a message-passing framework, as detailed in (Gilmer et al., ). The main idea is to iteratively propagate feature vectors through the graph by passing messages between nodes such that a node’s representation depends on feature vectors appearing in its neighborhood.
While most existing graph neural network models consider only node attributes, our model focuses on edge attributes instead.
Some existing models consider edge attributes (Simonovsky and
Komodakis, ; Kipf
et al., ; Schlichtkrull et al., ; Gong and Cheng, ; Jiang
et al., ; Wu
et al., ), but none of these models is directly applicable to our setting since they either consider multi-relational graphs or focus on node attributes and only utilize edge features to improve message passing between nodes. Other existing models (Shang
et al., ; Zhang
et al., ; Lin and Wang, ) focus on more specific tasks which differ from our setting.

Figure: (a) Network Flow Graph Extraction
Refer to caption: /html/2103.03939/assets/x1.png

## 3. Network Flow Graph Extraction

To decide whether a particular candidate instance of an application is malicious, we collect all network traffic generated during the execution of that application instance within a given time interval after installation.
The resulting data consists of a set of network flows described by feature vectors that can be extracted from pcap-files using tools such as *CICFlowMeter* (Draper-Gil et al., ). Thereby, each flow $F$ describes network traffic associated with one particular (Source-IP, Source-Port, Destination-IP, Destination-Port, Protocol)-tuple during the considered time frame and has a feature vector $f\in\operatorname{\mathbb{R}}^{d}$ attached to it. Typical features include the number of packets sent, mean and standard deviation of the packet length, or minimum and maximum interarrival time of the packets.

From the resulting set of flows $\operatorname{\mathcal{F}}$, we extract a flow graph, where the nodes correspond to endpoints in the network and edges model communication between these endpoints. Instead of considering (IP, Port)-tuples, we factor out the port information and consider IP-endpoints for two main reasons:

- (1)
Apart from standard ports, port selection is often arbitrary and could even be subject to port randomization techniques, leading to arbitrary and potentially misleading graph structure.
- (2)
Empirically, we found (IP, Port)-graphs to be very sparse and rather uninformative. In comparison, IP-graphs exhibit much more interesting topologies.

More specifically, from a set of flows $\operatorname{\mathcal{F}}$, we extract a directed graph $G=(V,E)$ where the nodes correspond to endpoints involved in any flow $F\in\operatorname{\mathcal{F}}$ and a directed edge is added for all pairs $(s_{i},t_{i})$ for which there exists a flow $F_{i}\in\operatorname{\mathcal{F}}$ with source and target IP $s_{i}$ and $t_{i}$, respectively. The feature vector assigned to this edge aggregates the feature vectors $f_{i}\in\operatorname{\mathbb{R}}^{d}$ of all flows $F_{i}$ along this edge using a set of five aggregation functions.
For each feature, the shape of the distribution of values along the edge is described using the first four moments, namely the mean, standard deviation, skew and kurtosis, and the median value. The aggregate values are computed for each feature and then concatenated, resulting in a feature vector $x_{i}\in\operatorname{\mathbb{R}}^{5d}$ for each edge $e_{i}\in E$.
The flow graph extraction procedure is illustrated in Figure [1(a)](#S2.F1.sf1). Figure [1(b)](#S2.F1.sf2) shows an exemplary graph extracted from real data.

Intuitively, the resulting graph captures how network traffic flows between different endpoints in the monitored network during a specific time frame. The graph structure reveals where traffic is flowing, and the additional edge attributes describe how it is flowing. Connecting individual flows in a graph provides a much richer relational representation compared to treating flows individually. Thus, we expect models learning from these graphs to perform significantly better at detection and classification tasks than models which classify individual flows. Our experimental results confirm this intuition.

We wish to note that such graphs could potentially be used for further applications, such as intrusion detection or identifying devices generating malicious traffic.

## 4. Network Flow Graph Neural Networks

Figure: (a) Node Update
Refer to caption: /html/2103.03939/assets/x3.png

From a machine learning perspective, we consider two different problems: Supervised graph classification and unsupervised graph anomaly detection. To solve these problems, we introduce a novel graph neural network model, which learns expressive representations from network flow graphs, along with three different variants of that base model, a supervised graph classifier, an unsupervised graph autoencoder, and an unsupervised one-class graph neural network. The different model variants are illustrated in Figure [2(c)](#S4.F2.sf3).

While we focus on malware detection and classification in this paper, the proposed models can be employed for general learning problems on (directed) graphs with edge attributes.

### 4.1. Problem Setting

Formally, we are given a set of graphs $\operatorname{\mathcal{G}}=\{G_{1},\dots,G_{N}\}$, a set of edge feature matrices $X_{i}\in\operatorname{\mathbb{R}}^{m_{i}\times d}$, $i=1,\dots,N$, where $m_{i}=|E_{i}|$, and a label matrix $\hat{Y}\in\{0,1\}^{N\times c}$ providing a class label for each graph, where $c$ is the number of classes.
For the sake of simplicity, we restrict ourselves to directed graphs in the following, though our models can be applied to undirected graphs in a straightforward fashion.
Further, it is not required that the input graphs share the same topology,

In a supervised anomaly detection setting, class labels could be binary (normal vs. anomalous) or multi-class (normal class and different categories or families of anomalies).
For supervised classification, a labeled training dataset is given as described above, and the task is to train a model which accurately predicts labels for new graphs not seen by the model during training.
For unsupervised anomaly detection, the training set is not labeled and consists of normal data and (usually a relatively small fraction of) anomalous data. The model is required to learn a concept of normality from the training data and correctly classify new graphs as either being normal or anomalous.

### 4.2. Learning Representations of Network Flow Graphs

Each input instance for our model is a directed graph $G=(V,E)$ with adjacency matrix $A\in\{0,1\}^{n\times n}$ and an edge feature matrix $X\in\operatorname{\mathbb{R}}^{m\times d}$, where $m:=|E|$. The representation learning part of our model computes latent representations of the edges and nodes in the graph and finally outputs a latent feature vector $h^{(1)}\in\operatorname{\mathbb{R}}^{h}$ for each node in the graph. Such a vector intuitively describes how the corresponding endpoint interacts with other endpoints in the network. Depending on the availability of labels, variants of our model compute either predictions or an anomaly score for an input graph from its latent node feature vectors. The model is trained end-to-end such that the latent representations are optimized towards the specific task.
Given an input graph with edge attributes, our model performs the following feature transformation and propagation steps to sequentially compute latent representations of the graph’s nodes and edges:

$$ (1) $\displaystyle E^{(0)}$ $\displaystyle=f_{1}(X)$ $\displaystyle\in\operatorname{\mathbb{R}}^{m\times h}$ (2) $\displaystyle H^{(0)}$ $\displaystyle=f_{2}\left(\left[\operatorname{\hat{\tilde{B}}}_{in}E^{(0)},\operatorname{\hat{\tilde{B}}}_{out}E^{(0)}\right]\right)$ $\displaystyle\in\operatorname{\mathbb{R}}^{n\times h}$ (3) $\displaystyle E^{(1)}$ $\displaystyle=f_{3}\left(\left[\operatorname{\hat{\tilde{B}}}_{in}^{T}H^{(0)},\operatorname{\hat{\tilde{B}}}_{out}^{T}H^{(0)},E^{(0)}\right]\right)$ $\displaystyle\in\operatorname{\mathbb{R}}^{m\times h}$ (4) $\displaystyle H^{(1)}$ $\displaystyle=f_{4}\left(\left[\operatorname{\hat{\tilde{B}}}_{in}E^{(1)},\operatorname{\hat{\tilde{B}}}_{out}E^{(1)},H^{(0)}\right]\right)$ $\displaystyle\in\operatorname{\mathbb{R}}^{n\times h},$ $$

where $[\cdot,\cdot]$ denotes concatenation and $f_{1},\dots,f_{4}$ are Multi-Layer Perceptrons (MLPs) with appropriate input and output dimensions. As per default, we use single-layer MLPs

$$ (5) $f_{i}(X)=q\left(XW_{i}+b_{i}\right),$ $$

where $W_{i}$ and $b_{i}$ are the learnable parameters of the model and $q$ is a non-linear activation. We use *ReLU* activations and add batch normalization. The propagation matrices $\operatorname{\hat{\tilde{B}}}_{in},\operatorname{\hat{\tilde{B}}}_{out}\in\operatorname{\mathbb{R}}^{n\times m}$ are obtained from the node-edge incidence matrices $B_{in},B_{out}\in\{0,1\}^{n\times m}$ with

$$ (6) $(B_{in})_{ij}=\begin{cases}1&\text{if}\quad\exists v_{k}\in V:e_{j}=(v_{k},v_{i})\\ 0&\text{else}\end{cases}$ $$

and

$$ (7) $(B_{out})_{ij}=\begin{cases}1&\text{if}\quad\exists v_{k}\in V:e_{j}=(v_{i},v_{k})\\ 0&\text{else}\end{cases},$ $$

indicating in- and out-going edges for each node, by substituting non-zero entries with normalized edge weights.
Normalization is applied to preserve the scale of the feature vectors. In particular, we apply symmetric normalization to the adjacency as in (Kipf and Welling, ) before computing the node-edge incidence matrices, where the normalized adjacency matrix is given as $\operatorname{\hat{\tilde{A}}}=\tilde{D}^{-\nicefrac{{1}}{{2}}}\tilde{A}\tilde{D}^{-\nicefrac{{1}}{{2}}}$ with $\tilde{A}=A+I$ and degree matrix $\tilde{D}$.
Self-loops added for normalization are removed again such that the graph structure remains unchanged.
Illustrations of the performed node and edge feature updates are provided in Figure [2(a)](#S4.F2.sf1) and [2(b)](#S4.F2.sf2), respectively.

The first network layer learns how endpoints interact with each other directly by first applying a learnable feature transformation to the original edge feature vectors (Equation [1](#S4.E1)) and subsequently computing node representations by aggregating feature vectors from neighboring edges (Equation [2](#S4.E2)).
Notably, incoming and outgoing traffic is modeled separately for each node.

The second layer enables the model to learn how endpoints communicate indirectly with their 2-hop neighbors. In a first step, the edge features are updated again by transforming the concatenated feature vectors of the source and destination node and the edge features from the previous layer (Equation [3](#S4.E3)). Concatenating the edge features from the previous layer as residual connections (He
et al., ) gives this layer direct access to previously learned features and aids in optimization. Such skip-connections have shown to improve the performance of graph neural networks when applied to node features (Xu et al., ), motivating us to apply them to edge features as well.
The edge feature update is followed by an update of the node features using features of incoming and outgoing edges and skip-connected node features from the first layer (Equation [4](#S4.E4)). These node representations constitute the final output of our representation learning module.

In principle, one could add more layers to the model in a similar fashion to model interaction between more distant endpoints.
However, the flow graphs considered in this paper usually have a relatively small diameter, such that additional layers might not result in improved performance but rather lead to over-fitting. In our experiments, we observed the best performance with either one or two layers.

### 4.3. Network Flow Graph Classifier

For supervised graph classification, we append two more layers to the representation learning module. First, a pooling layer aggregates all node feature vectors in the input graph to a single vector describing the whole graph. The second layer predicts the graph label from the pooled graph representation,

$$ (8) $\displaystyle h$ $\displaystyle=\operatorname{\text{pool}}\left(H^{(1)}\right)$ $\displaystyle\in\operatorname{\mathbb{R}}^{h}$ (9) $\displaystyle y$ $\displaystyle=\text{softmax}\left(Wh+b\right)$ $\displaystyle\in\operatorname{\mathbb{R}}^{c}.$ $$

Above, $\operatorname{\text{pool}}$ denotes a pooling function, such as element-wise mean or maximum, which aggregates all node representations into a single embedding vector for the whole graph. Predictions are computed by a dense prediction layer with learnable parameters $W\in\operatorname{\mathbb{R}}^{c\times h}$ and $b\in\operatorname{\mathbb{R}}^{c}$ and a softmax activation.
The model parameters are then optimized w.r.t. the *cross-entropy* loss

$$ (10) $\operatorname{\mathcal{L}}_{CLF}(\operatorname{\mathcal{G}})=\frac{1}{N\cdot c}\sum_{\begin{subarray}{c}G_{i}\in\operatorname{\mathcal{G}}\\ j\in 1,\dots,c\end{subarray}}-y_{ij}\log\hat{y}_{ij}.$ $$

We denote this model as *NF-GNN-CLF*.

### 4.4. Network Flow Graph Autoencoder

For unsupervised anomaly detection, autoencoder models often perform well in practice (Chalapathy and
Chawla, ). In general, an autoencoder consists of two neural network modules.
While an encoder learns compact and expressive representations of the model inputs, a decoder is supposed to reconstruct the original inputs from their learned representations. If the model is trained with exclusively or mostly normal data, the reconstruction loss can be interpreted as an anomaly score, where instances incurring a larger reconstruction loss are considered more anomalous.

We propose a graph autoencoder model where our representation learning module acts as an encoder. The latent node representations $H^{(1)}$ are then used to reconstruct the original edge feature vectors of the graph using a decoder, which is a mirrored version of the encoder:

$$ (11) $\displaystyle E^{(2)}$ $\displaystyle=f_{5}\left(\left[\operatorname{\hat{\tilde{B}}}_{in}^{T}H^{(1)},\operatorname{\hat{\tilde{B}}}_{out}^{T}H^{(1)}\right]\right)$ $\displaystyle\in\operatorname{\mathbb{R}}^{m\times h}$ (12) $\displaystyle H^{(2)}$ $\displaystyle=f_{6}\left(\left[\operatorname{\hat{\tilde{B}}}_{in}E^{(2)},\operatorname{\hat{\tilde{B}}}_{out}E^{(2)},H^{(1)}\right]\right)$ $\displaystyle\in\operatorname{\mathbb{R}}^{n\times h}$ (13) $\displaystyle E^{(3)}$ $\displaystyle=f_{7}\left(\left[\operatorname{\hat{\tilde{B}}}_{in}^{T}H^{(2)},\operatorname{\hat{\tilde{B}}}_{out}^{T}H^{(2)},E^{(2)}\right]\right)$ $\displaystyle\in\operatorname{\mathbb{R}}^{m\times h}$ (14) $\displaystyle E^{(4)}$ $\displaystyle=f_{8}\left(E^{(3)}\right)$ $\displaystyle\in\operatorname{\mathbb{R}}^{m\times h}$ $$

If the encoder uses only a single layer, the first layer of the decoder (Equation [11](#S4.E11)–[12](#S4.E12)) is dropped and the node embeddings $H^{(0)}$ are used as input instead. The model parameters are optimized w.r.t. a reconstruction loss

$$ (15) $\operatorname{\mathcal{L}}_{AE}(\operatorname{\mathcal{G}})=\frac{1}{N}\sum_{G_{i}\in\operatorname{\mathcal{G}}}\frac{1}{m_{i}}\left\lVert X_{i}-E^{(4)}_{i}\right\rVert_{F}^{2},$ $$

where $||\cdot||_{F}$ denotes the Frobenius norm. A similar loss was used in (Cen
et al., ) to reconstruct node attributes, whereas our model operates on edge-attributed graphs. We denote this variant of our model as *NF-GNN-AE*.

### 4.5. One-Class Network Flow Graph Neural Network

Though autoencoder models perform well in practice, they don’t optimize an anomaly detection objective directly. *Deep SVDD* (Ruff et al., ) combines *Support Vector Data Description (SVDD)* (Tax and Duin, ) with a neural network for anomaly detection in a learned latent space. The main idea is to learn a transformation into a latent space such that most instances are mapped into a hypersphere in that space, and anomalous instances will fall outside of the hypersphere.

We propose a one-class graph neural network consisting of our representation learning module and an additional pooling layer, which summarizes each input graph into a single feature vector, similarly as for the supervised graph classifier.
The model parameters are optimized w.r.t. a one-class loss

$$ (16) $\operatorname{\mathcal{L}}_{OC}(\operatorname{\mathcal{G}})=\frac{1}{N}\sum_{G_{i}\in\operatorname{\mathcal{G}}}\left\lVert h_{i}-\mu\right\rVert_{2}^{2}+\frac{\lambda}{2}\sum_{i=1}^{4}\left\lVert W_{i}\right\rVert_{F}^{2},$ $$

where $\mu\in\operatorname{\mathbb{R}}^{h}$ denotes the center of the hyper-sphere in latent space. The center is initialized with the mean embedding vector of all graphs in $\operatorname{\mathcal{G}}$ after the first forward-pass and does not change thereafter. The second part of the loss regularizes the model parameters to limit model complexity. Bias vectors have been removed from all layers to prevent trivial solutions (Ruff et al., ). We denote this variant of our model as *NF-GNN-OC*.

## 5. Experiments

**Table 1. Weighted recall and precision scores for the three supervised tasks. For competing methods, we report the scores provided by the respective authors. For our baselines and our model, scores are reported in terms of mean and standard deviation over 30 independent data splits.**
|  | Weighted Recall | Weighted Precision |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
|  | Binary | Category | Family | Binary | Category | Family |
| Flows (Lashkari et al., ) | $88.30$ | $48.50$ | $25.50$ | $85.80$ | $49.90$ | $27.50$ |
| Flows + Static + API Calls (Taheri<br>et al., ) | $95.30$ | $81.00$ | $61.20$ | $95.30$ | $83.30$ | $59.70$ |
| Conversations (Abuthawabeh and<br>Mahmoud, ) | $89.00$ | $79.64$ | $66.59$ | $86.65$ | $80.20$ | $67.21$ |
| SVM-LIN | $96.26\pm 2.12$ | $72.83\pm 10.03$ | $28.74\pm 15.56$ | $96.72\pm 1.49$ | $87.31\pm 0.80$ | $90.35\pm 0.37$ |
| SVM-RBF | $96.20\pm 1.51$ | $85.42\pm 3.84$ | $49.96\pm 16.20$ | $96.64\pm 1.06$ | $89.13\pm 2.18$ | $91.52\pm 0.98$ |
| KNN | $95.71\pm 2.05$ | $78.10\pm 12.29$ | $42.53\pm 17.86$ | $95.75\pm 1.96$ | $87.08\pm 2.40$ | $90.92\pm 0.76$ |
| DT | $92.65\pm 4.13$ | $73.42\pm 12.19$ | $45.98\pm 30.81$ | $93.79\pm 2.80$ | $85.63\pm 6.59$ | $85.72\pm 18.57$ |
| RF | $95.85\pm 2.00$ | $84.30\pm 8.24$ | $56.06\pm 19.60$ | $96.24\pm 1.60$ | $90.32\pm 2.60$ | $91.67\pm 0.99$ |
| ADA | $96.38\pm 1.62$ | $76.02\pm 12.67$ | $42.17\pm 28.82$ | $96.67\pm 1.31$ | $83.97\pm 6.72$ | $87.88\pm 13.35$ |
| MLP | $97.19\pm 1.19$ | $85.69\pm 4.46$ | $49.56\pm 17.75$ | $97.29\pm 1.07$ | $89.28\pm 2.49$ | $90.23\pm 4.32$ |
| NF-GNN-CLF | $\mathbf{99.42\pm 0.45}$ | $\mathbf{95.41\pm 1.48}$ | $\mathbf{91.37\pm 8.39}$ | $\mathbf{99.44\pm 0.44}$ | $\mathbf{96.14\pm 1.07}$ | $\mathbf{93.62\pm 2.52}$ |

We evaluate our approach on a graph dataset that we extract from the network traffic data provided by the CICAndMal2017 dataset (Lashkari et al., ).
We focus on this datasets since it addresses several common defects shared by other existing datasets, allowing for a realistic and meaningful evaluation. These issues are addressed by providing a sufficient number of malware samples from diverse malware categories and families with a realistic distribution of benign and malicious applications. To accurately capture dynamic behavior, each application is executed on an actual physical device instead of an emulator or a virtual machine.

### 5.1. Dataset Preparation

Our extracted dataset consists of 2126 samples, where each sample corresponds to one instance of an android application installed and executed on a mobile phone. For each sample, all network flows within the network during execution are captured. For each flow, 80 features are recorded, including, e.g., the number of packets sent, mean and standard deviation of the packet length, and minimum and maximum interarrival time of the packets.
For a more detailed description of the data collection process, we refer to (Lashkari et al., ).

For each sample, 3 different labels are available, a binary label indicating whether the application is malicious or not, a category label with 5 possible values indicating the general class of malware, and a family label with 36 different values indicating the specific type of malware. Malware families with fewer than 9 samples have been removed to ensure a reasonable split into train, validation, and test sets. Consequently, for the family prediction task, only 2071 samples are available.

For each sample, we extract a graph as described in Section [3](#S3) and remove the flow-id, timestamp, and endpoint IP and port information from the feature set. Additionally, we remove all features that are constant among all edges of all graphs, leaving 330 edge features.

To be able to compare against baselines apart from flow- and conversation-based methods and our graph neural network models, we construct additional datasets, which represent each sample by a single feature vector instead of a graph. We consider three different feature sets:

- (1)
Flow Features For each sample, we aggregate the features of all flows for this sample using the same aggregation functions we used for deriving the edge feature vectors and concatenate the aggregates to a 318-dimensional feature vector.
- (2)
Graph Features To evaluate the importance of the graph topology for the baseline models, we extract a set of structural features from each graph. In particular, we extract 2 global features (global clustering coefficient and assortativity) and 8 local node-features (degree, number of 2-hop neighbors, clustering coefficient, avg. neighbor degree, avg. neighbor clustering coefficient, number of edges in egonet, number of edges leaving egonet, betweenness centrality) that are aggregated over all nodes in the graph, again using the same aggregation functions. All extracted graph features are concatenated, leading to a 40-dimensional feature vector.
- (3)
Combined Features To provide access to both types of features, we concatenate the flow and graph features to a combined 358-dimensional feature vector for each sample.

Again, all constant feature columns have been removed. All feature matrices, including the edge feature matrices for our model, are standardized before training.

### 5.2. Supervised Malware Detection and Classification

We consider three supervised tasks, binary, category, and family classification. To ensure a fair and unbiased comparison, we follow a rigorous evaluation protocol.

#### 5.2.1. Experimental Setup

First, we split the dataset into a train, validation, and test part. Each model is trained on the training set, hyper-parameters are chosen based on validation set performance using a grid search, and results are reported on the test set using the optimal hyper-parameter values. All experiments are repeated on 30 randomly generated splits, and mean and standard deviation of the results are reported.

To ensure a balanced training set, we sample 100, 25, and 5 samples per class for training for binary, category, and family classification, respectively. For binary and category classification, 5% of the remaining samples are sampled in a stratified fashion for validation. The remaining samples are used for testing. For family prediction, 20% of the non-training samples are chosen for validation to account for smaller class sizes. Stratification ensures that smaller classes are represented appropriately in the validation set.

Again, to account for class imbalance, we report weighted precision, recall, and F1 scores. In all considered settings, we checked that our models outperform the respective best competitor with statistical significance at $P<1e-5$ according to a Wilcoxon signed-rank test.

We compare our model against 7 baseline algorithms with different inductive bias, *Support Vector Machine (SVM)* with linear and RBF-kernel, *k-Nearest Neighbor Classifier (KNN)*, *Decision Tree (DT)*, *Random Forest (RF)*, *Adaboost (ADA)* and a *Multi-Layer Perceptron (MLP)* with up to two dense layers and *ReLU* and *softmax* activations.
Additionally, we compare our graph-based approach against two existing flow-based approaches (Lashkari et al., ; Taheri
et al., ) and one conversation-based approach (Abuthawabeh and
Mahmoud, ). Since no source code has been made available, we report the scores provided by the respective authors. Results have been provided only for a single data split.

For all neural network models, we use early stopping based on validation set performance using a patience of 20 epochs and a maximum of 1000 epochs. The default learning rate for all MLP-models is fixed as $1e-3$. For our model, we additionally apply dropout regularization before each dense layer and on the propagation matrices. All considered hyper-parameter values for all models are provided in Appendix [A](#A1).

Since the original feature vectors are rather high-dimensional, we introduce an additional hyper-parameter for each baseline model indicating whether or not to perform *Principle Component Analysis (PCA)* as feature reduction before training where 95% of the variance in the data is retained.

Figure: Figure 3. Weighted F1 scores for the three supervised tasks using different feature sets. Results are reported in terms of mean and standard deviation over 30 independent data splits.
Refer to caption: /html/2103.03939/assets/x6.png

Figure: Figure 4. Performance of our model on supervised tasks with different numbers of layers.
Refer to caption: /html/2103.03939/assets/x7.png

#### 5.2.2. Detection and Classification Performance

Detection and classification results for all three tasks are reported in terms of weighted recall and precision in Table [1](#S5.T1).
For each of our baseline model, the best feature set (Flow, Graph, or Combined) has been chosen based on validation set performance.

While some baselines perform notably weaker than others, we can observe that all baseline models still exceed the best results reported for flow classification in (Lashkari et al., ) in terms of both recall and precision, in most cases by a large margin.

Flow classification with an added static detection model and additional API-call features (Taheri
et al., ) performs better than some of our weaker baselines, especially in terms of recall. However, this approach is outperformed in terms of precision by all our baselines on category and family prediction. Our stronger baselines can outperform this approach, sometimes even by a large margin, except in terms of recall for family classification. It is important to note that (Taheri
et al., ) use additional data compared to our baselines and our model. Our approach could, in principle, be extended to also use this additional data and thus further boost performance.

Conversation-level detection (Abuthawabeh and
Mahmoud, ) performs worse than (Taheri
et al., ), except for family classification. This competitor outperforms all of our baselines in terms of recall on the family classification task. In terms of precision, however, all of our baselines outperform all competitors by a significant margin.

The competitive and sometimes even vastly superior performance of our baselines already supports the main motivation of our approach to detect and classify malware using network flow graphs.
Notably, this performance has been achieved even under a rigorous evaluation protocol and using relatively small training sets. In comparison, the competitors have used training set sizes between 60% and 80%.

Our proposed graph neural network model NF-GNN-CLF can further boost performance significantly compared to the baselines.
It is able to significantly exceed the performance of all competitors on all three tasks in terms of both recall and precision. In particular, compared to the best competitor, recall can be improved by 4.12%, 14.41%, and 24.78% for binary, category, and family classification, respectively. Precision is improved by 4.14%, 12.84%, and 26.41%. We wish to note that in most cases, the best competitor (Taheri
et al., ) uses additional data that is not available to our baselines and model. Compared to the other two competitors, the performance gain is even more significant. The largest improvement is achieved for the family classification task with a performance increase of over $65\%$ compared to flow classification (Lashkari et al., ).

#### 5.2.3. Importance of Different Feature Sets

To get more insight into the importance of different feature sets for our baseline models, we compare their performance in terms of weighted F1 score on different feature sets in Figure [3](#S5.F3). We can observe that almost all baseline models perform best on the combined flow and graph feature set.

As a notable exception, the linear SVM performs best on category and family classification using only the graph features, and adding flow features significantly hurts performance. However, even using only graph features, this baseline still performs worst among all baselines. Similarly, DT and ADA perform best using only graph features for family classification but are also outperformed by other baselines using the combined feature set.
In most cases, the combination boosts performance significantly over the best individual feature set.

Our model operating on the raw graphs still outperforms all baselines.

#### 5.2.4. Influence of the Number of Network Layers

To further examine the influence of the number of layers on our model’s performance, we compare different choices for the supervised classification tasks in Figure [4](#S5.F4). We can observe that modeling 2-hop interactions between endpoints can boost performance on the binary prediction tasks, while direct interactions are more crucial for the remaining two tasks. In general, performance remains relatively stable for different numbers of layers.

**Table 2. AUROC scores for unsupervised malware detection in terms of mean and standard deviation over 30 independent data splits. Our models use the raw graphs as input instead of the features extracted for the baseline models.**
|  | OC-SVM-LIN | OC-SVM-RBF | LOF | KDE | IF | MLP-AE | MLP-OC | NF-GNN-AE | NF-GNN-OC |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Flow | $57.17\pm 4.81$ | $70.01\pm 1.90$ | $73.15\pm 1.22$ | $72.50\pm 1.03$ | $70.39\pm 1.12$ | $71.64\pm 1.20$ | $81.29\pm 4.07$ | $\lvert$ | $\lvert$ |
| Graph | $54.60\pm 19.32$ | $67.19\pm 2.89$ | $58.57\pm 5.12$ | $91.79\pm 0.66$ | $90.73\pm 1.31$ | $89.56\pm 0.77$ | $94.00\pm 1.32$ | $95.34\pm 0.85$ | $\mathbf{96.75\pm 1.22}$ |
| Combined | $58.21\pm 4.83$ | $76.07\pm 1.78$ | $77.94\pm 1.56$ | $86.60\pm 1.07$ | $85.73\pm 2.21$ | $83.04\pm 0.78$ | $94.03\pm 4.47$ | $\lvert$ | $\lvert$ |

Figure: Figure 5. AUROC scores for unsupervised malware detection using different fractions of training samples. The right-hand figure provides an enlarged view of the upper part of the left-hand figure.
Refer to caption: /html/2103.03939/assets/x8.png

Figure: Figure 6. AUROC scores for unsupervised malware detection using different feature sets.
Refer to caption: /html/2103.03939/assets/x9.png

### 5.3. Unsupervised Malware Detection

We further evaluate our approach in a more realistic unsupervised setting, where no labels are available for training.

#### 5.3.1. Experimental Setup

Our experimental setup is the same as in the supervised case with a few adjustments. To ensure a realistic distribution of benign and malicious samples, we perform stratified sampling to first split 20% of the samples for training and then 10% of the remaining samples for validation. The remaining samples are used for testing. All algorithms obtain access to the labeled validation set for hyper-parameter optimization, but training is still unsupervised. We evaluate detection performance using AUROC since it inherently adjusts for class imbalance (Campos et al., ).

We evaluate against a set of popular baseline algorithms for anomaly detection, *One-class SVM (OC-SVM)* with linear and RBF-kernel, *Local Outlier Factor (LOF)*, *Kernel Density Estimation (KDE)*, *Isolation Forest (IF)*, *Autoencoder with dense layers (MLP-AE)* and *One-Class Neural Network with dense layers (MLP-OC)*. Again, all considered hyper-parameter values are provided in the supplement.
Since the flow- and conversation-based competitors (Lashkari et al., ; Taheri
et al., ; Abuthawabeh and
Mahmoud, ) only consider supervised detection and classification, we are not able to include them for comparison.

#### 5.3.2. Detection Performance

Table [2](#S5.T2) shows the detection results for different feature sets.
Results for different feature sets are additionally visualized in Figure [6](#S5.F6).
We can observe that several models report better prediction performance using only structural graph features. Thus, compared to the supervised setting, it is even more important to consider the topology of the network flow graph. While both neural network baselines, as well as KDE and IF already exhibit high detection performance, our models can again boost performance by a significant margin, demonstrating the importance of learning suitable representations from network flow graphs. We wish to emphasize that the performance of our unsupervised models, NF-GNN-AE and NF-GNN-OC, almost matches that of their supervised binary classification counterpart, NF-GNN-CLF, even without any labels provided for training.

#### 5.3.3. Influence of the Training Set Size

In practice, there is often a shortage of available training data, even unlabeled data. Thus, we further investigate performance using different amounts of training data where we gradually reduce the fraction of training samples from 20% to 1%. For each training set size, a new grid search is performed to determine the best hyper-parameters for each model. Figure [5](#S5.F5) shows that while some models perform worse with more available training data, possibly due to overfitting to anomalies in the training set, especially MLP-OC and NF-GNN-OC benefit from more training data. For all training set sizes, both of our models consistently outperform all competing baselines.

## 6. Conclusion

We proposed a novel network flow graph-based approach to malware detection and classification, where we monitor network traffic generated by a candidate application and extract a flow graph, which models communication between devices during the considered time frame. In addition, we proposed a novel edge feature-based graph neural network model along with three different model variants for supervised and unsupervised settings. Empirically, we found that even baseline models operating on manually extracted graph and flow features perform very well in all settings.
In addition, our proposed models automatically learn suitable representations of network flow graphs and can boost performance even further, significantly outperforming all competitors on all tasks.
Ablation studies examined the influence of different feature sets, the number of network layers, and training set size on detection and classification performance. In future work, we plan to consider additional network architectures, such as attention, model temporal dynamics, and consider explainability of model decisions.

###### Acknowledgements.

###### Acknowledgements.

## Appendix A Hyper-Parameter Optimization

For the sake of a fair comparison, hyper-parameters of all models are optimized by a grid search based on performance on a separate validation set. For each algorithm, we consider a set of possible values for each of its adjustable hyper-parameters. While some common choices can be found in the literature, for the remaining hyper-parameters, we determine potential values, which seem most promising within the available computational budget. The considered hyper-parameter values for all supervised models can be found in Table [3](#A1.T3). The values considered for the unsupervised models are provided in Table [4](#A1.T4).

**Table 3. Hyper-parameter values used in grid search for supervised algorithms.**
| Algorithm | Parameter | Values |
| --- | --- | --- |
| Support Vector Machine (SVM) | $C$ | $[2^{-7},2^{-6},\dots,2^{7}]$ |
|  | $\gamma$ (RBF-kernel) | $[2^{-7},2^{-6},\dots,2^{7}]$ |
| k-Nearest Neighbor Classifier (KNN) | num. neighbors | $[1,2,3,5,8,13,21]$ |
| Decision Tree (DT) | max. depth | $[2,5,10,None]$ |
|  | max. features | $[sqrt,None]$ |
| Random Forest (RF) | num. estimators | $[10,100,1000]$ |
|  | criterion | $[entropy,gini]$ |
|  | max. features | $[sqrt,None]$ |
| Adaboost (ADA) | num. estimators | $[10,100,1000]$ |
|  | learning rate | $[1e-3,1e-2,1e-1,1]$ |
| Multi-Layer Perceptron (MLP) | num. layers | $[1,2]$ |
|  | num. hidden | $[16,32,64,128]$ |
|  | L2-reg. | $[0,1e-1,1e-2,1e-3,1e-4]$ |
| NF-GNN-CLF (ours) | num. layers | $[1,2]$ |
|  | num. hidden | $[16,32,64,128]$ |
|  | learning rate | $[1e-3,1e-2]$ |
|  | dropout prob. | $[0,0.2,0.4,0.6]$ |
|  | pool | $[mean,add,max]$ |

**Table 4. Hyper-parameter values used in grid search for unsupervised algorithms.**
| Algorithm | Parameter | Values |
| --- | --- | --- |
| One-class SVM (OC-SVM) | $\nu$ | $[1e-2,1e-1]$ |
|  | $\gamma$ (RBF-kernel) | $[2^{-10},2^{-9},\dots,2^{10}]$ |
| Local Outlier Factor (LOF) | num. neighbors | $[1,2,3,5,8,13,21]$ |
| Kernel Density Estimation (KDE) | bandwidth | $[2^{0.5},2,\dots,2^{5}]$ |
| Isolation Forest (IF) | num. estimators | $[10,100,1000]$ |
|  | max. features | $[256,None]$ |
| Autoencoder (MLP-AE) | num. layers | $[1,2]$ |
|  | num. hidden | $[16,32,64,128]$ |
|  | L2-reg. | $[0,1e-1,1e-2,1e-3,1e-4]$ |
| One-class MLP (MLP-OC) | num. layers | $[1,2]$ |
|  | num. hidden | $[16,32,64,128]$ |
|  | L2-reg. | $[0,1e-1,1e-2,1e-3,1e-4]$ |
| NF-GNN-AE (ours) | num. layers | $[1,2]$ |
|  | num. hidden | $[16,32,64,128]$ |
|  | learning rate | $[1e-3,1e-2]$ |
|  | dropout prob. | $[0,0.2,0.4,0.6]$ |
|  | pool | $[mean,add,max]$ |
| NF-GNN-OC (ours) | num. layers | $[1,2]$ |
|  | num. hidden | $[16,32,64,128]$ |
|  | learning rate | $[1e-3,1e-2]$ |
|  | dropout prob. | $[0,0.2,0.4,0.6]$ |
|  | pool | $[mean,add,max]$ |

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: 1] The following statement in Line 83 "such as GCN (Kipf & Welling, 2017) [...] In these models, messages exchanged between neighboring nodes do not depend on the number of message recipients." appears to be false. In the GCN the messages of neighbours are normalised by the square rooted node degrees of both nodes involved in the edge. Therefore, the number of message recipients is taken into account in the weighting of messages in the GCN. In fact, it seems to me that the normalisation scheme of the GCN considering both outgoing and incoming number of neighbours could give rise to an interesting extension of your FlowGAT model, although it would violate Kirchhoff's law. 

2] Your proposed FlowGNN is not described in sufficient detail: 

2.1] Since you now represent each node via two hidden representations $h^{rv}$ and $h^{fw}$ is unclear to me what the hidden states $h_i$ in Equations (9), (10) and (11) refer to. 

2.2] It is unclear how the hidden states $h^{rv},$ $h^{fw}$ and $h_i$ are initialised. 

2.3] The attention scheme you use in your FlowGNNs is not the standard GAT attention scheme since you do not have the LeakyReLU and one less weight matrix in the attention scheme (see Equations (16) and (17)). This difference should be better motivated, since you discuss the GAT model as a corresponding model to your FlowGAT model. 

2.4] It is unclear to me why you use a GRU model on the sequence $h^{rv}, m^{fw}$ of length two and do not use an MLP in which these are concatenated. 

2.5] Similarly it is unclear how the other variants of your model, e.g., the FlowGT, are computed. It would be great if you could provide the associated model equation. I am particularly curious about the FlowGT model since it is unclear to me how forward and backward message passing works in a model that freely rewires the entire graph in its attention scheme. 

3] In Section 3.3 you provide a promising start to a theoretical result on the expressivity of your model. It would however be more concise if you could formalise your discussion in a Theorem such that your theoretical claims are more easily to identify and more precisely proofed. 

4] It seems to me that also your experimental analysis could be improved:

4.1] It is customary in many papers to experiment with models of different depths, i.e., with varying numbers of layers, and to report the results for the optimal number of layers as established in a grid search. I recommend that you take this approach to your experiments and in particular, experiment with deeper models, since your maximal number of message passing layers appears to be optimal and it remains unclear whether even deeper models would perform better. 

4.2] I am unsure why you use the global maximum pooling (see Line 409). On graph level tasks often sum pooling is observed to be optimal. Could you please motivate this seemingly unusual choice?


5] Minor comment: In Lines 272-4 your sentence "However, since the flow of some arbitrary physical resource from node $j$ to node $i$ in a flow graph may also depend on all descendants of the node $i$" begs the question to me, why you do not consider bidirectional edges in these cases. Answering this question in your manuscript would strengthen the paper in my view.
soundness: 2
strengths: - The idea of enforcing Kirchhoff's first law in GNNs is interesting.
- The methodological propositions in this paper, i.e., the normalisation over outgoing edges and both a forward and backward pass on DAGs, are sensible.
- In practice, the proposed methods appear to work somewhat well.
summary: In the submitted manuscript the authors pose the problem of Graph Neural Networks (GNNs), designed to study flows on graphs, being unable to distinguish non-isomorphic graphs. The authors then go on to propose a variation of the attention mechanism of the Graph Attention Network (GAT) in which attention scores are not normalised over incoming, but rather outgoing edges, which means that the resulting GNN adheres to Kirchoff's first law of information preservation. They furthermore extend the DAGNN, to the DAFlowGNN, which now includes both a forward and a backward pass through the directed acyclic graph. Subsequently, they offer some theoretical discussion of what graphs may be distinguishable by their DAFlowGNNs. Finally, their FlowGNNs and DAFlowGNNs are shown to outperform several baseline models on the majority of the studied datasets.
weaknesses: Please find further details on my listed weaknesses in my questions below.
- The empirical evidence in favour of your model is not very strong, in the sense that you are sometimes outperformed by the Graph Isomorphism Network (published in 2019) and some improvements are marginal.
- The proposed model is not described in sufficient detail, i.e., not all aspects of your proposed model are well-motivated, the notation is not always clearly defined and certain models such as the FlowGT are not discussed at all.  
- The theoretical component of this work is not formal and rather small. This would be fine if there was overwhelming empirical evidence in favour of the proposed method, which does not seem to be the case either. So, I want to suggest to the authors to formalise and to further extend their theoretical study.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: Intuition behind reverse pass in DAFlowGNN should be revisited: it is not completely clear why it is needed, particularly why "flow of some arbitrary physical resource from node j to node i in a flow graph may also depend on all descendants of the node i," (lines 272-273)?
soundness: 3
strengths: Very simple and intuitive idea: also its motivation by emphasizing the difference of informational and flow graphs immediately captures reader's interest.
summary: The authors propose Flow Graph Neural Networks (FlowGNNs) and their extension to directed acyclic graphs with the target of ensuring the conservation laws associated with the flow of physical resources, in certain graphs (flow graphs). Their idea is very simple: normalize outgoing messages instead of incoming ones during message passing in GNNs. Doing so (flow attention), duplication, which would be a conservation violation, is avoided. To extend this simple idea to directed acyclic graphs (DAFlowGNN), this normalization step as part of a forward pass, follows a propagation stage of hidden states from nodes back to their predecessors (reverse pass). In this way all nodes of the graph connected with some given node are taken into account in computing its representation. FlowGNNs are shown to be more expressive than other GNNs for DAGs. In the experiments, they equip attention-based architectures (GAT, GT) with the proposed outgoing-message normalization (i.e. FlowGAT, FlowGT) and apply them for binary and multiclass graph classification tasks on power grid datasets and for graph regression tasks (i.e. predict values of properties) for a graph dataset of operational amplifiers. FlowGNN-based architectures are generally more performant (respectively: balanced accuracy and RMSE metrics) over popular GNNs (or DAG-based GNNs), closely followed by GIN-based and DAGNN models.
weaknesses: - Performance results in some cases for FlowGNNs are mixed and the benefits of the approach are not directly realized in the experiments (Table 3). In other cases, a simple GNN like GIN can be more performant (Table 1). So there is room for improvement in the consistency of the gains reported.   

- Typically the notation (u, v) for a directed edge is assumed to denote a connection from node u to node v, not the other way around as in here.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: Please refer to questions mentioned in the weakness sections.
soundness: 3
strengths: 1. This paper proposes a new flow graph neural network to address the constraint of resource conservations.
2. The framework is extended to DAGs, which enable discrimination between non-isomorphic flow graphs.
summary: The paper introduces FlowGNNs, a framework designed to improve GNNs for flow graphs where resource conservation is essential. FlowGNNs adapt attention mechanisms to prevent arbitrary duplication of node information by normalizing outgoing messages, thus enforcing resource conservation. Additionally, the paper presents DAFlowGNN, which extends FlowGNNs to directed acyclic graphs (DAGs), enabling the differentiation of non-isomorphic flow graphs that standard DAG-specific GNNs cannot distinguish. Experiments on electronic circuits and power grid data show FlowGNNs’ and DAFlowGNN’s superiority over traditional GNNs in classification and regression tasks.
weaknesses: 1. The novelty of this paper seems limited, as author just normalize the attention scores across outgoing neighbors instead of across incoming neighbors. The novelty of this paper needs to illustrate better. Specifically, for non-expert readers, it is unclear how significant impact such change leads to.

2. The relationship between FlowGNN and DAFlowGNN is unclear. While DAFlowGNN is a DAG version of FlowGNN, it is unclear what the differences of two GNNs in terms of applicability, e.g.  Are they both applicable to flow graphs?  For their architectures, it is unclear what are the main differences.

3.  In Section 3.3, it is better to illustrate in terms of rigor theorems  that DAFlowGNN is more expressive than any DAGNN, as the current version is not easy to follow.

4. For the experiment section, electronic circuits and power grids both belong to  electrical domain, which makes it doubtful that the proposed GNNs may have narrow applications limited by resource conservations. Can authors show more applications and compare results? Another concern is the computational expenses. As author admit in the paper, DAFlowGNN is twice as computationally expensive as DAGNN, but the efficiency experiments are missing, and it is necessary to discuss what techniques can be used to reduce computational time.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 2
questions: -	Could the authors comment on the absence of conservation of flow and how this impacts the discussions throughout the paper? Do you perhaps agree that the paper and the naming of the techniques might be changed to prevent the reader from being misled that the “flow” is indeed conserved?
-	The authors could show more convincingly that DAFlowGNN can discriminate the two DAGs of Figure 3. One (better) way would be to prove it slightly more formally and precisely in the paper, showing what are the benefits of running the reverse pass compared to the forward pass only. An alternative would be to run an ablation study to show it on synthetic graphs. Could  you comment on this?
-	Could the authors provide a revised table of numbers where only the best performing configuration on the validation set is used to provide a risk estimate on the test set? Provided that model selection was already performed, it would amount to re-evaluate just the best configuration for each model and dataset. This would allow us to fairly compare and evaluate the benefit of DAFlowGNN on the Ckt-Bench101.
-	Not really a comment, but it would help to refer to specific figures 1.a-1.b in the text rather than Fig 1.
soundness: 2
strengths: The paper is generally well written and presented, figures are clear, neat, and well supported by captions. The organization feels a bit off, mostly due to the alternating between the new attention mechanism and the DAG architecture throughout the paper methods and experiments, but the intentions and message of the authors remain clear.

It deserves mention the fact that the paper is self-contained and strives to get one simple message across, namely that we could “invert” the way we compute edge weights in attention mechanisms to prevent duplication of the same information across multiple outgoing edges. The technique introduced by authors is properly motivated and its scope is well defined.

The paper is also very detailed in the experimental section, and it seems that one might be able to easily replicate the results provided in the tables. The empirical comparison considers a reasonable number of baselines and datasets, considering all models have been retrained and a small model selection has been run. Despite results on the PowerGraph dataset do not look particularly exciting, I believe the Ckt-Bench101 is the dataset where the architectural bias of the proposed architecture might provide convincing evidence (although there are some concerns to be addressed). 

A simple discussion hints at DAFlowGNN being able to discriminate graphs that other recent neural networks for DAGs cannot, although it is unclear the influence of the normalization operation compared to the reverse pass (see questions). I believe the contribution lies at the intersection between recursive architectures for Directed Positional Acyclic Graphs (DPAGs) and the recent architectures for DAGs (that need to generalize without making any causal assumption on the parent nodes).

Overall, this paper proposes a simple but interesting architectural change that has much sense in specific contexts and I believe it can help to advance our understanding of the field.
summary: The authors tackle the expressiveness problem of recursive neural networks and GNNs when these are applied to a specific family of real-world graphs. In fact, it might be important to model the conservation of “information flow” in graphs like power grids and electronic circuits, and to this end the authors introduce an architectural bias that is reminiscent of graph attention. The new mechanism normalizes each incoming message according to the outgoing edges of the source node, rather than based on the incoming set of edges for the target node. This way, the contribution of each node is not duplicated during message-passing.
In addition, they propose a recursive network tailored to DAGs (DAFlowGNN) that incorporates said bias. The authors show that DAFlowGNN can distinguish non-isomorphic DAGs where recent models specifically tailored to DAGs fail.
weaknesses: It appears that the paper mentions several times the concept of “conservation of flow”, e.g., Korchhoff’s law, but my understanding is that there is no guarantee or mention that the flow is conserved at all: nodes will receive a certain amount of message information (greater or smaller of a “full single message”) and will always output a “single” message to its outgoing edges, that is without duplicating information. There might be something I am missing, but if this is really the case then the impact of the paper would be greatly reduced. As a matter of fact, if flow is not conserved then it is not surprising at all that the GIN method has similar performances to FlowGAT on the PowerGraph benchmark, as both the sum aggregator and the flow attention weights are susceptible to degree changes (while GCN for instance would be susceptible to distributional changes in the neighborhood).

Similarly, the claims that the authors need to distinguish “all” non-isomoprhic DAGs (lines 265-266) might be misleading. For instance, let us focus on flow attention weights and not on DAFlowGNN. What happens if you take the circuit in Fig 1.b left and you compare it with “in” -> branch into R1 x2 -> merge into R2 --> out? If you do not take into account normalization for incoming edges, you might end up with the same result also with FlowGAT. In any case, despite the claim made in said lines, the authors only (partially) showed that DAFlowGNN could distinguish a particular pair of DAGs, not that it is universal with respect to all DAGs. To summarize, some claims should be clarified/adapted to reflect the real contributions of the paper and avoid general statements.

Despite its novelty, the paper fails to acknowledge and position itself compared to a whole line of less recent works on recursive and contextual architectures that are relevant because they often incorporate the same architectural bias than recent works. Before GNNs were applied to DAGs -- in reverse order compared to historical developments -- (contextual) recursive neural networks for DAGs [1,2] and their expressive power were completely characterized [3], and later the causality assumptions were relaxed to allow cycles in the computation [4, Scarselli et al. 2009].

Finally, there are some concerns on empirical results. The authors have correctly split the dataset into training/validation/test. The validation set should be used to select the best hyper-parameters for a specific model on a specific dataset (a process called “model selection”). Then, once the best hyper-parameter configuration has been found on the validation set, the model should be (possibly after retraining) evaluated on the unseen test set. Given the specific hold-out strategy adopted in the paper, it makes no sense to show results for all models with a certain number of layers, e.g., DAGNN-2/4 or DAFlowGNN-1/2. What the authors should show is the estimate of the risk using the best configuration attained by each model and dataset. Arguments like the ones made at lines 415-417 cannot stand against the correct process for risk estimation. In this regard, the authors are recommended to show results attained by each model using only the best configuration found on the validation set. This would allow a fair comparison of different *classes of* models rather than a comparison of simple point estimates that will likely be misleading. The authors can refer to slides 23-33 of Samy Bengio’s lecture: https://bengio.abracadoudou.com/lectures/theory.pdf.

[1] Sperduti, Alessandro, and Antonina Starita. "Supervised neural networks for the classification of structures." IEEE transactions on neural networks 8.3 (1997): 714-735.

[2] Frasconi, Paolo, Marco Gori, and Alessandro Sperduti. "A general framework for adaptive processing of data structures." IEEE transactions on Neural Networks 9.5 (1998): 768-786.

[3] Hammer, Barbara, Alessio Micheli, and Alessandro Sperduti. "Universal approximation capability of cascade correlation for structures." Neural Computation 17.5 (2005): 1109-1159.

[4] Micheli, Alessio. "Neural network for graphs: A contextual constructive approach." IEEE Transactions on Neural Networks 20.3 (2009): 498-511.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 3
questions: - The authors should clearly explain why FlowGNN fails to achieve state-of-the-art (SOTA) performance in the binary classification task while achieving SOTA in the multiclass classification task compared to baseline methods.
- The time and space complexity of the FlowGNN method should also be provided in the methodology section, which is necessary for comparison with the traditional graph attention mechanism.
- More recent DAG methods should be introduced in the experimental part for fair comparisons, such as GraphNOTEARS [1], ContextualDAG [2], and DAG [3].

[1] Fan S, Zhang S, Wang X, et al. Directed acyclic graph structure learning from dynamic graphs[C] Proceedings of the AAAI Conference on Artificial Intelligence. 2023, 37(6): 7512-7521.

[2] Thompson R, Bonilla E V, Kohn R. Contextual directed acyclic graphs[C]//International Conference on Artificial Intelligence and Statistics. PMLR, 2024: 2872-2880.

[3] Luo Y, Thost V, Shi L. Transformers over directed acyclic graphs[J]. Advances in Neural Information Processing Systems, 2024, 36.
soundness: 2
strengths: - FlowGNN modifies the traditional attention mechanism by normalizing across outgoing neighbors instead of incoming neighbors. This simple yet impactful change addresses the limitations of traditional attention mechanisms in modeling physical flows.
- Additionally, FlowGNN extends existing GNN frameworks to DAGs, which enables it to distinguish non-isomorphic flow graphs that standard GNNs cannot differentiate.
summary: This paper proposes a novel framework for graph neural networks (GNNs) called FlowGNN to handle conservation laws in graph-structured data involving resource flows, such as electrical grids and traffic networks. Different from existing GNN methods, FlowGNN employs a new flow attention mechanism that aggregates messages across outgoing neighbors to respect resource conservation. Furthermore, this framework is extended to Directed Acyclic Graphs (DAGs) and can distinguish non-isomorphic flow graphs. Experiments on the power grid and electronic circuit datasets demonstrate the superior performance of FlowGNN in graph-level classification and regression tasks.
weaknesses: - The writing of this paper could be improved. For instance, the introduction is overly long (about 2 pages) and lacks clarity, which makes it difficult for readers to understand the key motivations of the work. 

- The theoritical analysis of FlowGNN is limited. This paper can not provide a comprehensive exploration of the expressiveness and computational complexity of FlowGNN compared to standard GNNs. Although the practical effectiveness of FlowGNN are demonstrated through experiments, a deeper theoretical understanding of how the proposed flow attention mechanism help FlowGNN handle resource conservation and distinguish non-isomorphic flow graphs is needed. 

- The novelty of FlowGNN is limited. This paper primarily focuses on modifying the attention mechanism by normalizing across outgoing neighbors instead of incoming ones. However, this adjustment does not introduce new architectures or theoretical innovations beyond those found in existing methods. Additionally, the extension of FlowGNN to DAGs represents only an incremental advancement.

- The experimental results are not convincing, and the baseline methods are not strong enough. Although the authors compare FlowGNN method with some widely used baseline methods like GCN, GAT, GIN, GT and PACE, these are neither the latest nor the most competitive, which undermines the significance of the reported performance.