Reconstruction of line-embeddings of graphons

DOI10.1214/21-EJS1940MaRDI QIDQ2136610zbMATH OpenFDO

Authors Yanyan Li

Publication date 11 May 2022

Published in Electronic Journal of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.06444, https://projecteuclid.org/journals/electronic-journal-of-statistics/volume-16/issue-1/Reconstruction-of-line-embeddings-of-graphons/10.1214/21-EJS1940.full

zbMATH Keywords

random graphgraphonR-matrixprobabilistic algorithm

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Combinatorial probability (60C05)

Abstract: Consider a random graph process with $n$ vertices corresponding to points $v_{i}simUnif[0,1]$ embedded randomly in the interval, and where edges are inserted between $v_i,v_j$ independently with probability given by the graphon $w(v_i,v_j)in[0,1]$. Following Chuangpishit et al. (2015), we call a graphon $w$ diagonally increasing if, for each $x$, $w(x,y)$ decreases as $y$ moves away from $x$. We call a permutation $sigmain{S}_n$ an ordering of these vertices if $v_{sigma(i)}<v_{sigma(j)}$ for all $i<j$, and ask: how can we accurately estimate $sigma$ from an observed graph? We present a randomized algorithm with output $hatsigma$ that, for a large class of graphons, achieves error $ma{x}_{1leqileqn}|sigma(i)-hatsigma(i)|=O^{\ast }(sqrtn)$ with high probability; we also show that this is the best-possible convergence rate for a large class of algorithms and proof strategies. Under an additional assumption that is satisfied by some popular graphon models, we break this "barrier" at $sqrtn$ and obtain the vastly better rate $O^{\ast }(n^{epsilon})$ for any $epsilon>0$. These improved seriation bounds can be combined with previous work to give more efficient and accurate algorithms for related tasks, including: estimating diagonally increasing graphons, and testing whether a graphon is diagonally increasing.

Recommendations

• Recovering the structure of random linear graphs
• Uniform linear embeddings of graphons
• Optimal graphon estimation in cut distance
• Learning random points from geometric graphs or orderings
• Rate-optimal graphon estimation

Cites work

• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• A general method for lower bounds on fluctuations of random variables
• A new tractable case of the QAP with a Robinson matrix
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Concentration inequalities. A nonasymptotic theory of independence
• Consistent Recovery Threshold of Hidden Nearest Neighbor Graphs
• Convex relaxations for permutation problems
• Hidden Hamiltonian cycle recovery via linear programming
• Large networks and graph limits
• Limits of dense graph sequences
• Linear embeddings of graphs and graph limits
• Matrix estimation by universal singular value thresholding
• NP-hard approximation problems in overlapping clustering.
• Optimal rates of statistical seriation
• Rate-optimal graphon estimation
• Recovering the structure of random linear graphs
• Seriation and matrix reordering methods: An historical overview
• Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
• Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
• Similarity-first search: a new algorithm with application to Robinsonian matrix recognition
• Spectral ranking using seriation
• The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure
• Towards optimal estimation of bivariate isotonic matrices with unknown permutations
• Uniform linear embeddings of graphons

Cited in

(5)

• Localization in 1D non-parametric latent space models from pairwise affinities
• A binary embedding of the stable line-breaking construction
• Recovering the structure of random linear graphs
• Robust recovery of Robinson property in \(L^p\)-graphons: a cut-norm approach
• Distinguishing two graph-encoded manifolds of Lins

This page was built for publication: Reconstruction of line-embeddings of graphons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2136610)