Abstract
Learning useful representations is a key ingredient to the success of modernmachine learning. Currently, representation learning mostly relies on embeddingdata into Euclidean space. However, recent work has shown that data in somedomains is better modeled by non-euclidean metric spaces, and inappropriategeometry can result in inferior performance. In this paper, we aim to eliminatethe inductive bias imposed by the embedding space geometry. Namely, we proposeto map data into more general non-vector metric spaces: a weighted graph with ashortest path distance. By design, such graphs can model arbitrary geometrywith a proper configuration of edges and weights. Our main contribution isPRODIGE: a method that learns a weighted graph representation of dataend-to-end by gradient descent. Greater generality and fewer model assumptionsmake PRODIGE more powerful than existing embedding-based approaches. We confirmthe superiority of our method via extensive experiments on a wide range oftasks, including classification, compression, and collaborative filtering.