---
abstract: '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.'
author:
- 'Tiantian He$^1$[^1]'
- Lu Bai$^1$
- |
    Yew-Soon Ong$^{1}$\
    $^1$School of Computer Science and Engineering, Nanyang Techonological University\
    {tiantian.he, bailu, phillipcline@example.org
bibliography:
- 'RTCMPN.bib'
title: Relational Thematic Clustering with Mutually Preferred Neighbors
---

=1

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 sample-sample relations, is thereby ideal for preserving illustrative information on the data samples and complex sample-sample 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 @he2019contextual, social recommendation @yang2013, biological module discovery @airoldi2008mixed, and topic modeling in scientific articles @chang2009. 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 model-based, 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 @clauset2004, 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 @blondel2008. Besides, modern machine learning techniques, including spectral analysis @shi2000 [@wang2019gmc], matrix factorization (MF) @yang2013 [@wang2016semantic; @ye2018deep; @xu2019gromov], and probabilistic modeling @chang2009 [@peng2015scalable; @bojchevski2018bayesian], 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 vertex-cluster 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 \[related-works\], the previous works related to the proposed model are investigated. In Section \[model\], 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 \[exp\]. 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. For example, Clauset-Newman-Moore algorithm @clauset2004, Stochastic block model (SBM) @airoldi2008mixed [@peng2015scalable], Deep autoencoder-like nonnegative matrix factorization (DANMF) @ye2018deep, Modularized nonnegative matrix factorization (M-NMF) @wang2017community, and Normalized cut (Ncut) @shi2000 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 @chang2009, Communities from edge structure and node attributes (CESNA) @yang2013, Semantic community identification (SCI) @wang2016semantic, Adaptive semantic community detection (ASCD) @qin2018adaptive, Contextual correlations preserving graph clustering @he2019contextual, Attributed Markov random filed model @he2019end, and Multi-view spectral clustering @kumar2011co [@wang2019gmc], 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.

= \[circle, draw, inner sep=2pt, text centered\] = \[rectangle, draw, minimum width=1.7cm, minimum height = 1.7cm\]

Relational thematic clustering with inclination aware neighbors {#model}
===============================================================

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, $\mid$E$\mid$ edges, $M$ vertex features, and $K$ ground-truth clusters, we use two binary matrices $\mathbf Y \in \{0,1\}^{N \times N}$ and $\mathbf {F} \in \{0,1\}^{M \times N}$ to represent whether two vertices are connected and whether a vertex has a corresponding feature, respectively. We denote $\mathbf Z \in R_{+}^{N \times N}$ and $\mathbf G \in R_{+}^{N \times 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 $\mathbf Y$ are denoted as $\mathbf Y_{ij}$, $\mathbf Y_{i\cdot}$, and $\mathbf Y_{j}$, respectively. To build the proposed model, we use $K$, $M$, and $N$ multinomial parameters $\mathbf V_{i\cdot}$, $\mathbf U_{k}$, and $\mathbf 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 $\mathbf X_{i\cdot}$ and binomial variables $\mathbf S_{i\cdot}$ to represent latent neighbor preference and dichotomous inclination of topology and features of vertex $i$.

The generative process {#structure}
----------------------

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. \[graphical-model\]. 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 $\mathbf V_{i\cdot}$, $\mathbf X_{i\cdot}$, and binomial parameters $\mathbf S_{i\cdot}$ as cluster preference, latent neighbor preference, and dichotomous inclinations;

-   For each cluster $k$, draw $M$ and $N$ dimensional multinomial parameters $\mathbf U_{k}$ and $\mathbf H_{k}$ as cluster theme and cluster-vertex proportion;

-   For each pair of vertices, draw $\mathbf X_{ij}$,$\mathbf S_{i}$,$\mathbf S_{j}$,$\mathbf Z_{ij}$,$\mathbf G_{ij}\!\sim\!Boltzmann(-\epsilon_{ij} |C)$, where $\epsilon_{ij} = -\mathbf X_{ij}(\mathbf S_{i1}\mathbf S_{j1} \mathbf Z_{ij}+\mathbf S_{i2}\mathbf S_{j2}\mathbf G_{ij})$; draw $\mathbf Y_{ij} \sim Poisson(\cdot|\sum_{k}\mathbf V_{ik}\mathbf V_{jk})$;

-   For each vertex $i$, draw $\mathbf F_{ji}\!\sim\! \lbrack\sum_{k}\mathbf V_{ik}\mathbf U_{jk}\rbrack^{\mathbf F_{ji}}$; draw $\mathbf V_{ik}, \sum_{l}\mathbf X_{il}\mathbf H_{lk}\sim\mathcal{N}(\mathbf V_{ik}-\sum_{l}\mathbf X_{il}\mathbf H_{lk}|0,\lambda_i)$;

where $\lambda_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 ($\mathbf X$), according to the adaptive dichotomous inclinations ($\mathbf S$) and corresponding observed similarities ($\mathbf Z$ and $\mathbf G$). Such neighbor preference is used to regularize the vertex-cluster 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 @nie2014clustering [@wang2019gmc; @wang2019parameter], as they are neither capable of modeling vertex-wise 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 \[structure\], the joint likelihood of the proposed model is: $$\label{jointlikeli}
\begin{aligned}
&p(\mathbf Y,\mathbf F,\mathbf Z,\mathbf G,\mathbf V,\mathbf U,\mathbf X,\mathbf H,\mathbf S|\lambda)=\\
&\prod_{ i \ne j} p(\mathbf Y_{ij}|\sum_{k}\mathbf V_{ik}\mathbf V_{jk})\cdot\prod_{i, k} \!p(\mathbf V_{ik},\sum_{l}\mathbf X_{il}\mathbf H_{lk}|\lambda_i)\\
&\cdot\!\prod_{i, j} \!p(\mathbf F_{ji}|\sum_{k}\mathbf V_{ik}\mathbf U_{jk})\!\cdot\!\prod_{ i \ne j} \!p(\mathbf X_{ij},\mathbf S_{i},\mathbf S_{j}, \mathbf Z_{ij}, \mathbf G_{ij}).\\
\end{aligned}$$ Taking the logarithm of the joint likelihood and substituting the aggregation operators with corresponding matrix operators, we have: $$\label{loglikeli}
\begin{aligned}
&L(\mathbf Y,\mathbf F,\mathbf Z, \mathbf G, \mathbf V,\mathbf U,\mathbf X,\mathbf H,\mathbf S|\lambda) =K\sum_{i}\!\log\sqrt{\lambda_i}\\
&-\!\sum_{i,k}\frac{\lambda_i}{2}\lbrack\mathbf V_{ik}-(\mathbf X\mathbf H)_{ik}\rbrack^2\!+\!\sum_{i,j}\mathbf F_{ji}\!\log(\mathbf U\mathbf V^T)_{ji}\\
&\sum_{i \ne j}\!\lbrack\mathbf Y_{ij}\!\log(\mathbf V\mathbf V^T)_{ij}\!-\!(\mathbf V\mathbf V^T)_{ij}\rbrack-\log A\\
&+ \sum_{i \ne j}\lbrack\mathbf X_{ij}(\mathbf S_{i1}\mathbf S_{j1}\mathbf Z_{ij}+\mathbf S_{i2}\mathbf S_{j2}\mathbf G_{ij})\rbrack+const,
\end{aligned}$$ where $A$ is the normalization term for Boltzmann distribution, which is $\sum_{i\ne j}\exp\{-\epsilon_{ij}\}$, and $const$ contains the terms that are irrelevant to all the latent variables. Based on Eq. (\[loglikeli\]), 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 vertex-cluster preferences which we expect RTCMPN to learn can be achieved when Eq. (\[loglikeli\]) is maximized.

Learning RTCMPN
---------------

As Eq. (\[loglikeli\]) 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 $\mathbf V$ and $\mathbf 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 @dempster1977. 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. (\[loglikeli\]) in E-step, we use the following well known property of the concavity of logarithmic functions: $$\begin{aligned}
&\log(\sum_{k}\!x_k)\!\ge\!\sum_{k}a_k\log(\frac{x_k}{a_k}),\text{if }\sum_{k}a_k \!= \!1, x_k>0.
\end{aligned}$$ Based on it, we may derive the following auxiliary function as the lower bound of the joint likelihood of RTCMPN (Eq. (\[loglikeli\])): $$\label{lowerbound}
\begin{aligned}
&L(\mathbf Y,\mathbf F,\mathbf Z, \mathbf G, \mathbf V,\mathbf U,\mathbf X,\mathbf H,\mathbf S|\lambda)\ge Q(\theta, \phi)=\\
&\sum_{i\ne j}\lbrack\mathbf Y_{ij}\sum_{k}\theta_{ij,k}\log(\frac{\mathbf V_{ik}\mathbf V_{jk}}{\theta_{ij,k}})-\!(\mathbf V\mathbf V^T)_{ij}\rbrack\\
&+\sum_{i,j}\lbrack\mathbf F_{ji}\sum_{k}\phi_{ji,k}\log(\frac{\mathbf V_{ik}\mathbf U_{jk}}{\phi_{ji,k}})\rbrack+\sum_{i}K\log\sqrt{\lambda_i}\\
&-\sum_{i,k}\!\frac{\lambda_i}{2}\lbrack\mathbf V_{ik}^2-2(\mathbf {XH})_{ik}\mathbf V_{ik}+(\mathbf {XH})^2_{ik}\rbrack-\log A\\
&+\sum_{i\ne j}\mathbf {X}_{ij}(\mathbf {S}_{i1}\mathbf {S}_{j1}\mathbf {Z}_{ij}+\mathbf {S}_{i2}\mathbf {S}_{j2}\mathbf {G}_{ij})+const,\\
&\theta_{ij,k} = \frac{\mathbf V_{ik}\mathbf V_{jk}}{\sum_{k}\mathbf V_{ik}\mathbf V_{jk}},\phi_{ji,k}=\frac{\mathbf V_{ik}\mathbf U_{jk}}{\sum_{k}\mathbf V_{ik}\mathbf U_{jk}}.\\
\end{aligned}$$ In E-step, we set the plug-in variables, including $\theta_{ij,k}$ and $\phi_{ji,k}$ as Eq. (\[lowerbound\]) 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. (\[loglikeli\]) via pushing-up the lower bound $Q(\theta, \phi)$.

### M-step

In M-step, we maximize the lower bound $Q(\theta, \phi)$, which is shown in Eq. (\[lowerbound\]), by simply performing point estimation. To optimize $Q$ relevant to latent variable $\mathbf V_{ik}$, we construct the following Lagrangian function: $$\label{lagrange}
\mathcal L(\mathbf V_{ik},\nu) = Q(\theta, \phi) - \nu\lbrack\sum_{k}\mathbf V_{ik}-1\rbrack,$$ where $\nu$ denotes the Lagrange multiplier in terms of the unity constraint of $\mathbf V_{i\cdot}$. Letting the partial derivative w.r.t. $\mathbf V_{ik}$ of Eq. (\[lagrange\]) be equal to zero and substituting $\nu$, we may derive the updating rule for $\mathbf V_{ik}$: $$\label{max-v}
\begin{aligned}
&\mathbf V_{ik} =\frac{\Delta_{ik}\sum_k\frac{\mathbf V_{ik}}{\Lambda_{ik}}+\mathbf V_{ik}}{\Lambda_{ik}\sum_k\frac{\mathbf V_{ik}}{\Lambda_{ik}}+\sum_k\frac{\mathbf V_{ik}\Delta_{ik}}{\Lambda_{ik}}},\\
&\Delta_{ik} \!=\! 2\sum_{j}\mathbf Y_{ij}\theta_{ij,k}+\sum_{j}\mathbf F_{ji}\phi_{ji,k}+\lambda_i(\mathbf{XH})_{ik}\mathbf V_{ik},\\
&\Lambda_{ik} = 2\sum_{j}\mathbf V_{jk}+\lambda_i\mathbf V_{ik}.\\
\end{aligned}$$ Similarly, we may obtain the updating rules for $\mathbf U_{jk}$, $\mathbf X_{ij}$, $\mathbf H_{jk}$, and $\mathbf S_{id}$ for $d\in\{1,2\}$. The rule for updating $\mathbf U_{jk}$ is: $$\label{max-u}
\begin{aligned}
\mathbf U_{jk} = \frac{\sum_{i}\mathbf F_{ji}\phi_{ji,k}}{\sum_{i,j}\mathbf F_{ji}\phi_{ji,k}}.
\end{aligned}$$ The updating rule for $\mathbf X_{ij}$ is: $$\label{max-x}
\begin{aligned}
&\mathbf X_{ij} =\frac{\Delta_{ij}\sum_j\frac{\mathbf X_{ij}}{\Lambda_{ij}}+\mathbf X_{ij}}{\Lambda_{ik}\sum_j\frac{\mathbf X_{ij}}{\Lambda_{ij}}+\sum_j\frac{\mathbf X_{ij}\Delta_{ij}}{\Lambda_{ij}}},\\
&\Delta_{ij}\! =\! \lbrack\!\lambda_i(\!\mathbf {V}\!\mathbf {H}^T\!)_{ij}\!+\!\eta_{ij}\!\rbrack\mathbf X_{ij}\!,\!\eta_{ij}\! =\! \mathbf S_{i1}\!\mathbf S_{j1}\!\mathbf Z_{ij}\!+\!\mathbf S_{i2}\!\mathbf S_{j2}\!\mathbf G_{ij},\\
&\Lambda_{ij} \!=\! \lambda_i(\mathbf {X}\mathbf {HH}^T)_{ij}\!+\!\eta_{ij}\frac{\exp\{-\epsilon_{ij}\}}{A}.\\
\end{aligned}$$ The updating rule for $\mathbf H_{jk}$ is: $$\label{max-h}
\begin{aligned}
&\mathbf H_{jk} =\frac{\mathbf H_{jk}(\mathbf {XV})_{jk}\sum_j\frac{\mathbf H_{jk}}{(\mathbf {X}^T\mathbf {XH})_{jk}}+\mathbf H_{jk}}{(\mathbf {X}^T\mathbf {XH})_{jk}\sum_j\frac{\mathbf H_{jk}}{(\mathbf {X}^T\mathbf {XH})_{jk}}+\sum_j\frac{\mathbf H_{jk}(\mathbf {XV})_{jk}}{(\mathbf {X}^T\mathbf {XH})_{jk}}}.\\
\end{aligned}$$ The updating rule for $\mathbf S_{id}$ is: $$\label{max-s}
\begin{aligned}
&\mathbf S_{i1} \!=\!\frac{\mathbf S_{i1}(\frac{\mathbf S_{i1}}{(\Psi\mathbf S)_{i1}}+\frac{\mathbf S_{i2}}{(\Phi\mathbf S)_{i2}})(\Delta\mathbf S)_{i1}+\mathbf S_{i1}}{\!(\!\Psi\mathbf S\!)_{i1}\!(\frac{\mathbf S_{i1}}{\!(\Psi\mathbf S)_{i1}}\!+\!\frac{\mathbf S_{i2}}{\!(\Phi\mathbf S)_{i2}})\!+\!(\frac{\mathbf S_{i1}\!(\Delta\mathbf S)_{i1}}{\!(\Psi\mathbf S)_{i1}}\!+\!\frac{\mathbf S_{i2}\!(\!\Lambda\mathbf S\!)_{i2}}{\!(\Phi\mathbf S)_{i2}})},\\
&\mathbf S_{i2}\!=\!\frac{\mathbf S_{i2}(\frac{\mathbf S_{i1}}{(\Psi\mathbf S)_{i1}}+\frac{\mathbf S_{i2}}{(\Phi\mathbf S)_{i2}})(\Lambda\mathbf S)_{i2}+\mathbf S_{i2}}{\!(\Phi\mathbf S)_{i2}\!(\frac{\mathbf S_{i1}}{\!(\Psi\mathbf S)_{i1}}\!+\!\frac{\mathbf S_{i2}}{\!(\!\Phi\mathbf S)_{i2}}\!)\!+\!(\frac{\mathbf S_{i1}\!(\Delta\mathbf S)_{i1}}{\!(\Psi\mathbf S)_{i1}}\!+\!\frac{\mathbf S_{i2}\!(\Lambda\mathbf S)_{i2}}{\!(\Phi\mathbf S)_{i2}})}\!,\\
&\!\Delta_{ij} = \mathbf{X}_{ij}\mathbf{Z}_{ij},\Lambda_{ij} = \mathbf{X}_{ij}\mathbf{G}_{ij},\\
&\Psi_{ij}\! =\! \mathbf{X}_{ij}\mathbf{Z}_{ij}\frac{\exp\{-\epsilon_{ij}\}}{A}, \Phi_{ij}\! =\! \mathbf{X}_{ij}\mathbf{G}_{ij}\frac{\exp\{-\epsilon_{ij}\}}{A}.
\end{aligned}$$ Finally, $\lambda_i$ can be updated through performing MLE: $$\label{max-lambda}
\begin{aligned}
\lambda_i = \frac{K}{\sum_{k}\lbrack\mathbf V_{ik}-(\mathbf {XH})_{ik}\rbrack^2}.
\end{aligned}$$ 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.

\[1\]\
Initialize $\mathbf U$, $\mathbf V$, $\mathbf X$, $\mathbf S$, $\mathbf H$, $\lambda_i$;\
$t \leftarrow 0$;\
$t \leftarrow t+1$;\
E-Step: Set lower bound of Eq. (\[loglikeli\]) by Eq. (\[lowerbound\]); M-Step: Maximize the lower bound via: Updating $\mathbf V_{ik}$, $\mathbf U_{jk}$, $\mathbf X_{ij}$, $\mathbf H_{jk}$, $\mathbf S_{id}$, and $\lambda_{i}$ by Eqs. (\[max-v\])-(\[max-lambda\]);\
Compute Log likelihood $L^{(t)}$ by Eq. (\[loglikeli\]);\
break;\
Identify cluster label for each vertex using $\mathbf V$.\
\[RTCMPN-learning\]

Complexity analysis
-------------------

Based on the E-step and M-step shown in Eq. (\[lowerbound\]), and Eqs. (\[max-v\])-(\[max-lambda\]), the complexity of the proposed model can be approximately analyzed as follows. In E-step, setting lower-bounder for $\mathbf V_{ik}$, and $\mathbf U_{jk}$ follows the order of $O(K)$. In M-step, updating $\mathbf V_{ik}$ and $\mathbf U_{jk}$ follows the order of $O(3N+M)$, and $O(2N)$, respectively. For $\mathbf X_{ij}$, RTCMPN considers only those connected vertices to improve the computational efficiency. Thus, updating $\mathbf X_{ij}$, $\mathbf H_{jk}$, $\mathbf S_{id}$, and $\mathbf \lambda_{i}$ follows the order of $O((e+2)K)$, $O((N+2)e)$, $O(4e)$, and $O((e+1)K)$, where $e$ represents the average vertex degree.

Experimental analysis {#exp}
=====================

In this section, we conduct a series of experiments on real-world datasets, including social network, document network, and biological network to validate the effectiveness of RTCMPN against state-of-the-art methods.

Experimental setup
------------------

### Baselines for comparison

Ten approaches are selected as baselines, which can be categorized into three classes. Ncut @shi2000, SBM @peng2015scalable, M-NMF @wang2017community, and DANMF @ye2018deep are four prevalent methods utilizing network topology to uncover clusters. $k$-means @mackay2003information is an effective vertex-feature-based approach to network clustering. MVSC @kumar2011co, CESNA @yang2013, SCI @wang2016semantic, ASCD @qin2018adaptive, and GMC @wang2019gmc 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-facebook$ (Ego) @leskovec2012learning and $Google+$ (Gplus) @mcauley2014discovering are two social networks whose vertices and edges respectively represent the social networking users and their social relationships. $Washington$ (Wash) @lu2003, $UAI$, and $Wiki$ @lu2003 are three widely used document networks, whose vertices and edges represent the documents, and the citations/hyperlinks between pairwise documents, respectively. $Biogrid$ @stark2006biogrid is a biological network used to describe the interactions between proteins in $Saccharomyces$ $cerevisiae$. The statistics of these testing datasets are summarized in Table \[dataset\], 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 ($NMI$) @he2018 and the Accuracy ($Acc$) @he2019end, are used in our experiments to evaluate the performance of different approaches. According to their definitions, larger values of $NMI$ and $Acc$ indicate a better matching between the detected clusters and the ground-truth.

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 $NMI$ and $Acc$) of all algorithms are summarized in Table \[performance\].

When the detected clusters are evaluated by $NMI$, 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-facebook$ dataset, RTCMPN performs better than SBM by 8.36%. In $Google+$, RTCMPN outperforms DANMF by 54.58%. In $Washington$, and $Wiki$, RTCMPN is better than $k$-means by 12.72%, and 45.55%, respectively. In $UAI$, 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-facebook$ and $Google+$, RTCMPN outperforms SBM by 12.54% and 111.89%, respectively. In $UAI$, RTCMPN is better than SCI by 16.83%. In $Wiki$, RTCMPN outperforms DANMF by 24.54%. From the experimental results in terms of $NMI$ 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 in testing datasets<span data-label="conv"></span>](convergence-6.jpg){width="\linewidth"}

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. \[conv\], 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.

= \[circle, draw, text centered\] = \[rectangle, draw\] =\[font=\]

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 in datasets $Ego-facebook$, $Google+$, $Washington$, $UAI$, $Wiki$, and $Biogrid$ are 246.43, 12756.90, 1.95, 212.87, 131.89, and 585.99 seconds, respectively. While, the optimization 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 \[neighbor\] illustrates a pair of cluster members correctly detected by RTCMPN in $Ego-facebook$ 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 {#conclusion .unnumbered}
==========

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.

[^1]: Contact Author

{'source': 'arXiv_out/2001'}