{'fraction_non_alphanumeric': 0.03270629026832613, 'fraction_numerical': 0.010013713871710612, 'mean_word_length': 4.588201272411799, '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': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Embedded Topics in the Stochastic Block Model

Communication networks such as emails or social networks are now ubiquitous and their analysis has become a strategic field. In many applications, the goal is to automatically extract relevant information by looking at the nodes and their connections. Unfortunately, most of the existing methods focus on analysing the presence or absence of edges and textual data is often discarded. However, all communication networks actually come with textual data on the edges. In order to take into account this specificity, we consider in this paper networks for which two nodes are linked if and only if they share textual data. We introduce a deep latent variable model allowing embedded topics to be handled called ETSBM to simultaneously perform clustering on the nodes while modelling the topics used between the different clusters. ETSBM extends both the stochastic block model (SBM) and the embedded topic model (ETM) which are core models for studying networks and corpora, respectively. The inference is done using a variational-Bayes expectation-maximisation algorithm combined with a stochastic gradient descent. The methodology is evaluated on synthetic data and on a real world dataset.


Introduction
Many real life interactions induce the exchange of texts, as in co-authorship networks, social networks or emails for instance. Since the storage capacity keeps increasing, networks with textual data on the edges become even more frequent. In order to make such networks, called communication networks, intelligible to humans, it is of great interest to gather information about the texts exchanged between the nodes and to summarise the connectivity structure. While those two questions have been studied independently, the work we propose aims at bridging the gap between the two by modelling the joint distribution of texts and edges. Indeed, this work aims at simultaneously modelling the connectivity of the nodes and the topics present in the exchanged texts to find meaningful clusters of nodes. To the best of our knowledge, the interest on making the two disciplines of topic modelling, when texts are present on the edges, and model-based graph clustering meets is recent and the methods that have been proposed only rely on the frequency of word within the documents without incorporating semantic meaning. In this paper, we propose to take advantage of pre-trained word embeddings in the topic-model as presented in Dieng et al. (2020) in order to incorporate semantic meaning of the words and to obtain topic-meaningful clusters. Figure 1, illustrates the necessity to combine graph clustering and topic modelling in order to distinguish all four clusters and to obtain more meaningful topics for each cluster.

Graph obtained by SBM algorithm
Graph obtained by SBM and ETM algorithms Graph obtained by ETSBM algorithm Figure 1: Comparison of results on a simulated network with SBM on the left, SBM and ETM in the middle and ETSBM on the right. The colours of the nodes and edges indicate the cluster assignment and the major topic used in the corresponding document respectively. Note that SBM alone does not provide edge information. Thus, the left network only has a single edge colour. On the left hand side, SBM clustering results uncover 3 clusters. In the middle, ETM edge information is added to the network through the 3 edge colours green, grey and blue. On the right hand side, ETSBM clustering results uncover 4 clusters. The cluster coloured in green, in the middle of the figure, is split into two cluster on the right hand side, the green one and the red one, each discussing of a different topic, the blue and grey topic respectively.

Related work
Both the topic modelling methods and the graph clustering techniques have first emerged as deterministic optimisation problems to progressively incorporate uncertainty which led to many developments in the statistical literature. The next part provides a brief summary of the advancements in those domains.

Probabilistic models for topic modelling
The statistical analysis of topics has emerged in the late 90s with Papadimitriou et al. (1998), developing statistical results for the latent semantic indexing (LSI), first proposed by Deerwester et al. (1990). LSI relies on a spectral analysis of the "term frequencyinverse document frequency" and successfully captures synonymy between words. To overcome the lack of probabilistic foundations of LSI, Hofmann (1999) introduced the probabilistic latent semantic index (pLSI) which models each word distribution as a mixture model such that each mixture component corresponds to a "topic". The topic membership of each word is modelled by a multinomial random variable in pLSI. Even though the topic membership of the words depends on the document, a major drawback of this model is the absence of model at the the document level. This was overcome by Blei et al. (2003) with the latent Dirichlet allocation (LDA) which for each document uses a Dirichlet random variable to model the proportion of each topic. However, the Dirichlet distribution makes the topics almost uncorrelated and does not directly model correlation. Blei & Lafferty (2006) then proposed to use a normal-logistic prior instead of a Dirichlet prior on the topic proportion to directly model the correlations. All these models require to derive the equations for any new generative model. In Srivastava & Sutton (2017), they bridged the gap between topic modelling and autoencoders, taking full advantage of gradient descent for those models. Nevertheless, all the former approaches do not incorporate semantic meaning to the words. Indeed, since the model is only based on the document term-frequency matrix, they loose the information provided by the order of the words. In the embedded topic model (ETM), Dieng et al. (2020) used the strength of word embeddings, such as the continuous bag of words (CBOW) or skipgram (Mikolov et al., 2013) as a part of the decoder of a variational autoencoder (VAE). The topics are also embedded into the same vector space which allows to easily measure similarities between words and topics. The optimisation is done using gradient descent, as proposed in Rezende et al. (2014) or Kingma & Welling (2014). For a review of the former methods relying exclusively on the document term frequency matrix, the reader may refer to Vayansky & Kumar (2020).

Probabilistic models for graph analysis
Statistical network analysis first started with random graph theory, initiated by Erdos et al. (1960). They studied probabilistic properties of graphs with binary connections, and a unique probability for any connection to exist. However, real life datasets do not show such regularity. Therefore, more complex and realistic graph structures have been considered. Here, a structure designates a partition of the nodes such that nodes in a cluster present a homogeneous connectivity pattern. For example, a community is a group of nodes highly connected one to another but with few connections to the rest of the graph. If the graph is only composed of communities, reordering the adjacency matrix by group would output a block matrix. Another direction emerged with Fienberg & Wasserman (1981) who first introduced a probabilistic model that assumes that the probability for two nodes to be connected only depends on the group to which they belong to and applied it to Sampson's monastery dataset (Sampson, 1969). Introducing a latent representation of the nodes then became popular thanks to the latent position cluster model (Handcock et al., 2007) or the stochastic block model (SBM) (Wang & Wong, 1987;Nowicki & Snijders, 2001). Many extensions have been developed to incorporate valued edges, as in Mariadassou et al. (2010), as well as categorical edges in Jernite et al. (2014) or to add prior information in Zanghi et al. (2010). Some developments also focused on looking for overlapping clusters (Airoldi et al., 2008;Latouche et al., 2011) as well as dynamic networks (Matias & Miele, 2017;Zreik et al., 2017;Corneli et al., 2016). The inference of SBM-based model is often done either using Markov chain monte carlo (MCMC), variational expectation maximisation (VEM) as in Daudin et al. (2008) or variational Bayes expectation maximisation (VBEM) as in Latouche et al. (2012). The classification can either be deduced from the latent variable distribution or be incorporated in the optimisation strategy with a hard clustering, for instance using the classification variational expectation maximisation (CVEM) algorithm (Bouveyron et al., 2018). The choice of the number of cluster K can either be done through a model selection criterion (Daudin et al., 2008;Latouche et al., 2012), through a greedy search (Côme & Latouche, 2015) or through a non parametric schemes (Kemp et al., 2006).
Fore more insights about SBM developments, see Lee & Wilkinson (2019). For reviews on statistical network modelling, we also relate to Goldenberg et al. (2010) and Matias & Robin (2014).

Probabilistic models for the joint analysis of texts and networks
The rise of data combining networks with texts, such as emails, social networks or co-authors articles led to developing methods using both the network and the textual information. In that regard, Zhou et al. (2006) proposed the community-user topic model Unfortunately, those models only rely on word counts and cannot use the position of words within a sentence or any form of context information.
Our contribution. This paper aims at bridging the gap between network analysis and topic modelling by performing a simultaneous clustering of nodes and edges. It distinguishes from former method by being able to learn a representation of topics using either the occurrence of word as before or incorporating a pre-trained representation of the vocabulary. The former allows to incorporate semantic meaning in our model-based clustering algorithm. To the best of our knowledge, it is the first strategy for modelbased clustering that can perform both nodes and edges clustering simultaneously while incorporating semantic meaning in the analysis.
Organisation of the paper. The embedded topics for the stochastic block model (ETSBM) is presented in Section 3. The inference and the model selection are presented in Section 4. Eventually, the model is evaluated against state of the art algorithms on synthetic data and we present results for a real word example build from tweets during the last French presidential election in Sections 5 and 6, respectively. Section 7 presents some concluding remarks and further work.

Background and notations
In this work, we focus on data represented by a directed graph G = {V, E}, such that Notice that all the present work can be extended to undirected networks using W ij = W ji for all pairs (i, j) such that A ij = A ji = 1. The directed case is more adequate to messages sent from i to j while the undirected case is better suited for co-authorships networks for instance.
The notation M d×p (F) will be used to denote the matrix space with matrix of dimension d × p and coefficients in F while the notation M d (N, ω) will be used to denote the multinomial distribution with parameters N ∈ N and ω ∈ ∆ d−1 where

Modelling the interactions
In this work, we assume that each node belongs to a single cluster. Moreover, we assume that the connexion probability between two nodes only depends on the cluster memberships. Indeed, let Y i denotes the cluster membership of node i for any i ∈ {1, . . . , M }.
All Y i are assumed to follow a multinomial distribution and to be independent and identically distributed (i.i.d ), given the cluster proportions γ ∈ ∆ Q−1 , lying in the simplex Thus, each node i is associated with cluster q with probability γ q . Then, we define the cluster membership matrix Y by stacking the node cluster membership vectors Besides, the connections between nodes are supposed to be independent given their cluster memberships. Moreover, if nodes i and j are respectively in clusters q and r, an edge is assumed to be present with probability π qr , where B(µ) denotes the Bernoulli distribution with probability µ. Thus, given the cluster memberships of the nodes Y and the probability matrix π, the probability of all node connections is given by Eventually, the joint-probability of the adjacency matrix A, and the cluster memberships vector Y , is obtained by multiplying Equations (1) and (3), Combining Equations (1), (3), and (4), we retrieve the SBM distribution (Daudin et al., 2008).

Modelling the texts
Our approach extends ETM to capture information of groups of texts. Essentially, texts are assumed to be generated according to a mixture of topics with latent topic vectors only depending on node clusters. More precisely, a text sent from node i in cluster q to node j in cluster r is assumed to have a logistic-normal topic proportion vector θ qr = (θ qr1 , . . . , θ qrK ) ∈ ∆ K−1 , with the number of topics K fixed beforehand.
It is obtained by applying the softmax function to a Gaussian random vector δ qr , In the rest of this paper, the notation θ = (θ qr ) 1≤q,r≤Q is used to refer to the topic proportions while δ = (δ qr ) 1≤q,r≤Q will refer to the sampling of the random variable. If two nodes i and j are connected and if they are respectively in cluster q and r, the words in document W ij are assumed to be i.i.d. Indeed, the n-th word of the d-th documents is assumed to be distributed according a mixture of topics conditionally on the node clusters, where the matrix β = (β 1 · · · β K ) ∈ M K×V (R) corresponds to the distribution over the vocabulary for each topic such that β k = softmax ρ α k for any k ∈ {1, . . . , K}.
The matrix ρ ∈ M L×V (R) corresponds to the matrix of the vocabulary embedded into an L-dimensional vector space, and α = (α 1 · · · α K ) ∈ M L×K (R) the matrix of topics represented into the same vector space.
Therefore, the probability of texts can be computed as follow: The number of time the word v of the dictionary is used in texts sent from cluster q to clus- Hereafter, W qr = (W 1 qr , . . . , W V qr ) ∈ N V shall be designated as meta-document (q, r). Moreover, we shall use the bag of words notations such that for any connected pair of nodes ij represents the total count of word v for all documents sent from i to j. The model is represented in Figure 2.

Distribution of the model and links with SBM and ETM.
Given a cluster configuration Y , the joint probability of the model is obtained using Equations (3) and (6) At this point, we emphasise that meta-documents between pairs of clusters of nodes are constructed using the cluster memberships Y and the node connections A. Assuming that the cluster membership Y is available as well as all the network information holded by π and γ, the model we propose would simply correspond to ETM applied on the meta-documents (W qr ) 1≤q,r,≤Q , computed with the available Y .
On the other hand, if no texts are exchanged between nodes or the texts are not available, the distribution would reduce to the second term of Equation 7. In that case, the conditional distribution of a standard SBM (Daudin et al., 2006) is recovered. It is also worth noticing that if a Dirichlet prior is assumed on the topic proportion instead of a logistic-normal, and no factorisation in a embedded latent space is considered, the model corresponds to STBM. By construction, ETSBM generalises SBM and ETM to incorporate both textual data and network information.

Inference
This section presents the Bayesian framework considered for inference. It also describes the variational-bayes EM algorithm used to maximise the integrated joint likelihood.

Bayesian framework for the graph modelling part
First, a Dirichlet distribution is assumed as a prior distribution on the proportions γ of nodes in each cluster, where γ 0 is set to (1, . . . , 1) ∈ R Q , which corresponds to a uniform prior on the simplex.
Moreover, each coefficient of the probability matrix π ∈ M Q×Q (R), is assumed to be sampled from from a Beta distribution, such that for any pair (q, r) ∈ {1, . . . , Q} 2 , In particular, a and b are set to 1. Thus, the Beta prior corresponds to a Uniform distribution between 0 and 1.

Variational inference
Eventually, the integrated joint log-likelihood is given by: Unfortunately, this quantity is intractable since it requires computing it for the Q M configurations of Y , which is naturally computationally too demanding. Moreover, the integral with respect to δ is not tractable either because of the softmax function. Thus, it cannot be optimised directly. However, it is possible to overcome this issue using a variational-bayes expectation-maximisation algorithm (VBEM) Attias (1999). This comes handy as it makes the inference scalable to large datasets.
Proposition 4.1. Denoting R(·), a distribution on Y, π, γ and δ, the integrated joint log-likelihood can be decomposed as follow: Proof. The proof is provided in Appendix A.
To make L (R(·); α, ρ) tractable, we use the following mean-field assumption : Following the optimality results of Latouche et al. (2012), we impose the following vari-ational distributions: Beta(π qr ;π qr1 ,π qr2 ), Each vector τ i is of size Q and encodes the (approximate) posterior probabilities for node i to be in each cluster. Given τ = (τ i ) i , the set of posterior cluster membership probabilities, for any pair (q, r) the corresponding expected meta-document can be computed By construction, the v-th element of vectorW qr is the expected pseudo count of word v for all documents sent from nodes in cluster q to nodes in cluster r. Finally, the variational distribution on latent topic proportions is assumed to be: with (µ qr (τ, ν), σ qr (τ, ν)) = f (W norm qr (τ ); ν) the output of a parametric function, typically a (deep) neural network, with parameters denoted ν. Hereafter, the ETM encoder will be used as the function f parametrised by ν. The normalised expected meta- qr (τ ) ∈ R V are then given to the encoder which outputs the mean and variance vectors (µ qr (τ, ν), σ qr (τ, ν)) of the posterior distribution. Our inference strategy is inspired by Dieng et al. (2020) and finds its roots in the original work of Kingma & Welling (2014) for classical data. However, as we shall see, a critical property of our methodology is that the (approximate) posterior allocation probabilities τ will change through the updates and so are the inputs of the encoder.
In all experiments we carried out, we used a 3-layer architecture with 800 units for the hidden layers, as originally proposed in Dieng et al. (2020). In order not to increase the number of parameters ν linearly with the number of pairs of groups, amortised inference is used as advocated in Gershman & Goodman (2014) or Kingma & Welling (2014).
Proof. The proof and the exact value of the ELBO is detailed in Appendix A

Optimisation and Algorithm
We now aim at maximising the ELBO with respect to the variational parameters π,γ, τ and ν and to the parameters ρ and α. On the one hand, following Latouche et al.
(2012), the variational parametersπ andγ only depend on τ and are updated as follow: On the other hand, the optimisation of the ETM parameters is done by stochastic gradient descent based on Dieng et al. (2020). Once both parts are done, we only need to update τ using the already up-to-date parameters. To do so, we switch from τ lying on the simplex ∆ Q−1 to the unconstrained space R Q−1 using for any i ∈ V and q ∈ {1, . . . , Q−1}: We then use auto differentiation for the optimisation algorithm with respect to ξ. It is worth emphasising that the ELBO is optimised over the whole set of allocation probability vectors τ = (τ i ) i contrary to STBM which looks for a hard allocation of nodes to clusters, one allocation being optimised at a time, all the others being fixed. Moreover, by optimising the entry of the encoder through τ , thus looking for an optimal allocation of documents to pairs of clusters, the moves in τ aim at uncovering the optimal direction in the posterior distribution in (θ qr ) qr maximising the ELBO. In that regard, ETSBM has links with the quasi branching bound algorithm of Jouvin et al. (2021) for document clustering.

Model selection
Finally, the selection of the number of cluster Q is performed using the ELBO. It is useful to remind that the aim of the model is to select the number of clusters providing the more meaning. Therefore, relying on Latouche et al. (2012), we take advantage of the Bayesian framework that automatically penalises the complexity of the model with respect to Q. The best number of cluster Q is then selected by estimating the parameters for models with different number of cluster Q and keeping the one with the highest ELBO.
Our experiment Section 2 confirms that this procedure provides a relevant model selection criterion. In this paper, the number of topics K is not selected. Indeed, we choose to keep a high K as advocated in Dieng et al. (2020). In practice, once the inference of the topics is done, a classical approach consists in focusing the interpretation on the results associated with the most frequent topics. As we shall see, in the experiment section, provided that the value of K chosen is large enough, the proposed procedure provides an accurate estimate of Q.

Numerical experiments
In this section, a series of experiments is presented to assess the proposed methodology.
First, three scenarii used for benchmarking are described. Second, an illustration of the results provided by ETSBM on a simulated dataset from one of the scenarii is given.

Simulation setup
The networks with textual edges are generated following three scenarii A, B, C, as originally introduced in Bouveyron et al. (2018).
Sampling networks with textual edges.
• Scenario A is composed of three communities, each defining a cluster, and four topics. By definition, a community is defined such that more connections are present between nodes of the same community. For each cluster, a specific topic is employed to sample all the documents associated with the corresponding intra-cluster connec- tions. Besides, an extra topic is considered to model documents exchanged between nodes from different clusters. Thus, by construction, the clustering structure can be retrieved either using the network or the texts only.
• Scenario B is made of a single community and three topics. Thus, all nodes connect with the same probability. Then, the community is split into two clusters with their respective topics. An extra topic is used to model documents exchanged between the two clusters. Therefore, in such a scenario, the network itself is not sufficient to find the two clusters but the documents are.
• Scenario C is composed of three communities and three topics. Two of the communities are associated with their respective topics, say t 1 and t 2 . Moreover, following the previous scenario, the third community is split in two clusters, one being associated with topic t 1 and the other with t 2 . Thus, considering both texts and topology, each network is actually made of four node clusters. Fundamentally, both textual data and the network itself are necessary to uncover the clusters. This scenario will be of major interest in this experiment section since it allows to ensure that the two sources of information are correctly used to retrieve partitions.
The edges holding the documents are constructed by sampling words from four BBC articles, focusing each on a given topic. The first topic deals with the UK monarchy, the second with cancer treatments, and the third with the political landscape in the UK. The last topic deals with astronomy. In the general setting, for all scenarii, the average text length for the documents is set to 150 words. The parameters used to sample data from the three scenarii are given in Table 1. Moreover, three examples of networks generated from A, B and C are presented in Figure 3.
Clustering performance evaluation. The main criterion used in the following to evaluate the clustering performances of the different strategies is the adjusted random index (ARI).

Scenario A
Scenario B Scenario C Figure 3: An example of each scenario is presented. The node colours denote the cluster memberships and the edge colours denote the major topic within the text. The Scenarii A, B and C are composed of 3, 1 and 3 communities respectively.
ARI measures how close two partitions are from one another. The closer ARI is to 1, the better the results are. A random cluster assignment leads to an ARI of 0, while a perfect retrieval of the cluster memberships gives an ARI of 1.

Network Topics Network & Topics
with ζ = 0.7. Thus, for each pair of clusters (q, r), the texts are sampled according to a mixture between a multinomial distribution with probability 1 on the corresponding topic and a uniform distribution over all topics considered. Finally, the intra-cluster connection probability is decreased from 0.2 to η = 0.1.

An introductory example
A first glimpse at the ETSBM results on a single network simulated with Scenario C is presented here. In Figure 4, the evolution of the ELBO and ARI values are monitored at each iteration of the inference of ETSM applied on this single simulated network. Node ARI Figure 4: Evolution of ETSBM ELBO and ARI (y-axis) at each iteration (x-axis) on the Scenario C after an initialisation with the K-means algorithm.
As we can see, both the ELBO and the ARI increase after each iteration. In particular, starting from the clustering initialisation with an ARI value of 0.62, the algorithm converges to a value of 1, characterising a perfect cluster recovery. This figure illustrates the ability of the methodology proposed to retrieve the true node partition, by combining the textual and network data.
In addition, Figure 5 provides representations for the expected posterior estimatesπ andγ computed as followsπ qr =π qr1 /(π qr1 +π qr2 ) andγ q =γ q /( Q r=1γ r ). We emphasise that the matrix characterises the connexion probabilities between clusters with a 10 −2 rounding. It matches the expected connectivity structure described in Table 1. Eventually, the topics learnt as well as the clustering results on the network are presented in Figure 6. In the network representation, the node colours correspond to the cluster memberships while the edge colours indicate the most used topic in the corresponding documents. Moreover, for each topic t k with k ∈ {1, 2, 3}, the 10 words with the highest probabilities, according to the corresponding topic vector β k , are displayed.
The three topics presented are well-separated and can be identified as the topics dealing respectively with astronomy, the political landscape in the UK, and the UK monarchy, as expected. In addition, four node clusters have been retrieved and the edge topics, or colours, match the description of the Scenario C setup. To conclude, ETSBM successfully render both the network topology and the edge topics. Clustering results by ETSBM algorithm Figure 6: On the left hand side, the top 10 words of each topic according to ETSBM results. Thus, for each topic t k with k ∈ {1, 2, 3}, the 10 words with the highest probability values, according to the corresponding topic vector β k , are displayed. On the right hand side, ETSBM clustering result is illustrated. The node colours indicate the node clusters while the edge colours correspond to the most used topic within the document.
Finally, Figure 7 provides a high level representation of the results. On the one hand, the "meta-nodes" represent ETSBM clusters and their size is proportional to the number of nodes assigned to the corresponding clusters. Moreover, the "meta-node" colours are consistent with the colours in Figure 6. On the other hand, the edges represent the meta-documents. We recall that they correspond to the expected posterior estimate of a document for a given pair of clusters. The edge colours correspond to the most used topic within the meta-document. The edge widths are determined by the number of connexions between the corresponding clusters. This figure underlines ETSBM capability to produce intelligible and accurate data summary. We emphasise that graphs with thousands of edges, that sometimes cannot be represented because of memory issues, are here able to be summarised in easy-to-read meta-graphs. To conclude, this introductory example showed the ETSBM capacity to render meaningful summaries by combining both network and text information. It is worth reminding that, since it comes from Scenario C, those results could not have been retrieved with models handling only network or texts as SBM, LDA or ETM.

Effect of the initialisation
This experiment aims to evaluate the impact of the initialisation on the final performance of our methodology. The networks are generated according to the Hard 2 difficulty, to easily visualise the differences between the tested configurations. Moreover, the experiment is performed on Scenario C to ensure both the network and textual data are used. Three different initialisations are compared: clusters may be randomly assigned to the nodes (random), or initial clusters can be determined by a K-Means algorithm fitted on the adjacency matrix A. Finally, the dissimilarity procedure proposed in Bouveyron et al. (2018) is evaluated as the last initialisation strategy (dissimilarity). It uses both network and textual information to build a similarity matrix based on the topics discussed between nodes. Then, a K-means algorithm is performed on this similarity matrix to find a cluster allocation for each node. This initialisation strategy requires to provide the topic proportion of each edge. Thus, ETM is trained on the texts and the estimated topic proportions (θ ij ) (i,j)∈E are used for the dissimilarity initialisation. Figure  While the random initialisation is close to 0 for ARI, both the K-means and the dissimilarity initialisation fluctuates in terms of ARI, with no clear advantage for one of the two strategies. However, ETSBM provides much better results with the dissimilarity initialisation than with K-means. It is also worth noticing that the gap between the random and K-Means initialisations has largely been closed by ETSBM algorithm. One possibility is that the model suffers the same flaws as SBM, which is for the ELBO to fall into local minimum. It is possible that the use of texts in the dissimilarity limits this effect. Therefore, we will only use the dissimilarity initialisation in the rest of the paper  as it provides the best results in most cases.

Model selection
This experiment aims to assess the efficiency of the model selection criterion, presented in Section 4.4. Let us remind that we do not aim at selecting the number of topics K since it is handled afterwards. As a consequence, the model selection criterion is evaluated for different values of K to ensure that the performances remain high, in all cases. For each scenario, 50 networks are sampled following the setup described in Section 5.1. For each network, ETSBM parameters are estimated taking the best initialisation out of 10. Table   2 presents the percentage of time a number Q is selected using the strategy proposed in Section 4.4 over the 50 networks, for each K value. It is worth noticing that the right model is selected more than 75% of the time, except for the Scenario B with K = 5, slightly bellow with 68%. In addition, as advocated before, for K = 10, the right model is selected more than 80% of the time in each scenario. This experiment illustrates the capacity of the model selection criterion to retrieve the number of clusters. Moreover, keeping a high value of K is confirmed to be compatible with an efficient cluster number selection.

Benchmark study
To end this section, ETSBM is evaluated against state of the art clustering algorithms for STBM, and SBM on the three levels of difficulty presented in Section 5.1. Results for LDA as well as ETM for text clustering are also provided. For each level of difficulty and each scenario, Table 3 displays the mean and the standard deviation of the ARI values obtained over 50 graphs. Both the node and edge clusters ARI are provided but in 2017 when a three-way split between the far-left political families, the centrists, or liberals, and the far-right emerged. This analysis aims at capturing the major topics discussed prior to the election. In addition, we want to understand the way those topics shape user groups interactions. However, this study does not aim at making any form of prediction about the election.

Dataset construction and method
In the collected data, each node represent a Twitter account. An account i is connected to j if the former retweeted the later or if i "mentioned" j with an "@account name" in a tweet. The text on the edges are the tweet themselves. Our database has been created by saving any tweet talking about one of the twelve candidates. If several tweets appear from i to j, the edge (i, j) holds all those tweets stack together. We only keep edges with text length greater than 100 characters. Then, a lemmatisation procedure is used to reduce the vocabulary size. The "stopwords", defined as non-informative words such as "and" or "it", are withdrawn, as well as numeric characters and words with a length inferior to 3 characters. In the end, we keep the largest connected component of this graph. Our dataset holds 2, 730 nodes and 403, 768 edges. This means that the graph is sparse at 94.58%. We emphasise that this level of sparsity is quite high and makes the data analysis particularly challenging. The number of topics is set to K = 20. Also, for each Q value, the model is trained for 10 different initialisations and the best result among those 10, ELBO wise, is kept. Then, the number of clusters is selected using our model selection criterion. Figure 9 shows that the most appropriate model according to our criterion corresponds to a number of clusters Q = 5. Selection of the best model

Results
The meta-graph presented in Figure 10a is a high-level representation of the network.
The "meta-nodes" correspond to ETSBM clusters and the edges to the meta-documents as defined in Equation (12). A translation of the top words is provided in Appendix B.11.
It is interesting to note the two types of clusters uncovered. nodes, ETSBM is able to detect it and to render its central function as a relay of information to other parts of the graph. This is stressed by the main topic discussed within the cluster. It regards the election as a democratic process: "round", "vote", "power", "president", "first" which we assume stands for "first round". This core cluster is retweeted differently by the four clusters which on the contrary hold clear political trends. The orange and green clusters are interested in Jean-Luc Mélenchon (pink arrow) and left parties in general (grey arrow) but they seem to differ in terms of function. The orange cluster clearly relays information about Jean-Luc Mélenchon and is interacting with the red cluster, interested in Eric Zemmour, or by the blue cluster, interested in Emmanuel Macron. On the contrary, the green cluster seems to only relegate contents without being retweeted. Eventually, a cluster (the red one), interested in Eric Zemmour, appears to relegate few contents from the central accounts but creates and shares many of its own content. This dynamic differs to the blue cluster interested in Emmanuel Macron, which mainly retransmits informations without many self interactions. To conclude, the threeway split of the French political landscape is rightfully captured. ETSBM is also able to detect subtleties such as a split within the left-wing, with the orange cluster interested only in Jean-Luc Mélenchon and the biggest one exchanging about different left-political front runners, Jean-Luc Mélenchon, Yannick Jadot, Fabien Roussel and Anne Hidalgo.
ETSBM combines the connection information, for instance all clusters are connected to the small one, and the topics information, for instance the green and orange should be separated, to provide relevant insights about the information organisation within the social network. This level of detail is promising and highlights how ETSBM gives a better comprehension of the complex dataset at our disposal.
(a) ETSBM allows to make high-level representation. Each node corresponds to a cluster and the edge colours indicate which topics is discussed between the clusters. The blue cluster reacts or retweets mainly about Emmanuel Macron, the French president, the orange cluster mainly reacts or retweets about Jean-Luc Mélenchon, a far-left candidate, the reactions or retweet of the red cluster mainly concerns Eric Zemmour, a far-right candidate, while the green cluster reacts or retweets information either about Jean-Luc Mélenchon or more generally about the left-wing candidates (Yannick Jadot, Jean-Luc Mélenchon, Fabien Roussel or Anne Hidalgo ).

Conclusion and discussion
The embedded topics for the stochastic block model (ETSBM) is well suited to simultaneously find meaningful node and edge clusters. In addition, ETSBM provides an intelligible high-level representation of the graph. It can be used both on directed and undirected graphs and is suited for large datasets thanks to the variational inference.
The numerical experiments showed that the ELBO is a relevant model selection criterion to estimate the number of node clusters Q in this Bayesian framework. Moreover, this criterion keeps provide a good estimate of Q for a high number of topics K. In the end, a use case on a Twitter dataset proved the usefulness of the method. ETSBM clustering results were both meaningful and humanly intelligible. Further work may be directed in the study of theoretical foundations of the model selection criterion proposed. Adding temporal information concerning the connectivity patterns and the topics modelling could also contribute to obtain useful information on the data.
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 δqr ij that can be approximated using a Monte-Carlo estimator, by drawing S samples for each pair (q, r), such that: s ∼ N (0, I K ), δ s qr = µ qr (τ, ν) + σ qr (τ, ν) s , θ s qr = softmax(δ s qr ).
with denoting the Hadamard product. Thus, for each pair of nodes (i, j) and pair of clusters (q, r), the estimate is given by: