Course:CPSC522/Topology and Embedding Multi-relational Data

Topological Data Analysis and Embedding Multi-relational Data

We discuss the application of topological data analysis in the context of the embedding multi-relational data and the TransE algorithm.

Principal Author: Carl Kwan

Figures are my own creation unless otherwise noted.

Abstract

In 2013, “Translating Embeddings for Modeling Multi-relational Data" (TransE) was published. TransE provided an effective algorithm for embedding multi-relational data into $\mathbb {R} ^{n}$. However, the embedding of the data depends on the metric of $\mathbb {R} ^{n}$. It would not be unusual to wonder whether there are benefits to using other metrics.

Topological data analysis is a (relatively) new approach to data analysis that levies the tools of topology for the purpose of examining data. Among the benefits of topology is the ability to discern the “shape" of the space independent of metric. This makes topology a potentially powerful tool in the context of TransE.

Builds On

The nature of topological data analysis builds upon algebraic topology. While this article remains informal in its approach, it would be prudent to consider some prerequisites (the first item is recommended viewing - the rest are for the interested):

• A short, informal but excellent video introduction to persistent homologies: Wright
• A longer video of a talk on topological data analysis: Carlsson
• An introductory paper on topological data analysis: Carlsson
• A standard (and free) introduction to algebraic topology: Hatcher
• A standard introduction to point set topology: Munkres
• Some excellent books on algebra and linear algebra: Artin, Lang, Jacobson

Finally, as this article applies topology to TransE, being familiar with TransE would be a good idea. The paper can be found here.

Related Pages

While this article focuses on applications to TransE, TDA can be applied to any field or problems involving large datasets. One possible application within this wiki would be the application to restaurant data.

TransE

The paper “Translating Embeddings for Modeling Multi-relational Data" was published in 2013. Since then, numerous similar algorithms have been developed to embed data into $\mathbb {R} ^{n}$. Among the strengths of TransE is its ability to predict relationships between entities (link prediction). This is done by embedding data points, say $h$ and $t$, with a relationship between them, say $\ell$ into $\mathbb {R} ^{n}$ such that

$h+\ell \approx t$

as members of $\mathbb {R} ^{n}$. This results in similar elements being clustered together in the embedding. The upshot of this is that link prediction for a subject data point $p$ reduces to looking the clusters with which the points surrounding $p$ have relationships.

TransE embeds data as points in $\mathbb {R} ^{n}$ according to their relationship. For example, if $h$ is "Saving Private Ryan" and $t$ is "Steven Spielberg", then $\ell$ could be "directed by".

TransE embeddings often resemble clusters.

Now consider once again

$h+\ell \approx t.$

In particular, what does $\approx$ mean in the context of $\mathbb {R} ^{n}$? The usual metric on $\mathbb {R} ^{2}$ is the Euclidean metric

$d_{2}(x,y)={\sqrt {\sum _{i=1}^{n}|x_{i}-y_{i}|^{2}}}$

but we can also define other metrics on $\mathbb {R} ^{n}$ such as the metrics induced by $\ell ^{p}$ norms

$d_{p}(x,y)=\left(\sum _{i=1}^{n}|x_{i}-y_{i}|^{p}\right)^{1/p}$

as well as the maximum metric

$d_{\infty }(x,y)=\sup _{i}|x_{i}-y_{i}|.$

Note that when $p=2$ we get the Euclidean metric.

The unit circle under the metrics $d_{1}$ (green), $d_{2}$ (red), and $d_{\infty }$ (blue).

The TransE paper proposed $d_{1}$ and $d_{2}$ as choices when running the embedding algorithm. However, it is unknown how the choice of metric will affect link prediction. It is possible that using different metrics will result in better performance. Topology can look at properties of spaces independent of metrics.

The TransE Algorithm.

Topology

Informally speaking, topology looks at characteristics of spaces that are retained under continuous deformations. One way of doing this is by looking at collections of subsets of the space which we call a topology. For $\mathbb {R} ^{n}$, the usual topology is created by subsets of the form

$B_{r}(x)=\{y\in \mathbb {R} ^{n}\mid d(x,y)<r\},$

ie. “open balls" of radius $r>0$. This approach is commonly referred to as point-set topology.

An open ball in $\mathbb {R} ^{2}$ with radius $r$.

Another approach is to look at paths in the space and their compositions under continuous deformations. These paths under composition form algebraic structures - the simplest of which is called the Fundamental Group. This approach to topology is algebraic topology.

The paths on the right (purple and teal) can be deformed continuously into a point so they are equivalent. However, the paths on the left (blue, red, and green) are not the same as the purple and teal paths because they cannot be deformed into a point without making a discontinuous "jump" over the hole on the left.

Embeddings

The TransE paper used “embedding” to describe the placing of data entities, say $h$, $t$, as points in $(\mathbb {R} ^{n},d)$. The problem we face now is the feasibility of taking one “embedding” in $(\mathbb {R} ^{n},d)$ into another space $(\mathbb {R} ^{n},d^{\prime })$. In general, we obtain the following definition:

Definition. An injection $f:(X,d)\hookrightarrow (Y,d^{\prime })$ between metric spaces is called an embedding.

If our dataset of interest is a finite set of points in $(\mathbb {R} ^{n},d)$, then the question of finding an embedding into $(\mathbb {R} ^{n},d^{\prime })$ becomes trivial since there is no condition on $d$, $d^{\prime }$.

Example. For example, if $S\subset \mathbb {R} ^{n}$ are our data entities and $\sigma :S\to S$ a permutation, then a simple embedding would be

$\varphi (x)=\left\{{\begin{array}{cl}\sigma (x)&{\text{if }}x\in S\\x&{\text{otherwise}}\end{array}}\right.$

A desirable embedding is one that would preserve the clusters of data points so that we can continue to perform link prediction. The simplest condition we can impose on the embedding to satisfy our requirement is for it to be distence-preserving or, in other words, isometric.

Definition. A function $\varphi :(X,d)\to (Y,d^{\prime })$ is an isometry or isometric if

$d(x,y)=d^{\prime }(\varphi (x),\varphi (y))$

for all $x,y\in X$.

Corollary. It is immediate that isometries must be injective since otherwise we could send distinct points in $X$ to the same point in $Y$.

But not all isometries are surjective.

Example. Let $f(x)=x+1$ on $[0,\infty )$ with metric $d(x,y)=|x-y|$. Now $f$ is trivially isometric but not surjective since $0$ is not in its image.

But what about the isometries that are bijective?

Definition. A global or total isometry is a bijective isometry.

Corollary. If $\varphi :(X,d)\to (Y,d^{\prime })$ is a global isometry, then so is $\varphi ^{-1}:(Y,d^{\prime })\to (X,d)$.

proof. Observe

$d^{\prime }(a,b)=d^{\prime }(f(x),f(y))=d(x,y)=d(f^{-1}\circ f(x),f^{-1}\circ f(y))=d(f^{-1}(a),f^{-1}(b))$

where $f(x)=a$, $f(y)=b$.

An isometry preserves the distance between two points even though the definition of distance may be different depending on the metric space.

Despite the existence of global isometries, one would be hard-pressed to require even a non-bijective isometry. The natural question for TransE, then, is “Given a TransE embedding $(\mathbb {R} ^{n},d_{p})$, are there isometries to $(\mathbb {R} ^{n},d_{q})$?"

Fortunately, there are some positive results. The TransE paper mentions $d_{1}$ and $d_{2}$ as potential metrics. We begin with the results concerning them.

Theorem.

1. There is an isometry $(\mathbb {R} ^{n},d_{p})$ to $(\mathbb {R} ^{n},d_{q})$ for any $1\leq p\leq q\leq 2$. In particular, there is an isometry $(\mathbb {R} ^{n},d_{2})\hookrightarrow (\mathbb {R} ^{n},d_{1}).$
2. There is an isometry $(\mathbb {R} ^{n},d_{2})\hookrightarrow (\mathbb {R} ^{n},d_{p})$ for $2\leq p\leq \infty$.
3. Incidentally, $(\mathbb {R} ^{n},d_{p})\hookrightarrow (\mathbb {R} ^{n},d_{\infty })$ isometrically for any $p$.

At this point, the existence of a metric space from which we can isometrically embed into any other relevant metric space is sufficient to decide an optimal choice of metric for TransE. However, not all spaces embed isometrically the other way. Instead, the space will embed with some error which is called distortion.

Definition. Given an embedding $f:(X,d)\to (Y,d^{\prime })$, the distortion of $f$ is the smallest $D\geq 1$ such that

$r\cdot d(x,y)\leq d^{\prime }(f(x),f(y))\leq Dr\cdot d(x,y)$

for every $x,y\in X$ and where $r>0$.

Distortion means that distance is not preserved under an embedding between metric spaces.

Essentially, this gives a bound on how much by which the embedding is scaled compared to the preimage. It is immediate that $f$ is an isometry when $D=1$

This provides a framework to consider the significance of the embedding’s failure. Indeed,

Theorem.

1. (Bourgain) A general metric embeds into $(\mathbb {R} ^{n},d_{2})$ with distortion $O(\log m)$ where $m$ is the number of points
2. (Matousek) In general, any metric space on $n$ points embeds into $(\mathbb {R} ^{n},d_{p})$ with distortion $O\left({\frac {\log m}{p}}\right)$
3. There is an embedding into $(\mathbb {R} ^{n},d_{2})$ that embeds with distortion $\Omega (\log n)$.

If one does need to embed the TransE embedding into another metric space and working under the assumption one does not want to run TransE multiple times, then one should run TransE with $d_{2}$ since embeddings from $(\mathbb {R} ^{n},d_{2})$ into any other $\ell ^{p}$ space can be isometric.

Homology and Barcodes

This section is particularly informal and would benefit greatly from a viewing of Matthew Wright's introductory video

We have been working under the assumption that embeddings should be isometric. In particular, we have assumed that distortion should be avoided. However, distortion may not be as debilitating as initially perceived. Recall that a successful TransE appears akin to the distinct clusters of data points with relationships in between. In order to perform link prediction we require sufficient separation between the clusters. As long as there is sufficient separation between the clusters we can proceed as usual. To track this requirement, we look at the "topological features" or the underlying "shape" of the data.

Distortion is acceptable as long as the clusters remain "separated".

To investigate the shape of the embedding we look at its persistent homology. The formal definition of homology is beyond the scope of this article, but roughly, it is an algebraic picture of the topological features of the data of interest. By topological features we mean structures such as connected components, holes, etc. However, finite data points in $\mathbb {R} ^{n}$ have a discrete topology which means not much can be discerned.

Instead, we form neighbourhoods of equal diameter $r$ around each point and connect points with overlapping neighbourhoods. As $r$ increases, the number of connected components decreases. This provides us with sufficient structure to investigate the shape of the data.

As the radius of the neighbourhoods increase, connect points that have overlapping neighbourhoods.

As the $r$ increases, we can record the number of connected components in a graphical structure known as a barcode. In the barcode, the number of connected components are recorded as an interval with respect to $r$. Ideally, the number with the longest interval will be the interval in which the clusters retains sufficient separation. The maximum of $r$ in the interval of interest should provide a sufficient bound for the acceptable amount of distortion for the embedding.

The barcode for the example above. The initial short bars represents the values of $r$ for which no vertices were connected and there were 9 "connected" components. The longest bar in the center represents the values of $r$ for which there are 3 connected components, ie. 3 clusters of data points that are sufficiently separated. The right bar represents the values of $r$ so large that all vertices are connected at which point we may stop since there is only one connected component.

Given such a framework, one could imagine the following procedure.

1 # Given some data, suppose we wish to embed first into a space with a metric $d$ and then decide whether it's possible to embed into another space with metric $d^{\prime }$ while maintaining separated clusters
2 Use TransE to exhibit an embedding with metric $d$
3 Look up the distortion $D$ of embedding from $d$ into $d^{\prime }$
4 Compute the barcode for the connected components in the embedding
5 Use the barcode to find a bound for the acceptable distortion
6 If $D$ is not within the acceptable amount of distortion, then the new embedding into $d^{\prime }$ is acceptable
7 Otherwise, its not

Conclusion and Future Work

Among the initial objectives of this project was to consider the feasibility of topological applications to the context of TransE. Indeed, it not only appears feasible, there seems to be concrete applications for topology. Given certain conditions we see evidence towards a choice for $d_{2}$ as the metric to run with TransE due to the existence of isometric embeddings into other metric spaces. Moreover, if we relax the requirement for isometrics, we see the framework for deciding the extent of acceptable distortion. From this point, there are several directions to take.

The immediate and obvious sequel is an implementation of these algorithms and decision procedures along with experimental testing. Algorithms for topological data analysis already exist. In particular, there are software packages for computing persistence intervals. Unification in the form of a codified procedure involving a single run of TransE, then the computation of acceptable distortion via persistent homology and barcode, and, finally, the embedding of data into other metric spaces - with or without distortion - would be a pleasure to see in practice.

Secondly, the partitioned nature TransE’s output resembles the objective of clustering algorithms. Of special interest are the clustering algorithms between metric spaces. Ideally, if $\Pi (X,d)$ is the partition of $X$ with metric $d$ returned by a clustering algorithm, such a clustering algorithm would have:

• Scale-Invariance: $\Pi (X,d)=\Pi (X,r\cdot d)$ where $r>0$.

• Richness: the image of $\Pi$ is all the possible partitions of $X$.

• Consistency: if $d^{\prime }$ is another metric for $X$ and

  1. for any $x,y$ in some cluster in $\Pi (X,d)$, we have $d^{\prime }(x,y)\leq d(x,y)$,

  2. for any $x,y$ in distinct clusters in $\Pi (X,d)$, we have $d^{\prime }(x,y)\geq d(x,y)$,

  then $\Pi (X,d)=\Pi (X,d^{\prime })$.

Unfortunately, it is a theorem of Kleinberg’s that no such algorithm satisfy all three characteristics. The trade offs will have to be investigated further to consider what compromise can be made for the purposes of TransE.

Finally, recent work in topological data analysis has focused on the application of sheaf theory.. Sheaves, loosely stated, considers structures of algebraic spaces that can be restricted to open subsets. Their application to algebraic geometry, differential geometry, and, in particular, to algebraic topology has been well explored. It remains to be of great interest what ramifications sheaves will have on topological data analysis and TransE.

Annotated Bibliography

• Antoine Bordes, Nicolas Usunier, Alberto Garcia-Durán, Jason Weston, and Oksana Yakhnenko. 2013. Translating embeddings for modeling multi-relational data. In Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2 (NIPS'13), C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger (Eds.), Vol. 2. Curran Associates Inc., USA, 2787-2795.
• Carlsson, Gunner (2009) Topology and data. Bull Am Math Soc 46:255–308. DOI: https://doi.org/10.1090/S0273-0979-09-01249-X
• Hatcher, Allen, Algebraic Topology. Cambridge University Press, Cambridge, 2002. ISBN 0-521-79160-X and ISBN 0-521-79540-0
• Ittai Abraham, Yair Bartal, and Ofer Neimany. 2006. Advances in metric embedding theory. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing (STOC '06). ACM, New York, NY, USA, 271-286. DOI: https://doi.org/10.1145/1132516.1132557
• Lang, Serge, Algebra. Springer, Berlin, 2002. ISBN 978-1-4613-0041-0
• Matoušek, Jiří, Lecture Notes on Metric Embeddings. Published online, 2013.
• Munkres, James, Topology: A First Course. Prentice Hall, 1974. ISBN 9780139254956

To Add

references (done) and figures (done) and hyperlinks (done)