Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper introduces a novel connection between adversarial attack on graph neural networks in a restricted black-box setup via node feature perturbation, on the one hand, and the influence maximization problem under the linear threshold model on the same graph, on the other hand. An analysis shows that the objective function of the corresponding IM problem is submodular under assumption, hence the problem admits greedy approximation algorithms as effective black-box attack strategies. Experiments show such attacks are effective compared to baselines in degrading the performance of GNNs in terms of mis-classification rate.

A question that remains unaddressed is whether the analogy to the IM problem under the LT model extends to other properties of the problem: under the uniform distribution of threshold θ, the diffusion of influence under the LT is equivalent to a diffusion whereby each node picks at most incoming edge to be active with probability corresponding to the incident edge's weight. This paper would be stronger if it addressed the question of whether this property also extends to the analogy, apart from the submodularity property.

Under the current analysis, two greedy algorithms are proposed for two different objectives, yet there is no analysis of their complexity and no runtime results on their efficiency. The algorithms are called efficient, but no evidence is provided to that effect. That is a weak point of the paper.
review_title: Interesting connection revealed, efficiency claim unsubstantiated

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary of the paper:
--------------

The authors propose an adversarial attack strategy for graph neural networks based on influence maximization. The attack is (claimed to be) black-box (does not have direct access to the model), evasion-based, and limited to perturbations of the node attributes (i.e. cannot insert / delete edges). The authors make simplifying assumptions about the GCN model (all ReLU paths are equally likely) and the distribution of the individual nodes' thresholds, theta_j. The attack is evaluated experimentally on three well-known datasets and three different models. The proposed attack outperforms the centrality-based baselines and the baselines of [Ma et al. 2020].

Strengths:
---------

* The paper is well-written and generally easy to follow. 
* The connection to influence maximization is interesting. 
* The problem of GNN robustness under (realistic) adversarial attacks is important.

Weaknesses:
-----------

* The description of the method and experimental set-up leave a number of open questions (see detailed feedback).
* Despite claiming black-box attacks, the method actually uses the target model's gradients, even for the test set, for the attack.
* The experimental evaluation is rather slim. For example, there is no analysis of the node selection algorithm, e.g. what kind of nodes are selected, no analysis of the sharp differences in performance on the different models, and no analysis of the hyperparameters a and sigma.

Detailed comments:
------------------

I have several concerns about both the method as it is described in the paper as well as the experimental evaluation.


Major points:

Method:
* The authors emphasize the black-box nature of their attack, however the perturbation vector requires access to the respective model's gradient, which violates the black-box setting. This is especially critical since Eq. (10) involves the gradient of the loss of ALL nodes, including the validation and test nodes. So effectively, the attack utilizes the gradient of the loss of the test nodes. Also, it is not stated which value of lambda is used for the perturbation, i.e. what magnitude the perturbation has. The authors mention that this is done because the input features lack semantic meaning; however, they do not mention how potential semantic meaning of the features could be used instead of using the gradients.
* The neighbor weight of alpha_{ij} = 1/|N_i| is not the weight proposed by [Kipf and Welling 2017]. Instead, they propose alpha_{ij} = (d_i+1)^{-0.5} * (d_j+1)^{-0.5}, where d_i is the degree of node i.
* Why is the attack target the misclassification rate on the whole dataset (Eqs. (3,5,6,7)) and not only on the test set? Does this mean that the results in Table 1 are also reported on the whole dataset? If not, why is there a mismatch between the reported misclassification rate and the optimization objective?
* Eq. (4) is unclear/not well defined. As stated above the equation, hat{k}_j is the predicted class of node j after perturbing the set S. However, if S fails to change the predicted class of node j, the numerator and the denominator both become 0, i.e. ill-defined. 
* Sec. 4.4: the authors mention that the first approximation leads to the problem becoming "likely to be submodular". Why is it only likely to be submodular and not guaranteed? 
* Also Sec. 4.4: According to the authors, the first approximation "integrates out the randomness in data [...]". Where is there any randomness in the data?
* Section 4 shows how the attack can be instantiated for GCN. How is the attack adapted to the other models, i.e. GAT and JKNet?
* The paper just briefly mentions that Eqs. (6) and (7) are used to select the target nodes via a greedy influence maximization approach. A few more sentences on how this will be exactly done would be readers not familiar with inf. max.
* The authors should give more details (proof and/or reference to existing work) regarding the derivation of Corollary 1 and 2.


Experimental evaluation:
* Unrealistic set-up: 60% train data. For semi-supervised node classification, typically we have 10% or less training samples.
* The authors use L=4 layers for the GNNs. However, [Kipf and Welling 2017] report substantially worse performance for L=4 compared to, e.g., L=2. What are the results of the attack when the L used for attacking is different than the L of the GNN?
* The node attributes in the datasets have special constraints, e.g. for Citeseer and Cora the features are binary, and for Pubmed the features are nonnegative. How is this accounted for by the perturbation model?
* How do the choice of sigma and a influence the results?
* Is there any insight into why JKNet and GAT seem to be much more fragile to the attacks? Even for the otherwise very weak random attack GAT's and JKNet's performances drop sharply. Why does this happen?
* There is no analysis into what kind of nodes the proposed algorithm selects; since node selection is the main contribution of this paper, some insight into this would greatly benefit the experimental evaluation.


Minor points:
* p. 1 original from => original form
* p. 6 first paragraph: non-decreasing => non-increasing
* The paper does not cite the correct sources for the dataset.
review_title: Official Blind Review

final_score: rating: 5: Marginally below acceptance threshold
review_content: ##########################################################################
Summary:
This paper studies the problem of designing adversarial attacks (on GNN models) that perturb the feature to maximize the misclassified instances. Assuming that the activations are activated independently at random, the paper shows that the attack design can be reduced to the influence maximization problem under the threshold model. The paper identifies several conditions on the threshold that can make the influence maximization problem submodular, thereby making it easy to optimize.  Experiments have been shown that the proposed attack method has higher performance compared to the existing ones.

##########################################################################
I find the paper interesting but lean towards rejection at this point. The main reason is that the assumptions are not realistic, and the contributions are incremental.
##########################################################################

Strength:

The technical proofs seem to be sound, and the relationship between the attack design and influence maximization is an interesting observation. 

Weakness:

The entire analysis is based on Assumption 1, but the paper does not provide a formal description of the data flow in the network under such an assumption, which makes it hard to follow the subsequent analysis. In addition, this assumption is very restrictive in the sense that it makes all the activation functions (\sigma) output random numbers, ignoring what has been received from the last layer. For theoretical analysis on general neural networks, such an assumption is somehow minimal (though not realistic, as pointed out in Kawaguchi 2016) to obtain theoretical results, but it is overly strong for designing a practical attack. In particular, assuming Assumption 1 means that we have ignored the structure of GCN, and therefore, it is not appropriate to target this paper for GCN model. In general, I would not think a meaningful attack could be designed without having certain types of prior knowledge. 

Another concern is that the technical analysis largely follows Ma 2020 - the proofs and ideas are very similar. From the introduction, the main difference is to adopt Assumption 1 and get theoretical results, which is somehow incremental.

The amount of perturbation is not extensively discussed in the experiments; to me, the strength of perturbation is critical to the attack performance. 

Minor issues:

It would better to introduce the goal of the attack along with the attack setup.
Please define \E_path[H(S)] before using it.
Please introduce RWCS and GC_RWCS before using these terms.




review_title: The paper studies an interesting problem but the settings are not very realistic.

final_score: rating: 5: Marginally below acceptance threshold
review_content: Paper summary: The paper studies the problem of attacking GNNs in a restricted black-box setup, i.e., by perturbing the features of a small set of nodes, with no access to model parameters and model predictions. The authors draw a connection between the restricted attack problem and the influence maximization problem, and then propose several approximation techniques to solve the reformulated attack problem. Experimental results on attacking three GNN models demonstrate the effectiveness of the proposed attack. 


Strengths
+The paper is well-written and well organized
+Solving the restricted black-box based on influence maximization is novel and interesting

Weaknesses
-Threat model is limited
-Assumptions are not satisfied
-Some details are unclear 
-Missing important references



Detailed comments:

-Threat model is limited.

My first concern is that the proposed attack only focuses on node feature perturbation, while not mentioning structure perturbation. For attacks to graph neural networks, structure perturbation attack is more meaningful and effective. (see Zugner et al., 2018, Dai et al., 2018). 

My second concern is that why restricting that the attacker does not know model predictions? What’s the motivation and in what scenarios? From my understanding, even in the black-box attack, an attacker can obtain the model  predictions, e.g., via querying the model using the input nodes. 

-Assumptions are not satisfied

The authors assume that theta is from certain simple distributions, in order to make the objective function submodular. However, from the experimental results, such simple distributions are inappropriate. 

-Some details are missing

In Equation (4), there is a connection between theta and epsilon.  But in your experimental setup, this connection is lost. Is epsilon necessary in your experiments, as theta is assumed to satisfy some distribution that is irrelevant to epsilon? 

How do you obtain the gradient (\partial L / \partial X) in Equation (10) in the black-box setting? What’s the lambda value? 

As you use the sign of the gradient and a fixed lambda, all the positive gradients should generate the same value and thus the feature perturbations. In this case, how do you select the feature indexes j as there are many ties in epsilon_j?  
 
In all experimental results, the improvement of the proposed attack over RWCS/GC-RWCS is marginal (less than 3 percent). I think one reason could be that the selected simple distribution for theta largely deviates from the true distribution. Can you plot the true theta distribution, assuming that W is known in advance?   

What’s the efficiency of the proposed attack? Is it better than RWCS/GC-RWCS? 

-Missing important references
The authors miss the following important works on attacks to graph neural networks:

Wang and Gong, “Attacking Graph-based Classification via Manipulating the Graph Structure”, CCS’19
Wu et al., “Adversarial Examples for Graph Data: Deep Insights into Attack and Defense”, IJCAI’19
Entezari et al., “All You Need Is Low (Rank): Defending Against Adversarial Attacks on Graphs ”, WSDM’20 
  

review_title: The paper is interesting and the proposed attack method is novel. However, some important details are missing and the threat model is limited.

Meta-review: This paper relates the problem of influence maximization and adversarial attacks on GCNs. 
The paper, and its formulation and assumptions stirred up quite a discussion among the reviewers and the authors. I do appreciate the thorough rebuttal that the authors provided, and the reviewers did take it into account (and revised their scores). 
However, all in all, I am afraid that there are just a few too many concerns with this paper. 
If the authors take the reviews to heart, they should be able to improve the manuscript and submit a stronger and improved version to the next conference. 
Decision: Reject