Year: 2019

Abstract:
The relational model is a ubiquitous representation of big-data, in part due to its extensive use in databases. However, recent progress in deep learning with relational data has been focused on (knowledge) graphs. In this paper we propose Equivariant Entity-Relationship Networks, a general class of parameter-sharing neural networks derived from the entity-relationship model. We prove that our proposed feed-forward layer is the most expressive linear layer under the given equivariance constraints, and subsumes recently introduced equivariant models for sets, exchangeable tensors, and graphs. The proposed feed-forward layer has linear complexity in the data and can be used for both inductive and transductive reasoning about relational databases, including database embedding, and the prediction of missing records. This provides a principled theoretical foundation for the application of deep learning to one of the most abundant forms of data.

heading: 1 INTRODUCTION
text: In the relational model of data, we have a set of entities, and one or more instances of each entity. These instances interact with each other through a set of fixed relations between entities. A set of attributes may be associated with each type of entity and relation.1 This simple idea is widely used to represent data, often in the form of a relational database, across a variety of domains, from shopping records, social networking data, and health records, to heterogeneous data from astronomical surveys.
Learning and inference on relational data has been the topic of research in machine learning over the past decades. The relational model is closely related to first order and predicate logic, where the existence of a relation between instances becomes a truth statement about a world. The same formalism is used in AI through a probabilistic approach to logic, where the field of statistical relational learning has fused the relational model with the framework of probabilistic graphical models. Examples of such models include plate models, probabilistic relational models, Markov logic networks, and relational dependency networks (Getoor & Taskar, 2007).
A closely related area that has enjoyed accelerated growth in recent years is relational and geometric deep learning, where the term “relational” is used to denote the inductive bias introduced by a graph structure. Although relational and graph-based terms are often used interchangeably in the machine learning community, they could refer to different data structures: graph-based models such as graph databases (Robinson et al., 2013) and knowledge graphs simply represent data as an attributed (hyper-)graph, while the relational model, common in databases, uses the entity-relation (ER) diagram (Chen, 1976) to constrain the relations of each instance (corresponding to a node), based on its entity-type; see Fig. 1(a).
Inspired by the success of equivariant deep learning, we use invariance and equivariance to encode the structure of relational data. This type of inductive bias informs a model’s behaviour under various transformations. Equivariant models have been successfully used for deep learning on data with a variety of structures, from translation equivariant images (LeCun et al., 1998), to geometric settings (Cohen et al., 2018a; 2019), to discrete objects such as sets (Zaheer et al., 2017), and graphs (Kondor et al., 2018b). By adopting this perspective, we present a maximally expressive feedforward layer that achieves equivariance w.r.t. exchangeabilities in relational data as it is expressed by the entity-relationship model. Our feedforward layer generalizes recently proposed layers for sets (Zaheer et al., 2017), exchangeable tensors (Hartford et al., 2018), and graphs (Maron et al., 2018).
1An alternative terminology refers to instances and entities as entities and entity types.

heading: 2 REPRESENTATIONS OF RELATIONAL DATA
text: We represent the relational model by a set of entities D = {1, ..., D} and a set of relations R ⊆ 2D , indicating how the entities interact with one another. For each entity d ∈ D we have a set {1, .., Nd} of instances of that entity. For each relation R ∈ R, where R = {d1, . . . , d|R|} is a set of entities, we observe data in the form of a set of tuples XR = {〈nd1 , . . . , nd|R| , x〉 | ndi ∈ [Ndi ], x ∈ RK}. That is, for each element of XR we associate the feature vector x with the relationship between the instances indexed by ndi for each entity di ∈ R. See Fig. 1 for a detailed, concrete example. Note that the singleton relation R = {di} can be used to incorporate individual entity attributes (such as professors’ evaluations in Fig. 1(a)).
In the most general case, we allow for both R, and any R ∈ R to be multisets (i.e., to contain duplicate entries). R is a multiset if we have multiple relations between the same set of entities. For example, we may have a SUPERVISES relation between STUDENTS and PROFESSORS, in addition to the WRITES REFERENCE relation. A particular relation R is a multiset if it contains multiple copies of the same entity. Such relations are ubiquitous in the real world, describing for example, the connection graph of a social network, the sale/purchase relationships between a group of companies, or, in our running example, the COURSE-COURSE relation capturing prerequisite information. For our derivations we make the simplifying assumption that each attribute x ∈ R is a scalar. Extension to x ∈ RK using multiple channels is trivial and discussed in Appendix F. Another common feature of relational data, the one-to-many relation, is addressed in Appendix E.

heading: 2.1 TUPLES, TABLES AND TENSORS
text: In relational databases the set of tuples XR is often represented using a table, with one row for each tuple; see Fig. 1(b). An equivalent representation for XR is using a “sparse” |R|-dimensional tensor XR ∈ RNd1×...×Nd|R| , where each dimension of this tensor corresponds to an entity d ∈ R, and the the length of that dimension is the number of instances Nd. In other words
〈nd1 , . . . , nd|R| , x〉 ∈ X R ⇔ XRnd1 ,...,nd|R| = x.
We work with this tensor representation of relational data. We use X = {XR | R ∈ R} to denote the set of all sparse tensors that define the relational data(base); see Fig. 1(c). For the following
discussions around exchangeability and equivariance, we assume that for all R, XR are fully observed, dense tensors. Subsequently, we will discard this assumption and attempt to make predictions for (any subset of) the missing records.
Note that relations R can be multisets. For simplicity, we handle this in the main text by considering equal elements as distinct through indexing (e.g., d(i) = d(j)), while leaving a formal definition of multisets for the supplementary material; see Appendix B.

heading: 3 EXCHANGEABILITIES OF ENTITY-RELATIONSHIP DATA
text: Recall that in the representation X, each entity d ∈ {1, ..., D} has a set of instances indexed by nd ∈ {1, .., Nd}. The ordering of {1, ..., Nd} is arbitrary, and we can shuffle these instances, affecting only the representation, and not the “content” of the relational data. However, in order to maintain consistency across data tables, we also have to shuffle all the tensors XR, where d ∈ R, using the same permutation applied to the tensor dimension corresponding to d. At a high level, this simple indifference to shuffling defines the exchangeabilities of relational data. A mathematical group formalizes this idea.
A mathematical group is a set equipped with a binary operation between its members, such that the set and the operation satisfy closure, associativity, invertability and existence of a unique identity element. SM refers to the symmetric group, the group of all permutations of M objects. A natural representation for a member of this group gM ∈ SM , is a permutation matrix G ∈ {0, 1}M×M . Here, the binary group operation is the same as the product of permutation matrices. In this notation, SNd is the group of all permutations of instances 1, . . . Nd of entity d ∈ {1, .., D}. To consider permutations to multiple dimensions of a data tensor we can use the direct product of groups. Given two groups G and H, the direct product G ×H is defined by
(g, h) ∈ G ×H⇔ g ∈ G, h ∈ H and (g, h) ◦ (g′, h′) = (g ◦ g′, h ◦ h′). (1)
That is, the underlying set is the Cartesian product of the underlying sets of G and H, and the group operation is the component-wise operation.
Observe that we can associate the group SN1 × . . .× SND with the D entities in a relational model, where each entity d has Nd instances. Intuitively, applying permutations from this group to the corresponding relational data should not affect the underlying contents, while applying permutations from outside this group should. To see this, consider the tensor representation of Fig. 1(c): permuting students, courses or professors shuffles rows or columns of X, but preserves its underlying content. However, arbitrary shuffling of the elements of this tensor could alter its content.
Our goal is to define a feed-forward layer that is “aware” of this structure. For this, we first need to formalize the action of SN1 × . . .× SND on the vectorized form of X.
Vectorization. For each tensor XR ∈ X, NR = ∏ d∈RNd refers to the total number of elements of tensor XR (note that for now we are assuming that the tensors are dense). We will refer to N = ∑ R∈RNR as the number of elements of X. Then vec(X
R) ∈ RNR refers to the vectorization of XR, obtained by successively stacking its elements along its dimensions, where the order of dimensions is given by d ∈ R. We use vec−1(·) to refer to the inverse operation of vec(·), so that vec−1(vec(X)) = X. With a slight abuse of notation, we use vec(X) ∈ RN to refer to [vec(XR1); . . . ; vec(XR|R|)], the vectorized form of the entire relational data. The weight matrix W that we define later creates a feed-forward layer σ(W vec(X)) applied to this vector.
Group Action. The action of g ∈ SN1 × . . .× SND on vec(X) ∈ RN , permutes the elements of vec(X). Our objective is to define this group action by mapping SN1 × . . . × SND to a group of permutations of all N = ∑ R∈R ∏ d∈RNd entries of the database – i.e., a homoomorphism into S
N . To this end we need to use two types of matrix product. Let G ∈ RN1×N2 and H ∈ RN3×N4 be two matrices. The direct sum G⊕H is an (N1 +N3)× (N2 +N4) block-diagonal matrix, and the
Kronecker product G⊗H is an (N1N3)× (N2N4) matrix:
G⊕H .= ( G 0 0 H ) , G⊗H .=  G1,1H . . . G1,N2H... . . . ... GN1,1H . . . GN1,N2H  . Note that in the special case that both G and H are permutation matrices, G⊕H and G⊗H will also be permutation matrices. Both of these matrix operations can represent the direct product of permutation groups. That is, given two permutation matrices G1 ∈ SN1 , and G2 ∈ SN2 , we can use both G1 ⊗ G2 and G1 ⊕ G2 to represent members of SN1 × SN2 . However, the resulting permutation matrices, can be interpreted as different actions: while the (N1 + N2) × (N1 + N2) direct sum matrix G1 ⊕G2 is a permutation of N1+N2 objects, the (N1N2)× (N1N2) Kronecker product matrix G1 ⊗G2 is a permutation of N1N2 objects.
Claim 1. Consider the vectorized relational data vec(X) of length N . The action of SN1 × . . .× SND on vec(X) is given by the following permutation group
GX . = {⊕
R∈R ⊗ d∈R Gd | (G1, . . . ,GD) ∈ SN1 × . . .× SND } . (2)
where the order of relations in ⊕
R∈R is consistent with the ordering used for vectorization of X.
Proof. The Kronecker product ⊗
d∈R G d when applied to vec(XR), permutes the underlying tensor
XR along the axes d ∈ R. Using direct sum, these permutations are applied to each tensor vec(XR) in vec(X) = [vec(XR1); . . . , vec(XRD )]. The only constraint, enforced by (2) is to use the same permutation matrix Gd for all R when d ∈ R. Therefore any matrix-vector product GN vec(X) is a “legal” permutation of vec(X), since it only shuffles the instances of each entity.

heading: 4 EQUIVARIANT ENTITY-RELATIONSHIP LAYER
text: Our objective is to constrain the standard feed-forward layer f : RK×N → RK′×N —where K,K ′ are the number of input and output channels, and N = | vec(X)|— such that any “legal” transformation of the input, as defined in (2), should result in the same transformation of the output. Doing so amounts to augmenting our input data by applying all such transformations and using an unconstrained feed-forward layer. This layer would be quadratic in the size of the database, and the model would require exponentially more data to train. In the case of even moderately sized databases this approach is simply infeasible, further motivation the our EERL (Definition 1). For clarity, we limit the following definition to the case where K = K ′ = 1; see Appendix F for the case of multiple channels.
Definition 1 (Equivariant Entity-Relationship Layer; EERL). Let GX be any N ×N permutation of vec(X). A fully connected layer σ(W vec(X)) with W ∈ RN×N is called an Equivariant Entity-Relationship Layer if
σ(WGX vec(X)) = GXσ(W vec(X)) ∀X ⇔ GX ∈ GX. (3)
That is, an EERL is a layer that commutes with the permutation GX if and only if GX is a legal permutation, as defined by (2).
An EERL2 captures the notion that the order of the entities in the relational data X is not important, and the layer should not produce different outputs when given different orderings. We now propose a procedure to tie the entries of W so as to guarantee the conditions of Definition 1. Moreover, we show that the resulting linear map W : RN×N is the most expressive linear map under the equivariance constraints.
2In its most general form, we can also allow for particular kinds of bias parameters in Definition 1; see Appendix D for parameter-tying in the bias term.
We build up the matrix W ∈ RN×N block-wise, with blocks Wi,j ∈ RNRi×NRj corresponding to each pair of relations Ri,Rj :
W = W 1,1 W1,2 . . . W1,|R| ... ... . . . ...
W|R|,1 W|R|,2 . . . W|R|,|R|  . (4) We tie parameters within each block, and not across blocks. To concisely express the somewhat complex tying scheme, we use the following indexing notation. Indexing Notation. The parameter block Wi,j is an NRi ×NRj matrix, where NRi = ∏ d∈Ri Nd. We want to index rows and columns of Wi,j . Given the relation Ri = {d1, . . . , d|Ri|}, we use the tuple ni .= 〈nid1 , . . . , n i d|Ri| 〉 ∈ [Nd1 ] × . . . × [Nd|Ri| ] to index an element in the set [NRi ]. Since each element of ni indexes instances of a particular entity, ni can be used as an index both for data block vec(XRi) and for the rows of parameter block Wi,j . In particular, to denote an entry of Wi,j , we use Wi,jni,nj . Moreover, we use n i d to denote the element of n
i corresponding to entity d ∈ Ri. Note that this is not necessarily the dth element of the tuple ni. For example, if Ri = {1, 4, 5} and ni = 〈400, 12, 3〉, then ni4 = 12 and ni5 = 3. When Ri is a multiset, we can use nid(k) to refer the to the element of ni corresponding to the k-th occurrence of entity d (where the order corresponds to the ordering of elements in ni). Table 1 in the Appendix summarizes our notation.

heading: 4.1 PARAMETER TYING
text: Let Wi,jni,nj and W i,j mi,mj denote two arbitrary elements of the parameter matrix W i,j . Our objective is to decide whether or not they should be tied together to ensure the resulting layer is an EERL (Definition 1). To this end we define an equivalence relation between the indices: 〈ni,nj〉 ∼ 〈mi,mj〉, and tie together all entries of W that are equivalent under this relation. Index 〈ni,nj〉 is equivalent to index 〈mi,mj〉 if they have the same equality patterns over their indices for each unique entity d.
We consider ni,j , the concatenation of ni with nj , and examine the sub-tuples ni,jd , where n i,j is restricted to only those indices that index entity d. We do this so that we can ask if these indices refer
to the same instance (e.g., the same student), and we can only meaningfully compare indices of the same entity (e.g., two entries in the STUDENT table may refer to the same student, but an entry in the STUDENT table cannot refer to the same thing as an entry in the COURSE table. Also, recall that we allow Ri and Rj to be multisets (e.g., the COURSE-COURSE relation R4 in Fig. 1). We say two tuples ni,jd = 〈nd(1) , . . . nd(L)〉 and m i,j d = 〈md(1) , . . .md(L)〉 are equivalent iff the have the same equality pattern nd(l) = nd(l′) ⇔ md(l) = md(l′)∀l ∈ [L]. Accordingly, two index tuples ni,j and mi,j are equivalent iff they are equivalent for all d ∈ Ri ∪Rj .
Because of this tying scheme, the total number of free parameters in Wi,j is the product of the number of possible different partitionings of ni,jd for each unique entity d ∈ Ri ∪Rj , and so is a product of Bell numbers3, which count the number of partitions of a set given size; see Appendix C for details. This relation to Bell numbers was previously shown for equivariant graph networks (Maron et al., 2018) which, as we see in Section 6, are closely related to, and indeed a special case of, our model. This parameter-sharing scheme admits a simple recursive form, if the database has no self-relations (i.e., the Ri are not multisets); see Appendix E. Example 1. [Fig. 2(a)] To get an intuition for this tying scheme, consider a simplified version of the relational structure of Fig. 1, restricted to the three relations R1 = {1, 2}, self-relation R2 = {2, 2}, and R3 = {1, 3} with N1 = 5 STUDENTS, N2 = 4 COURSES, and N3 = 3 PROFESSORS. Then N = 5×4+4×4+5×3 = 51, so W ∈ R51×51 and will have nine blocks: W1,1 ∈ R20×20,W1,2 ∈ R20×16.W2,2 ∈ R16×16 and so on. We use tuple n1 = 〈n11, n12〉 ∈ [N1] × [N2] = [5] × [4] to index the rows and columns of W1,1. We also use n1 to index the rows of W1,2, and use n2 = 〈n2
2(1) , n2 2(2) 〉 ∈ [N2]× [N2] = [4]× [4] to index its columns. Other blocks are indexed similarly.
Suppose n1 = 〈1, 4〉,n2 = 〈4, 5〉,m1 = 〈2, 3〉 and m2 = 〈3, 2〉 and we are trying to determine whether W1,2n1,n2 and W 1,2 m1,m2 should be tied. Then n
1,2 = 〈1, 4, 4, 5〉 and m1,2 = 〈2, 3, 3, 2〉. When we compare the sub-tuples restricted to unique entities, we see that the equality pattern of n1,21 = 〈1〉 matches that of m 1,2 1 = 〈2〉 (since it is only a singleton, it matches trivially), and the equality pattern of n1,22 = 〈4, 4, 5〉 matches that of m 1,2 2 = 〈3, 3, 2〉. So these weights should be tied.
We now establish the optimality of our constrained linear layer for relational data.
Theorem 4.1. Let X = {XR | R ∈ R} be the tensor representation of some relational data and vec(X) its vectorized form. If we define W block-wise according to (4), with blocks given by the tying scheme above, then the feed-forward layer σ(W vec(X)) is an Equivariant EntityRelationship Layer (Definition 1).
This theorem assures us that a layer constructed with our parameter-sharing scheme achieves equivariace w.r.t. the exchangeabilities of the relational data. However, one may wonder whether an alternative, more expressive parameter-sharing scheme (with the same form of output) may be possible. The following theorem asserts that this is not the case, and that our model is the most expressive parameter-tying scheme possible for an EERL.
Theorem 4.2. Let X = {XR | R ∈ R} be the tensor representation of some relational data. If W ∈ RN×N is any parameter matrix other than the one defined above, then the feed-forward layer σ(W vec(X)) is NOT an Equivariant Entity-Relationship Layer (Definition 1).
In practice, we approach this constrained layer in a much more efficient way: the operations of the layer can be performed efficiently using pooling and broadcasting over tensors; see Appendix E.

heading: 5 EXPERIMENTS

heading: 5.1 SYNTHETIC DATA
text: To continue with our running example we synthesize a toy dataset, restricted to R1 = {1, 2} (STUDENTCOURSE), R2 = {1, 3} (STUDENT-PROFESSOR), and R3 = {2, 3} (PROFESSOR-COURSE).4 Each matrix
3The k-th Bell number counts the number of ways of partitioning a set of size k. 4The code for our experiments is available at <anonymous> (synthetic data) and <anonymous> (soccer data).
transductive (a) and inductive (b) settings. The x-y location of each point encodes the prediction Ẑd, while the size and color of each encodes the ground-truth Zd. In the inductive setting, training and test databases contain completely distinct instances (i.e., completely different courses). Right (Missing record prediction). Average mean squared error in predicting missing records in STUDENT-COURSE as a function of sparsity level of the whole database X during training (x-axis) and test (y-axis), in the transductive setting (c) and the inductive setting (d). In (d) the model is tested on a new database with STUDENTS, COURSES and PROFESSORS unseen during training time. The baseline is predicting the mean value of training observations. At test time, the observed entries are used to predict the values of the fixed, held-out test set.
X{d1,d2} ∈ RNd1×Nd2 in the relational database, X = 〈X{1,2},X{1,3},X{2,3}〉, is produced by first uniformly sampling an h-dimensional embedding for each entity instance Zd ∈ RNd×h, followed by matrix product X{d1,d2} := Zd1Zd2T. A sparse subset of these matrices are observed by our model in the following experiments. Note that while we use a simple matrix product to generate the content of tables from latent factors, the model is oblivious to this generative process.
We use a factorized auto-encoding architecture consisting of a stack of EERN followed by pooling that produces code matrices Zd ∈ RNd×h′ ∀d ∈ {1, 2, 3} for each entity, STUDENT, COURSE and PROFESSOR. The code is then fed to a decoding EERN to reconstruct the sparse vec(X). For all experiments, the encoder consists of 7 EERLs, each with 64 hidden units, each using batch normalization (Ioffe & Szegedy, 2015) and channel-wise dropout. We then apply mean pooling to produce encodings. We found that batch normalization dramatically sped up the training procedure. See Appendix H for more details.
Once we finish training the model on a relational dataset, we can apply it to another instantiation — that is a dataset with completely different STUDENTS, COURSES and PROFESSORS.
Embedding and Missing Record Prediction. We use a small embedding dimension h = h′ = 2 for visualization of COURSE embeddings. Fig. 3(a) and (b) suggest that the learned embeddings agree with the ground truth. The structure within the data points has been preserved: in (a), points with a small x-coordinate in the ground-truth embeddings have a small x-coordinate in the learned embeddings (indicated by the darker color), and similarly for the y-coordinate and for (b). Note that in the best case, the two embeddings can agree up to a diffeomorphism. Next, we set out to predict missing records in the STUDENT-COURSE table using observed data from the whole database. For this, the factorized auto-encoding architecture is trained to only minimize the reconstruction error for “observed” entries in the STUDENT-COURSE tensor. We use N1 = N2 = N3 = 200, with an encoding size of 10. To study the model’s behaviour, we repeat the experiment while changing two quantities: 1) the percentage of observed entries (i.e., sparsity of all database tensors) at training time; and 2) the sparsity of test-time observations, after the model is trained. Fig. 3(c) visualizes the average prediction error, confirming our expectation that the amount of data seen during both training and testing can increase the prediction accuracy. More importantly, once the model is trained at a particular sparsity level, it shows robustness to changes in the sparsity level at test time.
Inductive Setting. Once we finish training the model on a relational dataset, we can apply it to another instantiation — that is a dataset with completely different STUDENTS, COURSES and PROFESSORS. Note that this is possible because the unique values in W do not grow with the number of instances of each entity in our database – i.e., we can resize W by repeating its pattern to fit the dimensionality of our data. In practice, since we use pooling-broadcasting operations, this resizing is implicit. Fig. 3(b) reproduces the embedding experiment, and Fig. 3(d) shows the missing record
prediction results for the inductive setting. In both cases the model performs well when applied to a new database. This setting can have interesting real-world applications, as it enables transfer learning across databases and allows for predictive analysis without training for new entities in a database as they become available.
The Value of Side Information. Do we gain anything by using the “entire” database for predicting missing entries of a particular table, compared to simply using the target tensor X{1,2} (STUDENT-COURSE table) for both training and testing? To answer this question, we fix the sparsity level of the STUDENTCOURSE table at 0.1%, and train models with increasing levels of sparsity for other tensors X{1,3} and X{2,3} in the range [0.025, 0.7]. This figure shows that the side information in the form of STUDENT-PROFESSOR and COURSE-PROFESSOR tables can significantly improve the prediction of missing records in the STUDENT-COURSE table.

heading: 5.2 PREDICTING ON SOCCER DATABASE
text: We use the European Soccer database to build a simple relational model with three entities: PLAYER, TEAM and MATCH. The database contains information for about 11,000 PLAYERS, 300 TEAMS and 25,000 MATCHES in European soccer leagues. We extract a COMPETES-IN relation between TEAMS and MATCHES, as well as a PLAYS-IN relation between PLAYERS and MATCHES that identifies which players played in each match. Our objective is to predict whether the outcome of a match was Home Win, Away Win, or Draw.
A simple baseline is to always predict Home Win, which obtains 46% accuracy. By engineering features from temporal statistics (such as the result of recent games for a team relative to a particular target match, recent games two teams played against each other, as well as recent goal statistics) the best model reported on Kaggle achieve 56% accuracy. Without using any temporal data, by simply taking the average for any such time series, our model achieves 53% accuracy. This also matches the accuracy of professional bookies. See Appendix H for details.

heading: 6 RELATED LITERATURE
text: For a more detailed literature review see Appendix A. Our work is related to a large body of work in statistical relational learning (Getoor & Taskar, 2007; Raedt et al., 2016) and knowledge-graph (KG) embedding (Nickel et al., 2016), as well as relational (e.g., Battaglia et al., 2018; Hamilton et al., 2017b), and equivariant (e.g., Cohen & Welling, 2016a; Ravanbakhsh et al., 2017b; Kondor & Trivedi, 2018; Cohen et al., 2019) deep learning. When dealing with a single relation, such as STUDENT-COURSE or USER-ITEM-TAG one may use tensor factorization methods for both embedding and tensor completion. However, with more than one relation, one needs to jointly factorize a set of tensors XR ∈ X, so that the factors in common between any two tensors are in agreement – e.g., in Fig. 1, X{1,2} and X{1,3} have a common factor, corresponding to the STUDENT entity.
Most relevant to our work in the statistical relational learning community is the relational neural network of Kazemi & Poole (2017). However, they focus on a single relation and the proposed model is more directly comparable to Hartford et al. (2018). See Appendix A.1.1 for discussion.
EERL generalizes several equivariant layers proposed for structured domains: Our model reduces to (equivariant model in) Deep-Sets (Zaheer et al., 2017) when we have a single relation R = {1} with a single entity – i.e., D = 1; i.e., a set of instances. Hartford et al. (2018) consider a more general setting of interaction across different sets, such as user-tag-movie relations. EERLs reduce to their parameter-sharing when we have a single relation R = {R} with multiple entities D ≥ 1, where all entities appear only once. Maron et al. (2018) further relax the assumption above, and allow for multiset relations. Intuitively, this form of relational data can model the interactions within and between sets; for example interaction within nodes of a graph is captured by an adjacency matrix, corresponding to D = 1 and R = {1, 1}. Our model reduces to this scheme when restricted to a single relation. For detailed discussion on these relations see Appendix A.

heading: CONCLUSION AND FUTURE WORK
text: We have outlined a novel and principled approach to deep learning with relational data(bases). In particular, we introduced a simple constraint in the form of tied parameters for the standard feedforward layer and proved that any other tying scheme either ignores the exchangeabilities of relational data or can be obtained by further constraining our model. The proposed layer can be applied in inductive settings, where the relational databases used during training and test have no overlap. While our model enjoys a linear computational complexity in the size of the database, we have to overcome one more hurdle before applying this model to large-scale real-world databases: relational databases often hold large amount of data, and in order for our model to be applied in these settings we need to perform mini-batch sampling. However, any such sampling has the effect of sparsifying the observed relations. A careful sampling procedure is required that minimizes this sparsification for a particular subset of entities or relations. While several recent works propose solutions to similar problems on graphs and tensors (e.g., Hamilton et al., 2017a; Hartford et al., 2018; Ying et al., 2018; Eksombatchai et al., 2017; Chen et al., 2018; Huang et al., 2018), we leave this important direction for relational databases to future work.

heading: A A MORE DETAILED REVIEW OF RELATED LITERATURE
text: To our knowledge there are no similar frameworks for direct application of deep models to relational databases, and current practice is to automate feature-engineering for specific prediction tasks (Lam et al., 2018).

heading: A.1 STATISTICAL RELATIONAL LEARNING AND KNOWLEDGE-GRAPH EMBEDDING
text: Statistical relational learning extends the reach of probabilistic inference to the relational model (Raedt et al., 2016). In particular, a variety of work in lifted inference procedures extends inference methods in graphical models to the relational setting, where in some cases the symmetry group of the model is used to speed up inference (Kersting, 2012). Most relevant to our work from this community is the Relational Neural Network model of Kazemi & Poole (2017); see Appendix A.1.1.
An alternative to inference with symbolic representations of relational data is to use embeddings. In particular, Tensor factorization methods that offer tractable inference in latent variable graphical models (Anandkumar et al., 2014), are extensively used for knowledge-graph embedding (Nickel et al., 2016). A knowledge-graph can be expressed as an ER diagram with a single relation R = {1(1), 2, 1(2)}, where 1(1), 1(2) representing HEAD and TAIL entities and 2 is an entity representing the RELATION. Alternatively, one could think of knowledge-graph as a graph representation for an instantiated ER diagram (as opposed to a set of of tables or tensors). However, in knowledge-graphs, an entity-type is a second class citizen, as it is either another attribute, or it is expressed through relations to special objects representing different “types”. Therefore, compared to ER diagrams, knowledge-graphs are less structured, and more suitable for representing a variety of relations between different objects, where the distinction between entity types is not key.

heading: A.1.1 RELATION TO RELNN OF KAZEMI & POOLE (2017)
text: An alternative approach explored in the statistical relational learning community includes extensions of logistic regression to relational data (Kazemi et al., 2014), and further extensions to multiple layers (Kazemi & Poole, 2017). The focus of these works is primarily on predicting properties of the various entity instances (the example they use is predicting a user’s gender based on the ratings given to movies).
Their model works by essentially counting the number of instances satisfy a given properties, but is easiest understood by interpreting it as a series of convolution operations using row- and column-wise filters that capture these properties. Consider Example 3 from (Kazemi & Poole, 2017) (also depicted in their Figure 4). We have a set of USERS and a set of MOVIES, and there is a matrix L ∈ RN×M , denoting which movies where liked by which users. As filters, they use binary vectors a ∈ RM , and o ∈ RN , representing which movies are ACTION and which users are OLD, respectively. The task they pose is to predict the gender of a user5, given this information. To do so, they include a third filter, φ ∈ RM , of learnable, “numeric latent properties”. Each layer of their model then convolves each of these filters with the LIKES matrix, then applies a simple linear scale and shift and a sigmoid activation. The result is three new filter vectors that can be used to make predictions or as filters in the next layer. For one layer, the outputs are then
va = σ ( wa0 + w a 1La ) , vo = σ ( wo0 + w o 1o TL ) , vφ = σ ( wφ0 + w φ 1Lφ ) where each w is a scalar. Observe that, for example, the nth element of La counts the number of action movies liked by user n. Observe also that va,vφ ∈ RN , while vo ∈ RM . So va and vφ can be used to make predictions about individual users. Note that the number of parameters in their model grows both with the number of movies and with the number of layers in the network.
Application of EERL to this example, reduces the 4 parameter model of (Hartford et al., 2018). Indeed, most discussions and “all” experiments in Kazemi & Poole (2017) assume a single relation. For completeness, we explain EERL in this setting. Consider the LIKES matrix, and the ACTION and
5For simplicity, and to follow the example of (Kazemi & Poole, 2017), we assume binary genders. However, we note that the real world is somewhat more complicated.
OLD filters as tables. We predict the gender of the nth user, as
gn = σ ( wo0on + w o 1 N∑ n′=1 on′ + w L 0 M∑ m=1 Ln,m + w L 1 M∑ n′=1 M∑ m=1 Ln′,m + w a 0 M∑ m=1 am ) . (5)
The main difference between their model and ours is that they require per-item parameters (e.g., one parameter per movie), while, as can be seen from (5), the number of parameters in our model is independent of the number of instances and so does not grow with the number of users or movies (note that we have the option of adding such features to our model by having unique one-hot features for each USER and MOVIE.) As a result, our model can be applied in inductive settings as well. One may also draw a parallel between row and column convolution in Kazemi & Poole (2017) with two out of four pooling operations when we have single relation between two entities. However these operations become insufficient when moving to models of self-relation (e.g., 15 parameters for a single self-relation) and does cannot adequately capture the interaction between multiple relations as discussed in our provably optimal linear layer.

heading: A.2 RELATIONAL, GEOMETRIC AND EQUIVARIANT DEEP LEARNING
text: See Hamilton et al. (2017b); Battaglia et al. (2018) for a detailed review. Scarselli et al. (2009) introduced a generic framework that iteratively updates node embeddings using neural networks. Li et al. (2015) integrated this iterative process in a recurrent architecture. Gilmer et al. (2017) proposed a similar iterative procedure that updates node embeddings and messages between the neighbouring nodes, and show that it subsumes several other deep models for attributed graphs (Duvenaud et al., 2015; Schütt et al., 2017; Li et al., 2015; Battaglia et al., 2016; Kearnes et al., 2016), including spectral methods. Their method is further generalized in (Kondor et al., 2018b) as well as (Maron et al., 2018), which is in turn subsumed in our framework. Spectral methods extend convolution to graphs (and manifolds) using eigenvectors of the Laplacian as the generalization of the Fourier basis (Bronstein et al., 2017; Bruna et al., 2014). Simplified variations of this approach leads to an intuitive yet non-maximal parameter-sharing scheme that is widely used in practice (Kipf & Welling, 2016). This type of simplified graph convolution has also been used for relational reasoning with knowledge-graphs (Schlichtkrull et al., 2018).
An alternative generalization of convolution is defined for functions over groups (Cohen & Welling, 2016a) or more generally homogeneous spaces (Cohen et al., 2018b). Moreover, convolution can be performed in the Fourier domain in this setting, where irreducible representations of a group become the Fourier bases (Kondor & Trivedi, 2018). Particularly relevant to our work are the models of (Kondor et al., 2018b) and (Maron et al., 2018) that operate on graph data using an equivariant design. Equivariant deep models for a variety of structured domains is explored in several other recent works. (e.g., Worrall et al., 2017; Cohen et al., 2018a; Kondor et al., 2018a; Sabour et al., 2017; Weiler et al., 2018); see also (Cohen & Welling, 2016b; Weiler et al., 2017; Kondor et al., 2018b; Anselmi et al., 2019).

heading: A.3 PARAMETER-SHARING, EXCHANGEABILITY AND EQUIVARIANCE
text: The notion of invariance is also studied under the term exchangeability in statistics (Orbanz & Roy, 2015); see also (Bloem-Reddy & Whye Teh, 2019) for a probabilistic approach to equivariance. In graphical models exchangeability is often encoded through plate notation, where parameter-sharing happens implicitly. In the AI community, this relationship between the parameter sharing and “invariance” properties of the network was noticed in the early days of the Perceptron (Minsky & Papert, 2017; Shawe-Taylor, 1989; 1993). This was rediscovered in (Ravanbakhsh et al., 2017b), where this relation was leveraged for equivariant model design. Ravanbakhsh et al. (2017b) show that when the group action is discrete “equivariance” to any group action can be obtained by parametersharing. In particular, one of the procedures discussed there ties the elements of W based on the orbits of the “joint” action of the group on the rows and columns of W. The parameter-tying scheme in the following can be obtained in this way:

heading: A.3.1 RELATION TO DEEP-SETS OF ZAHEER ET AL. (2017)
text: propose an equivariant model for set data. Our model reduces to their parameter-tying when we have a single relation R = {1} with a single entity – i.e., D = 1; i.e., a set of instances; see also Example 3 in Appendix E. Since we have a single relation, W matrix has a single block W = W1,1, indexed by n1. The elements of n1,1 = n1,11 = 〈n1(1) , n1(2)〉 index the elements of this matrix, for entity 1 (the only entity). There are two types of equality patterns n1(1) = n1(2) , and n1(1) 6= n1(2) , giving rise to the permutation equivariant layer introduced in (Ravanbakhsh et al., 2017a; Zaheer et al., 2017).

heading: A.3.2 RELATIONP TO EXCHANGEABLE TENSOR MODELS OF HARTFORD ET AL. (2018)
text: Hartford et al. (2018) consider a more general setting of interaction across different sets, such as user-tag-movie relations. Our model produces their parameter-sharing when we have a single relation R = {R} with multiple entities D ≥ 1, where all entities appear only once – i.e., κ(d) = 1∀d ∈ R. Here, again W = W1,1, and n1,1, the concatenation of row-index n1 and column index n1, identifies an element of this matrix. Since each d ∈ R has multiplicity 1, n1,1d = 〈n 1,1 d(1)
,n1,1d(2)〉 ∀d ∈ [D], and therefore n1,1d can have two class of equality patterns. This gives 2
D equivalence classes for n1,1, and therefore 2D unique parameters for a rank D exchangeable tensor.

heading: A.3.3 RELATIONSHIP TO EQUIVARIANT GRAPH NETWORKS OF MARON ET AL. (2018)
text: Maron et al. (2018) further relax the assumption of Hartford et al. (2018), and allow for κ(d) ≥ 1. Intuitively, this form of relational data can model the interactions within and between sets; for example interaction within nodes of a graph is captured by an adjacency matrix, corresponding to D = 1 and R = {1, 1}. This type of parameter-tying is maximal for graphs, and subsumes the parameter-tying approaches derived by simplification of Laplacian-based methods. When restricted to a single relation, our model reduces to the model of (Maron et al., 2018); however, when we have multiple relations, Wi,j for j 6= i, our model captures the interaction between different relations / tensors.

heading: B MULTISET RELATIONS
text: Because we allow a relation R to contain the same entities multiple times, we formally define a multiset as a tuple R̃ = 〈R, κ〉, where R is a set, and κ : R→ Nmaps elements of R to their multiset counts. We will call R the elements of the multiset R̃ = 〈R, κ〉, and κ(d) the count of element d. We define the union and intersection of two multisets R1 and R2 as R̃1 ∪ R̃2 = 〈R1 ∪R2, κ1 + κ2〉 and R̃1 ∩ R̃2 = 〈R1 ∩R2,min{κ1, κ2}〉. In general, we may also refer to a multiset using typical set notation (e.g., R = {d1, d1, d2}). We will use bracketed superscripts to distinguish distinct but equal members of any multiset (e.g., R = {d1, d1, d2} = {d(1)1 , d (2) 1 , d (1) 2 }). The ordering of equal members is specified by context or arbitrarily. The size of a multiset R̃ accounts for multiplicities: |R̃| = ∑ d∈R κ(d).

heading: C NUMBER OF FREE PARAMETERS
text: For the multiset relations R̃i = 〈Ri, κ〉 and R̃j = 〈Rj, κ〉, recall that two parameters Wi,jni,nj and Wi,jmi,mj are tied together if n i,j , the concatenation of ni with nj , is in the same equivalence class as mi,j . We partition each ni,jd into sub-partitions P(n i,j d ) . = {P1, . . . ,PL} of indices whose values are equal, and consider ni,j and mi,j to be equivalent if their partitions are the same for all d:
ni,j≡mi,j ⇔ P(ni,jd ) = P(m i,j d ) ∀d ∈ Ri ∪Rj (6)
See 4.1 for details. This means that the total number of free parameters in Wi,j is the product of the number of possible different partitionings for each unique entity d ∈ Ri ∪Rj :
|wi,j | = ∏
d∈Ri∪Rj
b(κi(d) + κj(d)) (7)
where wi,j is the free parameter vector associated with Wi,j , and b(κ) is the κth Bell number, which counts the possible partitionings of a set of size κ.
Example 2. [Fig. 2(a)] Consider again the simplified version of the relational structure of Fig. 1, restricted to the three relations R1 = {1, 2}, self-relation R2 = {2, 2}, andR3 = {1, 3} withN1 = 5 STUDENTS, N2 = 4 COURSES, and N3 = 3 PROFESSORS. We use tuple n1 = 〈n11, n12〉 ∈ [N1]× [N2] to index the rows and columns of W1,1. We also use n1 to index the rows of W1,2, and use n2 = 〈n2
2(1) , n2 2(2) 〉 ∈ [N2] × [N2] to index its columns. Other blocks are indexed similarly. The
elements of W1,1 take b(2)b(2) = 4 different values, depending on whether or not n11 = n 1′ 1 and n12 = n 1′ 2, for row index n
1 and column index n1′ (where b(k) is the k-th Bell number). The elements of W1,2 take b(1)b(3) = 5 different values: the index n11 can only be partitioned in a single way (b(1) = 1). However index n12 and indices n 2 2(1) and n2 2(2)
all index into the COURSES table, and so can each potentially refer to the same course. We thus have a unique parameter for each possible combination of equalities between these three items, giving us a factor of b(3) = 5 different parameter values; see Fig. 2(a), W1,1 is the upper left block, and W1,2 is the block to its right. The center block of Fig. 2(a), W2,2 produces the effect of R2 = {2, 2} on itself. Here, all four index values could refer to the same course, and so there are b(4) = 15 different parameters.

heading: D BIAS PARAMETERS
text: For full generality, our definition of EERL could also include bias terms without affecting its exchangeability properties. We exclude these in the statements of our main theorems for the sake of simplicity, but discuss their inclusion here for completeness. For each relation Ri = {d1, ..., d|Ri|}, we define a bias tensor Bi ∈ RNd1×...×Nd|Ri| . The elements of Bi are tied together in a manner similar to the tying of elements in each Wi,j : Two elements Bini and B i mi are tied together iff ni ≡ nj , using the definition of equivalence from Section 4.1. Thus, we have a vector of additional free parameters bi for each relation Ri, where
|bi| = ∏ d∈Ri b ( κi(d) ) . (8)
Consistent with our previous notation, we define B = {Bi | Ri ∈ R}, and vec(B) = 〈vec(B1), ..., vec(B|R|)〉. Then an EERL with bias terms is given by
vec(Y) = σ ( W vec(X) + vec(B) ) . (9)
The following Claim asserts that we can add this bias term without affecting the desired properties of the EERL.
Claim 2. If σ ( W vec(X) ) is an EERL, then σ ( W vec(X) + vec(B) ) is an EERL. The proof (found in Appendix G.1) argues that, since σ ( W vec(X) ) is an EERL, we just need to
show that GX vec(B) = vec(B) iff GX ∈ GX, which holds due to the tying of patterns in each Bi.

heading: E SIMPLIFICATIONS FOR MODELS WITHOUT SELF-RELATIONS
text: In the special case that the multi relations R̃i and R̃j are sets —i.e., have no self-relations— then the parameter tying scheme of Section 4.1 can be simplified considerably. In this section we address some nice properties of this special setting.

heading: E.1 EFFICIENT IMPLEMENTATION USING SUBSET-POOLING
text: Due to the particular structure of W when all relations contain only unique entities, the operation W vec(X) in the EERL can be implemented using (sum/mean) pooling operations over the tensors XR for R ∈ R, without any need for vectorization, or for storing W directly.
For Xi ∈ RNd1×...×Nd|R| and S ⊆ Ri, let pool(Xi,S) be the summation of the tensor Xi over the dimensions specified by S. That is, pool(Xi,S) ∈ R Nd′1 ×...×Nd′|Ri|−|S| where Ri\S = {d′1, . . . , d′|R|−|S|}. Then we can write element n i in the i-th block of W vec(X) as
(W vec(X))(i,ni) = ∑ Rj∈R ∑ S⊆Ri∩Rj wi,jS pool(X j ,S)ni Ri\S (10)
where ni Ri\S is the restriction of n i to only elements indexing entities in Ri\S. This formulation lends itself to a practical, efficient implementation where we simply compute each pool(Xi,S) term and broadcast-add them back into a tensor of appropriate dimensions.

heading: E.2 ONE-TO-ONE AND ONE-TO-MANY RELATIONS
text: In the special case of a one-to-one or one-to-many relations (e.g., in Fig. 1, one PROFESSOR may teach many COURSES, but each COURSE has only one PROFESSOR), we may further reduce the number of parameters due to redundancies. Suppose Ri ∈ R is some relation, and entity d ∈ Ri is in a one-to- relation with the remaining entities of Ri. Consider the 1D sub-array of XRi obtained by varying the value of nid while holding the remaining values n i Ri\{d} fixed. This sub-array contains just a single non-zero entry. According to the tying scheme described in Section 4.1, the parameter block Wi,i will contain unique parameter values wRi and wRi\{d}. Intuitively however, these two parameters capture exactly the same information, since the sub-array obtained by fixing the values of Ri\{d} contains exactly the same data as the sub-array obtained by fixing the values of Ri (i.e., the same single value). More concretely, to use the notation of Appendix E.1, we have pool(Xi,Ri\{d})ni{d} = pool(X i,Ri) in (10), and so we may tie w i,i Ri and wi,i Ri\{d}.
In fact, we can reduce the number of free parameters in the case of self-relations (i.e., relations with non-unique entities) as well in a similar manner.

heading: E.3 RECURSIVE DEFINITION OF THE WEIGHT MATRIX
text: We are able to describe the form of the parameter matrix Wi,j concisely in a recursive fashion, using Kronecker products: For any N ∈ N, let 1N ∈ RN×N be the N × N matrix of all ones, and IN the N × N identity matrix. Given any set of (unique) entities S = {d1, ..., d|S|} ⊆ {1, .., D}, for k = 1, ..., |S|, recursively define the sets
WSk = { W ⊗ 1Ndk +V ⊗ INdk |W,V ∈ W S k−1 } , (11)
with the base case of WS0 = R. Then for each block W i,j of (4) we simply have Wi,j ∈ WRi∩Rj|Ri∩Rj |.
Writing the blocks of the matrix (4) in this way makes it clear why block Wi,j contains 2|Ri∩Rj | unique parameter values in the case of distinct entities: at each level of the recursive definition we are doubling the total number of parameters by including terms from two elements from the level below. It also makes it clear that the parameter matrix for a rank-k tensor is built from copies of parameter matrices for rank-(k − 1) tensors.
Example 3. In the simple case where we have just one relation and one entity, R = {d} and the parameter matrix is an element of WR1 = {w ⊗ 1Nd + v ⊗ INd | w, v ∈ R}, which matches the parameter tying scheme of Zaheer et al. (2017). If instead we have a single relation with two distinct entities R = {d1, d2}, then the parameter matrix is an element of WR2 = {W ⊗ 1Nd2 +V ⊗ INd2 |W,V ∈ W R 1 }, which matches the tying scheme of Hartford et al. (2018).

heading: F USING MULTIPLE CHANNELS
text: Equivariance is maintained by composition of equivariant functions. This allows us to stack EERLs to build “deep” models that operate on relational databases. Using multiple input (K) and output (K ′) channels is also possible by replacing the parameter matrix W ∈ RN×N , with the parameter tensor W ∈ RK×N×N×K′ ; while K ×K ′ copies have the same parameter-tying pattern —i.e., there is no parameter-sharing “across” channels. The single-channel matrix-vector product in σ(W vec(X)) where (W vec(X))n = ∑ n′Wn,n′ vec(X)n′ is now replaced with contraction of two tensors
(W vec(X))n,k′ = ∑ n′,k∈[K] Wk,n,n′,k′ vec(X)n′,k, for k ′ ∈ [K ′].

heading: G PROOFS
text: Observe that for any index tuple n, we can express P(nd) (Section 4.1) as
P(nd) = {{ d(k), d(l) ∀k, l | nd(k) = nd(l) } ∣∣∣ d(k) = d(l) = d } . (12)
We will make use of this formulation in the proofs below.

heading: G.1 PROOF OF CLAIM 2
text: Proof. We want to show that GXσ ( W vec(X) + vec(B) ) = σ ( WGX vec(X) + vec(B) ) (13)
iff GX ∈ GX. Since σ ( W vec(X) ) is an EERL, this is equivalent to showing
GX vec(B) = vec(B) ⇐⇒ GX ∈ GX. (14)
(⇐=) Suppose GX ∈ GX, with GX defined as in Claim 1. Fix some relation R̃i and consider the i-th block of GX vec(B): (
GX vec(B) ) (i,ni) = ( Ki vec(Bi) ) ni
(15) = ∑ ni′ Kini,ni′ vec(B i)ni′ (16)
= vec(Bi)ni∗ , (17)
Where GX = diag(K1, ...,K|R|), and ni∗ is the unique index such that Kini,ni∗ = 1. As above, let nid be the restriction of n i to elements indexing entity d. Then we want to show that P(nid) = P(n i∗
d ) for all d ∈ Ri. Now, since GX ∈ GX and Kini,ni∗ = 1 we have
Gd nid(k) ,ni ∗ d(k) = 1 (18)
for all d ∈ Ri and all k. That is gd ( ni ∗
d(k) ) = nid(k) . Consider S ∈ P(n i d). we have
S = {d(k), d(l)∀k, l | nid(k) = n i d(l) } (19) = {d(k), d(l)∀k, l | gd −1( nid(k) ) = gd −1( nid(l) ) } (20)
= {d(k), d(l)∀k, l | ni ∗ d(k) = ni ∗ d(l) }. (21)
So P(nid) ⊆ P(ni ∗ d ). A similar argument has P(n i d) ⊇ P(ni ∗
d ). Thus, we have vec(Bi)ni∗ = vec(B i)ni , which completes the first direction.
(=⇒) Let GX vec(B) = vec(B). First, suppose for the sake of contradiction that GX 6∈ ⊕
R∈R S NR
and consider dividing the rows and columns of GX into blocks that correspond to each relation Ri. Then since GX 6∈ ⊕ R∈R S
NR , there exist Ri,Rj ∈ R, with i 6= j and ni ∈ [Ndi1 ]× ...× [Ndi|Ri| ] and nj ∈ [Ndj1 ]× ...× [Ndj|Rj | ] such that GX maps (i,ni) to (j,nj). That is gX ( (i,ni) ) = (j,nj) and thus GX(j,nj),(i,ni) = 1. So( GX vec(B) ) (j,nj) = ∑ k ∑ nk GX(j,nj),(k,nk) vec(B)(k,nk) (22)
= vec(B)(i,ni) (23)
= vec(Bi)ni (24)
6= vec(Bj)nj , (25)
by the definition of B. And so GX vec(B) 6= vec(B).
Next, suppose GX ∈ ⊕
R∈R S NR . Then for all Ri, there exist Ki ∈ SN
i
such that GX = diag(K1, ...,K|Ri|). For any ni we have
vec(Bi)ni = ( Ki vec(Bi) ) ni
(26) = ∑ ni′ Kini,ni′ vec(B i)ni′ (27)
= vec(Bi)ni∗ (28)
Where ni ∗
is the unique index such that Ki ni,ni∗
= 1. That is ki maps ni ∗
to ni. Then by the definition of Bi we have
P(ni ∗
d ) = P(n i d) = P ( (ki(ni ∗ ))d )
(29)
for all d ∈ Ri. (29) says that for each d the action of Ki on elements of ni∗ is determined only by the values of those elements, not by the values of elements indexing other entities, and so Ki ∈ ⊗ d∈Ri S Nd . But (29) also says that for all k, l
ni ∗
d(k) = ni
∗
d(l) ⇐⇒
( ki(ni ∗ ) ) d(k) = ( ki(ni ∗ ) ) d(l) , (30)
which says that the action of Ki is the same across any duplications of d (i.e., d(k) and d(l)), and so Ki = ⊗ d∈Ri G d, for some fixed Gd, and therefore GX ∈ GX.

heading: G.2 LEMMA 1 AND PROOF
text: To prove our main results about the optimality of EERLs we require the following Lemma.
Lemma 1. For any permutation matrices Ki ∈ SNi and Kj ∈ SNj we have
KiWi,j = Wi,jKj ⇔ Ki = ⊗ d∈R̃i Gd and Kj = ⊗ d∈R̃j Gd Gd ∈ SNd
for constrained Wi,j as define above. That is Ki and Kj should separately permute the instances of each entity in the multisets R̃i and R̃j , applying the same permutation to any duplicated entities, as well as to any entities common to both R̃i and R̃j .
To get an intuition for this lemma, consider the special case of i = j. In this case, the claim is that Wi,i commutes with any permutation matrix that is of the form Ki = ⊗ d∈Ri G
d. This gives us the kind of commutativity we desire for an EERL, at least for the diagonal blocks of W. Equivalently, commuting with Ki means that applying permutation Ki to the rows of Wi,i has the same effect as applying Ki to the columns of Wi,i. In the case of i 6= j, ensuring that Ki and Kj are defined over the same underlying set of permutations, {Gd ∈ SNd | d ∈ Ri ∪Rj}, ensures that permuting the rows of Wi,j with Ki has the same effect as permuting the columns of Wi,j with Kj . It is this property that will allow us to show that a network layer defined using such a parameter tying scheme is an EERL. See Fig. 2 for a minimal example, demonstrating this lemma.
We require the following technical Lemma for the proof of Lemma 1.
Lemma 2. Let Ri,Rj ∈ R, and for each d ∈ [D] let Gd ∈ SNd . If Gdnid(k) ,ni ′ d(k) = 1 for all d(k) ∈ Ri with d(k) = d, and Gdnj ′d(k) ,n j d(k) = 1 for all d(k) ∈ Rj with d(k) = d, then for all d(k) ∈ Ri and d(l) ∈ Rj with d(k) = d(l) = d, we have ni ′ d(k) = njd(l) ⇐⇒ n i d(k) = nj ′ d(l) .
Proof. Suppose Gd nid(k) ,ni′d(k) = 1 for all d(k) ∈ Ri, and Gdnj ′d(k) ,n j d(k) = 1 for all d(k) ∈ Rj . We prove the forward direction (=⇒). The backward direction follows from an identical argument. Fix some d(k) ∈ Ri and d(l) ∈ Rj and suppose ni ′ d(k)
= njd(l) . By assumption we have G d nid(k) ,ni′d(k) = 1
and so
gd(ni ′ d(k) ) = nid(k) . (31)
Similarly, we have Gd nj ′d(l) ,njd(l) = 1 and so
gd(njd(l)) = n j ′ d(l) . (32)
But ni′d(k) = n j d(l) and substituting into (31) we have
gd(njd(l)) = n i d(k) . (33)
And combining (32) and (33) gives nid(k) = n j ′ d(l) , as desired.
We are now equipped to prove our main claims, starting with Lemma 1:
Proof. (⇐=) Let R̃i = {di1, ..., di|R̃i|} and R̃j = {d j 1, ..., d j |R̃j| } and fix some {Gd ∈ SNd | d ∈ Ri ∪ Rj}. We index the rows of Wi,j , and the rows and columns of Ki, with tuples ni,ni ′ ∈ [Ndi1 ] × ... × [Ndi|Ri| ]. Similarly, the columns of W i,j , and rows and columns of Kj , are indexed with tuples nj ,nj ′ ∈ [Ndj1 ]× ...× [Ndj|Rj | ]. Since Ki = ⊗ d∈Ri G d we have
Kini,ni′ = ∏ d∈R̃i Gdnid,ni ′ d = ∏ d∈Ri κ(d)∏ k=1 Gdnid(k) ,n i′ d(k) .
And thus,
Kini,ni′ = 1 ⇐⇒ G d nid(k) ,ni′d(k) = 1,∀d(k) ∈ R̃i s.t. d(k) = d. (34)
The same is true for Rj . That is
Kj nj ′,nj = 1 ⇐⇒ Gd nj ′d(k) ,njd(k) = 1,∀d(k) ∈ R̃j s.t. d(k) = d. (35)
Now, fix some ni and nj . Since Ki is a permutation matrix, and so has only one 1 per row, we have( KiWi,j ) ni,nj = ∑ ni′ Kini,ni′W i,j ni′nj
= Wi,jni∗,nj , (36)
where ni∗ is the (unique) element of [Ndi1 ]× ...× [Ndi|Ri| ] which satisfies G d nid(k) ,ni∗d(k) = 1 for all d(k) ∈ R̃i with d(k) = d. Similarly,( Wi,jKj ) ni,nj
= ∑ nj ′ Wi,j ni,nj ′ Kj nj ′,nj
= Wi,jni,nj∗ (37)
where nj∗ is the (unique) element of [Ndj1 ]× ...× [Ndj|Rj | ] which satisfies Gd nj∗d(k) ,njd(k) = 1 for all d(k) ∈ R̃j with d(k) = d.
We want to show that P(ni ∗,j d ) = P(n i,j∗
d ) for all d ∈ Ri ∪ Rj . Fix d ∈ Ri ∪ Rj and let S̃ ∈ P(ni
∗,j d ). Then S̃ = {d(1), ..., d(K)}, where d(k) = d for all d(k) ∈ S̃, and for all d(k), d(l) ∈ S̃,
ni ∗,j d(k) = ni ∗,j d(l) . Then by Lemma 2 we have ni,j ∗ d(k) = ni,j ∗ d(l) , and so S̃ ∈ P(ni,j ∗ d ). So we have P(ni ∗,j d ) ⊆ P(n i,j∗ d ), and the other containment follows identically by symmetry. So n i∗,j ≡ ni,j∗ by our definition in Section 4.1, and so Wi,jni∗,nj = W i,j ni,nj∗ and by (36) and (37) above, KiWi,j = Wi,jKj .
(=⇒) Suppose KiWi,j = Wi,jKj . Fix some ni,nj . Let ni∗ be the unique index such that Ki
ni,ni∗ = 1, and nj the unique index such that Kj nj∗ ,nj = 1. Then
Wi,j ni∗ ,nj = ∑ ni′ Kini,ni′W i,j ni′,nj
= ( KiWi,j ) ni,nj
= ( Wi,jKj ) ni,nj
= ∑ nj ′ Wi,j ni,nj ′ Kj nj ′,nj
= Wi,jni,nj∗ , (38)
and so P(ni ∗,j d ) = P(n i,j∗ d ) for all d ∈ Ri ∪Rj . But this implies that
P(ni ∗
d ) = P(n i d) = P ( (ki(ni ∗ ))d ) . (39)
(39) says that for each d the action of Ki on elements of ni ∗
is determined only by the values of those elements, not by the values of elements indexing other entities, and so Ki ∈ ⊗ d∈Ri S
Nd . But (39) also means that for all k, l
ni ∗
d(k) = ni
∗
d(l) ⇐⇒
( ki(ni ∗ ) ) d(k) = ( ki(ni ∗ ) ) d(l) , (40)
which says that the action of Ki is the same across any duplications of d (i.e., d(k) and d(l)), and so Ki = ⊗ d∈Ri G d, for some fixed Gd. Similarly,
P(njd) = P(n j∗ d ) (41) = P ( (kj(nj))d ) , (42)
which shows that Kj = ⊗
d∈Rj G Nd ′. Finally, since P(ni ∗,j d ) = P(n i,j∗ d ), we also have
ni ∗
d(k) = njd(l) ⇐⇒ n i d(k)
= nj ∗
d(l) , (43)
for all k, l, which means
ni ∗
d(k) = njd(l) ⇐⇒
( ki(ni ∗ ) ) d(k) = ( kj(nj) ) d(l) . (44)
(44) says that Ki and Kj apply the same permutations to all duplications of any entities they have in common, and so Gd = Gd′, which completes the proof.

heading: G.3 PROOF OF THEOREM 4.1
text: Proof. Let GX ∈ SN and GX be defined as in Claim 1. We need to show that GXσ(W vec(X)) = σ(WGX vec(X)) iff GX ∈ GX for any assignment of values to the tables X. We prove each direction in turn.
(=⇒) We prove the contrapositive. Suppose GX 6∈ GX. We first show that GXW 6= WGX and then that GXσ(W vec(X)) 6= σ(WGX vec(X)) for an appropriate choice of X. There are three cases. First, suppose GX 6∈ ⊕ R∈R S
NR and consider dividing the rows and columns of GX into blocks that correspond to the blocks of W. Then since GX 6∈ ⊕ R∈R S
NR , there exist Ri,Rj ∈ R, with i 6= j and ni ∈ [Ndi1 ]× ...× [Ndi|Ri| ] and n j ∈ [Ndj1 ]× ...× [Ndj|Rj | ] such that GX maps (i,ni) to
(j,nj). That is gX ( (i,ni) ) = (j,nj) and thus, GX(j,nj),(i,ni) = 1. And so(
GXW ) (j,nj),(i,ni) = ∑ k ∑ nk GX(j,nj),(k,nk)W(k,nk),(i,ni)
= Wi,ini,ni ,
by the definition of W. Similarly,( WGX ) (j,nj),(i,ni) = ∑ k ∑ nk W(j,nj),(k,nk)G X (k,nk),(i,ni)
= Wj,jnj ,nj
But Wi,ini,ni 6= W j,j nj ,nj since i 6= j. And so G XW 6= WGX.
Next, suppose GX ∈ ⊕
R∈R S NR , but GX 6∈ ⊕ R∈R ⊗ d∈R S Nd and consider the diagonal
blocks of GXWGXT that correspond to those of W. If GX ∈ ⊕
R∈R S NR then it is block diagonal with blocks corresponding to each R ∈ R. But since GX 6∈ ⊕ R∈R ⊗ d∈R S Nd , there exists some
Ri ∈ R such that the ith diagonal block of GX is not of the form ⊗
d∈Ri G d for any Gd. Then by
Lemma 1 we will have inequality between GXWGXT and W in the ith diagonal block.
Finally, suppose GX ∈ ⊕ R∈R ⊗ d∈R S Nd . Then GX = K1 ⊕ ...⊕K|R|, where Ki ∈ ⊗ d∈R S Nd for all i. Since GX 6∈ GX, there exist R̃i, R̃j ∈ R, possibly with i = j, and a d∗ ∈ Ri ∩Rj such that
Ki = Gd i 1 ⊗ ...⊗Gd ∗ (k) ⊗ ...⊗Gd i |Ri| ,
and
Kj = Gd j 1 ⊗ ...⊗Gd ∗ (l) ⊗ ...⊗Gd j |Rj | ,
but Gd ∗ (k) 6= Gd ∗ (l) . Since Gd ∗ (k) 6= Gd ∗ (l) there exists n ∈ [Nd∗ ] with gd ∗ (l)(n) 6= gd ∗ (l)(n). Pick some ni and nj with nid∗ = n j d∗ = n. Let n
i∗ be the result of applying Ki to ni and nj∗ the result of applying Kj to nj . Then we have(
GXW ) (i,ni∗),(j,nj) = ∑ k ∑ nk GX(i,ni∗),(k,nk)W(k,nk),(j,nj)
= ∑ nk Kini∗,nkW i,j nk,nj
= Wi,jni,nj , (45)
and ( WGX ) (i,ni∗),(j,nj) = ∑ k ∑ nk W(i,ni∗),(k,nk)G X (k,nk),(j,nj)
= ∑ nk Wi,j ni∗,nk Kj nk,nj
= Wi,jni∗,nj∗ . (46)
Now, by construction we have nid∗ = n j d∗ , but n i∗ d∗ 6= nj ∗ d∗ . So P(n i,j d∗ ) 6= P(n i∗,j∗
d∗ ) and therefore Wi,jni,nj 6= W i,j ni∗,nj∗ . And so by (45) and (46) we have G XW 6= WGX.
And so in all three cases GXW 6= WGX. Thus, there exists some X, for which we have GXW vec(X) 6= WGX vec(X). Since σ is strictly monotonic, we have σ(GXW vec(X)) 6= σ(WGX vec(X)). And since σ is element wise we have GXσ(W vec(X)) 6= σ(WGX vec(X)), which proves the first direction.
(⇐=) Suppose GX ∈ GX. That is, for all d ∈ [D], let Gd ∈ SNd be some fixed permutation of Nd objects and let GX = ⊕ R∈R ⊗ d∈R G
d. Observe that GX is block-diagonal. Each block on the diagonal corresponds to an R ∈ R and is a Kronecker product over the matrices Gd for each d ∈ R. Let Ki = ⊗ d∈Ri G d for each i ∈ [|R|]. That is,
GX =  K1 0 K2 . . .
0 K|R|
 .
And so the i, j-th block of GXWGXT is given by:( GXWGX T )i,j = KiWi,jKj T
= Wi,j . (47)
The equality at (47) follows from Lemma 1. Thus, we have GXW = WGX, and so for all X, GXW vec(X) = WGX vec(X). Finally, since σ is applied element-wise, we have
σ(WGX vec(X)) = σ(GXW vec(X))
= GXσ(W vec(X))
Which proves the second direction. And so σ(W vec(X)) is an exchangeable relation layer, completing the proof.

heading: G.4 PROOF OF THEOREM 4.2
text: The idea is that if W is not of the form (4) then it has some block Wi,j containing two elements whose indices have the same equality pattern, but whose values are different. Based on these indices, we can explicitly construct a permutation which swaps the corresponding elements of these indices. This permutation is in GX but it does not commute with W. Now we present a detailed proof.
Proof. Let GX ∈ SN . For any relation R = {d1, ..., d|R|} ∈ R, let NR = [Nd1 ] × ... × [Nd|R| ] be the set of indices into XR. If W is not of the form described in Section 4 then there exist i, j ∈ [|R|], with ni,ni′ ∈ NRi and nj ,nj ′ ∈ NRj such that
Wi,jni,nj 6= W i,j ni′,nj ′
(48)
but
P(ni,jd ) = P(n i′,j′ d ), ∀d ∈ Ri ∪Rj (49)
That is, the pairs ni,nj and ni′,nj ′ have the same equality pattern over their elements, but the entries of Wi,j which correspond to these pairs have differing values, and thus violate the definition of W in Section 4. To show that the layer σ(W vec(X)) is not an EERL, we will demonstrate a permutation GX ∈ GX for which GXW 6= WGX, and thus GXσ(W vec(X)) 6= σ(WGX vec(X)) for some X. Let GX = ⊕ R∈R ⊗ d∈R G d, with the Gd defined as follows. For d ∈ Ri ∩Rj and all k:
Gd(n) =  ni ′ d(k) n = nid(k) nid(k) n = n i′ d(k) nj ′ d(k) n = njd(k) njd(k) n = n j ′ d(k)
n otherwise
.
For d ∈ Ri\Rj and all k:
Gd(n) =  ni ′ d(k) n = nid(k) nid(k) n = n i′ d(k)
n otherwise
.
For d ∈ Rj\Ri and all k:
Gd(n) =  nj ′ d(k) n = njd(k) njd(k) n = n j ′ d(k)
n otherwise
.
And for d 6∈ Ri ∪Rj :
Gd(n) = n.
That is, each Gd swaps the elements of ni with the corresponding elements of ni′, and the elements of nj with those of nj ′, so long as the relevant indices are present. For the case where d ∈ Ri ∩Rj , we need to make sure that this is a valid permutation. Specifically, we need to make sure that it is injective (it is clearly surjective from [Nd] to [Nd]). But it is indeed injective, since we have nid(k) = n j d(k) iff ni′d(k) = n j ′ d(k) for all d ∈ Ri ∩Rj and all k, since P(ni,jd ) = P(n i′,j′ d ).
Now, for all i, let Ki = ⊗
d∈Ri G d be the ith diagonal block of GX. By definition of the Gd, for all
d ∈ Ri we have Gdnid,ni′d = 1, and thus by the observation at (34) we have K i ni,ni′ = 1. And so( GXW ) (i,ni),(j,nj ′) = ∑ k ∑ nk GX(i,ni),(k,nk)W(k,nk),(j,nj ′)
= ∑ ni′′ Kini,ni′′W i,j ni′′,nj ′
= Wi,j ni′,nj ′ .
Similarly, Kj nj ,nj ′ = 1, so( WGX ) (i,ni),(j,nj ′) = ∑ k ∑ nk W(i,ni),(k,nk)G X (k,nk),(j,nj ′)
= ∑ nj ′′ Wi,j ni,nj ′′ Kj nj ′′,nj ′
= Wi,jni,nj .
Finally, by (48), GXW 6= WGX, completing the proof.

heading: H DETAILS OF EXPERIMENTS
text: The synthetic data we constructed used 200 instances for each of the three entities. Unless otherwise noted, we considered a 0.1 fraction as ‘observed’. We ensure that each row and column has at least 5 observations. For training, we pass our observed data through the network, producing encodings for each entity. We attempt to reconstruct the original input from these encodings. At test time, we use the training data to produce encodings as before, but now use these encodings to attempt to reconstruct test observations as well, reporting loss only on these test observations.
For all experiments, we used the following architecture: The encoder consists of 7 EERLs, each with 64 hidden units, each followed by a batch normalization (Ioffe & Szegedy, 2015) layer and a channel-wise dropout layer. We then apply a mean pooling layer to produce encodings. We found that batch normalization dramatically sped up the training procedure. The number of units in the pooling layer, and hence the size of the encodings, varied by experiment (see below for details). The decoder architecture is identical to that of the encoder, except that there is no pooling layer before the output. We used leaky ReLU activations (with parameter 0.1) in all layers except the final ones in both the encoder and decoder, where no activation is applied. In all experiments we used the Adam (Kingma & Ba, 2014) optimizer with initial learning rate 0.0001 to optimize a loss between the observed input values and our predicted output values in the relevant table(s). FOr the synthetic experiments the loss was RMSE, while for the soccer experiment we used cross-entropy. We did not perform any tuning of hyperparameters.

heading: H.1 EMBEDDING
text: We ran this experiment for 5000 epochs, and used an encoding size of 2 to facilitate plotting. We trained the model on 90% of the data, using 80% for training and 10% for validation. The remaining 10% was used to evaluate the quality of the model learned.

heading: H.2 MISSING RECORD PREDICTION
text: We held out a special 10% portion of the data for testing, then trained models using various amounts of the remaining data. For a 90%, 80%, ..., 10% fraction of the remaining data, we trained a model using this fraction of the data as observed (using a 90%/10% training/validation split). We then used each of these trained models to predict the held-out test set. When predicting the test set, we again varied the fraction of observed data we gave to the model to make its predictions, from 90% to 10%. For the inductive setting, the trained models were given data from the same distribution as they were trained on, while in the inductive setting the models were given data generated from a new set of entity embeddings. For each sparsity level, we trained the model for 4000 epochs, using an encoding size of 10. We repeated this experiment 15 times and averaged the results.

heading: H.3 PREDICTIVE VALUE OF SIDE INFORMATION
text: We fix the sparsity level of the STUDENT-COURSE table at 10% and calculate loss only on this table. We vary the sparsity level of the other tables over the range [.025, .7]. We use an 80%/10%/10% training/validation/test split and trained for 8000 epochs, producing an embedding of size 10. We repeat this experiment 17 times and average the results.

heading: H.4 PREDICTIONS ON THE SOCCER DATABASE
text: The dataset is available at https://www.kaggle.com/hugomathien/soccer. We constructed two tables for this experiment. The first table represents the relation between TEAMS and MATCHES. For input features we used all the player position features, as well as the match’s country, season, stage and date. We did not include any of the bookie predictions or the number of goals, as this would be cheating. For each team, we include all the team-related features found in the Team_Attributes table. When a team appears multiple times in the Team_Attributes table we aggregate the entries by averaging numerical features, and taking the most common value for categorical ones. We also include an additional binary feature indicating which team is home and which is away.
The second table captures the relation between PLAYERS and MATCHES. For each player participating in a match, we include all the features in the Player_Attributes table, aggregating entries for each player as described above. Again, we also include a binary feature indicating whether a player played for the home or away team.
We use a model built from five EERLs. All but the last one have 52 units (this is based on the limitation of our GPU memory), use ReLU activations, and are followed by a batch normalization layer (Ioffe & Szegedy, 2015) and channel-dropout. Chennel-dropout zeros whole channels at random for all entries of all tables, at a rate of 50%. The final EERL uses no activation and 8 output units. This is followed by a layer which sum-pools both tables into a single feature vector for each match. Finally, a linear layer produces a length-3 vector of predictions for each match. We train by minimizing cross-entropy loss between this output and the true match outcomes for 4000 steps. We report test results on a 90%/10% training/test split.

Review summaries:
This paper defines a parameter-tying scheme for a general feed-forward network which respects the equivalence properties of a vector encoding of relational (ie database) data. As long as this parameter-tying is observed, the resultant feed-forward network is guaranteed to respect the equivariant properties of this data, meaning entity indexes can be permuted, and the output produced by the layer will be permuted in the correct manner. This results in a maximally expressive feed forward layer for this kind of data.