X-Forest: Approximate Random Projection Trees for Similarity Measurement
Authors: Yikai Zhao
Peiqing Chen
Zidong Zhao
Tong Yang
Jie Jiang
Bin Cui
Gong Zhang
Steve Uhlig
Venue:  (2020)

Abstract: Similarity measurement plays a central role in various data mining and machine learning tasks. Generally, a similarity measurement solution should, in an ideal state, possess the following three properties: accuracy, efficiency and independence from prior knowledge. Yet unfortunately, vital as similarity measurements are, no previous works have addressed all of them. In this paper, we propose X-Forest, consisting of a group of approximate Random Projection Trees, such that all three targets mentioned above are tackled simultaneously. Our key techniques are as follows. First, we introduced RP Trees into the tasks of similarity measurement such that accuracy is improved. In addition, we enforce certain layers in each tree to share identical projection vectors, such that exalted efficiency is achieved. Last but not least, we introduce randomness into partition to eliminate its reliance on prior knowledge.   We conduct experiments on three real-world datasets, whose results demonstrate that our model, X-Forest, reaches an efficiency of up to 3.5 times higher than RP Trees with negligible compromising on its accuracy, while also being able to outperform traditional Euclidean distance-based similarity metrics by as much as 20% with respect to clustering tasks.   We have released codes in github anonymously so as to meet the demand of reproducibility.

Under review as a conference paper at ICLR 2020
X-FOREST: APPROXIMATE RANDOM PROJECTION TREES FOR SIMILARITY MEASUREMENT
A Anonymous authors Paper under double-blind review
A ABSTRACT
Similarity measurement, plays central role in various data mining and machine learning tasks. Generally, a similarity measurement solution should, in an ideal state, possess the following three properties: high accuracy, high efficiency in terms of speed and independence from prior knowledge. Yet unfortunately, vital similarity measurements are, no previous works have addressed all of them. In this paper, we propose X-Forest, consisting of group of approximate Random Projection Trees, such that all three targets mentioned above are tackled simull are as follows. First, we introduced RP Trees into similarity measurement such that accuracy is improved. In addition, enforce certain layers in each tree to share identical projection vectors, such that exalted speed is achieved. Last but not least, introduce randomness into partition to eliminate its reliance on prior knowledge. We conduct experiments on three real-world datascts, whose results demonstrate that model, X-Forest, reaches an efficiency of up to 3.5 times higher than RP Trees with negligible compromise on its accuracy, while also being able to outperform traditional Euclidean distance- based similarity metrics by as much as 20% with respect clustering tasks.
Our key techniques
1 INTRODUCTION
1.1 BACKGROUND AND MOTIVATION
Similarity measurement is to mcasure the similarity between every pair of items in given dataset. Generally, an item can be represented by data point in the space (e.g., Euclidean space). The target of similarity measurement is to generate a similarity matrix M whose element Mij represents the similarity value between two data points: and j.
Similarity measurement plays a central role in data mining and machine learning, and also has practical applications other fields such as biochemistry, biology, botany, etc. data mining, similarity is vital criterion in unsupervised clustering which is to classify objects into groups and eliminate inappropriate data [Santo et al. (2013): Kushawah Yadav (2016); be applied in various specific fields, e.g., liver lesions Jha ct al. (2010), the characterization of chemical structures and biological activity spectra Fliri al. (0055 or for ligand identification Koch
Jarvis & Patrick 19733 The result of clustering
the accurate segmentation
el al. (2004). In machine learning, similarity can be used in social filtering al algorithum to
make predictions for recommendation systems Billsus & Pazzani 1998).
Therefore, these extensive applications require the similarity measurement solution to main- tain high accuracy in different datasets Ma & Manjunath (1996), and this is the first design gool of this paper. The second design goal is to achieve efficient similarity measurement.
1.2 PRIOR ART AND THEIR LIMITATIONS
For similarity measurement, existing works can be divided into two kinds: mathematical distance-based similarity and multi-partition based similarity. Currently the prevailing approaches belong to the first kind of solutions, such Minkowski distance family, Fidelity or Squared-chord family, Shannon's entropy Cha (2007). Cosine similarity Trani et al. (0016). etc. These similarity measurement solutions only depend on the pairwise information (1.c., partial information), but neglect the overall information, such as the dimensions, features, distribution of the dataset. Consequently, they have low versatility, i.e., lacking the flexibility

---

Under review as a conference paper at ICLR 2020
to adapt to different datasets. Furthermore, they are not accurate enough, because they may not preserve the perceptual similarity (intuitive similarity) of the dataset, especially when encountered with high dimension datasets Ma & Manjunath 1996]; (2008).
Dasgupta & Freund
The second kind of solutions such as Multiple RP+ EM Fern & Brodley (2003) and RF similarity Gray et al. (2013) overcome the shortcomings of the first kind by projecting and partitioning the data. Unlortunately, this kind of solutions often depends on priori knowledge about data distribution or data labels, which can hardly be acquired in common sircumstances Consequently, The thind design goal of this paper is eliminate the dependence on priori knowledge. No existing works can achieve all the design goals at the same time.
1.3 OUR CONTRIBUTIONS
This paper aims to achieve the above three design goals at the same time. Towards the first. and third goal, we introduce the Random Projection Tree (RP Tree) to similarity measurement. RP Tree is used to randomly partition a set of data points in a space into several disjoint subsets. Tt is well known that in an RP Tree, data points that are closely distributed, indicating their high level of similarity in space, same subset Dasgupta & Freund (2008). This means that RP Tree can achieve the first goal high accuracy. As RP Tree uses random partitions, thus achieves the third goal climinating priori knowledge dependence.
always partitioned into the
Unfortumately, directly using RP Tree cannot achieve the second goal - high efficiency, because during each partition, we need to project all data points into a random vector which is time consuming (see details in Section 2 To address this problem, we propose the X-Forest. The key idea is to allow nodes at i + X, i + 2X... (i=0.1,2...) layers of the tree to share the same projection vector for partitioning. For example, let us assume that we are given a complete binary RP Tree with 4 layers. The root node denotes the entire dataset and each node denotes a subset of the entire datasct. For cach inner node, the standard RP Tree needs to project all data points into one random vector. In this way, it projects each data point four times. Our solution is let the nodes at the first and third layers share the same projection vector, and do so for the second and fourth layers. For the nodes al the third layer, we reuse the projection results of the first layer, and do so for the four layer. In this way, project each data point twice instead of four times.
Obviously, sharing vectors sacrifices the randomness of projection vectors, further degrading the accuracy. Fortunaeel,, the accuracy loss be almost eliminated by using great many Trees and carcfully choosing the sharing parameter
(sec dotails in Section 3.2
We propose 3-Similarity to record the results in X-Forest into similarity matrix. It features better representing the similarity relationship between data points, which is proved by the higher accuracy in clustering experiments.
Our key contributions are as follows:
We introduce RP Trees into similarity measurement and proposed new similarity matrix 3-Similarity, which better reveals the similarity relationships between data points than traditional distance based similarity measurement.
We propose X-Forest which significantly reduces the time of building procedure of RP Troes by sharing projection vectors.
We conduct extensive experiments on three real datasets, and our experimental results show that RP Trees achioves two design goals, while X-Forest achieves all three desigan goals at the same time.
We have released codes in github anonymously so as to meet the demand of reproducibility sou The mathematical proofs of our algorithm is detailed in supplementary materials.
2
BACKGROUND AND RELATED WORK
2.1
SIMILARITY MRASUREMENT
Existing solutions for similarity measurement can be classified into two categories: 1) mathematical distance based similarity and 2) multi-partition based similarity.
2

---

Under review as a conference paper at ICLR 2020
Figure 1: Relationship between projection and space partitioning. The red arrow is the projection direction. P the partition point. The vertical line is the spatial parti- tion hyperplane.
Figure 2: Example of standard RP Tree. Each node uses an independent unit random projection direction.
The first kind is Mathematical distance based similarity which is widely used. It includes Minkowski distance family, Fidelity or Squared-chord and Shannon's entropy Cha (007)
Cosine similarity Irani al. (2016). the correlation coefficient Billsus & Pazzani 1998)
travel time, and edit distance Chen et al. (2009), etc. According to the applying met of distance, it can be divided into two cases: 1) distance dircctly applied as similarity; 2) distance is first computed as a criterion for further similarity evaluation. An example of the second case is shared neighbours based clustering Jarvis Patrick (1973). The nearest neighbours of each data point are found using Euclidean distance. The similarity between data point and j delined as the number of common neighbours.
Existing works of the second kind, multi-partition based similarity, is rare, and an example Multiple RP+EM Fern & Brodley (2003). In each operation of RP+EM, the dimension of the original dataset is degraded through linear transformation. Then, it applies EM clustering to generate a probabilistic model of a mixture &o Gaussians. The similarity between data points and j is defined as the average value Ps = Σ P(I i, P(I j, of each RM.
The first kind of solutions falls short in terms of leading to unsatisfied results, especially in high-dimensional spaces. And the second kind depends on prior knowledge about data labels or data distribution.
2.2 RANDOM PROJECTION TREE
Sanjoy Dasgupta and Yoav Freund first propose the idea of RP Tree Dasgupta & Freund (2008). An RP Tree is a variant of 6-dd d tree Bentley 1975). The most popular application of RP Tree is in nearest neighbours finding, where compensates k d tree's diminishing ellicacy in ligh-dimensional spaces Dasgupla & Sinha (2015). Other applications of RP Tree
cover clustering Yan al. (2009). pallern discovering Minnen al. (2007) and nearest neighbours finding, vector quantization Dasgupta & Freund (2009). local symmetry detection
in natural images [Shen et al. (2016), etc.
The details of building an RP 'Tree are as follows. In an RP Tree, the root node includes all items in a given set S. Through RP operation, each of which is a child node of the root node. The child node will be recursively partitioned until its size is smaller than a predefined threshold т. In the end, each leaf node of an Tree forms set of size less than т. Figure 2 shows the structure of an RP Tree. The main operation of RP Tree, the operation, generates a random unit direction vector for each partition. After all data points have been jeoted into the random direction, uniformly choose a partition point at random within the projection range, where the projection range refers to the interval between the smallest and the largest projection value.
Tree partitions S into two disjoint sets,
The formal description of an RP operation is as follows. RP Tree computes the projection value of each point in the set S into the unit directional vector Let P. be the set of projection values, i.e., P fx-ex e S}. Let Pmax be the maximum value P and Pmin be the minimum value in P. The partition point P, is uniformly and randomly selected from
3

---

Under review as a conference paper at ICLR 2020
Sini larily
0.8
Sini larity
8.8
0.4
0.0
50
100
150
50
100
150
(a) Basic Similarity.
(b) E-Similarity (8=00 0.9)
Figure 3: Similarity between data points of the first class (number 1-50) and the entire dataset (number 1-50, number 51-100, number 101-150).
& ex (Pming P ).ax). ). P, partitions the set S into two disjoint subsets S, fx- and SR = ex P, |x E). This is equivalent to partitioning the space into two parts with (d - 1)-dimensional hyperplane x e P,. When d = 2, shown in Figure [ the (d - 1)-dimensionaa hyperplane degrades to a line. Building an RP Tree suffers from high computation complexity since, a large number of RP operations involved whenever an RP Tree is built, worsened by the fact that, it requires another large number of inner products to complete single RP operation.
x S}
THE X-FOREST ALGORITHM
As detailed in Section 2.2] RP Tree cluster similarly data points into the same node. In this section, we first show how to use number of RP Trees to generate the similarity malrix. Then we introduce X-Forest, which significantly accelerate the building procedure of these trees.
3.1 SIMILARITY MATRIX GENERATION
In an RP Tree, two data points are regarded as similar if they are in the same leaf node. Therefore, given a number of trees that are built independently, we can consider the probability that two data points fall into the same leaf node as their similarity. Based on this idea, the well known similarity matrix is defined as follows.
Definition Given m RP Trees Tı, ..., Tm, for RP Tree Te, suppose a data point æj belongs to the leaf node (x(x)) The basic similarily malria Mbusic is defined as
M Minsic
1
Σ
m
(()(()))) Ci(xxa))
(1)
where the indicator function.
The basic similarity matrix is the average of some 01 matrix, and each 01 matrix is similarity matrix generated by one RP Tree. In 01 matrix, the similarity between data points falling into the same leaf node is 1 and the similarity between data points falling into different. leaf nodes is O.
This definition does not consider the information of the structure of the RP Tree. This leads to the 01 matrix is too sparse, i.c., has large number of Os. To show that, consider the following example. Given n data points to build an RP Tree with each leaf nodes containing data points, this RP Tree has A leaf nodes and each leaf node fills the similarity matrix F with , 1s. Therefore, the size of this matrix generated by this Tree is n² but only nr elements are 1, accounting for of all elements (e.g. n = 150, r r= 3, 1 accounted for only 0.02). The issue is that the similarity of data points different leaf nodes should be a number between O and 1 rather than O. Thus we can get matrix better representing the similarity between data points, by reasonably eliminating some Os. achieve this, we need to consider information about the whole structure of an RP Tree. If the distance between two data points in an RP Tree is short (i.e., they are divided later), we should define their similarity value closer to 1. If the distance between two data points in RP Tree is long (i.e., they are divided earlier), we should define their similarity as a value closer to Based this observation, propose the 8-Simi cimilarity matrix.
4

---

Under review as a conference paper at ICLR 2020
Figure 5: Example of a X- X-Projection Tree. A tree uses only two random directions. One (red) for odd layers and the other (yellow) for even layers.
Figure 4: Example layer-by-laeer RP tree. Different nodes of each layer the same projection direction. The projection directions on each path from the root to the leaf are still independent.
Definition Given an RP Tree Tú let DIS, (X, r) be the distance between nodes X and Y in Tr. The B-S Simi larity matrix M is defined
M
DIS, (C,)
(2)
Here 3 is a parameter controlling the speed at which the similarity decays with increasing distance. When 3 - O, the B-Similarity matrix degenerates into the basic similarity matrix. We use the most popular Iris flower dataset Dua & Graff (2017) to compare the basic similarity and 3-Similarity and the result is shown in Figure 3 For basic similarity, most data points in the same class (number 1-50) have rather low similarity. For 3-Similaritt larity, the similarity between data points in the same class significantly greater than that of the data points in different classes. In our experiments, we find that the accuracy of clustering can be significantly improved by properly choosing (Figure
3.2 X-PROJECTION TREE AND X-FOREST
Generating a similarity matrix requires a large number of different Trees. However, the process of building such large number of RP Trees is rather slow. To address this issue, we propose X-Forest. The key idea to allow nodes at i, i X, i 2X, ... 1,2,...) layers of the tree to share the same direction vector.
In order to introduce the X-Forest, we first introduce an equivalent RP Tree called Layer-by-Layer RP Tree. Compared to the standard RP Tree, Layer-by-Layer RP Tree allows nodes in each layer share the same projection direction. An example of a Layer-by-Layer RP Tree is shown in Figure E Theoretically, the Layer-by-Layer RP Tree is equivalent to the standard RP tree. Here we give brief explanation: For a standard RP Tree, the partition of each node the tree relies directions. Intuitively, random partition of the dataset demands each data point to go through series of mutually independent partitions. Thus, in an Tree, the nodes which are rrrestoo-desceddaae related (ADR) need mutually independent projection directions, and the nodes which are not ADR can share the same projection directions. Specifically, is sufficient that the projection directions used by different layers are mutually independent. This shows the equivalence between the standard RP Tree and Layer-by-Layer RP Tree.
series of independent projection
To further explore her avenues to economize computation time, X-Forest allows different layers share the same projection directions. Sharing projection directions sacrifices the randomness of partition, further affecting the similarity generated. To implement the trade- off between speed and accuracy, we give a method by adjusting the sharing parameter X.
Here we describe the details about building an X-Forest, which is a group of X-Projection Trees. Given dataset S, for each X- X-Projection Tree, select X independent random projection directions ep, ... "x.,..,,xx,, and compute the projection value all data points into the X projection directions, i.e. P. (x-e; S}. When building X-Projection
5

---

Under review as a conference paper at ICLR 2020
Tree, rely on the following idea to allow data sharing of the projection directions: the root node uses the first projection direction e, for partitioning. The node in the i-th layer uses the (i mod X)tth projection direction @ mod x), and uses the pre-calculated projection value in P( mod X) to partition the set. The rest of the recursive tree construction is identical to standard RP Tree. Figure shows example of using X version of X-Projection Tree to partition data points.
The X-Projection Tree is equivalent a Layer- RP Tree when its depth is no greater than X. When X = 1, it is equivalent to using à series of parallel (d (d- 1)-dimension hyperplanes partition the space. This is the most efficient case because only one operation is required. According to our experimental analysis, we find out that: 1) the X = 2 version of X-Forest achieves the best trade-off between improvement in computational efficiency and loss in partition precision. 2) the X = 4 version of X-Forest almost achieves the accuracy of Layer-by-Layer RP Trees, while requiring little additional time compared to the X = 2 version. Further experimental details are discussed in Section 5
Here we provide an analysis of the computational complexity of X-Forest. Given a d- dimensional dataset S with data points, for RP Trees, the time complexity of building trees and generating the similarity matrix is O(m n (n + logn n. d)) in the average, and O(m n²² d) in the worst case. And the complexity for X-Forest made of m X-Projection Trees is always O(m n (n + X Xxdd d)). Therefore, X-Forest is especially suitable for datasets satisfying d >> n/ logn. n.
In term of implementation, X-Forest can calculate P3 in parallel for all projection directions. For the standard RP Tree, parallel acceleration cannot be used because information about which set of data points is to be projected into each direction remains uncertain.
APPLICATIONS OF X-FOREST
In this section, we demonstrate how to apply the similarity matrix to some classical clustering algorithms, including Kernel K-means, density clustering, and spectral clustering.
K-means Hartigan & Wong (1799) is the most popular unsupervised clustering algorithm. It partitions all data points into K clusters by finding K optimal cluster centers. The optimization goal is to minimize the sum of the distances of each data point to its nearest cluster center. The Kernel K-means is optimization of K-means clustering. The imput data points are mapped into a feature space using a nonlinear mapping d. A kernel function Fjs- (Ø(x;), ((xx)) is used to calculate the distance in feature space.
Kernel K-means:
For this application, X-Forest maps data points to unit vectors in the feature space, and the kernel function is given by the similarity matrix M.
F jk = (d(xx); o(xx)) M₁
Density clustering: DBSCAN Ester al. 1996) is the most popular density- based clustering method. In DBSCAN, a point is considered as a dense part if its e-neighborhood has enough points. In the process of clustering, DBSCAN arbitrarily selects an unvisited dense part and its c-ncighborhood as a cluster, and recursively adds the e-ncighborhoods of the dense parts alrcady added into this cluster, until no more points can be added. This process is repeated until all dense parts are visited.
In this application, the similarity matrix M can be used to express the inner product of two data points in the feature space & The distance of any two data points in the feature space can be obtained by the following formula.
|(x(x)) o(xx)112 ((0(x,) - ((xx), o(x,) +(xx)))) 12 - 2 M₁x)
Spectral clustering: Spectral clustering Ng et al. 2002); Shi & Malik 2000 is an
algorithm derived from graph theory and has been widely used in clustering. By defining the weight (similarity) between two data points, spectral clustering embeds data points into

---

Under review as a conference paper at ICLR 2020
undirected weighted complete graph. The complete graph is divided into K sub-graphs by cutting off the edge set with minimum weight to achieve the purpose clustering.
Classic spectral clustering uses exp (-1x, x /20²) the weight of the edge, where is the bandwidth of the graph. In this application, we directly use M₃s of the similarity matrix M the edge weight.
EXPERIMENTAL RESULTS
We first show the accuracy improvement of some classical clustering methods after using the B-Similarity generated by X-Forest. Then, we compare the performance in terms of computation time of X-Forest under different parameter scttings.
5.1 EXPERIMENTAL SETUP
Choice of Datasets: As is shown in Table T we conduct experiments three real datasets from the UC Irvine machine learning library Dua & Graff (2017). including Wine, Soybean and WDBC. All three datasets are labeled, allowing evaluate the actual performance of the clustering.
Dataset
dimension
# categories
# data points
Wine
13
3
178
Soybean
35
4
47
WDBC
30
2
569
Table 1: A summary of datasets.
Choice of Clustering Algorithms: In the first part of this section, we compare the accuracy of Kernel K-means, Density Clustering and Spectral Clustering using 3-Similarity generated by X-Forest and distance similarity. In the second part, we use Kernel K-means clustering algorithm to compare the performance of X-Forest under different parameter settings.
We use Accuracy as an evaluation metric of the performance of clustering. The definition of Accuracy is given by the formula below. It measures the fraction of matching labels given by the clustering algorithm divided by the real label.
Evaluation Metrics:
Definition Let = (x1 V2 12, Xn : Fnd be the dataset, i(.) the label obtained by the chustering algorithm, and (.) be the permutation of elements.
Accuracy max
[ū(x;)) -
T1
Default Configuration: Table 2 shows the default parameter configuration of X-Forest on 3 data sets, and lists the average depth of the X-Projection trees on these datasets. Since all the average depths are between 8 and 16, we regard the X = 16 X-Forest as standard RP Trees and layer-by-layer RP Trees. In the experiment, we generate 1000 similarity matrices for each parameter configuration and show the average value of Accuracy and Time. All experiments are conducted on laptop with 2.6 GHZ Intel Core i7 CPU.
Dataset # Trees
X
3
Average Depth
Wine
1000
2
10
0.9
9.6
Soybean
1000
2
3
0.9
12.4
WDBC
1000
2
30
0.9
15.1
Table 2: Default Configuraion.

---

Under review as a conference paper at ICLR 2020
Soybean
WDRC
Wine
1.0
Accuracy
0.8
0.6
0.4
Distance X-similority Distance X-similarity
X s-sinilarity
Kernel K-neans
DBSCAN
Spectual Clustering
Figure Accuracy of different clustering algorithms on several datasets with distance similarity and X x-Similarity.
5.1.1 EXPERIMENTS ON ACCURACY
In this experiment, we use different clustering algorithms (Kernel K-means, DBSCAN, Spectral Clustring) and different similarity measurements (3- (B-Similarity, distance similarity). Figure 6 shows that the Accuracy of Kernel K-means using g-Similarity are respectively about 11.1%, 9%. 24% higher than the of that of using distance similarity on the three datasets. The Accuracy of DBSCAN using 9-Similarity are respectively about 27.6%, 5.5%, 33.7% higher than that of using distance similarity on the three datasets. The Accuracy of Spectral Clustering using B-Similarity respectively about 21.3%, 28.6%, 34.8% higher than that of using distance similarity the three datasets.
Accuracy vs. Different Similarity (Figure 6
Accuracy vs. X (Figure 7) In this experiment, change the value of X (1, 2, 4, 8, 16) and the number of X-Projection trees (20, 40, 80, 160, 320, 640, 1280) in an X-Forest and use Kernel K-means for clustering. When tree number is 1280, for the soybean dataset (Figure 7(a)) we see that the accuracy of the = 2 and X = 4 version of X-Forest are respectively about 96.4% and 99.1% of that of standard RP Trees. For the WDBC dataset (Figure 7 we see that the accuracy of the X and = 4 version of X-Forest are almost the same that of standard RP Trees. For the wine dataset (Figure [(c)), we see that the accuracy of the X = and X = 4 version of X-Forest are respectively about 99.4% and 99.8% of that of standard Trees.
X=1
X-2 - X=1
X=1
X=2
X=1
X=1
X=2
X=4
X-8
X-16
X-8
X-16
X-8
X-16
Acouray
0. 76
Accuracy
0. 4.94
Accuracy
0. 0393
0. 72
0. 9.90
0. 68
0. 92
87
61
0. 84
64 256
1024
64 256 1024
64 256
1024
#Trress
#TTees
#Trecs
(a) Soybean.
(b) WDBC.
(c) Wine.
Figure 7: Accuracy of X-Forest with different numbers of trees and Xs.
80
0. 95
0. 94
Aoouraoy
70
Accurayy
Accuracy
0.
.29
0. 60
0. 90
0. 5.50
0. 93
0.0
0.
0.
0.9
0.0
0
0.
3
0.
6
0.
0.0 0. 0.
0.9
B
(a) Soybean.
(b) WDBC.
(c) Wine.
Figure Accuracy and variance 3-Similarity with different Bs.
Accuracy vs. 3 (Figure 8): In this experiment, we change 3 ([0, 1)) and use Kernel
K-means for clustering. For the soybean dataset (Figure 8(a]). the accuracy of the 0.9 version of 3-Similarity is about 25.9% higher than that of the 0 version of
8

---

Under review as a conference paper at ICLR 2020
#1rees=160
S2r #Trees=1280
#Trees-160
4rress5520
41rees-180
#Trees-S22 #Treess122
#1rees-660
360
60
60
Timo
Time(ms)
270
Timo(
10
180
40
90
20
0
16
2
16
X
(a) Soybean.
(b) WDBC.
(c) Wine.
Figure Time to build X-Forest for different numbers of trees and Xs.
B-Similarity. For the WDBC datasct (Figure 8(b]j, the accuracy of the 3 = 0.7 version of B-Similarity is about 0.9% higher than that the
version of 3-Similarity, while the variance is 5.28 limes smaller. For the wine dataset (Figure 8(c) the accuracy of the 0.9 version of B-Similarity about 3.8% higher than that the 3 version of 3-Similarity, while the variance is 2.16 times smaller.
5.1.2 EXPERIMENTS ON SPEED
Building Speed X-Forest vs. X (Figure 9): In this experiment, we vary X (1, 2, 4, 8, 16) and the number X-Projection trees (160, 320, 640, 1280) in X-Forest and use Kernel K-mcans for clustering. When the number of X-Projection trees is 1280, for the soybean dataset (Figure (()) ), the speed the X 2 and X versions of X-Forest are respectively about 2.98 and 1.74 times faster than standard RP Trees. For the WDBC dataset (Figure 9(b) the speed of the X and X = versions X-Forest are respectively about 3.61 and 2.57 times faster than standard RP Trees. For the wine dataset (Figure 9(c) the speed of the = 2 and X versions of X-Forest are respectively about 1.34 and 1.03 times faster than standard RP Trees.
CONCLUSION
The design goals of an ideal similarity measurement solution respectively high accuracy, high elficiency in terms of speed and independence from priori knowledge the dataset. We propose X-Forestto achieve all the above goals: 1) We introduce RP Tree into similarity measurement because it better represents the similarity value between item pairs; 2) We manage to reduce computational time through sharing projection values the partition process of some layers; 3) We rely on randomness in partition to get rid of the need of priori knowledge the dataset, such as data distribution characteristics.

---

Under review as a conference paper at ICLR 2020
REFERENCES
Source code.
Treess
git
Jon Louis Bentley. Multidhmensional binary scarch trees used for associative scarching. Communications of the ACM, 18(9):509 517, 1975.
Daniel Billsus and Michael Pazzani. Learning collaborative information filters. In Ieml, volume 98, pp. 46 54, 1998.
Sung- Cha. Comprehensive survey on distance/similarity measures between probability density functions. City, (2):11, 2007.
Yihua Chen, Eric K Garcia, Maya R Gupta, Ali Rahimi, and Luca Cazzanti. Similarity- -ased classification: Concepts and algorithms. Journal of Machine Learning Research, (arM::): 747-776, 2009.
Sanjoy Dasgupta and Yoav Freund. Random projection trees and low dimensional manifolds. In STOC, volume 8, pp. 537-564 546. Citeseer, 2008.
Sanjoy Dasgupta and Yoav Freund. Random projection trees for vector quantization. IEEE Transactions on Information Theory, 55(7):3229 3242, 2009.
Sanjoy Dasgupta and Kaushik Sinha. Randomized partition trees for nearest neighbor search. Algorithmica, 72(1):237-263 2015.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http::/arcchive ics. www.uciuuuuu. edu/ml
Martin Ester, Pans-Peter Kriegel, Jörg Sander, Xiaowei Xu, et al. A density-based algorithm for discovering clusters in large spatial databases with noise. In Kdd, volume 96, pp. 226 231, 1996.
Xiaoli Z Fern and Carla E Brodley. Random projection for high dimensional data clustering: A cluster ensemble approach. In Proceedings of the 20th international conference on machine learning (ICML-03), pp. 186-193, 2003.
Anton F. Fliri, William T. Loging, Peter F. Thadcio, and Robert A. Volkmann. Biological spectra analysis: Linking biological activity profiles to molccular structure. Proceedings of the National Academy of Sciences, 102(2):261 266, 2005. ISSN 0027-8424. doi: 10.1073/ p019.0407790101. URL https://wwrt pnas orgg/oontent/10222/55
Katherine R Gray, Paul Aljabar, Rolf A Heckemann, Alexander Hammers, Daniel Rueck- ert, Alzheimer's ''s Disease Neuroimaging Initiative, et al. Random forest-based similarity measures for multi-modal classification of alzheimer's disease. Neurolmage, 65:167-175, -15, 2013.
John Hartigan and Manchek A Wong. Algorithm as 136: A k-means clustering algorithm. Journal of the Royal Statistical Society. Series C (Applied Statistics), 28(1):100-108, 1979.
Jasmine Irani, Nitin Pise, and Madhura Phatak. Clustering techniques and the similarity measures used in clustering: A survey. International Journal of Computer Applications, 134(7):9 14, 2016.
Raymond Austin Jarvis and Edward A Patrick. Clustering using a similarity measure based on shared near neighbors. IEEE Transactions on computers, 100 100(11::0055-104, 1973.
Abhinav K Jha, Jeffrey J Rodríguez, Renu M Stephen, and Alison T Stopeck. A clustering algorithm for liver lesion segmentation of difiuteon-weighheed mr images. In 2010 IEEE Soutlwees Symposium Image Analysis & Interprelation (SSTAT), pp. 93 96. IEFE, 2010.
10

---

Under review as a conference paper at ICLR 2020
Marcus A. Koch, Lars-Oliver Wittenberg, Sudipta Basu, Duraiswamy A. Jeyaraj. Eleni Gourzoulidou, Kerstin Reinecke, Alex Odermatt, and Herbert Waldmann. Compound library development guided by protein structure similarity clustering and natural product structure. Proceedings of the National Academy of Sciences, (44)):66711117222) 2004. doi: 10. p003/pnas.00e pp44.0140771100..
Yogiraj Singh Kushawah and Ashish Mohan Yadav. A survey on unsupervised clustering algorithm based on k-means clustering. International Journal of Computer Applications, 975:8887, 2016.
Wei-Ying Ma and Bangalore $ Manjunath. Texture features and learning similarity. In Proceedings CVPR IEEE Computer Society Conference Computer Vision and Pattern Recognition, pp. 425 430. IEEE, 1996.
David Minnen, Charles Isbell, Irfan Essa, and Thad Starner. Detecting subdimensional motifs: An efficient algorithm for generalized multivariate pattern discovery. In Seventh IEEE International Conference on Data Mining (ICDM 2007), pp. 601-606. IEEE, 2007.
Andrew Y Ng, Michael I Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In Advances in neural information processing systems, pp. 849 856, 2002.
Ricardo S Santos, Suzana MF Malheiros, Sergio Cavalheiro, and JM Parente De Oliveira. A data mining system for providing analytical information brain tumors to public health decision makers. Computer methods and programs in biomedicine, 109(3):269-22) 282, 2013.
Wei Shen, Xiang Bai, Zihao Hu, and Zhijiang Zhangg Multiple instance subspace learning via partial random projection tree for local reflection symmetry in natural images. Pattern Recognition, 52:306-316, 2016.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. Deportmental Papers (CIS), pp. 107, 2000.
Donghui Yan, Ling Huang, and Michael Jordan. Fast approximate spectral clustering. In Proceedings of the 15th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 907-916. ACM, 2009.
Donghui Yan, Yingjie Wang, Jin Wang, Honggang Wang, and Zhenpeng Li. K-nearest neighbors search by random projection forests. IEEE Transactions on Big Data, 2019.
11

---

Under review as a conference paper at ICLR 2020
A APPENDIX
The growth of the individual X-Projection Tree in X-Forest involves randomness both in projection directions and partition thresholds. A natural concern of the X-Forest would be whether the distances in the similarity kernel maintain the characteristics of the Euclidean space R". In this appendix, we will prove that during the growth of the X-Forest, far-away points in the Euclidean space will be partitioned with higher probability than the near points.
Recall that during the partition of tree node, will choose partition threshold randomly in the range of the projection values. As the behavior of the partition depends on this range, first introduce the definition of the range follows
Definition 4 Let 8 be set of points. Define the range of one particular projection the following
L(S,e) sup {|x1 X2E8
X2 e|}
and define its boundaries as
(S sup c(),c)
8(S) inf L(S.e) e)
EET
where I is the set of unit direction vectors, i.c., fc CER A | = 1}.
The upper bound p(S) can be seen as the largest distance of two points in IK,, and the lower bound ((S) is called neck size in Yan et al. (2019). Based on this definition, we will state that the probability of two points not being partitioned a tree can be bounded by a function. Without. loss of generality, we give the theorem and the proof under the 2-dimensional case with X 2. When it comes to the high-dimensionall the proof can become much more difficult because projection directions are chosen on the hyper-sphere. This may be desirable for the future work.
Theorem 1 Let S be set of points in IR2 on which the algorithm X X-Forest runs. Given two point A, B, E S having distance 1, the probubility of this two point not being partitioned in a X-Projection Tree after 2n steps satisfies
S F (1(5))
Pr(A and B not partitioned)
p(S)
Fx(x) *(n - ry! S" d0 f ( (-log =)n-1 dz
2
Proof. Let V be a random variable defined as below
[0, and not partitioned
V == 1, otherwise
Since the parameter is set as X 2, two projection directions will be chosen the beginning of the algorithm. Let a, b represent them respectively. Let Yi, Y2 be random variables representing the angle between the Lwo directions and AB respectively. It is obvious that. the angle locates the interval [0, π /2]. Because these vectors are uniformly and independently chosen at random from I, we have Y1.Yz i.i.d Up.=//2.
We first analyze the probability of A and B not being partitioned given particular 0 and 02, ie., Pr (V = 0 Y; 02, Y2 0z). We notice that the partition performed on the direction affects the partition on direction b. This is because the partition on direction a will reduce the elements of S, which shrinks the length L(S, b). If we assume that partitions on two directions are independent with each other, then this shrink will not happen. In this case, the probability of and B not partitioned in tree becomes larger. That is
Pr(V = 0 Y 01, Y, 02) S Pr(Va Y 01) Pr(V. 0 Y2 -f2)
(6)
12

---

Under review as a conference paper at ICLR 2020
where Va and Vo random variables representing whether point A and B are partitioned on direction a and b respectively, similar to V. It is obvious that Pr(Va = Y, = 81) has the same form as Pr(V, = 0 Y2 82), therefore we just need to focus the direction
Recall that when the depth of a tree node even, direction a will be used. Therefore, n partition thresholds will be chosen direction We can simplify the procedure of choosing n partition thresholds as shrinking the total length L(S, a) by n times. The probability of the final total length being bigger than 1 cos(O1) is the probability of the two points A and B not being partitioned in direction a. In our algorithm, the partition threshold is uniformly chosen at random in the current range recursively, which means that the shrink factor satisfies Up..j. Therefore, we have
Pr(Va =0 Yi 01) =Pr (T((S,)) 7,72 ... 7n 2 cos(01))
1 coss(01)
Prr (Z(m) 2 L(S,a)
(7)
where Z1, ......, Zn are iid random variables such that Zi ~ U|o,11, and (() is the product of Z1, L2 ... Zn.
We now derive the upper bound of the probability as the following
Pr(V 0) Pr
V
SO,
Yi S 2
Y2 1 S 2)
d0,
d02
Pr(V = 0 Yi = 01, Y2 = =0) -2) (x, SY,
0
where fy, and fv, is the probability density function (PDF) of Y1 and Yz. Combining (6), (7) and the result from Lemma 2 find
1 (coo(01)) Pr 2(n) 1 co0s T) -
Pr(V 0)
d0,
d0. Pr (Z(n)
Jo
T(S, b) T22
I coos(01) Pr [(n)) 2 1 ccos((2))
d8,
d02
Pr
[(())=
2
Jo
p(S)
p(S)
4
ds1 / conter)
d0
d02
dæz
(log 21 log 22) 22
72(n
1).2
coste11
F2
p(S)
The inequality of Theorem I shows that the probability of the two point not being partitioned has an upper bound (l())) However, the reader may want to know whether Fn gives reasonable bound for the probability. Therefore, give lemma to further illustrate the feature of Fn.
Lemma F, (x) is strictly monotonically decreasing function with respect to in (0, 1), and satisfies
F. 1, F.(1)=1 =0
First we prove that F, is strictly monotonically docreasing. It is obvious that (- log =)n-1 > for any (0, Therefore, given æ1, (0, 1) such that æ1 < 22,
Proof.
have
ft
(-log log 1)log))=111 dz > /
(- log z)n-1 dz
xycos(0)
13

---

Under review as a conference paper at ICLR 2020
Apply the inequality above to the expression of Fn yields
2
2
[
(2()))= T(n - 1)! Jo
dB
(- log 2)m de
x1cos(0)
2
So
d0
1-log))m-1 dz
T(n - 1)1
x2c0s(0)
(x2)
which indicates that Fg is strictly monotonically decreasing. Now we calculate
2
d0 / 2- dz
(a
T(n 1)!
Jo
1
(- log 2) de
(n 1)1
1
" wn1 _ du
(u = log =)
(n 1)!
1
[(n)
(n 1)!
1
2
d0 (
F,(1)
(-log 2)m dz
T(n
1)!
30
0
The combination of Theorem 1 and Lemma shows that the probability of far-away points not being partitioned in X-Projection Tree is low. This is because far-away points will have bigger I, resulting in smaller (²))/p(S) which approaches 0. On the other hand, near points will have a loose upper bound approaching 1, therefore they are more likely to stay together. In summary, state that the characteristies of the Euclidean space are maintained our X-Forest algorithm.
Lemma Suppose Z1, Zz, ... Zn i.dd random variables such that Z, Ulo.1-- Let (nn) 7, 72 ... Zn. The probability densily funclion (PDF) of ((n) is
(-loge)"-1 (n- 1y
fz(m) (x)
0,
otherwise
Proof. We use mathematical induction to prove the lemma.
Base case. When 1, we have ((n) Ujo1j-- Obviously the statement is true. Inductive step. Assume the statement holds for k. For brevity, we rewrite fz()(z) as fz(z).
First we calculate the cumulative distribution function (CDF) Z + 1) based on the assumption. For [0, 1] find
14

---

Under review as a conference paper at ICLR 2020
Pr (2( S 2) =
Pr (Z(k: + +1) s x
Z(k) = fk fk (v)
J0
[
[[]
_
1. Jn (v) dy +
Ju (v) dy
y
SN. (u) dy
Pr (Z(k) 2) +
y
Differentiating both sides we have
Su (v)
Su (x)
SK+1 (x) = Ja (x) +
dy
y
fu (v)
dy
y
k-1 log y)-11
1
dy
(he 1)!
y
(-t)k-1
logar (h: - 1}! dt
(t = log y)
log.rr k (k: 1)!
Therefore, the statement holds for n k 1 when x E [0, For x < 0 or x it is obvious that (z) = 0. In summary, the lemma holds for n = k +.1. 1.
15


Reviews:
[{"review_id": "rkeLgBkTtS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes the similarity measure called 'beta-similarity' generated by an ensemble of Random projection trees (RP trees) by Dasgupta & Freund (2008). To reduce the computational costs for building many RP trees, the paper develops an efficient approximate version called X-Projection trees by first generating X independent random projection directions, and then by sharing them at layers in turns. X-Forest is a set of X-Projection trees with X different random projections, and the proposed 'beta similarity' between x and y is defined by distances between a leaf region having x and one having y in PR trees. Experimental evaluations demonstrated that the use of beta similarity improves the clustering accuracy using it within three types of methods (kernel k-means, DBSCAN, Spectral clustering). \n\nThe paper's idea of defining a similarity using many RP Trees with different randomization is quite interesting and sounds promising given that the recently reported performance of tree ensembles such as XGBoost and LightGBM is very good. Partition-based trees plus randomizations are known to have very nice properties particularly in high dimensions, theoretically speaking.\n\nHowever, this paper also has several problems 1) novelty and 2) confusing and imprecise statements.\n\n1) novelty\n\nThe novelty of the paper is basically (a) a simple computation savings of X-forest and (b) a definition of beta similarity.\n\nFor (a), the novelty is rather small, and how much this computation savings have a practical impact is questionable since reported computation timings in Figure.9 are in ms. Furthermore, trivial parallelization would be possible because individual computations of RP trees in the ensemble are independent. Also, there exists a highly cited paper by Yan et al KDD'09 proposed a fast clustering method based on RP trees as \"fast approximate spectral clustering\" in their title.\n\nOn the other hand, (b) would be novel but any consideration about alternatives is not given, and the definition sounds quite heuristic and less convincing.\n\nRP trees are existing spatial structures (proposed by Dasgupta & Freund) extending widely used k-d trees. It naturally defines the spatial closeness of data points, and thus the use of RP trees to define the similarity, and applying them to clustering (kernel k-means, DBSCAN, spectral) is not new. RP trees were proposed as an alternative of k-d trees, and the primary applications would be for nearest neighbor search or data compression like vector quantization. \n\n2) confusing and imprecise statements\n\nMany confusing and imprecise statements exist. \n\n2a) The proposed 'beta similarity' eq (2) seems to lack the definition of DIS_i(X, Y). It would be something like the path length between node X and Y, or steps to the LCA (the lowest common ancestor). Also, the number m (the number of trees?) is also undefined.\n\n2b) The three goals are set: accuracy, efficiency, and independence from prior knowledge. But when we use RP trees, 1st and 3rd are considered as resolved and sounds like the only remaining problem is 'efficiency' for their computations. Also, the third goal 'independence from prior knowledge' is quite vaguely explained, and hard to understand. For example, the affinity matrix in spectral clustering or kernel matrix with an RBF kernel is the case? It would be a kind of hyperparameters but not like 'dependence on prior knowledge'.\n\n2c) Also, 'accuracy' of 'similarity measurements' is quite ambiguous. The use of kernel distance with RBF kernel is less accurate than the use of RP trees?? The \"similarity measurement\" sounds like the problem of definition, and it cannot be accurate or inaccurate. The distance-based similarities themselves have no problems, and even when RP trees are used, we need some distance metric (i.e. Euclidean distance) in a space.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "Skx3jJ6qFB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers random projection forests for similarity measurements (which have been proposed earlier) and proposes to accelerate them by reusing projections. Tree levels up-to level-X use distinct random transformations, and subsequent levels cycle through existing projections (X of them). As this kind of reuse reduces the quality of trees, the paper proposes to (greatly) increase the number of trees in the forest. The paper also introduces a sensible \"beta-similarity\" which is based on average tree-distance between leafs into which the two data-points fall, rather than fraction of trees in which they fall into the same leaf-node. \n\nI recommend to reject the paper -- as the contribution in my opinion is incremental, not principled (more of an engineering trick) and not very convincing. Furthermore, the paper has a number of issues with presentation, language, and experimental results. RP trees have been introduced over a decade ago (Dasgupta and Freund, 2008), and the authors cite a reference to RP forests from (Yan et al, 2019, IEEE Big data). Level-wise use of the same projection within a tree (that the authors call \"layer-by-layer RP Trees\") has been discussed (and shown to be effective) in the original Dasgupta and Freund paper.  The paper makes it very hard to understand what is a contribution, and what is borrowed from existing papers -- as the authors say \"we introduce\" both for well-known concepts (like RP trees), and for what I understand to be their contribution. I would ask to clearly state what is existing work, and what is new, and what are the key contributions.\n\nOther comments. \n1. Experiments:  you cite a paper on RP-forests (Yan et al, 2019) -- so ensembles of RP trees have already been proposed.  Why in the experiments you still compare only to a single RP-tree?  You report speed gains ~ 2x or 3x  w.r.t standard RP Trees -- even when you use very many (hundreds or thousands of trees in an X-forest).  Are these layer-by-layer RP trees, or do you use new random projection for each node? Are these your implementations of RP trees, or did you use existing code? The experiments do not provide enough details on the implementation to judge their significance -- e.g. 2x gain of speed could be achieved by better software implementation of the same algorithm.  Is it standard to measure clustering quality by  taking a classification problem and assuming that clusters should correspond to class labels? There are various other measures of cluster quality that do not rely on labels (e.g. rand-index, homogeneity, ratio of within-cluster to inter-cluster distances e.t.c.).\n\n2. In figure 8, (a),(b),(c) -- it looks like choice of beta can have a dramatic impact on accuracy, and can either be monotone, or peak at intermediate values.  How do you propose to chose beta in practice -- don't you need supervision?  What is the cost to compute beta-similarity compared to naive 0-1 similarity?\n\n3. The claim that similarity measures should be independent from prior knowledge -- can be controversial -- and is not a widely accepted truth. The field of metric learning tries to find better similarity matrices based on additional prior information. It's hard to imagine that a single similarity matrix will be suitable for all problem domains. I agree that it's useful to have a generic default similarity measure to try first, but clearly if prior data is available it should be used. \n\n4. In addition to \"mathematical distance-based similarity\" and tree-based similarities -- there is also considerable work on similarity based on non-linear embeddings -- e.g. T-SNE or UMAP, provide an embedding, and then a simple cosine similarity can be used after the embedding. Overall -- this is a complex nonlinear similarity measure, not captured by your two classes. \n\n5. A well known paper \"Extremely randomized trees\" also proposes kernels (similarity measurements) based on a forest created with (nearly) random splits, and should be cited, and used in comparisons. There is even a scikit-learn implementation -- called random trees embedding.\n\n6. The introduction of the paper:  \"Similarity measurement is to measure similarity...\" conveys no information. The entire first paragraph does not have much content, and should be rewritten or skipped.  Bad word choice:  Unsupervised clustering is \"to classify\", \"Exalted speed\", dimension of original dataset is \"degraded\"...   If you say \"we introduce RP Trees\" -- it sounds like you propose them in this paper -- which is clearly not the case, as you cite Dasgupta and Freund's paper.   You can instead say -- we consider RP trees introduced by (ABC)... \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "SkgRmZra5r", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new method for measuring pairwise similarity between data points. The idea is to define the similarity between two data points to be the probability (over the randomness in constructing the trees) that they are close in an RP tree. More concretely, the proposed method constructs a collection of RP trees (albeit with some modifications), and takes the similarity to be the average over different RP trees of a strictly decreasing function of the distance between the leaf nodes containing the data points in each RP tree. The key modification to the RP tree is to limit the number of projection vectors used in an RP tree and re-use previous projection vectors. \n\nI believe the method is more or less equivalent to Euclidean distance, for the following reason. Two data points would have the highest similarity under the proposed similarity measure if they are in the same leaf node. For this to happen, both points must be on the same side of the dividing hyperplane corresponding to each of the ancestor nodes. Because the threshold along the projection vector is chosen randomly at uniform, this means that for the two data points to have high similarity consistently, the distance between them along the projection vector must be small (so that the probability of splitting them is small). Because the projection vectors themselves are chosen randomly on the unit sphere, this implies that this must hold along most projection vectors for similarity to be high consistently, which means that the Euclidean distance between the two points must be low. \n\nIf true, this raises several questions:\n\n1) Why does the proposed method work better than distance similarity (which I assume means Euclidean distance) in the experiments? Are there situations when the proposed method would yield a high similarity consistently whereas Euclidean distance wouldn’t? Are the results in Fig. 6 just for a single run of the proposed method? If so, many more runs need to be performed since the decisions of the RP tree should vary significantly depending on the projection vectors and thresholds. Both the mean and standard deviation should be reported. \n2) In Sect. 1.2, the authors critiqued distance-based similarity because it often does not correspond to intuitive notions of similarity/perceptual similarity. However, it does not appear that the proposed method would correspond to perceptual similarity either. For example, consider a dataset where some coordinates are more perceptually important than others (this is the case for example for the wavelet coefficients of a natural image - the lower frequencies are typically more perceptually important than higher frequencies). A more perceptually meaningful distance than Euclidean distance would be a Mahalanobis distance (which can essentially weight different coordinates differently), but the random projections use standard inner products and so are unable to capture the appropriate weighting of the different coordinates. So, why would one expect the proposed method to be more perceptually meaningful?\n3) In Sect. 1.2, the authors critiqued multi-partition-based similarity because it does depend on the data distribution and cited the elimination of “prior knowledge dependence” in Sect. 1.3 as one of the benefits of the proposed method. This appears to be at odds with the goal of devising a similarity measure that is perceptually aligned, because such a similarity measure must depend on the representation of the data (e.g.: if the data is represented in the wavelet domain, one needs to know which order the different dimensions are arranged, i.e. from lowest frequency to highest frequency or the other way around). \n\nOverall, it is unclear if the desiderata makes sense, and if the proposed method achieves the objectives. \n\nOther questions:\n\n4) For the X-Projection tree (which re-uses projection vectors), it seems to be equivalent to a layer-by-layer RP tree with larger branching factor. If so, the presentation of the method should be changed to this, because a layer-by-layer RP tree with larger branching factor is both conceptually clearer and simpler to analyze. If not, the proposed method should be compared to a layer-by-layer RP tree with larger branching factor, to justify the increased conceptual complexity of the X-Projection tree. \n5) For the experiments, comparisons should also be made to multi-partition-based similarity, like Multiple RP+EM and RF similarity. \n6) In addition, the proposed method should be compared to two simpler baselines that computes the average and the minimum distance of the two points along multiple random projection vectors, in order to justify the increased conceptual complexity of RP trees. \n7) In Sect. 1.3, the paper claims that “it is well known that in an RP Tree, data points that are closely distributed, indicating their high level of similarity in space, are always partitioned into the same subset”. This is not true, since hyperplane could divide a cluster down the middle for example. \n8) One of the claimed contributions in the abstract that “we introduce randomness into partition to eliminate its reliance on prior knowledge”. Note that just by introducing randomness, prior knowledge is not necessarily eliminated. For example, the way in which random projection is performed (i.e. standard inner product vs. other inner products) assumes knowledge of the distance metric, which is induced from the inner product. \n9) In Fig. 6, what is the distance metric used for the baseline?\n\nMinor issues:\n\npg. 2: “project all data points into one random vector” -> “project all data points along one random vector”\npg. 3: “leading to unsatisfied results“ -> “leading to unsatisfactory results”\npg. 3: “nearest neighbours finding” -> “nearest neighbour search”\npg. 3: “pattern discovering” -> “pattern discovery”\npg. 4: “similarly data points” -> “similar data points”\npg. 4: “01 matrix” -> “0-1 matrix”", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new method for measuring pairwise similarity between data points. The method is based on the idea that similarity between two data points to be the probability (over the randomness in constructing the trees) that they are close in a Random Projection tree. 

Reviewers found important limitations in this work, pertaining to clarity of mathematical statements and novelty. Unfortunately, the authors did not provide a rebuttal, so these concerns remain. Moreover, the program committee was made aware of the striking similarities between this submission and the preprint https://arxiv.org/abs/1908.10506 from Yan et al., which by itself would be grounds for rejection due to concerns of potential plagiarism. 
As a result, the AC recommends rejection at this time. 
Decision: Reject