Papers Graphon Estimation
“Graphon Estimation” 태그가 달린 논문 21편 · 필터 해제
Estimating Dyadic Treatment Effects with Unknown Confounders
This paper proposes a statistical inference method for assessing treatment effects with dyadic data. Under the assumption that the treatments follow an exchangeable distribution, our approach allows for the presence of a…
Graphon EstimationGraph data augmentation with Gromow-Wasserstein Barycenters
Graphs are ubiquitous in various fields, and deep learning methods have been successful applied in graph classification tasks. However, building large and diverse graph datasets for training can be expensive. While augme…
Data AugmentationGraph ClassificationGraphon EstimationPrivate graphon estimation via sum-of-squares
We develop the first pure node-differentially-private algorithms for learning stochastic block models and for graphon estimation with polynomial running time for any constant number of blocks. The statistical utility gua…
Graphon EstimationComputational Lower Bounds for Graphon Estimation via Low-degree Polynomials
Graphon estimation has been one of the most fundamental problems in network analysis and has received considerable attention in the past decade. From the statistical perspective, the minimax error rate of graphon estimat…
Community DetectionGraphon EstimationStochastic Block ModelGraphon Estimation in bipartite graphs with observable edge labels and unobservable node labels
Many real-world data sets can be presented in the form of a matrix whose entries correspond to the interaction between two entities of different natures (number of times a web user visits a web page, a student's grade in…
Graphon EstimationJoint Network Topology Inference via a Shared Graphon Model
We consider the problem of estimating the topology of multiple networks from nodal observations, where these networks are assumed to be drawn from the same (unknown) random graph model. We adopt a graphon as our random g…
Graphon EstimationGraph SamplingGraphon-aided Joint Estimation of Multiple Graphs
We consider the problem of estimating the topology of multiple networks from nodal observations, where these networks are assumed to be drawn from the same (unknown) random graph model. We adopt a graphon as our random g…
Graphon EstimationTraining Graph Neural Networks by Graphon Estimation
In this work, we propose to train a graph neural network via resampling from a graphon estimate obtained from the underlying network data. More specifically, the graphon or the link probability matrix of the underlying n…
Graph Neural NetworkGraphon EstimationGraphon Estimation from Partially Observed Network Data
We consider estimating the edge-probability matrix of a network generated from a graphon model when the full network is not observed---only some overlapping subgraphs are. We extend the neighbourhood smoothing (NBS) algo…
Graphon EstimationMatrix CompletionMinimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
This paper surveys some recent developments in fundamental limits and optimal algorithms for network analysis. We focus on minimax optimal rates in three fundamental problems of network analysis: graphon estimation, comm…
Community DetectionGraphon EstimationTwo-sample testingConsistent polynomial-time unseeded graph matching for Lipschitz graphons
We propose a consistent polynomial-time method for the unseeded node matching problem for networks with smooth underlying structures. Despite widely conjectured by the research community that the structured graph matchin…
Graph MatchingGraphon EstimationTowards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations
Many applications, including rank aggregation, crowd-labeling, and graphon estimation, can be modeled in terms of a bivariate isotonic matrix with unknown permutations acting on its rows and/or columns. We consider the p…
Graphon EstimationDistributed Cartesian Power Graph Segmentation for Graphon Estimation
We study an extention of total variation denoising over images to over Cartesian power graphs and its applications to estimating non-parametric network models. The power graph fused lasso (PGFL) segments a matrix by expl…
DenoisingGraphon EstimationLink prediction for egocentrically sampled networks
Link prediction in networks is typically accomplished by estimating or ranking the probabilities of edges for all pairs of nodes. In practice, especially for social networks, the data are often collected by egocentric sa…
Graphon EstimationLink PredictionPredictionThy Friend is My Friend: Iterative Collaborative Filtering for Sparse Matrix Estimation
The sparse matrix estimation problem consists of estimating the distribution of an $n\times n$ matrix $Y$, from a sparsely observed single instance of this matrix where the entries of $Y$ are independent random variable…
Collaborative FilteringCommunity DetectionGraphon EstimationMatrix Completion+1Rates of Convergence of Spectral Methods for Graphon Estimation
This paper studies the problem of estimating the grahpon model - the underlying generating mechanism of a network. Graphon estimation arises in many applications such as predicting missing links in networks and learning …
Community DetectionGraphon EstimationRecommendation SystemsStochastic Block ModelReducing Crowdsourcing to Graphon Estimation, Statistically
Inferring the correct answers to binary tasks based on multiple noisy answers in an unsupervised manner has emerged as the canonical question for micro-task crowdsourcing or more generally aggregating opinions. In grapho…
Graphon EstimationWhen is Nontrivial Estimation Possible for Graphons and Stochastic Block Models?
Block graphons (also called stochastic block models) are an important and widely-studied class of models for random networks. We provide a lower bound on the accuracy of estimators for block graphons with a large number …
Graphon EstimationEstimating network edge probabilities by neighborhood smoothing
The estimation of probabilities of network edges from the observed adjacency matrix has important applications to predicting missing links and network denoising. It has usually been addressed by estimating the graphon, a…
DenoisingGraphon EstimationLink PredictionAn iterative step-function estimator for graphons
Exchangeable graphs arise via a sampling procedure from measurable functions known as graphons. A natural estimation problem is how well we can recover a graphon given a single graph sampled from it. One general framewor…
ClusteringGraphon Estimation