PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Latent Block Structure in Weighted Networks

Christopher Aicher, Abigail Z. Jacobs, Aaron Clauset

arXiv:1404.0431v2stat.MLcs.SIphysics.data-anphysics.soc-ph

TL;DR

Unweighted community-detection methods can discard informative edge weights, limiting recovery of latent structure in weighted networks. The paper introduces the WSBM, which models edge presence and weights using exponential-family distributions and learns its posterior with a variational Bayes algorithm. Across real-world networks, it performs at least as well as alternatives on edge-existence prediction and better on edge-weight prediction.

  • Problem

    Unweighted network models often discard interaction weights through thresholding, although weights may contain information about latent community structure.

  • Method

    The WSBM models edge existence and edge weights jointly, with edge-weight distributions from an exponential family, and uses variational Bayes for efficient inference.

  • Results

    Across real-world weighted networks, the WSBM performs as well as alternatives on edge-existence prediction and outperforms them on edge-weight prediction.

  • Takeaways & Limitations

    The WSBM enables latent group structures to be discovered in weighted networks without applying thresholds before analysis.

  • Takeaways & Limitations

    Degree correction improves modeling of heterogeneous degree distributions but does not model heterogeneous within-bundle weight distributions; a strength-corrected model is left for future work.

Abstract

from arXiv · show

Community detection is an important task in network analysis, in which we aim to learn a network partition that groups together vertices with similar community-level connectivity patterns. By finding such groups of vertices with similar structural roles, we extract a compact representation of the network's large-scale structure, which can facilitate its scientific interpretation and the prediction of unknown or future interactions. Popular approaches, including the stochastic block model, assume edges are unweighted, which limits their utility by throwing away potentially useful information. We introduce the `weighted stochastic block model' (WSBM), which generalizes the stochastic block model to networks with edge weights drawn from any exponential family distribution. This model learns from both the presence and weight of edges, allowing it to discover structure that would otherwise be hidden when weights are discarded or thresholded. We describe a Bayesian variational algorithm for efficiently approximating this model's posterior distribution over latent block structures. We then evaluate the WSBM's performance on both edge-existence and edge-weight prediction tasks for a set of real-world weighted networks. In all cases, the WSBM performs as well or better than the best alternatives on these tasks.

1 Introduction

Community detection seeks compact representations of network structure by grouping vertices with similar connectivity roles. The WSBM addresses information loss from thresholding weighted networks by modeling edge presence and weights directly.

  • Motivation: Community detection groups vertices with similar group-level connectivity patterns to summarize large-scale network structure.The resulting communities can support network interpretation and prediction of unknown or future interactions.
  • Stochastic block models: The SBM models unweighted edges using latent vertex groups and group-pair-specific edge probabilities.Its flexible block-probability matrix can represent assortative, disassortative, core-periphery, and ordered connectivity patterns.
  • Information loss: Thresholding weighted networks can discard information and prevent recovery of the true community structure.In the example network, no threshold yields the correct inference because at most three weight groups remain instead of four planted groups.
  • Weighted stochastic block model: The WSBM generalizes the SBM by modeling each weighted edge with an exponential-family distribution whose parameters depend on endpoint group memberships.This approach uses both edge presence and edge weight information and includes standard distributions such as normal and exponential forms.
  • Evaluation: A variational Bayes algorithm learns WSBM parameters, which are evaluated on edge-existence and edge-weight prediction across real-world weighted networks.The WSBM matches alternatives on edge-existence prediction and outperforms all alternatives on edge-weight prediction.

2 Weighted Stochastic Block Model

The WSBM generalizes the SBM by modeling weighted edges with exponential-family distributions while retaining latent group structure and stochastic equivalence. Its sparse and degree-corrected extensions separately represent observed interactions, edge weights, and heterogeneous degree distributions.

  • Weighted model: The WSBM assigns vertices to latent groups and models each edge weight using parameters determined by the groups of its endpoints.It is a generalization of the SBM in which each edge-bundle parameter governs an exponential-family weight distribution.
  • Sparse weighted graphs: The complete-graph construction is insufficient for most sparse real-world networks, where only O(n) vertex pairs have connections.The paper introduces a sparse formulation to incorporate sparsity and obtain more scalable inference algorithms.
  • Sparse weighted graphs: The sparse formulation distinguishes non-edges, zero-weight edges, and unobserved interactions before modeling existence with a Bernoulli variable and weights with an exponential-family distribution.This distinction is assumed to be available in the input data; unobserved interactions do not contribute as observed interactions.
  • Sparse weighted graphs: The model can combine information from edge existence and edge weight, with α = 1 reducing to the SBM and 0 < α < 1 incorporating both sources.In practice, α = 1/2 often gives equal weight to edge existence and weights, while learning α is left for future work.
  • Degree correction: Degree correction adds vertex edge-propensity parameters so groups can contain heterogeneous degree distributions while preserving similar group-level connectivity patterns conditioned on propensity.The degree-corrected weighted model replaces the SBM contribution with the DCBM contribution and can include in- and out-propensities for directed networks.
  • Degree correction: The degree-corrected weighted model addresses degree heterogeneity but does not model heterogeneous weight distributions within edge bundles through vertex strength.A strength-corrected extension is not considered and is left for future work.

3 Learning Latent Block Structure

The WSBM is learned with Bayesian variational inference, which regularizes continuous edge-weight models and alternates updates for edge-bundle parameters and vertex memberships. Model selection uses a marginal-log-likelihood lower bound whose maximization tracks recovery of the planted structure.

  • Bayesian regularization: Continuous-weight maximum likelihood can become degenerate when a uniform edge bundle yields a zero variance estimate.Small groups with identical inter-group weights can create this situation; Bernoulli-valued SBM edges do not have the same degeneracy.
  • Bayesian regularization: Bayesian regularization assigns priors to parameters, preventing over-fitting to degenerate solutions through the posterior.The posterior combines the likelihood with prior information about group labels and edge-bundle parameters.
  • Variational objective: The variational approximation factorizes as q(z, θ) = qz(z)qθ(θ) and is optimized by maximizing a functional equivalent to minimizing KL divergence from the posterior.The functional combines expected log-likelihood with a negative KL-divergence term from the prior.
  • Conjugate distributions: Conjugate priors update each edge-bundle parameter with observed sufficient statistics, treating prior parameters as pseudo-observations that avoid invalid estimates.This regularization applies even when an edge bundle is small or has uniform weights.
  • Optimization algorithm: The algorithm alternates edge-bundle and vertex-label updates, with vertex memberships iterated to convergence and the membership probabilities normalized.Updating edge-bundle parameters takes O(nK^2) time, while iterative membership updates are the limiting step.
  • Selecting K with Bayes factors: Across candidate group counts, approximate marginal log-likelihood and NMI are both maximized at or near the true number of groups.The experiment varies inferred K from 1 to 14 for networks generated with K = 8 groups and different edge-weight variances.

4 Experimental Evaluation

The experiments show that edge existence and edge weights can encode distinct latent structures, while a balanced WSBM can perform strongly across both prediction tasks. Evaluation on real-world weighted networks compares WSBM variants with alternative models under controlled cross-validation.

  • 4.1 Edge weight versus edge existence latent group structure: The NFL-2009 network uses 32 teams as vertices, game participation as edges, and average score difference as edge weight.The models use K = 4 groups and a normal distribution for edge weights; α=1 ignores weights, whereas α=0 ignores edge presence.
  • 4.1 Edge weight versus edge existence latent group structure: The SBM recovers NFL conference and division structure because division membership explains which teams played each other.Its empty off-diagonal blocks correspond to division pairs that never play each other.
  • 4.1 Edge weight versus edge existence latent group structure: The pure WSBM recovers a cross-conference ordering by general skill, with within-group score differences tending toward zero.The upper-left group leads lower groups by a mean of 11 points, illustrating how weights reveal structure distinct from edge existence.
  • 4.1 Edge weight versus edge existence latent group structure: The balanced WSBM combines edge existence and weight information, allowing practitioners to target either latent structure or both simultaneously.The model’s α parameter interpolates between the SBM and pure WSBM settings.
  • 4.2 Predicting edge existence and weight: Across five real-world networks, models are evaluated with 80/20 cross-validation, K = 4 latent groups, and average MSE over 25 trials.Table 1 reports edge-prediction MSE, while Table 2 reports normalized weight-prediction MSE.
  • 4.2 Predicting edge existence and weight: The SBM and balanced WSBM are strongest for edge-existence prediction, while the pure WSBM is strongest for edge-weight prediction; balanced WSBM also substantially improves weight prediction over SBM.The balanced WSBM is as good or nearly as good as SBM on edge prediction and better on weight prediction.

5 Discussion

The WSBM preserves edge existence and weight information while providing efficient inference and strong prediction performance. Its usefulness extends to settings where the relevant latent structure or informative edge signal is unknown, although important theoretical questions remain open.

  • The WSBM generalizes the SBM to weighted sparse networks without requiring thresholding, preserving information for characterizing large-scale structure.It provides a statistically principled approach to community detection using weighted edges.
  • The model’s mixing parameter α controls the balance between learning from edge existence and edge weight information.The balanced setting α=0.5 performed as well or nearly as well as the best alternative block model.
  • WSBM-inferred groups can differ from groups found using only the unweighted network, and both latent structures may provide distinct insights.The network types for which weight information yields distinct partition structure remain an open question.
  • The variational algorithm is relatively scalable and should be applicable to networks with millions of vertices or more.Alternative inference methods must address technical problems caused by edge-weight distributions.
  • Open extensions include mixed memberships, bipartite and dynamic networks, heterogeneous edge distributions, and richer auxiliary information.The theoretical effect of weight information on latent-group detectability also remains open.

Funding

The work was supported by the U.S. Air Force Office of Scientific Research and the Defense Advanced Research Projects Agency.

  • Funding came from the U.S. Air Force Office of Scientific Research and DARPA.The grant number was FA9550-12-1-0432.

B Exponential Families

The appendix defines exponential-family distributions and summarizes their likelihood-relevant statistics, examples, and conjugate-prior structure. These properties support the WSBM’s distributional formulation and Bayesian inference.

  • An exponential family is a parametric distribution collection represented using a base function, sufficient statistic, and natural parameter map.The distributions are written as f(x | θ) = h(x) exp(T(x) · η(θ)).
  • Only the sufficient statistic T and natural parameters η directly affect the log-likelihood because h(x) contributes an additive constant.T and η may be vector-valued.
  • Normal, exponential, gamma, log-normal, Pareto, binomial, multinomial, Poisson, and beta distributions are examples of exponential families.The Uniform distribution and certain mixture distributions are identified as non-exponential-family examples.
  • The log-partition function may be absorbed into the sufficient-statistic and natural-parameter term to keep notation compact.The appendix notes this as a notational convention.
  • Exponential families admit conveniently written conjugate priors, whose hyperparameters can be interpreted as pseudo-observations of the sufficient statistic.The prior includes a normalizing constant.

C Belief Propagation Derivation

The belief-propagation derivation replaces the variational posterior with pairwise approximations and optimizes an objective combining likelihood and prior terms. It uses locally tree-like assumptions to obtain message-passing updates, which are effective for sparse but not dense networks.

  • Posterior approximation: Mean-field variational Bayes assumes independently distributed vertex labels, whereas belief propagation uses pairwise approximations to the posterior.Pairwise terms are represented by joint probabilities µij.
  • Posterior approximation: Normalizing the pairwise posterior approximation is generally difficult because each vertex appears once for every incident edge.Exact normalization is available for trees after accounting for this repetition.
  • Posterior approximation: Because the WSBM factor graph is not a tree, the tree-based pairwise form is not necessarily exact.The derivation therefore adopts a loopy belief-propagation approximation.
  • Objective and approximation: The variational objective combines an expected log-likelihood term with a prior regularizer term.The objective is optimized as a variational approximation to the data likelihood.
  • Update equations: Lagrange multipliers enforce normalization and marginalization constraints on the variational parameters.Differentiating the constrained objective yields update equations for µi and µij.
  • Update equations: The algorithm updates messages and group-membership parameters iteratively until convergence, with BP requiring O((m + n)K^2) time per iteration.Here m=|E| is the number of observed edges or interactions.

D Modifications for Sparse Weighted Graphs

The algorithms are adapted for graphs where weighted and missing edges are sparse, while non-edges may remain dense. The modifications exploit edge-existence structure to retain O(nK^2) running time.

  • The sparse-graph treatment modifies variational Bayes and loopy BP updates for edge bundles and vertex memberships.The procedure introduces notation, updates τ, and then modifies µ updates.
  • The network partitions interactions into weighted edges W, non-edges N, and missing edges M, with observed edges E = W ∪ N.This notation distinguishes observed weighted and unweighted interactions from unobserved ones.
  • Sparse weighted-graph modifications target cases with |W| = O(n), |M| = O(n), and potentially dense non-edges.The algorithms are reorganized around weighted edges, missing edges, and edge-existence structure.
  • Observed-edge degrees and weighted-edge degrees are tracked separately for each vertex.The notation distinguishes in- and out-degrees with respect to weighted edges from those with respect to observed edges.
  • The model uses separate exponential-family distributions for edge weights and edge existence, linked to group pairs through R.The edge-weight and edge-existence distributions each have fixed functions and parameters.

D.1 Update for τ (edge distribution)

The τ updates separate weighted-edge sufficient statistics from edge-existence statistics. Their complexity is reduced by summing over sparse weighted or missing edges rather than dense interaction sets.

  • The edge-bundle update consists of calculating expected sufficient statistics and then updating τ for each bundle.
  • Weighted τ updates use Eq. (18) across group pairs and take O(K^2(n + mW)) time per iteration.The cost is dominated by summation over the weighted-edge set W.
  • Edge-existence τ updates exploit the last sufficient-statistic dimension, which is 1 for observed edges and avoids summing over W ∪ N.The last dimension is instead updated using Eq. (19), taking O(K^2(n + mM)) time.
  • Degree-corrected edge existence replaces the constant observed-edge statistic with the product of the endpoints’ in- and out-degrees.This substitution changes Eq. (19) by replacing µi(z) with a degree-weighted term.
  • The running time remains unchanged for the corresponding edge-existence update.

D.2 Update for µ (vertex labels)

The µ updates handle weighted edges explicitly and approximate dense non-edge messages using marginal distributions. With sparse weighted and missing edges, all three update steps run in O(nK^2).

  • Weighted-edge vertex-label updates calculate sufficient-statistic derivatives for each weighted edge and group pair in O(K^2mW) time.
  • Loopy BP updates calculate edge evidence, weighted-edge messages, approximate non-edge messages, and vertex-label probabilities.
  • Weighted-edge message updates take O(K^2mW) overall when the weighted neighborhood of each vertex is sparse.Each local step requires O(|∂iW|K^2) calculations.
  • Non-edge messages are approximated by marginal distributions µj(z′), reducing their space and time cost to O(nK).This approximation exploits sparse weighted edges and the near-one non-edge evidence factor in the sparse Bernoulli case.
  • The Poisson and degree-corrected cases are left for future work because their non-edge-message treatment is more complicated.
  • All three steps take O(nK^2) when weighted and missing edges are sparse, although loopy BP’s constant depends on average weighted degree.
Loading 1404.0431v2…