<jupyter_start><jupyter_text>Configuration<jupyter_code>data_dir = "../data"
adj_path = os.path.join(data_dir, "adj_matrix_formal_stage.pkl")
feat_path = os.path.join(data_dir, "feature_formal_stage.npy")
label_path = os.path.join(data_dir, "train_labels_formal_stage.npy")
model_dir = "../saved_models"
adj_norm = True
feat_norm = None
feat_norm_func = utils.feat_norm(feat_norm)<jupyter_output><empty_output><jupyter_text>Data Loading<jupyter_code>dataset = data_loader.KddDataset(adj_path, feat_path, label_path)
raw_adj = dataset.adj
raw_features = dataset.features
raw_labels = dataset.labels
train_mask = dataset.train_mask
val_mask = dataset.val_mask
test_mask = dataset.test_mask
size_raw, num_features = raw_features.shape 
test_size = np.sum(test_mask)
size_reduced = size_raw - test_size
num_class = raw_labels.max() + 1<jupyter_output>Finished data loading.
NumNodes: 659574
NumEdges: 5757154
NumFeats: 100
NumClasses: 20
NumTrainingSamples: 559574
NumValidationSamples: 50000<jupyter_text>Attack Solution Our attack solution is based on **Adversarial Adjacent Matrix Generation** and **Enhanced Feature Gradiant Attack**. We first generate an attack matrix, then modify attack node features by optimizing a customized attack loss. Note that in previous reseach on graph adversarial attacks, many proposed attacks that modify features and connections at the same time. However, most of these research did experiments on toy datasets, not as big as this one (~100-1000x bigger). When the search space becomes very large, it would be difficult to find the optimal solution (even if it exists, computationally expensive). Hence, we choose to modify connections and features consecutively.  Adversarial Adjacent Matrix Generation  Step 1: Target Node SelectionSince there are strong constraints on attackers ($\leq500$ nodes, $\leq100$ edges for each node), it's ineffective to directly connect attack nodes to all test nodes (50000 in total). One connection for one node is obviously not enough considering such a big graph. We should focus on those test nodes that are probably classified correctly by target models, while leaving the nodes that are already difficult to classify. Since labels of test nodes are hidden, we use several models to classify test nodes and find their common predictions. The idea is that if a node is classified to the same class by a variaty of models, it is probably due to its special topology or feature properties. It would be interesting if we can affect these properties. Thus, we select this kind of nodes as targets to attack.<jupyter_code># GCN
model_1_name = "gcn_64_1.pkl"
model_1 = models.GCN(num_features, 64, num_class, 1, activation=F.relu, dropout=0)
model_1_states = th.load(os.path.join(model_dir, model_1_name), map_location=dev)
model_1.load_state_dict(model_1_states)
model_1 = model_1.to(dev)
model_1.eval()
# TAGCN
model_2_name = "tagcn_128_1.pkl"
model_2 = models.TAGCN(num_features, 128, num_class, 1, activation=F.leaky_relu, dropout=0)
model_2_states = th.load(os.path.join(model_dir, model_2_name), map_location=dev)
model_2.load_state_dict(model_2_states)
model_2 = model_2.to(dev)
model_2.eval()
# Adj normalization
if adj_norm:
    adj = utils.adj_preprocess(raw_adj)
else:
    adj = raw_adj
    
graph = dgl.DGLGraph()
graph.from_scipy_sparse_matrix(adj)
features = th.FloatTensor(raw_features).to(dev)
labels = th.LongTensor(raw_labels).to(dev)
graph.ndata['features'] = features
pred_1 = model_1.forward(graph, features)
print("Acc on train: {:.4f}".format(utils.compute_acc(pred_1[:size_reduced], labels, train_mask)))
print("Acc on val: {:.4f}".format(utils.compute_acc(pred_1[:size_reduced], labels, val_mask)))
pred_2 = model_2.forward(graph, features)
print("Acc on train: {:.4f}".format(utils.compute_acc(pred_2[:size_reduced], labels, train_mask)))
print("Acc on val: {:.4f}".format(utils.compute_acc(pred_2[:size_reduced], labels, val_mask)))
pred_1_np = pred_1.cpu().detach().numpy()
pred_2_np = pred_2.cpu().detach().numpy()
print("% of common predictions: {:.4f}".format(np.sum(np.argmax(
    pred_1_np[-test_size:], 1) == np.argmax(pred_2_np[-test_size:], 1)) / test_size))
target_node = np.where(
    np.argmax(pred_1_np[-test_size:], 1) == np.argmax(pred_2_np[-test_size:], 1))[0]<jupyter_output><empty_output><jupyter_text>Step 2: Adversarial ConnectionsAfter having selected target nodes, it's time to consider how to use limited number of connections to obtain the maximum influences. Here, we show three stratagies to present the key insight of our idea progressively, as shown in the figure. The first strategy, a basic one, all attack nodes are directly connected to target nodes. In this case, one attack node can influence in maximum 100  neighbour nodes. The second strategy, a better one, there are inter-connections between attack nodes. One attack node can now affect other attack nodes, thus more targets. The third strategy, push this further, some attack nodes are only connected to other attack nodes in a multi-layer fashion. Using this strategy, we can make the best use of limited connections to influence tagert nodes. As for how to choose the connection between specific attack node and target node, our answer is: choose it randomly. Indeed, we did a lot of work to find if there are some useful information related to the topological properties (e.g. degree, centrality, betweenness, etc.). However, we find the randomness is better than hand-crafted design. Besides, the attack performance is surprisingly stable. One possible reason is the isomorphy of graph. Initially all attack nodes are zeros, so there are no difference between them. After the connections are determined, their features are modified by the following attack algorithm. Hence, this process may result in some isomorphic graphs (or partially isomorphic) even considering the initialization is random.<jupyter_code>def get_noise_list(adj, K, target_noise, noise_tmp_list):
    i = 1
    res = []
    while len(res) < K and i < len(noise_tmp_list):
        if adj[target_noise, noise_tmp_list[i]] == 0:
            res.append(noise_tmp_list[i])
        i += 1

    return res


def update_noise_active(noise_active, noise_edge, threshold=100):
    for node in noise_active:
        if noise_edge[node] >= threshold:
            noise_active.pop(noise_active.index(node))
    return noise_active


def connect(test_node_list, max_connection, mode):
    adj = np.zeros((500, 50500))
    N = len(test_node_list)

    if mode == 'random-inter':
        # test_node_list: a list of test nodes to be connected
        noise_edge = np.zeros(500)
        noise_active = [i for i in range(500)]

        # create edges between noise node and test node
        for i in range(N):
            if not(noise_active):
                break
            noise_list = np.random.choice(noise_active, 1)
            noise_edge[noise_list] += 1
            noise_active = update_noise_active(noise_active, noise_edge)
            adj[noise_list, test_node_list[i]] = 1

        # create edges between noise nodes
        for i in range(len(noise_active)):
            if not noise_active:
                break
            noise_tmp_list = sorted(noise_active, key=lambda x: noise_edge[x])
            target_noise = noise_tmp_list[0]
            K = 100 - noise_edge[target_noise]
            noise_list = get_noise_list(adj, K, target_noise, noise_tmp_list)

            noise_edge[noise_list] += 1
            noise_edge[target_noise] += len(noise_list)

            noise_active = update_noise_active(noise_active, noise_edge)
            if noise_list:
                adj[target_noise, 50000 + np.array(noise_list)] = 1
                adj[noise_list, 50000 + target_noise] = 1

    elif mode == 'multi-layer':
        # test_node_list: a list of test nodes to be connected
        noise_edge = np.zeros(500)
        noise_active = [i for i in range(455)]

        # create edges between noise node and test node
        for i in range(N):
            if not(noise_active):
                break
            noise_list = np.random.choice(noise_active, 1)
            noise_edge[noise_list] += 1
            noise_active = update_noise_active(
                noise_active, noise_edge, threshold=90)
            adj[noise_list, test_node_list[i]] = 1

        # create edges between noise nodes
        for i in range(len(noise_active)):
            if not noise_active:
                break
            noise_tmp_list = sorted(noise_active, key=lambda x: noise_edge[x])
            target_noise = noise_tmp_list[0]
            K = 90 - noise_edge[target_noise]
            noise_list = get_noise_list(adj, K, target_noise, noise_tmp_list)

            noise_edge[noise_list] += 1
            noise_edge[target_noise] += len(noise_list)

            noise_active = update_noise_active(
                noise_active, noise_edge, threshold=90)

            if noise_list:
                adj[target_noise, 50000 + np.array(noise_list)] = 1
                adj[noise_list, 50000 + target_noise] = 1

        noise_active_layer2 = [i for i in range(45)]
        noise_edge_layer2 = np.zeros(45)
        for i in range(455):
            if not(noise_active_layer2):
                break
            noise_list = np.random.choice(noise_active_layer2, 10)
            noise_edge_layer2[noise_list] += 1
            noise_active_layer2 = update_noise_active(
                noise_active_layer2, noise_edge_layer2, threshold=100)
            adj[noise_list + 455, i + 50000] = 1
            adj[i, noise_list + 50455] = 1

    else:
        print("Mode ERROR: 'mode' should be one of ['random-inter', 'multi-layer']")

    return adj
adj_attack = connect(target_node, max_connection=90, mode='multi-layer')
adj_attack = sp.csr_matrix(adj_attack)
adj_attack
# conatnate to required size
adj_adv = sp.hstack([sp.csr_matrix(np.zeros([500, size_raw - 50000])), adj_attack])
adj_adv = sp.csr_matrix(adj_adv)
adj_adv
# sanity check
print("No more than 100 edges for any attack node?",
      adj_adv.getnnz(axis=1).max() <= 100)
print("Symmetric attack matrix?", bool(
    ~(adj_adv[:, size_raw:].T != adj_adv[:, size_raw:]).sum()))<jupyter_output>No more than 100 edges for any attack node? True
Symmetric attack matrix? True<jupyter_text>Enhanced Feature Gradient Attack  Step 1: InitializationAdversarial adjcent matrix generation + zeros features + attack target selection Since the targeted attack performs better than the untargeted attack (easier to optimize), we also consider conducting the targetd attack, where the attack target class for a node is the least probable class.<jupyter_code># adjacent matrix 
raw_adj_adv = sp.vstack([raw_adj, adj_adv[:, :size_raw]])
raw_adj_adv = sp.hstack([raw_adj_adv, adj_adv.T])
if adj_norm:
    raw_adj_adv = utils.adj_preprocess(raw_adj_adv)
    
# zeros features
feat_adv = np.zeros((500, 100))
# target model configuration
model_type = 'gcn'
model_name = "gcn_64_1.pkl"
num_hidden = 64
num_layers = 1
if model_type == 'gcn':
    model = models.GCN(num_features, num_hidden, num_class, num_layers,
                       activation=F.leaky_relu, dropout=0)
elif model_type == 'tagcn':
    model = models.TAGCN(num_features, num_hidden, num_class, num_layers,
                         activation=F.leaky_relu, dropout=0)
    
model_states = th.load(os.path.join(model_dir, model_name), map_location=dev)
model.load_state_dict(model_states)
model = model.to(dev)
model.eval()
# prediction on raw graph (without attack nodes)
raw_graph = dgl.DGLGraph()
raw_graph.from_scipy_sparse_matrix(adj)
features = th.FloatTensor(raw_features).to(dev)
labels = th.LongTensor(raw_labels).to(dev)
raw_graph.ndata['features'] = features
pred_raw = model.forward(raw_graph, features)
# select the least probable class as the target class
pred_raw_label = th.argmax(pred_raw[:size_raw][test_mask], 1)
pred_test_prob = th.softmax(pred_raw[:size_raw][test_mask], 1)
attack_label = th.argsort(pred_test_prob, 1)[:, 2]<jupyter_output><empty_output><jupyter_text>Step 2: Enhanced Gradient attackWe design the following loss function for the targeted attack:$$L=f(x)_{c_0}-\max f(x)_{c_{new}\neq c_0} + k\sum_{c\in C}f(x)_{c_0}log(f(x)_c)$$where $f$ is the softmax output of the model, $c_0$ is original predicted class, $k$ is a constant determines the proportion of two parts of the combination of two losses (i.e. **Callini-Wagner** loss and **Cross Entropy** loss). At each iteration, we calculate the gradient of the attack loss w.r.t. features of attack nodes. Then we use the **Adadelta** to modify the features as learning parameters and to optimize the attack loss. **Attention:** Other optimization methods are also possible, while the magnitude of learning rate may vary a lot.<jupyter_code># graph construction
graph_adv = dgl.DGLGraph()
graph_adv.from_scipy_sparse_matrix(raw_adj_adv)
features = th.FloatTensor(raw_features).to(dev)
features_adv = th.FloatTensor(feat_adv).to(dev)
features_adv.requires_grad_(True)
# attack configuration
lr = 1
k = 1000
epoch = 100
feat_lim = 2.0
optimizer = th.optim.Adadelta(
    [features_adv], lr=lr, rho=0.9, eps=1e-06, weight_decay=0)

# other possible optimizers
# optimizer = th.optim.Adam([features_ae], lr=lr)
# optimizer = th.optim.Adagrad([features_adv], lr=lr, lr_decay=0,
#                              weight_decay=0, initial_accumulator_value=0, eps=1e-10)
# optimizer = th.optim.SGD([features_adv], lr=lr)
for i in range(epoch):
    features_concat = th.cat((features, features_adv), 0)
    features_concat = feat_norm_func(features_concat)
    graph_adv.ndata['features'] = features_concat
    pred_adv = model(graph_adv, features_concat)
    pred_loss_ce = - \
        F.nll_loss(pred_adv[:size_raw][test_mask], pred_raw_label).cpu()
    pred_adv_prob = th.softmax(pred_adv[:size_raw][test_mask], 1).cpu()
    pred_loss_cw = (pred_adv_prob[[np.arange(50000), pred_raw_label]] - pred_adv_prob[
        [np.arange(50000), attack_label]]).sum()
    pred_loss = pred_loss_cw + k * pred_loss_ce

    optimizer.zero_grad()
    pred_loss.backward(retain_graph=True)
    optimizer.step()

    with th.no_grad():
        features_adv.clamp_(-feat_lim, feat_lim)

    if i % 10 == 0:
        print("Epoch {}, Loss: {:.4f}, Test acc: {:.4f}".format(i, pred_loss,
            utils.compute_acc(pred_adv[:size_raw][test_mask], pred_raw_label)))
print("Feature range [{:.2f}, {:.2f}]".format(
    features_adv.min(), features_adv.max()))
print("Acc on train: {:.4f}".format(utils.compute_acc(
    pred_adv[:size_reduced][train_mask], labels[train_mask])))
print("Acc on val: {:.4f}".format(utils.compute_acc(
    pred_adv[:size_reduced][val_mask], labels[val_mask])))
print("Acc on test(compared with raw predictions): {:.4f}".format(utils.compute_acc(
    pred_adv[:size_raw][test_mask], pred_raw_label)))
# save adversarial adjacent matrix and adversarial features
with open(os.path.join(data_dir, "adj_adv.pkl"), "wb") as f:
    pickle.dump(adj_adv, f)
np.save(os.path.join(data_dir, "features_adv.npy"), features_adv.detach().cpu().numpy())<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1007746805270476, 'fraction_numerical': 0.020260875322783554, 'mean_word_length': 4.140912185159973, 'pattern_counts': {'":': 0, '<': 26, '<?xml version=': 0, '>': 24, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '600408', 'license': 'Apache-2.0', 'n_tokens_mistral': 5043, 'n_tokens_neox': 4706, 'n_words': 1372, 'path': 'main/attack.ipynb', 'repo_name': 'Stanislas0/KDD_CUP_2020_MLTrack2_SPEIT', 'size': '15103'}