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.
In 2013, “Translating Embeddings for Modeling Multi-relational Data" (TransE) was published. TransE provided an effective algorithm for embedding multi-relational data into . However, the embedding of the data depends on the metric of . 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.
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.
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.
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 . Among the strengths of TransE is its ability to predict relationships between entities (link prediction). This is done by embedding data points, say and , with a relationship between them, say into such that
as members of . This results in similar elements being clustered together in the embedding. The upshot of this is that link prediction for a subject data point reduces to looking the clusters with which the points surrounding have relationships.
Now consider once again
In particular, what does mean in the context of ? The usual metric on is the Euclidean metric
but we can also define other metrics on such as the metrics induced by norms
as well as the maximum metric
Note that when we get the Euclidean metric.
The TransE paper proposed and 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.
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 , the usual topology is created by subsets of the form
ie. “open balls" of radius . This approach is commonly referred to as point-set topology.
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 TransE paper used “embedding” to describe the placing of data entities, say , , as points in . The problem we face now is the feasibility of taking one “embedding” in into another space . In general, we obtain the following definition:
Definition. An injection between metric spaces is called an embedding.
If our dataset of interest is a finite set of points in , then the question of finding an embedding into becomes trivial since there is no condition on , .
Example. For example, if are our data entities and a permutation, then a simple embedding would be
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 is an isometry or isometric if
for all .
Corollary. It is immediate that isometries must be injective since otherwise we could send distinct points in to the same point in .
But not all isometries are surjective.
Example. Let on with metric . Now is trivially isometric but not surjective since 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 is a global isometry, then so is .
where , .
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 , are there isometries to ?"
Fortunately, there are some positive results. The TransE paper mentions and as potential metrics. We begin with the results concerning them.
- There is an isometry to for any . In particular, there is an isometry
- There is an isometry for .
- Incidentally, isometrically for any .
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 , the distortion of is the smallest such that
for every and where .
Essentially, this gives a bound on how much by which the embedding is scaled compared to the preimage. It is immediate that is an isometry when
This provides a framework to consider the significance of the embedding’s failure. Indeed,
- (Bourgain) A general metric embeds into with distortion where is the number of points
- (Matousek) In general, any metric space on points embeds into with distortion
- There is an embedding into that embeds with distortion .
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 since embeddings from into any other 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.
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 have a discrete topology which means not much can be discerned.
Instead, we form neighbourhoods of equal diameter around each point and connect points with overlapping neighbourhoods. As increases, the number of connected components decreases. This provides us with sufficient structure to investigate the shape of the data.
As the 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 . Ideally, the number with the longest interval will be the interval in which the clusters retains sufficient separation. The maximum of in the interval of interest should provide a sufficient bound for the acceptable amount of distortion for the embedding.
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 and then decide whether it's possible to embed into another space with metric while maintaining separated clusters 2 Use TransE to exhibit an embedding with metric 3 Look up the distortion of embedding from into 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 is not within the acceptable amount of distortion, then the new embedding into 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 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 is the partition of with metric returned by a clustering algorithm, such a clustering algorithm would have:
Scale-Invariance: where .
Richness: the image of is all the possible partitions of .
Consistency: if is another metric for and
for any in some cluster in , we have ,
for any in distinct clusters in , we have ,
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.
- A. Bordes, N. Usunier, A. Garcia-Duran, J. Weston, and O. Yakhnenko, “Translating Embeddings for Modeling Multi-relational Data,” in Advances in Neural Information Processing Systems 26. Curran Associates, Inc., 2013, pp. 2787–2795.
- Much thanks to the peer who pointed out the distinction during the presentation
- J. Kleinberg. An Impossibility Theorem for Clustering. Advances in Neural Information Processing Systems (NIPS) 15, 2002.
- Curry, J.: Sheaves, Cosheaves and Applications. arXiv:1303.3255 [math.AT]
- 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
references (done) and figures (done) and hyperlinks (done)