PaperlayerView exact revision on arXiv

Source-linked AI summary

Infinite Edge Partition Models for Overlapping Community Detection and Link Prediction

Mingyuan Zhou

arXiv:1501.06218v2stat.MLcs.SI

TL;DR

The paper addresses community detection and link prediction in relational networks where communities may overlap and exhibit homophily or stochastic equivalence. It proposes hierarchical gamma process edge partition models with Bernoulli-Poisson factorization, and reports scalable computation and strong performance across four real networks.

  • Problem

    Existing methods do not simultaneously provide generative link prediction, overlapping communities, flexible homophily and stochastic-equivalence modeling, automatic community-number selection, and scalable inference for sparse networks.

  • Method

    The paper proposes hierarchical and simplified gamma process edge partition models that factorize binary adjacency matrices through Bernoulli-Poisson latent counts and infer communities nonparametrically.

  • Results

    Experiments on four real networks demonstrate scalability and state-of-the-art performance, with HGP-EPM achieving the best overall performance on Protein230.

  • Takeaways & Limitations

    Partitioning observed edges supports overlapping community discovery, community-interaction analysis, missing-edge prediction, and computation focused on linked node pairs.

  • Takeaways & Limitations

    The infinite interaction structure requires finite total interaction mass almost surely and may require structural regularization.

Abstract

from arXiv · show

A hierarchical gamma process infinite edge partition model is proposed to factorize the binary adjacency matrix of an unweighted undirected relational network under a Bernoulli-Poisson link. The model describes both homophily and stochastic equivalence, and is scalable to big sparse networks by focusing its computation on pairs of linked nodes. It can not only discover overlapping communities and inter-community interactions, but also predict missing edges. A simplified version omitting inter-community interactions is also provided and we reveal its interesting connections to existing models. The number of communities is automatically inferred in a nonparametric Bayesian manner, and efficient inference via Gibbs sampling is derived using novel data augmentation techniques. Experimental results on four real networks demonstrate the models' scalability and state-of-the-art performance.

1 INTRODUCTION

The paper introduces nonparametric Bayesian edge partition models for detecting overlapping communities, modeling homophily and stochastic equivalence, and predicting missing links while inferring community number automatically.

  • Existing heuristic community-detection methods generally lack generative modeling for network simulation and missing-edge prediction, while community-number selection remains difficult.
  • The proposed models fit unweighted undirected networks to discover overlapping communities and community-community interactions, predict missing edges, and infer the number of communities from data.
  • The edge partition model clusters observed edges rather than nodes or all possible edges, yielding overlapping node affiliations with O(d̄N) computation instead of MMSB’s O(N^2).
  • The hierarchical gamma process EPM uses a Bernoulli-Poisson link and infinite feature and interaction structures to model both homophily and stochastic equivalence.
  • The models extend prior approaches through latent-count edge partitioning, hierarchical gamma-process communities, and unbounded nonnegative feature matrices.

2 FACTOR ANALYSIS AND BERNOULLI-POISSON LINK

The paper factorizes network relations through Poisson latent counts and a Bernoulli-Poisson link, partitioning edge counts by community interactions to represent overlapping structure efficiently.

  • 2.1 Poisson Factor Analysis: The Poisson factor model explains node-pair interaction counts using node-community affiliations and community-community interaction rates.Feature strengths measure node affiliations, while rate parameters capture intra- and inter-community interactions.
  • 2.1 Poisson Factor Analysis: Setting inter-community rates to zero produces a simpler assortative model that emphasizes homophilous links and enables simpler inference.
  • 2.1 Poisson Factor Analysis: The paper addresses prior Poisson-factor limitations by providing principled nonparametric community-number selection and Bayesian inference without fabricated self-edges.
  • 2.2 Bernoulli-Poisson Link: The Bernoulli-Poisson link thresholds latent counts at one, making a binary edge represent at least one underlying interaction and enabling count-data tools.
  • 2.2 Bernoulli-Poisson Link: For an observed edge, the latent count follows a positive truncated Poisson distribution, while an absent edge has count zero almost surely.
  • 2.3 Overlapping Community Structures: The EPM partitions each edge’s latent count across community-community pairs, thereby assigning nodes to multiple communities and supporting block-structured adjacency representations.

3 EDGE PARTITION MODELS

The HGP-EPM factorizes network edges through infinitely many node-community affiliations and community interaction rates, with a finite-truncation implementation and Bayesian inference. Its GP-EPM simplification removes inter-community interactions, while both models support dense overlaps and connect to existing affiliation models.

  • Hierarchical Gamma Process: The HGP-EPM uses infinite node-community feature vectors and an infinite symmetric rate matrix to model intra- and inter-community interactions.The Bernoulli-Poisson construction links observed edges to latent counts that are factorized through community affiliations and interaction rates.
  • Hierarchical Gamma Process: The relational gamma process supplies countably infinite atoms with shrinkage, while a finite truncation K approximates the infinite model for implementation.The expected number of atoms above a weight threshold decreases as the threshold increases, and K is chosen large enough for approximation.
  • Gamma Process EPM: The GP-EPM sets inter-community rates to zero, favoring assortative networks, whereas the HGP-EPM retains interactions between distinct communities.The HGP-EPM's square rate matrix is not normalized and is inferred jointly with community weights.
  • Connections and overlap: Both EPMs allow overlapping communities whose shared regions can be denser than the communities themselves, unlike the restrictive assumption identified for several earlier methods.The GP-EPM also becomes closely related to the AGM under binary community affiliations, while the proposed models retain nonparametric Bayesian inference.
  • Model assumptions: The models assume an unweighted undirected network with exchangeable nodes and exclude self-links.Under this setting, only one direction of each node pair is represented because b_ji ≡ b_ij.
  • Inference: Gibbs updates for nearly all parameters follow from Bernoulli-Poisson augmentation, gamma-Poisson conjugacy, and augment-and-conquer techniques.The remaining γ0 parameter is sampled with an independence-chain Metropolis-Hastings proposal.

4 EXPERIMENTAL RESULTS

Across four real networks, the HGP-EPM generally achieved the strongest link-prediction performance while modeling both homophily and stochastic equivalence. The EPMs also supported interpretable overlapping-community structure and sparse-network computation, with performance varying by network structure.

  • 4 EXPERIMENTAL RESULTS: The experiments held out 20% of node pairs, used identical five training-testing partitions across algorithms, and evaluated mean AUC-ROC and AUC-PR.AUC-PR was emphasized because it is more sensitive to the proportion of true edges among highly ranked predictions.
  • 4 EXPERIMENTAL RESULTS: The HGP-EPM had the best overall performance on Protein230 and Yeast, while the HGP-EPM and GP-EPM both performed well on NIPS12.On NIPS234, the GP-EPM and HGP-EPM had the best overall performance; the simpler GP-EPM was sufficient because that network mainly exhibited homophily.
  • 4.1 Protein230 Network: On Protein230, HGP-EPM accurately modeled both diagonal and off-diagonal dense regions, capturing homophily and stochastic equivalence better than GP-EPM and IRM.GP-EPM created nonexistent blocks to fit off-diagonal interactions, whereas IRM overlooked small communities along the diagonal.
  • 4.1 Protein230 Network: The HGP-EPM inferred roughly 30 meaningful latent feature vectors and represented nodes with potentially strong affiliations to multiple communities.Its interaction-rate matrix also exposed distinct intra- and inter-community strengths, including dense connections between the two largest communities.

5 CONCLUSIONS

The paper proposes infinite edge partition models for unweighted undirected networks, combining overlapping-community discovery, interaction modeling, and link prediction with scalable inference.

  • The hierarchical gamma process EPM models homophily and stochastic equivalence using infinitely many communities and an infinite interaction-rate matrix.A Bernoulli-Poisson link assigns latent counts to binary edges, which are partitioned across community pairs.
  • The model naturally represents overlapping communities by partitioning each edge’s latent count according to the affiliations of both endpoint nodes.
  • The simpler gamma process EPM omits inter-community interactions and performs well on assortative networks.It has reduced ability to model stochastic equivalence.
  • Closed-form MCMC inference and sparse-network computation make the infinite EPMs scalable to networks with thousands of nodes.
  • Experiments on four real networks illustrate the models’ mechanisms, interpretable latent representations, and state-of-the-art performance.

A Proof for Lemma 1

The proof derives the relevant expectation using total expectation and Campbell’s theorem, then completes it by substituting moments of the gamma process.

  • The proof applies the law of total expectation as an intermediate step.
  • Campbell’s theorem is used to evaluate the expectation over the gamma-process construction.
  • The proof concludes by substituting E[G(Ω)] = γ0/c0 and E[G^2(Ω)] = γ0^2/c0^2 + γ0/c0^2.

B MCMC Inference for HGP-EPM

HGP-EPM inference alternates latent-count, community-assignment, and parameter updates using Poisson, multinomial, gamma, and auxiliary-variable constructions.

  • Latent edge counts are sampled for each observed binary edge and then partitioned across community pairs using Poisson–multinomial relationships.
  • The inference samples node-community weights, auxiliary variables, and community interaction rates using negative-binomial augmentation and gamma-Poisson conjugacy.
  • The mass parameter γ0 can tune the prior preference for the number of active communities, with γ0 ∼ Gam(1, 1) used in the experiments.
  • For the considered networks, the relevant probability is usually greater than 50%.
  • Each MCMC iteration proceeds through the HGP-EPM updates from equations (18) to (25).

C Gamma Process EPM

The gamma process EPM simplifies HGP-EPM by removing inter-community interactions, making inference faster but limiting its ability to model stochastic equivalence.

  • The gamma process EPM sets inter-community interactions aside, yielding a simpler hierarchical model and faster computation.
  • This simplification reduces the model’s ability to represent stochastic equivalence.
  • The simplified model performs well on assortative networks but not necessarily on disassortative networks.

C.1 Hierarchical Model

The hierarchical model uses a truncated gamma process formulation that approximates the infinite model as the truncation level grows. Gamma priors are imposed on the stated parameters.

  • C.1 Hierarchical Model: The truncated gamma process EPM is expressed through a finite approximation to the hierarchical model.
  • C.1 Hierarchical Model: As K →∞, the truncated gamma process recovers the exact gamma process with a finite and continuous base measure.The model is typically approximated with a sufficiently large finite K.
  • C.1 Hierarchical Model: A Gam(1, 1) prior is imposed on c0 and ci in the truncated formulation.

C.2 Gibbs Sampling

The Gibbs sampler uses latent-count definitions, Poisson additive properties, and marginalization steps to derive parameter updates. Closed-form updates are obtained for all model parameters but are omitted.

  • C.2 Gibbs Sampling: The inference derivation defines latent counts mi·k and m··k as auxiliary quantities.
  • C.2 Gibbs Sampling: The derivation exploits the Poisson additive property and marginalizes rk to obtain intermediate inference expressions.
  • C.2 Gibbs Sampling: Closed-form Gibbs sampling updates for all model parameters can be derived from the latent-count and marginalization identities.The update equations are omitted for brevity.

D Gamma Process AGM

The hierarchical gamma process AGM is closely related to the gamma process EPM and is inferred with Gibbs sampling. Its φik updates depend on whether the latent count mi·k is positive.

  • D Gamma Process AGM: The hierarchical gamma process AGM is formulated as a model closely related to the truncated gamma process EPM.
  • D Gamma Process AGM: When mi·k > 0, φik equals one almost surely; when mi·k = 0, φik is sampled from a Bernoulli distribution.
  • D Gamma Process AGM: Gibbs updates for rk, γ0, and c0 use the same sampling procedure as in the gamma process EPM, while other updates exploit conditional conjugacy.The update equations for the remaining parameters are omitted.
Loading 1501.06218v2…