SpectralNet is a graph clustering method that uses neural network to find an
embedding that separates the data. So far it was only used with $k$-nn graphs,
which are usually constructed using a distance metric (e.g., Euclidean
distance). $k$-nn graphs restrict the points to have a fixed number of
neighbors regardless of the local statistics around them. We proposed a new
SpectralNet similarity metric based on random projection trees (rpTrees). Our
experiments revealed that SpectralNet produces better clustering accuracy using
rpTree similarity metric compared to $k$-nn graph with a distance metric. Also,
we found out that rpTree parameters do not affect the clustering accuracy.
These parameters include the leaf size and the selection of projection
direction. It is computationally efficient to keep the leaf size in order of
$\log(n)$, and project the points onto a random direction instead of trying to
find the direction with the maximum dispersion.

本研究利用神经网络分离数据内嵌，提出了一种基于 rpTree 相似性度量的 SpectralNet 相似性度量方法来进行图聚类，实验证明，与基于距离度量的 $k$-nn 图相比，基于 rpTrees 的 SpectralNet 能够获得更好的聚类准确性。

SpectralNet 的随机投影树相似度度量

Random projection tree similarity metric for SpectralNet

Graph-based clustering methods like spectral clustering and SpectralNet are
very efficient in detecting clusters of non-convex shapes. Unlike the popular
$k$-means, graph-based clustering methods do not assume that each cluster has a
single mean. However, these methods need a graph where vertices in the same
cluster are connected by edges of large weights. To achieve this goal, many
studies have proposed graph reduction methods with parameters. Unfortunately,
these parameters have to be tuned for every dataset. We introduce a graph
reduction method that does not require any parameters. First, the distances
from every point $p$ to its neighbors are filtered using an adaptive threshold
to only keep neighbors with similar surrounding density. Second, the
similarities with close neighbors are computed and only high similarities are
kept. The edges that survive these two filtering steps form the constructed
graph that was passed to spectral clustering and SpectralNet. The experiments
showed that our method provides a stable alternative, where other methods
performance fluctuated according to the setting of their parameters.

本研究提出了一种不需要参数调整的图缩减方法来构建适用于谱聚类和 SpectralNet 的图，通过邻域密度和相似度过滤，实现了高效的聚类检测。