Fast Approximation of Similarity Graphs with Kernel Density Estimation
Constructing a similarity graph from a set $X$ of data points in $ \mathbb{R}^d$ is the first step of many modern clustering algorithms. However, typical constructions of a similarity graph have high time complexity, and a quadratic space dependency with respect to $|X|$. We address this limitation and present a new algorithmic framework that constructs a sparse approximation of the fully connected similarity graph while preserving its cluster structure. Our presented algorithm is based on the kernel density estimation problem, and is applicable for arbitrary kernel functions. We compare our designed algorithm with the well-known implementations from the scikit-learn library and the FAISS library, and find that our method significantly outperforms the implementation from both libraries on a variety of datasets.
Code (1)
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Entropic Spectral Learning for Large-Scale Graphs
Graph spectra have been successfully used to classify network types, compute the similarity between graphs, and determine the number of communities in a network. For large graphs, where an eigen-decomposition is infeasib…
Community DetectionDynamic Similarity Graph Construction with Kernel Density Estimation
In the kernel density estimation (KDE) problem, we are given a set $X$ of data points in $\mathbb{R}^d$, a kernel function $k: \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}$, and a query point $\mathbf{q} \in \…
Density EstimationFast Kernel Density Estimation with Density Matrices and Random Fourier Features
Kernel density estimation (KDE) is one of the most widely used nonparametric density estimation methods. The fact that it is a memory-based method, i.e., it uses the entire training data set for prediction, makes it unsu…
Density EstimationSub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation
Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel methods (learning and inference using ke…
Density EstimationA Maximum Entropy approach to Massive Graph Spectra
Graph spectral techniques for measuring graph similarity, or for learning the cluster number, require kernel smoothing. The choice of kernel function and bandwidth are typically chosen in an ad-hoc manner and heavily aff…
Graph Similarity