Network Recovery from Unlabeled Noisy Samples

Abstract

There is a growing literature on the statistical analysis of multiple networks in which the network is the fundamental data object. However, most of this work requires networks on a shared set of labeled vertices. In this work, we consider the question of recovering a parent network based on noisy unlabeled samples. We identify a specific regime in the noisy network literature for recovery that is asymptotically unbiased and computationally tractable based on a three-stage recovery procedure: first, we align the networks via a sequential pairwise graph matching procedure; next, we compute the sample average of the aligned networks; finally, we obtain an estimate of the parent by thresholding the sample average. Previous work on multiple unlabeled networks is only possible for trivial networks due to the complexity of brute-force computations.

References in corpus (11)

• De-anonymizing Social Networks
• Nonparametric Bayes Modeling of Populations of Networks
• Seeded graph matching for correlated Erdős-Rényi graphs
• Network classification with applications to brain connectomics
• Estimation of subgraph density in noisy networks
• Two-sample Hypothesis Testing for Inhomogeneous Random Graphs
• Impossibility of Partial Recovery in the Graph Alignment Problem
• Testing correlation of unlabeled random graphs
• On the k-Anonymization of Time-varying and Multi-layer Social Graphs
• A Quotient Space Formulation for Generative Statistical Analysis of Graphical Data
• Estimation of the Epidemic Branching Factor in Noisy Contact Networks

Cited by in corpus (1)

• Clustering of heterogeneous populations of networks