Source-linked AI summary
Uncovering latent structure in valued graphs: A variational approach
Mahendra Mariadassou, Stéphane Robin, Corinne Vacher
TL;DR
The paper addresses the challenge of uncovering latent groups in increasingly large valued graphs, extending approaches developed largely for binary networks. It proposes a covariate-capable mixture model with variational estimation, reports satisfying estimates across simulations, and applies the method to host–parasite networks where phylogenetic relatedness explains similarity better than distributional overlap.
Problem
Growing valued-graph datasets make latent-structure discovery an unsupervised classification problem, while existing methods have primarily addressed binary graphs.
Method
The paper extends the stochastic block model to valued graphs with covariates and uses a variational EM approach to approximate maximum-likelihood estimation.
Results
Simulation estimates are satisfying overall, and the forest-network application finds that phylogenetic relatedness explains parasite-assemblage similarity better than distributional overlap.
Takeaways & Limitations
Accounting for relevant factors can reduce the selected number of groups and distinguish apparent mixture structure from variability explained by phylogenetic relatedness.
Takeaways & Limitations
Broader variational distribution classes may improve accuracy but sacrifice tractability, while identifiability issues prevented classification-error evaluation.
Abstract
from arXiv · showhide
As more and more network-structured data sets are available, the statistical analysis of valued graphs has become common place. Looking for a latent structure is one of the many strategies used to better understand the behavior of a network. Several methods already exist for the binary case. We present a model-based strategy to uncover groups of nodes in valued graphs. This framework can be used for a wide span of parametric random graphs models and allows to include covariates. Variational tools allow us to achieve approximate maximum likelihood estimation of the parameters of these models. We provide a simulation study showing that our estimation method performs well over a broad range of situations. We apply this method to analyze host--parasite interaction networks in forest ecosystems.
1. Introduction.
The paper develops a model-based strategy for discovering latent groups in valued graphs, extending binary-network methods while allowing covariates and approximate likelihood estimation.
- Motivation: Community detection frames latent-structure discovery as an unsupervised classification problem requiring efficient estimation for growing data sets.
- Related work: Existing greedy and spectral methods assume strong within-group connectivity and weak between-group connectivity, which need not characterize all node groups.
- Motivation: Valued graphs retain edge intensity and specific edge features that binary representations omit.This supports modeling richer interaction information when estimating network structure.
- Contribution: The proposed extension uses a general mixture model for connection intensities among latent classes and accommodates possible covariates.
- Contribution: A variational EM approach provides approximate maximum likelihood estimation, followed by synthetic-data evaluation and application to host–parasite networks in forests.
2. Mixture model.
The mixture model assigns nodes to latent groups and models valued edges through group-specific parametric distributions, with optional covariate effects tailored to ecological interaction networks.
- Model and notation: Each node belongs to one of Q latent groups, while edges are conditionally independent given node-group assignments.
- Model and notation: The model is specified by mixture proportions α and a connectivity matrix θ, up to relabeling of the classes.
- Model and notation: The framework supports directed and undirected graphs, although directed models assume conditional independence between opposite edges.
- Ecological models: For tree networks, Poisson models represent edge values as counts of common fungal species hosted by two tree species.
- Ecological models: PRMI models covariate effects within each class pair, whereas PRMH models a common covariate effect competing globally with residual group structure.
- Ecological models: The same mixture and regression-mixture framework is applied to fungal interaction networks and can handle other data types with analogous models.
3. Likelihood and variational EM.
Because latent-group dependence makes the ordinary likelihood difficult to optimize, the paper replaces exact inference with a variational lower-bound strategy and fully factorized approximations.
- Likelihood: The incomplete-data likelihood requires summing over Q^n latent assignments, making direct calculation intractable.
- Likelihood: The standard EM algorithm also becomes intractable because network edges are strongly dependent in the latent-label conditional distribution.
- Variational EM: Variational EM maximizes a lower bound on the incomplete-data log-likelihood jointly over model parameters and an approximating distribution.
- Variational EM: Restricting the approximating distribution to fully factorized node-wise multinomials makes the objective tractable through first- and second-order expectations.
- Variational EM: Broader variational distributions could tighten the bound, but their entropy may become intractable; tighter approximations therefore trade accuracy for tractability.
4. Parameter estimation.
The paper estimates latent-group model parameters by maximizing a tractable variational lower bound through iterative optimization of group assignments and model parameters, while using ICL to select the number of groups.
- Variational approximation: The variational estimate maximizes J(R_X,γ) over factorized distributions R_X, providing an approximate maximum-likelihood strategy.Restricting R_X to factorized distributions makes the objective tractable and yields a lower bound of the log-likelihood.
- Estimation algorithm: The two-step algorithm alternates optimization of the variational distribution over group assignments and the model parameter γ.The optimization proceeds iteratively because simultaneous optimization is too difficult.
- Practical limitation: The iterative procedure converges only to a local optimum, making initialization of γ or R_X crucial; hierarchical clustering is reported as a useful starting strategy.This creates a practical dependence on the starting point when avoiding local optima.
- Optimization steps: For fixed γ, the variational parameters are obtained from a fixed-point relation iterated until convergence.This optimization is performed under the constraint that each node’s assignment probabilities sum to 1.
- Optimization steps: For fixed R_X, α and θ are optimized subject to mixture-proportion constraints, with model-specific procedures for Poisson and Poisson-regression models.The Poisson model has a straightforward optimum for λ_qℓ, while the regression variants use standard generalized-linear-model optimization procedures.
- Model selection: ICL selects the number of latent classes by approximating the complete-data likelihood while accounting for parameter dimensions and graph size.For θ, the data scale is n(n−1), whereas mixture proportions scale with n; the penalty depends on the model-specific number of independent parameters.
5. Simulation study.
Simulations evaluate parameter estimation and class-number selection across network sizes, class proportions, connection contrasts, and mean intensities. Estimation improves with larger graphs, while class imbalance and weak group separation create the main difficulties; ICL generally selects the correct class count for n > 100.
- Simulation design: The study simulates undirected networks with n = 100 or 500 and Q = 3 classes, varying proportions, connection contrast γ, and mean intensity λ.Class proportions range from uniform to α = (80.6%,16.1%,3.3%), with γ ∈ {0.1, 0.5, 0.9, 1.5} and λ ∈ {2,5}.
- Parameter estimation: RMSE is lower for larger n, while a and γ mainly affect estimation error and λ has nearly no effect.In the balanced case, departures for α1 and α3 result from systematically reordering estimated proportions.
- Parameter estimation: Overall estimates are satisfying, especially for diagonal λqq terms, but λ33 is the most difficult intensity parameter to estimate.Only nonredundant λpq parameters are evaluated because the networks are undirected.
- Parameter estimation: In the worst case, n = 100 with a = 0.2, the algorithm cannot distinguish classes 1 and 2, making estimated λ12 close to λ11 and λ22 although its true value is up to ten times smaller.This reflects the difficulty of estimating between-class intensity when classes are highly unbalanced.
- Classification uncertainty: Mean entropy is mainly controlled by γ: when γ is close to 1, the latent classes are almost indistinguishable.For n = 100, mean intensity λ has almost no effect on entropy.
- Model selection: For model selection, ICL almost always selects the correct number of classes when n > 100, but tends to underestimate it when n = 50.The selection study uses Q⋆ = 3 and evaluates candidate Q values across 100 simulations.
6. Uncovering the structure of host–parasite interactions in forest ecosystems.
The study applies mixture models with covariates to valued host–parasite networks, finding that phylogenetic relatedness explains much of tree–fungus interaction structure, whereas distributional overlap does not. Nutritional strategy likewise does not reduce the number of fungal groups, and covariates improve fit while reducing selected classes.
- Method: The analysis uses mixture models for valued host–parasite networks, incorporating species distances as covariates to explain interaction structure.The networks contain 154 parasitic fungal species and 51 tree species, with edge strength defined by shared hosts or parasites.
- Tree network: Seven tree groups were selected without covariates, with several groups composed exclusively of Magnoliophyta or Conipherophyta species.Two groups were exclusively Magnoliophyta, three exclusively Conipherophyta, and two mixed.
- Phylogenetic relatedness: Accounting for taxonomy reduced the selected tree groups from 7 to 4 and removed the association between groups and the two taxonomic classes.The estimated regression coefficient was bβ = −0.317, and genetic distance produced the same result.
- Phylogenetic relatedness: Phylogenetic relatedness accounts for a large part, but not all, of the tree–fungus interaction structure, because four groups remain after controlling for evolutionary history.If phylogeny were the sole source of structure, only one group would be expected.
- Distributional overlap: Geographical distance does not reduce the number of tree groups, suggesting distributional overlap does not explain parasite-assemblage similarity.The result contrasts with the field’s conventional emphasis on short-timescale ecological processes over longer-timescale evolutionary processes.
- Fungal host ranges: For fungal host ranges, taxonomy does not reduce the number of groups, and nutritional strategy also fails to reduce the nine groups selected by the PM model.The authors therefore report no clear nutritional or fungal phylogenetic signal in host-range structure.
- Conclusion: The authors conclude that tree parasite-assemblage similarity is explained more by phylogenetic relatedness than distributional overlap, while fungal host-range determinants remain inconclusive.Accounting for relevant factors decreases the number of groups selected, avoiding artificial inflation by the naive mixture model.
A.1. Other mixture models.
The framework accommodates several valued-graph distributions, including Bernoulli, multinomial, Gaussian, bivariate Gaussian, and regression models with covariates.
- Bernoulli: Bernoulli edges model networks where only edge presence or absence is observed.
- Multinomial: Multinomial edges represent categorical relationship types such as colleague, family, or friend.Directed graphs can encode symmetric-edge dependence by labeling equivalent undirected edges with ordered edge pairs.
- Gaussian: Gaussian models describe real-valued edge intensities, such as passenger traffic between airports.
- Bivariate Gaussian: A bivariate Gaussian specification models dependence between symmetric edge values Xij and Xji.
- Regression: Regression models incorporate edge-level covariates for Gaussian or generalized Poisson and Bernoulli-valued edges.A simple homoskedastic model can use group-specific intercepts and a common regression coefficient when controlling for geography.
- Parameter estimates: Table 6 reports parameter estimates for the listed classical distributions, with estimates interpreted as weighted versions of intuitive quantities.
A.3. Parameter estimates for the fungus interaction network.
Table 7 summarizes group sizes, mean interaction counts, and fungus-network parameter estimates for groups identified with PM.
- Table 7 reports each PM group’s size and mean number of interactions, denoted λ̄.
- For the fungus network, parameter estimates include λqℓ, the mean number of shared host species, and αq, the PM group proportion without covariates.An asterisk marks λqℓ values below 5e–3.
Interaction network between tree and fungal species
The interaction-network dataset contains tree–fungus adjacency data, species lists, and matrices describing genetic, geographical, taxonomic, and nutritional relationships.
- The supplementary file contains the adjacency matrix of interactions between tree and fungal species.
- It includes separate lists of tree species and fungal species.
- The file provides genetic, geographical, and taxonomic distance matrices, plus fungal nutritional-type data.