{'fraction_non_alphanumeric': 0.035117130630431904, 'fraction_numerical': 0.01186747253716857, 'mean_word_length': 5.036750998668442, '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': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Relational Thematic Clustering with Mutually Preferred Neighbors

Automatically learning thematic clusters in network data has long been a challenging task in machine learning community. A number of approaches have been proposed to accomplish it, utilizing edges, vertex features, or both aforementioned. However, few of them consider how the quantification of dichotomous inclination w.r.t. network topology and vertex features may influence vertex-cluster preferences, which deters previous methods from uncovering more interpretable latent groups in network data. To fill this void, we propose a novel probabilistic model, dubbed Relational Thematic Clustering with Mutually Preferred Neighbors (RTCMPN). Different from prevalent approaches which predetermine the learning significance of edge structure and vertex features, RTCMPN can further learn the latent preferences indicating which neighboring vertices are more possible to be in the same cluster, and the dichotomous inclinations describing how relative significance w.r.t. edge structure and vertex features may impact the association between pairwise vertices. Therefore, cluster structure implanted with edge structure, vertex features, neighboring preferences, and vertex-vertex dichotomous inclinations can be learned by RTCMPN. We additionally derive an effective Expectation-Maximization algorithm for RTCMPN to infer the optimal model parameters. RTCMPN has been compared with several strong baselines on various network data. The remarkable results validate the effectiveness of RTCMPN.


Introduction
Relational data, e.g., friends on social networking sites and cited documents in scientific corpora, are ubiquitous in the real world. Network, which contains a set of vertices and edges, respectively representing data samples and samplesample relations, is thereby ideal for preserving illustrative information on the data samples and complex sample-sample * Contact Author relationships. Due to its universality, how to effectively analyze the network data has been of great importance. Among various analytical tasks on network data, cluster analysis is one of the most important, and it is directly related to many real-world applications, such as social group detection [He et al., 2019b], social recommendation [Yang et al., 2013], biological module discovery [Airoldi et al., 2008], and topic modeling in scientific articles [Chang and Blei, 2009].
Cluster analysis in networks has been a long-lasting and challenging problem in machine learning community. A number of approaches, which are either heuristic or modelbased, have been proposed to effectively uncover the network clusters, by feat of maximizing the group-wise vertex cohesiveness regarding edge density, vertex features, or both aforementioned. For example, modularity maximization [Clauset et al., 2004], which aims at optimizing the difference in terms of density of vertices in the same group and that if the vertices are randomly grouped, is a prevalent heuristic measure for cluster analysis, and it has been incorporated into many approaches to network clustering, e.g., Fast unfolding algorithm [Blondel et al., 2008]. Besides, modern machine learning techniques, including spectral analysis [Shi and Malik, 2000;Wang et al., 2019a], matrix factorization (MF) [Yang et al., 2013;Wang et al., 2016;Ye et al., 2018;Xu, 2019], and probabilistic modeling [Chang and Blei, 2009;Peng et al., 2015;Bojchevski and Günnemann, 2018], have also been used to build effective model-based approaches to immediately uncover network clusters. Not only utilizing edge structure, but also incorporating vertex features, model-based approaches can unfold network clusters and simultaneously improve the interpretability of them by summarizing their themes. Thus, many recent methods attempt to adapt cutting-edge learning techniques to discover clusters in various network data.
Though very effective in uncovering network clusters via simultaneously learning in edge structure and features, most prevalent approaches perform the task only relying on observed data, and have to predefine the learning significance of structure and features. They inevitably overlook the latent neighbor preference indicating which proximal vertices are more possible to be in the same cluster, and hidden dichotomous inclination describing how relative significance of network topology and vertex features may trigger a pair of vertices to be related. To fill this void, in this paper, we propose a novel probabilistic model, dubbed Relational Thematic Clustering with Mutually Preferred Neighbors (RTCMPN), to learn vertex-cluster membership, concerning not only edge structure and features, but also the latent neighborhood constraints and corresponding vertex-wise dichotomous inclination about topology and features. The contributions of this paper can be summarized as follows: • We propose RTCMPN, which is a novel probabilistic model for revealing clusters in the network data. RTCMPN is able to learn the latent neighboring preferences, that indicate which proximal vertices have the same cluster membership, considering the vertex-wise dichotomous inclination w.r.t. network topology and features. Modeling the associations between vertexcluster membership and the mentioned latent neighboring preference, edge structure, and vertex features, RTCMPN is capable of learning more meaningful clusters in the network data.
• For RTCMPN, we design a novel generative process for generating network data, based on which, we formulate the clustering task as optimizing a unified likelihood function. We also derive a novel Expectation-Maximization algorithm for learning the optimal variables, and parameters of the model.
• RTCMPN has been extensively compared with a number of strong baselines on various network datasets. The experimental results show that RTCMPN outperforms all the baselines on most datasets, which validate the effectiveness of the proposed model.
The rest of this paper is organized as follows. In Section 2, the previous works related to the proposed model are investigated. In Section 3, we elaborate the proposed RTCMPN, derive the EM algorithm for learning the model parameters, and analyze the computational complexity of the proposed model. The extensive experiments that are used to verify the effectiveness of RTCMPN are presented in Section 4. In the last section, we conclude the paper and discuss future works.

Related works
To effectively discover clusters in network data, a number of approaches have been proposed. Some of them are able to uncover clusters utilizing network topology.  [Wang et al., 2017], and Normalized cut (Ncut) [Shi and Malik, 2000] are widely used approaches, which perform the task of network clustering utilizing either edge structure or topological similarities.
More recent methods attempt to discover clusters as well as learn the descriptive features of them. For example, Relational topic models [Chang and Blei, 2009], Communities from edge structure and node attributes (CESNA) [Yang et al., 2013], Semantic community identification (SCI) [Wang et al., 2016], Adaptive semantic community detection (ASCD) [Qin et al., 2018], Contextual correlations preserving graph clustering [He et al., 2019b], Attributed Markov random filed model [He et al., 2019a], and Multi-view spectral clustering [Kumar et al., 2011;Wang et al., 2019a], are prevalent approaches, which perform the task of network clustering by incorporating edge structure with vertex features. It is observed that none of the previous methods for network clustering considers simultaneously modeling latent neighborhood constraints and corresponding vertex-wise dichotomous inclination about topology and features. This motivates us to propose a novel model to fill the void.

Relational thematic clustering with inclination aware neighbors
In this section, we elaborate the proposed RTCMPN. First, we introduce the mathematical notations. The model structure is then introduced according to the newly designed generative process. At last, we derive an EM algorithm to infer the optimal parameters of RTCMPN and analyze the computational complexity of the model.

Notations
Given a network composed of N vertices, |E| edges, M vertex features, and K ground-truth clusters, we use two binary matrices Y ∈ {0, 1} N ×N and F ∈ {0, 1} M ×N to represent whether two vertices are connected and whether a vertex has a corresponding feature, respectively. We denote Z ∈ R N ×N + and G ∈ R N ×N + as the observed vertex-vertex similarities in terms of vertex topology and its features, respectively. In this paper, cosine similarity is adopted to compute the mentioned likeness. The (i, j)-th element, i-th row, and j-th column of a matrix Y are denoted as Y ij , Y i· , and Y j , respectively. To build the proposed model, we use K, M , and N multinomial parameters V i· , U k , and H k to respectively represent the cluster preference of vertex i, the feature-theme proportion for cluster k, and the vertex-proportion for cluster k. We use N dimensional multinomial variables X i· and binomial variables S i· to represent latent neighbor preference and dichotomous inclination of topology and features of vertex i.

The generative process
RTCMPN takes into account the modeling of edge structure, vertex features, latent neighbor preference, and dichotomous inclination. Therefore, we design a novel generative process for the model, and the corresponding graphical representation is depicted in Fig. 1. Given a set of network data, RTCMPN generates them according to the process shown as follows.
• For each vertex i, draw K and N dimensional multinomial parameters V i· , X i· , and binomial parameters S i· as cluster preference, latent neighbor preference, and dichotomous inclinations; • For each cluster k, draw M and N dimensional multinomial parameters U k and H k as cluster theme and cluster-vertex proportion; • For each pair of vertices, draw where λ i , and C are the precision of Gaussian distribution, and product of Boltzmann constant and temperature, respectively. Given such a generative process, it is found that RTCMPN is fundamentally different from previous models for network clustering. Besides considering modeling edge structure and cluster themes utilizing vertex-cluster membership, RTCMPN further learns the latent neighboring preference (X), according to the adaptive dichotomous inclinations (S) and corresponding observed similarities (Z and G). Such neighbor preference is used to regularize the vertexcluster preference via the estimated cluster-vertex proportions, so that pairwise vertices possessing similar topological/feature inclinations and local neighbors are more possible to be assigned with similar cluster membership. RTCMPN is also different from previous approaches to learning adaptive neighbors [Nie et al., 2014;Wang et al., 2019a;Wang et al., 2019b], as they are neither capable of modeling vertexwise topological/feature inclinations, nor designed for network clustering. By making use of RTCMPN, one can acquire more descriptive information in the network, including latent cluster structure, cluster themes, vertex-wise topological/feature inclination indicating how the vertex is related to others, and the neighboring structure within each cluster.

The joint likelihood
Based on the generative process introduced in Section 3.2, the joint likelihood of the proposed model is: (1) Taking the logarithm of the joint likelihood and substituting the aggregation operators with corresponding matrix opera-tors, we have: where A is the normalization term for Boltzmann distribution, which is i =j exp{− ij }, and const contains the terms that are irrelevant to all the latent variables. Based on Eq.
(2), we can observe that the joint likelihood of the proposed model may increase when the edges are generated by appropriate cluster preferences of the corresponding bridging vertices, the features are appropriate cluster themes, and preferred neighbors are in the same cluster. Therefore, the vertexcluster preferences which we expect RTCMPN to learn can be achieved when Eq.

Learning RTCMPN
As Eq.
(2) shows, it is intractable to directly optimize the model through point estimation since the summation operators are embedded into the logarithm operator. As a result, the latent variables, including V and U, can only be optimized via approximation methods. In this paper, we derive an alternative manner for updating the latent variables of the model, based on Expectation-Maximization (EM) framework [Dempster et al., 1977]. In the E-step of each iteration, RTCMPN constructs an auxiliary function which manifests the lower bound of the log-likelihood function regarding the latent variables. Then, this lower bound is maximized by RTCMPN in the M-step. By iteratively updating the latent variables using EM algorithm, the proposed model can converge in a finite number of iterations.

E-step
To derive the lower bound of Eq.
(2) in E-step, we use the following well known property of the concavity of logarithmic functions: (3) Based on it, we may derive the following auxiliary function as the lower bound of the joint likelihood of RTCMPN (Eq. (2)): In E-step, we set the plug-in variables, including θ ij,k and φ ji,k as Eq. (4) shows, so that these plug-in variables directly take effect on the corresponding latent variables of the model. Then, we are able to maximize Eq.

M-step
In M-step, we maximize the lower bound Q(θ, φ), which is shown in Eq. (4), by simply performing point estimation. To optimize Q relevant to latent variable V ik , we construct the following Lagrangian function: where ν denotes the Lagrange multiplier in terms of the unity constraint of V i· . Letting the partial derivative w.r.t. V ik of Eq. (5) be equal to zero and substituting ν, we may derive the updating rule for V ik : Similarly, we may obtain the updating rules for U jk , X ij , H jk , and S id for d ∈ {1, 2}. The rule for updating U jk is: The updating rule for X ij is: The updating rule for H jk is: The updating rule for S id is: Finally, λ i can be updated through performing MLE: By iteratively performing E-step and M-step, RTCMPN will converge to local optima in a finite number of iterations. The process of variable learning of RTCMPN has been summarized in Algorithm 1.

Algorithm 1 Relational thematic clustering with mutually preferred neighbors (RTCMPN)
Input: Network Data: Y, F, Z, G Output: Cluster preference for each vertex Updating V ik , U jk , X ij , H jk , S id , and λ i by Eqs. end if 12: end while 13: Identify cluster label for each vertex using V.

Complexity analysis
Based on the E-step and M-step shown in Eq. (4), and Eqs. (6)-(11), the complexity of the proposed model can be approximately analyzed as follows. In E-step, setting lowerbounder for V ik , and U jk follows the order of O(K). In Mstep, updating V ik and U jk follows the order of O(3N +M ), and O(2N ), respectively. For X ij , RTCMPN considers only  [Wang et al., 2019a] are state-of-the-art approaches to network clustering, which utilize both network structure and vertex features to unfold clusters in the network.
In our experiments, we used the source codes of all the baselines provided by the authors for implementation and configured the baselines by using either default settings or recommended ones. Specifically, CESNA does not need any predefined parameter. For the rest of the baselines, including SBM, M-NMF, DANMF, k-means, MVSC, CESNA, SCI, ASCD, and GMC, we used the default settings recommended by the authors. For the number of clusters, i.e., K, which has to be determined by all the baselines except CESNA, and the proposed model, we set it to be equal to the number of ground-truth clusters of the testing dataset. All of the experiments were performed on a workstation with 6-core 3.4GHz CPU and 32GB RAM and all approaches were executed 10 times to obtain a statistically steady performance.

Dataset description
We used six real-world networks with verified ground-truth clusters as testing datasets, including two social graphs, three document networks, and one biological network. These real-world networks have different sizes and different numbers of vertex features. Ego − f acebook (Ego) [Leskovec and Mcauley, 2012] and Google+ (Gplus) [McAuley and Leskovec, 2014] are two social networks whose vertices and edges respectively represent the social networking users and their social relationships. W ashington (Wash) [Lu and Getoor, 2003], U AI, and W iki [Lu and Getoor, 2003] are three widely used document networks, whose vertices and edges represent the documents, and the citations/hyperlinks between pairwise documents, respectively. Biogrid [Stark et al., 2006] is a biological network used to describe the interactions between proteins in Saccharomyces cerevisiae. The statistics of these testing datasets are summarized in Table 1, where N is number of vertices, |E| is the number of edges, M is the number of vertex features, and K is the number of ground-truth clusters, respectively.

Evaluation metrics
Two prevalent metrics, that are Normalized Mutual Information (N M I) [He and Chan, 2018] and the Accuracy (Acc) [He et al., 2019a], are used in our experiments to evaluate the performance of different approaches. According to their definitions, larger values of N M I and Acc indicate a better matching between the detected clusters and the groundtruth.

Clustering performance comparison
Social community detection, document segmentation, and biological module identification are typical applications of network clustering. In our experiment, we used the aforementioned networks to test the effectiveness of different approaches. The experimental results (in terms of N M I and Acc) of all algorithms are summarized in Table 2.
When the detected clusters are evaluated by N M I, RTCMPN outperforms all the other baselines in five testing datasets, and ranks the second-best on Biogrid dataset. In five datasets out of six, RTCMPN is better than the second best approach by at least 5%. Specifically, in Ego−f acebook dataset, RTCMPN performs better than SBM by 8.36%. In Google+, RTCMPN outperforms DANMF by 54.58%. In W ashington, and W iki, RTCMPN is better than k-means by 12.72%, and 45.55%, respectively. In U AI, the proposed model outperforms GMC by 16.69%.
When Acc is considered, RTCMPN still performs robustly when compared with other baselines. RTCMPN can obtain the best performance in terms of Acc in all the testing datasets, except Biogrid, where it ranks the second best. RTCMPN may outperform the second best approaches by at least 10% in four datasets. In Ego−f acebook and Google+, RTCMPN outperforms SBM by 12.54% and 111.89%, respectively. In U AI, RTCMPN is better than SCI by 16.83%. In W iki, RTCMPN outperforms DANMF by 24.54%.
From the experimental results in terms of N M I and Acc, we can observe that RTCMPN is effective in network clustering. It is the novel model structure that makes the proposed approach outperform other baselines. Considering modeling the latent neighboring preference which is also aware of topology/feature inclinations of each vertex, RTCMPN is able to assign similar cluster membership to those vertices having analogous structure of latent local neighbors and preference in terms of topology and feature. More meaningful clusters can thereby be uncovered by the proposed model.

Model convergence test
In addition to derive the EM algorithm for updating the latent variables of RTCMPN, we also investigated the convergence speed of the proposed method on real network datasets. Specifically, we recorded the value of log-likelihood function for the first 300 iterations on all the six datasets. As depicted in Fig. 2, the value of log-likelihood converges to a stable value in finite iterations, which showcases the capability of the derived EM algorithm to guarantee the model convergence and attain the optimal clustering results efficiently.

Scalability comparison
To show the scalability of RTCMPN, we compared the computational time of RTCMPN with CESNA, which is a well known efficient model-based approach to network clustering. The optimization time used by RTCMPN   time used by CESNA in the corresponding datasets are 372, 19320, 12.250, 850, 342, and 4080 seconds, respectively. It can be seen that the efficiency of RTCMPN outperforms CESNA.

Case study on mutually preferred neighbors
To verify whether the proposed model can uncover clusters by considering the mentioned latent preference and dichotomous inclinations, we conducted a detailed analysis on the clusters discovered by RTCMPN and provide a concrete example. Figure 3 illustrates a pair of cluster members correctly detected by RTCMPN in Ego − f acebook dataset. Why they are correctly detected in the same cluster can be explained using the depicted latent information learned by RTCMPN. It is observed that the mutual neighboring preferences between vertex 58 and 2814 are both larger than 0.1, which is a relatively high value in view of the size of the dataset (N =4039). As the topology/feature inclinations of these two vertices are very similar, RTCMPN deduces they are very possible to be associated (mutually preferred) and consequently learns high neighboring preferences. The clustering performance of RTCMPN is thereby improved by assigning such mutually preferred vertices with similar cluster membership.

Conclusion
In this paper, we propose a novel probabilistic model for network clustering, dubbed Relational Thematic Clustering with Mutually Preferred Neighbors (RTCMPN). Different from previous approaches which mainly utilize network topology and vertex features to unfold clusters in the network, RTCMPN further learns the latent preferences indicating which vertices and their neighbors are more possible to be in the same cluster, according to the vertex-wise dichotomous inclinations w.r.t. topology and features. Such latent neighboring preferences are then used to guide the proposed model to assign more analogous cluster membership to those vertices having similar proximal preferences and topology/feature inclinations. More interpretable clusters can thereby be learned by the proposed model. Having been compared with a number of strong baselines on various types of networks, RTCMPN is found to be more effective in unfolding network clusters. In future, we will further improve the interpretability of RTCMPN via developing the fully Bayesian version of the model and enhance its efficiency by deriving stochastic learning algorithms for model inference.