More Like this

1. Learning Graph Structure from Convolutional Mixtures

   Wasserman, Max; Sihag, Saurabh; Mateos, Gonzalo; Ribeiro, Alejandro (June 2023, Transactions on machine learning research)

   Machine learning frameworks such as graph neural networks typically rely on a given, fixed graph to exploit relational inductive biases and thus effectively learn from network data. However, when said graphs are (partially) unobserved, noisy, or dynamic, the problem of inferring graph structure from data becomes relevant. In this paper, we postulate a graph convolutional relationship between the observed and latent graphs, and formulate the graph structure learning task as a network inverse (deconvolution) problem. In lieu of eigendecomposition-based spectral methods or iterative optimization solutions, we unroll and truncate proximal gradient iterations to arrive at a parameterized neural network architecture that we call a Graph Deconvolution Network (GDN). GDNs can learn a distribution of graphs in a supervised fashion, perform link prediction or edge-weight regression tasks by adapting the loss function, and they are inherently inductive as well as node permutation equivariant. We corroborate GDN’s superior graph learning performance and its generalization to larger graphs using synthetic data in supervised settings. Moreover, we demonstrate the robustness and representation power of GDNs on real world neuroimaging and social network datasets. 

   more » « less
2. Joint inference of multiple graphs from matrix polynomials

   Novarro, M.; Wang, Y.; Marques, A.G.; Uhler, C.; Segarra, S. (January 2022, Journal of machine learning research)

   Inferring graph structure from observations on the nodes is an important and popular network science task. Departing from the more common inference of a single graph, we study the problem of jointly inferring multiple graphs from the observation of signals at their nodes (graph signals), which are assumed to be stationary in the sought graphs. Graph stationarity implies that the mapping between the covariance of the signals and the sparse matrix representing the underlying graph is given by a matrix polynomial. A prominent example is that of Markov random fields, where the inverse of the covariance yields the sparse matrix of interest. From a modeling perspective, stationary graph signals can be used to model linear network processes evolving on a set of (not necessarily known) networks. Leveraging that matrix polynomials commute, a convex optimization method along with sufficient conditions that guarantee the recovery of the true graphs are provided when perfect covariance information is available. Particularly important from an empirical viewpoint, we provide high-probability bounds on the recovery error as a function of the number of signals observed and other key problem parameters. Numerical experiments demonstrate the effectiveness of the proposed method with perfect covariance information as well as its robustness in the noisy regime. 

   more » « less
3. Inferring signed networks from preschoolers’ observed parallel and social play

   https://doi.org/10.1016/j.socnet.2022.07.002  

   Neal, Jennifer Watling; Neal, Zachary P; Durbin, C Emily (October 2022, Social Networks)

   Early childhood is an important developmental period for network formation. However, the observational methods used for measuring young children’s networks present challenges for capturing both positive and negative ties. To overcome these challenges, we explored the use of a bipartite projection backbone model for inferring both negative and positive ties from observational data of children’s play. Using observational data collected in one 3-year-old (N = 17) and one 4-year-old (N = 18) preschool classroom, we examined whether patterns of homophily, triadic closure, and balance in networks inferred using this method matched theoretical and empirical expectations from the early childhood literature. Consistent with this literature, we found that signed networks inferred using a backbone model exhibited gender homophily in positive ties and gender heterophily in negative ties. Additionally, networks inferred from social play exhibited more closed and balanced triads than networks inferred from parallel play. These findings offer evidence of the validity of bipartite projection backbone models for inferring signed networks from preschoolers’ observed play. 

   more » « less
4. Nonparametric Matrix Estimation with One-Sided Covariates

   https://doi.org/10.1109/ISIT50566.2022.9834608  

   Yu, Christina Lee (June 2022, International Symposium on Information Theory)

   Consider the task of matrix estimation, in which we desire to estimate a ground truth matrix given sparse and noisy observations. Each entry is observed independently with probability p, and additionally perturbed with additive observation noise. Assume the (u,i)-th entry of the ground truth matrix can be described by f(α u ,β i ) for some Holder smooth function f. We consider the setting where the row covariates α are unobserved yet the column covariates β are observed. We provide an algorithm and accompanying analysis which shows that our algorithm improves upon naively estimating each row separately when the number of rows is not too small. Furthermore when the matrix is moderately proportioned, our algorithm achieves the minimax optimal nonparametric rate of an oracle algorithm that knows the row covariates. In simulated experiments we show our algorithm outperforms other baselines in low data regimes. 

   more » « less
5. Gene Flow Increases Phylogenetic Structure and Inflates Cryptic Species Estimations: A Case Study on Widespread Philippine Puddle Frogs ( Occidozyga laevis )

   https://doi.org/10.1093/sysbio/syab034  

   Chan, Kin Onn; Hutter, Carl R; Wood, Perry L; Su, Yong-Chao; Brown, Rafe M (May 2021, Systematic Biology)

   Burbrink, Frank (Ed.)

   Abstract In cryptic amphibian complexes, there is a growing trend to equate high levels of genetic structure with hidden cryptic species diversity. Typically, phylogenetic structure and distance-based approaches are used to demonstrate the distinctness of clades and justify the recognition of new cryptic species. However, this approach does not account for gene flow, spatial, and environmental processes that can obfuscate phylogenetic inference and bias species delimitation. As a case study, we sequenced genome-wide exons and introns to evince the processes that underlie the diversification of Philippine Puddle Frogs—a group that is widespread, phenotypically conserved, and exhibits high levels of geographically based genetic structure. We showed that widely adopted tree- and distance-based approaches inferred up to 20 species, compared to genomic analyses that inferred an optimal number of five distinct genetic groups. Using a suite of clustering, admixture, and phylogenetic network analyses, we demonstrate extensive admixture among the five groups and elucidate two specific ways in which gene flow can cause overestimations of species diversity: 1) admixed populations can be inferred as distinct lineages characterized by long branches in phylograms; and 2) admixed lineages can appear to be genetically divergent, even from their parental populations when simple measures of genetic distance are used. We demonstrate that the relationship between mitochondrial and genome-wide nuclear $$p$$-distances is decoupled in admixed clades, leading to erroneous estimates of genetic distances and, consequently, species diversity. Additionally, genetic distance was also biased by spatial and environmental processes. Overall, we showed that high levels of genetic diversity in Philippine Puddle Frogs predominantly comprise metapopulation lineages that arose through complex patterns of admixture, isolation-by-distance, and isolation-by-environment as opposed to species divergence. Our findings suggest that speciation may not be the major process underlying the high levels of hidden diversity observed in many taxonomic groups and that widely adopted tree- and distance-based methods overestimate species diversity in the presence of gene flow. [Cryptic species; gene flow; introgression; isolation-by-distance; isolation-by-environment; phylogenetic network; species delimitation.] 

   more » « less