Community detection is one of the most widely studied topics in the graph domain, which aims to discover groups of nodes in a graph, such that the intra-group connections are denser than the inter-group ones [33]. It has been widely applied to many real-world applications ranging from functional module identifications in a protein-protein interaction network [1], scientific discipline discoveries in a coauthor network [36], to fraud organization detections in a user-user transaction network [2]. However, with the rapid development of the community detection algorithms, people realize that their privacy is over-mined [6]. In this context, some work begins to investigate the techniques that allow to hide individuals, communities [9, 34] or degrade the overall performance of community detection algorithms [6], mostly based on heuristics or genetic algorithms.
Recently deep graph learning models [15, 26] have achieved remarkable performance in many graph learning tasks. Meanwhile, some studies [8, 37] notice that deep graph models can be easily attacked on tasks such as node/graph classification. Motivated by these findings, in this work, we aim to address the following question: how vulnerable are graph learning based community detection methods? Can we hide individuals by imperceptible graph perturbations? A good solution to this problem can benefit many real-world applications, e.g., personal privacy protection, fraud escape understanding.
Unlike adversarial attacks on node/graph classification where gradients [37] or limited binary responses [8] of the target classifier are available, one challenge we face is that there is no feedback from the target model. For example, in social networking companies like Facebook or Twitter, community detection algorithms are serving as a backend for other purposes such as advertising, which prevents the direct interactions between the target model and individuals. To tackle this challenge, we design a surrogate community detection model which is based on the widely used graph neural networks (GNNs) [15] and a popular community detection measure normalized cut [30]. We attack this surrogate community detection model and verify that the attack can also be transferred to other popular graph learning based community detection models.
In the literature of adversarial attack on graph data, one commonly observed difficulty is that it is very hard to quantify the adversarial costs of various attacks [31]. While imperceptible perturbations can be checked by human in the image domain, it is impossible to adopt the same strategy in the graph domain. Currently, most existing methods tackle this indirectly with either a discrete budget to limit the number of allowed changes [8, 31] or a predefined distribution such as power-law distribution [37]. However, the former based on discrete changes is helpful but far from sufficient, whereas the latter emphasizing a power-law distribution is proven to be rare in reality [3]. In this work, we propose a clearly comprehensible graph objective to measure the degree of
Figure 1: An example of adversarial attack on community detection by hiding individuals. At first, the two targets are clustered into one community (Fig. 1(a)). With a small perturbation of deleting an edge (Fig. 1(b)), the two targets are assigned into different communities by the same detection method (Fig. 1(c)).
perturbations from two perspectives: local proximity and global proximity.
Another challenge we face is the huge computation space of selecting proper candidate edges/nodes to modify. It is non-trivial to develop a solution that can scale with the size of graphs. Existing solutions such as [34] rely on heuristics to bypass this problem, which, however, fail to derive optimal choices, especially for attributed graphs. In this work, we design a novel graph generation model which learns to select the proper candidates. With this approach, we can not only generate proper adversarial graphs to attack community detection models, but also explicitly take the imperceptible perturbation requirement into the learning process.
Our contributions are summarized as follows.
• We study adversarial attack on graph learning based community detection models via hiding a set of nodes, which, to the best of our knowledge, has not been studied before. Our proposed solution CD-ATTACK achieves superior attack performance to all competitors.
• We propose a new graph learning based community detection model which relies on the widely used GNNs and the popular measure normalized cut. It serves as the surrogate model to attack; furthermore, it can also be used for solving general unsupervised non-overlapping community detection problems.
• We define a comprehensible graph-related objective to measure the adversarial costs for various attacks from two perspectives: local proximity and global proximity.
• We design a novel graph generation neural network that can not only produce adversarial graphs to community detection algorithms, but also satisfy the discrete constraint.
• We evaluate CD-ATTACK on four real-world data sets. Our method outperforms competing methods by a large margin in two measures. In addition, we validate that the adversarial graphs generated by our method can be transferred to two other popular graph learning based community detection models.
The remainder of this paper is organized as follows. Section 2 gives the problem definition and Section 3 describes the design of CD-ATTACK. We report the experimental results in Section 4 and discuss related work in Section 5. Finally, Section 6 concludes the paper.
We denote a set of nodes as which represent real-world entities, e.g., authors in a coauthor network, users in a user-user transaction network. We use an
adjacency matrix A to describe the connections between nodes in
represents whether there is an undirected edge between nodes
and
or not, e.g., a coauthored paper that links two authors, a transaction that connects two users. In this study, we focus on an undirected graph; yet our methodology is also applicable to directed graphs. We use
to denote the attribute values of nodes in
-dimensional vector.
The community detection problem aims to partition a graph G = (V,A,X) into K disjoint subgraphs , where
. In our study, we adopt this formulation which produces non-overlapping communities.
In the context of community detection, we are interested in a set of individuals who actively want to escape detection as a community or part of a community, e.g., users who are involved in some underground transactions and thus eager to hide their identity, or malicious users who intend to fool a risk management system. Given a community detection algorithm f , the community detection adversarial attack problem is defined as learning an attacker function
to perform small perturbations on G = (V,A,X), leading to ˆ
, such that
where measures the quality of community detection results with respect to the target
is used to ensure imperceptible perturbations. In this work, we focus on edge perturbations such as edge insertion and deletion, i.e., ˆ
. Intuitively, we want to maximize the decrease of the community detection performance related to a subset
by injecting small perturbations.
Figure 1 depicts an example of community detection adversarial attack in a user-user transaction network. At the beginning, the two target individuals are clustered into a community in yellow, which corresponds to a money laundering group. One target, as a member of the community, would be suspected of money laundering given the other is exposed somehow. With a small perturbation by deleting an edge, the target individuals are assigned into two communities, where the community in purple is a high-credit user group. Thus the two targets decrease the probability of being detected as a whole.
3.1 Framework
In our problem setting, we have two main modules: (1) an adversarial attacker that aims to perform unnoticeable perturbations to the original graph such that a set of individuals could be hidden, and (2) a community detection algorithm
that can partition a graph into several subgraphs in an unsupervised way. These two modules are highly interrelated, i.e., the adversarial attacker
needs the feedback from
to check if the goal of hiding is achieved or not, and the community detection algorithm
relies on adversarial examples to enhance its robustness. In the literature, most studies achieve this interaction by exploiting the gradient or other moments of a differentiable loss function [37], which, however, is intractable in discrete data such as graph. To bypass this difficulty, motivated by [17], we utilize policy gradient in the Actor-Critic framework as the signal between the interaction of the two modules. Another point is that, as we focus on black-box attack meaning there is no specific community detection algorithm in hand, we need to instantiate ourselves with a surrogate model with the capacity of generalization and robustness.
In our solution, we design an iterative framework which consists of two neural networks, one working as the adversarial graph generator and the other working as the surrogate community detection method
. Figure 2 depicts the framework. The upper part generates the adversarial graph, which is optimized with respect to the optimum of the surrogate detection model in the lower part. However, when instantiating the two neural networks, we face three challenges as follows. Surrogate community detection model. How to design a surrogate community detection algorithm, such that the derived adversarial graph also applies to other community detection algorithms? Imperceptible perturbations. What criterion shall we use to ensure the modification is so small that it cannot be perceived by the detection module? Constrained graph generation. How to generate adversarial graphs which meet the imperceptible requirement efficiently?
These three issues make our problem very complicated. In the following, we present our solutions to the three challenges and then recap our framework at the end of this section.
3.2 Surrogate Community Detection Model
We propose a novel graph learning based community detection model. There are two key issues in a community detection model: (1) a distance function to measure the result quality, which corresponds to a loss function in neural networks, and (2) a method to detect
community detection model
Figure 2: Overview of our framework. The adversarial graph generator (in red) produces a constrained adversarial graph, which is used to train a robust surrogate community detection model (in yellow).
communities, which corresponds to the neural network architecture. We discuss these two issues accordingly below.
3.2.1 The loss function. We generalize normalized cut [30], a widely used community detection measure, to serve as the loss function of neural networks. Normalized cut measures the volume of edges being removed due to graph partitioning:
where . The numerator counts the number of edges be- tween a community
and the rest of the graph, while the denominator counts the number of incident edges to nodes in
. Let
be a community assignment matrix where
1 represents node i belongs to community k, and 0 otherwise. As we focus on detecting non-overlapping communities, an explicit constraint is that
is a diagonal matrix. With C, normalized cut can be re-written as:
where D is the degree matrix with is the k-th column vector of C. Subtracting Eq. 3 by 1, we get the following simplified target function:
where is element-wise division, Tr
is defined as the sum of elements on the main diagonal of a given square matrix. Please refer to Appendix A for detailed derivation for Eqs. 2-4.
Note that needs to be a diagonal matrix, we hereby introduce a new penalization term which explicitly incorporates the constraint on C into the target function. We subtract
a penalization, where
is an identity matrix. Thus we define the differentiable unsupervised loss function
as follows:
Figure 3: Schematic diagram of the surrogate community detection model. It first uses GNNs to derive node embeddings. Based on the node embeddings, it then assigns similar nodes to the same community.
whererepresents the Frobenius norm of a matrix,
is ap- plied as normalized cut encourages balanced clustering and voids shrinking bias [30, 32]. To analyze why the proposed penalization is valid, we suppose there are two communities i, j to be clustered with two assignment vectors
respectively. Suppose each row of C is a distribution and for a non-diagonal element
, it has a maximum value when nodes are assigned uniformly and a minimum value when nodes are assigned discriminatively. By minimizing this penalization term, we actually encourage nodes to be assigned discriminatively into different communities.
3.2.2 The network architecture. This part details the neural network architecture to derive the community assignment matrix C, which is trained by minimizing the unsupervised loss in Eq. 5. In the literature, spectral clustering [30] is usually used to compute the community assignment matrixC. Due to its limitations in scalability and generalization, some recent work [29] has used a deep learning approach to overcome these shortcomings. Our architecture, which is based on the recent popular graph neural networks (GNNs) [15, 16] on graph data, has two main parts: (1) node embedding, and (2) community assignment. In the first part, we leverage GNNs to get topology aware node representations, so that similar nodes have similar representations. In the second part, based on the node representations, we assign similar nodes to the same community. Figure 3 depicts the overall architecture of our community detection model. In the following, we introduce each part in details.
In this work, we use graph convolutional networks (GCNs) [15] for the purpose of node embedding. In the preprocessing step, the adjacency matrix A is normalized:
where is the identity matrix and ˜
. Then we transform node features over the graph structure via two-hop smoothing:
where is the activation function such as
and
are two weight matrices. Intuitively, this function can be considered as a Laplacian smoothing operator [20] for node features over graph structures, which makes nodes more proximal if they are connected within two hops in the graph. With the node representations
in hand, we are now ready to assign similar nodes to the same community by:
where are two weight matrices. The function of
is to linearly transform the node representations from a v-dimensional space to a r-dimensional space, then nonlinearity is introduced by tying with the function
is used to assign a score to each of the K communities. Then softmax is applied to derive a standardized distribution for each node over the K communities, which means the summation of the K scores for each node is 1.
To summarize, we design a neural network to serve as the surrogate community detection model, which is trained in an unsupervised way based on the loss function . Another function of this module is that it can be used to measure the degree of graph dissimilarities, which is the focus of the next section.
3.3 Imperceptible Perturbations
An adversarial graph should achieve the goal of potential community detection attack, while, at the same time, it should be as similar to the original graph as possible to be stealthy. In the literature, some work measures the similarity between graphs by the number of discrete changes, for example, [8, 31] limit the number of allowed changes on edges by a budget
Some other work [37] argues that the graph dissimilarity should be minimized by maintaining some predefined distribution such as the power-law distribution. The former based on discrete changes is helpful but far from sufficient, whereas the latter emphasizing a power-law distribution is proven to be rare in reality [3]. In this part, we define a clearly comprehensible graph-related objective to measure the degree of perturbations.
Figure 4: The proposed learning framework. There are two modules: constrained graph generation and surrogate community detection. With the optimum of the latter, it will generate two losses to guide the learning of the former.
Given , we know the correspondence between nodes of the two graphs. The degree of perturbations is measured by the following perturbation loss:
where is the Kullback-Leibler divergence, and KL(P||Q) =
learns node representations by capturing some proximities in an unsupervised fashion. We hereby introduce two proximities used to encode node representations:
• Local proximity: Given node correspondence, the corresponding nodes in two graphs would be similar if their neighbors are similar.
• Global proximity: Given node correspondence, the corresponding nodes in two graphs would be similar if their relations with all other nodes are similar. The local proximity, or neighborhood/adjacency proximity, is exploited by many node representation methods [15, 26] within a graph. As we know the node correspondence, it is also valid to be used as a graph similarity measurement [18]. By this means, the representations derived in Eq. 7 are effective to measure the degree of graph perturbations with respect to the local proximity.
For global proximity, we adopt the widely used Personalized PageRank [25] defined below.
Definition 3.1. Given a starting node distribution s, a damping factor , and the normalized adjacency matrix ¯A, the Personalized PageRank vector
is defined as:
With the stationary distribution , we actually get the influence score of the starting node to all the other nodes. By taking each node as a starting node, we can get A in which
denotes the influence score of node i to node j. We can utilize the influence scores by replacing the normalized adjacency matrix ¯A in GCN, which leads to the PPNP [16] formulation:
There is no overhead for this global proximity based graph perturbation measurement as we can use Eq. 12 instead of Eq. 7 in the surrogate community detection module. By using global proximity, the graph partition model would be equipped with broader views compared with local proximity used in GCN, which also benefits the community detection module.
3.4 Constrained Graph Generation
In this subsection, we describe our method which produces a modified graph ˆA that meets the budget constraint in Eq. 9 and the perturbation constraint in Eq. 10. Inspired by the recent success of latent variable generative models such as variational autoencoding [13] in graph generation [12, 14], we use a latent variable model parameterized by neural networks to generate the graph ˆA. To be more specific, we focus on learning a parameterized distribution over the adjacency matrix A and feature matrix X as follows:
where is the encoding part and
is the encoding parameter set,
is the generation part and
is the generation parameter set. While the encoding part is straightforward and can make use of the corresponding encoders in existing work [12, 14], the generation part is challenging due to the following issues:
• Budget constraint: Generating a valid graph structure with a budget constraint is hard, as it is a mixed combinatorial and continuous optimization problem.
• Scalability: Existing graph generation methods suffer from the large-scale problem [35].
To satisfy the budget constraint, we propose to directly incorporate prior knowledge about the graph structure using the mask [19] mechanism, which can prevent generating certain undesirable edges during the decoding process. To address the scalability issue, we use different solutions based on the input graph size: (1) for a large-scale graph, we design an efficient decoder with O(m) time complexity by focusing on deleting edges, where m is the number of edges, and (2) for a small-scale graph, we are allowed to both delete and insert edges.
3.4.1 Encoding using GCN. We follow VGAE [14] by using the mean field approximation to define the variational family:
where is the predefined prior distribution, namely, isotropic Gaussian with diagonal covariance. The parameters for the variational marginals
are specified by a two-layer GCN:
where and
are the vector of means and standard deviations for the variational marginals
is the parameter set for encoding.
3.4.2 Constrained generation. For a large-scale graph A, to strictly meet the budget requirement in Eq. 9, we approximate by the following operation:
where represents element-wise multiplication,
is a concatenation of
are defined as below:
where is the computed score for keeping the edge by two-layer perceptrons and softmax function. We sample without replacement
edges according to their keeping scores
defined in Eq. 18, and we use set S to denote these edges that have been chosen. Intuitively, we want to select
edges that exist in the original graph and maximize their product of keeping scores. With this strategy, we can also generate graphs that strictly meet the budget requirement in Eq. 9.
For a small-scale graph, we split the budget into two parts:
for deleting edges and
2 for inserting edges. We approximate
where are derived in the same way as Eqs. 17-18 except that we just mask out or delete
2 edges. ¯S denotes the set of edges that have been chosen to be inserted.
is computed in the same way as
with non-identical parameters and the essential differences are: (1) we compute with the condition of
(2) we add
2 edges to ¯S.
3.4.3 The loss function. Different from the traditional VAE, our method is not optimized by the unsupervised reconstruction error, rather it is powered by the following combined loss:
where is the prior loss with p(Z) =
is the imperceptible per- turbation requirement introduced in Eq. 10,
is used to diverge the community assignment distributions within the set of individuals:
where can be regarded as the margin loss or the smallest distance for any pair inside
0 as we aim to maximize the margin so that the members of
are spread out across the communities in
To summarize, Eq. 20 receives error signals from the surrogate community detection model, which serves as a reward to guide the optimization of our graph generator.
3.5 The Proposed Model
From the perspective of Actor-Critic framework, the adversarial attacker could be considered as the Actor and the community detection algorithm
could be regarded as the Critic. As the error signals of adversarial graph generator are obtained from the community detection model and the community detection model needs the generated graphs as inputs for robust training, we design an iterative framework, named Community Detection ATTACKer (CD-ATTACK), to alternate between minimizing the loss of both
. We refer to Figure 4 and Algorithm 1 for details of the training procedure.
At the beginning of Algorithm 1, we exploit the constrained graph generator so as to get an adversarial graph ˆG (line 4). We then utilize the idea of robust training and feed both G and ˆG into the surrogate community detection model
to compute
(line 6). Based on the optimum of
to power the learning process of
(line 7-8).
In practice, we have observed the devil in the training process. We therefore provide a list of practical considerations:
• Pre-training community detection model: An appealing property of CD-ATTACK is that pre-training the community detection model before the iteration results in better performance and faster convergence.
• Normalization trick of G: When feeding both G and ˆG into , there could be trouble as G and ˆG have discrete differences. We thus observe better results if decoupling self-loop and neighborhood smoothing in GCN, i.e., ¯
and another weight matrix for self-loop.
Table 1: Statistics of graphs considered
Finance-large. We first evaluate the surrogate model, then check if the attack can be transferred to other community detection models.
4.1 Data
From DBLP bibliography data, we build two coauthor graphs with 5,304 and 20,814 authors respectively. The former is named DBLP-medium and the latter is named DBLP-large. For each author, we use a one-hot representation with 305 dimensions encoding his/her research keywords. Accordingly we construct an adjacency matrix A by denoting
1 and
1 if the two authors have coauthored papers.
4.1.2 Finance. From an anonymized user-user transaction data set provided by Tencent, we select 5,206 and 20,121 users and build two transaction networks respectively. The former is named Finance-medium and the latter is named Finance-large. For each user, we collect 7 features. We construct an adjacency matrix A by denoting 1 and
1 if the two users have one or more transaction records.
Table 1 lists the statistics of the four graphs.
4.2 Baselines and Metrics
4.2.1 Baselines. We use the following approaches as our baselines:
• DICE [34], which is a heuristic attack strategy. It first deletes some edges incident to the target set , then spends the remaining budget for inserting edges between
and the rest of the graph.
• Modularity Based Attack (MBA) [9], which weakens the community structure by deleting intra-community edges and inserting inter-community edges. It is based on modularity [24].
• Random Target Attack (RTA), which follows the idea of RND [37]. Given , in each step we randomly sample a node. If the node is connected to
, we delete an edge between the node and
randomly; otherwise we add an edge between the node and
4.2.2 Metrics. We follow [34] and use two measures to quantify the degree of hiding:
where K > 1. The numerator grows linearly with the number of communities thatis distributed over. The denominator penalizes the cases in which
is skewly distributed over the community structures. Intuitively this measure
focuses on how well the members of
spread out across
[0, 1].
where the numerator grows linearly with the number of nonmembers of that appear simultaneously with members of
the same community. Note the numerator only counts the communities in which there exists a member of
. Basically, this measure focuses on how well
is hidden in the crowd and
For both measures, a greater value denotes a better hiding performance.
4.2.3 Setup. For all the data sets, we set K = 10, i.e., we cluster the nodes in each graph into 10 communities. We select the target nodes by the following process: (1) use Infomap [27] to divide the graph into 10 communities, and (2) in each community select 5 nodes with the highest degrees and another 5 nodes randomly. Thus we totally have 100 target nodes for our attack. The budget
is always 10, if not specified otherwise.
For CD-ATTACK, We use the same network architecture through all the experiments. Our implementation is based on Tensorflow. We train the model using minibatch based Adam optimizer with exponential decay. We set 1, the output dimension of the first-layer GCN to be 32 and that of the second-layer GCN to be 16. In addition, we set the fully connected layer with 32 rectified linear units with a dropout rate of 0.3. The initial learning rate is 0.001.
For fair comparison, we separate the training process of CDATTACK and the surrogate community detection model. In other words, CD-ATTACK receives no feedback from the model to be attacked. We run all the methods 5 times and report their average performance.
4.3 Attacks on the Surrogate Model
4.3.1 Attack performance. Table 2 lists the experimental results on the four data sets. As all the attacks are based on the same graphs in each data set, we report the values of M1 and M2 rather than the gain/changes of these measures. Among all approaches, CDATTACK achieves the best performance on all data sets in terms of both measures, which demonstrates CD-ATTACK’s superiority. In the following, we compare the performance of the three baseline methods.
DICE: DICE performs better than RTA on all data sets except DBLPmedium, worse than MBA on most data sets except Finance-medium. One possible explanation is that DICE follows the heuristic that decreasing the density of the connections with will help, while RTA is randomly based and it has a higher probability not to cut the edges between targets.
MBA: MBA performs quite well compared with the other two baselines, which proves the effectiveness of adopting modularity to select the candidate edges. However it performs worse than DICE on Finance-medium, meaning it is not stable.
RTA: RTA performs worse than most methods except that it outperforms DICE on DBLP-medium. A possible explanation is that randomness may win in some scenarios as it can explore more possibilities.
Table 2: Performance comparison of different attacks on the surrogate model
Figure 5: CD-ATTACK performance with different budgets on DBLP-medium
We evaluate how the budget
affects the attack performance. Taking CD-ATTACK on DBLPmedium as an example, we vary
from 2 to 20 and plot the corresponding attack performance in terms of M1 and M2 in Figure 5. As we increase
, the attack performance improves (i.e., both M1 and M2 increase), meaning that a larger budget is helpful for a successful attack. Another observation is that the attack performance increases quite fast when
10 and becomes stable when
10, indicating the effect of
becomes less obvious as we further increase the budget.
4.3.3 Adversarial cost. We compare the adversarial costs of different attacks on DBLP-medium. The result is shown in Figure 6, in which local means we use GCN for the neighborhood smoothing in the surrogate community detection model and global means we use PPNP [16] instead. From the figure we can find that our method achieves the lowest perturbation loss, and this is not surprising as we explicitly take this constraint into consideration when selecting the proper candidates.
4.3.4 Visualization. To have a better understanding of how CDATTACK works, we target a subgraph of DBLP-medium which consists of 24 nodes under the attack in Section 4.3.1. We have two target nodes 8 and 9 included in this subgraph, which correspond to Sumit Chopra and Geoffrey Hinton respectively. We inspect how the community assignment changes with respect to the attack, as depicted in Figure 7. In this figure, different colors represent different community assignment. As we can see, at the beginning the community detection algorithm considers the two targets are in the same community (on the left). As we cut an edge (0, 15) (in red), the community detection algorithm separates the subgraph
Figure 6: Cost comparison of different attacks on DBLP-
into two parts, thus fails to treat the two targets in one community. An interesting observation is that the attack CD-ATTACK chooses is not a direct attack but rather an influence attack, as the removed edge does not involve either node 8 or 9 as an end point, which differs from most of our competitors.
4.4 Transferability
In this part, we shall explore whether the adversarial graphs generated by our methods also apply to other graph learning based community detection models. In this vein, we select two widely used target models as follows:
• Node2vec + K-means (NK) which first uses Node2vec [11] to get node embeddings and then utilizes K-means to derive community assignments.
• ComE [5] which jointly solves community embedding, community detection and node embedding in a closed loop. We use the highest probability across the K communities as the last community assignment. We test the transferability of our method with the following procedure: (1) run our method and three competitors and get the corresponding adversarial graphs, and (2) train the target models based on the adversarial graphs. We report the performance on DBLPmedium and Finance-medium in Table 3 and Table 4 for NK and ComE respectively.
As we can see, while all the attacking methods are effective, our method achieves the best transferability on most measures. We therefore conclude that our surrogate model and normalized cut measure are a sufficient approximation of the true measures used in other models.
Attacks on Community Detection. In the literature, three studies have a similar setting as ours in the sense that they also want to hide a set of individuals. [22] first formulates the problem and
Figure 7: A case to show how CD-ATTACK hides individuals
Table 3: Performance comparison of different attacks on NK
Table 4: Performance comparison of different attacks on ComE
comes up with a solution by adding edges for nodes with high degree centrality. Later [34] proposes two heuristic algorithms ROAM and DICE for hiding an individual and a community respectively. It also formulates two measures to quantify the level of deception of a detection algorithm, which we follow in this work. [9] further extends the idea by proposing the concept of community deception and two attacking methods: safeness-based deception and modularity-based deception. Our work differs from them in three aspects: (1) we focus on deep graph based community detection methods, (2) our method can handle attributed graphs while none of the previous studies can, and (3) we consider not only a budget but also a graph similarity to ensure unnoticeable perturbations.
Neural Network based Community Detection. There have been many neural network based community detection methods ever since the pioneer graph embedding studies [11, 26]. One straightforward approach is first utilizing node embedding methods such as Node2vec [11] and then applying K-means to obtain cluster assignment results. However, such a pipeline lacks a unified optimization objective, which makes the results suboptimal. In this regard, [5] jointly solves community embedding, community detection and node embedding in a closed loop. However, the gradient still cannot be passed between different modules. [7] overcomes this problem by introducing a line-graph based variation of GNNs in a supervised community detection scenario. [23] further generalizes GNNs to tackle unsupervised community detection problems based on min-cut. Our design is similar to [23] except that we encourage cluster assignments to be orthogonal by a novel regularization.
Imperceptible Perturbations. Adversarial perturbations are required to be imperceptible in order to foul the corresponding detecting module. In the image domain, one can use norm distance [4] to achieve unnoticeable modifications. In the graph domain, it is still an open problem to ensure unnoticeable perturbations [31]. In [8], the attacker is restricted to add/remove edges in the original graph within a budget. In [37], the attacker is further required to maintain the power-law degree distribution in addition to the budget constraint. However, maintaining the power-law distribution is neither necessary nor sufficient as a recent study [3] has found real-world networks with a power-law distribution are very rare. In this work, we leverage the general graph similarity metrics to measure the degree of modifications, in the hope of guaranteeing minimal perturbations on the original graph. Especially, we instantiate our measurements by two similarities: Personalized PageRank [25] and adjacency matrix based similarity.
Constrained Graph Generation. Although there are many studies on graph generation [12, 14], constrained graph generation has been studied less. GVAE [19] first constructs parse trees based on the input graph and then uses Recurrent Neural Networks (RNNs) to encode to and decode from these parse trees. It utilizes the binary mask mechanism to delete invalid vectors. NeVAE [28] and CGVAE [21] both leverage GNNs to generate graphs which match the statistics of the original data. They make use of a similar mask mechanism to forbid edges that violate syntactical constraint. Our model also uses the mask mechanism to prevent generating undesirable edges.
Relation with Other Frameworks. We design an iterative framework in this work. It has some connections with some popular frameworks.
• Generative Adversarial Network (GAN) [10], which is an iterative framework consisting of two modules: the generator and the discriminator. Usually GAN is formulated as a minimize/maximize paradigm in which the generator aims to minimize the distance between true and generated data, while the discriminator wants to maximize the distance. Our framework is different as it does not belong to this paradigm.
• Actor-Critic framework [17], which is a class of techniques in reinforcement learning. It consists of two modules: the actor (generator) and the critic (discriminator). Usually the actor must learn based on the estimated error signals, e.g., policy gradient, from the critic. Our model belongs to this framework.
In this paper, we study adversarial attack on graph learning based community detection models via hiding a set of nodes. To overcome the difficulty of no explicit feedback from the detection module in reality, we design a new graph learning based community detection model based on the widely used GNNs and normalized cut. Given the huge search space of selecting proper candidate edges to change, we take a learning approach and design a graph generator that can meet the discrete constraint. We systematically analyze how we can measure the adversarial costs of various attacks and come up with a clear graph objective from two perspectives: local proximity and global proximity. Experimental results on four real-world data sets show that CD-ATTACK outperforms other competitors by a significant margin in two measures. The adversarial graphs generated can also be transferred to other graph learning based community detection models.
The work described in this paper was supported by grants from the Research Grant Council of the Hong Kong Special Administrative Region, China [Project No.: CUHK 14205618], Tencent AI Lab RhinoBird Focused Research Program GF201801.
[1] Yong-Yeol Ahn, James P Bagrow, and Sune Lehmann. 2010. Link communities reveal multiscale complexity in networks. Nature 466, 7307 (2010), 761–764.
[2] Leman Akoglu, Hanghang Tong, and Danai Koutra. 2015. Graph based anomaly detection and description: a survey. Data Mining and Knowledge Discovery 29, 3 (2015), 626–688.
[3] Anna D Broido and Aaron Clauset. 2019. Scale-free networks are rare. Nature Communications 10, 1 (2019), 1017.
[4] Nicholas Carlini and David Wagner. 2017. Towards evaluating the robustness of neural networks. In IEEE Symposium on Security and Privacy (SP). 39–57.
[5] Sandro Cavallari, Vincent W Zheng, Hongyun Cai, Kevin Chen-Chuan Chang, and Erik Cambria. 2017. Learning community embedding with community detection and node embedding on graphs. In CIKM. 377–386.
[6] Jinyin Chen, Lihong Chen, Yixian Chen, Minghao Zhao, Shanqing Yu, Qi Xuan, and Xiaoniu Yang. 2018. GA-Based Q-Attack on Community Detection. IEEE Transactions on Computational Social Systems 6 (2018), 491–503.
[7] Zhengdao Chen, Xiang Li, and Joan Bruna. 2019. Supervised community detection with line graph neural networks. In ICLR.
[8] Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. 2018. Adversarial attack on graph structured data. In ICML. 1123–1132.
[9] Valeria Fionda and Giuseppe Pirro. 2017. Community deception or: How to stop fearing community detection algorithms. IEEE Transactions on Knowledge and Data Engineering 30, 4 (2017), 660–673.
[10] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. 2014. Generative adversarial nets. In NIPS. 2672–2680.
[11] Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable feature learning for networks. In KDD. 855–864.
[12] Aditya Grover, Aaron Zweig, and Stefano Ermon. 2019. Graphite: Iterative generative modeling of graphs. In ICML. 2434–2444.
[13] Diederik P Kingma and Max Welling. 2014. Auto-encoding variational bayes. In ICLR.
[14] Thomas N Kipf and Max Welling. 2016. Variational Graph Auto-Encoders. In NIPS Workshop on Bayesian Deep Learning.
[15] Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In ICLR.
[16] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. 2019. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR.
[17] Vijay R Konda and John N Tsitsiklis. 2000. Actor-critic algorithms. In NIPS. 1008–1014.
[18] Danai Koutra, Ankur Parikh, Aaditya Ramdas, and Jing Xiang. 2011. Algorithms for graph similarity and subgraph matching.
[19] Matt J Kusner, Brooks Paige, and José Miguel Hernández-Lobato. 2017. Grammar variational autoencoder. In ICML. 1945–1954.
[20] Jia Li, Yu Rong, Hong Cheng, Helen Meng, Wenbing Huang, and Junzhou Huang. 2019. Semi-Supervised Graph Classification: A Hierarchical Graph Perspective. In WWW. 972–982.
[21] Qi Liu, Miltiadis Allamanis, Marc Brockschmidt, and Alexander Gaunt. 2018. Constrained graph variational autoencoders for molecule design. In NeurIPS. 7795–7804.
[22] Shishir Nagaraja. 2010. The impact of unlinkability on adversarial community detection: effects and countermeasures. In International Symposium on Privacy Enhancing Technologies Symposium. 253–272.
[23] Azade Nazi, Will Hang, Anna Goldie, Sujith Ravi, and Azalia Mirhoseini. 2019. GAP: Generalizable Approximate Graph Partitioning Framework. In ICLR workshop.
[24] Mark EJ Newman. 2006. Modularity and community structure in networks. Proceedings of the National Academy of Sciences 103, 23 (2006), 8577–8582.
[25] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. The PageRank Citation Ranking: Bringing Order to the Web. Technical Report 1999-66. Previous number = SIDL-WP-1999-0120.
[26] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. Deepwalk: Online learning of social representations. In KDD. 701–710.
[27] Martin Rosvall and Carl T Bergstrom. 2008. Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences 105, 4 (2008), 1118–1123.
[28] Bidisha Samanta, DE Abir, Gourhari Jana, Pratim Kumar Chattaraj, Niloy Ganguly, and Manuel Gomez Rodriguez. 2019. Nevae: A deep generative model for molecular graphs. In AAAI. 1110–1117.
[29] Uri Shaham, Kelly Stanton, Henry Li, Boaz Nadler, Ronen Basri, and Yuval Kluger. 2018. Spectralnet: Spectral clustering using deep neural networks. In ICLR.
[30] Jianbo Shi and Jitendra Malik. 2000. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 22, 8 (2000), 888– 905.
[31] Lichao Sun, Ji Wang, Philip S Yu, and Bo Li. 2018. Adversarial attack and defense on graph data: A survey. arXiv preprint arXiv:1812.10528 (2018).
[32] Meng Tang, Abdelaziz Djelouah, Federico Perazzi, Yuri Boykov, and Christopher Schroers. 2018. Normalized cut loss for weakly-supervised cnn segmentation. In CVPR. 1818–1827.
[33] Meng Wang, Chaokun Wang, Jeffrey Xu Yu, and Jun Zhang. 2015. Community detection in social networks: an in-depth benchmarking study with a procedureoriented framework. Proceedings of the VLDB Endowment 8, 10 (2015), 998–1009.
[34] Marcin Waniek, Tomasz P Michalak, Michael J Wooldridge, and Talal Rahwan. 2018. Hiding individuals and communities in a social network. Nature Human Behaviour 2, 2 (2018), 139.
[35] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. 2019. A comprehensive survey on graph neural networks. arXiv preprint arXiv:1901.00596 (2019).
[36] Yang Zhou, Hong Cheng, and Jeffrey Xu Yu. 2009. Graph clustering based on structural/attribute similarities. Proceedings of the VLDB Endowment 2, 1 (2009),
718–729.
[37] Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. 2018. Adversarial Attacks on Neural Networks for Graph Data. In KDD. 2847–2856.