Projective Ranking-based GNN Evasion Attacks

Graph neural networks (GNNs) offer promising learning methods for graph-related tasks. However, GNNs are at risk of adversarial attacks. Two primary limitations of the current evasion attack methods are highlighted: (1) The current GradArgmax ignores the"long-term"benefit of the perturbation. It is faced with zero-gradient and invalid benefit estimates in certain situations. (2) In the reinforcement learning-based attack methods, the learned attack strategies might not be transferable when the attack budget changes. To this end, we first formulate the perturbation space and propose an evaluation framework and the projective ranking method. We aim to learn a powerful attack strategy then adapt it as little as possible to generate adversarial samples under dynamic budget settings. In our method, based on mutual information, we rank and assess the attack benefits of each perturbation for an effective attack strategy. By projecting the strategy, our method dramatically minimizes the cost of learning a new attack strategy when the attack budget changes. In the comparative assessment with GradArgmax and RL-S2V, the results show our method owns high attack performance and effective transferability. The visualization of our method also reveals various attack patterns in the generation of adversarial samples.

INTRODUCTION
G RAPHS consist of nodes and edges defined between these nodes. As an abstract data type, graphs have powerful modelling capabilities. By extracting attributes from entities and describing their relationships, graphs can represent a range of objects or technical systems in realworld situations, such as drug molecules [1], biological networks [2], and traffic networks [3], [4]. Graph neural networks (GNNs) have proven to be effective graph learning methods [5] for exploring graph data and have demonstrated promising performance on node classification [6], [7], link prediction [8], anomaly detection [9], [10], and graph classification [11]. For example, in biological chemistry, the GNNs are engaged in recognizing the chemical properties of molecules.
In practice, GNNs raise urgent security concerns, although they have garnered considerable attention in the context of complex graph-structured data applications [12], [13], [14], [15]. Generally, graph neural networks are regarded as the generalization of deep neural networks into graph data. However, GNNs inherit the vulnerability of deep neural networks despite possessing adequate expressive power. Several recent studies demonstrate that adversaries can attack GNNs [16], [17], [18], [19], [20], [21]. Among others, evasion attacks [22], [23] are notoriously dangerous. Attackers could perturb test samples to generate adversarial samples of a victim model trained on original clean data. On adversarial samples, the victim model will give incorrect results, different from those of clean samples.
Prior work on GNN evasion attacks has demonstrated that well-designed slight perturbations are able to significantly degrade the performance of the victim models [22].
• H. Zhang  This type of attack is tricky since adversarial samples are similar to clean samples in appearance [17]. Adding a few elaborate adversarial edges can dramatically reduce the classification accuracy of the victim models [23]. To create an adversarial example, attackers can change the features of few nodes or add/remove a few edges in a clean graph. A budget k with positive integer values controls the number of these perturbation operations to make their perturbations stealthy. Moreover, once the models are deployed, it is practical for attackers to launch the evasion attacks at any time [19].
The existing studies of evasion attacks on the GNN models mainly focus on node classification and link prediction, while few of them are designed for graph classification [16], [17], [19]. We note there are some limitations in those methods for graph classification, which need to be solved to improve the attack practicality.
• In the vanilla gradient-based attack method GradArgmax [22], the greedy mechanism uses the gradient on the graph in the perturbation process to make the perturbation decision. Although the gradient information could approximate the attack benefit to some extent, it ignores the long-term benefit of operation at each step [22]. Moreover, GradArgmax is not efficient since it needs the up-to-date gradient information to complete each step of all the perturbation operations.
• Attack methods [22], [24] use reinforcement learning (RL) to perturb clean samples and use the final predicted result on adversarial samples to estimate the attack benefit. When the perturbation budget changes, they have to be retrained to learn an attack strategy suitable for the new budget. In addition, we observe that RL-S2V [22], a known attack method, does not appear to be able to generate adversarial samples in high attack success rates when the perturbation budget increases [24].
Motivated by these observations, we summarize the arXiv:2202.12993v2 [cs.LG] 2 Nov 2022 challenges in building an effective evasion attack against GNNs for graph classification: (1) in the generation of powerful adversarial samples, how to measure the attack benefits of each operation based on the clean graph, and (2) how to adapt the learned attack strategy to changed perturbation settings (e.g., budget) with least effort.
To address these challenges, we first formulate the perturbation space composed of all possible perturbation operations and present four properties of it. Then, we propose an evaluation framework consisting of three principles decomposed from the adversary's expectation. We use these three principles as the design goal of our method and employ them to evaluate typical evasion attack methods. In our evaluation framework, we consider a basic fact in the evasion attack: an intelligent attacker always expects to choose the perturbation operation which will bring the most significant attack benefit at each perturbation step. This fact includes three critical principles for evasion attack: attack benefit, operation ranking and baseline graph. Finally, we propose the projective ranking method as an instantiation under the evaluation framework.
In our method, we expect to find a suitable metric that considers the attack benefits of each operation to rank them and then use this ranking directly to generate adversarial samples under different perturbation budget settings. Towards the first challenge, we employ the mutual information (MI) between elements of perturbation space and attackers' goals as a measure to evaluate the importance of each possible operation. We regard the perturbation space ranking as the learned attack strategy. Inspired by the projected gradient descent method, we propose to project the learned attack strategy into practical attackers' perturbations with the specified budget for the second challenge. Through this projection operation, the adjustment cost of the learned attack strategy is almost zero.
Our contributions are summarized below: • We formulate the perturbation space and its four properties, and we propose an evaluation framework for evasion attack methods and analyze typical methods from the principles of the framework.

•
We propose the projective ranking method. We first employ the mutual information to measure the attack benefits of a perturbation operation towards strong attack performance, then use the projection operation to reduce the cost of the strategy adaptation process by considering the transferability of attack strategies.

•
We conduct evaluations on several real world datasets and a synthesized dataset, and our attack method achieves high attack performance and effective transferability. The visualization of adversarial samples present various attack patterns and reveals the vulnerability of the victim model.
In this paper, we review different attack methods for graph classification in Section 2 and introduce the graph classification and evasion attacks in Section 3. In Section 4, we first formulate the perturbation space and show its four properties. Then we propose the evaluation framework of evasion attack methods and show the instantiation design of our method. Next, we show the detail of the projective ranking method. In Section 5, we use the evaluation frame-work to make a comparison evaluation of typical methods. In Section 6, we experimentally demonstrate the high attack performance and effective transferability of our method, and the attack patterns in our adversarial samples reveal the weaknesses of the victim model. Finally, we show the conclusion and discuss the future works in Section 7.

RELATED WORK
Current research shows that graph neural networks are vulnerable to adversarial attacks. According to the intention of attackers, the adversarial attack methods for graph classification include evasion attacks, backdoor attacks, and poisoning attacks.

Evasion Attack Methods on GNNs
Evasion attacks perturb the inputs of the GNNs during their inference phase and intend to degrade the performance of the victim model. Hence, the more the classification accuracy of the victim model decreases, the better the performance of an attack method. As the most intuitive approach, RandomSampling randomly perturbs the graph structure or nodes' features of clean graphs to generate adversarial samples. However, the attack performance of this method is lower than adding well-designed perturbations. In the GradArgmax method, the attackers own the ability to access the victim model. They first calculate the gradient information of the loss function on each possible perturbation operation, then use the gradient information to choose the perturbation operation that maximizes the loss of the victim model.
To better describe the perturbations on graph data, Dai et al. [22] proposed to employ the Markov decision process to model the whole perturbation process and use reinforcement learning to obtain an attack strategy on current clean samples. The graph data in the perturbation process is modeled as the state of reinforcement learning. The action space comprises all perturbation operations in the current state, and the final attack result defines the reward function. Benefiting from the modelling and learning ability of reinforcement learning, the attack performance of RL-S2V outperforms that of RandSampling and GradArgmax on synthetic data [22].
To improve the stealthiness of attack, Ma et al. proposed ReWatt to redefine the action space of reinforcement learning [24]. The perturbations generated by ReWatt are more unnoticeable since the edge numbers of adversarial samples are equal to those of clean samples. Besides the above attack methods, the attackers could also attack the components of GNNs if they know a specified operation is included in the victim model. For example, some methods introduce hierarchical pooling operations in the models, which selects typical nodes to compress the node number and determine the structure of the coarse graph [25], [26], [27]. Tang et al. proposed to attack the selecting operation in pooling operation [28]. By training a surrogate model with hierarchical pooling on some clean data, the attackers obtain the selecting function that simulates the victim model's hierarchical pooling. Based on this selection function, the attackers could obtain the adversarial samples that invalidate the pooling in the victim model. However, this method may not be available for attacking models that employ global pooling operations. A comparison of representative evasion attack methods are summarized in Table 1.

Differences in Evasion Attacks
In addition to the differences in technical methods, the evasion attack methods also have differences in perturbation space, the definition of imperceptible perturbations, the attacker's knowledge, and the attack goal. In the aspect of perturbation space, the attackers usually make perturbations by adding fake nodes with the fake features [29], modifying node features [30], adding or deleting edges [31]. In graph classification evasion attacks, ReWatt, RL-S2V, RandSampling and GradArgmax only modify graph structure. The attack method in [28] makes perturbations in node features or graph structure.
In the aspect of imperceptible perturbations, the distance between the original clean graph and the modified adversarial graph is usually limited by the perturbation budget, which is defined as the number of nodes modified or distance of feature vectors, or the number of edges modified by adding/deleting/rewriting. In the aspect of attackers' knowledge, based on how much information an attacker knows about the victim model, the attack methods are generally divided into white-box, grey-box, and black-box attack. A white-box attack means the attackers can access all information about the victim model like architecture, parameters, training input, and labels. Grey-box attack indicates that only limited information about the victim model, like training data labels, is available. As the strictest setting, the black-box attack only allows attackers to do queries of samples for output or labels [16].
In graph classification evasion attack, GradArgmax is a white-box attack method, RL-S2V and ReWatt are typical black-box attack methods based on reinforcement learning. In the aspect of the attackers' goal, the attacks are divided into untargeted attacks and targeted attacks. In an untargeted attack, the attackers expect the victim model to classify the adversarial samples into labels different from their original labels. As a more strict attack goal, targeted attacks attempt to fool the victim model by specifying the output categories of the adversarial samples.

Poisoning and Backdoor Attacks on GNNs
Besides evasion attacks, another two typical adversarial attacks on GNN models are poisoning attacks and backdoor attacks. The poisoning attacks [32] suppose the attackers own the ability to poison training data and label. In this way, the performance of the GNN models trained on poisoned data will degrade dramatically on clean samples. In backdoor attacks [33], [34], the attackers inject a fixed or adaptive trigger into clean training data and change their labels to the desired categories. As a result, the models trained on these data performs well on the clean samples but predicts the desired labels once the well-designed trigger is injected into the clean samples.

Graph Classification
Assuming G = {V, E} is a graph, where V = v 1 , . . . , v |V| is the set of nodes, E = e 1 , . . . , e |E| is the set of edges of graph G. The edges set E describes the structural information of G. It can also be expressed as the adjacency matrix A ∈ {0, 1} |V|×|V| , where A ij = 1 means the existence of the edge from v i to v j , otherwise A ij = 0. The features associated with nodes are expressed as matrix X ∈ R |V|×d , where the i-th row of X is the features of node v i and d is the dimension of features. So a graph can also be expressed as G = {A, X}.
In the graph classification, a set of graphs is denoted by G = {G i } N i=1 and a label y i ∈ Y = {1, 2, . . . , Y } is associated with each graph G i , where N is the number of graphs and Y is number of categories. The dataset is composed of pairs of graph and its label. In graph learning, the classifier f ∈ F : G → Y is trained and expected to learn the mapping from graph G to its label y with optimal parameters θ that minimize the below loss function: where L(·, ·) is used to measure the distance between the predicted and ground-truth labels. A general instance of L(·, ·) is the cross-entropy function.

Graph Neural Networks Model
The graph neural networks (GNNs) is a family of architectures of neural networks that are designed to process graph data G = {V, E}. These models iteratively update the expression of nodes by message passing and aggregation as below [35]: where N (v) is the set of neighbours of node v in graph G, h t v means the hidden expression of node v at time t ∈ {1, 2, . . . , T } and e vw is the features of the edge from node v to node w. M t (·, ·, ·) is the message functions and U t (·, ·) is the vertex expression updating functions. After the message passing phase, the expression of whole graph G is obtained by the readout operation: where R(·) is the readout operation, and it is invariant to permutations of the nodes. A general instance of R(·) is the max-pooling or sum-pooling.
In graph classification, the model f θ based on the above architecture is generally trained under an inductive learning setting, in which the classifier learns on training data D train and then make graph label prediction on test data D test .

Problem Formulation
Assuming a GNN model f θ is trained on clean graph samples and then employed to predict the category of graph data D = {G j } M 1 . In evasion attacks, an attacker T attempts to make unnoticeable perturbations on the original G to degrade the performance of this victim model f θ . We use T f (G) to indicate the attacker's perturbation on G which is specifically designed for the classifier f θ . In untargeted evasion attacks, the attackers expect the predicted category of an adversarial sample is different from its true category. More precisely, the objective of untargeted evasion attacks on the victim model f θ is Here G is the adversarial sample generated from the clean sample G, and I(·) is the binary indicator function. k is the perturbation budget of T f . Given specific k, I(·, ·; k) is a similarity measure function whose output is 1 when two input graph samples are semantically the same and 0 otherwise. Particularly, in targeted evasion attacks, the attackers expect the predicted category is a specified category y t , which is different from its true category y j . The objective of targeted evasion attacks is Note. The probability function p(·) can be employed as a substitute of I(·) to describe objective functions [16]. Given G j and budget k, we use O( G j ; k) to denote the value of objective function in equation (5)/(6) when using up all budget k (e.g., in equation (5),

PROPOSED APPROACH
Our projective ranking method mainly includes the ranking module and the projection module. In this section, we first formulate the perturbation space and propose the principles of our evaluation framework. Then we present the detail of the ranking module and the perturbation projection operation. Finally, we give an algorithm to show the generation of adversarial samples.

Attack Setting
In our method, given a victim model f θ , we assume that the attackers can have access to the nodes embedding and predictive probability distribution of f θ to learn the attack strategy. Then, only accessing the embedding of nodes, the attackers may utilize the learned strategy to attack any samples of the victim model under any budget setting.
To further explore the transferability of the learned strategy (in Section 6.5), we assume an intelligent attacker attempts to fool the victim models by accessing the nodes embedding of the target models based on the attack strategy learned from the other source models engaged in the similar data domain. We note that the attacker does not know any other knowledge (like the architecture or parameters of the target models) except for the embedding of nodes. This scenario reflects the vulnerability of the models that use the pre-training models [36].

Perturbation Space
In an evasion attack, an attacker T can perturb a clean sample G to obtain an adversarial sample G. We formulate the process of this perturbation on graph G as where ∆G = {∆A, ∆X} is the perturbation graph. To be more precise, the graph structure and node features of G are expressed as where A ∈ {0, 1} |V|×|V| is the adjacency matrix, X ∈ {0, 1} |V|×d is binary node features matrix, . |V| is the number of nodes in G, and d is the size of node features. m A ∈ {0, 1} |V|×|V| and m X ∈ {0, 1} |V|×d represent the masks of graph structure and node features respectively. I(add)/I(del) is the indicator function to show if adding/deleting edge operation is allowed in generating adversarial samples. is the Hadamard product and · is the scalar multiplication. Therefore, the perturbation graph ∆G = {∆A, ∆X} is actually defined by the combination of specified structure mask m A and feature mask m X . The similarity measure function in (5) and (6) is refined as where ||·|| 1 is the L1 Norm, k is the budget of perturbations. a is a scalar coefficient, and it is 1 if G is a directed graph and 1 2 otherwise since the adjacency matrix of undirected graph is symmetric.
Given the clean sample G, the perturbation space T(G) of G is defined as the set of all possible perturbation graph ∆G = {∆A, ∆X}. The size of a perturbation graph ∆G is defined as: where Z + 0 is the set of non-negative integer. In the perturbation space T(G), the operators and + on perturbation graphs are defined as: where · means the elements of the input matrix is limited Specially, we call ∆G ∈ T 1 (G) an operation element of perturbation space T(G). Given the above definitions and operators, the perturbation space T(G) owns the following properties: Proof : Given the definition of T k (G), the result is a direct consequence of the following calculations. Based on the definitions of + and operation, we have Based on property 3, it is easy to obtain that the perturbation space T k (G) is actually composed of k different operation elements of T(G), which means that and the size of T k (G) is where | · | is the size of a set, and C is the combination operation of two integers.

Design Goals and Principles in Evaluation Framework
Incorporating with the objective in (5)/(6), we also consider a fundamental expectation of the adversary as a design goal of evasion attack methods: An intelligent attacker always expects to choose the perturbation operation which will bring the most significant attack benefit at each perturbation step for achieving stealthy and effective attacks.
The intelligent attackers expect to ranking these k different ∆G i w.r.t B(∆G i ), and at each perturbation step they choose arg max ∆Gi B(∆G i ). Moreover, the objective in (5)/(6) can also be regarded as ranking all operations in the perturbation space and selecting k operations. Therefore, the core question in this paper is how to rank ∆G ∈ T 1 (G) concerning their relative importance to the attack goal.

A. From Design Goals to Evaluation Framework
To achieve the above expectation, we propose an evaluation framework to reveal its core requirements. Our framework composed of three principles, they are: (1) Benefit decomposition. Explaining B(·) is necessary for understanding the three principles. When budget k > 1, perturbations at each step are combined together to function as a whole. Although final attack results come from collab- can be chosen at each perturbation step. This fact requires that the attack benefit B(·) should be felicitously defined on ∆G ∈ T 1 (G) from a global view, i.e., distributing O( G; k) to each ∆G, to support the intelligent attacker making perturbation decision. For example, when using Shapley value φ [37] as the contribution distribution function, B(∆G) = φ(∆G O( G; k)). In this paper, an attack method satisfies the benefit decomposition principle if it considers all perturbations as a whole to evaluate their attack results, and uses some mechanisms to distribute the overall benefit to the perturbations at each step.
(2) Baseline graph. When defining B(·), an implicit ground object is that the baseline graph of attack benefit should be fixed on the clean graph G, i.e., B(·) = B(· G), and B(∆G) = 0 where ||∆G|| = 0. If the baseline graph changes to other graphs, the measure of attack benefit will deviate from the original meaning (see the example of GradArgmax in Appendix B).
(3) Operation ranking. To achieve stealthy and effective evasion attacks, given specific values of B(·) on ∆G ∈ T 1 (G), an intelligent attacker should choose the perturbation with maximal attack benefit in each step. In the above process, the intelligent attacker ranks ∆G ∈ T 1 (G) according to their attack benefits, and then choose top-k different perturbation operations one-by-one. In this paper, an attack method satisfies the operation ranking principle if its perturbation at each step consumes the attack budget by considering the B(·)-based ranking of ∆G ∈ T 1 (G).

B. From Evaluation Framework to Our Method
In this section, we utilise principles in the evaluation framework and additional requirements to guide the design of our Test on clean sample  Fig. 1. Illustration of the projective ranking method. The victim model f θ can make the correct prediction on a clean sample G (shown in hollow arrows). During the scoring module training (shown in the steps 1-9 with solid arrows), the attacker T f employs the mutual information between the perturbation space T(G) and the attacker's goal y G = y G to measure and rank the importance of all elements in T(G). The scoring module needs access node embedding and predictive probability distribution of the victim model. In the evaluation phase (shown in dashed arrows), the attacker T f only needs to access the node embedding to obtain the ranking of the elements in T(G), and then projects the operation ranking to generate adversarial sample G under the specified budget.
method. Generally, an intelligent attacker always attempts to maximise the profits in attacks (see Appendix A). In this paper, we extend the definition of transferability of attack strategies. The transferability means that once attackers learn the attack strategies, they can generate adversarial samples for unseen clean samples under different perturbation budgets. However, if attack strategies are learned from fixed budget k (e.g., RL-S2V), these strategy cannot easily satisfy transferability since they are designed for specific k. Therefore, the evaluation framework and desired transferability practically require an attack method accomplishes B(·)based ranking of ∆G ∈ T 1 (G) without considering specific k in B(·). Inspired by the recent research on GNN explainability [38], [39], we employ all perturbation operation ∆G ∈ T 1 (G) of the clean graph G (i.e., baseline graph) as a whole to attack target GNNs for getting rid of the limitation of specific k. Based on mutual information, the B(·) of each ∆G is then calculated as their importance (see more in Appendix B) for final attack results. In this way, our method satisfies the benefit decomposition principle. To satisfy the operation ranking principle, we first rank ∆G ∈ T 1 (G) according to their importance values (i.e., attack benefit), and then project this ranking into practical attacks with specific k.

Ranking method
Now, given a clean sample G as the baseline graph, attackers attempt to rank all operation elements in perturbation space T(G) with respect to their importance. We measure the importance of elements in T 1 (G) by mutual information (MI) between the modified graph G and the attacker's goal. It can be expressed as: where H(·) is the entropy function. In untargeted evasion attacks, Y = (· · · , p y G = 0, · · · ) is the expected prediction distribution of G, y G is the original category of G. For the clean sample G, the first item in (15) is a constant since the victim model f θ is fixed and Y is also invariant. So the objective in (15) is equal to To reduce the computational difficulties caused by the discrete graph structure, we apply continuous relaxation on ∆G and assume it is a graph variable ∆G ∼ T f (G). Based on Jensen's inequality and H(·) is a concave function, we obtain that where E[·] is expectation function. So the objective (16) is equal to min To be more specific, given the victim model f θ , the objective of the untargeted evasion attacks is where p · G is the predictive probability distribution of f θ on G. The objective of the targeted evasion attacks is where y t is the specified target category. Following the attack setting in previous methods [22], we assume that attackers are only able to add edges when generating G. So we have where ∆A = m A (I A − A), the mask m A is obtained by where h i is the embedding of node i, s(·, ·) is the scoring function which measures the importance of elements in T 1 (G) with respect to the attacker's expectation. In our method, after concating the embedding of nodes v i and v j , a Multi Layer Perceptron (MLP) model and the softmax function are employed to obtain the final score. Since the value of ∆A is a real number rather than a discrete value, we call G is generated by adding continuous structure perturbations ∆G c = {∆A c , 0}.

Perturbation Projection
In our method, the learned attack strategy is embedded in the ranking of ∆G = {∆A, ∆X} ∈ T 1 (G). Due to the discrete structure limitation of graph data, although attackers could obtain the adversarial sample G in (21) where k is the perturbation budget, topk(·, k) is the set of ∆A c;i,j with top-k values, i and j indicate the element at i-th row and j-th column of matrix. By this projection, attackers obtain the adversarial sample G = {A+∆A d , X} from clean sample G under specified budget k. Figure 1 illustrates the pipeline of our projective ranking method. After obtaining the adversarial samples D = { G m } M m=1 , the attacker use them to attack the victim model f θ . Algorithm 1 shows how attackers generate adversarial samples from clean samples D by our projective ranking method. To learn an attack strategy, in line 6, attackers first need to obtain the embedding representation of all nodes h of clean samples in D from the victim model f θ . In the training phase (lines 9-12), attackers use the scoring function in equation (22) to obtain structure mask m A , then obtain the perturbations on graph structure ∆A c by limiting m A with the allowed perturbation operation type. Then, in line 11, attackers add perturbations ∆A c to the clean samples to generate a relaxed adversarial sample G c . In line 12, attackers use the objective (19) to learn an attack strategy embedded in the scoring function. In the evaluation phase (lines 13-18), attackers will obtain the practical adversarial sample G d to evaluate the attack performance of the learned attack strategy. In line 14, attackers project the learned ranking into the practical attack space, in which attackers are only allowed to add edges with the specified budget (k = 1). Then attackers obtain the final adversarial samples in line 15 and attack the victim model in line 17. Attackers will repeat the process (lines 9-18) until the projective ranking method learned a high attack strategy. By replacing the objective in line 12 with objective (20), attackers could obtain the adversarial samples under the setting of targeted attacks.  18 ASR best = ASR current

METHOD ANALYSIS UNDER OUR EVALUATION FRAMEWORK
In this section, we use the three principles in Section 4.3.1 to make an evaluation on our method and three typical attack methods: RandomSampling, GradArgmax and RL-S2V.
The results are summarized in the Table 2. In these methods, RandomSampling only satisfies the baseline graph principle, our method satisfies the attack benefit, operation ranking and baseline graph simultaneously. The other methods are partially consistent with the evaluation framework. The reasons are as follows.
(1) GradArgmax. Similar to the use of gradient descent for training in neural networks, GradArgmax employs the gradient of f θ on all operation elements ∆G cur ∈ T 1 (G cur ) to choose perturbation operation, where G cur is the graph waiting to be modified at the current perturbation step. Hence, GradArgmax neglects the baseline graph principle. To use up all perturbation budget k, attackers need to calculate the gradient information at each perturbation step. Then it will use the real-time local gradient as the measure of attack benefits. Actually, the gradient information is a measure of modification sensitivity (see Appendix B), so GradArgmax does not satisfy the attack benefit principle. To generate adversarial samples, GradArgmax focuses on integrating all perturbation graph ∆G cur ∈ T 1 (G cur ), which owns the biggest local benefit at each perturbation step. Although the operations in GradArgmax have an order, it does not satisfy the operation ranking principle since the local gradient information is not a suitable measure for attack benefits.
(2) RL-S2V. In the generation of adversarial samples, RL-S2V uses the attack benefit of ∆G ∈ T k (G) to decide the perturbation operation ∆G ∈ T 1 (G) of each step in consuming perturbation budget k. The reward function in RL-S2V is designed by considering the outputs of the victim model f θ on G and G, so it satisfies the baseline graph and attack benefit requirements. However, it emphasizes using ∆G ∈ T k (G) as a whole perturbation to attack the victim model f θ with specified budget k, while cares less about the order of the element ∆G ∈ T 1 (G) that composes the perturbation space T(G). Hence, the RL-S2V attack method neglects the attack ranking. Furthermore, we analyze the difference between the measures of attack benefits (sensitivity, long-term benefit, importance) in the Appendix B. We also show the weakness of GradArgmax concerning the attack benefits from three different aspects and empirically demonstrate them in our experimental results.

Datasets and Baselines
We employ several real-world datasets ENZYMES, Mutagenicity, PC-3, NCI109, NCI-H23H [40] and one synthesized dataset BA-2Motifs [39] for graph classification. For the NCI-H23H dataset, we only choose the graphs whose node size is less than 50. Table 3 shows some basic statistics of these datasets.
To evaluate the performance of our method, we select RandomSampling, GradArgmax, and RL-S2V [22] as baselines. In the RandomSampling method, we performed ten times with different seeds and then averaged these accuracy results. In our experiments, the attack performance is measured by the accuracy of the victim model, in which a low accuracy number indicates a high attack performance.

Experimental Setup
In the victim models, we randomly split each dataset into training data (80%), validation data (10%), and test data (10%) to train the victim GAT [41] or GCN [42] models. The victim models have three hidden layers, with 20 as the output feature dimension. We concatenate the maxpooling and sumpooling results of the final embedding of nodes to obtain the expression of the whole graph, then use a fully connected layer to predict the category of the graph. In our projective ranking method, we use a 2-layers MLP to serve as the scoring module.
To evaluate the transferability of our method, we directly project the learned strategy under k = 1 to the generation of adversarial samples under k = 2, 3. The other results are obtained by running corresponding attack methods under a specified budget, respectively.

Untargeted Attacks
The upper half of Table 4 and 5 show the accuracy of the victim model f θ on both clean and adversarial samples generated by different attack methods. The bold numbers indicate the best attack results under the same setting.
In Table 4 and 5, our method achieves the best or competitive attack performance on all datasets with k=1, indicating the projective ranking method owns powerful attack performance. When k=2 or 3, we use the learned attack strategy under k=1 to generate adversarial samples for the changed perturbation budget. The results show our method also obtain the best or competitive attack effect, which shows that the projective ranking method has learned an effective transferable attack strategy under budget k=1.
GradArgmax generates the adversarial examples based on the gradient of the victim model and makes a greedy choice in each step. The attack results of GradArgmax in the Table 4 and 5 empirically prove our discussion about sensitivity in Appendix B. Firstly, the perturbation generated by GradArgmax is sub-optimal since the gradient is the sensitivity measure of the victim model. Although the GradArgmax achieves effective attack performance on the victim GCN model, its ability on the victim GAT model is limited (see Figure 2). Secondly, the result on the NCI109 dataset with k=1 in Table 5 shows the GradArgmax generates samples with negative attack performance. This indicates that its attack performance is limited by the non-linear nature of the GNN model in some situations. Finally, the attack performance of GradArgmax is worse than the RandomSampling on ENZYMES, PC-3 and NCI109 datasets when k=2 and 3, on which GradArgmax shows weak marginal attack performance concerning the budget. Moreover, the GradArgmax does not learn any attack strategy in the attack process. Above results indicate that GradArgmax is not desirable for attackers in some situations since it misses the baseline graph and attack benefit principles in evasion attacks.
Compare with using the "local" gradient in GradArgmax, RL-S2V and our method achieve stable attack performance on both GAT and GCN models since both of them consider the importance of perturbation operation with "global" criteria. We also use RandomSampling as a baseline to evaluate other attack methods. Table 4 and 5 show our method always achieve better attack performance than Random-Sampling. The italic shows unexpected results in the aspect of attack ability, where the performance of RL-S2V is worse than RandomSampling on ENZYMES (k=2, 3) in Table 4 and ENZYMES (k=3), NCI109 (k=3) in Table 5. Moreover, attackers always expect to obtain better attack performance when giving more budgets. If the budget increases, a well-designed attack method should not decrease    its performance. However, like the result in [24], we also observed that the attack performance of RL-S2V degrade when increasing the perturbation budget on Mutagenicity (k=3) in Table 4. This may be due to the less effectiveness of the Q-learning method in RL-S2V, especially for the Markov decision process with a long horizon.

Targeted Attacks
We also conduct targeted attacks on the ENZYME dataset. Without loss of generality, these methods attempt to attack GNN models so that they classify graphs from other classes (i.e., 1-5) as class 0. The upper half of Table 6 shows the attack success rate of different attack methods, and our method far outperforms other baselines in attack perfor-mance. Moreover, in targeted attacks, we also found the same weaknesses of GradArgmax and RL-S2V that they have in untargeted attacks (see italic results).
Remarks. Although the attention mechanism in GAT models introduces more parameters, previous research [43] in imbalanced learning shows that GAT's performance is lower than GCN's because the minority class does not have enough data to train a competent model. When training the GAT model on the NCI-H23H dataset, we employ undersampling on the category with most samples to alleviate the unfavourable effect caused by unbalanced distribution. In the training data, the # of positive samples: # of negative samples = 1:2.
All results in this section are achieved by directly ap-  plying attack methods on the vanilla GNN models. Recently, the randomized smoothing method [44], [45] has been widely employed to improve the robustness of AI models. In this paper, we follow the setting (noise parameter β = 0.9/0.7, sampling number d = 10000) of recent research on certified robustness of GNNs [46] to evaluate the attack performance of our method. Experimental results show randomized smoothing [46] is an effective defence method. However, for GNN models in this paper, randomized smoothing is not applicable because it significantly degrades the performance (i.e., accuracy) of GNNs. For example, as shown in Table 7, although our method almost cannot attack the GCN models on ENZYMES/Mutagenicity after introducing randomized smoothing, the accuracy of GCN equipped with the defence method (β = 0.9) on clean graphs is only 22.29%/53.00%, which is dramatically lower than that of vanilla GCN models suffering attacks with k = 1 (i.e., 52.50%/67.63%).

Transferability on Unseen Samples
To reduce attackers' effort to generate adversarial samples from unseen clean samples, they generally expect a transferable attack strategy. In this section, we use the attack strategies obtained in Section 6.3 to generate adversarial samples for unseen samples and then employ them to attack the victim models.

Untargeted Attacks
The lower half of Table 4 and 5 show the classification accuracy of f θ on both clean and adversarial samples. We consider the RL-S2V and our projective ranking method since only they can learn transferable attack strategies. The bold results indicate the best method under the same setting, and italic show unexpected results in the aspect of transferable attack performance. Firstly, the results in Table  4 and 5 show both RL-S2V and our method could use the learned attack strategy to generate effective adversarial samples under perturbation budget k=1 on all datasets. It indicates that the learned strategy can be transferred to attack unseen samples. Secondly, the results under k=2, 3 further demonstrate that the projective ranking method owns transferable attack performance on unseen samples when the budget changes. Especially, our method obtains the best attack performance on some datasets when k=2 or 3 even if it does not own the best performance when k=1.
Finally, compared with RandomSampling, the transferability of the attack strategy of RL-S2V is limited on most datasets when k=2 or 3, maybe the RL-S2V did not learn a powerful attack policy when k > 1. These results reveal that the victim models make consistent mistakes at both the sample and the budget levels. The attackers can utilize this fact to learn the attack strategy only under a specific budget with limited resources and then use the attack strategies to attack the target classifiers when the attack scenario changes.

Targeted Attacks
The lower half of Table 6 shows attack success rate of attack methods on unseen samples. Attack results show our method observably outperforms RandomSampling and RL-S2V. Moreover, in targeted attacks, the transferability of attack strategy from RL-S2V is also limited (see italic results) when comparing with RandomSampling. Figure 3 shows the attack performance of our method on seen samples under different attack budgets. The perfor-mance curves illustrate our method learned effective and transferable attack strategies in untargeted and targeted attacks. Moreover, Figure 3 also empirically demonstrates that our method satisfies the operation ranking principle in the evaluation framework since smaller budgets own larger marginal attack performance.

Transferability on Victim Model
To further explore the transferability, we use the adversarial samples generated from GCN/GAT model to attack the victim GAT/GCN model. The attack results are shown in Table 8, and these adversarial samples achieve better attack performance than RandomSampling. It indicates these victim models used for the same task on the same dataset may make consistent mistakes to some extend.

Transferability on Data Domain
This evaluation explores the transferability of the attack strategy learned on one dataset to attack the victim models built on other datasets. We visualized the attack results on the victim GCN model in Figure 4. Firstly, the relative attack performance's colour indicates that when the source attacker and the target model have the same dataset, it achieves the best attack performance. Secondly, since the graphs in all datasets are small molecules or come from bioinformatics, the result values in Figure 4 show the domain similarity of these graphs brings non-negative attack performance. These results reveal the potential risk of employing a pre-training model with a freezing setting [36] in the downstream tasks. In Figure 4, we observe that when attacking the NCI-H23H dataset using the attack strategy from the ENZYMES dataset, the accuracy performance drops 8.9%, which is larger than that of RandSampling (4.7%) and GradArgmax (8.6%). Once the adversary knows the victim model f (θ) uses the pre-training model f emb , they could train a classifier f (φ) on graphs G f that come from the same domain of the data G f in f (θ), then use the attack strategy learned on f (φ) and the embedding of G f from f emb to attack the victim models.

Visualization of Attack Patterns
To reveal the attack strategies of the projective ranking method, we visualize the perturbations in adversarial samples on the BA-2Motifs dataset based on the GCN model. BA-2Motifs is a synthetic dataset in which two motifs (House and Pentagon) are attached on random base graphs. Table 9 shows the attack results of different methods.  5. Visualization of adversarial samples. The graphs in the left column are clean samples, and the subgraphs in first/second block composed of green nodes are the motif "Pentagon"/"House". The graphs in the middle and right column are adversarial samples generated by RL-S2V and our method, respectively. In this figure, the attackers attempt to fool the victim models to predict "House"/"Pentagon" on the adversarial samples in first/second block. Both RL-S2V and our method present two attack patterns: imitation of other motifs and collapse of self-motif.
In untargeted evasion attacks, we found two fundamental strategies in the generation of the adversarial samples. They are: (1) placing the adversarial samples in the highconfidence region of the other categories in the victim models, and (2) moving the clean samples to the classification boundary or other low-confidence areas of the victim models. We dive into the adversarial samples and observe some enlightening attack patterns in them: Imitation of other motifs. In the first row of the first block in Figure 5, both RL-S2V and our method add one edge in the Pentagon so that there is a House in the adversarial samples. In this way, the victim GCN model classifies the adversarial samples as House graphs.
Collapse of self-motif. In the second row of the first block and the second block in Figure 5, both RL-S2V and our method attack the victim model by adding one edge in which one node is in the self-motif. In this way, the attackers destroy the self-motif pattern by moving the samples to the low-confidence areas to fool the victim model.
Although the attack results in Table 9 indicate RL-S2V and our method have the same attack performance, we find the attack patterns of RL-S2V are simple and lack variation from the second column in both Figure 5 and 6. However, another two attack patterns are found in our method:

RL-S2V Ours
Coexistence of motifs. In the first block of Figure 6, our method shows a new attack pattern. One edge is added between two nodes that are outside of the self-motif in the clean samples. The exciting part of this edge is that the distance of the two end-nodes of it is 5, and after this perturbation operation, there is a motif Pentagon in these samples. The coexistence of motifs is regarded as one behaviour that belongs to the second strategy in generating adversarial samples, in which the clean samples are moved to the decision boundary of the victim models.
Fake self-motif. In the second block of Figure 6, our method adds one edge between two nodes outside of the selfmotif, resulting in one triangle constructed in the adversarial samples. As a critical part of the House motif, the constructed triangle could confuse the victim models since two "similar" self-motifs exist in current samples. In this way, the samples are moved from the high-confidence region of the victim model to the low-confidence area.
In this section, we visualize the adversarial samples and summarize two basic attack strategies in them. We also found four attack patterns-imitation of other motifs, the collapse of self-motif, coexistence of motifs, and fake selfmotif-of the adversarial samples. Compared with the RL-S2V, the adversarial samples generated by the projective ranking method show various attack patterns. These attack patterns are helpful for the adversary to find the graph pattern differences between different data classes. Based on these observations, the attackers can customize the pattern operation to obtain adversarial samples of the specified type of clean graph samples.

CONCLUSION
In this paper, we present the projective ranking approach to perform an evasion attack for graph classification. We contend that current evasion approaches either do not provide adequate attack performance without considering the perturbations' long-term benefits or require attackers to readjust the attack strategies when the attack environment changes. To that purpose, we define the perturbation space and propose an evaluation framework on the evasion attacks for graph classification. Then we first relax perturbation space for ranking its elements based on mutual information, and then we project the ranking into generating adversarial samples with a specified budget. The experimental results show that our method performs well in attack performance, and the learned attack strategies can be directly transferred to generate adversarial samples when the budget changes. Furthermore, the visualization of adversarial samples generated by our method shows a variety of attack patterns, which helps identify the vulnerability of the victim models.
Our future works include simultaneously making perturbations in structure and node features and performing evasion attacks on directed graphs and graphs with edge attributes. In addition, two promising directions are exploring how imbalanced datasets influence the performance/robustness of GNNs and the interaction between robustness and explainability [47] by diving into adversarial samples.

APPENDIX A CHALLENGES IN EVASION ATTACK
Unlike attack methods for node classification and link prediction, we find some challenges in designing evasion attack methods for graph classification. They are: (1) Huge search space. The perturbation space is huge when the size of graph data is big. For example, it is hard for attackers to obtain the optimal adversarial samples when making edge perturbations. Different from mainly considering the link situation of the target node in the nodelevel task, the time complexity in the graph-level attack tasks is O(n 2 ), where n is the node number of the graph. When d-dimension binary attributes are associated with edges [48], this complexity changes to worse O(2 d n 2 ). It is usually difficult for the adversary to solve this discrete combinatorial optimization problem.
(2) Profits maximization. The profits here include the direct and indirect profits. The direct profit is the attack benefit since the primary goal of attackers is to obtain adversarial samples with high attack performance. The indirect profits contain learning transferable strategies and defect mining. In the aspect of transferable strategies, attackers expect to learn strategies that help attack unseen samples or generate adversarial samples under a changed perturbation budget. In the aspect of defect mining, the adversary yearns for revealing the defects or weaknesses of the victim models by analyzing the patterns in adversarial samples. The weaknesses of the victim models inspire attackers in designing more powerful attack methods. Once the flaws of the victim models are found, they could customize the attack strategies for different types of data to improve the attack performance.

APPENDIX B DIFFERENT MEASURES OF ATTACK BENEFIT
In this section, we will discuss the measure differences between sensitivity, long-term benefit, and importance concerning the attack benefit principle. Fig. 7. Illustration of GradArgmax and RL-S2V. GradArgmax uses realtime gradient information to make perturbations, RL-S2V utilizes the estimated long-term benefits to finish the attack.

B.1 Sensitivity
The sensitivity here refers to the gradient in the GradArgmax method. It is intuitional to employ the gradient to make perturbation decision, since the gradient in GradArgmax method exactly describe the structure or feature sensitivity of graph G with respect to the victim model f θ . Taking the edge perturbation on graph G as example, a coefficient a u,v is introduced for each nodes pair (u, v) ∈ V × V, and a u,v = I(v ∈ N (u)). The message function in Section 3.2 changes to To generate an adversarial sample, attackers first need to calculate the gradient on all a u,v where L is the loss function of victim models. Then GradArgmax will choose the position with the largest positive g u,v to add an edge or the smallest negative g u,v to remove an edge. GradArgmax will repeat the above process until it uses up all perturbation budget k. However, the gradient which measures the sensitivity is not suitable enough to measure the importance of each perturbation operation for some reasons [49], [50], [51]: (1) The perturbation generated by GradArgmax is suboptimal. The principle in GradArgmax is choosing the position with gradient extremum to make modifications. If there is an edge at the position with the largest positive gradient value or there is no edge at the position with the smallest negative gradient value, GradArgmax will have to re-select the perturbation position.
which is only a first-order linear approximation function about ∆G. However, to obtain powerful discrimination ability, GNN models usually contain nonlinear activation functions like ReLU. The linear approximation based on local gradient can't describe the change in the output of the victim models well when the input value changes greatly.
(3) The iterative selection of perturbation operations based on local gradients cannot accurately describe the attacker's expectations. The GradArgmax attempts to use the local gradient to approximately measure the importance of each perturbation operation in the generation of adversarial samples. When the perturbation budget k > 1, the local gradient is not a suitable approximate meassure. The reason is the local gradient g u,v at the κ th (1 < κ ≤ k) perturbation step is calculated based on current graph which is obtained by adding a perturbation graph ∆G ∈ T κ−1 (G). Actually, in the κ th perturbation step, the attackers attempt to choose the perturbation operation which brings κ th largest attack benefit for the original clean sample G, but not the operation that brings 1 st largest benefit for current graph G + ∆G (∆G ∈ T κ−1 (G)). So the gradient information is enough to predict the sensitivity but not a suitable meassure to identify the importance of each operation.

B.2 Long-term Benefit
The long-term benefit here is the estimated reward of each operation in the adversarial samples generated by reinforcement learning. A conspicuous drawback of GradArgmax is that the greedy selection mechanism focuses on the shortterm benefit (i.e., maximizing loss function) of the current operation, while neglect the benefit of current operation should be defined by its importance in final adversarial samples. In the training of RL-S2V with perturbation budget k, the estimated reward of each perturbation operation is 0 when the perturbation budget k is not used up. Once the budget is exhausted, the adversarial samples obtain positive or negative reward defined by the output of the victim model f θ on these samples. In the experience pool of RL-S2V, the long-term benefit of each perturbation operation is determined by the final benefit of adversarial samples. In this way, RL-S2V can learn a more powerful attack strategy than GradArgmax.

B.3 Importance
The reward function in RL-S2V mainly focuses on the overall benefits caused by all perturbation operations in the adversarial samples. The long-term benefit of each perturbation operation in RL-S2V can only be evaluated by the reward function after the generation of adversarial examples exhausts all perturbation budget k. The long-term benefit reflects the absolute importance of each perturbation operation according to the reward function under a specific budget k. This kind of absolute importance of the same perturbation operation is different under various perturbation budgets in attack methods based on reinforcement learning [22], [24], so RL-S2V needs retraining to obtain attack strategy when the perturbation budget changes. From the perspective of operation ranking principle, compared with the specific absolute importance of each perturbation operation, attackers are more concerned about which perturbation operation should be selected from the perturbation space (i.e., relative importance).


SyncMesh: Improving Data Locality for Function-as-a-Service in Meshed Edge Networks

The increasing use of Internet of Things devices coincides with more communication and data movement in networks, which can exceed existing network capabilities. These devices often process sensor or user information, where data privacy and latency are a major concern. Therefore, traditional approaches like cloud computing do not fit well, yet new architectures such as edge computing address this gap. In addition, the Function-as-a-Service (FaaS) paradigm gains in prevalence as a workload execution platform, however the decoupling of storage results in further challenges for highly distributed edge environments. To address this, we propose SyncMesh, a system to manage, query, and transform data in a scalable and stateless manner by leveraging the capabilities of Function-as-a-Service and at the same time enabling data locality. Furthermore, we provide a prototypical implementation and evaluate it against established centralized and decentralized systems in regard to traffic usage and request times. The preliminary results indicate that SyncMesh is able to exonerate the network layer and accelerate the transmission of data to clients, while simultaneously improving local data processing.

INTRODUCTION
With the increase in computational power and popularity of smart mobile devices, the Internet of Things (IoT) has been gaining momentum in the past years. In turn, aspects like scalability [12] and locality of data [25] are becoming more challenging [7]. Therefore, cloud infrastructures are getting increasingly distributed to support localized edge and fog architectures that manage requests in close proximity to the users and data [23]. These architectures reduce response latencies and at the same time unburden the network layer [17,20]. In order to cope with the increasing scale and the dynamic nature of IoT environments, ongoing research [4,14] proposes to integrate ad-hoc mesh networks and decentralized capabilities to further enhance the scalability and resilience of edge and IoT architectures. In addition, the Serverless and FaaS paradigm has been identified as a suitable computing model for the IoT [18], since it simplifies the deployment at the edge, enables on-demand allocation of resources, and allows for the execution of tasks in lightweight containers [19].
In the FaaS paradigm, computation and storage are typically decoupled: The functions themselves are stateless and the used data or results are stored in distributed storage systems. Although distributed file systems (DFS) or object stores like S3 simplify the usage of FaaS in cloud computing environments, the dynamic nature of upcoming architectures in the edge-cloud continuum poses new challenges: Devices are often connected via an unreliable and possibly slow network connection, only provided with limited hardware resources, and can join and leave the network at any time in an ad-hoc manner [11].
Summarizing, Serverless and FaaS enable a scalable workload execution, but rely on external storage to store and retrieve state, typically outsourced to centralized cloud systems [10]. The possible impact of the external storage for FaaS and Serverless has been identified as a major issue in cloud architectures [13], yet is even further exacerbated in dynamic IoT and edge environments.
In an effort to address this challenge, this paper presents SyncMesh, a new system that improves data locality in mesh-based edge and fog computing environments for FaaS workloads. Instead of moving all generated data of edge devices, i.e. sensor readings, to a central cloud storage, the information is stored on the respective nodes, analyzed, aggregated and transformed locally, and provided to other nodes in the network on-demand. Our prototype implementation of SyncMesh offers a FaaS interface for local data processing and is able to exchange data between participating nodes in a sensor network, significantly reducing network transmissions in the highly distributed and dynamic edge/fog environments.
In summary, the main contributions of this paper are: • We outline assumptions, challenges and requirements of data storage and locality in highly distributed fog and edge environments.
arXiv:2203.14801v1 [cs.DC] 28 Mar 2022 • We derive the SyncMesh architecture and implement a prototype 1 to tackle the identified challenges and enable data locality as well as in-situ data processing. • We present a preliminary evaluation of our prototype by implementing a relevant use case using real world data and comparing our results to different baseline scenarios. The remainder of this paper is structured as followed: We first provide an overview of the related work before stating our assumptions and discussing the requirements. Subsequently, we present the SyncMesh prototype, conducted experiments as well as results before concluding the paper.

RELATED WORK
In general, the importance of storage and data management for the upcoming distributed environments is growing, not only due to the ever increasing generated data [16]. Subsequently, several approaches to improve the storage layer in fog and edge computing environments exists: Many systems focus on efficient cloud offloading [3,26], in which advanced algorithms are used to time the offloading of data to the cloud efficiently [22]. In contrast to this, with SyncMesh our goal is to store and analyze the data where it is created.
In [9], the authors evaluate the performance of different object store system in edge and fog environments, while also identifying storage as a major challenge. In subsequent works, Confais et. al. [8] propose a combination of a network attached storage and peer-topeer technology to improve the performance of object stores in the aforementioned environments. Although presenting promising results, their approach still relies on a distributed storage layer available to the respective edge nodes, whereas SyncMesh aims to improve the data locality.
More similar to our approach, other works avoid the use of central instances entirely and rely on P2P communication between the devices [24]. Mayer et al. [15] address data management problems within decentralized fog networks and introduce their own solution called FogStore, which is a context-aware distributed data storage system. In addition to state management, the paper outlines specific replica placement strategies and a generalized API for querying and manipulating data. In contrast, in our approach we neglect replicas and rather only exchange data between nodes if needed.
Furthermore, the Nebulastream platform [27] was designed with the specific purpose of usage as a data management system for the IoT and addresses issues arising from centralized approaches. They rely on stream processing instead of FaaS.
In regard to FaaS, the Fog function project [5] explores FaaS as a serverless programming model within the context of IoT and uses event-listeners to discover and orchestrate devices and resources in IoT environments. In addition, Fog function was integrated into FogFlow, which is a framework for fog computing with the goal of providing a programming model that enables programmers to develop IoT systems more easily [6].
Although the FaaS paradigm is often highlighted as fitting workload and data analytics platform for fog and edge computing [18], most are focused on i.e. enabling a lightweight orchestration [19] or scheduling based on resource availabilities [21] and often not

Assumptions
In order to define the scope and envisioned use case of SyncMesh, we make the following assumptions about the expected environment: We assume a highly distributed environment in the edge-cloud continuum, consisting of lightweight and heterogeneous devices. The devices are interconnected via peer-to-peer connections in an ad-hoc mesh network and act as autonomous nodes. Therefore, the environment is not administered or managed by a central entity, and devices organize themselves in, i.e. swarms, in order to enable scenarios in the context of remote sensing and environmental awareness [11]. In the related work, such architectures are often proposed to increase the scalability and reliability of fog and edge computing environments and to cope with the dynamic nature of the IoT.
Furthermore, we assume that the devices are equipped with sensors such as temperature and air quality sensors or audio and video sources, resulting in data directly created on the respective nodes. The devices are not constrained to data center boundaries and can be located anywhere in i.e. a smart city or a wildlife refuge [1], and due to the possibly unreliable and slow network it is not feasible to constantly synchronize data between nodes or upload all sensor data to the cloud.
Finally, for our initial prototype we presume that inside the network of edge devices, a discovery process for neighboring nodes in the mesh exists. Therefore, for the remainder of this paper we expect that devices can join the network and automatically discover other nodes in the proximity, but neglect an actual implementation and refer to the related work. For instance, previous work [2] has utilized metrics provided by the underlying mesh network to identify direct neighbors in the ad-hoc swarm.

Requirements
From our assumptions, we derive the following requirements for our system: Support operation during unreliable network conditions. The described edge sites are often distributed across several remote locations and are only connected with limited bandwidth and high latencies. In addition, network partitions and outages are more common than in traditional data centers. Therefore, the system needs to be able to cope with and automatically adjust to poor network connectivity without intrusive impact on the local processing of data.
Enable local data processing and storage. In order to not overload the network layer and subsequently interfere with other and possibly critical network traffic, the data needs to be stored, processed, transformed, or aggregated where it is created. Thus, data locality needs to be enabled and the local processing simplified.
Autonomous operation and resilience. Due to the dynamic nature of the aforementioned IoT environments, lightweight edge nodes are expected to join and leave the network at any time. Therefore, the system needs to cope automatically with node joins, churns, and failures by, i.e., enabling the entities to work as autonomous as possible.
Environmental awareness. Although the devices are expected to work in an autonomous manner, to increase the remote sensing capabilities and subsequently the environmental awareness, nodes need to be able to exchange their raw or aggregated data on-demand with other nodes in the proximity.

System Architecture
With the given assumptions on the environment and subsequently to fit the requirements stated before, we implemented a prototype based on lightweight containerization technologies, which improves the data locality and simplifies the deployment or workload by utilizing FaaS capabilities.
Therefore, each device in the environment -in the following called a SyncMesh node -acts as an autonomous node in the mesh network, stores sensor data, and offers an interface that enables users and other nodes in the proximity to collaborate with it. A SyncMesh node contains several key components, which will be discussed in more detail in the remainder of this section.
Local database. Each node employs a local database which is used to store data generated by connected sensors and the availability model of other available devices in the proximity. The database can further be accessed by the coordinator function and other available functions on the device and offers the possibility to use event listeners to, i.e., automatically react to changes in the database. In our prototype, we use a MongoDB instance, although other solutions can be used where appropriate.
Database event listener. A separately instantiated database listener registers new sensor data input and forwards the change events to the coordinator function. Therefore, it provides notification functionalities, sharing database changes to subscribed external nodes or calling (transformer) functions for additional processing.
Coordinator function. The SyncMesh interface is exposed via the coordinator function and is used as an entry point for users and other nodes in the sensor network to access data on the respective node. In general, it is a serverless function implemented in the OpenFaaS framework and provided via an HTTP API. Every request uses the same unified request schema containing the data query as a GraphQL statement, as well as additional parameters like for instance transformer functions.
The coordinator function can store and modify data on the node itself by interacting with the local database. In addition, it forwards events registered by the database listener to subscribed nodes, enabling decentralized data replication as well as event-driven mechanisms. Although the coordinator function already implements aggregation functionalities, it forwards more advanced data preprocessing tasks to other local transformer functions that enable diverse workloads, from simple analysis to Machine Learning (ML) workloads. Finally, before sending the data to the client, the response is compressed with gzip.
Transformer functions. In order to reduce the data transmission between nodes and to facilitate operation in limited bandwidth scenarios, transformer functions can be used to pre-process data directly on the respective nodes. Sensor data can, i.e., be aggregated and analyzed with ML models, e.g., image classifiers or other data analysis pipelines, before being transferred over the network.
The envisioned workload is implemented in a function or a chain of functions, provided in docker containers and started by the coordinator function in case of changes in the database or when triggered externally, e.g. by nodes in the proximity. The respective containers are scaled on-demand as well as stopped in case they are not needed anymore, therefore relieving resources of lightweight edge nodes.
Requirement analysis. In summary, in order to support the operation during unreliable network conditions, SyncMesh nodes only exchange data on-demand and favor local data pre-processing as much as possible, subsequently relieving the network layer. The sensor data is initially only stored on the respective devices, and by leveraging FaaS capabilities, the local processing is simplified via the deployment of arbitrary (transformer) functions. Due to the stateless nature of the serverless functions, they can be scaled up and down if needed, thus automatically adapting to increasing and decreasing demand. Therefore, a single SyncMesh node acts autonomously in regard to processing the locally available (sensor) data.
Further, the data can also be exchanged and replicated across other available nodes in the environment on-demand. For that reason, each SyncMesh node maintains a model of other available devices in the proximity [2] and transparently forwards user requests regarding sensor readings in the surrounding area to respective neighboring nodes, possibly aggregating the results and returning a unified response. The requests are only forwarded to currently available nodes. Consequently, SyncMesh is automatically adjusting to node churns and joins.
Finally, since all components and used functions in Syncmesh are provided as containers, they can be adapted to heterogeneous CPU architectures by i.e. providing multi-arch Docker images 2 .

EVALUATION
In order to evaluate our SyncMesh prototype, we conducted a set of experiments, comparing it to several baselines and describe our results in this section.

Experiment setup
To simulate an environment as described in our assumptions, we created a virtual testbed on the Google Cloud Platform. The hardware and software specifications for each used virtual machine instance are listed in Table 1. As depicted in Figure 2, we deployed virtual machines in different cloud regions to introduce latencies between participating nodes in a distributed environment. Subsequently this resulted in latencies ranging between 20 and 300ms. In addition, in some cases we used a separate virtual machine as an external server for the implemented baselines. In order to simulate sensors connected to the edge devices, we leveraged a real-world IoT dataset, containing air quality, temperature and humidity measurements collected in a city in Bulgaria 3 . The dataset was distributed across the nodes and added to the respective databases, simulating real world measurements.
For the evaluation, we considered two different scenarios: • Collect: A client requests all data from all nodes of a sensor network for a given time span. Therefore, the sensor data is retrieved from all participating nodes and provided to the user. • Transform: A client requests i.e. aggregated data from the surroundings of an edge node. Therefore, the sensor data is, if applicable, preprocessed and then provided to the user. As illustrated in Figure 2, we monitored the used traffic for requests from the client (blue), internal network traffic between the nodes (green), and in case of baselines from and to the external cloud server (red). In addition, we used the Round Trip Time (RTT) until a clients request was successfully processed as a further evaluation metric.
Finally, we performed the experiments for different amounts of nodes in the network (3, 6, 9 and 12) and several data time spans (1, 7, 14 and 30 days). Each configuration was repeated 20 times to improve accuracy and soften outliers.

Baselines
We implemented three other systems to compare them against SyncMesh. These baselines were chosen because they are being used in practice to handle vast amounts of data in IoT networks. central cloud storage A standard implementation of a sensor network. Each sensor sends the data to a central cloud database (MongoDB) from where clients can retrieve it. sharded cloud storage A sharded implementation of the central cloud storage. Each sensor stores its own data, and a central server is supplying unified access to the client. Each sensor thereby represents a shard in the database. p2p distributed database storage A peer-to-peer database with eventual consistency based on GunDB 4 . Clients need to individually connect to peers in the network in order to retrieve all sensor data or synchronize data between nodes. In contrast to the other baselines, p2p sends all data uncompressed. The MongoDB based systems use snappy and SyncMesh implements a gzip compression.

Results
In this section we first discuss the measurements of our comparison benchmark. Figure 3 describes the evaluation results of a three node sensor network. Therefore, Figure 3a depicts the time a client needs to retrieve all sensor data from all nodes, when using different baselines and SyncMesh. As can be seen, the p2p baseline needs significant more time than all other baselines, which is why we excluded it in other plots to improve the detectability. Furthermore, SyncMesh performs 10.1% better than sharded and 20.7% worse than the central baseline.
In Figure 3b we show the produced traffic for each systems during the collect scenario, except for the p2p baseline (91.03 MB). The results further show that SyncMesh is able to outperform the sharded and central baselines by up to 57.8% in regard to network efficiency.   This is in part due to the different compression algorithms used in MongoDB and SyncMesh. In the case of p2p the amount of data sent is even doubled, due to protocol specifics of the employed solution. In addition, SyncMesh therefore also produces less internal traffic between participating nodes than all of the other solutions. This is especially evident in Figure 3c, which depicts the used traffic during the transform scenario. SyncMesh is again able to outperform the baselines by only using 6.99 kB. As can be seen, the majority of used traffic results from transmitting the sensor data to the central server. In contrast to Figure 3c, the sharded system performs 75.0% better than the central system, as the sharded MongoDB also uses local workers (for aggregation) on each shard, decreasing the amount of traffic between the server and its shards.
The plots in Figure 4 describe the same experiment as Figure 3, but for a three, six, nine and twelve node network respectively. As expected and depicted in Figure 3a, the sharded and central baseline show a continuous increase in request times for growing network sizes due to the increased data amount that must be send to the cloud from all nodes and retrieved by the client. However, the performance of SyncMesh does not degrade significantly: The time is only increased by 25.7%, in comparison to 175.6% for shared and 266.1% in case of central, most likely due to the decreased traffic between nodes.
This trend is also observable in Figure 4b and Figure 4c, that describe the used traffic for the collect and transform scenarios across different network sizes. As can be seen, SyncMesh scales significantly better in regard to transmitted traffic, and therefore is able to exonerate the network link between participating nodes in the network.

CONCLUSION
In this paper we have introduced SyncMesh, a system that improves the data locality and enables local data processing based on the FaaS paradigm in a meshed network of edge nodes. We prototypical implemented SyncMesh and evaluated our approach in a virtualized testbed on a real world IoT dataset, and compared it against several baselines in regard to request time and network utilization.
As indicated by the preliminary results, SyncMesh is able to outperform the traditional approaches in regard to network usage and request times, in particular for larger amounts of nodes.
Consequently, our results underline the importance and impact of data locality, especially for the the application of FaaS in highly distributed environments.
In future work we plan to further extend the SyncMesh prototype, include more complex analysis workloads and evaluate our approach on real-world edge devices. In addition, we intend to assess the impact of cold starts in the FaaS framework.