DotHash: Estimating Set Similarity Metrics for Link Prediction and Document Deduplication

Consider the sets $A$ and $B$, and let $A\cap B$ denote their intersection and $A\cup B$ their union. The Jaccard index (Jaccard, 1912) between $A$ and $B$ is defined as:

where the vertical bars denote the cardinality of the enclosed set. This is one of the oldest and most established ways of comparing sets. Over time, numerous adaptations of this simple metric have emerged, specializing it for particularly interesting applications. Next, we describe one of these adaptations which is widely used, especially in network science (Barabási, 2013).

The Adamic-Adar index was created for the problem of link prediction in social graphs (Adamic and Adar, 2003). Let $G=(V,E)$ be a graph, composed of a set of nodes $V$ and a set of edges $E$. Each $e=(u,v)\in E$ represents an edge (or link) between nodes $u,v\in V$. With $\Gamma\mathopen{}\mathclose{{}\left(v}\right)\subseteq V$ we denote the subset of nodes that are adjacent to $v$, i.e., the neighbors of $v$. The cardinality of a neighborhood $|\Gamma\mathopen{}\mathclose{{}\left(v}\right)|$ is referred to as the degree of $v$.

In the context of graphs, Jaccard can be used to compare pairs of nodes by looking at how many connections they have in common, normalized by the size of the union of their neighborhoods. Adamic-Adar seeks to improve this comparison based on the intuition that the more popular a node in the intersection is (i.e., the higher its degree), the less informative it is about the similarity of the nodes being compared. In the case of social networks, for example, a common connection with a celebrity says little about the chance of two people connecting with each other compared to a less popular mutual friend. To account for this, Adamic-Adar penalizes the number of connections that each shared connection has by taking the logarithm of its degree. Formally, the Adamic-Adar between two nodes is defined as:

Given the importance of link prediction, several other metrics have emerged for the purpose of comparing neighborhoods. Similar to Adamic-Adar, these metrics take the local properties of the nodes in the intersection into account. Many of these metrics can also be directly estimated using DotHash. One such example is the Resource Allocation index, used to evaluate the resource transmission between two unconnected nodes through their neighbors which is defined as:

In Section 4.5, we provide a formal description of the family of set similarity metrics that DotHash can directly estimate.

MinHash (Broder, 1997) is a probabilistic method for estimating the Jaccard index. The technique is based on a simple intuition: if we uniformly sample one element $x$ from the set $A\cup B$, we have that:

which makes the result of this experiment an estimator for Jaccard. However, an important problem remains: how to uniformly sample from $A\cup B$? Explicitly computing the union is at least as expensive as computing the intersection, that is, it would be as expensive as calculating the Jaccard index exactly. The main merit of MinHash is an efficient way of circumventing this problem.

Let $h:A\cup B\to\mathbb{N}$ denote a min-wise independent hash function, i.e., for any subset of the domain, the output of any of its elements is equally likely to be the minimum (see Broder et al. (2000) for a detailed discussion). Then, we have:

Given the above, the problem of uniformly sampling an element of the union and checking if it belongs to the intersection can be emulated as follows: hash the set elements and check if the smallest value obtained in both sets is the same. Although the result of this random variable is an unbiased estimator of the Jaccard index, its variance is high when the Jaccard is around 0.5. The idea of MinHash is therefore to do $k$ such experiments with independent hash functions and return the sample mean to reduce the variance.

SimHash (Charikar, 2002), sometimes indistinctly called angular LSH, is another popular estimator of set similarity. The sketches of sets are fixed-length binary vectors and are generated as follows: 1) all elements of the superset $S$ are mapped uniformly to vectors in $\{-1,1\}^{d}$; 2) for each set $X\subseteq S$ a $d$-dimensional vector is created by adding the vectors of its elements; 3) the SimHash sketch of the set is a bit string obtained by transforming each positive entry to one and the non-positive entries to zero. The similarity between pairs of sets is then measured by the Hamming distance between these sketches.

Despite being a general estimator for set similarity metrics, SimHash owes its popularity largely to a specific use. Manku et al. (2007) showed an efficient way to solve the following problem: in a collection of SimHash sketches, quickly find all sketches that differ at most $k$ bits from a given sketch, where $k$ is a small integer. This particular formulation is very useful in the context of duplicate text detection and its efficient solution led to SimHash being used by Google Crawler.

The problem described above is an instance of the problem known as locality sensitive hashing (LSH) which, in general, tries to detect pairs of objects whose similarity exceeds a threshold by maximizing the collision probability of the hashes of these objects (Indyk and Motwani, 1998; Indyk et al., 1997). Note that LSH is used to group similar objects and the output is binary, i.e. two objects are either similar or not (Leskovec et al., 2020). Therefore, we emphasize that the problem of estimating the metrics directly, addressed in this paper, is different from LSH. Directly estimating similarity has other possible outcomes, such as ordering pairs by similarity, which is crucial in some applications like query optimization (Cormode et al., 2011) and link prediction as we will discuss in Section 5.

Although SimHash is much more popular in the context of LSH, for the sake of completeness, but underscoring the above, we consider SimHash as a baseline of the general problem as the method was originally proposed by Charikar (2002). Despite this, we make it clear that the other baseline, MinHash, is much more common in the literature for the problem of estimating the actual value of metrics as we discuss in the next section.

Our primary focus in this study is to address the task of estimating set similarity metrics in its broadest sense. However, it is important to acknowledge other advancements in the field that are not directly aligned with our specific contribution. These advancements, discussed below, primarily involve enhancements tailored to specific contexts and applications. It is important to note that our method is not intended to directly compete with these notable developments in each individual application, but rather aims to serve as a new baseline for the general problem. We emphasize, however, that DotHash also brings practical contributions to the state of the art. This is achieved by supporting a wider range of metrics, which is formally defined in Section 4.5. As we will show in Section 5, this allows for greater accuracy in important problems such as link prediction and document deduplication.

While MinHash remains the standard framework for estimating the actual value of set similarity metrics, several techniques have been proposed to enhance its accuracy and efficiency in specific application contexts. For instance, Chum and Matas (2012) propose an efficient method to compute MinHash sketches for image collections using inverted indexing. Another technique, introduced by Koslicki and Zabeti (2019), employs Bloom filters for fast membership queries and is known as containment MinHash. They demonstrate the superiority of this technique in metagenomic analysis by more accurately estimating the Jaccard index when dealing with sets that significantly differ in size.

Several other works have focused on a variant of the problem that involves estimating the weighted Jaccard index (Wu et al., 2020). For datasets with sparse data, Ertl (2018) and Christiani (2020) have explored the concept of consistent weighted sampling (CWS) (Ioffe, 2010) with their respective BagMinHash and DartMinHash techniques. Conversely, when dealing with dense data, methods based on rejection sampling have been demonstrated to be more efficient (Shrivastava, 2016; Li and Li, 2021).

Another important recent endeavor has been to develop LSH techniques based on deep learning, known as “learn to hash” methods. These include Deep Hashing (Zhu et al., 2016) and various others (Dutt et al., 2019; Hasan et al., 2020; Kipf et al., 2018). In general, these techniques do not estimate any particular metric directly, but seek to create sketches that allow for approximate nearest neighbor search. Another key distinction lies in the methodology employed by these approaches. They rely on constructing trained models through annotated data, where the concept of similarity is derived from the mapping of training examples to a specific target. Consequently, this similarity may not necessarily extend to other datasets, making it potentially non-generalizable. In contrast, the methods discussed in this paper estimate the similarity between two sets solely based on the sets themselves.

Although “learn to hash” methods have demonstrated promising accuracy in situations where supervised learning is viable, their broader adoption has also been hindered by other challenges. These limitations encompass high costs associated with training and inference, the inherent unpredictability due to unknown bounds in estimation error, and their high sensitivity to data distribution, often concealed by the reliance on purely empirical assessments (Kim et al., 2022; Wang et al., 2021). As a result, traditional methods such as MinHash and SimHash continue to be utilized in important applications such as the ones mentioned earlier. Despite the inherent differences and the difficulty of setting up an accurate and unbiased study that delves deep into both approaches, we believe that a comparative study between these traditional methods and learning-based approaches would yield significant value for the scientific community.

A common way of representing sets is by using bit strings (Rosen, 2012; Fletcher et al., 2018). In this representation, an arbitrary order $[x_{1},x_{2},\dots,x_{d}]$ of the elements of the superset $S$ is established. Then, each set $X\subseteq S$ is represented by an $\mathopen{}\mathclose{{}\left|S}\right|$-dimensional binary vector whose $i$-th bit is one if $x_{i}\in X$, and zero otherwise. Table 1 illustrates this representation for sets $A=\{a,b,c,d\}$ and $B=\{b,c,d,e\}$. This representation is especially common for graphs, where it is called an adjacency matrix, and each set consists of the neighborhood of a node.

It is easy to observe that the size of the intersection between $A$ and $B$ is given by the number of columns where both elements are one. This provides a straightforward way to get the size of the intersection of sets: calculate the dot product between their bit strings (Fletcher et al., 2018; Brusco et al., 2021).

An alternative way of visualizing the set bit strings, important for the generalization we propose, is: consider that each element $x_{i}\in S$ is encoded by an $\mathopen{}\mathclose{{}\left|S}\right|$-dimensional vector of value one in position $i$, and zero elsewhere. This representation is usually called one-hot encoding. From this, we can define the bit string of a set as the sum of its one-hot encoded elements, as illustrated in Figure 1.

In Theorem 1, we show that the dot product results in the intersection of sets not only when they are the sum of one-hot encoded elements, but more generally when we encode the elements using any orthonormal basis of $\mathbb{R}^{\mathopen{}\mathclose{{}\left|S}\right|}$, of which one-hot is a particular case—the standard basis. Although this, arguably trivial, generalization alone may not seem advantageous at this point, in the next section we show how it is fundamental in the transition from exact to estimation with our method.

While the above yields a way of representing sets so that we can compute intersection sizes by simple dot products, notice that each set is represented using $\mathopen{}\mathclose{{}\left|S}\right|$ bits, resulting in a time and space complexity of $O\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left|S}\right|}\right)$. Although this can be useful in certain scenarios, clearly this method becomes prohibitively expensive for very large supersets $S$, for example, in the large scale applications described in the previous sections. Another problem is that in many real applications, such as those related to social networks, the sets change over time, so there is no way to establish the superset size a priori.

In some cases the time and space complexity can be improved to $O\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left|A}\right|+\mathopen{}\mathclose{{}\left|B}\right|}\right)$ by restricting $\phi\mathopen{}\mathclose{{}\left(\cdot}\right)$ to the standard basis encoding, represented using a sparse vector format so that only the non-zero elements are stored. With this modification the dot product can be computed by iterating over both vectors at once, similar to merging lists. However, because of the overhead of sparse vector representations, this is mainly useful when $\mathopen{}\mathclose{{}\left|A}\right|+\mathopen{}\mathclose{{}\left|B}\right|\ll\mathopen{}\mathclose{{}\left|S}\right|$.

There are still limitations to the sparse vector improvement, especially when even $\mathopen{}\mathclose{{}\left|A}\right|+\mathopen{}\mathclose{{}\left|B}\right|$ is very large. This happens both in social networks where nodes can have more than a million connections, and in document deduplication where large documents can hold many word sequences. In the next section we present a method to improve the time complexity to a constant value by giving up the exact intersection size in favour of an estimate.

The method described above seems unsuitable for large scale applications as it requires a number of dimensions equal to the size of the superset. This constraint is imposed by the fact that the smallest real vector space with $\mathopen{}\mathclose{{}\left|S}\right|$ orthogonal vectors is $\mathbb{R}^{\mathopen{}\mathclose{{}\left|S}\right|}$. Intuitively, we need orthogonality so that $\phi\mathopen{}\mathclose{{}\left(x}\right)\cdot\bm{a}=1$ if, and only if, $x\in A$, and zero otherwise. This ensures that $\bm{a}\cdot\bm{b}=\mathopen{}\mathclose{{}\left|A\cap B}\right|$ (for a detailed discussion see the proof of Theorem 1 in the Appendix A.1). From an information theory perspective, this guarantees a lossless representation of the sets by the sum of the encoded elements, since by the above operation we can verify exactly which elements make up the set.

Our proposed estimator, DotHash, relies on a very interesting property of high-dimensional vector spaces: uniformly sampled vectors are nearly orthogonal, or quasi-orthogonal, to each other with high probability (Kanerva, 2009). This valuable feature has been explored in several other domains, especially to model human cognition and memory (Kanerva, 1988; Gayler, 2003). It is based on this insight that DotHash turns the above method into an estimator for the size of the intersection of sets.

Instead of using a precisely orthonormal basis of vectors of $\mathbb{R}^{\mathopen{}\mathclose{{}\left|S}\right|}$ to encode the elements of $S$, DotHash uses unit vectors sampled from $\mathbb{R}^{d}$, with $d<\mathopen{}\mathclose{{}\left|S}\right|$. The set sketches (fixed-length representations) are then built in the same way, by adding the encodings of their elements, as depicted in Figure 2. Intuitively from the above, each encoded element would be quasi-orthogonal to all others, allowing to approximate the dot product relations mentioned above. In Theorem 2 we formalize this idea, showing that the the dot product between the DotHash sketches of sets is an unbiased estimator for their intersection cardinality.

Using the variance provided in Theorem 2 and the Chebychev inequalty we can bound the probablity of error by:

If we use the observation that each dimension can be interpreted as an independent sample, we can use the Central Limit Theorem (CLT) to approximate the probability of error as follows:

where $\Phi\mathopen{}\mathclose{{}\left(\cdot}\right)$ denotes the standard normal cumulative distribution function. In Figure 3 we provide the CLT estimate (solid line) and the empirical probability (dashed line).

We can rewrite the CLT (or the Chebychev inequality) to get the required number of dimensions $d$ to obtain an error greater or equal to $\epsilon\mathopen{}\mathclose{{}\left|A\cap B}\right|$ with a given probability $p$:

where $\Phi^{-1}\mathopen{}\mathclose{{}\left(\cdot}\right)$ denotes the standard normal percent point function.

Now that we have established a method for estimating the size of the intersection, we describe how to adapt DotHash to estimate the Adamic-Adar index. The idea starts from the fact that $\bm{a}$ and $\bm{b}$ are sums of the vectors that encode the elements of their respective sets. Given this and the distributive property of the dot product over addition, we have:

Observing that $\mathbb{E}\mathopen{}\mathclose{{}\left[\psi\mathopen{}\mathclose{{}\left(a}\right)\cdot\psi\mathopen{}\mathclose{{}\left(b}\right)}\right]=1$ if $a=b$, and zero otherwise (see the proof of Theorem 2):

The right-hand side of this equation is similar to Adamic-Adar in that both sum values over the intersection items. The key missing part is that the value to be summed must be a function of the size of the neighborhoods, not a constant.

In the above case, the summation parameter is one because every element is encoded to a unit vector. However, the construction of DotHash allows us to adjust the summation parameter by modifying the magnitude of the vectors used to represent each element. To obtain the Adamic-Adar index, we want each element, in this case each node, to be encoded in such a way that:

Theorem 3 shows how to adapt the vector magnitudes to obtain the Adamic-Adar index.

Building upon the result presented in the previous section, we naturally extend it to encompass a general formulation of all set similarity metrics that can be directly estimated using DotHash. This family includes all metrics of the form: $\sum_{x\in A\cap B}f(x)$, where $f:S\to\mathbb{R}$ is any function on intersection elements. Besides the item $x$, the function $f$ can use any global parameters such as the cardinalities of $A$, $B$ or $S$. The DotHash sketches for this general set similarly metric are given by:

and the estimate is obtained by $\bm{a}\cdot\bm{b}$. Observe that the intersection size, the Adamic-Adar index, and the Resource Allocation index all fit into this general framework: the intersection size corresponds to $f(x)=1$, Adamic-Adar to $f(x)=\frac{1}{\log{\mathopen{}\mathclose{{}\left|\Gamma\mathopen{}\mathclose{{}\left(x}\right)}\right|}}$, and Resource Allocation to $f(x)=\frac{1}{\mathopen{}\mathclose{{}\left|\Gamma\mathopen{}\mathclose{{}\left(x}\right)}\right|}$. This group of metrics directly supported by DotHash includes the majority of metrics listed in Martínez et al. (2016) and  Lü and Zhou (2011).

An overview of the datasets used is shown in Table 2. To compare the methods under different circumstances, we consider a range of common benchmarks used in the literature that have different characteristics and are associated with different applications. For the link-prediction task we evaluate each method on the following datasets:

• •

  Drugs (Guney, 2017): This dataset represents the interaction between drugs, where the joint effect of using both drugs is significantly different from their effects separately.

• •

  Wikipedia (Rozemberczki et al., 2019): This dataset represents a webpage network where each node represents a web page and the edges represent hyperlinks between them.

• •

  Facebook (Rozemberczki et al., 2019): A network of verified Facebook pages where nodes correspond to Facebook pages and edges are the mutual likes between pages.

• •

  Proteins (Szklarczyk et al., 2019): Is a protein network where nodes represent proteins from different species and edges show biological meaningfulness between the proteins associations.

• •

  Epinions (Richardson et al., 2003): Represents the who-trusts-whom social network of the general consumer review site Epinions.com, where each node represents a user, and each edge is a directed trust relation.

• •

  Slashdot (Leskovec et al., 2008): Represents the Slashdot social network as of February 2009, where each node is a user and each edge is a directed friend/foe link.

For the document deduplication we use the following datasets:

• •

  CORE Deduplication Dataset 2020 (Gyawali et al., 2020): This dataset consists of more than 1.3M scholar documents labeled as duplicates or non-duplicates.

• •

  Harvard Dataverse Duplicate Detection Restaurant dataset (Ali, 2022). This dataset consists of a collection of 864 restaurant records containing 112 duplicates.

• •

  Harvard Dataverse Duplicate Detection cddb dataset (Ali, 2022): This dataset contains a set of 9,763 records with 299 duplicated entries, with each row representing information about a particular audio recording.

This experiment aims to demonstrate a practical advantage of DotHash. While the baseline estimators, MinHash and SimHash, are limited to estimating the Jaccard index, DotHash offers the ability to estimate more complex metrics, known to be more effective for certain applications, including link prediction. We evaluate the accuracy of each estimator in solving the link prediction problem. The problem consists of inferring which links will appear in the future, called the inference time interval, given a snapshot of a graph (Liben-Nowell and Kleinberg, 2007). In practice, the task is seen as a ranking problem for pairs of nodes, i.e., the approaches compare pairs of nodes and predict that the most similar pairs are those that are likely to connect in the future.

The quality of the methods is evaluated based on how well they rank pairs that effectively form in the inference time interval, against random pairs that do not connect. These edges are respectively called the positive and negative samples. The most popular metric, Hits@$K$, counts the ratio of positive edges that are ranked $K$ or above the negative edges (Hu et al., 2020). The Jaccard, Adamic-Adar, Common Neighbors, and Resource Allocation indices are all used in the literature for establishing this ranking.

The results, presented in Figure 4, provide evidence to substantiate the claim that estimating more appropriate metrics makes DotHash a better estimator for the link prediction problem. By employing sufficient dimensions and selecting suitable metrics, DotHash consistently outperforms the baselines across all datasets and approaches the exact indices, shown in dashed lines. Each solid line represents the mean of the values observed in the five repetitions, and the corresponding colored shades show the 95% confidence interval. Importantly, as explained in the previous section, the adoption of DotHash does not impose a significant additional computational burden compared to the baseline methods. Figure 5 shows the normalized execution time of each method on the same datasets. For more details on execution times, please refer to Appendix B.

The detection of duplicate documents was the first major application to motivate the development of set similarity estimators. Both MinHash and SimHash were developed and became popular for their use in deduplicating web pages in Google and Alta Vista search engines. With our experiments in this section we seek to show how DotHash compares to these methods in this important problem.

Once again, we took advantage of the broader capability of DotHash to estimate a metric richer than the Jaccard coefficient between documents. While MinHash and SimHash give equal weight to shingles (sequences of words) when comparing documents, with DotHash we can assign different weights to reflect how important each shingle is to each document in the corpus. Our intuition is that the more important a term is to identify each text, the more its presence in different texts indicates their similarity.

One of the most popular ways of evaluating how important a term is to a document is by the inverse document frequency, or IDF (Jones, 1972). The measure is widely used in the information retrieval literature for text mining (Robertson, 2004; Henzinger et al., 2003), and is defined as:

where $|D|$ is the number of documents in the entire corpus and $|\{d\in D:x\in d\}|$ the number of documents that contain the term $x$. Given this, we can compare documents $A$ and $B$ not only by the number, but also by the importance of common shingles, as follows:

which is in the family of functions that DotHash can estimate.

In Table 3 we show the comparative results between the three estimators for the near-duplicate detection problem in the three different datasets described in Section 5.1. For each estimator we present the near-duplicity detection accuracy in terms of Hits@25 and execution time in seconds. The number of hash values and dimensions for MinHash, SimHash, and DotHash were set to 128, 500, and 10,000, respectively. These values were chosen to ensure comparable accuracy and enable the observation of differences in computational efficiency between the algorithms.

The numerical results presented indicate that DotHash is able to surpass the accuracy of MinHash in all datasets, even with a number of dimensions in which its execution time is between 0.5 and 3$\times$ faster. The same is observed in the comparison with SimHash, which obtains the lowest accuracy in all cases. These empirical results reinforce the findings observed in the link prediction experiments, highlighting the advantage of DotHash. By efficiently estimating richer metrics through a single dot product computation between set sketches, DotHash consistently delivers superior cost-benefit compared to other estimators.