Title: EQUIVARIANT ENTITY-RELATIONSHIP NETWORKS

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.

1. INTRODUCTION:

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) . The attributes associated with each entity and relation are stored in the corresponding table -e.g., table X {1,2} suggests that the STUDENT 5 took COURSE 4 and received a GRADE of 93. (c) Sparse tensor representation X R 1 , . . . , X R 7 of the tables of (b). The vectorized form of this set of sparse tensors, vec(X) = vec(X {1} ); . . . ; vec(X {2,2} ) -the column-vector concatenation of vec(X R )'sis the input to our feed-forward layer σ(W vec(X)). Here, the parameter-tying in the weight matrix W of the EERL (Fig. 2 ) guarantees that any permutation of elements of vec(X) corresponding to a shuffling of entities in this tensor representation (and only these permutations), results in the same permutation of the output of the layer.

2. REPRESENTATIONS OF RELATIONAL DATA:

We represent the relational model by a set of entities D = {1, ..., D} and a set of relations R ⊆ 2 D , indicating how the entities interact with one another. For each entity d ∈ D we have a set {1, .., N d } of instances of that entity. For each relation R ∈ R, where R = {d 1 , . . . , d |R| } is a set of entities, we observe data in the form of a set of tuples X R = { n d1 , . . . , n

d |R| , x | n di ∈ [N di ], x ∈ R K }.

That is, for each element of X R we associate the feature vector x with the relationship between the instances indexed by n di for each entity d i ∈ R. See Fig. 1 for a detailed, concrete example. Note that the singleton relation R = {d i } 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 ∈ R K 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.

2.1. TUPLES, TABLES AND TENSORS:

In relational databases the set of tuples X R is often represented using a table, with one row for each tuple; see Fig. 1(b ). An equivalent representation for X R is using a "sparse" |R|-dimensional tensor

X R ∈ R N d 1 ×...×N d |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 N d . In other words

n d1 , . . . , n d |R| , x ∈ X R ⇔ X R n d 1 ,...,n d |R| = x.

We work with this tensor representation of relational data. We use X = {X R | 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, X R 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.

3. EXCHANGEABILITIES OF ENTITY-RELATIONSHIP DATA:

Recall that in the representation X, each entity d ∈ {1, ..., D} has a set of instances indexed by

n d ∈ {1, .., N d }.

The ordering of {1, ..., N d } 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 X R , 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. S M refers to the symmetric group, the group of all permutations of M objects. A natural representation for a member of this group g M ∈ S M , 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, S N d is the group of all permutations of instances 1, . . . N d 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

EQUATION

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 S N1 × . . . × S N D with the D entities in a relational model, where each entity d has N d 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 S N1 × . . . × S N D on the vectorized form of X.

Vectorization. For each tensor X R ∈ X, N R = d∈R N d refers to the total number of elements of tensor X R (note that for now we are assuming that the tensors are dense). We will refer to N = R∈R N R as the number of elements of X. Then vec(X R ) ∈ R NR refers to the vectorization of X R , 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) ∈ R N to refer to [vec(X R1 ); . . . ; vec(X R |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 ∈ S N1 × . . . × S N D on vec(X) ∈ R N , permutes the elements of vec(X). Our objective is to define this group action by mapping S N1 × . . . × S N D to a group of permutations of all N = R∈R d∈R N d 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 ∈ R N1×N2 and H ∈ R N3×N4 be two matrices. The direct sum G ⊕ H is an (N 1 + N 3 ) × (N 2 + N 4 ) block-diagonal matrix, and the

Kronecker product G ⊗ H is an (N 1 N 3 ) × (N 2 N 4 ) matrix: G ⊕ H . = G 0 0 H , G ⊗ H . =    G 1,1 H . . . G 1,N2 H . . . . . . . . . G N1,1 H . . . G N1,N2 H    .

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 G 1 ∈ S N1 , and G2 ∈ S N2 , we can use both G 1 ⊗ G 2 and G 1 ⊕ G 2 to represent members of S N1 × S N2 . However, the resulting permutation matrices, can be interpreted as different actions: while the

(N 1 + N 2 ) × (N 1 + N 2 ) direct sum matrix G 1 ⊕ G 2 is a permutation of N 1 +N 2 objects, the (N 1 N 2 ) × (N 1 N 2 ) Kronecker product matrix G 1 ⊗ G 2 is a permutation of N 1 N 2 objects.

Claim 1. Consider the vectorized relational data vec(X) of length N . The action of S N1 × . . . × S N D on vec(X) is given by the following permutation group

EQUATION

)

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(X R ), permutes the underlying tensor X R along the axes d ∈ R. Using direct sum, these permutations are applied to each tensor vec(X R ) in vec(X) = [vec(X R1 ); . . . , vec(X R D )]. The only constraint, enforced by ( 2) is to use the same permutation matrix G d for all R when d ∈ R. Therefore any matrix-vector product G N vec(X) is a "legal" permutation of vec(X), since it only shuffles the instances of each entity.

4. EQUIVARIANT ENTITY-RELATIONSHIP LAYER:

Our objective is to constrain the standard feed-forward layer f : R K×N → R K ×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 G X be any

EQUATION

)

That is, an EERL is a layer that commutes with the permutation G X if and only if G X is a legal permutation, as defined by ( 2).

An EERL 2 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 : R N ×N is the most expressive linear map under the equivariance constraints. and G 3 ∈ S 3 are simply the respective identity permutations, while G 2 ∈ S 4 is the permutation (2, 1, 3, 4) (i.e., swap the first and second items). This corresponds to a "legal" permutation as defined by (2). We can see that this swapping is applied block-wise to blocks of rows of W corresponding to each W i,j for which 2 ∈ Ri.

In the case of R2 = {2, 2}, G 2 must also be applied to rows within blocks, as these correspond to entity 2 as well. (c) The result of applying the inverse permutation (in this case, the same permutation) to the columns of W. Here, we swap columns block-wise in each W i,j for which 2 ∈ Rj. By doing so we recover the original matrix. This symmetry condition on W is essential in achieving equivariance (see Lemma 1 in the proof of Theorem 4.1).

We build up the matrix W ∈ R N ×N block-wise, with blocks W i,j ∈ R NR i ×NR j corresponding to each pair of relations R i , R j :

EQUATION

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 W i,j is an N Ri × N Rj matrix, where N Ri = d∈Ri N d . We want to index rows and columns of W i,j . Given the relation R i = {d 1 , . . . , d |Ri| }, we use the tuple

n i . = n i d1 , . . . , n i d |R i | ∈ [N d1 ] × . . . × [N d |R i | ] to index an element in the set [N Ri ]

. Since each element of n i indexes instances of a particular entity, n i can be used as an index both for data block vec(X Ri ) and for the rows of parameter block W i,j . In particular, to denote an entry of W i,j , we use W i,j n i ,n j . Moreover, we use n i d to denote the element of n i corresponding to entity d ∈ R i . Note that this is not necessarily the d th element of the tuple n i . For example, if R i = {1, 4, 5} and n i = 400, 12, 3 , then n i 4 = 12 and n i 5 = 3. When R i is a multiset, we can use n i d (k) to refer the to the element of n i corresponding to the k-th occurrence of entity d (where the order corresponds to the ordering of elements in n i ). Table 1 in the Appendix summarizes our notation.

4.1. PARAMETER TYING:

Let W i,j n i ,n j and W i,j m i ,m j 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: n i , n j ∼ m i , m j , and tie together all entries of W that are equivalent under this relation. Index n i , n j is equivalent to index m i , m j if they have the same equality patterns over their indices for each unique entity d.

We consider n i,j , the concatenation of n i with n j , and examine the sub-tuples n i,j d , 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 R i and R j to be multisets (e.g., the COURSE-COURSE relation R 4 in Fig. 1 ). We say two tuples

n i,j d = n d (1) , . . . n d (L) and m i,j d = m d (1) , . . . m d (L) are equivalent iff the have the same equality pattern n d (l) = n d (l ) ⇔ m d (l) = m d (l ) ∀l ∈ [L].

Accordingly, two index tuples n i,j and m i,j are equivalent iff they are equivalent for all d ∈ R i ∪ R j .

Because of this tying scheme, the total number of free parameters in W i,j is the product of the number of possible different partitionings of n i,j d for each unique entity d ∈ R i ∪ R j , 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 R i 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

R 1 = {1, 2}, self-relation R 2 = {2, 2}, and R 3 = {1, 3} with N 1 = 5 STUDENTS, N 2 = 4 COURSES, and N 3 = 3 PROFESSORS. Then N = 5×4+4×4+5×3 = 51, so W ∈ R 51×51 and will have nine blocks: W 1,1 ∈ R 20×20 , W 1,2 ∈ R 20×16 .W 2,2 ∈ R 16×16 and so on. We use tuple n 1 = n 1 1 , n 1 2 ∈ [N 1 ] × [N 2 ] = [5] × [4]

to index the rows and columns of W 1,1 . We also use n 1 to index the rows of W 1,2 , and use

n 2 = n 2 2 (1) , n 2 2 (2) ∈ [N 2 ] × [N 2 ] = [4]× [4]

to index its columns. Other blocks are indexed similarly. Suppose n 1 = 1, 4 , n 2 = 4, 5 , m 1 = 2, 3 and m 2 = 3, 2 and we are trying to determine whether W 1,2 n 1 ,n 2 and W 1,2 m 1 ,m 2 should be tied. Then n 1,2 = 1, 4, 4, 5 and m 1,2 = 2, 3, 3, 2 . When we compare the sub-tuples restricted to unique entities, we see that the equality pattern of n 1,2 1 = 1 matches that of m 1,2 1 = 2 (since it is only a singleton, it matches trivially), and the equality pattern of n 1,2 2 = 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 = {X R | 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 Entity-Relationship 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 = {X R | R ∈ R} be the tensor representation of some relational data. If W ∈ R N ×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.

5. EXPERIMENTS:



5.1. SYNTHETIC DATA:

To continue with our running example we synthesize a toy dataset, restricted to R 1 = {1, 2} (STUDENT-COURSE), R 2 = {1, 3} (STUDENT-PROFESSOR), and R 3 = {2, 3} (PROFESSOR-COURSE).4 Each matrix 

X {d1,d2} ∈ R N d 1 ×N d 2 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 Z d ∈ R N d ×h , followed by matrix product X {d1,d2} := Z d1 Z d2 T . 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 Z d ∈ R N d ×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 instantiationthat 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 N 1 = N 2 = N 3 = 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. 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 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.

6. RELATED LITERATURE:

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 X R ∈ 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. 

CONCLUSION AND FUTURE WORK:

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.

A A MORE DETAILED REVIEW OF RELATED LITERATURE:

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) .

A.1 STATISTICAL RELATIONAL LEARNING AND KNOWLEDGE-GRAPH EMBEDDING 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.

A.1.1 RELATION TO RELNN OF KAZEMI & POOLE (2017):

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 ∈ R N ×M , denoting which movies where liked by which users. As filters, they use binary vectors a ∈ R M , and o ∈ R N , 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, φ ∈ R M , 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

v a = σ w a 0 + w a 1 La , v o = σ w o 0 + w o 1 o T L , v φ = σ w φ 0 + w φ 1 Lφ

where each w is a scalar. Observe that, for example, the n th element of La counts the number of action movies liked by user n. Observe also that v a , v φ ∈ R N , while v o ∈ R M . So v a 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 OLD filters as tables. We predict the gender of the n th user, as

g n = σ w o 0 o n + w o 1 N n =1 o n + w L 0 M m=1 L n,m + w L 1 M n =1 M m=1 L n ,m + w a 0 M m=1 a m . (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.

A 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) .

A.3 PARAMETER-SHARING, EXCHANGEABILITY AND EQUIVARIANCE:

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:

A.3.1 RELATION TO DEEP-SETS OF ZAHEER ET AL. ( 2017)

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 = W 1,1 , indexed by n 1 . The elements of n 1,1 = n 1,1 1 = n 1 (1) , n 1 (2) index the elements of this matrix, for entity 1 (the only entity). There are two types of equality patterns n 1 (1) = n 1 (2) , and n 1 (1) = n 1 (2) , giving rise to the permutation equivariant layer introduced in (Ravanbakhsh et al., 2017a; Zaheer et al., 2017) . Here, again W = W 1,1 , and n 1,1 , the concatenation of row-index n 1 and column index n 1 , identifies an element of this matrix. Since each

d ∈ R has multiplicity 1, n 1,1 d = n 1,1 d (1) , n 1,1 d (2) ∀d ∈ [D]

, and therefore n 1,1 d can have two class of equality patterns. This gives 2 D equivalence classes for n 1,1 , and therefore 2 D unique parameters for a rank D exchangeable tensor.

A.3.3 RELATIONSHIP TO EQUIVARIANT GRAPH NETWORKS OF MARON ET AL. (2018):

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, W i,j for j = i, our model captures the interaction between different relations / tensors.

x, n, m tuple or column vector (bold lower-case) •, • a tuple X, G, W tensor, inc. matrix (bold upper-case) X, R set (or multiset) S, G group (caligraphic)

D = [D] = {1, . . . , D} set of entities N 1 , . . . , N D number of instances R ⊆ 2 D a set of relations R i ⊆ D a relation X i = X Ri ∈ R Nd 1 ×...,Nd |R i | data for a relation R i X = {X i | R i ∈ R} relational data vec(X i ) vectorization of X i vec(X) vec(X 1 ), . . . , vec(X |R| ) N i = d∈Ri N d length of vec(X i ) N = Ri∈R N i length of vec(X) W ∈ R N ×N parameter matrix W i,j ∈ R N i ×N j (i,j) th block of W n i = n i d1 , . . . , n i d |R i | index for vec(X i )

and for rows of W i,j n = n 1 , . . . , n |R| index for vec(X) and rows/columns of W S M symmetric group M G X group of N × N "legal" permutations of vec(X) 

B MULTISET RELATIONS:

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 → N maps 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 R 1 and R 2 as

R 1 ∪ R 2 = R 1 ∪ R 2 , κ 1 + κ 2 and R 1 ∩ R 2 = R 1 ∩ R 2 , min{κ 1 , κ 2 } .

In general, we may also refer to a multiset using typical set notation (e.g., R = {d 1 , d 1 , d 2 }). We will use bracketed superscripts to distinguish distinct but equal members of any multiset (e.g.,

EQUATION

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).

C NUMBER OF FREE PARAMETERS:

For the multiset relations R i = R i , κ and R j = R j , κ , recall that two parameters W i,j n i ,n j and W i,j m i ,m j are tied together if n i,j , the concatenation of n i with n j , is in the same equivalence class as m i,j . We partition each n i,j d into sub-partitions P(n i,j d ) .

= {P 1 , . . . , P L } of indices whose values are equal, and consider n i,j and m i,j to be equivalent if their partitions are the same for all d:

EQUATION

See 4.1 for details. This means that the total number of free parameters in W i,j is the product of the number of possible different partitionings for each unique entity d ∈ R i ∪ R j :

EQUATION

where w i,j is the free parameter vector associated with W i,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

R 1 = {1, 2}, self-relation R 2 = {2, 2}, and R 3 = {1, 3} with N 1 = 5 STUDENTS, N 2 = 4 COURSES, and N 3 = 3 PROFESSORS. We use tuple n 1 = n 1 1 , n 1 2 ∈ [N 1 ] × [N 2 ]

to index the rows and columns of W 1,1 . We also use n 1 to index the rows of W 1,2 , and use

n 2 = n 2 2 (1) , n 2 2 (2) ∈ [N 2 ] × [N 2 ]

to index its columns. Other blocks are indexed similarly. The elements of W 1,1 take b(2)b(2) = 4 different values, depending on whether or not n 1 1 = n 1 1 and n 1 2 = n 1 2 , for row index n 1 and column index n 1 (where b(k) is the k-th Bell number). The elements of W 1,2 take b(1)b(3) = 5 different values: the index n 1 1 can only be partitioned in a single way (b(1) = 1). However index n 1 2 and indices n 2 2 (1) and n 2 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), W 1,1 is the upper left block, and W 1,2 is the block to its right. The center block of Fig. 2 (a), W 2,2 produces the effect of R 2 = {2, 2} on itself. Here, all four index values could refer to the same course, and so there are b(4) = 15 different parameters.

D BIAS PARAMETERS:

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

R i = {d 1 , ..., d |Ri| }, we define a bias tensor B i ∈ R N d 1 ×...×N d |R i | .

The elements of B i are tied together in a manner similar to the tying of elements in each W i,j : Two elements B i n i and B i m i are tied together iff n i ≡ n j , using the definition of equivalence from Section 4.1. Thus, we have a vector of additional free parameters b i for each relation R i , where

EQUATION

Consistent with our previous notation, we define B = {B i | R i ∈ R}, and vec(B) = vec(B 1 ), ..., vec(B |R| ) . Then an EERL with bias terms is given by

EQUATION

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 G X vec(B) = vec(B) iff G X ∈ G X , which holds due to the tying of patterns in each B i .

E SIMPLIFICATIONS FOR MODELS WITHOUT SELF-RELATIONS:

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.

E.1 EFFICIENT IMPLEMENTATION USING SUBSET-POOLING:

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 X R for R ∈ R, without any need for vectorization, or for storing W directly.

For X i ∈ R N d 1 ×...×N d |R| and S ⊆ R i , let pool(X i , S

) be the summation of the tensor X i over the dimensions specified by S. That is, pool

(X i , S) ∈ R N d 1 ×...×N d |R i |-|S| where R i \S = {d 1 , . . . , d |R|-|S| }.

Then we can write element n i in the i-th block of W vec(X) as

EQUATION

where n i Ri\S is the restriction of n i to only elements indexing entities in R i \S. This formulation lends itself to a practical, efficient implementation where we simply compute each pool(X i , S) term and broadcast-add them back into a tensor of appropriate dimensions.

E.2 ONE-TO-ONE AND ONE-TO-MANY RELATIONS:

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 R i ∈ R is some relation, and entity d ∈ R i is in a one-to-relation with the remaining entities of R i . Consider the 1D sub-array of X Ri obtained by varying the value of n i d 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 W i,i will contain unique parameter values w Ri and w Ri\{d} . Intuitively however, these two parameters capture exactly the same information, since the sub-array obtained by fixing the values of R i \{d} contains exactly the same data as the sub-array obtained by fixing the values of R i (i.e., the same single value). More concretely, to use the notation of Appendix E.1, we have pool(X i , R i \{d}) n i {d} = pool(X i , R i ) in ( 10), and so we may tie w i,i Ri and w i,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.

E.3 RECURSIVE DEFINITION OF THE WEIGHT MATRIX:

We are able to describe the form of the parameter matrix W i,j concisely in a recursive fashion, using Kronecker products: For any N ∈ N, let 1 N ∈ R N ×N be the N × N matrix of all ones, and I N the N × N identity matrix. Given any set of (unique) entities S = {d 1 , ..., d |S| } ⊆ {1, .., D}, for k = 1, ..., |S|, recursively define the sets

EQUATION

with the base case of W S 0 = R. Then for each block W i,j of (4) we simply have

W i,j ∈ W Ri∩Rj |Ri∩Rj | .

Writing the blocks of the matrix (4) in this way makes it clear why block W i,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

W R 1 = {w ⊗ 1 N d + v ⊗ I N d | 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 = {d 1 , d 2 }, then the parameter matrix is an element of

W R 2 = {W ⊗ 1 N d 2 + V ⊗ I N d 2 | W, V ∈ W R 1 }

, which matches the tying scheme of Hartford et al. (2018) .

F USING MULTIPLE CHANNELS:

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 ∈ R N ×N , with the parameter tensor W ∈ R K×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 W n,n vec(X) n is now replaced with contraction of two tensors

(W vec(X)) n,k = n ,k∈[K] W k,n,n ,k vec(X) n ,k , for k ∈ [K ].

G PROOFS:

Observe that for any index tuple n, we can express P(n d ) (Section 4.1) as

EQUATION

We will make use of this formulation in the proofs below.

G.1 PROOF OF CLAIM 2:

Proof. We want to show that

EQUATION

(⇐=) Suppose G X ∈ G X , with G X defined as in Claim 1. Fix some relation R i and consider the i-th block of G X vec(B):

EQUATION

Where G X = diag(K 1 , ..., K |R| ), and n i * is the unique index such that K i n i ,n i * = 1. As above, let n i d be the restriction of n i to elements indexing entity d. Then we want to show that P(n

i d ) = P(n i * d ) for all d ∈ R i . Now, since G X ∈ G X and K i n i ,n i * = 1 we have G d n i d (k) ,n i * d (k) = 1 (18) for all d ∈ R i and all k. That is g d n i * d (k) = n i d (k) . Consider S ∈ P(n i d ).

we have

EQUATION

So P(n i d ) ⊆ P(n i * d ). A similar argument has P(n i d ) ⊇ P(n i * d ). Thus, we have vec(B i ) n i * = vec(B i ) n i , which completes the first direction.

(=⇒) Let G X vec(B) = vec(B). First, suppose for the sake of contradiction that G X ∈ R∈R S NR and consider dividing the rows and columns of G X into blocks that correspond to each relation R i . Then since G X ∈ R∈R S NR , there exist R i , R j ∈ R, with i = j and n

EQUATION

by the definition of B. And so G X vec(B) = vec(B).

Next, suppose G X ∈ R∈R S NR . Then for all R i , there exist

EQUATION

Where n i * is the unique index such that K i n i ,n i * = 1. That is k i maps n i * to n i . Then by the definition of B i we have

EQUATION

for all d ∈ R i . (29) says that for each d the action of K i on elements of n i * is determined only by the values of those elements, not by the values of elements indexing other entities, and so K i ∈ d∈Ri S N d . But (29) also says that for all k, l n

EQUATION

which says that the action of K i is the same across any duplications of d (i.e., d (k) and d (l) ), and so

K i = d∈Ri G d , for some fixed G d , and therefore G X ∈ G X .

G.2 LEMMA 1 AND PROOF:

To prove our main results about the optimality of EERLs we require the following Lemma.

Lemma 1. For any permutation matrices K i ∈ S N i and K j ∈ S N j we have

K i W i,j = W i,j K j ⇔ K i = d∈ Ri G d and K j = d∈ Rj G d G d ∈ S N d

for constrained W i,j as define above. That is K i and K j 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 W i,i commutes with any permutation matrix that is of the form K i = 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 K i means that applying permutation K i to the rows of W i,i has the same effect as applying K i to the columns of W i,i . In the case of i = j, ensuring that K i and K j are defined over the same underlying set of permutations,

{G d ∈ S N d | d ∈ R i ∪ R j }

, ensures that permuting the rows of W i,j with K i has the same effect as permuting the columns of W i,j with K j . 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 R i , R j ∈ R, and for each d ∈ [D] let G d ∈ S N d . If G d n i d (k) ,n i d (k) = 1 for all d (k) ∈ R i with d (k) = d, and G d n j d (k) ,n j d (k) = 1 for all d (k) ∈ R j with d (k) = d, then for all d (k) ∈ R i and d (l) ∈ R j with d (k) = d (l) = d, we have n i d (k) = n j d (l) ⇐⇒ n i d (k) = n j d (l) . Proof. Suppose G d n i d (k) ,n i d (k) = 1 for all d (k) ∈ R i , and G d n j d (k) ,n j d (k)

= 1 for all d (k) ∈ R j . We prove the forward direction (=⇒). The backward direction follows from an identical argument. Fix some

d (k) ∈ R i and d (l) ∈ R j and suppose n i d (k) = n j d (l) . By assumption we have G d n i d (k) ,n i d (k) = 1

and so

EQUATION

Similarly, we have

G d n j d (l) ,n j d (l)

= 1 and so

EQUATION

But n i d (k) = n j d (l) and substituting into (31) we have

EQUATION

And combining (32) and (33) gives n i d (k) = n j d (l) , as desired.

We are now equipped to prove our main claims, starting with Lemma 1:

Proof. (⇐=) Let R i = {d i 1 , ..., d i | Ri| } and R j = {d j 1 , ..., d j | R j | } and fix some {G d ∈ S N d | d ∈ R i ∪ R j }.

We index the rows of W i,j , and the rows and columns of K i , with tuples n

i , n i ∈ [N d i 1 ] × ... × [N d i |R i | ].

Similarly, the columns of W i,j , and rows and columns of K j , are indexed with tuples n j , n

j ∈ [N d j 1 ] × ... × [N d j |R j | ]. Since K i = d∈Ri G d we have K i n i ,n i = d∈ Ri G d n i d ,n i d = d∈Ri κ(d) k=1 G d n i d (k) ,n i d (k)

.

And thus,

EQUATION

)

The same is true for R j . That is

EQUATION

for all k, l, which means

EQUATION

(44) says that K i and K j apply the same permutations to all duplications of any entities they have in common, and so G d = G d , which completes the proof.

G.3 PROOF OF THEOREM 4.1

Proof. Let G X ∈ S N and G X be defined as in Claim 1. We need to show that G X σ(W vec(X)) = σ(WG X vec(X)) iff G X ∈ G X for any assignment of values to the tables X. We prove each direction in turn.

(=⇒) We prove the contrapositive. Suppose G X ∈ G X . We first show that G X W = WG X and then that G X σ(W vec(X)) = σ(WG X vec(X)) for an appropriate choice of X. There are three cases. First, suppose G X ∈ R∈R S NR and consider dividing the rows and columns of G X into blocks that correspond to the blocks of W. Then since G X ∈ R∈R S NR , there exist R i , R j ∈ R, with i = j and

n i ∈ [N d i 1 ] × ... × [N d i |R i | ] and n j ∈ [N d j 1 ] × ... × [N d j |R j |

] such that G X maps (i, n i ) to (j, n j ). That is g X (i, n i ) = (j, n j ) and thus, G X (j,n j ),(i,n i ) = 1. And so G X W (j,n j ),(i,n i ) =

k n k G X (j,n j ),(k,n k ) W (k,n k ),(i,n i )

= W i,i n i ,n i , by the definition of W. Similarly, WG X (j,n j ),(i,n i ) =

k n k W (j,n j ),(k,n k ) G X (k,n k ),(i,n i ) = W j,j n j ,n j But W i,i n i ,n i = W j,j n j ,n j since i = j. And so G X W = WG X .

Next, suppose G X ∈ R∈R S NR , but G X ∈ R∈R d∈R S N d and consider the diagonal blocks of G X WG X T that correspond to those of W. If G X ∈ R∈R S N R then it is block diagonal with blocks corresponding to each R ∈ R. But since G X ∈ R∈R d∈R S N d , there exists some R i ∈ R such that the i th diagonal block of G X is not of the form d∈Ri G d for any G d . Then by Lemma 1 we will have inequality between G X WG X T and W in the i th diagonal block.

Finally, suppose G X ∈ R∈R d∈R S N d . Then G X = K 1 ⊕ ... ⊕ K |R| , where K i ∈ d∈R S N d for all i. Since G X ∈ G X , there exist R i , R j ∈ R, possibly with i = j, and a d * ∈ R i ∩ R j such that

K i = G d i 1 ⊗ ... ⊗ G d * (k) ⊗ ... ⊗ G d i |R i | ,

and (l) there exists n ∈ [N d * ] with g d * (l) (n) = g d * (l) (n). Pick some n i and n j with n i d * = n j d * = n. Let n i * be the result of applying K i to n i and n j * the result of applying K j to n j . Then we have G X W (i,n i * ),(j,n j ) = k n k G X (i,n i * ),(k,n k ) W (k,n k ),(j,n j ) n i ,n j = W i,j n i * ,n j * . And so by ( 45) and ( 46) we have G X W = WG X .

K j = G d j 1 ⊗ ... ⊗ G d * (l) ⊗ ... ⊗ G d j |R j | , but G d * (k) = G d * (l) . Since G d * (k) = G d *

EQUATION

And so in all three cases G X W = WG X . Thus, there exists some X, for which we have G X W vec(X) = WG X vec(X). Since σ is strictly monotonic, we have σ(G X W vec(X)) = σ(WG X vec(X)). And since σ is element wise we have G X σ(W vec(X)) = σ(WG X vec(X)), which proves the first direction.

(⇐=) Suppose G X ∈ G X . That is, for all d ∈ [D], let G d ∈ S N d be some fixed permutation of N d objects and let G X = R∈R d∈R G d . Observe that G X is block-diagonal. Each block on the diagonal corresponds to an R ∈ R and is a Kronecker product over the matrices G d for each

d ∈ R. Let K i = d∈Ri G d for each i ∈ [|R|]. That is, G X =       K 1 0 K 2 . . . 0 K |R|      

.

And so the i, j-th block of G X WG X T is given by:

EQUATION

The equality at (47) follows from Lemma 1. Thus, we have G X W = WG X , and so for all X, G X W vec(X) = WG X vec(X). Finally, since σ is applied element-wise, we have σ(WG X vec(X)) = σ(G X W vec(X))

= G X σ(W vec(X))

Which proves the second direction. And so σ(W vec(X)) is an exchangeable relation layer, completing the proof.

G.4 PROOF OF THEOREM 4.2

The idea is that if W is not of the form (4) then it has some block W i,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 G X but it does not commute with W. Now we present a detailed proof. with n i , n i ∈ N Ri and n j , n j ∈ N Rj such that W i,j n i ,n j = W i,j n i ,n j 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.

:

An alternative terminology refers to instances and entities as entities and entity types.

In 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.

The k-th Bell number counts the number of ways of partitioning a set of size k.

The code for our experiments is available at <anonymous> (synthetic data) and <anonymous> (soccer data).

For 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.

Figures and Tables:

Figure 1: (a) The Entity-Relationship (ER) diagram for our running example. There are three entities: STUDENT, COURSE and PROFESSOR (labeled 1,2 and 3 respectively), and four pairwise relations: TAKES (STUDENT-COURSE, represented by R1 = {1, 2}); the self-self relation PREREQUISITE (COURSE-COURSE, represented by R2 = {2, 2}); WRITES REFERENCE (STUDENT-PROFESSOR, represented by R3 = {1, 3}); and TEACHES (PROFESSOR-COURSE, represented by R4 = {2, 3}). The full set of relations is R = {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {2, 2}}. Both entities and relations have associated attributese.g., when a STUDENT takes a COURSE, they receive a GRADE. The singleton relation R = {1} can encode STUDENT attribute(s) such as number of INTERNSHIPS, or SALARY after graduating. Since each COURSE has a single PROFESSOR as its teacher, this relation is one-to-many. (b) Some possible relational tables in an instantiation of the ER diagram of (a). There are N1 = 5 instances of STUDENT, N2 = 4 instances of COURSE and N3 = 3 instances of PROFESSOR.The attributes associated with each entity and relation are stored in the corresponding table -e.g., table X {1,2} suggests that the STUDENT 5 took COURSE 4 and received a GRADE of 93. (c) Sparse tensor representation X R 1 , . . . , X R 7 of the tables of (b). The vectorized form of this set of sparse tensors, vec(X) = vec(X {1} ); . . . ; vec(X {2,2} ) -the column-vector concatenation of vec(X R )'sis the input to our feed-forward layer σ(W vec(X)). Here, the parameter-tying in the weight matrix W of the EERL (Fig.2) guarantees that any permutation of elements of vec(X) corresponding to a shuffling of entities in this tensor representation (and only these permutations), results in the same permutation of the output of the layer.

Figure 2: (a) The parameter matrix W from Example 2. Each colour represents a unique parameter value. The nine blocks, showing the interaction of three relations, are clearly visible. The arrows indicate the permutation that is being applied. (b) The result of applying a permutation to the rows of W. The permutation isG = G 1 ⊗ G 2 ⊗ G 3permuting the instances of STUDENT, COURSE and PROFESSOR. Here, G 1 ∈ S 5 and G 3 ∈ S 3 are simply the respective identity permutations, while G 2 ∈ S 4 is the permutation (2, 1, 3, 4) (i.e., swap the first and second items). This corresponds to a "legal" permutation as defined by (2). We can see that this swapping is applied block-wise to blocks of rows of W corresponding to each W i,j for which 2 ∈ Ri.In the case of R2 = {2, 2}, G 2 must also be applied to rows within blocks, as these correspond to entity 2 as well. (c) The result of applying the inverse permutation (in this case, the same permutation) to the columns of W. Here, we swap columns block-wise in each W i,j for which 2 ∈ Rj. By doing so we recover the original matrix. This symmetry condition on W is essential in achieving equivariance (see Lemma 1 in the proof of Theorem 4.1).

Figure 3: Left (Embeddings). Ground truth versus predicted embedding for COURSE instances in the 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 Z d . 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.

Fig. 3(b)  reproduces the embedding experiment, andFig. 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.

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.

.3.2 RELATIONP TO EXCHANGEABLE TENSOR MODELS OF HARTFORD ET AL. (2018) 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.

Let G X ∈ S N . For any relation R = {d 1 , ..., d |R| } ∈ R, let N R = [N d1 ] × ... × [N d |R| ]be the set of indices into X R . If W is not of the form described in Section 4 then there exist i, j ∈ [|R|],

i,j d ) = P(n i ,j d ), ∀d ∈ R i ∪ R j (49)

{1,2}  (STUDENT-COURSE table) for both training and testing? To answer this question, we fix the sparsity level of the STUDENT-COURSE 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.

Table content: <table/>

Summary of Notation

Table content: <table/>

WG X(i,n i * ),(j,nj ) = k n k W (i,n i * ),(k,n k ) G X (k,n k ),(j,n j )Now, by construction we haven i d * = n j d * , but n i * d * = n j * d * . So P(n i,j d * ) = P(n i * ,j * d * )and therefore W i,j

Table content: <table><tr><td>=</td><td>W i,j n i *  ,n k K j n k ,n j</td></tr><tr><td>n k</td><td/></tr><tr><td colspan="2">= W i,j n i *  ,n j  *  .</td><td>(46)</td></tr></table>

Peer review (iclr2020):
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. This is a very good paper and should be accepted. The approach is convincing, and provides a clear way forward for representing an important class of data. The paper is surprisingly well-written and comprehensible given the complexity of the math. I learned a lot from reading this paper. The experiments are somewhat rudimentary, but they are perfectly adequate for a paper whose contribution is primarily methodological and theoretical. One suggestion I have is that some of the details from the Appendix should be moved into the paper proper, most notably the details of the experiments in Appendix H.