An End-to-End Community Detection Model: Integrating LDA into Markov Random Field via Factor Graph

1 Introduction

Networks such as social and biological networks often contain abundant topological and attribute information. Detecting communities in such networks can help people understand the organization structures and function modules underlying the networks.

Many community detection methods using different theories and techniques have been proposed (see a nice review in [Fortunato and Hric, 2016]). They include hierarchical clustering [Girvan and Newman, 2002], modularity-based methods [Newman and Girvan, 2004], heuristic methods [Ruan et al., 2013], spectral optimization [Chen and Li, 2010], and statistical modeling [He et al., 2015]. Among these methods, statistical modeling has been actively studied in community detection due to the solid theories and good performance. The method was first used on networks with topology structure alone [Brian and Newman, 2011], and later extended to networks with both topological and attribute information [Tao et al., 2019].

∗Corresponding author.

Existing community detection methods mainly belong to the directed graphical model. That is, they typically formulize the generative process of networked data as a sequence of rigorous probability distributions. In contrast, Markov Random Field (MRF), which is a type of undirected graphical model, has also been applied to community detection very recently [He et al., 2018; Jin et al., 2019]. They obtained satisfactory results because, 1) the field structure of MRF more naturally describes the neighborhood information in networks, and 2) MRF is more flexible than directed graphical model since the probabilistic constrains for MRF are often relaxed when defining energy functions.

However, existing MRF methods focus on the network topology alone while ignore the semantic attributes of nodes (which are also important to community detection). A straightforward way to combine these two sources of information (also as discussed in the above MRF works) is that, one can first use a topic clustering model (e.g. LDA [Blei et al., 2003]) to derive the group membership of nodes by using semantic attributes, and then take this result as a prior to define the MRF model (which utilizes topological information).

However, in this two-stage approach, the modeling of network topology in MRF has no effect on the clustering of topics in LDA. Moreover, the influence of LDA's result on MRF is largely limited since it is fixed after training LDA and only taken as a prior of MRF. That is, the parameters of these two models (LDA and MRF) cannot be adjusted by each other. This prevents the two-stage approach from really realizing the complementation of the advantages of these two models in dealing with network structure and node semantics.

To address this problem, one can integrate LDA into MRF to form an end-to-end model, where the parameters of these two sub-models can be learned jointly. However, LDA is a directed graphical model (which is modeled by the conditional dependence between probability distributions) whereas MRF is an undirected graphical model (which is modeled in the form of energy functions). The different nature of the two models make their integration challenging for at least two reasons. First, it is difficult to derive the parameter sharing mechanism between directed and undirected models, which is necessary to bridge the two models. Second, the training mechanism of directed and undirected models are essentially different, making it difficult to propagate information between parameters of the two models.

In this paper we integrate the topic model LDA [Blei et al., 2003] into a network-specific MRF [He et al., 2018] to form an end-to-end learning system, named attrMRF, for community detection in attributed networks. To address the first challenge (parameter sharing mechanism between directed and undirected models), we first unify the likelihoods of LDA and MRF using Gibbs distribution, and then transform them into a unified factor graph framework based on the new likelihoods. To handle the second challenge (training mechanism of directed and undirected models), we propose an efficient belief propagation algorithm under the unified factor graph, to achieve an end-to-end learning of the two models (such that their parameters can be trained jointly).

Our main contributions are as follows.

1. Existing MRF-based community detection methods consider the network topology alone while ignore the semantic attributes of nodes (which are also important to community detection). This is the first time to consider these two sources of data together under the MRF framework in an end-to-end way.
2. We integrate LDA (which is good at modeling the semantic attributes of nodes and a directed graphical model) into MRF (which is good at describing the network structures and an undirected one) to form a unified model. The challenge in parameter sharing and joint training are handled by unifying the two models using a factor graph and propagating belief on the factor graph.
3. Empirical results on 6 real-world datasets show that the proposed approach usually compares favorably with the state-of-the-art methods.

2 Preliminaries

Here we introduce the notations used and the Markov Random Field, which is the base of the proposed approach.

2.1 Notations

Let G = (A,W) be an attribute network with N nodes and e edges. Here, A is a N × N adjacent matrix, where entry aij is 1 if the i-th and j-th nodes are connected in G and 0 otherwise. Matrix W, on the other hand, is a N ×M attribute (content) matrix (where M is the number of attributes in each node). We use X = {x1, . . . , xN} to represent the nodes in the network and C = {c1, . . . , cN} to represent a community partition of network G, where ci denotes the community node xi belongs to.

2.2 Markov RandomField

Markov Random Field (MRF), which is an undirected graphical model, has been widely used in many areas, such as image segmentation and network analysis [Blake et al., 2011]. The energy function of a general MRF model is often defined as

Here ϕi is the unary potential of node xi (e.g. a pixel in the image or a node in the network), measuring the cost for the difference between the source priori and value of xi; θij is the pairwise potential of nodes xi and xj (defined on the neighborhood systems of the data), describing the costs across all the possible combinations of values of the nodes.

3 The Method

We will first provide an overview of the method, then propose the unified model, and last introduce the inference algorithm.

3.1 Overview

The proposed model, attrMRF, consists of two parts, the LDA layer and MRF layer. The LDA layer uses the attribute information (as the unary potentials) to find communities by extracting features on the global level. The MRF layer, on the other hand, uses the topology information (as the pairwise potentials) to find communities smoothly in neighbor systems. The key of attrMRF is integrating LDA (a directed graphical model) into MRF (an undirected one) by formulizing them using a unified factor graph framework in an end-to-end way (such that their parameters can be shared and trained jointly).

To build the unified factor graph, we first unify the likelihoods of LDA and MRF, making them both suitable for factor graph. We then combine them into a new likelihood function via Gibbs distribution. Last, we formulize them into a unified factor graph framework using the new likelihoods.

To make attrMRF a real end-to-end learning process, we design a set of message passing rules under the framework of factor graph, so that the parameters of LDA and MRF can be adjusted by each other. To be specific, in the process of message passing, every node in LDA receives messages from its neighbors (in LDA) to obtain a rough solution. The nodes then send this rough solution as a message to MRF. Consequently, every node in MRF uses this message as unary potentials, and collects messages from its neighbors (in MRF) to refine this solution. Then the nodes send this solution back to LDA to start the next iteration. The above message passing (starting from LDA, passing to MRF, then passing back to LDA) repeats until the model has converged (or reaching the maximum number of iterations). In this way, we are able to integrate and train these two types of models jointly to develop a true end-to-end method for community detection.

3.2 Building the UnifiedModel

In order to integrate LDA (a directed model) into MRF (an undirected one), we need to transform them into a unified form. As mentioned previously, in this paper the transformation is done using factor graph due to the fact that it is a general and flexible probabilistic graphical model. To be specific, factor graph can not only describe the conditional dependence of probability distribution, but also describe the constraint between variables by using energy functions. More importantly, both directed and undirected graphical models can be converted into a factor graph without losing their inherent characteristics [Yedidia et al., 2003]. If we want to build a factor graph, we need to first get the joint probability distribution of the model and then decompose it into the products of a set of factor nodes. We will explain how this is done in the rest of this section.

As mentioned previously, the proposed unified model, attrMRF, integrates LDA into MRF. For MRF [He et al., 2018], the pairwise potential between nodes xi and xj is defined as

Here di is the degree of node xi, and δ(ci, cj) is 1 if ci=cj (i.e. xi and xj in the same community) and 0 otherwise. Since the MRF in attrMRF uses pairwise potentials alone, the global energy potential is thus the sum of all pairwise potentials:

For the LDA in attrMRF, on the other hand, the joint probability distribution is

where wm,n says that word m is in document n and zkm,n says that word m is in topic k of document n. Particularly, m is the semantic attribute of the n-th node in the model.

In order to represent the probability distribution as the product of a set of factor nodes, we rewrite the above joint probability distribution of LDA as

Based on the definition of conditional probability, we have

In order to combine (2) (the energy function of MRF) and (3) (the joint probability distribution of LDA), we convert P(Z|W, α, β) into the form of energy function according to Gibbs distribution:

where β1 is a temperature coefficient.

Then the global energy function of the unified model can be written as the sum of (2) and (4):

Last we can use Gibbs distribution to convert the global energy function in (5) back into the form of probability:

Here Z is a normalization term, fθn and fφm are defined in (3), and fγij is the pairwise potential of nodes xi and xj.

It is worth noting that (6) is the objective function of the unified model, attrMRF, which can be represented as a factor graph, shown in Figure 1. Here xn (where n ∈ [1,N]) is a node in MRF, zm,n (where m ∈ [1, M]) the semantic attribute m of node xn, while α and β the hyperparameters of LDA.

3.3 Inferring the UnifiedModel

With the objective function in (6), the community partition C on N nodes can be estimated as the joint maximum of the posteriori configuration:

The equation in (7) says that the estimated community configuration is the one that corresponds to the largest joint probability. Since Loopy Belief Propagation (LBP) [Chorowski et al., 2014; Rosenberg, 2007] allows identifying a configuration (of variables) that contributes to the largest joint probability from factor graph (containing cycles), it is also used here to find the estimated community configuration. Another reason for using LBP is that, the message passing in the method allows the parameters of the two models in attrMRF (LDA and MRF) to influence each other.

Specifically, there are two kinds of messages when using LBP on factor graph. The message from a variable node to a neighboring factor node, and the message from a factor node to a neighboring variable node (for simplicity, in the rest of this section we use VNs to denote variable nodes and FNs to represent factor nodes). These two kinds of messages can be calculated iteratively in our model:

1. The message fromVN xi to neighboring FN fj:

This says that message fromxi to fj is the product of the messages from neighboring FNs of xi (except for fj).

1. The message from FN fj to VN xi:

This says that themessage fromfj to xi is themaximum of the product of fj and the product of the messages from neighboring VNs of fj (except for xi).

Here are three main steps for passing messages in attrMRF. 1. Initialize each VN with a probability distribution, representing the probabilities of the node belonging to the communities. The probability distributions are then used as the messages from VNs to FNs. Since we have the initial communities allocation of all nodes, the pairwise potentials can then be calculated as

Here di is the degree of node xi, β1 is a temperature coefficient, and δ(ci, cj) is 1 if ci = cj and 0 otherwise. Note that the pairwise potentials are the same as the factor functions of the FNs in MRF layer.

The value of FNs in LDA layer can be calculated as

Here fθd normalizes incoming messages by the total number of messages for all topics (i.e. communities) associated with node xn (to make the outgoing messages comparable across nodes). On the other hand, fφm normalizes incoming messages by the total number of messages for all attributes (to make the outgoing messages comparable across attributes).

1. Update messages from FNs to VNs. Once all messages from VNs and the factor functions are obtained, the messages

Algorithm 1 The Inference Process for attrMRF

Input: The topology and attribute matrices of the network,

• A, W. The hyperparameters of attrMRF, α, β, and β1.

Output: Community partition C

• 1: Initialize the messages fromVNs to FNs.
• 2: do t = 0 ; conv = ε + 10.
• 3: while conv > ε and t < T do
• 4: for every FN in attrMRF do
• 5: Update messages from FN to VNs via (8) to (11).
• 6: end for
• 7: for every VN in in attrMRF do
• 8: Update messages fromVN to FNs via (12) to (15).
• 9: end for
• 10: do t = t +1 ; conv = |µnew -µold|.
• 11: end while
• 12: Compute ˆ C from the max-beliefs according to (16).

form FNs to VNs could be updated. In practice, however, the product of multiple incoming messages often leads to a result close to zero [Zeng and Liu, 2008]. To avoid arithmetic underflow, we approximate the product operation by the sum operation of incoming messages (since when the product value increases, the sum value also increases [Zeng et al., 2013]).

Specifically, there are three types of FNs: fθi , fφw , and γij . First, the messages from fθi to VNs are updated as

where µ-m,i(ci) represents the sum of all messages from VNs connected to θn (except for zm,i). Particularly, the message from fθi to VN xi is updated as

where µ·,i(ci) represents the sum of all messages from VNs connected to θn (except for xi). It is worth noting that while (8) and (9) look different, they actually work in the same way.

Next, the messages from fφw (the second kind of FNs) to VNs are updated as

where µm,-i(ci) represents the sum of all messages from VNs connected to φm (except for zm,i).

Last, the messages from the third kind, γik, are updated as

where µxk→γik (ck) is the message from VN xk to FN γik.

1. Update messages from VNs to FNs. Once all messages from FNs to VNs have been updated, the messages from VN

xi to FN can update again as

Here µγik→xi represents the message from FN γik to VN xi. Since there are only two FNs (red and yellow squares in Figure 1) connected to each VN (circles in the figure) in the LDA layer, the message can be updated as

With the above three steps we can update the messages passing in the unified model. When the algorithm converges, the variable max-belief, Bi(ci), can be calculated as

which is the sum of all the messages sending to node xi

The inference process discussed above is summarized in Algorithm 1.

4 Experiments

We first validate why attrMRF (the proposed method) works and then compare it with some state-of-the-art methods.

A summary of the datasets used is shown in Table 1. Since all the methods require the number of communities to be given, we set it the same as that of the ground truth. We used Accuracy (AC) [Liu et al., 2012] and Normalized Mutual Information (NMI) [Danon et al., 2005] as accuracy metrics for performance evaluation.

4.1 Why attrMRFWorks

In this section we analyze why attrMRF works from both quantitative and qualitative perspectives.

Quantitative Analysis

Here we compare attrMRF with NetMRF (which is a MRFbased method using network topology alone and the base of the MRF part of our method) and the two-stage approach (where we first use LDA on attributes to derive an initial solution and then use MRF for refinement using topology) in terms of AC and NMI.

As shown in Table 2, attrMRF performs better than the two-stage approach which performs better than NetMRF. To be specific, attrMRF is on average 11.03% and 5.98% more accurate than the two-stage approach and NetMRF in terms of AC. We get similar result in terms of NMI. It validates that the proposed end-to-end model, attrMRF, indeed better integrates the advantages of MRF and LDA, and consequently derives better results.

Qualitative Analysis

We demonstrate how the end-to-end mechanism in attrMRF leads to better results. This can be done by taking a closer look at the results of the two-stage approach and attrMRF. As an example Figure 2 shows node id17 and its neighbors in the Cora dataset, where (a) is the result of the two-stage approach and (b) the result of attrMRF. Specifically, the two-stage approach wrongly finds the community node id17 belongs to (denoted by color green), which is different from the community its neighbors belong to (color orange). This error is due to the fact that LDA and MRF are trained separately in the two-stage approach. Thus, without the correction fromMRF during training, the probability for the wrong community produced by LDA is too large and stubborn to be overturned by the following MRF.

While the two-stage approach finds the wrong community for node id17, attrMRF detects the correct one. The reason why attrMRF is able to do so is due to the fact that LDA and MRF are trained jointly in attrMRF. Thus, with the correction fromMRF during training, the probability for the wrong community produced by LDA is small enough to be overturned by MRF (as shown in the histogram of Figure 2 (b)). This theoretically explains what we experimentally demonstrated in the quantitative analysis (where attrMRF has the highest AC and NMI values).

4.2 Comparison with ExistingMethods

We also compared attrMRF with some state-of-the-art community detection methods, which can be divided into three categories. The first includes DCSBM [Brian and Newman, 2011] and MRF-N [Jin et al., 2019], which use network topology alone. The second includes BPLDA [Zeng et al., 2013], which denotes the LDA model optimized by belief propagation. The third includes PCLDC [Yang et al., 2009], BlockLDA [Balasubramanyan and Cohen, 2011], SCI [Wang et al., 2016], and TLSC [Zhang et al., 2018], which use both the network topology and semantic attributes in the networks.

As shown in Table 3, attrMRF performs the best on 5 and 4 out of the 6 networks in terms of AC and NMI, respectively. On the remaining networks where attrMRF does not perform the best, it is still competitive with the best baselines. To be specific, attrMRF is on average 19.85%, 12.62%, 7.66%, 16.77%, 18.63%, 12.06% and 6.45% more accurate than DCSBM, MRF-N, BPLDA, PCLDC, B-LDA, SCI and TLSC in AC; and 13.31%, 12.17%, 3.79%, 12.82%, 22.92%, 15.22% and 6.11% more accurate than these methods in NMI.

It is not surprising to see attrMRF performs better than DCSBM, MRF-N and BPLDA since it utilizes more sources of information. It is, however, more interesting to see attrMRF outperforms the other four methods, which also use both topological and attribute information in networks. This superiority is not by chance. Instead it could be because 1) attrMRF ideally utilizes the advantages of MRF and LDA which are more suitable to describe the topological information and semantic attributes respectively, while 2) existing methods (e.g. TLSC) are mainly the extension of topic models, which incorporate network topology into the original directed graphical model to serve as a role of refinement.

5 RelatedWork and Discussion

Here we discuss two types of the most related works to state the advantages of the proposed model, attrMRF.

5.1 MRF-Based Community DetectionMethods

To our best knowledge, only two MRF methods have been proposed recently for community detection. The first is NetMRF [He et al., 2018]. It uses the MRF field structure to characterize the irregular structure of networks, and then defines the energy function to encode the structure and properties of network communities. This is also the base of the MRF part of our attrMRF approach. The second method is proposed in [Jin et al., 2019]. It makes up for the defect of low coupling of network embedding methods by taking the advantages of MRF in characterizing the relational data, leading to a general MRF framework to better find communities.

However, these existing methods only consider the network topology while ignore the semantic attributes of nodes. Though as discussed by their authors, one can easily incorporate node attributes (by first using LDA on node attributes to get an initial solution and then employing MRF to perform the refinement based on network topology), this is, however, not an ideal way to combine these two sources of information. This claim was experimentally demonstrated by the quantitative and qualitative comparison between NetMRF, the twostage approach, and attrMRF (Table 2 and Figure 2).

5.2 Community DetectionModels on Attributed Networks

Recently, many statistical models for finding communities in attributed networks have been proposed. For example, [Balasubramanyan and Cohen, 2011] proposed the Block-LDA model. It uses the stochastic block model to model the links to assist LDA (which can make good use of the semantic attributes of nodes), allowing it to integrate these two sources of information. [Zhang et al., 2018] proposed a two-level semantic community model. It divides the topics into two levels to solve the problem that topics in the generation of contents are often not from a unique topical level.

However, these methods are typically based on directed graphical model. This may be because the directed graphical model (e.g. topic models or Gaussian mixture model) is good at describing the semantic information of nodes, and the integration of network topology to improve topic models under the original directed graphical model framework is more straightforward to be designed. However, MRF (which is a type of undirected graphical model) could be more suitable to model the topological information. Thus methods such as our attrMRF, which combines MRF and topic models, could be a more suitable way to incorporate these two sources of data. This claim was echoed by the comparison between the state-of-the-art methods and attrMRF (Table 3).

6 Conclusion and Discussion

In this work, we proposed the first MRF approach for community detection in attributed networks in an end-to-end way. We first integrate LDA into MRF to form a unified model via factor graph modeling. We then use belief propagation under this new factor graph model to learn parameters of the two sub-models jointly. Empirical results on 6 real-world datasets show that the proposed approach usually compares favorably with other state-of-the-art methods. While the proposed work focuses on disjoint community, it may be readily extended to find overlapping communities by replacing max-sum rule of BP with sum-product rule.

Acknowledgments

This work was supported by the Natural Science Foundation of China (61876128, 61772361), and the National Key R&D Program of China (2017YFB1401201).