Learning Hidden Structures with Relational Models by Adequately Involving Rich Information in A Network

Effectively modelling hidden structures in a network is very practical but theoretically challenging. Existing relational models only involve very limited information, namely the binary directional link data, embedded in a network to learn hidden networking structures. There is other rich and meaningful information (e.g., various attributes of entities and more granular information than binary elements such as"like"or"dislike") missed, which play a critical role in forming and understanding relations in a network. In this work, we propose an informative relational model (InfRM) framework to adequately involve rich information and its granularity in a network, including metadata information about each entity and various forms of link data. Firstly, an effective metadata information incorporation method is employed on the prior information from relational models MMSB and LFRM. This is to encourage the entities with similar metadata information to have similar hidden structures. Secondly, we propose various solutions to cater for alternative forms of link data. Substantial efforts have been made towards modelling appropriateness and efficiency, for example, using conjugate priors. We evaluate our framework and its inference algorithms in different datasets, which shows the generality and effectiveness of our models in capturing implicit structures in networks.


Introduction
Learning hidden structures within a network is an emergent topic in various areas including social-media recommendation (Tang & Liu, 2010), customer partitioning, social network analysis, and partitioning protein interaction networks (Girvan & Newman, 2002; Preliminary work. Under review by the International Conference on Machine Learning (ICML). Do not distribute. Fortunato, 2010). Many models have been proposed in recent years to address this problem by using linkage information such as a person's view towards others. Examples include stochastic blockmodel (Nowicki & Snijders, 2001) and its infinite communities case infinite relational model (IRM) (Kemp et al., 2006), both aiming at partitioning a network of entities into different groups based on their pairwise, directional binary observations. The "inter-nodes" link data used in existing approaches contributes to the explicit insight on social structures.
On the other hand, the "intra-nodes" metadata information could complement the disclosure of hidden implicit relations structures. Let us take the Lazega lawfirm network (detailed in Section 6) as an example, which contains both link and metadata information: The metadata information include attributes such as offices (Boston, Hartford or Providence), law schools (harvard, yale, ucon or other) and age associated with each of the entities (attorneys). Naturally, people with similar attributes tend to have relationship with each other. The directional link data including elements such as basic advice frequency, co-work time and friendship. These elements however, may take different forms. Here the first two elements can be represented by integer values (i.e. count link data), while friendship may better be represented by a real value on the unit interval (i.e. unit link data). If they have to be "binarized" as in the case of the existing models, then the lost of granularity could lead to poorer utilization of information.
We propose a new informative relational model (In-fRM) framework, which incorporates both the rich metadata information and granular link data in a sensible and efficient way. To integrate the metadata information, a new transform is proposed, and the corresponding result is placed as the prior for the communities of each entity. This enables the similarity of metadata information between entities to be reflected in their corresponding hidden structures. Inspired by the existing benchmark relational models of MMSB (Airoldi et al., 2008) and LFRM (Miller et al., 2009), we individually model the hidden structure as mixed memberships and latent features respectively. This lead to informative mixed membership model (InfMM) and informative latent feature model (InfLF) which is the centerpiece of this paper. The stick breaking process (Sethuraman, 1994) (Teh et al., 2007) alike methods were proposed to model the unknown number of communities. In particular, our InfMM model successfully gains the conjugate property. As discussed in Section 3.1, through these efforts, the existing models can be seen as the special cases of our proposed models.
In addition, we designed a set of solutions to model the various forms of link data, including the count and unit link data. We have chosen the likelihood and prior model carefully for both of their practical appropriateness and computation efficiencies. Their effects have been demonstrated in our experiments.
As a result, our models capture much richer information embedded in a network, thus leading to better performance as illustrated in Section 6 in modelling hidden structures. The rest of the paper is organized as follows. Section 2 introduces the relational models and necessary notations for our work. In Section 3, we describe the InfRM framework for integrating metadata information into each entity's hidden structure, including InfMM and InfLF. The generation distributions proposed for different forms of link data are provided in Section 4. Section 5 discusses the sampling methods and computational complexity analysis. Experiments in Section 6 compare our methods with the previous work and validate our model performance. Conclusions and future works are in Section 7.

Relational Models
The stochastic blockmodel (Nowicki & Snijders, 2001) assumes that each entity has a latent variable that directly represents its community membership. Each of the fixed number of communities associates with a weight, and the whole weight vector can be seen as a draw from a K-dimensional Dirichlet distribution. Naturally, the community memberships are realized from the multinomial distribution parameterized by the weight vector. The binary link data between two entities is determined by their belongingness communities. This model has been extended to an infinite K community, i.e., infinite relational model (IRM) (Kemp et al., 2006) where the Dirichlet distribution has been replaced by a Dirichlet process.
Various recent work has been proposed to capture the complex interactions amongst entities based on stochastic blockmodel, which can be categorized into two notable branches, both are a generalisation of stochastic blockmodel. The first branch features the latent feature relational model (LFRM) (Miller et al., 2009): instead of associating an entity with only a single feature, i.e., its membership indicator, it allows a variable number of binary features to be associated with each entity. The second branch follows the mixedmembership stochastic blockmodel (MMSB) model, in which each entity has its own community distribution, hence having a "mixed" class of interactions with other entities.
The LFRM-like work was originated from (Hoff et al., 2002;Hoff, 2005), while it assumes a latent realvalued feature vector for each entity. The LFRM in (Miller et al., 2009) uses a binary vector to represent latent features of each entity, and the number of features of all entities can potentially be infinite using an Indian Buffet Process prior (Griffiths & Ghahramani, 2006;2011). The work in (Palla et al., 2012) further uncovers the substructure within each feature and uses the "co-active" features from two entities during generating their link data. On the MMSB-typed work, a few variants have been subsequently proposed, including (Koutsourelakis & Eliassi-Rad, 2008) which extends the MMSB into the infinite community case and (Ho et al., 2012) which uses the nested Chinese Restaurant Process (Blei et al., 2010) to build the hierarchical structure of communities.

Notations
All notations in this paper are given in Table 1 directional, binary interactions s ij , r ij membership indicators of e ij in MMSB z i latent feature vector of entity i in LFRM π i membership distribution for entity i, π ik is the significance of community k for entity i B asymmetric, role-compatibility matrix, B kl indicates compatibility of communities k, l Figure 1 depicts the generative models of all the variables used in our work. In this paper, metadata information is incorporated into both branches of the stochastic blockmodel described earlier, i.e. MMSB and LFRM. Further, it can be applied to their base mode IRM (Kemp et al., 2006) with the similar approach, which we will not elaborate here.
Here C1 and C2 are the stick breaking representation for our mixed membership distribution π i . C3 and C4 correspond to the membership indicator and link data's generation, respectively. Detailed elaboration is in (Airoldi et al., 2008;Koutsourelakis & Eliassi-Rad, 2008). We leave equation C4 in its general form, i.e., g(B sij rij ), which may take on a variety of forms, such as those described in Section 4.
We use the attribute age in Lazega lawfirm to further explain the importance indicator η f k used in C1. W.l.o.g., we let f th 0 column of φ matrix denote the age attribute of all the entities, φ if0 = 1 implies that entity i has age > 40 (in our experimental setting), and C4 Figure 1. The generative model for several implementations. Observations are denoted in grey. The part above the dashed line corresponds to involving metadata information in Section 3; the below part corresponds to modeling link information discussed in Section 4. C1 to C4 represent four conditional distributions in two different forms as shown in Sections 3.1 and 3.2, respectively. 0 otherwise. From equation C1, one can easily see that when η f0k ≪ 1, age would largely increase the impact of the k th community. Likewise, η f0k ≫ 1 reduces the significance of the age attribute on the k th community. η f0k = 1 means that age does not have influence on the k th community at all. When φ if0 = 0, it makes age of the entity i neutral towards all other communities.
Instead of C1, the NMDR model (Kim et al., 2012;Kim & Sudderth, 2011) uses the logistic normal distribution (with the mean value being the linear sum (i.e., f φ if η f k )) to construct a stick-breaking weight ψ ik . While the method can successfully integrate the metadata information into the entity's membership distribution, it suffers from the lack of conjugacy, which makes inference inefficient. In our approach InfMM, we replaced the logistic normal distribution with a beta distribution, parameterised by f η φ if f k , where the positive, importance indicator η f k is given a vague gamma prior η f k ∼ Gamma(α η , β η ).
Despite the model relaxation, empirical results show that NMDR has a slow convergence. It is therefore imperative for us to search for a more efficient way to incorporate the metadata information. Compared to iMMM, our InfMM model replaces unified f k for the generation of ψ ik . Its conjugate property makes our model appealing in terms of mixing efficiency, which is confirmed in the results shown in Section 6.3. What is more is that our model can be seen as a natural extension of the popular iMMM model. By letting η f k = α 1/F and φ if = 1 , we obtain the classical iMMM. This makes sense, as without the presence of metadata, each feature is assumed to be counted equally, which implies that the model becomes the classical iMMM.

Informative Latent Feature Model
The generative process for informative latent feature (InfLF) model is defined as follows: Here C1 and C2 refer to the detailed construction of our specialized stick breaking representation π i . Similar to the traditional stick-breaking process (Sethuraman, 1994) (Teh et al., 2007), they are used to generate the latent feature matrix z in C3. C4 corresponds to the link data's generation in our model. Our work can be seen as an extension to the traditional LFRM, which can be seen at (Miller et al., 2009).
However, our InfLF's hidden structure differs from the one of LFRM. More specifically, the original LFRM uses one specialized beta process as the underlying representation for all the n entities' latent feature z. This process can be easily marginalized out in convenient of the Beta-Bernoulli conjugacy (Thibaux & Jordan, 2007). In our InfLF, each i th entity's latent feature is motivated by their own stick breaking representation π i , i.e., there are n representations in total. Thus, the individual metadata information is contained in each corresponding representation, which will be reflected in the latent feature.
We use the new transform, i.e., f η φ if f k , as the mass parameter (Thibaux & Jordan, 2007) in the construction of the stick breaking representation, as stated in C1. The importance indicator η here plays an opposite role when comparing to the InfMM model, i.e., larger value of η f k would make the present of attribute f promote the k th community.
An interesting notation is that the stick breaking representations in both of our InfMM and InfLF are no longer Dirichlet Process and Beta Process individually, as the single valued α parameter is replaced by a set

Count Link Data
In iMMM, we propose to model the count link data with the following likelihood and prior distributions: The parameter B kl in the Poisson distribution reflects the compatibility between the two communities k and l. The lager B kl encourages larger e ij . Further, we put a vague gamma prior on it as B kl ∈ R + . The resultant predictive distribution is the Negative Binomial distribution (Hilbe, 2011)

when marginalizing out B kl
For the discovered communities k, l in iMMM, we sample B kl as: Here On calculating an undiscovered community K + 1 in iMMM, we can marginalize the corresponding B value out:

Unit Link Data
In modelling the unit Link Data, we use the Beta Distribution instead as the corresponding generation distribution. For the iMMM case, we have: Thus, the posterior distribution of B kl between the discovered communities k, l is: While involving an undiscovered community K + 1, we have Due to the space limit, the detailed sampling procedures of both InfMM and InfLF models are summarised in the Supplementary Material. In here, we explicitly sample {π i } n i=1 . In fact, most of the conditional distributions used in Gibbs have been stated in the preceding sections.

Computational Complexity
We estimate the computational complexities for each model and present the results in Table 2. Our InfMM and InfLF are O(Kn 2 + Kn + F Kn) and O(K 2 n 2 + Kn + F Kn) respectively, with O(Kn) for the sampling of {π i } n i=1 and O(F Kn) for the metadata information's incorporation.
We have independently implemented the above benchmark algorithms to the best of our understanding. There have been a slight variation to NMDR, in which we have employed Gibbs sampling to sample the unknown cluster number, instead of Retrospective MCMC (Papaspiliopoulos & Roberts, 2008) used in the original paper. This is because we have set the conjugate priors to their corresponding generation distributions.
To validate the model's prediction accuracy, we use a ten-fold cross-validation, where we randomly select one out of ten for each entity's link data as testing data and the rest as training data. The criteria for evaluating the prediction capability are the training error (0−1 loss), the testing error (0−1 loss), the testing log likelihood and the AUC (Area Under the roc Curve) score, where these detailed derivations can be found in the Supplementary Material. Also, an extra study is performed on learning the importance indicator of metadata information in the lazega-lawfirm dataset as we have successfully inferred the corresponding η values.
At the beginning of the learning process, we set the vague Gamma prior Γ(1, 1) for all the hyperparameters, including α η , β η , α B , β B .
The initial states are of random guesses on the hidden labels (membership indicators in MMSB and latent feature in LFRM). For all the experiments, we run chains of 10, 000 MCMC samples for 30 times, assuming 5000 samples are used for burn-in. The average of the remaining 5000 samples are reported.

Lazega-lawfirm Dataset
The lazega-lawfirm dataset is about a social networking corporate located in the northeastern part of the U.S. in 1988 -1991. The dataset contains three different types of relations: co-work network, basic advice network, and friendship network for 71 attorneys, in which each link data is labelled as 1 (exist) or 0 (absent). Apart from these three 71 binary asymmetric matrices, the datasets also provide some metadata information on each of the attorneys, including the status (partner or associate), gender, office (Boston, Hartford or Providence), years with the firm, age, practice (litigation or corporate), law school (harvard, yale, ucon or other). After binarizing these attributes, a 71 × 11 binary metadata information matrix is obtained.
We conduct the link prediction on the co-work network and show the result in Table 3. Notably, the performance of our implementation of NMDR model is inferior compared to its original (Kim et al., 2012). The reason may be as a result of a sub-optimal metadata binarization process. However, we have shown that with the same attributes, our InfMM performs better than the NMDR in terms of training error, test capability and convergence behaviour (including the burn in samples needed and mixing rate).
Another interesting topic here is the learning of the importance indicator η for the attributes in the metadata information. We take a geometric mean value of participating the communities for each attribute and show the detail result in Table 4. As stated in Section 3.1, smaller value indicates larger influence. Table 4. The recovered Importance indicator η in Lazegalawfirm dataset. As we can see, the value of attribute office is the smallest amongst all these values, which indicates it has a largest influence. This phenomenon is consistent with common sense as people in the same place would be more likely to have a relation. Also, the attribute practice is more important than the others in forming this co-work link data.  towards the others, i.e., e i,j represents the proximity from i to j based on participant i's opinion. The detailed link values indicate the average proximity from one subject to another, which is categorised into 5 values correspondingly. While using previous models (Koutsourelakis & Eliassi-Rad, 2008), we manually set the proximity value larger than 10 minutes per day as 1, and 0 otherwise. We hence obtain a 73 × 73 asymmetric matrix. According to the generation distribution used, we can choose either the integer matrix or its binary version.
Alongside this directional link data, we also have a survey data on the entities involving metadata, including the traffic choice to work, personal habitat, social activity, the communication method, and satisfaction of university life.
As we can see in Table 3, we find our InfMM's performance is similar to the ones in iMMM. The reason may be that the metadata information does not correlate with the link data. Our pInfMM and piMMM's performance is the best among all these models. This validates the necessity of using Poisson distribution while encountering the count link data.

Convergence Behaviour
Trace plot for AUC A trace plot for the AUC value versus iteration time could help us choose an appropriate burn-in length. An earlier reach to the stable status of MCMC is desirable as it indicates fast convergence. Figure 2 shows the detailed results.
Mixing rate for a stable MCMC. Besides the MCMC trace plot, another interesting observation is the mixing rate of the stable MCMC chains. We use the number of active communities K as a function of the updated variable to monitor the mixing rate of the MCMC samples, whereas the efficiency of the algorithms can be measured by estimating the integrated autocorrelation time τ and Effective Sample Size (ESS) for K. τ is a good performance indicator as it measures the statistical error of Monte Carlo approximation on a target function f . The smaller τ , the more efficient of the algorithm. Also, the ESS of the stable MCMC chains informs the quality of the Markov chains, i.e., a larger ESS value indicates more independent useful samples, which is our desired property.

NIPS Coauthor Dataset
We use the co-authorship as a relation gained from the proceedings of the Neural Information Processing Systems (NIPS) conference for years 2000-2012. Due to the sparsity of the co-authorship, we observe the author activities in all 13 years (i.e. regardless of the time factor) and set the link data being 1 if two corresponding authors have co-authored on no less than 2 papers, which is to remove the co-authoring randomness. Further, the authors with less than 4 relationships with others are manually eliminated. Thus, a 92 × 92 symmetric, binary matrix is obtained.
We focus on the count link data's modelling in this dataset, where the actual link data among these 92 entities are used. As the detail result shown in Table 3, our piMMM performs better than the classical iMMM.

Conclusions & Future work
Increasing applications with natural and social networking behaviors request the effective modelling of hidden relations and structures. This is beyond the currently available models, which only involves limited link information in binary settings. In this paper, we have proposed a unified approach to incorporate various kinds of information into the relational models, including the metadata information and different formats of link data. The proposed informative mixed membership (InfMM) model and informative latent feature (InfLF) model have been demonstrated effective in learning the structure and show advanced performance on learning implicit relations and structures. Also, our adaptive link data modelling method further boosts the capability of utilizing rich link data in the real-work scenario.
We are extending our work to: 1), how to integrate the multi-relational networks and unify them into the InfMM framework to deeply understand network structure; 2), when the link data is categorical, what