Learning Hierarchical Relational Representations through Relational Convolutions
Authors: Awni Altabaa
John Lafferty
Venue: Accepted by TMLR ()

Abstract: An evolving area of research in deep learning is the study of architectures and inductive biases that support the learning of relational feature representations. In this paper, we address the challenge of learning representations of hierarchical relations—that is, higher-order relational patterns among groups of objects. We introduce “relational convolutional networks”, a neural architecture equipped with computational mechanisms that capture progressively more complex relational features through the composition of simple modules. A key component of this framework is a novel operation that captures relational patterns in groups of objects by convolving graphlet filters—learnable templates of relational patterns—against subsets of the input. Composing relational convolutions gives rise to a deep architecture that learns representations of higher-order, hierarchical relations. We present the motivation and details of the architecture, together with a set of experiments to demonstrate how relational convolutional networks can provide an effective framework for modeling relational tasks that have hierarchical structure.

Published in Transactions on Machine Learning Research (09/2024)
Learning Hierarchical Relational Representations through Relational Convolutions
Awni Altabaa
aumi.altabna@yale.cck
Deportment of Statistics & Data Science
Yale University
John Lafferty
john. Sohn.lafferty@@aalle edu
Department of Statistics & Data Science, Wu. Tsai Institue
Yale University
Reviewed on OpenReview: https: // openreview. net/ formm? id= id=uNZtnanm12
Abstract
An evolving of research in deep learning is the study of architectures and inductive biases that support the learning of relational feature representations. In this paper, we address the challenge of learning representations of hierarchical relations-that is, higher-order relational patterns among groups of objects. We introduce "relational convolutional networks", a neural architecture equipped with computational mechanisms that capture progressively more complex relational features through the composition of simple modules. A key component of this framework is a novel operation that captures relational patterns groups of objects by convolving graphlet filters letess-learabble templates of relational patterns agaanstt subsets of the input. Composing relational convolutions gives rise to deep architecture that learns representations of higher-order, hierarchical relations. We present the motivation and details of the architecture, together with set of experiments to demonstrate how relational convolutional networks can provide an effective framework for modcling relational tasks that have hierarchical structure.
1 Introduction
Objects in the real world rarely exist in isolation; modeling the relationships between them is essential to accurately capturing complex systems. As increasingly powerful machine learning models advance towards building internal "world models," it becomes crucial to explore natural inductive biases to enable efficient learning of relational representations. The computational challenge lics in developing the components required to construct robust, flexible, and progressively more complex relational representations.
An important component of relational cognitive processing in humans is ability to reason about higher-order relational patterns between groups of objects. To illustrate this, it is instructive to consider experimental tasks from the cognitive psychology literature that probe abstract relational reasoning ability. Consider, for example, the task depicted to the right in Figure 1 which is a variant of a relational "match-to-sample"" task (Ferster, 1960; Webb al., 2021). The subject is presented with a source triplet of objects and several target triplets, with each triplet having particular relational pattern. The task is to match the source to target triplet with the same relational pattern (in this case, the source has an "ABA" pattern that matches the second target). This lask requires going beyond reasoning about pairwise relations: the subject must reason about each triplet of objects as a group, determine its relational pattern, then compare it those of the target triplcts, inferring the abstract rule the process. The ability to infer generalizable abstract rules in such tasks is believed to be unique to humans (Fagot et al., 2001).
1
2
3
variant a relational match-to-sample
Figure
task.

---

Published in Transactions on Machine Learning Research (09/2024)
Compositionality used here to mean ability to compose modules together to build iteratively more complex feature representations is essential to the success of deep representation learning. For example, in the domain of visual processing, CNNs are able to extract higher-level features (e.g,, textures and object-specific features) by composing simpler feature maps (Zeiler and Fergus, 2014), resulting in a flexible architecture for computing "features of features". In contrast, existing work on relational representation learning has primarily been limited to "shallow" first-order architectures (e.g., only explicitly capturing pairwise relations).
In this work, we propose relational convolutional networks as a compositional framework for learning hierarchical relational representations. The key to the framework involves formalizing the concept of convolving learnable templates of relational pattern against larger relation tensor. This operation produces sequence of vectors representing the relational pattern within each group of objects. Crucially, composing relational convolutions captures higher-order relational features-is i.e., relations between relations. Specifically, our proposed architecture introduces the following concepts and computational mechanisms.
Graphlet filters. A "graphlet filter" a template for the pattern of relations ween a (small) collection of objects. Since pairwise relations can be viewed as edges on graph, the term "graphlet" used to refer to a subgraph, and the term "filter" is used refer to learnable template or pattern.
Relational convolutions. We formalize notion of relational convolution, analogous to spatial convolutions in CNNs, where a graphlet filter is matched against the relations within groups of objects to obtain a representation of the relational pattern in different groupings of the input.
Grouping mechanisms. For large problem instances, considering relational convolutions across all object combinations would be intractable. To achieve scalability, we introduce a Icarnable grouping mechanism based on attention which identifies the relevant groups that should be considered for the downstream task.
Compositional relational modules. The proposed architecture supports composable modules, where each module has learnable graphlet filters and groups. This enables learning higher-order relationships between jijects-relations between relations.
The components of the architecture are presented in detail in Sections 2 and 3, and a schematic of the proposed architecture is shown in Figure 2. Tn a series of experiments, we show how relational convolutional networks provide a powerful framework for relational learning. We first carry out experiments on the "relational games" benchmark for relational reasoning proposed by Shanahan et al. (2020), which consists of a suite of binary classification tasks for identifying abstract relational rules between a set of geometric objects represented images. We next carry out experiments on version of the Set card game, which requires processing of higher-order relations across multiple attributes. We find that relational convolutional networks outperform Transformers, graph neural networks, and existing relational architectures. These results demonstrate that both compositionality and relational inductive biases are essential for efficiently learning representations of complex higher-order relations.
1.1
Related Work
To place framework in the context of previous work, we briefly discuss related forms of relational Icarning below, pointing first to the review of relational learning inductive biases by Baltaglia et al. (2018).
Graph neural networks (GNNs) are a class of neural network architectures which operate on graphs and process "relational" data (e.g., Niepert et al., 2016; Kipf and Welling, 2017; Schlichtkrull et al., 2018; Veličković et al., 2018; Kipf et al., 2018; Xu et al., 2019). A defining feature of GNN models is their use of a form of neural message-passingg
wherein the hidden representation of a node updated as a function of the hidden representations of its neighbors on a graph (Gilmer et al., 2017). Typical examples of tasks that GNNs are applied to include node classification, graph classification, and link prediction (Hamilton, 2020).
In GNNs, the 'relations' are given to the model as input via edges in graph. In contrast, our architecture, as well as the relational architectures described below, operate on collections of objects without any relations given as input. Instead, such relational architectures must infer the relevant relations from the objects themselves. Still, graph neural networks can be applied to these relational tasks by passing in the collection of objects along with a complete graph.
2

---

Published in Transactions on Machine Learning Research (09/2024)
Several works have proposed architectures with the ability to model relations by incorporating an atten- tion mechanism (e.g., Vaswani et al., 2017; Veličković et al., 2018; Santoro et al., 2018; Zambaldi et al.,
(z Rng E R
Ruixd
Relational Convolution
2018; Locatello et al., 2020). Attention mechanisms, such as self-attention in Transformers (Vaswani et al., 2017), model relations between objects implicitly intermediate step in an information-retriewe operation to update the representation of each object as function of its context.
R(1-1) IR 1
Inner Product Relation
(2) (2 p 222 E IR xd;
There also exists growing literature on neural ar- chitectures that aim to explicitly model relational information between objects. An early example is the
Relational Convolution
R(1) E m.xnxr
relation network proposed by Santoro et al. (2017), which produces an embodding representation for a
Inner Product Relation
set of objects based on aggregated pairwise rela- tions. Shanahan et al. (2020) proposes the PrediNet architecture, which aims to learn relational repre- sentations that are compatible with predicate logic. Kerg et al. (2022) proposes CoRelNet, a simple ar- chitecture based on 'similarity scores' that aims to distill the relational inductive biases discovered in previous work into a minimal architecture. Altabaa et al. (2024) and Altabaa and Lafferty (2024b) ex- plore relational inductive biases in the context of Transformers, and propose view of relational in- ductive biases as a type of selective "information bottlencck" which disentangles relational informa- tion from object-level features. Webb et al. (2024) provides a cognitive science perspective on this idea, arguing that a relational information bottleneck may be a mechanism for abstraction in the human mind.
(2 ,4.),..,,, 2n E Raxd
Initial Emhedder
(X X,.) E EX"
Figure 2: Proposed architecture for renational convo- lutional networks. Hierarchical relations are modeled by itcratively computing pairwise relations between objects and convolving the resultant relation tensor with graphlet filters representing templates of relations between groups of objects.
2 Multi-Dimensional Inner Product Relation Module
A relation function maps a pair of objects v, y X' to vector that represents the relationship between them. For example, relation may represent comparisons along different attributes of the two objects, such "x has the same color as y, is larger than y, and x is to the left of y". In principle, this can be modeled by an arbitrary learnable function on the concatenation of the two objects' feature representations. For example, Santoro et al. (2017) use multilayer perceptrons (MLPs) to model relations by processing the concatenated feature vectors of object pairs. However, this approach lacks crucial inductive biases. While it is theoretically capable of modeling relations, it imposes no constraints to ensure that the learned pairwise function reflects meaningful relational patterns. In particular, entangles the feature representations of the two objects without explicitly comparing their features.
Following previous work (e.g., Vaswani et al., 2017; Webb et al., 2021; Kerg et al., 2022; Altabaa al., 2024), we propose modeling pairwise relations between objects via inner products of feature maps. This introduces added structure to the pairwise function that explicitly incorporates comparison operation (the inner product). The advantage of this approach is that it provides added pressure to learn explicitly relational representations, disentangling relational information from attributes of individual objects, and inducing a geometry on the object space X. For example, in the symmetric case, the inner product relation r(z, v) = (δ(z), Φ(y) satisfics symmetry, positive definiteness, and induces a pscudometric on X. The triangle inequality of the pseudometric expresses a transitivity property- if x is related to y and y is related to 2, then æ must be related to
More generally, we can allow for multi-dimensionall relations by having multiple encoding functions, each extracting feature to compute relation on. Furthermore, we can allow for asymmetric relations by having
3

---

Published in Transactions on Machine Learning Research (09/2024)
different encoding functions for each object. Hence, we model relations by
r(z. v) (x)1(x), 1/1 (v)). ..... (oa, (1), (v)))
(1)
where Φ1: (i,-...,dd, th, are learnable functions. The intuition is that, for each dimension, the encoders extract, or 'filter' out, particular attributes of the objects and the inner products compute similarity across each attribute. A relation, in this sense, is similarity across a particular attribule. In the asymmelric case, the attributes extracted from the two objects are different, resulting in an asymmetric relation where one attribute of the first object is compared with different attribute of the sccond object. For example, this can model relations of the form "x is brighter than v² (an antisymmetric relation).
Altabaa and Lafferty (2024a) analyzes the function approximation properties of neural relation functions of the form of Equation (1). In particular, the function class of inner products of neural networks is characterized in both the symmetric case and the asymmetric case. In the symmetric case (i.e., Φ = v), it is shown that inner products of MLPs are universal approximators for symmetric positive definite kernels. In the asymmetric case, inner products of MLPs are universal approximators for continuous bivariate functions. The efficiency of approximation is characterized in terms of a bound on the number of neurons needed to achieve a particular approximation error.
To promote weight sharing, we can have one common non-linear map & shared across all dimensions together with different linear projections for each dimension of the relation. That is, r: X' x X - Rd is given by
r(z,v) (< (WFo(z), W ((v))(()))))))))))) ke[d.]'
where the learnable parameters are and Wf, W k [d.]] The non-linear map o X Rd may be an MLP, for example, and W W are dproj de matrices. The class of functions realizable by Equation (2) is the same as Equation (1) but enables greater weight sharing.
The "Multi-dimensional Inner Product Relation" (MD-IPR) module receives a sequence of objects (z1, Tn) as input and models the pairwise relations between them by Equation (2), returning an n x n x dp relation tensor, J = r(z,, 22), describing the relations between each pair of objects.
3
Relational Convolutions with Graphlet Filters
3.1
Relational Convolutions with Discrete Groups
In this section, we formalize a relational convolution operation which processes pairwise relations between objects to produce representations of the relational patterns within groups of objects. Suppose that we have a sequence of objects (Ii,..., and a relation tensor R describing the pairwise relations between them, obtained by MD-IPR layer via R] r));;,))) The key idea is to learn template of relations between a small set of objects, and to "convolve" the template with the relation lensor, matching it against the relational patterns in different groups of objects. This transforms the relation tensor into sequence of vectors, each summarizing the relational pattern in some group of objects. Crucially, this can now be composed with another relational layer to compute higher-order relations- iee., relations on relations.
Fix some filter size s << n, where s hyperparameter of the relational convolutton layer. One 'filter' of size is given by the graphlet filter E Rexexd, This is template for the pairwise relations between a group of objects. Since pairwise relations can be viewed as edges on graph, use the term "graphlet filter" to refer to a template of pairwise relations between a small set of objects. Let g c [m] be group of objects among (ZI,...,,,) Then, denote the relation sub-tensor associated with this group by R[g] := [A[i.jjkkee We define the 'relational inner product' between this relation subtensor and the filter fi by
[R[g], fixrel = Σ> Σ Ai..
(3)
1 ke|d]
This is simply the standard inner product in the corresponding Euclidean space Rdd This quantity represents how much the relational pattern in g matches the template ft.
In a relational convolution layer, we learn ny different filters. Denote the collection of filters by f (Jı,..., Say) Rexexd,xxy which we call graphlet filter. We define the relational inner product of relation
4

---

Published in Transactions on Machine Learning Research (09/2024)
graphlet filters f E R R
(re)
r-r)rel
(chrel
relation subtensors R[gl.g E g
R
Z1
Z2
Zng
Figure 3: A depiction of the relational convolution operation. A graphlet filter f is compared to the relation subtensor in each group of objects, producing sequence of vectors summarizing the relational pattern within each group. The groups can be differentiably learned through an attention mechanism.
subtensor R[g] with the graphlet filters f as the ny-dimensional vector consisting of the relational inner products with each individual filter,
(1]g),Sirre)
(R(g), Dree
R
(4)
(R[g). fny)ro)) >
This vector summarizes various aspects of the relational pattern within a group, captured by several different filters!. Each filter corresponds to one dimension. This is reminiscent of convolutional neural networks, where each filter gives us one channel in the output tensor.
For given group = [n], the relational inner product with graphlet filter, (R[g), fr gives us vector summarizing the relational patterns inside that group. Let G be a set of groupings of the n objects, each of size s. The relational convolution between a relation tensor R and a relational graphlet filter f is defined as the sequence of relational inner products with each group in G
R * = ((R[g),
Dreal Drg gFg = (ZI,.... Zig) Z(g)) E IR gllixny
In this section, we assumed that G was given. If some prior information is known about what groupings are relevant, this can be encoded in G. Otherwise, if n is small, & can be all possible combinations of size s. However, when n is large, considering all combinations will be intractable. the next subsection, we consider the problem of differentiably leorning the relevant groups.
3.2 Relational Convolutions with Group Attention
In the above formulation, the groups are 'discrete:. Having discrete groups can be desirable for interpretability if the relevant groupings are known priori or if considering every possible grouping is computationally and statistically feasible. However, if the relevant groupings are not known, then considering all possible combinations results in a rapid growth of the number of objects at cach layer.
In order to address these issues, we can explicitly model and learn the relevant groups. This allows us control the number of objects the output sequence of a relational convolution such that only relevant. groups are considered. We propose modeling groups via an allention operation.
We have overloaded the notation <, <r) but will use the convention that collection of filters denated by a bold symbol (e.g., fi) to distinguish between forms of the relational inner product.
5

---

Published in Transactions on Machine Learning Research (09/2024)
Consider the input (21,...,, 2, E R Let ng be the number of groups to be learned and be the size of the graphlet filter (and hence the size of each group). These are hyperparameters of the model that we control. For each group 9 E [ng]] we learn s different queries, {q Igefnyleee that will be used to retrieve a group of size s via attention. The i-th object in the k-th group is retrieved as follows,
g E [m,], [+],
(6)
exp (3 (9. key(z;)))
0
g [ng] i [s],] [n]
k=1 exp (g key (xx)))
where xy is the i-th object retrieved in the g-th group, of is the query for retrieving the i-th object in the g-th group, key(z,) the key associated with the object zy, and | a temperature scaling parameter.
The key for each object is computed as function of its position, features, and/or context. For example, to group objects based on their position, the key can be a positional embedding, key(2;) PE. To group based on features, the key can be linear projection of the object's feature vector, key( Wa To group based on both position and features, the key can be sum or concatenation of the above. Finally, computing keys after a self-attention operation allows objects to be grouped based on the context in which they occur.
The relation subtensor R[y] E Rexaxx- for each group g E [ng]] is computed using a shared MD-IPR layer r(s-),
Rigl [r(*). + [
(7)
The relational convolution is computed before via, R a f = (<R[g). f),m)) gF[mg]
(8)
Overall, relational convolution with group attention can be summarized as follows: 1) learn ng groupings of objects, retrieving objects per group; 2) compute the relation tensor of each group using an MD-IPR
module; 3) compute relational convolution with learned set of graphlet filters f, producing sequence of ng vectors each describing the relational pattern within a (learned) group of objects.
Computing input-dependent queries. In the simplest case, the query vectors are simply learned parameters of the model, representing a fixed criterion for selecting the ng groups. The queries can also be produced an input-dependent manner. There are many ways to do this. For example, the input. (zi,..., can be processed with some sequence or set embedder (e.g., through self-attention operation) producing vector embedding that can be mapped to diffcrent queries {g]),, lig using learned linear maps.
Entropy regularization. Intuitively, we would ideally like the group attention scores in Equation (6) to be close to discrete assignments. To encourage the model to learn more structured group assignments, we add an entropy regularization to the loss function, Lentr = (ny s)- Eg ((a where H(a = - Σ, ag log(ag)) is the Shannon entropy. As a heuristic, this regularization can be scaled by a factor proportional to log(n_classes)) claasee))/oo(()) so that doesn't dominate the underlying task's loss. Sparsity regularization neural attention has been explored in several previous works, including through entropy regularization (e.g., Niculae and Blondel, 2017; Martins et al., 2020; Attanasio et al., 2022).
Symmetric relational inner products. So far, we considered ordered groups. That is, the relational pattern computed by the relational inner product [) for the group (1, 2,3) is different from the group (2,3,1) 1). In some scenarios, symmetry in the representation of the relational pattern a useful inductive bias. To capture this, we define a symmetric variant of the relational inner product that is invariant to the ordering of the elements in the group. This can be done by pooling over all permutations the group. In particular, we suggest max-pooling or average- average-poolingg pooling, although any sel-aggregator would be valid. We define the permutation innnutttaioo-ivvriantt
invariant relational inner product
(R[g], f) Deelsym= == Pool ((<Rgg)) : g' g!]),
where g! denotes the set of permutations of the group g, and pooling done independently across dimensions.
6

---

Published in Transactions on Machine Learning Research (09/2024)
Computational efficiency. Equation (6) can be computed in parallel with O(n ny- s- d) operations. When the hyperparameters of the model are fixed, this is linear in the sequence length n. Equation (7) can be computed in parallel via efficient matrix multiplication with (ng sdn dproo) operations. Finally, Equation (8) can be computed in parallel with Ong s² d, n2)) operations. The latter two computations do not scale with the number of objects in the input, and are only a function of the hyperparameters of the model.
3.3 Deep Relational Architectures by Composing Relational Convolutions
A relational convolution block (including a MD-IPR module) is a simple neural module that can be composed to build deep architecture for learning iteratively more complex relational feature representations.
Following the notation in Figure 2, let ne denote the mumber of objects and de the object dimension at layer f. A relational convolution block receives as input a sequence of objects of shape ne de and returns a sequence of objects of shape ne+1 x d representing the relational patterns among groupings of objects. The output dimension de+1 corresponds to the number of graphlet filters ny, and is a hyperparameler. The sequence length 74-1 corresponds to the number of groups, and is |g] in the case of given discrete groups (Section 3.1) or a hyperparameter ny in the case of learned groups via group attention (Section 3.2). Each composition of relational convolution block computes relational features of one degree higher (i.e., relations between relations).
A common recipe for building modern deep learning architectures is by using residual connections (He et al., 2016) and normalization (Ba et al., 2016). This can be achieved for relational convolutional networks by fixing the number of groups Mg and number of filters ny hyperparameters to be the same across all layers, such that the input shape and output shape remain the same. Then, letting H₃ denote the hidden representation at layer E, the overall architecture becomes H4+1 = Norm(Hz + W Rel:Roeo linear transformation that controls where information written to in the residual stream. This ResNet-style architecture allows for the hidden representation to encode relational information at multiple layers of hierarchy, retaining the information al shallower layers. Additionally, we can insert. MLP layers to process the relational representations before the next relational convolution layer. In this paper, limit our exploration to relatively shallow networks of the form He+1 = RelConvBlocke (H,..
where We+1 is a
4 Experiments
In this section, we empirically evaluate the proposed relational convolutional network architecture (abbreviated RelConvNet) to assess its effectiveness at learning relational tasks. We compare this architect ure to several existing relational architectures as well as general-purpose sequence models. The common input to all models is a sequence of objects X (Z1,..., e Raxd We evaluate against the following baselines.
Transformer (Vaswani et al., 2017). The Transformer is powerful general-purpose sequence model. It consists of alternating self-attention and multi-layer perceptron blocks. Self-attention performs an information retrieval operation, which updates the internal representation of each object as a function of its context. Dot product attention is computed via X' + and the MLP is applied independently on each object's internal representation. The attention scores computed as an intermediate step in dot-product attention can perhaps be thought of as relations that determine what information to retrieve.
PrediNet (Shanahan et al., 2020). The PrediNet architecture is an explicitly relational architecture inspired by predicate logic. At a high-level, the PrediNet architecture computes j relations between k pairs of objects. The & pairs of objects are selected via learned attention operation. The "j relations" refer to difference between j-dimensional embeddings of the selected objects. More precisely, for each head h E [k], a pair of objects E E E Rd is retrieved via an attention operation, and the final output of PrediNet is a set of difference relations given by D* = E/W, - E.W,, WWW.WWWW
CoRelNet (Kerg et al., 2022). The CoRelNet architecture is proposed as a minimal relational architecture distilling the core inductive biases that the authors argue are important for relational tasks. The CoReINet module simply computes inner products between object representations and applies Softmax normalization, returning an n n "similarity matrix". That is, the objects x (Z1,-..,, Up) are processed independently to produce embeddings 7 (21,-..; En), and the
7

---

Published in Transactions on Machine Learning Research (09/2024)
similarity matrix is computed as R = (oftmax(ZZT)) The similarity matrix R is then flattened and passed through an MLP to produce the final outpui.
Graph Neural Networks. Graph neural networks are class of neural network architectures which operate on graphs-structured data. A graph neural network typically receives two inputs: a graph described by a set of edges, and feature vectors for each node in the graph. GNNs can be described through the unifying framework of neural message-
Under this framework, graph-structured data is processed through an iterative message-passing operation given by ((4+1) Update(A) (1) (1))) )))) where 11!0) - z;. That is, each node's internal representation is iteratively updated as a function of its neighborhood. Here, Update is parameterized by a neural network, and the variation between different GNN architectures lies in the architectural design of this update process. We use Graph Convolution Networks (Kipf and Welling, 2017), Graph Attention Networks (Veličkovié et al., 2018), and Graph Isomorphism Networks (Xu et al., 2019) as representative GNN baselines.
CNN. As a non-relational baseline, we lest a regular convolutional neural network which processes the raw image imput. The central modules in the baselines above receive an object-centric representation as input. That is, a sequence of vector embeddings produced by a small CNN each corresponding to one of the n objects in the input. Here, instead, a deeper CNN model processes the raw image input representing the entire "scene" in an end-to-end manner.
4.1 Relational Games
The relational games dataset was contributed as benchmark for relational reasoning by Shanahan et al. (2020). It consists of a family of binary classification tasks for identifying abstract relational rules between a set of objects represented as images. The object images depict simple geometric shapes and consist of three different splits with different visual styles for evaluating out-of-distribution generalization, referred to as "pentominoes", "hexominoes", and "stripes". The input is a sequence of objects arranged in a 3 x 3 grid. Each task corresponds to some relationship between the objects, and the target is to classify whether the relationship holds among the objects in the input or not (see Figure 4).
In our experiments, we evaluate out-of-distribution generalization by training on the pentominoes objects and evaluating the hexominoes and stripes objects. The input to the models is presented sequence of 9 objects, with each object represented as a 12 x 12 x 3 RGB image. All models share the common architecture (f1,...,,,,) - CNN - {-] - MLP - 9, where {-} indicates the central module being tested. In all models, the objects are first processed independently by a CNN with a shared architecture. The processed objects are then passed to the central module of the model. The final prediction is produced by an MLP with a shared architecture. In this section, we focus our comparison on four models: RelConvNet (ours); CoRelNet (Kerg et al., 2022), PrediNet (Shanahan et al., 2020), and a Transformer (Vaswani et al., 2017)3. The pentominoes split is used for training, and the hexominoes and stripes splits are used to test -uttof-distribution generalization after training. We train for 50 epochs using the categorical cross-entropy loss and the Adam optimizer with learning rate 0.001, &1 = 0.9, B2 = 0.999, c = 10-7, and batch size 512. For each model and task, we run 5 trials with different random seeds. Appendix A describes further experimental details about the architectures and training setup.
Out-of-distribution generalization. Figure 5 reports model performance on the two hold-out object sets after training. On the hexominoes objects, which are similar-looking to the pentominoes objects used for training, RelConvNet and CoReINet do nearly perfeetly. ProdiNct and the Transformer do well on the simpler tasks, but struggle with the more difficult 'match pattern' task. The 'stripes' objects are visually more distinct from the objects in the training split, making generalization more difficult. We observe an overall drop in performance for all models. The drop is particularly dramatic for CoReINet The scparation between RelConvNet and the other models is largest on the 'match pattern' task of the stripes split (the most difficult task and the most difficult. generalization split). Here, RelConvNet maintains a mean accuracy
TThe GNN baselines failed to learn the relational games tasks in way that generalizes, often severely overfitting. For clarity of presentation, we defer results on the GNN basclines to Appendix A. The experiments in Kerg et al. (2022) on the relational games benchmark use tochnique called "context uormalization" (Webb et al., 2020) as a preprocessing step. We choose not to use this technique since it is an added confounder. We discuss this choice in Appendix C.
8

---

Published in Transactions on Machine Learning Research (09/2024)
same
occurs
Xoccurs
between
match patt
11+
Pentominoes
Hexominoes
Stripes
PAH
L
rh
JL4
Figure 4: Relational games dataset. Left Examples of objects from each split. Right Examples of problem instances for each lask. The first row an example where the relation holds and the second row an example where the relation does not hold.
Split
Hexas
Split Stripes
Model
Accuracy
RelConwNet
CoReINet
PrediNet
Transformer
CNN
betwien
match
betwoen
match
Task
Task
Figure 5:
generalization on hold-out object sets. Bar heights indicate the mean over 5 trials and the crror bars indicate a bootstrap 95% confidence interval.
of 87% while the other models drop below 65%. We attribute this to RelConvNet's ability to naturally represent higher-order relations and model groupings of objects. The CNN bascline learns the casior 'same', 'between', and 'occurs' lasks nearly perfectly, but completely fails to learn the more difficult 'xoccurs' and 'match pattern' tasks. This hard boundary suggests that explicit relational architectural inductive biases are necessary for learning more difficult relational tasks.
Data efficiency. We observe that the relational inductive biases of RelConvNet, and relational models generally, grant significant advantage in sample-efficiency. Figure 6 shows the training accuracy over the first 2,000 batches for each model. RelConvNet, CoRelNet, and PrediNet are explicitly relational architectures, whereas the Transformer is not. The Transformer is able to process relational information through its attention mechanism, but this information is entangled with the features of individual objects (which, for these relational tasks, is extrancous information). The Transformer consistently requires the largest amount of data to learn the relational games lasks. PrediNet tends to be more sample-efficiett. RelConvNet and CoRelNet are the most sample-efficient, with RelConyNet only slightly more sample-efficient most tasks.
On the 'match pattern' task, which is the most difficult, RelConvNet significantly more sample-efficient. We attribute this to the fact that RelConvNet is able to model higher-order relations through its relational convolution module. The 'match pattern' task can be thought of as second-order relational task it involves computing the relational pattern in each of two groups, and comparing the two relational patterns. The relational convolution module naturally models this kind situation since learns representations of the relational patterns within groups of objects.

---

Published in Transactions on Machine Learning Research (09/2024)
same
between
occurs
training accuracy
training accuracy
training accuracy
1.0
0.8
0.8
0.8
0.6
0.6
1000
2000
1000
2000
1000
2000
batch step
batch step
batch step
xoccurs
match pattern
training accuracy
1.0
training accuracy
1.0
Model
RelConvNet
CoRelNet
PrediNet
0.6
0.6
Transformer
1000
2000
0
1000
2000
batch step
batch step
Figure 6: Training curves, up to 2,000 batch steps, for each relational games task. Solid lines indicate the mean over 5 trials and the shaded regions indicate bootstrap 95% confidence interval. Note that this is in-distribution (i.e., on the "pentominoes" split).
Group
Group
Group
Group
Learning groups via group attention. Next, we analyze RelConvNet's ' ability to learn useful group- ings through group attention in an end-to-end man-
ner. We train 2-layer relational convolutional net- work with learned groups and a graphlet size of
Group 5
Group
Group
Group
3. We group based position by using positional embeddings for key(z;). In Figure 7, we visualize the group attention scores ay (sce Equation (6)) learned from one of the training runs. For each group E [my]. the figure depicts a x 3 grid repre- senting the objects attended to that group. Since each group contains objects, we represent the value (e())s(ss) in the 3-channel HSV color representation. We observe that 1) group attention learns to ignore the middle row, which contains relevant information; and 2) the selection of objects in the top and the bottom row is structured. In particular, group 2 considers the relational pattern within the bottom row and group 8 considers the relational pattern in the top row, which is exactly how a human would tackle this problem. We refer to Figure 11 for an exploration of the effect entropy regularization on group attention. find that entropy regularization is necessary for the model to learn and causes the group allention scores to converge to interpretable discrete assignments.
Figure 7: Learned groups in the 'match pattern' tasks by a 2-layer RelConyNet with group attention.
4.2
Set: Grouping and Compositionality in Relational Reasoning
Sel is card game that forms sinple-todeescribe but challenging relational task. The 'objects' cards with four attributes, each of which take one of three possible values. "Color" can be red, green, purple; 'number' can be one, two, or three; 'shape' can be diamond, squiggle, or oval; and 'fill' can be solid, striped, or emply. A 'set' is a triplet of cards such that each altribute either a) the same on all three cards, or b) different on all three cards.
set of
In Sel, the lask is: given a hand of n > 3 cards, find a 'set' among them. Figure Sa depicts a positive and negative example for n = 5, with a indicating the 'set' in the positive example. This task is deceptively challenging, and is representative of the type of relational reasoning that humans excel at but machine learning systems still struggle with. To solve the task, one must process the sensory information of individual cards to identify the values of each attribute, and then reason about the relational pattern in each triplet of
10

---

Published in Transactions on Machine Learning Research (09/2024)
1.0
$
00
label
Accuracy
label = 1
0.0
RelConVNet
CoReiNet
PrediNet
Transformel
GCN
GiN
GAT
LSTM
CNN
Model
(a) Example "contains set" task.
(b) Hold-out test accuracy.
Split Train
Split
Validation
1.0
Model
0.9
RelConwNet
CoRelNet
Accuracy
0.8
PrediNet
Transformer
0.7
GCN
GIN
0.6
GAT
0.5
CNN
0
20
40
60
80
100
0
20
40
60
80
100
epoch
epach
(c) Training accuracy and validation accuracy over the course of training.
Figure 8: Results of ccntaiin set" experiments. Bar height/solid lines indicate the mean over 10 trials and error bars/shaded regions indicate 95% bootstrap confidence intervals.
cards. The construct relational convolutions proposed in this paper is a step towards developing machine learning systems that perform this kind of relational reasoning.
In this section, we evaluate RelConvNel is: given collection of n images of Set cards, determine whether not they contain 'set'. All models share the common architecture (II,..., - CNN - {.} - MLP - û, where {-} indicates the central module being tested. The CNN embedder is pre- pre-trained on the task of classifying the four attributes of the cards and an intermediate layer is used to generate embeddings. The output MLP architecture is shared across all models. Further architectural details can be found in Appendix A.
task based on Sel and compare it to several baselines. The task
In Set, there exists (5) = 85 320 triplets cards, of which 080 are a 'set'. We partition the 'sets' into training (70%), validation (15%), and test (15%) sets. The training, validation, and test datasets are generated by sampling n-tuples of cards such that with probability 1/2 the n-tuple does not contain a set, and with probability 1/2 it contains set among the corresponding partition of sets. Partitioning the data in this way allows us to measure the models' ability to "learn the rule" and identify unseen 'sets', We train for 100 epochs with the same loss, optimizer, and batch size as the experiments in the previous section. For cach model, we run 10 trials with different random seeds.
When using the default optimizer hyperparamcters as in the previous experiment without hyperparameter luning, we find that RelConvNet. is the only model able to meaningfully learn the task in a manner that generalizes to unseen 'sets'. In particular, we observe that many baselines severely overfit to the training data, failing to learn the rule and generalize (see Appendix B.1). Although RelConvNet did not require hyperparameter tuning, we carry out an extensive hyperparameter sweep for all other baselines individually in order to validate conclusions against the best-achievable performance for each baseline. We total
11

---

Published in Transactions on Machine Learning Research (09/2024)
of 1600 experimental runs searching combinations of architectural hyperparameters (number of layers) and optimization hyperparameters (weight decay, learning rate schedule) individually for each baseline, with the goal of finding a hyperparameter configuration that is representative of the best achievable performance for each model class on this task. The results of the hyperparameter sweep are summarized in Appendix B.
Figure 8b shows the hold-out test accuracy for each model. Figure Sc shows the training and validation accuracy over the course of training. Here, RelConvNet uses the Adam optimizer with the default Tensorflow hyperparameters (constant learning rate of 0.001, 31 = 0.9, 82 0.999) while each baseline has its own individually-optimiied hyperparameters, described in Appendix B.
We observe a sharp separation between RelConvNet and all other baselines. While RelConvNet is able to learn the task and generalize to new 'sets' with near-perfect accuracy (avg: 97.9%), no other model is able to reach a comparable generalization accuracy even after hyperparameter tuning. The next best is the GAT model (avg: 67.5%). Several models are able to fit the training data, reaching near-perfect training accuracy, but they are unable to "learn the rule" in way that generalizes to the validation or test sets. This suggests that while these models are powerful function approximators, they lack the induclive biases to learn hierarchical relations.
In Figure we analyze the geometry of the represen- tations learned by the relational convolution layer. We consider all triplets of cards, compute the rela- tion subtensor using the learned MD-IPR layer, and plot the relational inner product with the learned graphlet filter f E Ixx The result is a nt-- dimensional vector for each triplet of cards. We perform PCA to plot this in two dimensions, and color-code each triplet of cards according to whether or not it forms a 'set'. We find that the relational convolution layer learns a representation of the re- lational pattern in groups of objects that separates 'sets' and 'non-sets'. In particular, the two classes form clusters that are linearly separable even when projected down to two dimensions by PCA. This explains why RelConvNet is able to learn the task in a way that generalizes while the other models are not. In Appendix E we expand on this discussion, and further analyze the representations learned by the MD-IPR layer, showing that the learned relations map to the color, number, shape, and fill attributes.
not set set
40
(R[g). Fia (PC2)
-20
-0
20 (R[g), f) (PC1]
60
80
Figure 9: The relational convolution layer produces representations that separates 'sets' from 'non-sets..
It is perhaps surprising that models like GNNs and Transformers perform poorly on these relational tasks, given their apparent. ability to process relations through neural message-passing and attention, respectively We remark that GNNs operate in different domain compared to relational models like RelConvNe, PrediNet, and CoRelNet. In GNNs, the relations are an input to the model, received in the form of a graph, and are used to dictate the flow of information in a neural message- message-passing operation. By contrast, in relational convolutional networks, the input simply set of objects without relations the relations need to be inferred as part of the feature representation process. Thus, GNNs operate in domains where relational information is already present (e.g., analysis of social networks, biological networks, etc.), whercas our framework aims to solve tasks that rely relations but those relations need to be inferred end-to-end. This offers partial explanation for the inability of GNNs to learn this task-GNNs are good at processing network-style rolations when they are given as input, but may not be able to infer and hierarchically process relations when they are not given. In the case of Transformers, relations are modeled implicitly to direct information retrieval in attention, but are not encoded explicitly the final representations. By contrast, RelConvNet operates on collections of objects and possesses inductive biases for learning iteratively more complex relational representations, guided only by the supervisory signal of the downstream task.
12

---

Published in Transactions on Machine Learning Research (09/2024)
Models like CoReINet and PrediNet have relational inductive biases, but lack compositionality. On the other hand, deep models like Transformers and GNNs are compositional, but lack relational inductive biases. This experiment suggests that compositionality and relational inductive biases are both necessary ingredients to efficiently learn representations of higher-order relations. RelConvNet is a compositional architecture imbued with relational inductive biases and a demonstrated ability to tackle hierarchical relational lasks.
5 Discussion
Summary
In this paper, we proposed a compositional architecture and framework for learning hierarchical relational representations via a novel relational convolution operation. The relational convolution operation we propose here is 'convolution' in the sense that it considers patch of the relation tensor, given by a subset of objects, and compares the relations within it lo a template graphlet filter via approprialellyddffnee inner product. This is analogous to convolutional neural networks, where an image filter is compared against different patches of the imput image. Moreover, we propose an attention-based mechanism for modeling useful groupings of objects in order to maintain scalability. By alternating inner product relation layers and relational convolution layers, we obtain an architecture that naturally models hierarchical relations.
Discussion on relational inductive biases
In our experiments, we observed that general-purpont sequence models like the Transformer struggle to learn tasks that involve relational reasoning in data-efficient manner. The relational inductive biases of RelConvNet, CoReINet, and PrediNet result in significantly improved performance on the relational games tasks. These models each implement different kinds of relational inductive biases, and are each designed with different motivations in mind. For example, PrediNet's architecture is loosely inspired by the struct ure of predicate logic, but can be understood as ultimately producing representations of pairwise difference-relation. with pairs of objects selected by an attention operation. CoReINet is a minimal relational architecture inner product similarity matrix followed by softmax normalization.
that consists of computing an RelConvNet, our proposed architecture, provides further flexibility across several dimensions. Like CoReINet, it models relations as inner products of feature maps, but it achieves greater representational capacity by learning multi-dimensional relations through multiple learned fcature maps or filters. More importantly, the relational convolutions operation enables learning higher-order relations between groups of objects. This in contrast to both PrediNet and CoReINet, which are limited to pairwisc relations. Our experiments show that the inductive biases of RelConvNet result in improved performance in relational reasoning tasks. In particular, the Set task, where RelConvNet the only model able to generalize non-trivially, demonstrates the necessity for explicit inductive biases that support learning hierarchical relations.
Limitations and future work
The tasks considered here are solvable by modeling only second-order relations. In the case of the relational games benchmark of Shanahan et al. (2020), we observe that the tasks are saturated by the relational convolutional networks architecture. While the "contains set" task demonstrates a sharp separation between relational convolutional networks and existing baselincs, this task too only involves second-order relations. A more thorough evaluation of this architecture, and future architectures for modeling hierarchical relations, would require the development of new benchmark tasks and datasets that involve a larger number of objects and higher-order relations. This is a subtle and non-trivial task that we leave for future work.
The modules proposed in this paper assume object-centric representations as input. In particular, the tasks considered in our experiments have an explicit delineation between different objects. In more general settings, object information may need to be extracted from raw stimulus explicitly by the system (e.g., natural image containing multiple objects in apriori unknown positions). Learning object-centric representations is an active area of research (Sabour el al., 2017; Greff et al., 2019; Locatello et. al., 2020; Kipf et al., 2022), and is related but separate from learning relational representations. These methods produce a set of embedding vectors, each describing different object in the scene, which can then be passod to the central processing module (e.g., a relational processing module such as RelConvNet). In future work, it will be important to explore how well RelConvNet integrates with methods for learning object-centric representations in an end-to-end system.
13

---

Published in Transactions on Machine Learning Research (09/2024)
The experiments considered here are synthetic relational tasks designed for controlled evaluation. In more realistic settings, we envision relational convolutional networks as modules embedded in a broader architecture, For example, a relational convolutional network can be embedded into an RL agent to enable performing tasks involving relational reasoning. Similarly, relational convolutions can perhaps be integrated into general-purpose sequence models, such as Transformers, to enable improved relational reasoning while retaining the generality of the architecture.
Code and Reproducibility
The project repository can be found here: https://github.. http://////iiii//eeiiiiiaaaaaaaa cot.riooooniinooooooiiooooo It includes an implementation of the relational convolutional networks architecture, code and instructions for reproducing our experimental results, and links to experimental logs.
Acknowledgment
This work supported by the funds provided by the National Science Foundation and by DoD OUSD (R&E) under Cooperative Agreement PHY-2229929 (The NSF AT Institute for Artificial and Natural Intelligence).
References
Altabaa, Awni and John Lafferty (2024a). "Approximation of relation functions and attention mechanisms". arXiv: 2402. 08856 [cs.LG] (cited on page 4).
Altabaa, Awni and John Lafferty (2024b). "Discntangling and Integrating Relational and Sensory Information in Transformer Architectures", arviv: 2405. 16727 Altabaa, Awni, Taylor Whittington Webb, Jonathan D. Cohen, and John Lafferty (2024). "A "Abstractors and relational cross-attention: An inductive bias for explicit relational reasoning in Transformers". In: The Twelfth International Conference on Learning Representations (cited on page 3).
(cited on page 3).
Attanasio, Giuseppe, Debora Nozza, Dirk Hovy, and Flena Baralis (2022). "Entropy-based Attention Regu- larization Frees Unintended Bias Mitigation from Lists", In: Findings of the Association for Computational Linguistics: ACL 2022 (cited on page 6).
Ba, Jimmy Lei, Jamie Ryan Kiros, and GeofTrey E. Hinton (2016). "Layer Normalization". arXiv: 1607.0648 [stat.ML] (cited on page 7).
Battaglia, Peter W. et al. (2018). "Relational Inductive Biases, Deep Learning, and Graph Networks". arXiv:
1806.01261 [cs, stat] (cited on page 2).
Carpenter, Patricia A, Marcel A Just, and Peter Shell (1990). "What one intelligence test measures: a theoretical account of the processing in the Raven Progressive Matrices Test." " In: Psychological review. Englund, CE, DL Reeves, CA Shingledecker, DR Thorne, KP Wilson, and FW Hegge (1987). "Unified tri- service cognitive performance assessment battery (UTC-PAB) I. Design and Specification of the Battery". In: Naval Health Rescarch Center Report. San Diego, California.
Fagol, Joël, Edward A Wasserman, and Michael E Young (2001). "Discriminating the relation between relations: the role of entropy in abstract conceptualization by baboons (Papio papio) and humans (Homo sapiens)." In: Journal of Experimental Psychology: Animal Behavior Processes (cited on page 1). Ferster, Charles Bohris (1960). "Intermittent reinforcement of matching to sample in the pigeon". In: Journal of the Experimental Analysis of Behavior (cited on page 1). Frank, Stefan L, Rens Bod, and Morten H. Christiansen (2012). "How hierarchical is language use?" In Proceedings of the Royal Society B: Biological Sciences (cited on page 28).
Gilmer, Justin, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl (2017). "Neural Message Passing for Quantum Chemistry". In: International Conference on Machine Learning. PMLR (cited on page 2).
Greff, Klans, Raphaäl Lopez Kaufman, Rishabh Kabra, Nick Watters, Christopher Burgess, Daniel Zoran, Loic Matthey, Matthew Botvinick, and Alexander Lerchner (2019). "Multi-Object Representation Learning with Iterative Variational Inference". In: Proceedings of the 36th International Conference on Machine Learning. Ed. by Kamalika Chaudhuri and Ruslan Salakhutdinov. Proceedings of Machine Learning Research. PMLR (cited page 13).
Hamilton, William L (2020). "Graph Representation Learning". Synthesis Lectures on Artificial Intelligence and Machine Learning. San Rafael, CA: Morgan & Claypool (cited on page 2).
14

---

Published in Transactions on Machine Learning Research (09/2024)
He, Kaiming, Xiangyu Zhang, Shaoqing Ren, and Jian Sun (2016). "Deep residual learning for image recognition". In: Proceedings of the IEFE conference on compuler vision and pallern recognition (cited on page 7).
Hochmann, Jcan-Rémy, Arin S. Tuerk, Sophia Sanborn, Rebecca Zhu, Robert Long, Megan Dempster, and Susan Carey (2017). "Children's representation of abstract relations in Illational/arrayy match-lo-sample tasks". In: Cognétive Psychology.
Johnson, Justin, Bharath Hariharan, Laurens Van Der Maaten, Li Fei-Fei, C Lawrence Zitnick, and Ross Girshick (2017). "CLEVR: A diagnostic dataset for compositional language and elementary visual reasoning". In: Proceedings of the TEFE conference on computer vision and pattern recognation (cited on page 28). Kerg, Giancarlo, Sarthak Mittal, David Rolnick, Yoshua Bengio, Blake Richards, and Guillaume Lajoie (2022). [cs] (cited on pages 3,
"On Neural Architecture Inductive Biases for Relational Tasks". arXiv: 2206.05056 05056
7, 8, 26).
Kipf. Thomas, Gamaleldin Fathy Elsayod, Aravindh Mahendran, Austin Stone, Sara Sabour, Goorg Heigold, Rico Jonschkowski, Alexey Dosovitskiy, and Klaus Greff (2022). "Conditional Object- Learning from Video". In: International Conference on Learning Representations (cited page 13).
Kipf, Thomas, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, and Richard Zemel (2018). "Neural relational inference for interacting systems". In: International conference on machine learning (cited on page 2). Kipf, Thomas N. and Max Welling (2017). "Semi-Supervised Classification with Graph Convolutional Networks", Xiv: 1609. 029077 [cs, stat] (cited on pages 2, 8).
Locatello, Francesco, Dirk Weissenborn, Thomas Unterthiner, Aravindh Mahendran, Georg Heigold, Jakob Uszkoreit, Alexey Dosovitskiy, and Thomas Kipf (2020). "Object-centiie
learning with slot attention". In: Advances in Neural Information Processing Systems (cited on pages 3, 13).
Marcus, Gary F, Sugumaran Vijayan, Shoba Bandi Rao, and Peter M Vishton (1999). "Rule learning by seven-month-old infants". In: Science.
Martins, André, António Farinhas, Marcos Treviso, Vlad Niculae, Pedro Aguiar, and Mario Figueiredo (2020). "Sparse and continuous attention mechanisms". In: Advances in Newral Information Processing Systems (cited on page 6).
Niculae, Vlad and Mathieu Blondel (2017). "A regularized framework for sparse and structured neural attention". In: Advances in neural information processing systems (cited on page 6).
Niepert, Mathias, Mohamed Ahmed, and Konstantin Kutzkov (2016). "Learning convolutional neural networks for graphs". In: International conference on machine learning. PML. (cited on page 2).
Rosario, Barbara, Marti A Hearst, and Charles J Fillmore (2002). "The descent of hierarchy, and selection in relational semantics". In: Proceedings of the 40th Annual Meeting of the Association for Computational Linguisties (cited on page 28).
Sabour, Sara, Nicholas Frosst, and Geoffrey Hinton (2017). "Dynamic routing between capsules". In: Advances in neurol information processing systems (cited on page 13).
Santoro, Adam, Ryan Faulkner, David Raposo, Jack Rae, Mike Chrzanowski, Theophane Weber, Daan Wierstra, Oriol Vinyals, Razvan Pascanu, and Timothy Lillicrap (2018). "Relational Recurrent Neural Networks". In: Advances in Neural Information Processing Systems. Curran Associates, Inc. (cited on
page 3).
Santoro, Adam, David Raposo, David G Barrett, Mateusz Malinowski, Razvan Pascanu, Peter Battaglia, and Timothy Lillicrap (2017). "A simple neural network module for relational reasoning". In: Advances in neural information processing systems (eited on pages 3, 28).
Schlichtkrull, Michael, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling (2018). "Modeling relational data with graph convolutional networks". In: The Semontic Web: 15th International Conference, ESWC 2018, Heraklion, Crete, Greece, June 8-7, 2018, Proceedings 15. Springer (cited on page 2).
Shanahan, Murray, Kyriacos Nikiforou, Antonia Creswell, Christos Kaplanis, David Barrett, and Marta Garnelo (2020). "An Explicitly Relational Neural Network Architecture". In: Proceedings of the 37th International Conference on Machine Learning. Ed. by Hal Daumé III and Aarti Singh. Proceedings of Machine Learning Research. PMLR (cited on pages 2, 3, 7, 8, 13).
Vaswani, Ashish, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin (2017). " "Attention is all you need". In: Advonces in neural information processing systems (cited on pages 3, 7, 8).
15

---

Published in Transactions on Machine Learning Research (09/2024)
Veličkovié, Petar, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio (2018). "Graph Attention Networks". In: International Conference on Learning Represenlations (cited on pages 2, 3, 8).
Webb, Taylor, Zachary Dulberg, Steven Frankland, Alexander Petrov, Randall O'Rcilly, and Jonathan Cohen (2020). "Learning Representations that Support Extrapolation". In: Proceedings of the 37th International Conference on Machine Learnöng. Ed. by Hal Daumé III and Aarti Singh. Proccedings of Machine Learning Research. PMLR (cited on pages 8, 26).
Webb, Taylor W., Steven M. Frankland, Awni Altabaa, Kamesh Krishnamurthy, Declan Campbell, Jacob Russin, Randall O O'Reilly, John Lafferty, and Jonathan D. Cohen (2024). "The Relational Bottleneck as an Inductive Bias for Efficient Abstraction". arXiv: 06629 [cs] (cited on page 3).
Webb, Taylor Whittinglon, Ishan Sinha, and Jonathan Cohen (2021). "Emergent Symbols through Binding in External Memory". In: International Conference on Learning Representations (cited on pages 1, 3, 26). Xu, Keyulu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka (2019). "How Powerful are Graph Neural Networks?" In: International Conference on Learning Represenlations (cited pages 2, 8).
Zaheer, Manzil, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola (2017). "Deep sets". In: Advances in neural information processing systems (cited on page 28). Zambaldi, Vinicius, David Raposo, Adam Santoro, Victor Bapst, Yujia Li, Igor Babuschkin, Karl Tuyls, David Reichert, Timothy Lillicrap, Edward Lockhart, et al. (2018). "Deep reinforcement learning with relational inductive biases". In: International conference on learning representations (cited on page 3). Zeiler, Matthew and Rob Fergus (2014). "Visualizing and understanding convolutional networks". " In: Computer ECCon 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part 13. Springer (cited page 2).
16

---

Published in Transactions on Machine Learning Research (09/2024)
A Experiments Supplement
A.1 Relational Games (Section 4.1)
The pentominoes split is used for training, and the hexominoes and stripes splits are used to test out-of- distribution generalization after training. We hold out 1000 samples for validation (during training) and 5000 samples for testing (after training), and use the rest as the training set. We train for 50 epochs using the categorical cross-entropy loss and the Adam optimizer with learning rate 0.001, 31 0.9, 82 0.999, c 10- We use a batch size of 512. For each model and task, we run trials with different random seeds. Table contains text descriptions of each task in the relational games dataset in the experiments of Section 4.1. Table 2 contains description of the architectures of each model (or shared component) in the experiments. Table 3 reports the accuracy on the hold-out object sets (i.c., the numbers depicted in Figure 5 of the main text). Figures 10 and 11 explore the effect of entropy regularization in group attention on learning using the "match pattern" task as an example.
Task
Description
same
Two random cells out of nine occupied by object. They are the "same" if they have the same color, shape, and orientation (i.e., identical image) The top row contains one object and the bottom row contains three objects. The "oceurs" relationship holds if at least one of the objects in the bottom row is the same as the object in the top row.
occurs
Xoccurs
Same as occurs, but the relationship holds if exactly one of the objects in the bottom row is the same as the object in the top row.
between
The grid is occupied by three objects in a line (horizontal or vertical). The "between" " relationship holds if the outer objects are the same.
row match pattern
The first and third rows of the grid are occupied by three objects each. The "match pattern" relationship holds the relation pattern in each row is the same (c.g., AAA, AAB, ABC, etc.)
Table 1: Relational games tasks.
17

---

Published in Transactions on Machine Learning Research (09/2024)
Model / Component
Architecture
Common CNN Embedder
Conv2D + MaxPoo12D Conv2D MaxPoo12D Flatten.
Conv2D: filters 16, filter size activation relu.
MaxPoo12D: stride = 2.
Common output MLP
Dense (64, 'relu') Dense (2).
RelConvNet
CNN Embedder - MD- + RelConv - Flatten - MLP.
MD-IPR: relation dim = 16, projection dim 4, symmetric.
RelConv: num filters 16, filter size 3, discrete groups combinations.
CoReINet
CNN Embedder CoRelNet - Flatten MLP.
Standard CoRelNet has hyperparameters..
PrediNet
CNN Embedder PrediNet Flatten MLP.
PrediNet: key dim = 4, number of heads 4, num relations 16.
Transformer
CNN Embedder TransformerEhcoder - AveragePooling - MLP.
orme mum layers 1, num heads 8, feedforward intermediate size = 32, activation = relu.
GCN
CNN Embedder + AddPosEmb + (GCNConV - Dense) x2 - AveragePooling -
MLP.
channels = 32, Dense: num neurons = 32, activation relu CNN Embedder + AddPosEmb + (GATConV - Dense) x2 - AveragePooling -
GCConv:
GAT
MLP.
channels 32, Dense: num neurons 32, activation relu CNN Embedder AddPosEmb + (GINConV Dense)
GATonv:
GCN
AveragePooling
MLP.
GINConv: channels = 32, Dense: num neurons 32, activation relu (Conv2D - MaxPoo12D) x - Flatten - Dense Dense(128, 'relu') - Dense (2)
CNN
Conv2D: mum filters = [16, 16, 32, 32, 64, 64, 128, 128), filter size = 3
MaxPoo12D: stride = 2, apply every other layer.
Table 2: Model architectures for relational games experiments.
18

---

Published in Transactions on Machine Learning Research (09/2024)
Hexos Accuracy
Stripes Accuracy
Task
Model
same
RelConvNet
0.989 + 0.002
0.974 + 0.003
CoRelNet
0.988 + 0.006
0.724 + 0.112
PrediNet
0.990 + 0.004
0.983 + 0.007
Transformer
0.997 + 0.001
0.993 = 0.004
CNN
0.990 0.001
0.976 + 0.002
between
RelConv.Net
0.991 + 0.001
0.988 + 0.002
CoReINet
0.995 0.001
0.582 + 0.063
PrediNet
0.978 0.006
0.950 + 0.019
Transformer
0.986 + 0.003
0.961 + 0.010
CNN
0.990 + 0.001
0.971 + 0.003
occurs
RelConv Net.
0.980 + 0.001
0.880 + 0.015
CoRelNet
0.992 + 0.004
0.518 + 0.012
PrediNet
0.907 + 0.020
0.775 - 0.046
Transformer
0.881 0.015
0.724 + 0.021
CNN
0.984 0.008
0.953 + 0.012
xoccurs
RelConvNect
0.967 + 0.001
0.946 + 0.006
CoRelNet
0.980 + 0.007
0.606 + 0.035
PrediNet
0.872 + 0.036
0.810 = 0.028
Transformer
0.867 + 0.017
0.753 + 0.031
CNN
0.597 + 0.097
0.590 = 0.084
match pattern
RelConyNNet
0.961 + 0.015
0.870 + 0.041
CoRcINet
0.942 + 0.011
0.581 + 0.026
PrediNet
0.710 0.040
0.658 + 0.053
Transformer
0.627 0.005
0.591 + 0.006
CNN 0.499 0.000
0.489 + 0.000
Table 3: Out-of-distribution generalization results relational games. We report means + standard error of mean over 5 trials. These are the numbers associated with Figure 5.
A.2
Set (Section 4.2)
We train for 100 epochs using the cross-entropy loss. RelConvNet uses the Adam optimizer with learning rate 0.001, 31 = 0.9, Bg = 0.999, c 10-? The basclines cach use their own individually-tuned optimization hyperparameters, described in Appendix B. We use a batch size of 512. For each model and (ask, we run trials with different random seeds. Table 4 contains a description of the architecture of each model the "contains set" experiments Scction 4.2. Table 5 reports the generalization accuracics on the hold-out 'sets' (i.e., the numbers depicted in Figure 8b of the main text). Figure explores the effect of different NelConvNet hyperparameters the model's ability to learn the the Set task.
19

---

Published in Transactions on Machine Learning Research (09/2024)
Model / Component
Architecture
Common CNN Embedder
Conv2D - MaxPoo12D Conv2D MaxPoo12D Flatten
Dense (64,
'relu') Dense (64, ' 'tanh').
Conv2D: mum filters = 32, filter size 5 5, activation = relu.
BaxPoo12D: stride = 4.
Common output ML.
Dense(64, 'relu') - Dense 'relu') - Dense
RelConyNet
CNN Embedder + MD-IPR - RelConv - Flatten - MLP.
MD-IPR: relation dim = 16, projection dim 16, symmetric.
RelConv: num filters 16, filter size 3, discrete groups combinations, symmetric relational inner product with 'max' aggregator.
CoRelNet
CNN Embedder CoRelNet Flatten MLP.
Standard CoRelNet has no hyperparameters..
PrediNet
CNN Embedder - PrediNet - Flatten MLP.
PrediNet: key dim = 4, number of heads = 4, num relations = 16. CNN Embedder + TransformerEncoder - AveragePooling - MLP.
Transformer
TransformerFacoderr num layers = 2, num heads = 8, feedforward intermediate
size = 128, activation = relu.
GCN
CNN Embedder + (GCNConV - Dense) x2 - AveragePooling + MLP. GCConv: channels 128, Dense: num neurons 128, activation relu
GAT
CNN Embedder (GATConv Dense) - AveragePooling MLP.
GATonv: channels 128, Dense: mum neurons 128, activation relu
GON
CNN Embedder (GINConv Dense) - AveragePooling MLP.
GINConv: channels 128, Dense: num neurons = 128, activation rclu
CNN
(Conv2D + MaxPoo12D) 10 Flatten + Dense (128, 'relu') Dense (2)
Conv2D: num filters = 16. 16, 32, 32, 64, 64, 128, 128, 128, 128). filter size 3 MaxPoo12D: stride = [222),, NA, (2,2), NA, (2,2), NA, (2,2), (1,2), (1,2), (2, 2)]
Table 4: Model architectures for "contains set" experiments.
Accuracy
Model
RelConvNet
0.979 0.006
CoReINet
0.563 + 0.001
PrediNet
0.513 0.003
Transformer
0.563 + 0.002
GCN
0.635 + 0.003
GIN
0.593 + 0.001
GAT
0.675 0.002
LSTM
0.609 0.002
CNN
0.506 0.006
Table 5: Hold-out test accuracy on "contains set." task. We report means + standard error of mean over 10 trials. These are the numbers associated with Figure 8b.
20

---

Published in Transactions on Machine Learning Research (09/2024)
Cross-yntropy Loss
Group Attention Entropy
0.7
1.0
0.6
0.8
Group Attention Entropy
Cross-entrope Loss
0.5
0.6
0.4
0.3
0.4
0.2
0.2
0.1
0.0
0.0
0.0
0.05
0.1
0.2
0.4
0.8
1.6
Entropy Regularization Scale (A)
Figure 10: Trade-off between task loss and group attention entropy. RelConvNet models are trained on the "match pattern" task in the Relational Games benchmark varying the entropy regularization level. The overall model loss is Liose + ACeatz, where Ciose CrossEntropy(s, 9) is the task loss (blue line), Centr is the entropy regularization term for the group attention scores (orange line) defined in Section 3.2, and À is scaling factor. Different lines correspond to different values of A. When X = 0 (no entropy regularization) the model fails to learn the task. A small amount regularization is enough to guide the model to a good solution. Increasing À causes smaller group attention entropy at convergence, approaching discrete assignments.
Effect of Entropy Regularization Group Attention
Group Attention Entropy
2.0
0.6
Cross-entrope Loss
1.5
0.4
1.0
0.2
0.5
0.0
20
40
60
80
100
0
20
40
80
100
Epoch
Epoch
Entropy Regularization Scale
0.0
0.05
0.1
0.2
0.4
Figure Efffect of group attention entropy regularization. Group attention entropy (left) and baseline cross-entropy loss (right) of relational convolutional network model trained on the "match pattern" task with different levels of entropy regularization. The overall model loss is Ciose ALentr. where Lioes is the task loss, Lentr is the entropy regularization term, and À is scaling factor. Different lines correspond to different values of X. Without entropy regularization, the model fails to learn the task. With sufficient entropy regularization, the model is able to learn the task and group aliention converges towards discrete assignments. The group attention entropy starts at log x 2.2 (the entropy of uniform distribution) and decreases over the course of training. Expectedly, larger À values cause the entropy to decrease faster, converging towards a smaller value. When À is too large, the entropy regularization overwhelms the base cross-entropy loss and results in converging to worse cross-entropy loss. Intuitively, one needs strike balance such that both the entropy regularization and the cross-entropy loss guide the evolution of the group attention map.
21

---

Published in Transactions on Machine Learning Research (09/2024)
Split Train
Split Validation
1.0
0.9
Accuracy
0.8
0.7
0.6
0.5
20
40
60
80
100
0
20
40
60
80
100
epoch
opoch
Model
RelConvNet
RelConvNet (d, 1)
RelConNNet (Symmetry Relations False)
Exploring the effect of iuutti-dimensional relations and symmetric relations in RelConvNet. RelConvNet models matching the architecture described in Table 4 are trained on the Set task. We test two variants: 1) set the relation dimension to be d, = 1 (instoad of d, = 16), and 2) remove the symmetry inductive bias (i.e., W1 * W2 in Equation (2)). We find that with d, = 1 (which is analogous to CoRelNet's single-dimensional similarity matrix), the model struggles to find good solutions. In 10 different runs with random seeds, one run was able to find a good solution reaching an accuracy 98.5%, whereas the other runs were stuck below 65%. This suggests that having multi-dimensional relations yiclds a more robust model with multiple differrnt avenues for finding good solutions during the optimization process. In the case of the model with the asymmetric relations (i.e., lacking symmetry inductive bias), the model is able to fit the training data, but fails to generalize. This suggests the symmetry is an important inductive bias for certain tasks.
Figure 12:
B Hyperparameter sweep for baseline models
In order to ensure that we compare RelConvNet against the best-achievable performance by each baseline architecture, we carry out an extensive hyperparameter sweep over combinations of architectural hyperparam- eters and optimization hyperparameters. In particular, seen in Appendix B.1, the baseline models severely overfit on the Set task, fitting the training data but failing to generalize to unseen 'sets'. Hence, we explore whether it is possible to avoid or alleviate overfitting through an appropriate choice of hyperparameters.
In Figure 13, we vary the mumber of layers in the baseline models select optimal configuration of each architecture. We find that increased depth beyond 2 layers is generally detrimental on this task. Based on these results, we choose the optimal number of layers as 2 for the Transformer, GCN, GIN baselines and for the GAT baseline.
In Figure 14, we vary the level of weight decay. Expectedly, larger weight decay results in decreased training accuracy. Generally, weight decay has small effect on validation performance (c.g., no discernable effect in CoReINet or CNN). For some models, some choices of weight decay result in improved validation performance. Based on these results, we use a weight decay of 0 for CoRelNet/CNN 0.032 for Transformer/GAT] /GIN, and 1.024 for ProdNet/GCX/ISTM.
In Figure 15, we explore the effect of the learning rate schedule, comparing a cosine decay schedule against our default constant learning rate. For most models, there no significant difference, with a constant learning rate sometimes slightly better. On the GAT model, however, the cosine learning rate schedule results significantly improved performance. Based on these results, we use a cosine learning rate schedule for GAT and constant learning rate for all other models.
22

---

Published in Transactions on Machine Learning Research (09/2024)
1.0
Training Accuracy
Validation Accuracy
Model
0.8
Transformer
0.60
GCN
0.7
GAT
GIN
0.55
0.5
0.50
Number of Layers
Number of Layers
Figure 13: Hyperparameter sweep over number of layers in baseline architectures. Transformers and GNNs (e.g., GCN, GAT, GIN) are "compositional" deep learning architectures. Here, we explore the effect of depth (i.e., number of layers) on task performance for these baselines. The plots show the maximum training and validation accuracy reached throughout training for each depth (5 trials with different random seeds). Generally, we find that gencralization performance drops with increasing depth. The optimal depth for the Transformer, GCN, and GIN models is 2 layers, and the optimal depth for the GAT model is 1-layer. The performance drop with depth can perhaps be attributed to increased difficulty of training and overfitting due to limited data and a lack of relational inductive biases. The AdamW optimizer is used with a constant learning rate of 10"
0.70
1.0
Model
Training Accuracy
0.9
Validation Accuracy
0.65
CoReINet
PrediNet
Transformer
GCN
0.7
GAT
GIN
0.55
0.6
LSTM
CNN
10
10a
10
10
10
10
10
Weight Decay
Weight Decay
Figure 14: Hyperparameter sweep of weight decay in bascline architoctures. To alleviate possible overfitting, we optimally tune weight decay parameter for each model independently. We test weight decay values including 0 and 0.004. 2', (0,..., 10). We the AdamW optimizer. The default weight decay in Tensorflow is 0.004.
23

---

Published in Transactions on Machine Learning Research (09/2024)
Model
1.0
CoRelNet
0.65
PrediNet
Training Accuracy
0.9
Validation Accuracy
Transformer
GCN
GAT
GIN
0.7
0.55
LSTM
CNN
0.6
Sched
0.50
Constant
0.5
Cosine
60
80
60
epoch
epoch
Figure 15: Hyperparameter sweep over learning rate schedule (constant vs cosine decay). We explore the effect of the learning rate schedule on model performance, comparing constant learning rate against a cosine decay schedule. For most models, there no significant difference, with constant learning rate sometimes slightly better. On the GAT model, however, the cosine learning rate schedule results in significantly improved performance.
B.1 Results without hyperparameter tuning
Figure 16 and Table 6 show the results of the Set experiment with a common default optimizer, without individual hyperparamoter tuning.
Accuracy
Model
RelConyNet
0.979 + 0.006
CoRelNet
0.563 0.001
PrediNet
0.508 0.002
Transformer
0.584 0.004
GCN
0.595 0.003
GAT
0.517 0.015
GIN
0.590 0.003
LSTM
0.602 + 0.003
GRU
0.593 + 0.004
CNN
0.506 0.006
Table 6: Hold-out accuracy on "contains set" task, with default optimizer hyperparameters. We report
means + standard error of mean over 10 trials. These are the numbers associated with Figure 16a.
24

---

Published in Transactions on Machine Learning Research (09/2024)
Accuracy
0.6
0.4
0.2
0.0
ReiConvNet
CoRelfeer
PrediNet
Transformer
GCN
GAT
LSTM
CNN
Model
(a) Hold-out test accuracy.
Split Train
Split Validation
1.0
0.9
Model
RelConwNet
CoReINet
Accuracy
0.8
PrediNet
Transformer
0.7
0.6
GAT
LSTM
0.5
0
20
40
80
100
20
40
60
100
epoch
epach
(b) Training accuracy and validation accuracy over the course of training, without hyperparameter tuning (i.e.,
Adam optimizer, no weight decay, constant learning rate of 0.001.
Figure 16: Results of "contains set" experiments with default optimization hyperparameters. Bar height/solid lines indicate the mean over 10 trials and error bars bars/shadee /sadeed regions indicate 95% bootstrap confidence intervals.
25

---

Published in Transactions on Machine Learning Research (09/2024)
C Discussion on use of TCN in evaluating relational architectures
In Section 4.1 the CoRelNet model of Kerg et al. (2022) was among the baselines we compared to. In that work, the authors also evaluate their model on the relational games benchmark. A difference between their experimental set up and ours is that they use a method called "context normalization" as a preprocessing step on the sequence of objects.
"Context normalization" was proposed by Webb et al. (2020). The proposal simple: Given a sequence of objects, (21....; and set of context windows Wi...., Ww = (I,..., m)] which partition the objects, each object is normalized along each dimension with respect to the other objects in its context. That is, (Zi..... 2m) = CN(z1..... Fmm] is computed as;
(K) = M4
1
Σ (mt)
WW
AEW,
1
Σ
1 (1=))-p1(h))
(18)
of =
+
V
[WAll rEW,
(It)) uig (R)
(z)) = 71
+ B3.
for t W4
(A)
where y= (?.....:7)) (B)..... Ba) are learnable gain and shift parameters for each dimension (initializod at 1 and 0, respectively, as with batch normalization). The context windows represent logical groupings of objects that are assumed to be known. For instance, (Webb et al., 2021; Kerg et al., 2022) consider "relational malch-to-sample" task where 3 pairs of objects are presented in sequence, and the task is to identify whether the relation in the first pair is the same as the relation in the second pair or the third pair. Here, the context windows would be the pains of objects. In the relational games "match rows pattern" task, the context windows would be each row.
It reported in (Webb al., 2021; Kerg et al., 2022) that context normalization significantly accelerates learning and improves out-of-distribution generalization. Since (Webb et al., 2021; Kerg al., 2022) use context normalization in their experiments, in this section we aim to explain our choice to exclude it. We argue that context normalization is confounder and that an evaluation of relational architectures without. such preprocessing is more informative.
To understand how context normalization works, consider first a context window of size 2, and let B = 0,7 = 1. Then, along each dimension, we have
CN(z, 2) (0,0), CN(r, = (sign(z v), sign(yyxx))
In particular, what context normalization does when there are two objects is, along each dimension, output 0 if the value is the same, and +1 if is different (encoding whether it is larger or smaller). Hence, it makes the nnrmait-or output independent of the original feature representation. For tasks like relational games, where the key relation to model is same/differs in "symbolic" way. In particular, for two objects I1,42, context normalized to produce æ1, #2, we have that 2 22 if and only if (2,, 0. This makes -utto--distr generalization trivial, and does not properly test a relational architecture's ability to model the same/ /diferrent relation.
this preprocessing is directly encoding this information
Similarly, consider context window of size Then, along each dimension, we have,
(N(x, (0, 0),
CN(2, (
1 ( sign(x - v).
1 sign(y sign(y-x))
22 sign(r - v),
S22
Again, context normalization symbolically encodes the relational pattern. For any triplet of objects, regardless of the values they take, context normalization produces identical output in the cases above. With context windows larger than the behavior becomes more complex.
26

---

Published in Transactions on Machine Learning Research (09/2024)
These properties of context normalization make it confounder in the evaluation of relational architectures. In particular, for small context windows especially, context normalization symbolically encodes the relevant. information. Experiments on relational architectures should evaluate the architectures' ability to learn those relations from data. Hence, we do not use context normalization in our experiments.
27

---

Published in Transactions on Machine Learning Research (09/2024)
D Higher-order relational tasks
As noted in the discussion, the tasks considered in this paper are solvable by modeling second-order relations at most. One of the main innovations of the relational convolutions architecture over existing relational architectures is its compasitionality and ability to model higher-order relations. An important direction of future research is to test the architecture's ability to model hierarchical relations of increasingly higher order. Constructing such benchmarks is a non-trivial task which requires careful thought and considcration. This was outside the scope of this paper, but we provide an initial discussion here which may be useful for constructing such benchmarks in future work.
Propositional logic. Consider evaluating boolean logic formula such as,
21 ((22 Σ3) ((-x3 ZA) (æs z6 A z7))).
Evaluating this logical expression (in this form) requires iteratively grouping objects and computing the relations between them. For instance, begin by computing the relation within 9i (æa, 244 and the relation within 92 (æs, T6, #7), then we compute the relation between the groups 91 and 92, etc. For a task which involves logical reasoning of this hierarchical form, one might imagine the group attention in RelConvNet learning the relevant groups and the relational convolution operation computing the relations within each group. Taking inspiration from logical reasoning with such hierarchical structure may lead to interesting benchmarks of higher-order relational representation.
Sequence modeling. In sequence modcling (e.g.: language modcling), modcling the relations between objects is usually essential. For example, synlactic and semantic relations between words are crucial to parsing language. Higher-order relations are also important, capturing syntactic and semantic relational features across different locations in the text and across multiple length-scales and layers of hicrarchy (see for example some relevant work linguistics Frank et al., 2012; Rosario et al., 2002). The attention matrix Transformers can be thought of as implicitly representing relations between tokens. It is possible that composing Transformer layers also learns hierarchical relations. However, as shown in this work and previous work relational representation, Transformers have limited efficiency in representing relations. Thus, incorporating relational convolutions into Transformer-basel sequence models may yield meaningful improvements in the relational aspects of sequence modeling. One way to do this is by cross-attending to a the sequence of relational objects produced by relational convolutions, each of which summarizes the relations within a group of objects at some level of hicrarchy.
Set embedding. The objective of set embedding is map a collection of objects to a euclidean vector which represents the important features of the objects in the set (Zaheer al., 2017). Depending on what the set embedding will be used for, it may need to represent combination of object-level features and relational information, including perhaps relations of higher order. A set embedder which incorporates relational convolutions may be able to generate representations which summarize relations between objects at multiple layers of hierarchy.
Visual scene understanding. In a visual scene, there are typically several objects with spatial, visual, and semantic relations between them which are crucial for parsing the scene. The CLEVR benchmark on visual scene understanding (Johnson et al., 2017) was used in early work on relational representation (Santoro et al., 2017). In more complex situations, the objects in the scene may fall into natural groupings, and the spatial, visual, and semantic relations between those groups may be important for parsing scene (c.g., objects forming larger components with functional dependence determined by the relations between them). Integrating relational convolutions into a visual scene understanding system may enable reasoning about such higher-order relations.
28

---

Published in Transactions on Machine Learning Research (09/2024)
E Geometry of representations learned by MD-IPR and Relational Convolutions
In this section, explore and visualize the representations learned by MD-IPR and RelConv layers. In particular, we will visualize the representations produced by the RelConvNet model trained on the Set lask described in Section 4.2. Recall that the MD-IPR layer learns encoders Φ1, 11,,..,, Ad,,, Va,,- In this model d, 16, o; = 1/ (so that learned relations are symmetric), and each Φ; is a linear transformation to dproj 4-dimensional space. The representations learned by a selection of encoders is visualized Figure 17. For each of the 81 possible Set cards, we apply each encoder in the MD-IPR layer, reduce to 2-dimensions via. PCA, and visualize how each encoder separates the attributes: number, color, fill, and shape. Observe, for example, that "Encoder 0" disentangles color and shape, "Encoder 2" disentangles fill, and "Encoder 3 disentangles number.
Next, we visualize, we explore the geometry of learned representations of relation vectors. That is, the inner products producing the 16-dimensional relation vector for each pair of objects. For each (2) pairs of Set cards, we compule the 16-dimensional relation vector learned by the MD-IPR layer, reduce dimensions via PCA, and visualize how the learned relation disentangles the latent same same/differe /different relations among the four attributes. This is shown in Figure 18. We see scparation of the underlying same/ ciferdiffeeet relations among the four attributes, even with only two dimensions out of 16.
Finally, we visualize the representations learned by the relational convolution layer. Recall that this layer learns a set of graphlet filters f E Rexaxd,xx, which form templates of relational patterns against which groups of objects are compared. In our experiments, the filter size " 16. Hence, for each group g of 3 Set cards, the relational convolution layer produces a 16-dimensional vector, (R[g]] frrr R",, summarizing the relational structure of the group. Of the (3) possible triplets of Set cards, we create balanced sample of "sets" and "non-sets". We then compute ( (R[g]. f)re and reduce to 2 dimensions via. PCA. Figure 9 strikingly shows that the represent ations learned by the relational convolution layer very clearly separate triplets of cards which form set from those that don't 't form a set.
3 and the number of filters is
29

---

Published in Transactions on Machine Learning Research (09/2024)
Number
Color
Fill
Shape
Encoder
Encoder 1
Encoder 2
Encoder 3
Encoder 4
Encoder 5
red
empty
diamond
two
green
striped
oval
three
purple
solid
squiggle
Figure 17: The encoders learned in the MD-IPR layer represent the latent attributes in the Set cards, with different encoders seemingly specializing to encode one or two attributes.
30

---

Published in Transactions on Machine Learning Research (09/2024)
Number
Color
Fill
Shape
different
R(x, y) [PC2]
50
50
50
50
same
-50
0
50
50
50
550
50
-50
50
R(x, y) [PC1]
R(x. y) [PC1]
R(x, y) [PC1]
R(x, y) [PC1]
Figure 18: The relations learned by the MD-IPR layer encodes the latent relations underlying the Set task.
not set set
40
(R[g). re [PC2]
20
-20
-40
-20
40
60
80
(R[g), fl [PC1]
Figure 19: The relational convolution layer produces representations which separates 'scts' from 'non-scts!.
31


Reviews:
[{"review_id": "n5j7MG49g2", "reviewer": "Reviewer_gD6M", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\nThe work is well-written, easy to read, highly pedagogical. The figures and graphs are well-annotated and clear. \n\nThe work is also highly reproducible. with the majority of important hyperparameters exposed to the reader. \n\nExperiments are accompanied by bootstrap CI estimates and multiple runs per point, lending trustworthiness to specific numbers quoted in the manuscript.\n\n# Weaknesses\n\nThe main weakness of the paper lies in empirical evaluation.\n\nThe high-level problem is that broad generalizations about entire classes of architectures based on one hyperparameter set for each architecture, which are given for “Relational Games”  and “Set” in Tables 2 and 4 respectively. It is not stated how these hyperparameters were chosen, and critically (as is the primary interest for TMLR readers) whether these represent close to best-in-class choice for each problem setting.\n\nA more specific problem for is that the RelConvNet architecture is explicitly designed as a two layer architecture in all experimental settings, first with the ML-IPR layer, followed by the RelConv layer. In contrast to the Transformer model being compared to, which has a single layer in each setting, as to the GNN variants. This lends a systematic advantage to the RelConvNet architecture being proposed, particularly when considering that the class of functions transformers represent on inputs changes significantly as the number of layers increases https://arxiv.org/abs/2209.11895. Additionally it is known that for 12 layer transformer models, relational NLP tasks like Named Entity Recognition are solved very well (https://arxiv.org/abs/1810.04805). This can be done in 6 layers with distillation procedures (https://arxiv.org/abs/1910.01108).\n\nIt is also unclear if standard optimization procedure is being followed, which would include a learning warmup period, and some form of decay schedule (cosine or liner) to a constant. No weight decay is used in the experimental settings, yet there is strong overfitting phenomena being observed in Figure 7. Similarly in Figure 7, we see GCN significantly outperforms GAT in terms of training accuracy - this should only happen if the optimization of the GAT model is being done poorly.\n\nThe remaining weakness (though less major) lies in Section 3, which builds up the proposed architecture. This section has no citations in it, which can give the reader an impression that this is all completely new, and can make it challenging to situate the proposed architecture amongst existing architectures and methods. For example, when talking about building pairwise relations, it could be useful to link to the transformer paper https://arxiv.org/abs/1706.03762, and when introducing Equation 6, it would be useful to relate this to a PerceiverEncoder https://arxiv.org/abs/2107.14795 where the learnable group query vector is the Perceiver Latent variable.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work investigates the impact of inductive biases on solving tasks relational tasks - whose problem instances are inputs containing multiple objects which may or may not be related in some way, and the task is to predict this relation (or its absence).\n\nThe work develops an architecture called Relational Convolutional Networks, which is designed to compositional in inferred relations, i.e. it has a compositionally and relational inductive bias. This proposed architecture is contrasted with architectures that are stated as only compositional (Transformers, GNNS) or only relational (PrediNet, CoRelNet), but not both.\n\nThe authors conduct experiments which support that both inductive biases are required for solving relational tasks.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "# Required (critical)\n\n* Perform a reasonable hyperparameter sweep for the experimental section, critically including multilayer variants of all architectures, include the results of the hyperparameter sweep as an Appendix section. Optimization hyperparameters should be allowed to differ across methods. Optimization should be done using optimizers that use weight decay sensibly (e.g. AdamW), and a learning rate schedule should be used. The optimal weight decay may be zero, and other values should be investigated.\n* Update main text results with best-in-class values for each method. An optional search constraint could be considering total-compute tied variants in order to be able to compare algorithms like-for-like.\n* The hyperparameter search does not need to be exhaustive, but the results do need to support the primary claim of the paper (compositional and relational biases are both required for solving relational tasks) beyond reasonable doubt.\n\n\n# Recommended for strengthening but not critical \n\n* Remove instances of the word “novel” throughout.\n* Consider renaming “Relational Convolutional Networks” as the naming is close to Relational Graph Convolutional networks which may cause confusion. Alternatively, highlight these are not the same early on.\n* Clarify what is meant by hierarchical relation in the abstract - is it a hierarchy of element-wise relations or something else?\n* Introduction paragraph 1: “...essential to accurately capturing complex systems.” Add citation.\n* Introduction paragraph 1: “...building internal world models.” Add citation.\n* Introduction paragraph 2: “...essential to success of deep representation learning.” Add citation.\n* Introduction paragraph 2: “..flat first order architectures.” Add citation.\n* Introduction paragraph 2: Add explanation here why Transformer is not a compositional framework for learning hierarchical relational representations. Add relevant citations.\n* Bullet point end of page 1 “Grouping mechanisms”: Define “statistically intractable”.\n* Page 2\": \"SET game\". Add citation.\n* Page 2: \"Transformers\". Add citation.\n* Page 2: \"Graph Neural Networks\". Add citation.\n* Section 2: Where discussing the proposal to model pairwise relations between objects, explain why Transformer and GNNs are insufficient, as both of these models naively sound like they would do this. Alternatively if the thinking is consistent with prior methods this should be stated here, and then specifically what is new in this work should be called out.\n* Above Equation 2: Add elaboration why we want to promote weight sharing.\n* Equation 3: the i, j indices at this part of the manuscript feel unusual since there should be a symmetry over i, j as the filter acts on elements of a set. This may cause the reader to expect the i, j insides on the relational filters to be redundant. The issue is re solved by the attention mechanism in Equation 6 which restores the permutation equivariance. It would be good to add here some commentary around the symmetry at this point, and that the x_i x_j being discussed at this point are abstract, and may be choosable in a way that restores the symmetry.\n* Relate Equation 6 to the PerceiverIO Encoder with citations.\n* Explain to what extent Named Entity Recognition is or is not a relational task, and how BERT’s solving Named Entity Recognition is consistent with your results.\n* If after the hyperparameter sweep, GAT is still worse than GCN on training set, this should be explained.\n* Add the number of layers used for every architecture to the hyperparameter tables 2 and 4.", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "GXpXDglalm", "reviewer": "Reviewer_p6Dm", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- The paper is well written and clear.\n- The authors provide a detailed explanation on the motivation of the model architecture.\n- The proposed learning method is reasonable.\n- The experiment results appear to support the effectiveness of the method.\n\nWeakness:\n- Only results on synthetic tasks are provided, though this may not be a huge issue given the lack of suitable benchmark.\n- Ablation studies on each component are not provided (apologies if I missed it). \n- The originality over existing works are not immediately clear from reading the introduction.\n\nI am not sufficiently familiar with the literature and existing works to list other major weaknesses, and am open to hearing thoughts from other reviewers.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper develops a method, termed relational convolutional networks, to learn representations of hierarchical relations. The authors propose an operation that convolve graphlet filters to incorporate the relational patterns in groups of objects. The final method enables compositional relational modules. Experiment results on various tasks or datasets are provided.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Since the method involves several modules, ablation studies on the contribution of each module would be beneficial.\n- In the introduction, it is helpful to give a clear explanation of the originality of the work over existing ones (e.g., with respect to the problem setting considered or learning method).", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "QbqBFizwV2", "reviewer": "Reviewer_XLHi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Generally the paper is well written, easy to understand, proposes an interesting and novel method, and provides strong basic evidence that the method performs well and does as intended.\n\nBeyond the usual \"there could be larger scale results\", I think there could be more results demonstrating how the method works. The current investigative results very much pass the bar of TMLR to me, but I'd encourage the authors to dig even deeper (e.g. can the authors quantify and generalize what's in Figure 9? Compare it against other methods, including methods that do disentanglement?).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a novel type of DNN layer which performs _relational_ computations through inner products of embeddings. This is done by groups, and in a \"convolutional\" way, i.e. all groups are applied the same filters to. Fixed-sized groups are constructed via an attention mechanism which is regularized to have low entropy (i.e. picking objects rather than aggregating them).\n\nThe authors demonstrate good performance or relational tasks, as well as qualitatively different (and better) generalization properties on a set pattern matching task.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Things I'd like the authors to address:\n\n\n$\\left<x_1W_1,x_2W_2\\right>=x_2W_2W_1^\\top x_1^\\top = x_2 W x_1$ has interesting properties when $W$ is positive definite, and also it's interesting that if $d_{proj} < d_\\phi$ then $W_2W_1^\\top$ is a low-rank approximation of $W$. I wonder if the authors have thought about this?\n\nThe text mentions that pairwise computations are a limitation, but really the number of possible groups is $2^n$ (or $\\binom{n}{s}$ if we limit ourselves to size $s$ groups); isn't that the \"scary number\"? Transformers work \"just fine\" in $O(n^2)$ (and reasonable $O(n\\log n)$ versions exist).\n\nAbout the attention grouping, the text notes: \"learn $n_g$ groupings of objects, retrieving $s$ objects per group.\" I'm a bit ambivalent w.r.t. describing this as \"retrieving objects\". In the limit, the attention operation in (6) can just average all the objects' embeddings, did it really \"retrieve\" something or did it do some intermediate aggregation operation? I don't think the way the authors wrote it is necessarily wrong but it feels misleading. In the proposed architecture, the relational convolutions are applied on aggregates, not directly on (groupings of) objects. The authors propose adding entropy regularization on the attention, but this entropy or the attention values are not reported (Figure 6 has no colorbar; no way to know exactly what those colors mean). How does entropy change during training? Are different factors more or less effective?\n\nRegularizing attention entropy for sparsity is something that's been done before, please reference prior work.\n\nOne elephant in the room is what happens when objects are not neatly separated in the input space? or when the notion of what's an object or a collection of objects is blurry? Presumably this shouldn't be a problem, given the attention mechanism which is known to work even in e.g. vision tasks, but it would have been nice for the authors to train on even just a toy vision task (CIFAR100 SET?). As the authors point out in Limitations, this work is meant to lay the foundations, but this or experiments on >2 order interactions would add a lot to the work.\n\nI wonder if a regular deep ConvNet baseline would make sense? One thing that the proposed architecture does is apply local filters to inputs. Sure the inputs of those tasks to a ConvNet would be biased by their location within the input, but that should be something that the model should be able to easily overcome with sufficient depth. The \"Common CNN Embedder\" described in Table 2 feels incredibly shallow.\n\nThe authors do a classic mistake, introduce a regularization term and not report results without the term applied/different weights on the term. More generally, many design choices appear to not be justified by empirical results (and I suspect they are, but the results just aren't reported in the paper. \"Trust me it works\" is not sufficient).\n\nFinal point, I know it may be unfair to compare to highly optimized transformer CUDA kernels, but I couldn't find it mentioned how the method fares computationally in practice. Does it seem to scale well?", "broader_impact_concerns": "Not addressed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Given that the paper presents a novel framework for learning hierarchical relations, and provides a reasonable amount of empirical validation, it is safe to say that it makes a clear contribution that is technically sound. The reviewers were also unanimous in recommending it for acceptance.
Decision: Accept (poster)