Randomized near-neighbor graphs, giant components and applications in data science.
Randomized near-neighbor graphs, giant components and applications in data science.
复制标题
数据科学中的随机近邻图、巨型组件和应用。
DOI：
10.1017/jpr.2020.21
复制
发表时间：
2020
影响因子：
1
通讯作者：
Steinerberger,Stefan
中科院分区：
文献类型：
--
作者：
Linderman,GeorgeC;Mishne,Gal;Jaffe,Ariel;Kluger,Yuval;Steinerberger,Stefan
如果我们在中均匀地选取n个随机点，并将每个点连接到其最近的邻居，其中是维数，并且是取决于维数的常数，则众所周知，该图以高概率连通。我们证明，它足以连接到它的最近的邻居中随机选择的点，以确保一个巨大的组件的大小与高概率的每个点。这种构造产生了一个稀疏得多的随机图，而不是具有可比连通性的边。这一结果对于构建亲和矩阵的数据科学问题具有重要意义：而不是将每个点连接到其k个最近的邻居，人们通常可以从k个最近的邻居中挑选随机点，并且只连接到那些不牺牲结果质量的点。这种方法可以简化和加速计算，我们说明了这一点，在大规模数据集的谱聚类的实验结果。
If we pick n random points uniformly in and connect each point to its nearest neighbors, where is the dimension and is a constant depending on the dimension, then it is well known that the graph is connected with high probability. We prove that it suffices to connect every point to points chosen randomly among its nearest neighbors to ensure a giant component of size with high probability. This construction yields a much sparser random graph with instead of edges that has comparable connectivity properties. This result has non-trivial implications for problems in data science where an affinity matrix is constructed: instead of connecting each point to its k nearest neighbors, one can often pick random points out of the k nearest neighbors and only connect to those without sacrificing quality of results. This approach can simplify and accelerate computation; we illustrate this with experimental results in spectral clustering of large-scale datasets.