Contribution
It combines the stochastic blockmodel, in which each node belongs to one block and edges depend on the pair of blocks, with mixed membership, in which each node has a vector of memberships. The combination keeps relational dependence by drawing, for each interaction, a block for each party from its own membership vector. It adds a sparsity parameter separating rare contact from block structure, a nested variational EM algorithm whose memory is NK + 2K scalars per cycle, and applications to a monastery, a school friendship network and a yeast protein-interaction network.
Key insight
A node does not have a role. It has a distribution over roles, and in each interaction it takes one: “the group membership of each node is context dependent. That is, each node may assume different membership when interacting to or being interacted by different peers.” Marginally, the probability of an edge from p to q is π_pᵀBπ_q, a bilinear form in the two nodes’ memberships with the block matrix in the middle. That makes the model a latent-space model with simplex-valued positions and an arbitrary interaction matrix, which is how §5 relates it to Hoff, Raftery and Handcock’s models.
Assumptions
- A directed binary graph on N nodes; Y(p, q) ∈ {0, 1} for ordered pairs.
- Memberships. π_p ~ Dirichlet(α) on the K-simplex, K fixed.
- Per-interaction roles. For each ordered pair, z_{p→q} ~ Mult(π_p) and z_{p←q} ~ Mult(π_q), independently across pairs.
- Edges. Y(p, q) ~ Bernoulli((1 − ρ) z_{p→q}ᵀ B z_{p←q}), with B a K × K matrix of rates in [0, 1] and ρ ∈ [0, 1] the sparsity parameter (§2.1).
- Given the memberships, edges are independent across pairs and across replicated graphs (Appendix A).
- Estimation. Empirical Bayes for (α, B) by variational EM on a mean-field family: a Dirichlet for each π_p and a multinomial for each z. K by held-out likelihood on large networks and an approximate BIC on small ones.
- No dynamics, no covariates, no interventions.
Key results
- Marginal edge probability. Summing over the two indicators gives P(Y(p, q) = 1 | π_p, π_q) = (1 − ρ) Σ_{g,h} π_p(g) B(g, h) π_q(h) (Appendix A’s mixture form, with Bernoulli f). Re-derived and checked numerically.
- Variational updates (§3, Appendix B). φ_{p→q,g} ∝ exp(E[log π_{p,g}]
- Σ_h φ_{p←q,h} f(Y(p, q), B(g, h))), and symmetrically; γ̂_{p,k} = α_k + Σ φ_{p→q,k} + Σ φ_{p←q,k}; B̂(g, h) = Σ Y φφ / ((1 − ρ) Σ φφ); α by Newton–Raphson. The nested schedule iterates the pair-level updates to convergence before partially updating γ and B. The naïve schedule “often converged only after many iterations”.
- Sparsity estimator. ρ̂ = Σ_{p,q} (1 − Y(p, q))(Σ_{g,h} φφ) / Σ_{p,q} Σ_{g,h} φφ. Since each φ vector sums to one, Σ_{g,h} φ_{p→q,g}φ_{p←q,h} = 1 for every pair, so ρ̂ as printed is the fraction of absent edges, whatever the φ. Footnote 9 says it equals the density-based ρ̃ “in the case of single membership”. As printed, the two are always equal. Checked numerically.
- Monks (§2.3). Sampson’s 18 novices. Approximate BIC selects three groups, the number Sampson identified, with the Young Turks, Loyal Opposition and Outcasts at the simplex’s corners and John Bosco and Gregory between them. “Amand’s uncertain affiliation, however, is not captured.”
- Simulations (§4.1). Graphs of 100, 300 and 600 nodes from MMSB with 4, 10 and 20 blocks and α = 0.05, 0.1, 0.25. Reordering rows by most likely membership “accurately reveals the original blockmodel” (Fig. 6, by eye). The nested schedule reached the same likelihood faster than the naïve one on 100 nodes and 4 blocks over 26 paired runs (Fig. 7 left). In one 300-node example, five-fold held-out likelihood peaked at the true K = 10 (Fig. 7 right).
- School friendship (§4.2). Add Health, 69 students in grades 7–12. BIC suggests K = 6; α̂ = 0.0487, ρ̂ = 0.936, a nearly diagonal B. “Few students display mixed membership.” Assigning each student to the grade of their highest posterior membership, MMSB matches 63 of 69, against 57 for a mixture blockmodel and 37 for a latent space cluster model (Table 1).
- Yeast proteins (§4.3). 871 proteins in MIPS’s hand-curated
interactions, each with about 2.4 of 15 top-level MIPS functions.
- With K = 15, blocks were mapped to functions greedily on 87 proteins, memberships thresholded at the 95th percentile, and predicted annotations on the other 90% scored: “about 87%” accuracy, against “about 70%” for random guessing at the right proportions.
- With K = 50, chosen by held-out likelihood among K from 2 to 255, predicted interactions thresholded at ten levels have higher functional precision by gene ontology co-annotation than the MIPS collection itself at low recall (Fig. 13, Table 3).
- The identifiability claim (§5). “The model decouples the observed connectivity patterns into two sources of variability, B, Πs, that are apparently in competition for explaining the data, possibly raising an identifiability issue. This is not the case, however, as the blockmodel B captures global/asymmetric relations, while the mixed membership vectors Πs capture local/symmetric relations. This difference practically eliminates the issue, unless there is no signal in the data to begin with.” No argument beyond this is given.
- A limitation the authors name (§5). The model “does not readily generate hubs” or “networks with skewed degree distributions”.
Claims
| id | claim | strength | support |
|---|---|---|---|
| C1 | MMSB lets a node play different latent roles in different interactions, with marginal edge probability π_pᵀBπ_q | strong | the generative process, §2; Appendix A |
| C2 | Nested variational EM converges faster than the naïve schedule at equal likelihood, in less memory | moderate | Fig. 7, one setting, 26 paired runs |
| C3 | Memberships and B are recovered from simulated MMSB graphs | moderate | Fig. 6 by eye; one held-out-K example |
| C4 | On the school network MMSB matches grades better than a mixture blockmodel and a latent space cluster model | moderate | Table 1, one network, highest-membership assignment |
| C5 | On yeast proteins, memberships carry functional information | weak to moderate | §4.3.2’s accuracy against a weak baseline (see Limitations); §4.3.3’s precision–recall |
| C6 | B and the memberships do not compete, because B is global and asymmetric and the memberships local and symmetric | weak, and false as a statement about the likelihood | asserted in §5; see THEORY-993 |
| C7 | MMSB’s estimate of ρ separates zeros due to rare contact from zeros due to block structure | weak | §2.1. In the marginal likelihood ρ enters only as (1 − ρ)B, and the printed estimator is the zero fraction (THEORY-993) |
Concepts
- Mixed membership vector π_p: “the expected proportion of times node n instantiates the connectivity pattern of group k” (Fig. 1’s caption).
- Interaction-specific membership z_{p→q}: the single block p takes in its interaction with q.
- Summarizing and de-noising (§2.2): predicting edges from (B, Π), or re-weighting observed edges with (B, Z).
- Sparsity parameter ρ: the share of non-interactions attributed to “limited opportunities of contact” rather than to blocks.
Connections
It extends the stochastic blockmodel (Holland and Leinhardt; Wang and Wong; Snijders and Nowicki) and its Dirichlet-process form (Kemp et al.; Xu et al.), and the mixed-membership models of Erosheva and of Pritchard, Stephens and Donnelly, of which LDA is one. It compares itself with latent space models (Hoff, Raftery and Handcock 2002; Handcock et al. 2007), whose edge probability uses π_pᵀIπ_q with Gaussian positions. A nonparametric version would need memberships from a hierarchical Dirichlet process, which the authors propose and do not build. hLDA’s paper (LIT-1542) cites it among flat mixed-membership models of non-text data.
Bearing on the record
- QUESTION-276, condition 4. The LIT says a mixed-membership blockmodel of the communication and authority graph is the baseline inferred structure must beat. The reading supports that and sharpens it. MMSB is a static model of one graph’s edges, independent given memberships, with no dynamics and no interventions, so it cannot itself predict “the effect of changing an authorization pathway”. As a baseline it has to be extended to the outcome that is to be predicted. And it “does not readily generate hubs”, which an authorization graph with managers has, so a fitted MMSB would misdescribe the graph it is meant to summarize.
- QUESTION-276, condition 2 (overlap). MMSB’s overlap is proportional: π_p sums to one, so a node’s roles compete for its interactions. T19’s participation without that constraint is a feature allocation’s kind of overlap, not this one. MMSB’s per-interaction role, one block per partner, is closer than any of the batch’s models to the idea of a member taking different perspectives in different interactions.
- QUESTION-276, “without their number being fixed”. K is chosen by BIC or held-out likelihood, not inferred. In the one simulated example the held-out peak was at the true K.
- CLAIM-148 and CLAIM-135. The paper’s one passage on identifiability asserts that B and the memberships do not compete. Given the graph they do, along a continuum of changes of block basis, and the sparsity factor is not identified at all apart from B’s scale (THEORY-993). That is CLAIM-148’s gauge in bilinear form, and it puts the paper’s readings of blocks (factions, grades, protein functions) at CLAIM-135’s first achievement plus whatever the Dirichlet family adds. The PPI mapping “estimate[s] a permutation” of blocks to functions, which is exactly the part of the gauge the paper admits.
- CLAIM-427. §4.3.2 is the one place in the batch where inferred memberships are checked against labels the model never saw, the MIPS annotations. That is the kind of external check CLAIM-427 asks for, done weakly (THEORY-1008, Proposed).
- CASE-166. Its analyzer found modes with the number of factors fixed. MMSB would find blocks of the interaction graph with K chosen by criterion. Neither separates a block of members who interact from a block of members who respond alike to a common driver, unless the common driver also makes them link. Condition 3 of QUESTION-276 is untouched by this paper.
- CLAIM-454. A block is a pattern of who links to whom. It is relational, unlike a feature allocation, so it holds some of what the claim says an allocation leaves open (access). It holds no uptake or authority. The paper’s readings of blocks as factions and functions are by correspondence with external labels.
No instruction for machine-learning practice; nothing for the anthology.
Limitations
- The identifiability claim is unsupported, and false for the likelihood given the memberships (THEORY-993). Whether the empirical-Bayes (α, B) is identified in the marginal likelihood rests on the Dirichlet family of the memberships, which the paper does not examine.
- ρ is confounded with B’s scale. The edge probability depends on ρ and B only through (1 − ρ)B, so ρ is fixed only by the bound B ≤ 1, and the printed ρ̂ is the fraction of zeros regardless of the fit.
- The PPI baseline is weak. With about 2.4 of 15 functions per protein, predicting no function at all would score about 84% if accuracy is per protein–function entry, which the paper does not define. Against that, “about 87%” is a small gain. Random guessing at the right proportions scores about 0.16² + 0.84² ≈ 73%, close to the paper’s “about 70%”, so the per-entry reading is likely. The record’s arithmetic, not the paper’s.
- Simulations judged by eye. No recovery error is reported for π or B.
- No hubs or skewed degrees.
- Variational approximation without a check against MCMC on these data; MCMC is called impractical.
- The arXiv copy was not compared.
Open questions
- Under what conditions on B and the membership distribution are B and Π identified up to permutation? Results on identifiability of mixed membership and latent-structure models (Allman, Matias and Rhodes, named in CLAIM-135, not held) may apply; the paper does not ask.
- Does a dynamic MMSB, fitted to an organization’s interactions over time, predict the effects of interventions on the graph better than the graph’s own history? That would make it the baseline QUESTION-276 needs.
- How does the per-interaction role compare with a feature allocation of the same members, on the same data?