Equivariant Entity-Relationship Networks
Authors: Devon Graham
Siamak Ravanbakhsh
Venue:  (2020)
Keywords: deep learning
relational model
knowledge graph
exchangeability
equivariance

Abstract: Due to its extensive use in databases, the relational model is ubiquitous in representing big-data. However, recent progress in deep learning with relational data has been focused on (knowledge) graphs. In this paper we propose Equivariant Entity-Relationship Networks, the 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 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.

Under review as a conference paper at ICLR 2020
EQUIVARIANT ENTITY-EELATIONSII NETWORKS
Anonymous authors
Paper under Nouble-blind review
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
Networks, a general class of parameter-sharing neural networks derived from the entity-reationshiip model. We prove that our proposed feed-forward layer 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 principled theoretical foundation for the application of deep learning to one of the most abundant forms of data.
INTRODUCTION
In the relational model of data, we have set of entities, and one more instances of each entity. These instances interact with each other through set of fixed relations between entities. A set of attributes may be associated with each type of entity and relation." 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, 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 world. The same formalism is used in AI through a probabilistic approach 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).
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 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- ggrap, 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. ((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 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 maximally expressive feed- forward layer that achieves equivariance w.r.t exchangeabilities in relational data as it is expressed by the entity-relaiionsipp 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).
An alternative terminology refers instances and entities entities and entity types.

---

Under review as a conference paper at ICLR 2020
1-Queet
2: CoCrrs
Studeett
21 Crune
Qulyy
Caras
100
Tacke
Prifese
Dunn 200
(8)
(b)
(c)
Figure 1: (a) The Entity- Relito--llaiinshiip (ER) diagram for our running example. There are three enti-
ties: STUDENT, COURSE and PROFESSOR (labeled 1.2 and 3 respectively), and four pairwise relations: TAKES (STUDENT-COURSE, represented by R1 {1,2]): the self-selff relation PREREQUISITE (COURSE- COURSE, represented by IR2 = {2,2]); WRITES REFERENCE
represented by
R3 {1,33); and TEACHES (PROFESSOR-COURSZ represented by R4 = (2,3)). The full of relations is R = [(1), (2), (3), {1, 2]. (1,3), (2,3), (2,2]} Both entities and relations have associated attributes
egg. when a STUDENT takes COURSE, they receive GRADE. The singleton relation = [11} 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 one-to-many. (b) Some possible relational tables an instantiation of the ER diagram of (a). There are Ni 5 instances of STUDENT, N₂ = 4 instances of COURSE and N3 = 3 instances of PROFESSOR. The attributes associated with each entity and relation are stored in the corresponding table -..., table X (1.2) suggests that the STUDENT 5 took COURSE 4 and received GRADE of 93. (c) Sparse tensor representation RR XR7 of the tables of (b). The vectorized form of this set of sparse tensors, vec(X) = (vec(X(")); .... vec(X (e.22((2.))) the column-vector concatenation of vec [ Ry's is the input to our feed-forward layer o( vec( Here, the parameter-tyinn in the weight matrix W of the EERL (Fig. 2) guarantees that any permutation of elements of vec(X) corresponding 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 A C 20 indicating how the entities interact with one another. For each entity d OD we have a set { Na of instances of that entity. For each relation & E R. where R = {d1,...
} is a set of entities, we observe data in the form of a set of tuples X = [(nd).... Rdd,y x) ndd E [Na,] E R*). That is, for each element of X2 we associate the feature vector with the relationship between the instances indexed by n'd, for each entity d: E R. See Fig. 1 for a detailed, concrete example. Note that the singleton relation R. {d:} can be used to incorporate individual entity attributes (such as professors' evaluations in Fig. (a)).
In the most general case, we allow for both R, and any E R to be multisets (i.e., to contain duplicate entries). Ri is 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 the real world, describing for example, the connection graph of a social network, the sale/purchase relationships between a group of companies, or, in running example, the COURSE-COURSE relation capturing prerequisite information. For our derivations make the simplifying assumption that each attribute x E R is scalar. Extension to x E R 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 XR is often represented using a table, with one row for each tuple; see Fig. 1(b). An equivalent representation for X is using "sparse" |R -dimensional tensor x E RR Naz x...x NajRi, where each dimension of this tensor corresponds to an entity d E IR, and the the length of that dimension is the number of instances No. In other words
(nd Mad......dppp. x²) X
XR
We work with this tensor representation of relational data. We use X = {X | the set of all sparse tensors that define the relational data(base); see Fig. 1(c). For the following
R E R} to denote
2

---

Under review as a conference paper at ICLR 2020
discussions around exchangeability and equivariance, we assume that for all R, X 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(x) d( while leaving a formal definition of multisets for the supplementary material; see Appendix B.
3 EXCHANGEABILITIES OF UNTITY-RELATIONS
DATA
Recall that in the representation X, each entity d E {I,..., D3 has set of instances indexed by na E [I,,,,,N! The ordering of {I,..., Na} 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 where d E R. using the same permutation applied 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 set equipped with binary operation between its members, such that the set and the operation satisfy closure, associativityy, invertability and existence of a unique identity element. 8 refers to the symmetric group, the group of all permutations of M objects. A natural representation for a member of this group g" E S.M is a permutation matrix G E {0. 1) M X Here, the binary group operation is the same as the product of permutation matrices. In this notation, 8Na is the group of all permutations of instances 1,... Na of entity d E {1..., D}. . To consider permutations multiple dimensions of data tensor can the direct product of groups. Given two groups G and H. the direct product G x H is defined by
hg E x H
G. He and (g,4)o(d',')) = o'
(1)
That is, the underlying set is the Cartesian product of the underlying sets of & and H. and the group operation the component-wise operation.
Observe that where each entity d has Na 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. I(c): permuting students, courses 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.
associate the group Ni x... x ND with the D entities in relational model,
Our goal is to define feed-forware layer that is "aware" of this structure. For this, first need to formalize the action of N x x N on the vectorized form of X.
Vectorization. For each tensor X X, No = NaER Na refers to the total number of elements of tensor 8 (note that for now we are assuming that the tensors are dense). We will refer to N Eee Np as the number of elements of X. Then vec(X*) E I refers to the vectorization of X obtained by successively stacking its elements along its dimensions, where the order of dimensions given by E R. We use vec-1() to refer to the inverse operation of vec(-), so that vec vec--
R
X. With a slight abuse of notation, we use vec(X) E R to refer to [vec(X : ( the vectorized form of the entire relational data. The weight matrix W that we define later creates feed-forward layer o oWW vec(X)) applied to this vector.
Group Action. The action of g E N:N x... x No on vee(X) R permutes the elements of vec(X). Our objective is to define this group action by mapping 8N x x ND to group of permutations of all N ERER I[ Na entries of the database - i..., homoomorphism into &. To this end we need to use two types of matrix product. Let G E R x and H E Ng Na be two matrices. The direct sum G @ H is (N₂ + No) x (N2 N4) block-diagonal matrix, and the
3

---

Under review as a conference paper at ICLR 2020
Kronecker product G @ H an (N1Ng) x (N2N)) matrix:
G1,HH
GI,,H
G 0 0
G + H
G
H
GN.HH
N,
Note that the special case that both G and are permutation matrices, G @ H and G H will also be permutation matrices. Both of these matrix operations represent the direct product of permutation groups. That is, given two permutation matrices G E &N,, and G E S2 we can use both G' & G and G @ G to represent members of S X 8N2, However, the resulting permutation matrices, can be interpreted as different actions: while the (Ni + N2) x (N1 + N2) direct matrix G
+ G is a permutation of Ni+N22 objects, the N2) (NiN) Kronecker product matrix G X G is permutation of N1 objects.
Claim 1. Consider the vectorized relational data vec(X) of length N. The action of N X... No on vec(X) is given by the following permutation group
GH
Ga (G' (G!....,G*) S.N. x... x &No).
dER
where the order of relations in DReo is consistent with the ordering used for vectorization of X.
Proof. The Kronecker product ØdER Gd when applied to vec(X*), permutes the underlying tensor X* along the axes d E R. Using direct sum, these permutations are applied to each tensor vec(X vec(X) [veo(X*) ): ::.... vec(X"R)] The only constraint, enforeed by (2) is to use the same permutation matrix G for all R when E R. Therefore any matrix-vector product G vec(X) is "legal"" permutation of vee(X), since it only shuffles the instances of each entity.
4 EQUIVARIANT ENTITY-RELATIONSHIIP LAYER
Our objective is to constrain the standard feed-forward layer f R + RK'N where K, K' are the number of input and output channels, and N /vee(X)] such that any "legal" transformation the input, as defined in (2), should result in the same transformation of the output. Doing so amounts augmenting our input data by applying all such transformations and using unconstrained feed-forward layer. This layer would be quadratic the size 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' 1; see Appendix for the case of multiple channels.
Definition (Equivariant Entity-Relationsinn Layer; EERL). Let G be any N N permutation of vec(X). A fully connected layer a (W vec(X)) with W e NNN is called an Equivariant Entity- Reliti-Reltiionshi Layer if
o(WG* vec(X)) G ( vec(X))
VX
G x G
That is, an EERL is a layer that commutes with the permutation G if and only if G is a legal permutation, defined by (2).
An EERL? captures the notion that the order of the entities in the relational data not important, and the layer should not produce different outputs when given different orderings. We now propose 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 is the most expressive linear map under the equivariance constraints.
II its most general form, we can also allow for particular kinds of bios parameters in Definition 1; see Appendix for parameter-tying in the bias term.
4

---

Under review as a conference paper at ICLR 2020
C
ST.CENN cOunSE-Coum STUCeIT COURT
(
(b)
(c)
Figure 2: (a) The parameter matrix W from Example 2. Each colour represents 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 permutation the of W. The permutation @ G² & G permuting the instances of STUDENT, COURSE and PROFESSOR. Here, G E 8 and G 8 simply the respective identity permutations, while G² 8 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 for which In the case of R2 {2, 2 G² must also be applied to rows within blocks, as these correspond to entity as well. (c) The result of applying the inverse permutation this case, the same permutation) to the columns of W. Here, swap columns block-wise in each W for which 2 R,, By doing we recover the original matrix. This symmetry condition on W essential achieving equivariance (see Lemma the proof of Theorem 4.1).
R,,
We build up the matrix W E RRN block-wise, with blocks W E R Na, x XNa,, corresponding each pair of relations R, Ry:
W1.
W1.2
WL
W
(4)
We tic parameters within each block, and not across blocks. To conciscly express the somewhat complex tying scheme, we use the following indexing notation.
Indexing Notation. The parameter block W is No, x NR, matrix, where NR; IaER. Na- We want to index rows and columns of Wi., Given the relation R, [di,..., ] use the tuple n' (ná,,..... md E [Na,] x ... x [Naja,]] to index an element in the set [Na.]- Since each element of n' indexes instances of particular entity, n' can be used as index both for data block vec( X R.) and for the rows of parameter block Wid. In particular, to denote an entry of W use w n'.."" Moreover,
use n' to denote the element of n' corresponding to entity d R. Note that this is not necessarily the dth element of the tuple n'. For example, R2 = {1, 4, 5} and n' (400, 12, 3), then mi} 12 and n 3. When R; is multiset, the element of n' corresponding the k-tth occurrence of entity (where the order corresponds to the ordering of elements in n²). Table in the Appendix summarizes our notation.
n n²(s) refer the
4.1 PARAMETER TYING
Let Wii n' ma and Wii m' mi denote two arbitrary elements of the parameter matrix Wir, Our objective 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 (m', m²), and tie together all entries of W that are equivalent under this relation. Index (n' n²) equivalent to index (m', m²) if they have the same equality patterns over their indices for each unique entity d.
equivalence relation between the indices: (n' nn)
We consider n.j, the concatenation of n' with n2, and examine the sub-tuples n where n' is restricted to only those indices that index entity d. We do this that we ask if these indices refer
5

---

Under review as a conference paper at ICLR 2020
to the same instance (e.g., the same student), and 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 allow R2 and R, to be multisets (e.g., the COURSE-COURSE relation IR, in Fig. 1). We say two tuples i. nd ( (atz)) and m 1.j = (man,, ... maar)) are equivalent iff the have the same equality pattern gg = g' O gay gor) vl E [T.]. Accordingly, two index tuples n and m are equivalent iff they are equivalent for all d E R2 U R.
entry in the COURSE table. Also, recall that
Because of this tying scheme, the total number of free parameters in W is the product of the number of possible different partitionings of n for each unique entity R, U R., and so is a product of Bell numbers', which count the number of partitions of 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 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 IR are not multisets); see Appendix E.
Example 1. [Fig. 2(a)] To get an intuition for this tying scheme, consider simplified version of the relational structure of Fig. 1, restricted to the three relations R1 {1. 2], self-relation B2 {2. 2}. and R3- = {1,3} with N1 5 STUDENTS, N2 = COURSES, and N3 3 PROFESSORS. Then
N = 5x 5xx44x445xx = 51, so W E ER51x5 and will have nine blocks: W E RR20 2020x W R 20 W2 E R16x16 and so on. We use tuple n' (nt, m²) [N1] [N₂] = 55 x [4]
to index the rows and columns of W1,1 We also use n to index the rows of W1, and use n² = (nza, (2 E [N2]]
{ x [N2] = [4] [4] to index its columns. Other blocks are indexed similarly. Suppose n (1, 4), n² = (4,5), m = (2 and m² = (3, 2) and we are trying to determine whether W1.2
n na and W m .ma should be tied. Then n = (1, 4, 4, 5) and m (2, 3, 2). When we compare the sub-tuples restricted to unique entities, we see that the equality pattern of ni (1) matches that of m, 1.2 = (2) (since it is only singleton, it matches trivially), and the 1.2 equality puttern of n22 (4, 4, 5) matches that of m (3,3,2) So these weights should be tied.
1.2
We now establish the optimality of our constrained linear layer for relational data.
Theorem 4.1. Let x = (x? R E R} be the tensor representation of some relational data and vec(%) (X) its vectorized form. we define W block-wise according to (4), with blocks given by the rying scheme above, then the feed-forward layer (W vee( (X)) is an Equivariant Entity- Relationship Layer (Definition 1).
This theorem assures us that layer constructed with our parameter-sharing scheme achieves equiv- ariace 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 possi- ble. 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 E R) be the tensor representation of some relational data. If W E NxN is any parameter matrix other than the one defined above, then the ferd-forward layer (W vec(X)) is NOT an Equivariant Entity- Relatto-etti Layer (Definition 1).
In practice, we approach this constrained layer in a much more efficient way: the operations of the layer can performed efficiently using pooling and broadcasting over tensors; see Appendix E.
EXPERIMENTS
5.1 SYNTHETIC DATA
To continue with our running example we synthesize toy dataset, restricted to R; = (1,2) (STUDENT- Each matrix
COURSE), R2 = (1 SETUDENT-PROFESSON and R3 = {2.3) 3)
'The k-th Bell number counts the number of ways of partitioning set of size kt
"The code for our experiments is available <anonymous> (synthetic data) and <anonymouss (soccer data).

---

Under review as a conference paper at ICLR 2020
10%
50%
90%
10%
50%
90%
baseline (1.89)
treining
50%
(0.95)
(0 (04
(0.24)
90%
% test time obs.
% test time ots.
(a) Transductive
(b) Inductive
(c) Transductive
(d) Inductive
Figure 3: Left (Embeddings). Ground truth versus predicted embedding for COURSE instances in the
transductive (a) and inductive (b) settings. The x-y location each point encodes the prediction 24, while the size and color of each encodes the ground-trutt truth Z In the inductive setting. training and test databases contain completely distinct instances (i.c., completely different courses). Right (Missing record prediction). Average mean squared error in predicting missing records in CUUDENT-COURSS whole database X during training (X-axis) and (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 predict the values of the fixed. held-out test set.
function of sparsity level of the
(d).da)) E Na, XN in the relational database, X = (x ((13), X x223)),, ). is produced by first uniformly sampling an h-dimensional embedding for each entity instance z E RR followed by matrix product X (d) := zd z T A sparse subset of these matrices are observed by our model in the following experiments. Note that while we use simple matrix product to generate the content of tables from latent factors, the model is oblivious to this generative process.
We factorized auto-encoding architecture consisting of stack of EERN followed by pooling that produces code matrices z NaNk Yd E {1, (1,2.3 3} for each entity, STUDENT, COURSE and PROFESSOR. The code is then fed to a decoding EERN to reconstruct the sparse voc(X). For all experiments, the encoder consists of EERLs, each with 64 hidden units, each using batch normalization (Toffe & 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 another instantiation that is a dataset with completely different STUDENTS, COURSES and PROFESSORS.
Embedding and Missing Record Prediction. We use small embedding dimension /: = 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 z-coordinate in the ground-truth embeddings have a small r-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-COURS! 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-COURSY tensor. We use Ni N2 N₂ 200, with an encoding size of 10. To study the model's behaviour, we repeat the experiment while changing two quantities: 1) the percentage observed entries (i.e., sparsity of all database tensors) 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 particular sparsity level, it shows robustness to changes the sparsity level at test time.
Inductive Setting. Once we finish training the model on a relational dataset, we can apply to another instantiation that is 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 gpoling-broadcuse implicit. Fig. 3(b) reproduces the embedding experiment, and Fig. 3(d) shows the missing record
operations, this resizing is
7

---

Under review as a conference paper at ICLR 2020
prediction results for the inductive setting. In both cases the model performs well when applied to 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 database as they become available.
The Value of Side Information. Do we gain anything by using the "entire" database for pre- dicting missing entries of particular table, compared to simply using the target tensor X (1,2) (STUDENT-COURSE table) for both training and testing? To an- swer 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 and ( in the range [0.025, 0.7]. This figure shows that the side information in the form of STUDENT-PROFESSON and COURSE-PROFESSOD ta- bles can significantly improve the prediction of missing records in the STUDENT-COURSE table.
The Value Information
0.45
0.30
0.25
0.20
5.2 PREDICTING ON SOCCER DATABASE
0.1
0.4
0.5
0.6
0.7
Percent Observed (side tablea)
We use the European Soccer database to build simple rela- tional 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 COMPETES-IN relation between TEAMS and MATCHES, as well as a PLAYS-IN IN relation between PLAYERS and MATCHES that identifies which players played in each match. Our objective is predict whether the outcome of match was Home Win, Away Win, or Draw.
simple baseline is always predict Home Win, which obtains 46% accuracy. By engincering 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 al., 2016) and knowledge-grapp (KG) embedding (Nickel et al., 2016), as well as relational (e.g., Battaglia et al., 2018; Hamilton 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 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 E X, so that the factors in common berween 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 1. for discussion.
EERL generalizes several equivariant layers proposed for structured domains: Our model reduces to (cquivariant 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-movee relations. EERLs reduce to their parameter-sharing 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 graph is captured by adjacency matrix, corresponding to D = 1 and = {1, 1}. Our model reduces to this scheme when restricted to a single relation. For detailed discussion these relations Appendix A.
when we have single relation Ri = [R.} with multiple entities > 1,
8

---

Under review as a conference paper at ICLR 2020
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 feed- forward 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 linear computational complexity in the size of database, we have to overcome one more hurdle before applying this model to large-scale real-world databases: relational databases often hold large amount data, and in order for our model be applied in these settings 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 particular subset of entities relations. While several recent works propose solutions to similar problems on graphs and tensors (e.g., Hamilton et al., 201 7a; Hartford et al., 2018; Ying et al., 2018; Eksombatchai al., 2017: Chen al., 2018 88; Huang et al., 2018), we leave this important direction for relational databases to future work.
REFERENCES
Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M Kakade, and Matus Telgarsky. Tensor decompositions for learning latent variable models. The Journal of Machine Learning Research, 15(1):2773-28322 2014.
Fabio Anselmi, Georgios Evangelopoulos, Lorenzo Rosasco, and Tomaso Poggio. Symmetry-adapted representation learning. Pattern Recognition, 86:201-208, 2019.
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. In Advances in neural information processing systems, pp. 4502-4510, 2016.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanzhez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv: arXiv:1806.00 1806.01261, 2018.
Benjamin Bloem-Redde and Yee Whye Teh. Probabilistic symmetry and invariant neural networks. arXiv preprint, (eXXiv/900..000 2019,
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18 42, 2017.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. ICLR, 2014.
Jie Chen, Tengfei Ma. and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. CoRR, abs/ 2018
Peter Pin-Shan Chen. The entity-relationship model-towart a unified view of data. ACM Transac- lions on Dutabase Systems (TODS), 1(1):9-36, 1976.
Taco S Cohen and Max Welling. Group equivariant convolutional networks. arXiv preprint
1oXx::6002.0776. 2016a.
Taco Cohen and Max Welling, Steerable enns. arXiv preprint arXiv:1612.08499, 2016b.
Taco S Cohen, Mario Geiger, Jonas Köhler, and Max Welling. Spherical cnns. arXiv preprint
arXiv: 1r01 10130, 2018a.
Taco S Cohen, Mario Geiger, and Maurice Weiler. Intertwiners between induced representations (with applications to the theory equivariant neural networks). arXiv preprint 1803 10743, 2018b.

---

Under review as a conference paper at ICLR 2020
Taco S Cohen, Maurice Weiler, Berkay Kicanaoglu, and Max Welling. Gauge equivariant convolu- tional networks and the icosahedral enn. arXiv preprint arXiv: S551::9902.04535. 2019.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems, 2015.
Chantat Eksombatchai, Pranav Jindal, Jerry Zitao Liu, Yuchen Liu, Rahul Sharma, Charles Sugnet, Mark Ulrich, and Jure Leskovec. Pixie: A system for recommending 3+ billion items to 200+ million users real-time. CoRR, abs/1711 1.106660,,, 2017.
Lise Getoor and Ben Taskar. Introduction to statistical relational learning. MIT press, 2007.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. arXiv preprint 1704:1170..0212,, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017a.
William L Hamilton, Rex Ying, and Jure Leskovec. Representation learning graphs: Methods and applications. arXiv preprint I 100::050944444 2017b.
Jason Hartford, Devon R Graham, Kevin Leyton-Brown, and Siamak Ravanbakhsh. Deep models of interactions across sets. Proceedings of the 35th International Conference on Machine Learning, pp. 1918, 2018.
Wenbing Huang. Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In Advances in Neural Information Processing Systems 31, pp. 4559-4566 2018.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint 102iv:1502.03167, 2015.
Seyed Mehran Kazemi and David Poole. Relnn: deep neural model for relational learning, arXiv preprint arXiv: 2017.
Seyed Mehran Kazemi, David Buchman, Kristian Kersting, Sriraam Natarajan, and David Poole. Relational logistic regression. In KR. Vienna, 2014.
Steven Kearnes, Kevin McCloskey, Mare Berndl, Vijay Pande, and Patrick Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of computer-aided molecular design, 30(8): 595-608, 2016.
Kristian Kersting. Lifted probabilistic inference. In ECAI, pp. 33-38, 2012.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 142.::1412.6980, 2014.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 1609.02907, 2016.
Risi Kondor and Shubhendu Trivedi. On the generalization of equivariance and convolution in neural networks to the action of compact groups. arXiv preprint arXiv: / 8802003690, 2018.
Risi Kondor, Zhen Lin, and Shubhendu Trivedi. Clebsch-gordan nets: fully fourier space spherical convolutional neural network. In Advances in Neural Information Processing Systems, pp. 10137- 10146, 2018a.
Risi Kondor, Hy Truong Son, Horace Pan, Brandon Anderson, and Shubhendu Trivedi. Covariant compositional networks for learning graphs. arXiv preprint arXiv:1801.02144 2018b.
Hoang Thanh Lam. Tran Ngoc Minh, Mathieu Sinn, Beat Buesser, and Martin Wistuba. Learning features for relational data. arXiv preprint arXiv: 1801.05372. 2018.
10

---

Under review as a conference paper at ICLR 2020
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, al. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 86(11))2278-2 2324, 1998.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint arXiv: 15 1.004993, 2015.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. arXiv preprini arXiv: 18f2::88/200922. 2018.
Marvin Minsky and Seymour A Papert. Perceptrons: An introduction to computational geomelry. MIT press. 2017.
Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 104(1):11-33) 2016.
Peter Orbanz and Daniel M Roy. Bayesian models of graphs, arrays and other exchangeable random structures. IEEE transactions on paltern analysis and machine intelligence, 37(2):437-46,, 2015.
Luc De Raedt, Kristian Kersting, Sriraam Natarajan, and David Poole. Statistical relational artificial intelligence: Logic, probability, and computation. Synthesis Lectures Artificial Intelligence and Machine Learning, 10(2):1-889, 2016.
Siamak Ravanbakhsh, Jeff Schneider, and Barnabas Poczos. Deep learning with sets and point clouds. In International Conference on Learning Representations (ICLR) - workshop track, 2017:t 7a.
Siamak Ravanbakhsh, Jeff Schneider, and Barnabas Poczos. Equivariance through parameter-share sharing.. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of JMLR: WCP, August 2017b.
Ian Robinson, Jim Webber, and Emil Eifrem. Graph databases. "O'Reilly Media, Inc.". 2013.
Sara Sabour, Nicholas Frosst, and Geoffrey E Hinton. Dynamic routing between capsules. In Advances in Neural Information Processing Systems, pp. 3856-3866, 2017.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-8)) 2009.
Michael Schlichtkrull, Thomas Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 593-607. Springer, 2018
Kristof T Schütt, Farhad Arbabzadah, Stefan Chmiela, Klaus R Müller, and Alexandre Tkatchenko. Quantum-chemical insights from deep tensor neural networks. Nature communications, 8: 13890, 2017.
John Shawe- Shawe-Taylor. Building symmetries into feedforward networks. In Artificial Neural Nenworks, 1989., First IEE International Conference on (Conf. Publ. No. 313), pp. 168-162. IET, 1989.
John Shawe-Taylor Symmetries and discriminability in feedforward network architectures. JEEE Transactions on Neural Networks, (5):816-826, 1993.
Maurice Weiler, Fred A Hamprecht, and Martin Storath. Learning steerable filters for rotation 2017.
equivariant enns. arXiv preprint
Maurice Weiler, Wouter Boomsma, Mario Geiger. Max Welling, and Taco Cohen. 3d steerable cnns: Learning rotationally equivariant features in volumetric data. In Advances in Neural Information Processing Systems, pp. 10401-10412, 2018.
Daniel E Worrall, Stephan J Garbin, Daniyar Turmukhambetov, and Gabriel J Brostow. Harmonic networks: Deep translation and rotation equivariance. In Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), volume 2, 2017.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. arXiv preprint /.ff:18806.0973.. 2018
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances in Neural Information Processing Systems, 2017.
11

---

Under review as a conference paper at ICLR 2020
A A MORE DETAILED REVIEW OF RELATED LITERATURE
To our knowledge there are similar frameworks for direct application of deep models to relational databases, and current practice is to automate feature-engineering for specifie prediction tasks (Lam et al., 2018).
A.1 STATISTICAL RELATIONAL LEARNING AND KNOWLEDGE-GRAN GRAPH EMBEDDING
Statistical relational learning extends the reach of probabilistic inference to the relational model (Raedt al., 2). In particular, 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 speed up inference (Kersting, 2012). Most relevant our work from this community the Relational Neural Network model of Kazemi & Poole 201 see Appendix A.I.I.
An alternative to inference with symbolic representations of relational data 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-gras et al., 2016), 6). A knowledge-graph can be expressed as an ER diagram with a single relation R [1())22 2, (2)), where (1) ((2) representing HEAD and TAIL. entities and 2 is an entity representing graph representation for an
embedding (Nickel
the RELATION. Alternatively, one could think of knowledge-gran instantiated ER diagram (as opposed to a set of of tables or tensors). However, in Knowledge-graphs. an entity-type is second class citizen, it is either another attribute, or it is expressed through relations to special objects representing different "types". Therefore, compared to ER diagrams, knowledge-o -gapphs are less structured, and more suitable for representing 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 primarily on predicting properties of the various entity instances (the example they use is predicting user's gender based on the ratings given to movies).
Their model works by essentially counting the number of instances satisfy given properties, but is easiest understood by interpreting 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 E R N denoting which movies where liked by which users. As filters, they use binary vectors a E I and E RR representing which movies are ACTION and which users are OLDD, respectively. The task they pose is to predict the gender of a user', given this information. To do so, they include third filter, & E R of learnable, "numeric latent properties". Each layer of their model then convolves each of these filters with the LIKES matrix, then applies simple linear scale and shift and 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 = ( wi + wi weLLa); v =====
wg + =o (08
(ow++oo u v = o 0010 + w
where each w is a scalar. Observe that, for example, the th element of La counts the number of action movies liked by user Observe also that v v E R.V. while v E R.M. So v and ve 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 single relation. For completeness, we explain EERL in this setting. Consider the LIKES matrix, and the ACTION and
Forr 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.
12

---

Under review as a conference paper at ICLR 2020
OLD filters as tables. We predict the gender of the n user,
N
M Σ m=1
M
M
M
gn =0 [o(oo Σ n'=1
+ wi
Op
mm + w1
Σ ===m=1
Σ
La + W0
am
(5)
m=1
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 (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 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 single self-relation) and does cannot adequately capture the interaction between multiple relations as discussed in our provably optimal linear layer.
grow with the number of users movies
A.2 RELATIONAL, GEOMETRIC AND EQUIVARIANT DEEP LEARNING
See Hamilton et al. (2017b); Battaglia et al. (2018) for 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 recurrent architecture. Gilmer et al. (2017) proposed 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., 201 8b) as well as (Maron et al., 2018), which is in turn subsumed in our framework. Spectral methods extend convolution to graphs (and manifolds) using cigenvectors 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 al., 2018).
An alternative generalization of convolution is defined for functions over groups (Cohen & Welling, 2016a) 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 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 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 SARAMETER-SHARINS EXCHANGEABILITY AND EQUIVARIANCE
The notion of invariance is also studied under the term exchangeability in statistics (Orbanz & Roy, 2015); see also Glloem-Redds & Whye Teh, 2019) for a probabilistic approach equivariance. In graphical models exchangeability is often encoded through plate notation, where parameter-sharin Seapieitli
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 parameter- sharing. In particular, 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:
of the procedures discussed there ties the elements of W based on the
13

---

Under review as a conference paper at ICLR 2020
A.3.1 RELATION TO DEEP-SETE 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 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 indexed by (Mi(s) ?1 index the elements of this matrix, for entity 1 (the only entity). There are two types of equality patterns Rig; (22 and Ri + (2, giving rise to the permutation equivariant layer introduced in (Ravanbakhsh et al., 2017a; Zaheer et al., 2017).
n'. The elements of n ni
A.3.2 RELATIONP TO EXCHANGEABLE TENSOR MODELS OF HARTFORD AL. (2018)
Hartford et al. (2018) consider 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 2 1, where all entities appear only once - i.e., k(d) 14d E R. Here, again W W and n the concatenation of row-index n' and column index n identifies an element of this matrix. Since each d E IR has multiplicity 1, nd 1.1 (m 4(2)
1.1 1.1 Ad [D], and
therefore n 1.1 can have two class of equality patterns. This gives 2 equivalence classes for n1.1, and therefore 2 unique parameters for 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 x(d) 2 1. Intuitively, this form of relational data can model the interactions within and between sets; for example interaction within nodes of graph is captured by an adjacency matrix, corresponding to
D = 1 and R = 11, 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 for j # i, our model captures the interaction between different relations / tensors.
J. (.-)
tuple column vector (bold lower-case) a tuple (ensor, inc. matrix (bold upper-case)
veo(X) N'
{ven (X) "....... vec(X vec(X|(9)))
ILEe Na
length of vee(X*)
N Riem N
length of vec(X)
X. G.
W C ROx
parameter matrix (i.i)h block of W
W R N
X. R
set (or multiset)
8.
G
group (caligraphic)
(n
index for vec(X*) and for rows of Wis index for vec(%) and rows/columns of W symmetric group M group of N x N "legal" permutations of voc(X)
① D
(1,
D
set of entities number of instances
ND
(n)
n 1911
2 C 2
a set of relations a relation
R,
8.
X = RR. E R N4.
data for relation R, relational data
G
X X
R, St)
vec(X')
vectorization of X
Table I: Summary of Notation
B MULTISET RELATIONS
Because allow relation IR to contain the same entities multiple times, we formally define multiset tuple R (R. rs). where R is set, and R - IN maps elements of to their multiset counts. We will call R the elements of the multiset IR (R, k),, and x(d) the count of element d. We define the union and intersection of two multisets R2 and R2 as R2 U UR2 = (R, U R22 K1 + k2) and R n R2 (R, n R2, min (K1, k2 In general, we may also refer to multiset using typical set notation (e.g., R [d1 dd, dz)). We will use bracketed superscripts to distinguish distinct but equal members of any multiset (e.g., R = {d1, d1, d2) = {d"", ,d(²) d The ordering of equal members is specified by context arbitrarily. The size of multiset RR accounts for multiplicities: [R| Eder (d))
14

---

Under review as a conference paper at ICLR 2020
C NUMBER OF FREE PARAMETERS
For the multiset relations R2 (Ra, x)) and R = (B,, k), recall that two parameters W n' and W m'.m' are tied together if n* the concatenation of n' with n², is in the same equivalence class as m We partition each n into sub-partitions IP ((( ( = {PI,...., (P)) of indices whose values are equal, and consider n f and m² be equivalent their partitions are the same for all
-==* 55 + P( ((m))) Vd E R. URj
(6)
See 4.1 for details. This means that the total number free parameters in Wir is the product of the number of possible different partitionings for each unique entity d E IR; U Ry:
|
II dER,UR;
(c)
where w is the free parameter vector associated with W and b(K) is the 1²t Bell number, which counts the possible partitionings of a set of size k.
Example 2. [Fig. 2(a)] Consider again the simplified version of the relational structure of Fig. 1, restricted to the three relations R1 2). self-relation B2 = [2.2]. and R3 {1, 3) with N1
STUDENTS, N2 = 4 COURSES, and Ng = 3 PROFESSorS. We use tuple n' = (mi, m2) E [Ni] x [N2] index the rows and columns of Wi.1 We also n to index the rows of WL.2 and use n² = =mZaa> n2aa)) E [N2) x [N₂] to index its columns. Other blocks are indexed similarly. The
elements of W take 6(2)6(2) 4 different values, depending on whether or not n n'' and nz = 2or row index n² and column index n²' (where b(k) the k-th Bell number). The elements of W1.2 take b(1)b(3) = 5 different values: the index ni can only be partitioned in single way (b(1)= = 1). However index n. and indices n2en, and 12g0, all index into the COURSES table, and so can each potentially refer to the same course. We thus have 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. is the block 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 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, = =dd1.... dRR
we define a bias tensor B' E R. X...X.N The elements of B' are tied together in a manner similar to the tying of elements in each WiJ; Two elements By and B are tied together iff
n' = n², using the definition of equivalence from Section 4. Thus, have vector of additional free parameters b' for each relation R,, where
[bl| II ((x(dd). dER.
(8)
Consistent with previous notation, define B (vec(B)) ),..., ve pi))). Then an EERL with bias terms is given by
(B*
R; R}. and vec(B)
vec(Y Y) o W vec(X) vec(B)).
The following Claim asserts that can add this bias term without affecting the desired properties of the EERI.
Claim 2. If o (W vec(X)) is an EERL, then a (W veo(X) + vec(B)) an EERL.
The proof (found in Appendix G.1) argues that, since o [W vec(X)) is an EERL, just need to show that G veo(B) veo((B) iff G E ςX which holds due to the tying of patterns in each B
15

---

Under review as a conference paper at ICLR 2020
E SIMPLIFICATIONS FOR MODELS WITHOUT SELF-RELATIONS
In the special case that the multi relations R and Rj are sets -i... 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. EFFICIENT IMPLEMENTATION USING POOLING
Due to the particular structure of W when relations contain only unique entities, the operation W (Xc(X) in the EERL can be implemented using (sum/mean) pooling operations over the tensors X R for E R, without any need for vectorization, or for storing W directly.
XX, () be the summation of the tensor X For X E R NN,,, X...X... and S S R2 let pool
Na; X...xNg, 1/, where R
over the dimensions specified by S. That is, pool(X', () E IR [d'....,,RI1- Then we can write element n' in the i-th block of W W vec(X) as
(W veo vec(
w w pool(X), ,) RyE9t SCR,NR,
Σ
(10)
where n/g is the restriction of n' to only elements indexing entities in R,AS. This formulation lends itself to a practical, efficient implementation where we simply compute each pool(X', S) term and broadcast-add them back into 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 (c.g., in Fig. one PROFESSOR may teach many COURSES, but each COURSE has only PROFESSOR), may further reduce the number of parameters due to redundancies. Suppose R; E R some relation, and entity E R2 is in a one-to- relation with the remaining entities of RR; Consider the ID sub-array of XR, obtained by varying the value of n while holding the remaining values (d) fixed. This sub-array contains just single non-zero entry. According to the tying scheme described in Section 4.1, the parameter block W will contain unique parameter values Wa, and WRA\(d)- Intuitively however, these two parameters capture exactly the same information, since the sub-array obtained by fixing the values of (R,) (d) contains exactly the same data as the sub-array obtained by fixing the values of R, (i.e., the same single value). More concretely, to use the notation of Appendix E.I, we have pool(X', R,) in (10), and
pool(X', R. (dd)))n
i. may tie wR; and (a
In fact, we can reduce the number of free parameters in the case of self-relations (i.e., relations with non-unique entities) well in a similar manner.
E.3 RECURSIVE DEFINITION OF THE WEIGHT MATRIX
We are able to describe the form of the parameter matrix Wid concisely in a recursive fashion, using Kronecker products: For any N E IN, let Iy E RNN be the N x N matrix of all ones, and Iy the N x N identity matrix. Given any set of (unique) entities = {di...., djs/] S {l,.., DJ. for ..... |S], recursively define the sets
w = W & INa, + + INa, W. W )
(11)
with the base case of w/S- R. Then for each block Wio of (4) simply have W W W2,CR,
Writing the blocks of the matrix (4) in this way makes it clear why block W contains 2 n unique parameter values in the case 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. 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.
16

---

Under review as a conference paper at ICLR 2020
Example 3. In the simple case where we have just relation and entity, R = {d} and the parameter matrix is an element of W {w @ 1N, + INa w. E R}. which matches the parameter rying scheme of Zaheer al. (2017). If instead have single re- lation with two distinct entities IR = {d1, d2), then the parameter matrix is an element of wo (W NN2 IN,, W. WR), which matches the rying 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 relational databases. Using multiple input (K) and output (K") channels also possible by replacing the parameter matrix W E I N with the parameter tensor W E R R while K x K' copies have the same parameter-tying pattern -iee. there is parameter-sharing "across" channels. The single-channel matrix-vector product in a (W vec(X)) where (W vec()))n = En' Wn. vec(X) is now replaced with contraction of two tensors (W vec(X))n. Em(Ke(K] Wk.n'' xe vec(X)n: ko for k' [K'].
G
PROOFS
Observe that for any index tuple n, we can express P(n.) (Section 4.1)
((.a) -
= (dies Vk, (dga ndw } dws de) d
(12)
We will make use of this formulation in the proofs below.
G.1 PROOF OF CLAIM
Proof. We want to show that
G Goo(W vec(X) vec(B)) of (WWG* vec(X) + vec(B))
(13)
iff G E G Since a (W voc(X)) is EERL, this is equivalent to showing
vec(B) vec(B)
G C
(14)
(=) Suppose G e G. with kx defined as in Claim 1. Fix some relation R and consider the i-th block of G vec(B):
(G* vec(B)) (K' vec(BB)) n'
(15)
Σ K " vec (3) vec n
(16)
(B*)
(17)
Where G = diag(K), ..., klat),, and n' is the unique index such that K = As above, let
n be the restriction of n' to elements indexing entity d. Then want show that P(n{) P(n
for all d RR; Now, since G Cx and K m
1 we have
Gd
(18)
(M
d E RR and all k. That is / (n na Consider P(n)). we have
S [d(a). d() 1 m'ay nd
(19)
= (d(s)s d(y Vk, ge- (márn)) = g (1d(r))
(20)
= [d(s) dry Vk, /| n = nd
(21)
17

---

Under review as a conference paper at ICLR 2020
So P(nh) _ P(n ) A similar argument has P(n))) 2 P(nn) Thus, have
veo B¹) In vec(B') nt. which completes the first direction.
(=) Let GO (B) vBc First, suppose for the sake of contradiction that G & DRED S.N and consider dividing the rows and columns of G into blocks that correspond to each relation R. Then since G & DRer S.Wa, there exist R2, Rj E R, with + j and n' E [Na;] x x aa
and n'
[44] x x [N 1
such that G maps (i, to (j, n²). That is g ((i, = (j.n')
and thus G
(i,'))( = 1. So
(G* vec((B)) (imm) (Im) = =Σ
GX (..0), (B)(B))),
(22)
n
vec(()(((nt))
(23)
vec(BB) )'
(24)
vec(BB) (B')n'
(25)
by the definition of B. And G vec(B) ( voc(BB).
Next, suppose G DRED S.N Then for all Ri there exist K
8.N such that
G diag(K',.. ,..,,Kla.]] Kla.1). For any n' we have
vec(B') B') n'
(K' vec (B') n
(26)
Σ K n vec (B*)
(27)
vec ( B'))
(28)
Where n is the unique index such that Ki n'n = 1. That is ke maps n" to n'. Then by the definition of B have
((n (P(n)) = =(k(k(n ))a)
(29)
for all d R (29) says that for each d the action of K' elements of n' is determined only by the values of those elements, not by the values of elements indexing other entities, and so K' 8dER, S.Na, But (29) also says that for all k,
n = rdd = (k'(n))) ))m, = (k'(nn)) dey
(30)
which says that the action of K' is the same across any duplications of d (i.e., d(y and d(r)). and so K' = ØdER, Gd, for some fixed Gd, and therefore G e kx
G.2 LEMMA AND PROOF
To prove our main results about the optimality of EERLS we require the following Lemma.
Lemma 1.
For any permutation matrices K' E N and Ki E S.N2 we have
Kiwis = WwiK +
d and K
Gd
Gd NNa
deR.
dER
for constrained W as define above. That is K' and K should separately permute the instances of each entity in the multisets R2 and R applying the same permutation to any duplicated entities, as well as any entities common to both R2 and J.
18

---

Under review as a conference paper at ICLR 2020
To get an intuition for this lemma, consider the special case of i j. In this case, the claim is that W commutes with any permutation matrix that is of the form K' = 2 dER G This gives us the kind of commutativity we desire for EERL, at least for the diagonal blocks of W. Equivalently, commuting with K' means that applying permutation K to the rows of W has the same effect as applying K' the columns of W In the case of o j. ensuring that K' and K' are defined over the same underlying set of permutations, {G" E & | E R. U R ensures that permuting the rows W with K' has the same effect as permuting the columns Wis with K', It is this property that will allow to show that network layer defined using such 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., R. R. and for each d E [D] ler G E 8NN If G
for all
"lgm) x Aie)
d(y) R2 with d(s)) d, and G "n'sgs maa(s)
1 for all d(x) E Ba with daa) d, then for all
doy E RR and dis E B with d(x) daa d, we have n² n'd = vaay = namm n den"
Proof. Suppose G
for all d(w)= [R; and Gd
"'aaay 1aan 1 for all d(s) E R.. We
"a x0 dee)
prove the forward direction (=) The backward direction follows from an identical argument. Fix some d(k) E R. and day E R, and suppose n² n''me
daas maay"" By assumption we have Gd ant
=1
(())
and
A des) naaes)
(31)
Similarly, we have Gd nit (0 ml00
and so
g = ret "''""""
(32)
But n daa nege and substituting into (31) we have
g (maann nadus
(33)
And combining (32) and (33) gives naq,, a'm as desired.
We are now equipped to prove our main claims, starting with Lemma
Proof. (+) Let R {di d and R3 {dd..... d d and fix some (G't E Na d [Ry]
Ri R. U R3J. We index the rows of Wis, and the rows and columns of K with tuples n' n"
[Na]] x ... [Nar Similarly, the columns of Wi.,, and rows and columns of K2, are indexed
with tuples n², n² [N x x (N J. Since K = 2 dER, Gd we have
x(d))
Ki n' . II
Gd S
II dER,
II
Gd
ni "200
deR
And thus,
Ki n'
ed
1, Vdlaa
E Ri s.t. d(x) =
(34)
The same is true for i. That is
K ns
=
+
G
1, vd(a) R s.t. d(.) d.
(35)
19

---

Under review as a conference paper at ICLR 2020
Now, fix some n' and n', Since K' is permutation matrix, and so has only one I per row, we have
(K' n'
Σ
K
Wi
ner
nt'no
n
-Wis
n'* mnh
(36)
where n² is the (unique) element of [Na;] x... x [ which satisfies G
"aw x n = 1 for all
day E & with d(k) d. Similarly,
(Work n'nn
Σ Whs
ms K'
n²
= =Wid
(37)
n'
where nd is the (unique) element of [N x... [N Rgl
which satisfies Gd = 1 for all
duy E Rj with dus) = d.
We want to show that P(n -) P(n))) for all d R; U.. Fix d E R U UR, and let $ ((n Then $ = [d(1), ..., d.)) where d(x) = d for all d(x) ES, and for all d(x) d( E E "dga "d Then by Lemma 2 have iJ
is 'day "d and so S E P(nn") ). So we have P( ) and the other containment follows identically by symmetry. So n n by our definition in Section 4.1, and so w n"
j'J ''J
w n' and by (36) and (37) above,
K'W Wi
Suppose K'WiJ = w Fix some n², n' Let n" be the unique index such that K n'n" = 1, and n' the unique index such that K. nz 1. Then
(-)
W
K .n W
n"
(K')'))
n'.n
(WiJK) ni.n/
Σ
wii
nz mi
n²
w
(38)
n'n
and P(n P(n2"") for all d E R; R. But this implies that
P(n ) P(n))
= (n
(39)
(39) says that for each d the action of K' elements of n' is determined only by the values of those elements, not by the values of elements indexing other entities, and so K' E 2 BERR SNa But (39) also means that for all k
deo"" which says that the action of K is the same across any duplications of d (i.e. d(y and dar)) and so K' = ØdER; Gd, for some fixed Gd, Similarly,
(k'(n") )) den (k'(n")
(40)
((nn) (P(nz))
(41)
= (P (n )d))
(42)
which shows that K = ØdER, Nu', Finally, since P( 1' .) = PP(n (P("""" ), we also have
Bai n
(43)
20

---

Under review as a conference paper at ICLR 2020
for all k,,, which means
doe
ndd - (((nn)) = =(k((n))) Ae)"
(44)
(44) says that K' and K apply the same permutations to all duplications of any entities they have in common, and G G which completes the proof.
G.3 PROOF OF THEOREM 4.1
Proof. Let G E SN and G be defined as in Claim 1. We need to show that G vec(X))
(WG* vec(X)) iff Q G for any assignment of values the
tables x. We prove each direction in turn.
(=) We prove the contrapositive, Suppose G & G We first show that G that G GW vec(X)) * (WG vec(X)) for an appropriate choice of X. There are three cases. First, suppose G + RRE 8N and consider dividing the rows and columns of G* into blocks that correspond to the blocks of W. Then since
W o WG and then
G &f DRED SNN there exist R2, R3 E R, with such that GO maps (i, n') to
i * and n' E [Na;) x
[N [R.
and n'
[N&e] X... x (Nat d/s,1
().m))((mm)) = 1. And so (j, n²). That is g²x ((i, n²)) = (j, n and thus, G
(G* W) (i.)))
-EΣ G (.a)), W (k.a))((im))
W n',n"
by the definition of W. Similarly,
(WG*) (j.n))(inn))
>>>
W (R..). G G (ka)))
WWi. n'mi
n' But W * W..
n'mn ns since j. And so G W + X
Next, suppose G E DREN Nu, but GZ & DREm ØdeR SNa and consider the diagonal blocks of G* that correspond to those of W. If x E DRE S. then is block diagonal with blocks corresponding to each E At But since G & Daco 2dER S.Na, there exists some R; E R such that the th diagonal block of G is not of the form X DER, Gd for any G Then by Lemma I we will have inequality between GWWG>" and W in the 7th diagonal block.
Finally, suppose G E RER 8 dER NN Then G = K $... @ KPA where K x HER 8Na
for all i. Since x of Gx there exist Ry R2 E R. possibly with i j. and a d' E R, n Ry such that
K' G @ G @ G G mdl
and
K' G .... & To @
G G
but Go + Goo, Since G f Gd there exists n E [Na-] with d (m) * y gio (n). Pick some n' and n' with n = ntz- = n. Let n" be the result of applying K to n' and n²" the result of applying KS to n'. Then we have
(G (G*W) (i.m"))(i.m))
= ΣΣ G Caa () W ((in)))
Σ n
Ki n W nt
W
(45)
n' m
21

---

Under review as a conference paper at ICLR 2020
and
(WG*) (i.""))(i = ΣΣ
((.n"")((ka" G (kat).
n²
Σ Why n
K
n" .nt
na n
W n ..
(46)
Now, by construction we have n²g- = ny-, but n' + n So P(n))) + P(n ( and therefore n'an/ o Whd nn'"."/-. And so by (45) and (46) we have Go + WG*.
Whi
And so in all three cases G o WG Thus, there exists some X, for which we have G vee(X) * WG vee(X). Since is strictly monotonic, we have a (G*W vec(X)) # (WG* vec(X)). And since is element wise we have Go vec(X)) & a (WG veo(X)), which proves the first direction.
(=) Suppose GO E G That is, for all [D], let Gd E S: be some fixed permuta- tion of Na objects and let G Quem ORER Gd. Observe that G is block-diagonal. Each block on the diagonal corresponds an R E R and is Kronecker product over the matrices G" for each d E R. Let K' = =x DERR, dER, Gd for each i E [[]]] That is,
K
K2
G
O
K
And so the i, j-t block of Gx WG*T is given by:
(CXWa*T) is
K'
(47)
The equality at (47) follows from Lemma 1. Thus, we have G WG and so for all X. G W vec(X) WG vec(X). Finally, since a is applied element-wise, we have
o(WG* vec(X)) = = W vec(X))
= -G*ooV W vec(X))
Which proves the second direction. And so o ( vec(X)) is an exchangeable relation layer, complet- ing 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 Wir containing two elements whose indices have the same equality pattern, but whose values different. Based these indices, we can explicitly construct permutation which swaps the corresponding elements of these indices. This permutation is in G but does not commute with W. Now we present a detailed proof.
[N be the set of indices into XR. If W is not of the form described in Section 4 then there exist i,j [[9]]] with n', n' NR: and n², n² e NP, such that
Proof. Let O E SNN For any relation R = (di, ..., d } E R, let N [Na,] x
w n'
+ W n' nor
(48)
mi
but
p(n))) (( Ad AdER, R,R
(49)
22

---

Under review as a conference paper at ICLR 2020
That is, the pairs n', n' and n",, n have the same equality pattern over their elements, but the entries of W which correspond to these pairs have differing values, and thus violate the definition of W in Section 4, To show that the layer o vec(X)) is not an EERL, will demonstrate permutation G E G for which G W o WG* and thus G x of (W vec(X)) * a (WG* veo(X)) for some X.
Let G DREst deR GO with the Gd defined as follows. For d E I2; n R2 and all k:
n' de:
Bags n' dik) (dds)) n
ni d(
(m)n==
n
= ni dey)
otherwise
For d E R,A, and all k:
n² den
n1 = ma
Gm
n'dw))
n = n' day otherwise
For d E Rý\RR, and all k:
n²' de
n1 Te das
(n)
na 7
n = ne' dey) otherwise
And for d & BR RRy
G (n)
That is, each Gd swaps the elements of n' with the corresponding elements of n",, and the elements of n² with those of n'', so long as the relevant indices are present. For the case where E R; R,,, we need to make sure that this is a valid permutation. Specifically, we need to make sure that is injective (it is clearly surjective from [Na] to [Na]). But it is indeed injective, since have nddn = =ndge iff n i'
du: n daa) for all d E R; O RR, and all k; since P(n (.5) = P(n 555))
Now, for all i, let K' = =ddER, Gd be the 7hh diagonal block of x By definition of the Gd, for all d E R. we have Gd
ni.nt' 1, and thus by the observation at (34) we have K n'.""" = 1. And so
(G W) (i.n). = ΣΣ
G ( W (k.,")))
n Σ
Ki nin
Wii ms
n
Wii
n² m/
Similarly, KJ
n. An 1, so
(WG*)
ΣΣ
W ((lm"))(kk GX (let)..
nt
Σ
wis
KJ
ma
n79
n'n'
Finally, by (48), G o WG completing the proof.
23

---

Under review as a conference paper at ICLR 2020
H DETAILS OF EXPERIMENTS
The synthetic data we constructed used 200 instances for each of the three entities. Unless otherwise noted, we considered 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 EERLs, each with 64 hidden units, each followed by batch normalization (Ioffe & Szegedy, 2015) layer and 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 applied. In all experiments we used the Adam (Kingma & Ba, 2014 4) optimizer with initial learning rate 0.0001 to optimize 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.
H.1 EMBEDDING
We ran this experiment for 5000 epochs, and used an encoding size of 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.
H.2 MISSING RECORD PREDICTION
We held out 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 90%/10% vraining/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 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 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.
H.3 PREDICTIVE VALUE OF SIDE INFORMATION
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, We use 80%/10%/100 100% training/validatiooneess split and trained for 8000 epochs, producing an embedding of size 10. We repeat this experiment 17 times and average the results.
H.4 PREDICTIONS ON THE SOCCER DATABASE
The dataset is available at https: / www. kaggle. wtt.cc/c.cco..eeec homm/hugomtthi inroomathieiiii hntugomathien//occcee. soccer. We con- structed 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 aggre- gate the entries by averaging numerical features, and taking the most common value for categorical ones. We also include additional binary feature indicating which team is home and which is away.
24

---

Under review as a conference paper at ICLR 2020
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 player described above. Again, also include a binary feature indicating whether player played for the home or away team.
Saariu_Atributes table, aggregating entries for each
We model built from five EERLs. All but the last one have 52 units (this is based the limitation of our GPU memory), use ReLU activations, and are followed by a batch normalization layer (Toffe & Szegedy, 2015) and channel-dropout. Chennel-dropout zeros whole channels at random for all entries of all tables, at rate of 50%. The final EERL uses no activation and 8 output units. This followed by layer which sum-pools both tables into single feature vector for each match. Finally, a linear layer produces 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 90% 10% training/test split.
25


Reviews:
[{"review_id": "rJe4Mpt25H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a parameter tying scheme to express permutation equivariance in entity-relationship networks that are ubiquitous in relational databases. Results on the generality of the tying scheme are presented, as well as some experimental validation.\n\nThe paper extends several previously-proposed lines of work in statistical relational learning, including the work of Hartford et al. (2018) to multiple relations. In contrast to this earlier paper, which builds its argument step by step with great clarity (helped by illustrations), the current paper would prove hard to read to an ICLR audience, since most of its language and methods borrow more from the database theory literature. Since the proposed tying scheme is quite close to that of Hartford et al. (2018), one way to present the paper could be to construct the argument in such a way as to emphasize the difference with the previously-proposed scheme, thereby far better outlining the current contribution.\n\nIn addition, the experimental validation leaves much to be desired. In the synthetic data experiments (e.g. Figure 3), there is no guidance as to how to judge the quality of the resulting embedding. Also, it would be helpful to contrast the performance of the proposed approach against alternatives on a wider variety of datasets, such as MovieLens, Flixster, Netflix. (See the methodology followed by Hartford et al., 2018).\n\nAll in all, even though the proposed approach could usefully extend the state of the literature, the paper in its current form would need additional work before recommending acceptance at ICLR.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HJx6sQe5qS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThis 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.\n\nThe experiments are somewhat rudimentary, but they are perfectly adequate for a paper whose contribution is primarily methodological and theoretical.\n\nOne 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.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "HJx3fjF_cr", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes Equivariant Entity-Relationship Networks, the class of parameter-sharing neural networks derived from the entity-relationship model.\n\nStrengths of the paper:\n1. The paper is well-written and well-structured.\n2. Representative examples, e.g., the Entity-Relationship diagram in Figure 1, are used to demonstrate the proposed algorithms.\n3. Detailed proofs for some equations are provided for better understanding the proposed equivariant entity-relationship networks.\n\nWeaknesses of the papers:\n1. No effective baselines are used for comparisons in the experiments. Are there state-of-the-art algorithms that have been proposed by other researchers to be used as baselines in the experiments?\n2. No effective real-world datasets are used in the experiments. The authors only take synthesized toy dataset in their experiments. Are there other real-world datasets to be used in the experiments?\n3. In terms of missing record prediction, why do the authors embed, e.g., the COURSE, in this way but not the other ways? What are the motivations of embedding like this? Are there other embedding techniques, e.g., Matrix Factorization and Skip-gram frameworks like that in Word2VEC, can be used for your purposes?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "Bye-OJY_cH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors extend recent work in equivariant set encoding to the setting of entity-relation data.  Similar to the cited previous work, they encode sets of objects (in this case the tuples of a relational database) with a permutation invariant function. They use a parameter tieing scheme to enforce this invariance.\n\nI don’t find the paper to be particularly well motivated. Relational DBs are not necessarily a setting where you would always want equivariance. While the ordering of tuples do not matter, relations are often asymmetrical. Further, the idea of concatenating all tuples of a relational DB to be passed through a particular feed forward layer is infeasible for all but the smallest datasets. Real world databases such as knowledge bases contains millions to billions of entries. Scaling issues aside, the experiments do not actually show that this method outperforms any reasonable baselines such as a simple tensor factorization. \n\nI also found it particularly hard to follow the descriptions of the methods. A few specific points:\n- The text and notation in the beginning of section 2 could be a lot clearer. I had to read these paragraphs multiple times to pick out precisely what you were trying to say. Maybe have the set of relations be [R] like your other sets rather than a different script R. \n- In the next paragraph you say “A particular relation R is a multiset if it contains multiple copies of the same entity” but you previously defined R to be a set of instances and not entities. I think you need to be more consistent with your terminology since the differences between type level entities and instances is important for your definitions and as you noted in your first footnote, these terms are often used very differently.\n- This explanation could be helped a lot by improving the figure. The caption and images are both very dense but still requires a lot of coreference. For example, labeling the entities and relations with their ids in figure 1a directly would make it much easier to mentally map to what you are explaining in the caption. Also figure 1c is not at all clear.\n\nLastly, the methodology seems quite incremental over the previous work. A lot of the context and background that was sent to the appendix should be included in the main paper, particularly the relation to related work\n\n\nedits:\ndouble ‘the’ in abstract “linear complexity in the the data “", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkxqhAyTKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper handles the permutation invariance of the entity-relationship data entries by tying the weights of linear parameterization together. Heavy math was used to describe the proposed idea, and experiments were performed on simple problems.\n\nThe main idea of the paper seems to be equation (3) and the associated method of tying weights in the linear layer. This is actually quite simple, and does not require the numerous complicated definitions in section 2 and 3 to reach the same conclusion. Using math is good, but using more than necessary simply slows down the dissemination of ideas.\n\nIn both theory and experiment, the paper does not demonstrate the advantage of the weight tying method compared to an untied baseline. This weakens its necessity and motivation.\n\nThis paper also has very weak relationship with deep neural networks, while the word 'deep learning' was mentioned in both introduction and conclusion.\n\nIn general, it is a weakly motivated and math-excessive paper. Based on these considerations, I recommend rejection.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper defines a parameter-tying scheme for a general feed-forward network with the equivalence properties of relational data. Most reviewers raised a few concerns around the experiments, baselines, datasets used and motivation. A few pointed out that the paper is hard to read - for a person without heavy database theory literature, which includes most of ICLR readers. While this paper may read well for the folks in the domain, authors should consider revising the paper to be more inclusive so that it can be read more widely. The motivation of the problem was also another point that many reviewers have mentioned (perhaps related to the language issues above) that some noted that you may not always want equivariance in relational DB and other noted that the paper did not sufficiently demonstrate the advantage of the proposed methods. Reviewers also univocally commented on experiments - many voiced the lack of baselines (not even any simple one). Authors wrote back to defend that there is no similar method and even simple tensor factorization isn’t applicable. That makes me wonder - is there really no single simple method you can compare with? If nobody had solution for this problem, is this a problem worth solving? Reviewers also encouraged to use larger (beyond Kaggle dataset) real-world datasets to strengthen the paper. All the points raised by reviewers suggests that this paper can benefit from another round of nontrivial editing before it’s ready for the show.

Decision: Reject