Source-linked AI summary
Deep Models of Interactions Across Sets
Jason Hartford, Devon R Graham, Kevin Leyton-Brown, Siamak Ravanbakhsh
TL;DR
The paper addresses how to model interactions between multiple sets when their matrix or tensor representation is unchanged by row and column permutations. It introduces and theoretically characterizes permutation-equivariant parameter sharing, then evaluates deep models built with it on matrix-completion and inductive settings. The models achieve state-of-the-art or competitive benchmark performance and support inductive completion for rating matrices that can differ from those observed during training.
Problem
Matrix and tensor interactions are exchangeable, but existing parametric factorization and completion methods associate parameters with rows and columns and therefore are not Permutation Equivariant.
Method
The paper uses tied parameters in deep exchangeable matrix and tensor layers, and proves the resulting layers are permutation equivariant with maximal expressiveness under that constraint.
Results
The models achieve state-of-the-art or competitive performance on widely studied matrix-completion benchmarks and generalize inductively to rating matrices differing from those observed during training.
Takeaways & Limitations
The approach supports inductive completion without side information, including settings involving previously unseen objects and differing object distributions.
Takeaways & Limitations
The models take the whole data matrix as input, creating fixed-GPU-memory challenges as datasets grow and making predictions from subsets typically different and worse.
Abstract
from arXiv · showhide
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).
1. Introduction
The paper frames matrix completion over exchangeable interactions as requiring models whose predictions respect row and column permutations. It introduces parameter sharing to enforce this Permutation Equivariance efficiently and extends the approach to related matrix and tensor settings.
- Problem: Exchangeable matrices represent the same matrix-completion problem after any row-wise or column-wise permutation.Matrix completion predicts unobserved entries from patterns in the observed matrix.
- Permutation Equivariance: Permutation Equivariance requires a learning algorithm to give the same answer across all exchangeable inputs.The paper presents PE as an inductive bias for exchangeable domains.
- Parameter sharing: A simple parameter-sharing scheme enforces PE without enumerating all M! × N! row and column permutations.The authors compare their approach with explicitly augmenting inputs by every row and column permutation, which is computationally infeasible except for the smallest matrices.
- Extensions: The approach applies to arbitrary matrices and higher-dimensional arrays, while reducing to graph convolution for jointly exchangeable 2D arrays.Joint exchangeability constrains row and column permutations to be identical.
- Connections: The model generalizes earlier parameter-sharing work and can be viewed as a generalization of deep sets to exchangeable matrices.The paper also connects the approach to prior work on behavioral game theory.
2. Exchangeable Matrix Layer
An exchangeable matrix layer enforces permutation equivariance by tying weights according to whether inputs share an output’s row, column, position, or neither. This yields a parameter-efficient architecture that extends to channels, features, jointly exchangeable matrices, and sparse observations.
- The same four-parameter sharing pattern repeats across all output units, making the layer’s effective degrees of freedom independent of matrix dimensions.
- Permutation equivariance requires permuting the input rows and columns to produce the same permutations of the output.
- Each output element connects through shared parameters to its counterpart, other inputs in the same row, inputs in the same column, and all remaining inputs, plus a bias.
- Theorem 2.1 shows that, for strictly monotonic activations, this equivariance holds exactly when the fully connected layer uses the prescribed tied-weight structure.
- The construction preserves equivariance under commutative pooling and layer stacking, applies to jointly exchangeable matrices with w2 = w3, and extends to sparse observed entries.
- Multiple input and output channels use five parameters per channel pair, including a channel-independent bias, while row and column features can be broadcast as additional channels.
3. Matrix Factorization and Completion
The paper frames recommendation as matrix completion and introduces exchangeable deep models for transductive and inductive prediction. Its factorized autoencoder learns row and column factors, while subsampling procedures address the memory costs of processing large sparse matrices.
- Problem: Matrix completion predicts missing user–item ratings from a sparse observed matrix, with transductive settings sharing rows or columns between training and testing.Inductive matrix extrapolation instead uses completely disjoint training and test row and column indices.
- Self-supervised model: The self-supervised model masks observed entries and trains exchangeable matrix layers to reconstruct the held-out values.It partitions observed entries into input and prediction sets, then predicts the latter from the former.
- Factorized model: The factorized exchangeable autoencoder encodes a sparse matrix into row and column factors, then decodes those factors to reconstruct the input.Its objective minimizes reconstruction error, and the architecture extends to tensor factorization.
- Inductive prediction: Once trained, the factorized autoencoder can factorize unseen matrices without performing additional optimization.This distinguishes it from classical matrix factorization procedures that learn embeddings through optimization for the observed entities.
- Subsampling: The models process the whole data matrix and may predict worse from subsets, creating GPU-memory challenges that motivate the two subsampling procedures.This limitation arises because predictions aggregate shared representations across data points.
- Subsampling: Uniform subsampling is unbiased and cheap but can sparsify relationships, whereas conditional sampling preserves all interactions among selected rows and columns at greater cost.Conditional sampling derives columns from row-marginal and column-conditional distributions, while test-time coverage requires repeated sampling of relevant indices.
4. Empirical Results
The empirical evaluation finds competitive or state-of-the-art matrix-completion performance, while the exchangeable models also generalize to new users, movies, and entirely new datasets. Performance remains strong in inductive settings but weakens on the larger MovieLens-1M dataset under memory-constrained subsampling.
- Evaluation scope: The released experiments evaluate standard transductive completion, inductive generalization to new users and movies, cross-dataset extrapolation, and alternative sampling procedures.The experiments use datasets including MovieLens, Netflix, Flixster, Douban, and Yahoo Music.
- Transductive setting: The model achieves competitive, state-of-the-art performance on the reported matrix-completion benchmarks with a constant number of parameters.The competing methods’ parameter counts grow with the numbers of users and/or items.
- Transductive setting: On MovieLens-1M, both models perform comparatively weaker than on MovieLens-100K and extrapolation experiments, likely because GPU memory limits batch size and model depth.The authors report that larger batches and deeper models each improve performance, but both cannot be used together on the larger dataset.
- Inductive setting: The model significantly outperforms K-nearest-neighbour baselines when trained on MovieLens-100K and tested on new MovieLens-1M ratings, across 5%–95% observed data.Performance degrades gracefully as the amount of observed test data decreases.
- Cross-dataset extrapolation: When trained on MovieLens-100K and tested without retraining on Flixster, Douban, and Yahoo Music, the model achieves competitive results despite differing rating scales.Inputs were binned to a 1–5 range and outputs were linearly rescaled where applicable; the input was therefore coarser-grained than for comparison models.
- Cross-dataset extrapolation: The model improves over previous state-of-the-art results on Flixster and Yahoo Music, matches GC-MC closely on Douban, and gains most on sparse-rating datasets.The comparison uses models trained separately for each target dataset.
- Sampling analysis: Subsampling large input matrices reduces performance relative to full-batch processing, although conditional sampling recovers some of the loss.The authors link this issue partly to the weaker MovieLens-1M results.
5. Extention to Tensors
The tensor extension defines layers equivariant to independent permutations along each tensor dimension. Its parameter tying is exactly sufficient for this guarantee: fewer ties would violate equivariance.
- Tensor exchangeability: The tensor layer applies a vectorized linear transformation and element-wise nonlinearity to D-dimensional arrays while respecting dimension-wise permutations.The input has shape N1×...×ND, and equivariance concerns permutations in S(N1)×...×S(ND).
- Guarantee: Theorem 5.1 states that this parameter-sharing construction is exchangeable if and only if its weights follow the prescribed equality-pattern structure.The result applies with any strictly monotonic element-wise nonlinearity.
- Parameter tying: Each output element depends on input elements grouped by the set of tensor indices on which the input and output positions agree.Thus the parameter matrix is determined by equality patterns between index tuples.
- Guarantee: The resulting layer is equivariant to permutations along tensor axes, but not to arbitrary permutations of the flattened tensor elements.Illegal permutations can disrupt the required movement of whole subtensors and therefore violate equivariance for some input.
- Special cases: For matrices, the construction reduces to the earlier exchangeable matrix layer; for jointly exchangeable matrices, it also specializes to graph convolution.The tensor formulation therefore includes both matrix and graph-related cases.
- Optimality: The tying scheme is maximally expressive under the equivariance constraint: adding parameters by removing ties would break the guarantee.The theorem establishes optimality rather than merely sufficiency.
Conclusion
The paper develops permutation-equivariant deep models for predicting relationships in exchangeable matrices and tensors. It reports competitive benchmark performance, parameter counts independent of matrix size, and strong extrapolation and transfer results, including across domains.
- Problem: The paper addresses prediction of relationships between elements of two or more distinct sets represented as exchangeable matrices or tensors.This includes matrix-completion settings with missing interaction values.
- Method: The proposed weight-tying scheme produces permutation-equivariant models, and the paper proves that greater expressiveness would violate this guarantee.The conclusion presents this as the central theoretical result.
- Results: The models achieve state-of-the-art or competitive performance on widely studied matrix-completion benchmarks.The conclusion reports this across the benchmark setting rather than for one dataset or metric.
- Scalability: The number of model parameters is independent of the size of the matrix being completed.The conclusion contrasts this property with other strong-performing approaches.
- Extrapolation and transfer: The models obtain competitive results when completing matrices containing objects unobserved during training and show strong transfer from MovieLens to other datasets.The reported transfer datasets include settings with different user populations and object distributions, including different object kinds.
B.1. Proof of Proposition 5.2
The proof shows that a permutation of tensor entries preserves the required structure only when each dimension is transformed independently. An inductive argument establishes membership in the product of the dimension-wise permutation groups.
- Inductive setup: The proof assumes that each dimension’s mapped index is independent of the values in the remaining dimensions.This independence allows the global permutation to be decomposed into separate dimension-wise actions.
- Base case: Under that assumption, the two-dimensional base case factors the global permutation into one permutation for each tensor dimension.The factorization places the permutation in S(N1)×S(N2).
- Inductive step: Induction on the number of dimensions extends the factorization to g(N)(n)=g(N1)(n1)×...×g(ND)(nD).Therefore the global permutation belongs to S(N1)×...×S(ND).
- Algebraic argument: The proof uses the behavior of permutation matrices and the tied weight structure to complete the characterization.The intermediate algebra identifies how entries of the parameter matrix depend on index agreement.
B.3. Proof of Theorem 5.1
The proof establishes both directions of Theorem 5.1: dimension-wise permutations preserve the layer, while any other permutation fails for a suitable input. Thus the layer is equivariant exactly to the intended product group.
- Necessity: The reverse-direction argument constructs a permutation that swaps selected index pairs while preserving their equality pattern, then shows the required weight relation fails.With an appropriate input, the resulting layer is not an exchangeable tensor layer.
- Equivariance: For a permutation in S(N1)×...×S(ND), independent actions on tensor dimensions imply G(N)W vec(X)=W G(N) vec(X).Applying the element-wise nonlinearity preserves the resulting equivariance.
- Non-equivariance: For a permutation outside the product group, the products G(N)W and W G(N) differ at some matrix entry.The proof relies on the propositions identifying an inconsistent movement of subtensors.
- Counterexample: Choosing an input vector with a single 1 at the corresponding position yields G(N)W vec(X) ≠ W G(N) vec(X).The construction provides a concrete witness input for failure of equivariance.
B.4. Proof of Theorem 2.1
Theorem 2.1 follows as a special case of Theorem 5.1 when D = 2, after reparameterizing matrix W into the form of (3).
- A simple reparameterization writes matrix W from (6) in the form of (3).
- Theorem 2.1 is the special case of Theorem 5.1 with D = 2.
- The proof of Theorem 2.1 follows from Theorem 5.1.
C. Details of Architecture and Training
The paper describes two exchangeable neural architectures: a nine-layer self-supervised feed-forward network and a factorized exchangeable autoencoder with pooled user and movie representations.
- Self-Supervised Model: The self-supervised model uses 9 exchangeable matrix layers with leaky ReLU activations and 256 channels per hidden layer.
- Self-Supervised Model: Channel-wise dropout with probability 0.5 is applied after the first to seventh layers and is reported as crucial for good performance.
- Factorized Exchangeable Autoencoder Model: The factorized autoencoder encoder uses three exchangeable matrix layers, with 220 channels in each of the first two layers and 100 output features per entry.
- Factorized Exchangeable Autoencoder Model: Mean pooling along both input dimensions encodes each user and movie as a length 100 real-valued latent vector.
- Factorized Exchangeable Autoencoder Model: The autoencoder decoder uses five similar exchangeable matrix layers.