Timezone: »
A wide variety of machine learning tasks such as knowledge base completion, ontology alignment, and multi-label classification can benefit from incorporating into learning differentiable representations of graphs or taxonomies. While vectors in Euclidean space can theoretically represent any graph, much recent work shows that alternatives such as complex, hyperbolic, order, or box embeddings have geometric properties better suited to modeling real-world graphs. Experimentally these gains are seen only in lower dimensions, however, with performance benefits diminishing in higher dimensions. In this work, we introduce a novel variant of box embeddings that uses a learned smoothing parameter to achieve better representational capacity than vector models in low dimensions, while also avoiding performance saturation common to other geometric models in high dimensions. Further, we present theoretical results that prove box embeddings can represent any DAG. We perform rigorous empirical evaluations of vector, hyperbolic, and region-based geometric representations on several families of synthetic and real-world directed graphs. Analysis of these results exposes correlations between different families of graphs, graph characteristics, model size, and embedding geometry, providing useful insights into the inductive biases of various differentiable graph representations.
Author Information
Michael Boratko (UMass Amherst)
Dongxu Zhang (University of Massachusetts Amherst)
Nicholas Monath (Google)
Luke Vilnis (University of Massachusetts, Amherst)
Kenneth L Clarkson (IBM Almaden)
Andrew McCallum (UMass Amherst)
More from the Same Authors
-
2021 : CSFCube - A Test Collection of Computer Science Research Articles for Faceted Query by Example »
Sheshera Mysore · Tim O'Gorman · Andrew McCallum · Hamed Zamani -
2022 Poster: Modeling Transitivity and Cyclicity in Directed Graphs via Binary Code Box Embeddings »
Dongxu Zhang · Michael Boratko · Cameron Musco · Andrew McCallum -
2022 Poster: Structured Energy Network As a Loss »
Jay Yoon Lee · Dhruvesh Patel · Purujit Goyal · Wenlong Zhao · Zhiyang Xu · Andrew McCallum -
2020 Poster: Improving Local Identifiability in Probabilistic Box Embeddings »
Shib Dasgupta · Michael Boratko · Dongxu Zhang · Luke Vilnis · Xiang Li · Andrew McCallum -
2019 : Coffee Break & Poster Session 2 »
Juho Lee · Yoonho Lee · Yee Whye Teh · Raymond A. Yeh · Yuan-Ting Hu · Alex Schwing · Sara Ahmadian · Alessandro Epasto · Marina Knittel · Ravi Kumar · Mohammad Mahdian · Christian Bueno · Aditya Sanghi · Pradeep Kumar Jayaraman · Ignacio Arroyo-Fernández · Andrew Hryniowski · Vinayak Mathur · Sanjay Singh · Shahrzad Haddadan · Vasco Portilheiro · Luna Zhang · Mert Yuksekgonul · Jhosimar Arias Figueroa · Deepak Maurya · Balaraman Ravindran · Frank NIELSEN · Philip Pham · Justin Payan · Andrew McCallum · Jinesh Mehta · Ke SUN -
2019 : Opening Remarks »
Manzil Zaheer · Nicholas Monath · Ari Kobren · Junier Oliva · Barnabas Poczos · Ruslan Salakhutdinov · Andrew McCallum -
2019 Workshop: Sets and Partitions »
Nicholas Monath · Manzil Zaheer · Andrew McCallum · Ari Kobren · Junier Oliva · Barnabas Poczos · Ruslan Salakhutdinov -
2019 : Andrew McCallum: Learning DAGs and Trees with Box Embeddings and Hyperbolic Embeddings »
Andrew McCallum -
2019 Poster: Search-Guided, Lightly-Supervised Training of Structured Prediction Energy Networks »
Amirmohammad Rooshenas · Dongxu Zhang · Gopal Sharma · Andrew McCallum -
2018 Poster: Compact Representation of Uncertainty in Clustering »
Craig Greenberg · Nicholas Monath · Ari Kobren · Patrick Flaherty · Andrew McGregor · Andrew McCallum -
2017 : Invited Talk: "Light Supervision of Structured Prediction Energy Networks" »
Andrew McCallum -
2017 : Poster Session - Session 2 »
Ambrish Rawat · Armand Joulin · Peter A Jansen · Jay Yoon Lee · Muhao Chen · Frank F. Xu · Patrick Verga · Brendan Juba · Anca Dumitrache · Sharmistha Jat · Robert Logan · Dhanya Sridhar · Fan Yang · Rajarshi Das · Pouya Pezeshkpour · Nicholas Monath -
2017 Poster: Active Bias: Training More Accurate Neural Networks by Emphasizing High Variance Samples »
Haw-Shiuan Chang · Erik Learned-Miller · Andrew McCallum -
2014 Workshop: Representation and Learning Methods for Complex Outputs »
Richard Zemel · Dale Schuurmans · Kilian Q Weinberger · Yuhong Guo · Jia Deng · Francesco Dinuzzo · Hal Daumé III · Honglak Lee · Noah A Smith · Richard Sutton · Jiaqian YU · Vitaly Kuznetsov · Luke Vilnis · Hanchen Xiong · Calvin Murdock · Thomas Unterthiner · Jean-Francis Roy · Martin Renqiang Min · Hichem SAHBI · Fabio Massimo Zanzotto -
2014 Workshop: 4th Workshop on Automated Knowledge Base Construction (AKBC) »
Sameer Singh · Fabian M Suchanek · Sebastian Riedel · Partha Pratim Talukdar · Kevin Murphy · Christopher Ré · William Cohen · Tom Mitchell · Andrew McCallum · Jason E Weston · Ramanathan Guha · Boyan Onyshkevych · Hoifung Poon · Oren Etzioni · Ari Kobren · Arvind Neelakantan · Peter Clark -
2012 Poster: MAP Inference in Chains using Column Generation »
David Belanger · Alexandre T Passos · Sebastian Riedel · Andrew McCallum -
2011 Workshop: Big Learning: Algorithms, Systems, and Tools for Learning at Scale »
Joseph E Gonzalez · Sameer Singh · Graham Taylor · James Bergstra · Alice Zheng · Misha Bilenko · Yucheng Low · Yoshua Bengio · Michael Franklin · Carlos Guestrin · Andrew McCallum · Alexander Smola · Michael Jordan · Sugato Basu -
2011 Poster: Query-Aware MCMC »
Michael Wick · Andrew McCallum -
2009 Poster: FACTORIE: Probabilistic Programming via Imperatively Defined Factor Graphs »
Andrew McCallum · Karl Schultz · Sameer Singh -
2009 Poster: Training Factor Graphs with Reinforcement Learning for Efficient MAP Inference »
Michael Wick · Khashayar Rohanimanesh · Sameer Singh · Andrew McCallum -
2009 Spotlight: Training Factor Graphs with Reinforcement Learning for Efficient MAP Inference »
Michael Wick · Khashayar Rohanimanesh · Sameer Singh · Andrew McCallum -
2009 Poster: Rethinking LDA: Why Priors Matter »
Hanna Wallach · David Mimno · Andrew McCallum -
2009 Spotlight: Rethinking LDA: Why Priors Matter »
Hanna Wallach · David Mimno · Andrew McCallum