From Local to Global: Geodesic Distance for Semantic Similarity

从局部到全局：语义相似度的测地线距离 苏剑林 · 2022-12-07 · Machine Learning riemannian geometry semantics semantic similarity

I recently came across a new concept in a paper titled Unsupervised Opinion Summarization Using Approximate Geodesics, called "Geodesic Distance." I found it quite interesting, so I wanted to share it with you.

For me, what's "new" here isn't the concept of geodesic distance itself (I already encountered it back when studying Riemannian geometry), but rather the discovery that the field of semantic similarity can also cleverly construct geodesic distances and put them to good use in certain scenarios. If we like, we could even call this "semantic similarity on a manifold" — sounds fancier already, doesn't it?

Paper Overview

First, let's briefly summarize the main content of the original paper. As the name suggests, the paper's topic is summarization. Typically, unsupervised summarization works like this: assume an article consists of $n$ sentences $t_1,t_2,\cdots,t_n$, and we design a scoring function $s(t_i)$ for each sentence (the classic choice being tf-idf and its variants), then pick out the sentences with the highest scores as the summary. Of course, this paper doesn't do plain summarization but "Opinion Summarization." Here, "Opinion" can be understood as a given topic or focus $c$ — the summary should tend to extract sentences related to $c$, so the scoring function should also depend on $c$, i.e. $s(t_i, c)$.

Ever since "everything is an embedding," a mainstream design for $s(t_i,c)$ has been to encode both the sentence $t_i$ and the topic $c$ into their corresponding sentence vectors $\boldsymbol{v}(t_i),\boldsymbol{v}(c)$, and then use the reciprocal of some distance as the scoring function:

\begin{equation}s(t_i, c) = \frac{1}{d(\boldsymbol{v}(t_i), \boldsymbol{v}(c))}\end{equation}

In this design, both the sentence-vector encoding model $\boldsymbol{v}(\cdot)$ and the distance function $d(\cdot,\cdot)$ are open to design choices. The original paper does some work on both $\boldsymbol{v}(\cdot)$ and $d(\cdot,\cdot)$, but $\boldsymbol{v}(\cdot)$ isn't the focus of this post, so I'll set it aside — interested readers can check the original paper. As for the paper's contribution regarding $d(\cdot,\cdot)$, it replaces the common simple distance with today's topic: "geodesic distance."

Analysis of the Underlying Idea

Why use geodesic distance at all? This has to do with how we typically train sentence vectors.

Sentence vectors can be learned either in a supervised or unsupervised manner. Take the supervised case as an example: generally, we do contrastive learning using positive and negative sample pairs (see CoSENT (I): A More Effective Sentence Vector Scheme Than Sentence-BERT). A positive pair marks two sentences that are essentially semantically equivalent, so we can say they have high similarity, or small distance. The problem lies with negative pairs: as two semantically distinct sentences, they might be specially labeled hard negatives, or they might just be two randomly chosen unrelated samples. In principle these two cases ought to be assigned different distances, but in practice they are both just marked with the same label — "negative."

This leads to a consequence: the distance values computed from our sentence vectors are, in theory, only accurate for sentences that are semantically quite close to each other. For sentences with a larger semantic gap, the distance value can only be used to distinguish positive from negative samples, but cannot be meaningfully compared within that far-apart range. For example, we can say that a distance of $1$ indicates greater similarity than a distance of $2$, and likewise a distance of $1$ indicates greater similarity than $10$, but we cannot say that a distance of $10$ indicates greater similarity than $11$ — because once the distance grows large, its absolute value is no longer reliable.

In retrieval scenarios, we usually want to recall samples with very high similarity (i.e., very small distance), so it's fine to just use a simple distance function $d(\cdot,\cdot)$ directly for retrieval. But in the "Opinion Summarization" scenario of the original paper, what needs to be computed is the distance $d(\boldsymbol{v}(t_i), \boldsymbol{v}(c))$ between a sentence $t_i$ and a topic $c$, and the similarity between a "sentence" and a "topic" is not necessarily very high (i.e., the distance tends to be large). In other words, we need to make relative comparisons in the region where distances/similarities tend to be large — and that's exactly where geodesic distance becomes useful.

Geodesic Distance

Geodesic distance, put simply, is the shortest distance between two points. Since a manifold need not be flat, this distance is not necessarily the straight-line (Euclidean) distance between the two points. The classic example is traveling from the South Pole to the North Pole of the Earth: we can't walk in a straight line through the Earth's core, so we can only travel along the Earth's surface — say, first to the equator, then on to the North Pole — tracing out a curved path (a semicircle) instead.

Within a local range (where distances are relatively small), the Earth still looks flat, so Euclidean distance remains usable. But once we consider large distances like "South Pole–North Pole" or "South Pole–equator," it's no longer accurate. This closely parallels the semantic similarity scenario described above — a known distance measure (such as Euclidean distance) is fairly accurate at short range but inaccurate at long range, fundamentally because the manifold is not flat.

Fortunately, having only local distances is enough. We can turn this into a graph problem, and use a "shortest path" algorithm to estimate an approximate geodesic distance. Specifically, we can use an existing distance function to compute the distance from each point to all the rest, then keep only the $k$ nearest points (or alternatively truncate by a threshold, depending on the situation), connecting an edge between them labeled with their distance. In this way, all the points and edges together form a weighted graph (which we call a "$k$-nearest-neighbor graph"). We can then use Dijkstra's algorithm to find the shortest path between any two points in the graph, and compute its length — this serves as the approximate geodesic distance.

In short, under the assumption that "distances between nearby points are fairly accurate, while distances between far-apart points are not," we can use a $k$-nearest-neighbor graph combined with shortest-path search to estimate the geodesic distance between distant points as a substitute measure. Because geodesic distance takes into account the manifold structure of the vector space, it can potentially achieve better results (see Table 8 of the original paper).

Summary

This post shared the concept of "geodesic distance," pointing out that the similarity measures we normally train may only be reliable locally, and that switching to geodesic distance at larger distances may help with certain semantic similarity problems.