{'fraction_non_alphanumeric': 0.04027270513757, 'fraction_numerical': 0.01628926223520818, 'mean_word_length': 4.671223418945043, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Graph Clustering with Graph Neural Networks

Graph Neural Networks (GNNs) have achieved state-of-the-art results on many graph analysis tasks such as node classification and link prediction. However, important unsupervised problems on graphs, such as graph clustering, have proved more resistant to advances in GNNs. Graph clustering has the same overall goal as node pooling in GNNs - does this mean that GNN pooling methods do a good job at clusterings graphs? Surprisingly, the answer is no - current GNN pooling methods often fail to recover the cluster structure in cases where simple baselines, such as k-means applied on learned representations, work well. We investigate further by carefully designing a set of experiments to study different signal-to-noise scenarios both in graph structure and attribute data. To address these methods' poor performance in clustering, we introduce Deep Modularity Networks (DMoN), an unsupervised pooling method inspired by the modularity measure of clustering quality, and show how it tackles recovery of the challenging clustering structure of real-world graphs. Similarly, on real-world data, we show that DMoN produces high quality clusters which correlate strongly with ground truth labels, achieving state-of-the-art results with over 40% improvement over other pooling methods across different metrics.


Introduction
In recent years there has been a surge of research interest in developing varieties of Graph Neural Networks (GNNs)-specialized deep learning architectures for dealing with graphstructured data, such as social networks (Perozzi et al., 2014b), recommender graphs (Ying et al., 2018a), or molecular graphs (Defferrard et al., 2016). GNNs leverage the structure of the data as a computational graph, allowing the information to propagate across the edges of graphs (Scarselli et al., 2008). When many real-wold systems are represented as graphs, they exhibit locally inhomogeneous distributions of edges, forming clusters (also called communities or modules)-groups of nodes with high in-group edge density, and relatively low out-group density. Clusters can correspond to interesting phenomena in the underlying graph, for example to education (Traud et al., 2011) or employment (Papacharissi, 2009) in social graphs. GNNs have been shown to benefit from leveraging higher-order structural information that could arise from clusters Ying et al., 2018b), for example through pooling or trainable attention over edges (Veličković et al., 2017).
Interestingly, most existing work on GNNs to leverage higher-order structure does not directly address node partitioning or cluster assignments within the computational graph. Furthermore, most works explore these mechanisms only within a semi-supervised or supervised framework, ignoring the fact that unsupervised graph clustering is often an extremely useful end-goal in itself-whether for data exploration (Perozzi and Akoglu, 2018), visualization (Clémençon et al., 2012;Cui et al., 2008), genomic feature discovery (Cabreros et al., 2016), anomaly detection (Perozzi and Akoglu, 2016), or for many other use-cases discussed e.g. in Fortunato and Hric (2016). Additionally, many of the existing unsupervised structure-aware methods have undesirable properties, such as relying on a multi-step optimization process which does not allow for an end-to-end differentiable objective (Perozzi et al., 2014a).
In this work, we take an ab initio approach to the clustering problem in the GNN domain, bridging the gap between traditional graph clustering objectives and deep neural networks. We start by drawing a connection between graph pooling, which was typically studied in the literature as a regularizer for supervised GNN architectures, and fully unsupervised clustering. Specifically, we contribute: • DMoN, an unsupervised clustering module for GNNs that allows optimization of cluster assignments in an end-to-end differentiable way with strong empirical performance.
• An empirical study of performance on synthetic graphs, illustrating the problems with existing work and how DMoN allows for improved model performance in those regimes.
• Thorough experimental evaluation on real-world data, showing that many pooling methods poorly reflect hierarchical structures and are not able to make use of either graph structure and node attributes nor leverage joint information.

Related Work
We build upon a rich line of research on graph neural networks and graph pooling methods.
Graph Neural Networks (GNNs) (Scarselli et al., 2008;Duvenaud et al., 2015;Niepert et al., 2016;Gilmer et al., 2017;Kipf and Welling, 2017) allow end-to-end differentable losses over data with arbitrary structure. They have been applied to an incredible range of applications, from social networks (Perozzi et al., 2014b), to recommender systems (Ying et al., 2018a), to computational chemistry (Gilmer et al., 2017). While GNNs are flexible enough to allow for unsupervised losses, most work follows the semi-supervised setting for node classification from (Kipf and Welling, 2017). For a complete introductions to the vast topic we refer interested readers to detailed surveys (Bronstein et al., 2017;Hamilton et al., 2017;Chami et al., 2020).
Unsupervised training of GNNs is commonly done via maximizing mutual information (Belghazi et al., 2018;Tschannen et al., 2020;Song and Ermon, 2020) in a self-supervised fashion. Deep Graph Infomax (DGI) (Veličković et al., 2019) adapted the mutual informaton-based learning from Deep InfoMax (Hjelm et al., 2019), learning unsupervised representations for nodes in attributed graphs. InfoGraph (Sun et al., 2020) extended the idea to learning representations of whole graphs instead of nodes. A very similar approach was independently proposed by  in the context of pre-training GNNs for producing graph representations, which was first studied in Navarin et al. (2018).
Graph pooling aims to tackle the hierarchical nature of graphs via iterative coarsening. Early architectures (Defferrard et al., 2016) resorted to fixed axiomatic pooling, with no optimization of clustering while the network learns. DiffPool (Ying et al., 2018b) suggests to include a learnable pooling to GNN architecture. To help the convergence, DiffPool includes a link prediction loss to help encapsulate the clustering structure of graphs and an additional entropy loss to penalize soft assignments. Top-k (Gao and Ji, 2019) and SAG pooling (Lee et al., 2019) learn to sparsify the graph (select top-k edges for each node) with learned weights. MinCutPool (Bianchi et al., 2020) pooling studies differentiable formulation of spectral clustering as a pooling strategy. As we show in Section 4.2, MinCutPool does not optimize its spectral objective, it merely orthogonalizes its features. We summarize mainstream graph pooling methods in Table 1 in terms of seven desirable properties related to their clustering capabilities: • End-to-end training allows to capture both graph structure and node features. AGC (Zhang et al., 2019), DAEGC (Wang et al., 2019a), and SDCN (Bo et al., 2020) use k-means to initialize the model, prohibiting end-to-end learning.
• Unsupervised training is a desirable setting for clustering models. Works on supervised graph clustering (Yang et al., 2019;Wang et al., 2019b) are outside of our scope.
• Node aggregation is crucial for our interpretation of graph pooling in terms of clustering. Both Top-k and SAG pooling only sparsify the graph and do not reduce the nodeset.
• Sparse. As graphs in the real-world vary in size and sparsity, methods cannot be limited by an O(n 2 ) link prediction objectives, like DiffPool (Ying et al., 2018b), or computing A t , like top-k pooling methods (Gao and Ji, 2019;Lee et al., 2019) or AGC and DAEGC. The gradients of NOCD (Shchur and Günnemann, 2019) are quadratic in the number of nodes; however, subsampling is solved to attain desirable subquadratic scalability.
• Soft assignments allow for more flexible reasoning about the interactions of clusters.
• Stable -the method should be stable in terms of the graph structure. DiffPool, AGC, DAEGC, and SDCN is not stable in terms of graph sparsity, while MinCutPool fails to converge on power-law graphs. We additionally analyze the computational complexity of the methods. Generally, nonsparse methods, for instance DiffPool, AGC, and DAEGC can not scale to large graphs, since their complexity is at least quadratic. Some methods, like NOCD, top-k pooling, and SAG subsample the quadratic terms in their objectives/optimizations to attain desirable scalability. We analyze the complexity of DMoN in Section 4.1. DMoN maintains best-in-class scalability without sacrificing any information to subsampling.
Graph embeddings (Perozzi et al., 2014b;Grover and Leskovec, 2016;Tsitsulin et al., 2018) can be thought of as (very restricted) unsupervised GNNs with an identity feature matrix, meaning each node learns its own positional representation (You et al., 2019). The learning process in graph embeddings is often done in a similar way to DGI through noise contrastive estimation (Gutmann and Hyvärinen, 2010). As far as we know, all pooling strategies for learning node embeddings without attributes have been rigid Liang et al., 2018;Deng et al., 2020); making learning-based ones an interesting future research direction.

Preliminaries
We introduce the necessary background for DMoN, starting with the problem formulation, reviewing common graph clustering objectives and how they can be made differentiable.
A graph G = (V, E) is defined via a set of nodes V = (v 1 , . . . , v n ), |V | = n and edges E ⊆ V × V, |E| = m. We denote the n × n adjacency matrix of G by A, where A ij = 1 iff {v i , v j } ∈ E (otherwise entries of A are equal to 0). The "degree" of v i is its number of connections d i := n j=1 A ij . We are interested in measuring the quality of graph partitioning function F : V → {1, . . . , k} that splits the set of nodes V into k partitions V i = {v j : F(v j ) = i}. In contrast to standard graph clustering, we are also provided with node attributes X ∈ R n×s .

Graph Clustering Quality Functions
As classical clustering objectives are discrete and therefore unsuitable for gradient-based optimization, DMoN and the few prior works depend on spectral approximations. To contextualize and motivate our contributions, we review two families of clustering quality functions amenable to spectral optimization, and review some of their shortcomings.
Cut-based metrics. In his seminal work, Fiedler (1973) suggested that the second eigenvector of a graph Laplacian produces a graph cut minimal in terms of the weight of the edges. This plain notion of cut degenerates on real-world graphs, as it does not require partitions to be balanced in terms of size. It is possible to get normalized partitions with the use of ratio cut (Wei and Cheng, 1989), which normalizes the cut by the product of the number of nodes in two partitions, or normalized cut (Shi and Malik, 2000), which uses total edge volume of the partition as normalization.
In real networks, however, there is evidence against existence of good cuts (Leskovec et al., 2008) in ground-truth communities. This can be explained by the fact that a single node implicitly participates in many different clusters (Epasto et al., 2017), e.g. a person in a social network is simultaneously connected with family and work friends, forcing the algorithm to merge these communities together.
Recently, MinCutPool (Bianchi et al., 2020) adapted the notion of the normalized cut to use as a regularizer for pooling. While MinCutPool's objective should, theoretically, be suitable for clustering nodes in graphs, we show that MinCutPool does not optimize its own objective function, using synthetic and real-world experiments.
Modularity. The modularity (Newman, 2006a) objective approaches the same problem from a statistical perspective, incorporating a null model to quantify the deviation of the clustering from what would be observed in expectation under a random graph. In a fully random graph with given degrees, nodes u and v with degrees d u and d v are connected with probability dudv /2m. Modularity measures the divergence between the intra-cluster edges from the expected one: where δ(c i , c j ) = 1 if i and j are in the same cluster and 0 otherwise. Note Q ∈ ( −1 /2; 1] (it is 0 when there is no correlation of clusters with edge density), but it is not necessarily maximized at 1, and is only comparable across graphs with the same degree distribution. While problems with the modularity metric have been identified (Good et al., 2010), it remains one of the most commonly-used and eminently useful graph clustering metrics in scientific literature (Fortunato and Hric, 2016).

Spectral Modularity Maximization
Maximizing the modularity is proven to be NP-hard (Brandes et al., 2006), however, a spectral relaxation of the problem can be solved efficiently (Newman, 2006b). Let C ∈ 0, 1 n×k be the cluster assignment matrix and d be the degree vector. Then, with modularity matrix B defined as B = A − dd 2m , the modularity Q can be reformulated as: Relaxing C ∈ R n×k , the optimal C maximizing Q is the top-k eigenvectors of the modularity matrix B. While B is dense, iterative eigenvalue solvers can take advantage of the fact that B is a sum of a sparse A and rank-one matrix − dd 2m , meaning that the matrix-vector product Bx can be computed efficiently as Bx = Ax − d xd 2m and optimized efficiently with iterative methods such as power iteration or Lanczos algorithm. One can then obtain clusters by means of spectral bisection (Newman, 2006b) with iterative refinement akin to Kernighan-Lin algorithm (Kernighan and Lin, 1970). However, these formulations operate entirely on the graph structure, and it is non-trivial to adapt them to work with attributed graphs.

Graph Neural Networks
Graph Neural Networks are a flexible class of models that perform nonlinear feature aggregation with respect to graph structure. For the purposes of this work, we consider transductive GNNs that output a single embedding per node. Graph convolutional networks (GCNs) Kipf and Welling (2017) are simple yet effective Shchur et al. (2018) message-passing networks that fit our criteria. Let X 0 ∈ R n×s be the initial node features andÃ = D − 1 2 AD − 1 2 be the normalized adjacency matrix, the output of t-th layer X t+1 is We make two changes to the classic GCN architecture: first, we remove the self-loop creation and instead use an W skip ∈ R s×s trainable skip connection, and, second, we replace ReLU nonlinearity with SeLU (Klambauer et al., 2017) for better convergence.

Method
In this section, we present DMoN, our method for attributed graph clustering with graph neural networks. Inspired by the modularity quality function and its spectral optimization, we propose a fully differentiable unsupervised clustering objective which optimizes soft cluster assignments using a null model to control for inhomogeneities in the graph. We then discuss the challenge of regularizing cluster assignments, and present collapse regularization that is effective at preventing trivial solutions without compromising optimization of the objective.

DMoN: Deep Modularity Networks
Our approach to GNN modularity is comprised of (1) the architecture to encode the cluster assignments C, and (2) the objective function with which to optimize the assignments. We propose to obtain C via the output of a softmax function, which allows the (soft) cluster assignment to be differentiable. The input to the cluster assignment can be any differentiable message passing function, but here we specifically consider the case where a graph convolutional network is used to obtain soft clusters for each node as follows: where GCN is a (possibly) multi-layer convolutional network operating on a normalized adjacency matrixÃ = D − 1 2 (A)D − 1 2 . We then propose to optimize this assignment with the following objective, which combines insights from spectral modularity maximization (recall Eq. (2)) with a novel regularization to prevent trivial solutions to the optimization problem: where · F is the Frobenius norm. We decompose the computation of Tr(C BC) as a sum of sparse matrix-matrix multiplication and rank-one degree normalization Tr(C AC − C d dC). This brings the time complexity of computing L DMoN down from O(n 2 ) to O(d 2 n) per update, allowing DMoN to efficiently work with sparse graphs.

Collapse regularization
Without additional constraints on the assignment matrix C, spectral clustering for both min-cut and modularity objectives has spurious local minima: assigning all nodes to the same cluster produces a trivial locally optimal solution that traps gradient-based optimization methods. MinCutPool addresses this problem by adapting spectral orthogonality constraint in the form of soft-orthogonality regularization C C − I F (Bansal et al., 2018). We notice that this term is overly restrictive when combined with softmax class assignment -intuitively, when the value range of C is restricted to R ∩ [0, 1], optimization of the soft-orthogonality regularizer dominates the loss.  We illustrate this problem in Figure 1, which depicts the progress of optimization for both methods in terms of their main objective and regularizer term over the course of 200 epochs on the CORA dataset. The soft orthogonality regularization term dominates the optimization for MinCutPool, such that the cut objective becomes worse than random over the course of training.
We experimentally verify that the MinCut clustering objective is a proverbial fifth wheel for MinCut-Pooling optimization. Table 2 presents the difference in performance of the optimization of full MinCutPool objective and simple feature orthogonalization (Ortho in the table). On 3 out of 5 datasets, orthogonalityonly version achieves better label correlation than the join optimization of MinCutPool. Regularization dominates the method's performance.
With DMoN, we fix this problem by proposing a relaxed notion of collapse regularization that prevents the trivial partition while not dominating the optimization of the main objective. The regularizer is a Frobenius norm of the (soft) cluster membership counts, normalized to range [0, √ k]. It gets value of 0 when cluster sizes are perfectly balanced, and √ k in the case all clusters collapse to one. We also improve the training by applying dropout (Srivastava et al., 2014) to GNN representations before the softmax, preventing the gradient descent from getting stuck in the local optima of the highly non-convex objective function.

Theoretical insights
In this section we examine the validity of our proposed objective function, and in particular our novel collapse constraint. Specifically, we show two theorems: 1. We prove that optimizing our collapse constraint avoids the solution with trivial clusters, and hence accomplishes the effect for which it was designed.
2. Since the collapse constraint inherently discourages unbalanced cluster assignments (to avoid the trivial clustering), we also show that this discouragement does not affect the asymptotic performance of our overall objective function.
The first theorem essentially tells us that that the collapse regularization can not hurt optimization in non-trivial graphs: Theorem 1 If the clustering solution encoded by the C matrix has positive modularity, then our objective score L DMoN it smaller than the one produced by the trivial clustering.
Proof We show that both components of the loss are smaller. Since modularity of the trivial clustering is 0, any positive modularity will result in a smaller loss. Maximum of L 2 norm of a vector with given L 1 norm is achieved when only one element is nonzero -in case of the collapse regularization, when all nodes are in one cluster. Therefore, any other partition produces a smaller value.
Our second theorem is based on previous work on the "consistency" of graph clustering algorithms under an appropriate graph generative model. In Bickel and Chen (2009) and Zhao et al. (2012), a graph clustering algorithm is consistent if the global maximum clustering solution from its objective function has (in-probability) vanishing error rate in the limit of large graphs, when graphs are generated from the cluster-laden Degree-Corrected Stochastic Block Model (DC-SBM). We now detail this model and specific notions of consistency, and show that our novel, GNN-compatible objective function has consistency properties that are equivalent to standard objective functions.
The standard (degree-free) Stochastic Block Model (Nowicki and Snijders, 2001) is a generative graph model which divides n vertices into k classes, and then places edges between two vertices v i and v j with probability p ij determined from the class assignments. Specifically, each vertex v i is given a class y i ∈ {1, . . . , k}, and an edge {v i , v j } is added to the edge set E with probability P y i y j , where P is a symmetric k × k matrix containing the between/withincommunity edge probabilities. In other words, each entry A ij of the adjacency matrix is an independent Bernoulli random variable with probability P y i y j = E[A ij ]. Assortative clustering structure in a graph can be induced using the SBM by setting the on-diagonal probabilities of P higher than the off-diagonal probabilities. Thus, the SBM has been used to analyze graph clustering algorithms both theoretically (Bickel and Chen, 2009;Abbe and Sandon, 2015) and empirically (Mothe et al., 2017).
The Degree-Corrected SBM (Karrer and Newman, 2011) was introduced to handle the heterogeneity of real-world degree distributions. In the DC-SBM, each node v i is given a degree parameter θ i , and edges are generated via the formula E[A ij ] = θ i θ j P y i y j . Thus two nodes with higher degree parameters will connect more frequently under this model.
In this paper, we adopt the theoretical setting from Zhao et al. (2012): in a DC-SBM P n on n nodes with k classes, each node v i is given a label/degree pair (y i , θ i ) drawn from a discrete joint distribution Π k×m which is fixed and does not depend on n. This implies that each θ i is one of a fixed set of values 0 ≤ x 1 ≤ . . . ≤ x m . To facilitate analysis of asymptotic graph sparsity, we parameterize the edge probability matrix P as P n = ρ n P where P is independent of n, and ρ n = λ n /n where λ n is the average degree of the network. We assume that x 2 m max P n ≤ 1.0 so that all edge probabilities are proper. We define the marginal distribution of the labels y asπ = (π 1 , . . . ,π k ).
Given a DC-SBM P n on n nodes with k classes, we denoteŷ n = [ŷ 1 ,ŷ 2 , . . . ,ŷ n ] to be a predicted class label vector, andĈ n to be the associated n × k row-wise one-hot matrix.
With A (n) the random adjacency matrix of the DC-SBM, define the random variableĈ n to be the global maximum of L DMoN ( · ; A (n) ) over all n × k label matrices. Let C n be the true one-hot label matrix associated with the DC-SBM class labels y n := [y 1 , y 2 , . . . , y n ]. Let µ be any k × k permutation matrix, and let || · || F be the Frobenius norm. As in Zhao et al. (2012), we consider two notions of consistency: We now state our main theorem, which shows that DMoN's novel collapse constraint does not prevent asymptotically-consistent prediction of the optimal class labels.
Theorem 2 Under the conditions of Theorem 3.1 from Zhao et al. (2012), when the cluster sizes of the DC-SBM are equal, L DMoN is strongly consistent when λ n / log(n) → ∞ and weakly consistent when λ n → ∞.
Proof This result relies on a general theorem from Zhao et al. (2012), which is restated here for completeness. For convenience, dependence on n will be ignored when it does not cause ambiguity. The DMoN objective can be re-written as a function of inter-class edge counts O(A, y) rs = i,j A ij · 1(y i = r, y j = s) and class proportions π(y) r = n −1 i 1(y i = r). LetŌ(A, y) r = s O(A, y) rs and m(A) = rŌ (A, y) r . Henceforth dependence on y will sometimes be ignored for clarity. With these notations, we have Hence L DMoN (C; A) can be written as a function F (O, π) of a k × k edge count matrix O and a k × 1 class proportion vector π. Theorem 4.1 from Zhao et al. (2012) shows that if F satisfies regularity conditions and is uniquely minimized by the conditional expectation of its arguments under the DC-SBM P n , then the objective function that F describes is both strongly and weakly consistent under the model. The regularity conditions are listed in Section 4 of Zhao et al. (2012) and are easy to verify against L DMoN . We now show that L DMoN is uniquely minimized by the conditional expectation of its arguments under the DC-SBM P n . In other words, L DMoN must be uniquely minimized at any point (y * , A * ) such that E n [π(y n )] = π(y * ) and E n A (n) = A * . Note that the first term of L DMoN is the (negative) standard Newman-Girvan modularity, which was shown to be minimized under the expected DC-SBM in Zhao et al. (2012) (see the proof of Theorem 3.1). The proof is complete as the DMoN collapse constraint is minimized when the cluster sizes are equal.

Experiments
In this section, we describe empirical experiments-involving both synthetic and real-world data-on DMoN and baseline methods, to test robustness and performance against both graph clustering and label alignment metrics. We use open-source graph simulation tools, publicly-available datasets, and we release the implementation of DMoN at this URL 1 .  Datasets. We use 11 real-world datasets for assessing model quality. Cora, Citeseer, and Pubmed (Sen et al., 2008) are citation networks; nodes represent papers connected by citation edges; features are bag-of-word abstracts, and labels represent paper topics. Amazon PC and Amazon Photo (Shchur et al., 2018) are subsets of the Amazon co-purchase graph for the computers and photo sections of the website, where nodes represent goods with edges between ones frequently purchased together; node features are bag-of-word reviews, and class labels are product category. Coauthor CS, Coauthor Phys, Coauthor Med, Coauthor Chem, and Coauthor Eng (Shchur et al., 2018;Shchur and Günnemann, 2019) are co-authorship networks based on the Microsoft Academic Graph for the computer science, physics, medicine, and engineering fields respectively; nodes are authors, which are connected by edge if they co-authored a paper together; node features are a collection of paper keywords for author's papers; class labels indicate most common fields of study. OGB-arXiv ) is a paper co-citation dataset based on arXiv papers indexed by the Microsoft Academic graph. Nodes are papers; edges are citations, and class labels indicate the main category of the paper.
Baselines. As we study how to leverage the information from both the graph and attributes, we employ two baselines that employ either strictly graph or attribute information. We give a brief description of the baselines used below: • k-means(features) is our baseline that only considers the feature data. We use the local Lloyd algorithm (Lloyd, 1982) with the k-means++ seeding strategy (Arthur and Vassilvitskii, 2007).
• SBM (Peixoto, 2014a) is a baseline that only relies on the graph structure. We estimate a constrained stochastic block model with given k, the maximum number of clusters.
• k-means(DeepWalk, features) (Perozzi et al., 2014b) represents a naïve strategy of concatenating node attributes to learned node embeddings of the graph without attributes.
• k-means(DGI) (Veličković et al., 2019) demonstrates the need of joint learning of clusters and representations. We learn unsupervised node representations of the attributed graph with DGI and run k-means on the resulting representations.
• SDCN(graph, features) (Bo et al., 2020) is another graph reconstruction-based clustering method. Representations are initialized through k-means over auto-encoded features.
• Ortho(graph, features) (Bianchi et al., 2020) is a variant of MinCutPool that only does the cluster orthogonalization without any graph-related objective.
Metrics. We measure both the graph-based metrics of clustering and label correlation to study clustering performance of attributed graphs both in terms of graph and attribute structure. For experiments on real-world data, we measure both (1) standard graph-based clustering metrics, and (2) correlation to ground-truth node labels. Our graph-based metrics are average cluster conductance (as per definition from Yang and Leskovec (2015)) and graph modularity (Newman, 2006a). Our label-based metrics are normalized mutual information (NMI) between the cluster assignments and labels and pairwise F1 score between all node pairs and their associated cluster pairs. For experiments on synthetic data, we report only the NMI against the (simulated) cluster labels. Where possible, we normalize all metrics by multiplying them by 100 for readability and ease of comparison.
Parameter settings. We run both synthetic and real-world experiments for 10 times and average results across runs. All models were implemented in Tensorflow 2 and trained on CPUs. We fix the architecture for all GNNs (including DMoN) have one hidden layer-with 512 neurons for real-world data experiments, and 64 neurons for experiments with smaller synthetic graphs. We set the maximum number of clusters to 16 for all datasets and methods.
We aim to keep the hyperparameters constant across datasets, since (i) tuning hyperparameters in an unbiased way is non-trivial in the unsupervised setting, (ii) we report an array of metrics that relate to the graph and to the labels -favoring one group over other is not in the scope of this paper. One notable exceptions is SDCN, as it requires an autoechoder on the features to function. We keep the original three-layer encoder structure and set the architecture to [32,32,128,128,32,32] for synthetic SBM graphs and[500, 500, 2000, 2000, 500, 500] for all other datasets. Setting hyperparameters in a more fair way to keep the total number of parameters same across different methods led to random performance.
We now discuss method-specific hyperparameters for methods that have specific settings: • k-means(DeepWalk, features): We keep the learning parameters as per Perozzi et al. (2014b) number of walks γ = 80, walk length t = 80, and window size w = 10.
• AGC(graph, features): We set k = 1 to mimic a single-layer graph convolution that we set for all GNN-based methods.
• DAEGC(graph, features): We set the clustering loss coefficient γ = 10 as per the original paper.
• SDCN(graph, features): We set the clustering loss coefficient α = 0.1 and GNN loss coefficient β = 0.01 as per the original paper.
• NOCD(graph, features): We set the dropout to 0.5 uniformly across datasets and set the batch size to 2000 as per the original paper. • DMoN (graph, features): We set the dropout to 0.5 uniformly across datasets. The dropout setting we use does not benefit DAEC, SDCN, DiffPool, or MinCutPool, hence we are not able to unify the setting of that parameter across methods.

Simulation Experiments on Stochastic Block Model with Features
To explore the robustness and sensitivity of DMoN and baselines to variance in the graph and node features, we conduct a study on synthetic graphs using an attributed, degree-corrected stochastic block model (ADC-SBM). The SBM (Snijders and Nowicki, 1997) plants a partition of clusters ("blocks") in a graph, and generates edges via a distribution conditional on that partition. This model has been used extensively to benchmark graph clustering methods (Fortunato and Hric, 2016), and has recently been used for experiments on state-ofthe-art supervised GNNs (Dwivedi et al., 2020). In our version of the model, node features are also generated, using a multivariate mixture model, with the mixture memberships having some association (or de-assocation) with the cluster memberships. We proceed to describing the graph generation and feature generation components of our model.

ADC-SBM graph generation.
We fix a number of nodes n and a number of clusters k, and choose node cluster memberships uniformly-at-random. Define the matrix D k×k where D ij is the expected number of edges shared between nodes in clusters i and j. We determine D by fixing (1) the expected average degree of the nodes d ∈ {1, n}, and (2) the expected average sub-degree d out ≤ d of a node to any cluster other than its own. Note that the difference d in − d out , where d in := d − d out , controls the spectral detectability of the clusters (Nadakuditi and Newman, 2012). Finally, we generate a power-law n-vector θ, where θ i is proportional to i's expected degree. We use the generated memberships and the generated parameters D and θ as inputs to the degree-corrected SBM function from the graph-tool (Peixoto, 2014b) package.
ADC-SBM feature generation. We generate feature memberships from k f cluster labels. For graph clustering GNNs that operate both on edges and node features, it is important to examine performance on data where feature clusters diverge from or segment the graph clusters: thus potentially k f = k. We examine cases where feature memberships match, group, or nest the graph memberships, as illustrated in Figure 3. With feature memberships in-hand, we generate k zero-mean feature cluster centers from a s-multivariate normal with covariance matrix σ 2 c · I s×s . Then, for feature cluster i ≤ k f , we generate its features from a s-multivariate normal with covariance matrix σ 2 · I s×s . Note that the ratio σ 2 c /σ 2 controls the expected value of the classical between/within-sum-of-squares of the clusters.
The above paragraphs describe a single generation of our synthetic benchmark model, the ADC-SBM. To study model robustness, we define "default" ADC-SBM parameters, and explore model parameters in a range around the defaults. We configure our default model as follows: we generate graphs with n = 1, 000 nodes grouped in k = 4 clusters, and s = 32dimensional features grouped in k f = 4 matching feature clusters with σ = 1 intra-cluster center variance and σ c = 3 cluster center variance. We mimic real-world graphs' degree distribution with d = 20 average degree and d out = 2 average inter-cluster degree with power law parameters d min = 2, d max = 4, α = 2. In total, we consider 6 different scenarios, as described in Table 3. 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 d max

Scenario 6
Figure 5: Synthetic results on the ADC-SBM model with 6 different scenarios described in Table 3. DMoN leverages information from both graph structure and node attributes.
Results. We split the presentation of results for neural methods (Figure 4) and other baselines ( Figure 5) for the ease of understanding. Overall, end-to-end graph pooling methods outperform multi-step baselines by a wide margin. DMoN demonstrates overwhelming superiority over all baselines, with the most significant improvements over other pooling methods. MinCut pooling suffers from the presence of even the weak noise in the graph (Scenario 1) or in the features (Scenario 2). Moreover, it is susceptible to both nested and grouped features (Scenarios 3 and 4), while DMoN and DiffPool are less sensitive to these variations. Both DiffPool and MinCutPool are dependent on the sparsity level and degree homogeneity of the graph -DiffPool performs better denser graphs while MinCutPool shows the opposite picture.
To better understand the limits of the task, we study the performance of our baselines and report the results on Figure 5. In particular our interest lies in the performance of the SBM and pure k-means over features, as these two baselines depict the performance possible when utilizing only one aspect of the data. Scenario 1 shows that DMoN can effectively leverage the feature signal to obtain outstanding clustering performance even when the graph structure is close to random, far beyond the spectral detectability threshold (pictured in gray). Scenario 2 demonstrates that even in the presence of a weak feature signal DMoN outperforms stochastic SBM minimization. We also notice that while the k-means(DGI) baseline offers some improvements over using features or the graph structure alone, it never surpasses the strongest signal provider in the graph, never being better than the best one between k-means(features) and SBM. K-means applied over the extracted DeepWalk representations are also almost never stronger than the community detection using direct SBM likelihood optimization.  Sen et al. (2008) in terms of graph conductance C, modularity Q, NMI with ground-truth labels, and pairwise F1 measure. We group the methods into three categories: baselines using only one aspect of data, neural representation learning, and neural graph pooling methods. We highlight best neural method performance.

Cora
Citeseer Pubmed graph labels graph labels graph labels   Shchur et al. (2018) in terms of graph conductance C, modularity Q, NMI with ground-truth labels, and pairwise F1 measure. We group the methods into three categories: baselines using only one aspect of data, neural representation learning, and neural graph pooling methods. We highlight best neural method performance.

Real-world Data
We now move on to studies on real-world networks, featuring DMoN and 7 baselines on 7 different datasets. DMoN achieves better clustering performance than its neural counterparts on every single dataset and metric besides losing twice to DGI+k-means on Cora and Citeseer in terms of NMI. Compared to SBM, a method that exclusively optimizes modularity, we are able to stay within 3% in terms of modularity, while simultaneously clustering the features. Surprisingly, on Citeseer and Pubmed we achieve better modularity than the method optimizing it directly -we attribute that to very high correlation between graph structure and the features. Compared to other pooling methods, DMoN improves by over 40% in conductance, modularity and NMI on average. In particular, DiffPool achieves overall poor performance across metrics due to its quadratic reconstruction term that does not scale well with graph sparsity (cf. Scenario 5). MinCut pooling performs better, but only manages to match the performance of non-pooling neural representation learning methods on one dataset in terms of ground-truth label NMI. On Amazon PC and Amazon Photo both MinCutPool and its orthogonality-only version failed to converge, even with tuning the parameters. We attribute that to extremely uneven structure of these graphs, as popular products are co-purchased with a lot of other items, so the effects discussed in Epasto et al. (2017); Leskovec et al. (2008) are prohibiting good cuts. This corresponds to high values of d ad d max in our synthetic scenarios 5 and 6. We also highlight that we beat MinCutPool in terms of conductance (average graph cut) on all datasets, even though it attempts to optimize for this metric.
On large-scale datasets presented in Table 6, DMoN achieves 16% better performance on average across all metrics compared to other end-to-end learning methods. Some methods, like AGC, DAEGC, and DiffPool are not able to scale to large-scale graphs due to their quadratic time complexity.
Overall, DMoN demonstrates excellent performance on both graph clustering and label correlation, successfully leveraging both graph and attribute information. Both synthetic and real-world experiments prove that DMoN is vastly superior to its counterparts in attributed graph clustering. Table 6: Results on four large-scale datasets in terms of graph conductance C, modularity Q, NMI with ground-truth labels, and pairwise F1 measure. We group the methods into three categories: baselines using only one aspect of data, neural representation learning, and neural graph pooling methods. We highlight best neural method performance.

Conclusion
In this work, we study GNN pooling through the lens of attributed graph clustering. We introduce Deep Modularity Networks (DMoN), an unsupervised objective and realize it with a GNN which can recover high quality clusters. We compare against challenging baselines that baselines that optimize structure (SBM), features (kmeans), or both (DGI+k-means), in addition to a recently proposed state-of-the-art pooling method (MinCutPool). We explore the limits of GNN clustering methods in terms of both graph and feature signals using synthetic data, where we see that DMoN better leverages structure and attributes than all existing methods. In extensive experiments on real datasets we show that the clusters found by DMoN are more likely to correspond to ground truth labels, and have better properties as illustrated by clustering metrics (e.g. conductance or modularity). We hope that this work will further advancements in unsupervised learning for GNNs as well as attributed graph clustering, allowing further advances in graph learning.