# Clustering networks with textual edges by combining the Embedded Topic Model and the Stochastic Block model. Variational inference and derivation of a model selection criterion

Rémi Boutin, Pierre Latouche, Charles Bouveyron

► To cite this version:

Rémi Boutin, Pierre Latouche, Charles Bouveyron. Clustering networks with textual edges by combining the Embedded Topic Model and the Stochastic Block model. Variational inference and derivation of a model selection criterion. 53 èmes Journées de Statistique de la SFDS, Jun 2022, Lyon, France. hal-04910328

HAL Id: hal-04910328

https://hal.science/hal-04910328v1

Submitted on 4 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
CLUSTERING NETWORKS WITH TEXTUAL EDGES BY
COMBINING THE EMBEDDED TOPIC MODEL AND THE
STOCHASTIC BLOCK MODEL. VARIATIONAL INFERENCE
AND DERIVATION OF A MODEL SELECTION CRITERION.

Rémi Boutin¹ & Pierre Latouche¹ & Charles Bouveyron²

¹ Université de Paris, MAP 5, UMR 8145, Paris, France
remi.boutin@u-paris.fr pierre.latouche@maths.cnrs.fr

² Université Côte d'Azur, Inria, CNRS, Laboratoire J.A. Dieudonné, Maasai team
charles.bouveyron@univ-cotedazur.fr

**Résumé.** Les réseaux de communications (courriels, réseaux sociaux, objects connectés) sont de plus en plus présents autour de nous et leur analyse devient prépondérante pour le fonctionnement de notre modèle numérique. De nombreux réseaux de communication présentent des arêtes comportant du texte dont l'information n'est pas utilisée dans les méthodes classiques. Dans ce papier, nous proposons le ETSBM (embedded topic for the stochastic block model) pour détecter simultanément les partitions des nœuds et les thèmes présents dans les textes. Ce travail étend le SBM (stochastic block model) et le ETM (embedded topic model) grâce à un algorithme VBEM (variational-Bayes expectation-maximization) et une descente de gradient stochastique. Nous proposons également un critère de sélection de modèle. Notre méthodologie est évaluée sur des données simulées ainsi que sur des données réelles.

**Mots-clés.** embeddings, topic Models, clustering de nœuds, modèles génératifs, STBM, ETM, LDA, SBM.

**Abstract.** Communication networks (emails, social networks, IOT) are now ubiquitous and their analysis has become a strategic field to secure our numerical lives. Unfortunately, most of communication networks come with textual data on the edges which are not incorporated in classical model. In this paper, we introduce the embedded topics for the stochastic block model (ETSBM) in order to simultaneously perform clustering on the nodes while modelling the topics used between the different clusters. ETSBM extends both the stochastic block model and the embedded topic model. The main motivation of this work is to allow a simultaneous analysis of texts and node interactions. A variational-Bayes expectation-maximisation algorithm (VBEM) combined with a stochastic gradient descent (SGD) is used to perform inference. A model selection criterion is also derived. The methodology is evaluated on synthetic data and on a real world dataset.

**Keywords.** embeddings, topic models, graph clustering, generative models, STBM, ETM, LDA, SBM.
<figure><img src="image_2.png" /><figcaption>Figure 1: Graphical representation of the Embedded Topics for the Stochastic Block Model. The link between $\theta$ and $\delta$ is deterministic. In this figure, we give the dependency through $\theta$.</figcaption></figure>

# 1 Introduction and notations

The STBM model proposed in Bouveyron et al. (2016) aims at jointly analysing textual data and graph connections in order to perform simultaneously node clustering and topic modelling tasks for each detected cluster. The analysis of the textual data relies on word counts through LDA (Latent Dirichlet Allocation), see Blei et al. (2003) for more details. In LDA, the word “topic” refers to a distribution over the vocabulary. To overcome some of the limitations of LDA, e.g the bag-of-words representation of documents, ETM (Embedded Topic Model) has been introduced in Dieng et al. (2020). ETM makes use of a deep generative network that jointly learns word and topic representations in a vector space. It can also be used with pre-trained word embeddings, i.e vector representations of words, to incorporate semantic meaning of the words to improve the topic quality. We propose to use ETM instead of LDA within STBM to benefit from those advantages.

In the rest of this paper, we consider a graph with $M$ nodes, for which $A \in \mathbb{R}^{M \times M}$ is the binary adjacency matrix of the graph such that there are no self loop, i.e $A_{ii} = 0$ for any $i$. Moreover, for any $i, j \in \{1, \dots, M\}$ with $i \neq j$, $i$ is connected to $j$ if and only if $A_{ij}$ equals one. If so, they share a set of documents $W_{ij} := \{W_{ij}^{1}, \dots, W_{ij}^{D_{ij}}\}$ where $D_{ij}$ denotes the number of documents shared by $i$ and $j$ such that for any $d = 1, \dots, D_{ij}$, $W_{ij}^d$ is a collection of words with size $N_{ij}^d$, i.e $W_{ij}^d = \{w_{ij}^{d1}, \dots, w_{ij}^{dN_{ij}^d}\}$. $V$ denotes the vocabulary size and the $v$-th word of the vocabulary will either be represented with a one hot encoded vector or directly with the vocabulary index of the word $w = v$. The embeddings are denoted $\rho \in \mathbb{R}^{d \times V}$ with $d$ the dimension of the vector space and $\alpha_k$ refers to the vector representation of the topic $k$ in the same space for all $k \in \{1, \dots, K\}$, with $K$ the number of topics.
## 2 Generative model

This section presents our assumptions about the generation of the real data and are represented in Figure 1. The cluster memberships of the nodes are assumed to be independent and identically distributed following a multinomial distribution while the connections between the nodes are assumed to be independent and to only depend on the cluster of the nodes given each node’s cluster:

$$p(Y | \gamma) = \prod_{i=1}^{M} \prod_{q=1}^{Q} \gamma_{q}^{Y_{iq}}, \qquad p(A | \pi, Y) = \prod_{i \neq j}^{M} \prod_{q,r}^{Q} (\pi_{qr}^{A_{ij}} (1 - \pi_{qr})^{1-A_{ij}})^{Y_{iq} Y_{jr}}. \quad (1)$$

We also assume that $\gamma \sim \text{Dir}_Q(1, \dots, 1)$ and $\pi_{qr} \sim \text{Beta}(1, 1)$ for any $q, r$.

For any pair of clusters $(q, r)$, the prior on the topic proportions $\theta_{q,r}$ is a logistic normal distribution:

$$\delta_{qr} \sim \mathcal{N}(0_K, I_K), \qquad \theta_{qr} = \text{softmax}(\delta_{qr}).$$

with $\text{softmax}(\delta) = \left( \frac{e^{\delta_1}}{\sum_k^K e^{\delta_k}}, \dots, \frac{e^{\delta_K}}{\sum_k^K e^{\delta_k}} \right)$ for any $\delta \in \mathbb{R}^K$.

If two nodes $i, j$ are connected and in the clusters $q$ and $r$ respectively, the $n$-th word of the $d$-th document is assumed to be distributed according to a mixture of topics:

$$p(w_{ij}^{dn} | \theta_{qr}, Y_{iq}Y_{jr}A_{ij} = 1) = \sum_{k=1}^{K} \theta_{qrk} \text{softmax}(\rho^{\top}\alpha_k)|_{w_{ij}^{dn}}. \quad (2)$$

Finally, given each node’s cluster membership $Y_i$, marginalizing the topic proportions gives the following:

$$p(W | Y, A, \alpha, \rho) = \prod_{i \neq j}^{M} \left\{ \prod_{q,r}^{Q} \left( \int p(\delta_{qr}) \prod_{d=1}^{D_{ij}} \prod_{n=1}^{N_{ij}^d} p(w_{ij}^{dn} | \delta_{qr}, Y_{iq}Y_{jr}A_{ij} = 1) d\delta_{qr} \right)^{Y_{iq}Y_{jr}} \right\}^{A_{ij}}. \quad (3)$$

## 3 Inference

We aim at maximising $\log p(A, W | \alpha, \rho)$ with respect to the parameters $\alpha, \rho$. To evaluate it, it is necessary to marginalize over the set of parameters,

$$\log p(A, W | \alpha, \rho) = \log \left( \sum_Y \int_{\delta} \int_{\gamma} \int_{\pi} p(A, W, Y, \pi, \gamma, \delta | \alpha, \rho) d\pi d\delta d\gamma \right). \quad (4)$$
Unfortunately, the quantity in (4) is intractable since it requires computing the integral for all the $Q^M$ configurations of $Y$. Moreover, the integral with respect to $\delta$ is not tractable because of the softmax function. To overcome this, we use a variational-bayes expectation-maximization (VBEM) approach to keep this method scalable to large datasets.

$$ \log p(A, W | \alpha, \rho) = \mathcal{L}(R(\cdot)) + \mathrm{KL}(R(\cdot) || p(Y, \pi, \gamma, \delta | A, W)), $$

with

$$ \mathcal{L}(R(\cdot)) = \sum_{Y} \int_{\pi, \gamma, \theta} R(Y, \pi, \gamma, \delta) \log \frac{p(A, W, Y, \pi, \gamma, \delta | \alpha, \rho)}{R(Y, \pi, \gamma, \delta)} d\pi d\delta d\gamma. $$

To make $\mathcal{L}(R(\cdot))$ tractable, we use the mean-field assumption,

$$ R(Y, \pi, \gamma, \delta) = R(Y)R(\pi)R(\gamma)R(\delta). $$

We propose to use the same distributions as the one in the generative model. We use the amortized inference to avoid increasing the number of parameters linearly with the number of pairs of groups and to keep the training of the auto-encoder tractable, see Gershman and Goodman (2014) for more details.

$$ R_{\tau}(Y) = \prod_{i=1}^{M} \mathcal{M}_{Q}(Y_{i}; \tau_{i}), \quad R_{\tilde{\pi}_{qr1}, \tilde{\pi}_{qr2}}(\pi) = \mathcal{B}eta(\pi_{qr}; \tilde{\pi}_{qr1}, \tilde{\pi}_{qr2}), \qquad (5) $$

$$ R_{\tilde{\gamma}}(\gamma) = \prod_{q=1}^{Q} Dir(\gamma; \tilde{\gamma}), \quad R_{\mu, \sigma}(\delta) = \prod_{q,r}^{Q} \mathcal{N}(\delta_{qr}; \mu_{qr}^{\nu}, \sigma_{qr}^{\nu}), \qquad (6) $$

with $\mu_{qr} = f(\tilde{w}_{qr}; \nu, \nu_m)$ and $\sigma_{qr} = f(\tilde{w}_{qr}; \nu, \nu_v)$, typically a neural network, $\nu$ denotes some parameters of the neural network shared by the function encoding $\mu$ and $\sigma$ while $\nu_m$ and $\nu_v$ are parameters specific to each encoder. Finally, $\tilde{w}_{qr} = \sum_{i \neq j} \tau_{iq} \tau_{jr} A_{ij} W_{ij}$, are the expected documents under the approached posterior distribution, which simply is the variational distribution. Since $\tilde{w}_{qr}$ are constructed using $\tau = (\tau_i)_{1 \le i \le M}$, the parameters $\mu_{qr}^{\nu}$ and $\sigma_{qr}^{\nu}$ also depend on $\tau$. The Kullback-Leibler divergence between two Gaussian variables has a close form and is easy to compute. All the terms can be computed except for the expectation of $T_{ij}^{\theta_{qr}}$ that can be approximated using a Monte-Carlo estimator, by drawing $S$ samples for each pair $(q, r)$, such that:

$$ \epsilon^s \sim \mathcal{N}(0, I_K), \quad \delta_{qr}^s = \mu_{qr}^{\nu} + \sigma_{qr}^{\nu} \odot \epsilon^s, \quad \theta_{qr}^s = \mathrm{softmax}(\delta_{qr}^s). $$

## 3.1 Optimisation & Algorithm

We aim at maximising the ELBO with respect to the variational parameters $\tilde{\pi}, \tilde{\gamma}, \tau$ and $\eta$ and to the parameters $\rho$ and $\alpha$. Since $\tau$ lies on the simplex, the Lagrangian $\mathcal{L}$ of the
ELBO is given by:

$$ \mathcal{L}(\gamma, \kappa, \tau, \lambda) = \mathcal{L}(\gamma, \kappa, \tau) + \sum_{i=1}^{M} \lambda_i \left( \sum_{q=1}^{Q} \tau_{iq} - 1 \right) $$

On the one hand, setting the derivatives of the Lagrangian with respect to $\tilde{\pi}$, $\tilde{\gamma}$ to zero gives the classical updates of the variational Bayes SBM, depending only on $\tau$, see Latouche et al. (2012) for more details.

On the other hand, the optimisation of the ETM parameters is done by stochastic gradient descent based on Dieng et al. (2020). One should be careful about the fact that the meta-documents given to the encoder are based on $\tau$ and impact the ELBO also through the KL term which is very specific to our approach and allows regularization in the clustering task. Thus, contrary to existing variational auto-encoding strategy, the inputs of the encoder can here be optimized through $\tau$ and the allocations of nodes to clusters. In practice, we rely on the automatic differentiation technique to perform the optimization of the NLP term of the ELBO.

# 4 Conclusion and discussion

The embedded topics for the stochastic block model (ETSBM) introduced in this paper is well suited to perform clustering simultaneously on the nodes and edges and to sum up the textual edges content and the connections pattern. It can be used both on directed and undirected graphs and is suited for big datasets since it relies on a variational inference. The numerical experiments suggest the ELBO can be used as a criteria for selecting the number of cluster $Q$ thanks to the Bayesian framework used. The model has been tested on a real dataset which showed both usefulness and its capacity in capturing information and performing meaningful clustering. Further work may be directed in the study of theoretical foundation of the selection model criteria, in incorporating dynamic networks and finally in using out of vocabulary words.

**On going work** This section is under current investigation. We will conduct a set of simulations based on the ones in Bouveyron et al. (2016). An application will be carried out on a dataset of academic papers and a co-authors network to detect both groups of authors and underlying topics. We will also conduct simulation to validate the use of Bayesian priors as a regularization within the model to penalize the ELBO and to make it a good model selection criterion for the number of clusters $K$ in the network. The result will be presented at the conference if this paper is accepted.
References

Blei, D. M., Ng, A. Y., and Jordan, M. I. (2003). Latent dirichlet allocation. *the Journal of machine Learning research*, 3:993–1022.

Bouveyron, C., Latouche, P., and Zreik, R. (2016). The stochastic topic block model for the clustering of vertices in networks with textual edges. *Statistics and Computing*, 28(1):11–31.

Dieng, A. B., Ruiz, F. J., and Blei, D. M. (2020). Topic modeling in embedding spaces. *Transactions of the Association for Computational Linguistics*, 8:439–453.

Gershman, S. and Goodman, N. (2014). Amortized inference in probabilistic reasoning. In *Proceedings of the annual meeting of the cognitive science society*, volume 36.

Latouche, P., Birmele, E., and Ambroise, C. (2012). Variational bayesian inference and complexity control for stochastic block models. *Statistical Modelling*, 12(1):93–115.