""" Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective https://arxiv.org/pdf/1906.04214.pdf Tensorflow Implementation: https://github.com/KaidiXu/GCN_ADV_Train """ import numpy as np import scipy.sparse as sp import torch from torch.nn import functional as F from torch.nn.parameter import Parameter from tqdm import tqdm import warnings from deeprobust.graph import utils from deeprobust.graph.global_attack import BaseAttack class IGAttack(BaseAttack): """[Under Development] Untargeted Attack Version of IGAttack: IG-FGSM. Adversarial Examples on Graph Data: Deep Insights into Attack and Defense, https://arxiv.org/pdf/1903.01610.pdf. Parameters ---------- model : model to attack nnodes : int number of nodes in the input graph feature_shape : tuple shape of the input node features attack_structure : bool whether to attack graph structure attack_features : bool whether to attack node features device: str 'cpu' or 'cuda' """ def __init__(self, model=None, nnodes=None, feature_shape=None, attack_structure=True, attack_features=False, device='cpu'): super(IGAttack, self).__init__(model, nnodes, attack_structure, attack_features, device) assert attack_features or attack_structure, 'attack_features or attack_structure cannot be both False' self.modified_adj = None self.modified_features = None if attack_structure: assert nnodes is not None, 'Please give nnodes=' self.adj_changes = Parameter(torch.FloatTensor(int(nnodes*(nnodes-1)/2))) self.adj_changes.data.fill_(0) if attack_features: assert feature_shape is not None, 'Please give feature_shape=' self.feature_changes = Parameter(torch.FloatTensor(feature_shape)) self.feature_changes.data.fill_(0) def attack(self, ori_features, ori_adj, labels, idx_train, n_perturbations, **kwargs): """Generate perturbations on the input graph. Parameters ---------- ori_features : Original (unperturbed) node feature matrix ori_adj : Original (unperturbed) adjacency matrix labels : node labels idx_train : node training indices n_perturbations : int Number of perturbations on the input graph. Perturbations could be edge removals/additions or feature removals/additions. """ victim_model = self.surrogate self.sparse_features = sp.issparse(ori_features) ori_adj, ori_features, labels = utils.to_tensor(ori_adj, ori_features, labels, device=self.device) victim_model.eval() warnings.warn('This process is extremely slow!') adj_norm = utils.normalize_adj_tensor(ori_adj) s_e = self.calc_importance_edge(ori_features, adj_norm, labels, idx_train, steps=20) s_f = self.calc_importance_feature(ori_features, adj_norm, labels, idx_train, steps=20) import ipdb ipdb.set_trace() for t in tqdm(range(n_perturbations)): modified_adj self.adj_changes.data.copy_(torch.tensor(best_s)) self.modified_adj = self.get_modified_adj(ori_adj).detach() def calc_importance_edge(self, features, adj, labels, idx_train, steps): adj_norm = utils.normalize_adj_tensor(adj) adj_norm.requires_grad = True integrated_grad_list = [] for i in tqdm(range(adj.shape[0])): for j in (range(adj.shape[1])): if adj_norm[i][j]: scaled_inputs = [(float(k)/ steps) * (adj_norm - 0) for k in range(0, steps + 1)] else: scaled_inputs = [-(float(k)/ steps) * (1 - adj_norm) for k in range(0, steps + 1)] _sum = 0 # num_processes = steps # # NOTE: this is required for the ``fork`` method to work # self.surrogate.share_memory() # processes = [] # for rank in range(num_processes): # p = mp.Process(target=self.get_gradient, args=(features, scaled_inputs[rank], adj_norm, labels, idx_train)) # p.start() # processes.append(p) # for p in processes: # p.join() for new_adj in scaled_inputs: output = self.surrogate(features, new_adj) loss = F.nll_loss(output[idx_train], labels[idx_train]) # adj_grad = torch.autograd.grad(loss, adj[i][j], allow_unused=True)[0] adj_grad = torch.autograd.grad(loss, adj_norm)[0] adj_grad = adj_grad[i][j] _sum += adj_grad if adj_norm[i][j]: avg_grad = (adj_norm[i][j] - 0) * _sum.mean() else: avg_grad = (1 - adj_norm[i][j]) * _sum.mean() integrated_grad_list.append(avg_grad) return integrated_grad_list def get_gradient(self, features, new_adj, adj_norm, labels, idx_train): output = self.surrogate(features, new_adj) loss = F.nll_loss(output[idx_train], labels[idx_train]) # adj_grad = torch.autograd.grad(loss, adj[i][j], allow_unused=True)[0] adj_grad = torch.autograd.grad(loss, adj_norm)[0] adj_grad = adj_grad[i][j] self._sum += adj_grad def calc_importance_feature(self, features, adj_norm, labels, idx_train, steps): features.requires_grad = True integrated_grad_list = [] for i in range(features.shape[0]): for j in range(features.shape[1]): if features[i][j]: scaled_inputs = [(float(k)/ steps) * (features - 0) for k in range(0, steps + 1)] else: scaled_inputs = [-(float(k)/ steps) * (1 - features) for k in range(0, steps + 1)] _sum = 0 for new_features in scaled_inputs: output = self.surrogate(new_features, adj_norm) loss = F.nll_loss(output[idx_train], labels[idx_train]) # adj_grad = torch.autograd.grad(loss, adj[i][j], allow_unused=True)[0] feature_grad = torch.autograd.grad(loss, features, allow_unused=True)[0] feature_grad = feature_grad[i][j] _sum += feature_grad if adj_norm[i][j]: avg_grad = (features[i][j] - 0) * _sum.mean() else: avg_grad = (1 - features[i][j]) * _sum.mean() integrated_grad_list.append(avg_grad) return integrated_grad_list def calc_gradient_adj(self, inputs, features): for adj in inputs: adj_norm = utils.normalize_adj_tensor(modified_adj) output = self.surrogate(features, adj_norm) loss = F.nll_loss(output[idx_train], labels[idx_train]) adj_grad = torch.autograd.grad(loss, inputs)[0] return adj_grad.mean() def calc_gradient_feature(self, adj_norm, inputs): for features in inputs: output = self.surrogate(features, adj_norm) loss = F.nll_loss(output[idx_train], labels[idx_train]) adj_grad = torch.autograd.grad(loss, inputs)[0] return adj_grad.mean() def get_modified_adj(self, ori_adj): adj_changes_square = self.adj_changes - torch.diag(torch.diag(self.adj_changes, 0)) ind = np.diag_indices(self.adj_changes.shape[0]) adj_changes_symm = torch.clamp(adj_changes_square + torch.transpose(adj_changes_square, 1, 0), -1, 1) modified_adj = adj_changes_symm + ori_adj return modified_adj def get_modified_features(self, ori_features): return ori_features + self.feature_changes