Near-Perfect Recovery in the One-Dimensional Latent Space Model
Near-Perfect Recovery in the One-Dimensional Latent Space Model
复制标题
一维潜在空间模型中近乎完美的恢复
DOI：
10.1145/3366423.3380261
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Khanna, Sanjeev
中科院分区：
文献类型：
--
作者：
Chen, Yu;Kannan, Sampath;Khanna, Sanjeev
假设图G是通过沿一条线段对顶点进行均匀采样并以已知的距离递减函数的概率连接每一对顶点来随机创建的。我们问，是否有可能通过只观察生成的未标记图来重建G中顶点的实际位置。我们针对两个自然边概率函数来研究这个问题--一个是边的概率随距离指数衰减的情况，另一个是该概率仅线性衰减的情况。我们以一个较弱的目标开始我们的研究，即只恢复顶点在线段上出现的顺序。对于长度为n且精度参数为δ的分段，我们证明了对于指数衰减边概率函数和线性衰减边概率函数，仅使用样本(顶点)就可以正确地恢复(直到反射对称性)相距至少δ的所有顶点的顺序。在此结果的基础上，我们证明了顶点(样本)足以额外地将线上每个顶点的位置恢复到δ的精度内。我们用重建位置所需样本的下界来补充这一结果(即使是通过计算上无界的算法)，表明恢复位置的任务是信息-理论上比恢复顺序更难。实验结果表明，该算法恢复了几乎所有点的位置，具有较高的精度。
Suppose a graph G is stochastically created by uniformly sampling vertices along a line segment and connecting each pair of vertices with a probability that is a known decreasing function of their distance. We ask if it is possible to reconstruct the actual positions of the vertices in G by only observing the generated unlabeled graph. We study this question for two natural edge probability functions — one where the probability of an edge decays exponentially with the distance and another where this probability decays only linearly. We initiate our study with the weaker goal of recovering only the order in which vertices appear on the line segment. For a segment of length n and a precision parameter δ, we show that for both exponential and linear decay edge probability functions, there is an efficient algorithm that correctly recovers (up to reflection symmetry) the order of all vertices that are at least δ apart, using only samples (vertices). Building on this result, we then show that vertices (samples) are sufficient to additionally recover the location of each vertex on the line to within a precision of δ. We complement this result with an lower bound on samples needed for reconstructing positions (even by a computationally unbounded algorithm), showing that the task of recovering positions is information-theoretically harder than recovering the order. We give experimental results showing that our algorithm recovers the positions of almost all points with high accuracy.
评论：H. G. Hardy、J. E. Littlewood 和 G. Pólya，《不平等》
DOI：
--
发表时间：
1953
期刊：
影响因子：
--
作者：
A. Zygmund
通讯作者：
A. Zygmund