Overlapping Communities and Roles in Networks with Node Attributes: Probabilistic Graphical Modeling, Bayesian Formulation and Variational Inference (Extended Abstract)

1 Introduction

The integration of community discovery and role analysis can take advantage of node attributes and behavioral role patterns. To elaborate, attributes are in principle beneficial to refine communities and roles, by enabling the detection of the affiliations of nodes to such communities and roles even with few or no interactions with other nodes. In addition, behavioral role patterns are useful to model connections between nodes, in terms of both their involvement in communities and their roles in the participated communities.

Unfortunately, the interrelationship of network communities, roles with respective behavioral patterns and node attributes raises several issues. First, modeling network structure in terms of both communities and behavioral role patterns is problematic. Indeed, community discovery and role analysis provide different explanations of links. More precisely, in community discovery (that typically ignores roles), links are usually explained by community involvement. In this regard, pluralistic homophily was found in [Yang and Leskovec, 2013] to be a realistic model of tie formation, in which links are more likely between nodes with a larger number of affiliations to common communities. Instead, in traditional role analysis (that generally disregards communities), links are commonly interpreted via mixed-membership block-modeling [Anderson et al., 1992; Arabie et al., 1978; Holland et al., 1983; Rossi and Ahmed, 2015]. This amounts to considering links as interactions between node roles, whose strength is determined by underlying behavioral patterns. Second, it is not clear how node attributes are interrelated with communities, roles and respective behavioral patterns. Third, the sought-after interrelationship should be explicative and predictive of network structure.

∗This paper is an abridged version of the homonymous article published in Artificial Intelligence, i.e., [Costa and Ortale, 2022].

In this paper, we aim to refine the joint analysis of overlapping communities and behavioral roles in networks, through the incorporation of node attributes and behavioral role patterns. Also, we intend to investigate whether looking simultaneously at network structure and node attributes is advantageous in terms of robustness to noise (or lack of observations) in either of the two properties. Yet, we strive to formulate plausible models explaining the interaction of node attributes with communities, roles and respective behavioral patterns.

In order to pursue the above-mentioned objectives, we develop two new model-based machine-learning approaches [Bishop, 2013; Ghahramani, 2015; Pfeffer, 2016] to the exploratory and unsupervised analysis of overlapping communities, roles and respective behavioral patterns in networks with node attributes [Yang et al., 2013]. Both approaches rely on probabilistic graphical modeling [Bishop, 2006; Koller and Friedman, 2009; Murphy, 2012] to establish conditional (in)dependencies between visible and hidden aspects of networks. The visible aspects include node attributes and links. Both are treated as observed variables. The hidden aspects are treated as latent variables and include behavioral role patterns along with affiliations [Lattanzi and Sivakumar, 2009; Yang and Leskovec, 2013]. These are used to capture the extent of node involvement in communities and roles, the degree of role specificity to communities, as well as the strength of attribute relatedness to either roles or communities.

The above-mentioned conditional (in)dependencies are encoded in two Bayesian generative models of networks, i.e., SCANNER and PERISCOPE, that postulate alternative assumptions on node attributes. Under SCANNER (StruCture and Attributes of Nodes from commuNitiEs and Roles), node attributes are affiliated to roles. Instead, under PERISCOPE (toPology and nodE attRIbuteS from Communities and rOle PattErns), node attributes are affiliated to communities.

The latent variables of SCANNER and PERISCOPE are estimated in [Costa and Ortale, 2022] through variational inference [Blei et al., 2017; Jordan et al., 1999; MacKay, 2002]. The latter enables exploratory, predictive and descriptive tasks under SCANNER and PERISCOPE. The exploratory tasks include the analysis of communities and roles with respective behavioral patterns as well as the posterior explanation of link formation. The predictive tasks comprise the prediction of unobserved links and attributes. The descriptive tasks involve the interpretation of communities and roles.

In [Costa and Ortale, 2022], SCANNER and PERISCOPE are extensively tested quantitatively and qualitatively, through a comparative evaluation (in the above tasks) on realworld benchmark data sets from different social networking services. Their scalability is also comparatively investigated.

2 Preliminaries

The notation used in this paper is summarized below along with some fundamental concepts.

2.1 Networks, Communities, Attributes, Roles and Latent Affiliations

The network-based representation of a targeted complex system is a graph G = {N, E}, where N = {1, . . . N} is a set of nodes (numbered 1 through N) and E ⊆ N ×N is a set of links. Nodes correspond to entities, which interact in the network (e.g., individuals, organizations and so forth). Links represent interactions between nodes and are summarized via a binary adjacency matrix L, whose generic entry Ln,n′ is 1 iff a link between nodes n and n′ is observed and 0 otherwise.

We are interested in the joint modeling and analysis of three primary properties of an input network G, i.e., its community structure, the roles of its nodes and their attributes.

Communities are structures of G, which can be formalized as a set C ≜ {C1, . . . , CK} of K overlapping groups of nodes (i.e., Ck ⊆ N with k = 1, . . . ,K). The generic node n can participate in all communities, although with a different involvement. In particular, ϑn,k is the degree to which n is involved in the arbitrary community Ck.

Roles are a set R ≜ {R1, . . . , RH} of H behavioral classes (i.e., Rh ⊆ N with h = 1, . . . , H) 1 . The generic node n can play all roles, although with a different attitude. Specifically, σn,h is the extent to which n is suitable for playing the arbitrary role Rh. Besides, roles are specific to communities and the specificity of role Rh to community Ck is ϕh,k.

Let A ≜ {f1, . . . , fA} be a set of A binary attributes. The boolean indicator Fn,a (with 1 ≤ a ≤ A) is 1 iff node n exhibits attribute fa and 0 otherwise. Notation F ≜ {Fn,a|n ∈ N, fa ∈ A} is the characterization of all nodes in terms of their attributes. In practical applications, L and F are usually (very) sparse. Attributes are related to roles to a varying degree. The relatedness of attribute fa to role Rh is πa,h.

1 Notice that, in our formulation, roles are not explicitly observed as structural patterns of node connectivity in G.

Overall, node affiliations to communities and roles are respectively denoted as Θ ≜ {ϑn,k|n ∈ N, Ck ∈ C} and Σ ≜ {σn,h|n ∈ N, Rh ∈ R}. Role affiliations to communities are compactly indicated as Φ ≜ {ϕh,k|Rh ∈ R, Ck ∈ C}. Notation Π ≜ {πa,h|1 ≤ a ≤ A, Rh ∈ R} means the relevance of all attributes to individual roles.

2.2 Behavioral Role Patterns

The establishment of links between nodes is assumed to be influenced (among others) by their common community affiliations, the strength of such affiliations and the respective behavioral role patterns. The combination of such components to rule tie formation is detailed in Section 3. Here, we supplement roles with their corresponding behavioral patterns.

Let Rh be a generic role fromR. The behavioral role pattern associated with Rh is ϵh ≜ {ϵh,h′ |Rh′ ∈ R}, where ϵh,h′ is the unknown strength of interaction between Rh and Rh′ (with 1 ≤ h′ ≤ H). Intuitively, ϵh (with 1 ≤ h ≤ H) captures the behavior involved in the fulfillment of the social function ascribed to role Rh. Notation Υ ≜ {ϵh|Rh ∈ R} succinctly represents the behavioral patterns of all roles.

2.3 Problem Statement

Given an input network G, a number K of communities and a number H of roles, we aim to perform

• the unsupervised exploratory analysis of G, to infer the unknown values of all elements of Θ, Σ, Υ, Φ and Π;
• the prediction of missing links between nodes of G.
• the prediction of unobserved node attributes.

The above tasks are accomplished by inferring a posterior distribution over Θ, Σ, Φ, Υ and Π given G (or, equivalently, the adjacency matrix L and attribute matrix F ). Actually, the true posterior is approximated through variational inference in a generative network model, that explains the formation of G from a Bayesian probabilistic perspective. Henceforth, all elements of Θ, Σ, Φ, Υ and Π are treated as random variables, being unknown and not directly measurable.

3 The SCANNERModel

SCANNER is a Bayesian probabilistic generative model of overlapping communities, roles and respective behavioral patterns in networks with node attributes. SCANNER explains the observed aspects of a network G (i.e., topology L and node attributes F), in terms of its latent aspects, namely

• the affiliations of nodes to communities and roles (i.e. Θ and Σ);
• the behavioral role patterns (i.e Υ);
• the relevance of roles to communities (i.e Φ);
• the relatedness of attributes to roles (i.e Π).

Fig. 1 illustrates the conditional (in)dependencies between observed and latent aspects of G under SCANNER in the form of shaded and unshaded random variables, respectively.

The likelihood of observations L and F is

where ϑn = {ϑn,k|k ∈ C}, σn = {σn,h|h ∈ H} and πa = {πa,h|h ∈ H}. Moreover, the individual observations Pr(Ln,n′ |ϑn,σn,ϑn′ ,σn′ ,Φ,Υ) and Pr(Fn,a|ϑn,σn,Φ,πa) are defined as Poisson distributions with suitable parameterizing rates. The Poisson distribution is well suited to binary data and beneficial to expedite inference on sparse networks [Gopalan et al., 2015]. Moreover, rates naturally allow for the incorporation of the causes deemed to be determining for the emergence of links and node attributes. Formally, for each pair of nodes n, n′ ∈ N and each attribute fa ∈ A, Pr(Ln,n′ |ϑn,σn,ϑn′ ,σn′ ,Φ,Υ) ≜ Poisson(Ln,n′ |δn,n′) and Pr(Fn,a|ϑn, σn, Φ, πa) ≜ Poisson(Fn,a|δn,a), where

The parameterizing rate δn,n′ at Eq. 2 captures the latent interaction in G between n and n′ , through their affiliations to common communities and respective roles. Remarkably, Eq. 2 seamlessly reconciles pluralistic homophily with mixed-membership block-modeling from traditional role analysis. Hence, the formation of ties between nodes is influenced by their affiliations to shared communities, the strength of affiliation to such communities and respective roles, the specificity of roles to the participated communities as well as the patterns of interactions between roles.

The Poisson rate δn,a at Eq. 3 is meant to rule the inclusion of fa as an attribute of node n, according to the strength with which n is affiliated to communities and roles, the specificity of roles to communities and the relevance of fa to roles.

In compliance with conjugacy [Bishop, 2006], Gamma priors are placed on the individual random variables corresponding to the different latent aspects of G. More precisely, for each n ∈ N, Ck ∈ C, Rh, Rh′ ∈ H and fa ∈ A,

where αψ and βψ with ψ ∈ {ϑ, σ, ϕ, π, ϵ} are, respectively, shape and rate hyperparameters.

Notably, the above Gamma distributions enforce nonnegativity both on affiliation strengths and behavioral role patterns. This improves the interpretability of SCANNER by favoring sparseness in its representation. Additionally, it ensures that the overall strength of affiliation for each node, role and attribute does not amount to 1, thus avoiding the typical inconvenient of conventional mixed-membership modeling. Therefore, a very strong affiliation of any node, role or attribute does not imply a corresponding drop in the overall strength of all other affiliations of that node, role or attribute.

Under SCANNER, a network G is assumed to be generated through a sequence of interactions among the random variables of Fig. 1. As detailed in Fig. 2, such a process consists of six steps. Steps I through IV preliminarily deal with the realization of the latent affiliations and behavioral role patterns. Steps V through VI eventually generate G through the realization of the observed links and node attributes. More precisely, at steps I, II and III, the generative process samples the strength of the latent affiliations covered in Section 2.1 from the respective Gamma priors. At step IV, another Gamma prior is again sampled to draw the behavioral role patterns of Section 2.2. At step V, the presence/absence of a link between any two nodes is sampled from the Poisson distribution, that is placed over L as the link data likelihood. Lastly, at step VI, the presence/absence of attribute fa in the characterization of node n is sampled from the Poisson distribution, which is placed over F as the attribute data likelihood.

4 Tasks

Fitting SCANNER to an input network G enables the accomplishment of a wide variety of exploratory, predictive and descriptive tasks, including those enumerated at Section 2.3 (please see [Costa and Ortale, 2022] for further details).

4.1 Exploratory Network Analysis

Node affiliations reveal the underlying organization of G into overlapping communities and roles. The degree to which node n participates in community Ck is ϑ∗n,k ≜ E[ϑn,k]. Moreover, the extent to which node n is suitable for playing role Rh is σ∗n,h ≜ E[σn,h].

Community structure and roles allow the posterior explanation of links. Let n and n′ be two connected no-

1. For each node n ∈ N
2. For each community Ck ∈ C
3. draw the degree ϑn,k to which n is involved in community Ck, i.e., ϑn,k ∼ Gamma(ϑn,k|αϑ, βϑ).
4. For each role Rh ∈ R
5. draw the extent σn,h to which n is suitable to play role Rh, i.e., σn,h ∼ Gamma(σn,h|ασ, βσ).
6. II) For each role Rh ∈ R
7. For each community Ck ∈ C
8. draw the relevance of role Rh to community Ck, i.e., ϕh,k ∼ Gamma(ϕh,k|αϕ, βϕ).
9. III) For each attribute fa ∈ A
10. For each role Rh ∈ R
11. draw the relatedness of attribute fa to role Rh, i.e., πa,h ∼ Gamma(πa,h|απ, βπ).
12. IV) For each role Rh ∈ R
13. For each role Rh′ ∈ R
14. draw the strength of interaction between role Rh and role Rh′ , i.e., ϵh,h′ ∼ Gamma(ϵh,h′ |αϵ, βϵ).
15. For each node n ∈ N
16. For each node n′ ∈ N

Ln,n′ ∼ Poisson(Ln,n′ |δn,n′ ), where δn,n′ is the rate defined by Eq. 2.

• draw the presence/absence of a link Ln,n′ between n and n′ , i.e.,
• VI) For each node n ∈ N
• For each attribute fa ∈ A
• drawwhether or not attribute fa characterizes node n, i.e., Fn,a ∼ Poisson(Fn,a|δn,a), where δn,a is the rate defined by Eq. 3.

Figure 2: The generative process under SCANNER

des of G, i.e., such that 〈n, n′ 〉 ∈ E and, consequently, Ln,n′ = 1. Also, assume that notation z(k,h,h′ ) n,n′ = 1 means that z(k,h,h′ ) n,n′ is the only Poisson count in zn,n′ amounting to 1, whereas all other counts are zero. The probability P (z(k,h,h′ ) n,n′ = 1|Ln,n′ ,Θ,Σ,Υ,Φ) that 〈n, n′ 〉 was established with n and n' playing, respectively, roles Rh and Rh′ within community k is approximated by E[τ (k,h,h′ ) n,n′ ], according to the mean-field approximation. Therefore, 〈n, n′ 〉 can be reasonably explained by the triple (k∗ , h∗ , h′∗ ), such that (k∗ , h∗ , h′∗ ) = arg max(k,h,h′ ) E[τ (k,h,h′ ) ].

Behavioral patterns supplement roles, by unveiling their functioning in the fulfillment of the respective social functions. Here, the strength of interaction between roles Rh and Rh′ is ϵ∗h,h′ ≜ E[ϵh,h′ ].

4.2 Predictive Analysis

The emergence of missing links and node attributes is forecast by associating them with a respective score, that is used to rank their prospective observation. In particular, the score sn,n′ associated with unconnected pairs of nodes n and n′ is the posterior expectation of the corresponding Poissondistribution rate. More precisely, sn,n′ ≜ E[δn,n′ ], where δn,n′ is defined by Eq. 2.

Analogously, the score sn,a regarding the unobserved attribute fa of node n is the posterior expectation of the respective Poisson-distribution rate. Specifically, sn,a ≜ E[δn,a], where δn,a is defined by Eq. 3.

4.3 Descriptive Analysis

SCANNER supports the interpretation of roles and communities by discriminatory characterizations, therefore roles can be characterized by related node attributes. In fact the relatedness of attribute fa to role Rh is π∗ a,h ≜ E[πa,h]. A discriminatory characterization of Rh is, hence, any suitable subset of strongly related attributes.

Communities can be characterized by relevant role affiliations (directly) and pertinent node attributes (indirectly). The relevance of role Rh to community Ck is ϕ∗h,k ≜ E[ϕh,k]. In addition, the pertinence of attribute fa to community Ck is ω∗ a,k ≜ E[∑Hh=1 πa,hϕh,k]. Accordingly, Ck can be discriminatorily characterized in terms of highly relevant roles and/or especially pertinent attributes.

5 The PERISCOPEModel

SCANNER assumes that node attributes are directly affiliated to roles. By contrast, PERISCOPE is a new model conceived to formulate and investigate an important and otherwise unexplored conjecture, i.e., the direct affiliation of node attributes to communities instead of roles. The directed graphical representation of the conditional (in)dependencies between observed and latent variables under PERISCOPE is reported in [Costa and Ortale, 2022] along with the corresponding generative process. Here, we only emphasize that, under PERISCOPE, the inclusion of fa among the attributes of node n is governed by the below rate

6 Conclusions

We presented two new approaches to the exploratory and unsupervised analysis of communities and behavioral roles in networks, whose novelty consists in accounting for node attributes and behavioral role patterns. The devised approaches are based on as many Bayesian probabilistic latent-factor models of networks, namely SCANNER and PERISCOPE. Both assume a generative process, in which the observed network topology and node attributes are statistically dependent on latent network aspects. These include node affiliations to overlapping communities and roles, role affiliations to communities, attribute affiliation either to roles (under SCANNER) or to communities (under PERISCOPE) as well as behavioral role patterns.

An extensive experimentation is carried out on real-world benchmark data sets in [Costa and Ortale, 2022]. Tests reveal that the devised approaches are more accurate in community discovery, link prediction and attribute prediction than several competitors. The devised approaches are also found more accurate in community discovery and link prediction, despite noise or lack of observations in network structure or node attributes. This finding substantiates that the unified modeling and processing of network structure and node attributes makes both the approaches more robust to perturbations. Besides accuracy and sensitivity to perturbations, the scalability of our approaches is also studied in [Costa and Ortale, 2022].