Deep Models of Interactions Across Sets

By Jason S. Hartford, Devon R. Graham, Kevin Leyton-Brown, Siamak Ravanbakhsh. 2018

174 citations recorded by the source corpus.

We use deep learning to model interactions across two or more sets of objects, such as user-movie ratings, protein-drug bindings, or ternary user-item-tag interactions. The canonical representation of such interactions is a matrix (or a higher-dimensional tensor) with an exchangeability property: the encoding's meaning is not changed by permuting rows or columns. We argue that models should hence be Permutation Equivariant (PE): constrained to make the same predictions across such permutations. We present a parameter-sharing scheme and prove that it could not be made any more expressive without violating PE. This scheme yields three benefits. First, we demonstrate state-of-the-art performance on multiple matrix completion benchmarks. Second, our models require a number of parameters independent of the numbers of objects, and thus scale well to large datasets. Third, models can be queried about new objects that were not available at training time, but for which interactions have since been observed. In experiments, our models achieved surprisingly good generalization performance on this matrix extrapolation task, both within domains (e.g., new users and new movies drawn from the same distribution used for training) and even across domains (e.g., predicting music ratings after training on movies).

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Relational inductive biases, deep learning, and graph networks (2018, background): “For example, each object in a set may be aﬀected by pairwise interactions with the other objects in the set (Hartford et al., 2018).”
Gauge Equivariant Convolutional Networks and the Icosahedral CNN (2019, neutral): “Equivariant Deep Learning Equivariant networks have been proposed for permutation-equivariant analysis and prediction of sets (Zaheer et al., 2017; Hartford et al., 2018), graphs (Kondor et al., 2018b; Hy et al., 2018; Maron et al., 2019), translations and rotations of the plane and 3D space…”
Invariant and Equivariant Graph Networks (2018, methodology): “Although the layers in Hartford et al. (2018) satisfy the order invariance and equivariance, they do not exhaust all possible such layers in case some node sets coincide.”
Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputs (2018, background): “Hartford et al. (2018) proposes a matrix completion model invariant to (possibly separate) permutations of the rows or columns.”
Universal approximations of permutation invariant/equivariant functions by deep neural networks (2019, unknown): “(2017), Hartford et al. (2018), Risi Kondor (2018), Maron et al.”
On Learning Sets of Symmetric Elements (2020, background): “Moreover, other recent works can also be viewed as special cases of our approach (Hartford et al., 2018; Aittala & Durand, 2018; Sridhar et al., 2019).”
On the Universality of Invariant Networks (2019, background): “However, universality is not known for tabular and multi-set networks (Hartford et al., 2018), graph”
Conditional Structure Generation through Graph Variational Generative Adversarial Nets (2019, background): “Moreover, none of the existing methods really solve the fundamental challenge of graph permutation invariance [26, 42, 15, 48, 30] during their translation between graph structures and representations, due to the facts that their embedding spaces or generated graphs are essentially not permutation-i”
Probabilistic Symmetries and Invariant Neural Networks (2020, background): “…out the details of the program outlined in Section 5.1 to various exchangeable random structures, and relates the resulting representations to some recent (Zaheer et al., 2017; Gilmer et al., 2017; Hartford et al., 2018) and less recent (Shawe-Taylor, 1989) work in the neural networks literature.”
Universal Invariant and Equivariant Graph Neural Networks (2019, background): “This generalizes several previous constructions, for instance for sets (Zaheer et al., 2017; Hartford et al., 2018) and points clouds (Qi et al.”
Relational Pooling for Graph Representations (2019, background): “Another line of work derives bases for permutation-invariant functions of graphs and propose learning the coefficients of basis elements from data (Maron et al., 2018; Hartford et al., 2018).”