Faculty Recruiting Support CICS

Graph Representation Learning with Box Embeddings

27 Feb
Monday, 02/27/2023 10:00am to 12:00pm
Zoom
PhD Thesis Defense
Speaker: Dongxu Zhang

Abstract: Graphs are ubiquitous data structures, present in many machine-learning tasks, such as link prediction, node classification, ontology alignment, etc. As gradient descent drives the training of most modern machine learning architectures, the ability to encode graph-structured data using a differentiable representation is essential to make use of this data. Most approaches encode graph structure in Euclidean space, however, it is non-trivial to model directed edges. The naive solution is to represent each node using a separate "source" and "target" vector, however, this can decouple the representation, making it harder for the model to capture information within longer paths in the graph.

In this dissertation, we proposed to model graphs by representing each node as a box (a Cartesian product of intervals) where directed edges are captured by the relative containment of one box in another. Theoretical proof shows that our proposed box embeddings have the expressiveness to represent any directed acyclic graphs. We also perform rigorous empirical evaluations of vector, hyperbolic, and region-based geometric representations on several families of synthetic and real-world directed graphs. Extensive experimental results suggest that the box containment can allow for transitive relationships to be modeled easily. We further proposed t-Box, a variant of box embeddings that learns the temperature together during training. t-Box 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.

Though promising, modeling directed graphs that both contain cycles and some element of transitivity, two properties common in real-world settings, is challenging. Box embeddings, which can be thought of as representing the graph as an intersection over some learned super-graphs, have a natural inductive bias toward modeling transitivity, but (as we prove) cannot model cycles. To this end, we propose binary code box embeddings, where a learned binary code selects a subset of graphs for intersection. We explore several variants, including global binary codes (amounting to a union over intersections) and per-vertex binary codes (allowing greater flexibility) as well as methods of regularization. Theoretical and empirical results show that the proposed models not only preserve a useful inductive bias of transitivity but also have the sufficient representational capacity to model arbitrary graphs, including graphs with cycles.

Lastly, we discuss the use case where box embeddings are not free parameters but produced by functions. In particular, we explore whether neural networks can map node features into the box space. This is critical in lots of real-world scenarios. On the one hand, graphs are sparse and the majority of vertices only have few connections or are completely isolated. On the other hand, there may exist rich node features such as attributes and descriptions, that could be useful for prediction tasks.

Advisor: Andrew McCallum

Join via Zoom