Improving Out-of-distribution Generalization with Indirection Representations
Authors: Kha Pham
Hung Le
Man Ngo
Truyen Tran
Venue: ICLR 2023 poster (2023)
Keywords: out-of-distribution generalization
indirection
representation

Abstract: We propose a generic module named Indirection Layer (InLay), which leverages indirection and data internal relationships to effectively construct symbolic indirect representations to improve out-of-distribution generalization capabilities of various neural architectures. InLay receives data input in the form of a sequence of objects, treats it as a complete weighted graph whose vertices are the objects and edge weights are scalars representing relationships between vertices. The input is first mapped via indirection to a symbolic graph with data-independent and trainable vertices. This symbolic graph is then propagated, resulting in new vertex features whose indirection will be used for prediction steps afterward. Theoretically, we show that the distances between indirection representations are bounded by the distances between corresponding graphs, implying that unseen samples with very different surface statistics can still be close in the representation space to the seen samples if they share similar internal relationships. We demonstrate that InLay is consistently effective in improving out-of-distribution generalization throughout a comprehensive suite of experiments, including IQ problems, distorted image classification, and few-shot domain adaptation NLP classification. We also conduct ablation studies to verify different design choices of InLay.

Published as a conference paper at ICLR 2023
IMPROVING OUT-OF-DISTRIBUTION GENERALIZATION WITH INDIRECTION REPRESENTATIONS
Kha Pham 1 Hung Le Man Ngo 3, Truyen Tran
Applied Artificial Intelligence Institute, Deakin University
2 Faculty of Mathematics and Computer Science, VNUHCM-University of Science (phti, thai. le, truyen. tran @deakin. au, edu. vn,
ABSTRACT
We propose a generic module named Indirection Layer (Inlayy) which leverages indirection and data internal relationships to effectively construct symbolic indirect representations to improve out-of-distribution generalization capabilities of various neural architectures. InLay receives data input in the form of sequence of objects, treats it as complete weighted graph whose vertices are the objects and edge weights are scalars representing relationships between vertices. The input is first mapped via indirection to a symbolic graph with data-independent and trainable vertices. This symbolic graph is then propagated, resulting in new vertex features whose indirection will be used for prediction steps afterward. Theoretically, we show that the distances between indirection representations are bounded by the distances between corresponding graphs, implying that unseen samples with very different surface statistics can still be close in the representation space the seen samples if they share similar internal relationships. We demonstrate that InLay is consistently effective in improving out-of-distribution generalization throughout a comprehensive suite of experiments, including IQ problems, distorted image classification, and few-shot domain adaptation NLP classification. We also conduct ablation studies to verify different design choices of InLay
INTRODUCTION
There have been several evidences showing that deep learning models may fail drastically in out-of- distribution (OOD) testing circumstances (Geirhos et al., 2018; Keysers et al., 2020). One reason widely agreed upon that neural networks tend to learn surface statistics of data (Lake al., 2017) and thus can not generalize to samples with different statistics. On the other hand, humans excel at generalizing, and it has been long believed that the ability to think a symbolic way is the key for humans quickly adapt to situations (Mitchell, 2021). A powerful concept that can bridge concrete data and symbols is indirection, which binds two objects together and uses one to refer to the other. In computer science, indirection widely used via pointer: data bound its memory address, and programs use the memory address to refer to that data.
The capacity draw analogies is yet another trait that facilitates human generalization. Several cognitive science theories have been proposed to explain analogy, and the Structure-Mapping Theory (SMT) (Gentner, 1983) is one of the most successful among them. SMT argues that not object attributes but the relationships between them are transferred in an analogy. For example, the hydrogen atom is analogous to the solar system not because they share the same sizes or temperatures because they both have entities revolving around center due to the attractive force. This suggests that internal relationships of a situation contain essential information for generalization. In this paper, we propose method that simultaneously leverages indirection and data internal relationships to construct indirection representations, which can be interpreted as symbolic representations that respect the similarities between internal relationships. For instance, two IQ problems with similar hidden rules (i.c., similar internal relationships) should have similar indirection representations, though they contain completely different shapes images.

---

Published as a conference paper at ICLR 2023
conceete represettation
dota groph
symbollic proph
InLay indirection represeniationn
indirection
propagation
uppralor
Figure 1: Indirection Layer. Concrete data representation is viewed as a complete graph with weighted edges. The indirection operator maps this graph to symbolic graph with the same weight edges, however the vertices fixed and trainable. This symbolic graph is propagated and the updated node features are indirection representations. Different conerete inputs may share the same indirection representations their corresponding graphs have the same adjacency matrices. This illustrates the core idea of InLay: constructing indirection representations by transferring internal relationships through indirection.
To this end, we implement our method in the form of a generic module named Indirection Layer (InLay), which can construct indirection representations from either encoded or raw low-sensory data and can be equipped with various models improve their OOD generalization capabilities. InLay receives a sequence of objects as input and produces sequence with the same length including associated indirection representations. The input sequence is viewed as a complete weighted graph where each edge weight represents the relationship between two corresponding objects, and thus the adjacency matrix of this graph captures the internal relationships of the input. The core operation of InLay consists of two steps: indirection and graph propagation (see Fig. for illustration).
The input is first processed through indirection to transfer all edge weights to another symbolic graph whose vertices are Kata-independent and trainable. This symbolic graph is then propagated, resulting in updated vertex features as the indirection representations of the input. These indirection representations are used new representations for prediction steps afterward.
We show both theoretically and empirically that Inlay can help to improve OOD generalization. Theoretically, we show that Inlay indirection preserves internal structures of graphs, and the distances between indirection representations are bounded by the cut distances between corresponding graphs. Thanks to these theoretical properties, the indirection representation of new data instance can be located near a seen one if they share similar internal relationships (although the surface features may be entirely different), thus the two instances have a higher chance of being interpreted similarly. Empirically, we show that InLay consistently helps different models to improve their OOD general- ization capabilities in a comprehensive suite of experiments involving numerous datasets and OOD scenarios, including IQ problems with unseen objects and unseen rules, distorted image classification, and sew-shot domain adaptation NLP classification. We also conduct ablation experiments to study the necessity of different design choices in InLay and provide practical analysis the success of InLay.
METHOD
We introduce our main contribution, namely the Indirection Layer (InLay). InLay takes a sequence of objects as input and transforms the sequence into a new indirect graph-structured representation. Concretely, let X = (2,,,2,... ................................ 2x)) .x)) E & be the input sequence for InLay, where k is the number of objects and each x, E TRn represents an object. For example, an object may be either an image in IQ problems, or a patch of image in image classification task, or paragraph in few-shot NL.P classification task (see Section 4). To better exploit data internal relationships, we treat each input sequence as a directed complete weighted graph (with no self-loop) whose vertices represent the objects and edges represent relationships as scalars in [-1, 1]. Specifically, for each sequence X, we denote Gx as its corresponding graph. We define G& to be the space of all directed weighted complete graphs G with & vertices and edge weights in [-1, 1]. From now on, we will only write G instead of G x when it is not necessary to specify X, and we denote Ag as the adjacency matrix of G. This adjacency matrix captures the internal relationships of the corresponding data sequence.
Remark 1. (Canonical indexing assumption) As the set of graph vertices may permute, a graph G with & vertices may not have an unique adjacency matrix. To assure the well-definedness of Ag. we assume that (when computing the adjacency matrix) the i-th vertex represents the i-th element of the input sequence. We show in Appendix C that the indirection representations are still maintained the canonical indexing assumption is not obeyed.
2

---

Published as a conference paper at ICLR 2023
We aim to learn suitable representations for the graph such that the internal relationships of the input sequence can be transferable to novel settings. To this end, we contribute the Indirection Layer (InLay), which leverages indirection and data internal relationships to construct indirection representations. Inl.ay is generic and flexible module that can be equipped into different models to construct indirection representations from either encoded data raw low-sensory data (e.g, for the case of Vision Transformer; see Section 4.2) in two steps: indirection and graph propagation.
Indirection
For each X, the adjacency matrix AGx E & of Gx represents the internal relationships between objects in X. Each component oN of AGx is computed as a. = tanh
Q 2"=..K' if + j and v4n
4i = 0 i = j. where is the inner product and Q, K E IR are trainable weights that project o;; and zi onto higher dimensional space that a linear kernel may represent the relationship between 3; and J.4- The choice of tanh as a non-linear transformation is important: it maps the dot products to [-1, 1]. allowing InLay to possess nice theoretical properties regarding boundedness of distances (see Section 3); and, tanh allows negative similarities between objects, which may help to represent opposite relations, e.g., translations to the left and to the right. See Section 4.1.1 and Appendix G for experimental details.
In indirection, each object is bound a symbol. We denote by V = (u]jdd , 2x E Rxx to the set of symbols where each o!!ad E I is data-independent and trainable. Let Gl be the subset Gy that consists of all graphs whose set of vertices is /innd (i.e., each vertex represents some uf and no two vertices represent the same o/ The space Gimll can be interpreted as the space of symbolic graphs with fixed vertices. We define the indirection operator as follows.
Definition 2.2. Given an input sequence X = (I), Z2,..., .xk) Gk. the indirection operator I is a mapping from 9k Gidd that maps Gx to I(Gx) that AGx AI(Gx) and the i-th vertex of I(Gx) represents ujndd
,k)
and its corresponding graph Gx E
Remark 2.3. Definition 2.2 is introduced in the when the canonical indexing assumption (see Remark 2.1) is obeyed. The vertex order emerges when computing the adjacency matrix. more general definition is given in Appendix C.
The indirection operator maps each object x; its associated symbol u.th while assuming the pairwise relationship between afnd and ujnn is the same one between m; and z; (see Fig. 1). That is, Z ignores the concrete features of objects but still maintains the relationships between them.
Graph propagation
After indirection, each data graph G is mapped to a symbolic graph I(G). This operation can be interpreted as follows: at first, edge weights of I()) are unspecified; then the indirection operator I assigns edge weights from the data to I(G). Once receiving this information from data, I(G) propagated and the updated vertex features are indirection representations of the input sequence. Formally, for an input sequence X, if we denote rx to be the indirection representations of X, then rx = AGx yind This symbolic r'x used as new representation for X for prediction steps afterward.
To summarize, for each input sequence X. InLay constructs associated indirection representation rx:
tanh (XQ(X))
Vind
(1)
V4n
This equation is closely related self attention, except for three points: 1. data are projected onto a higher dimensional space by matrix multiplying with Q and K; 2. the softmax operator is replaced by tanh; and most importantly, 3. the value Alnd is not computed based on the data X. While the first two differences empirically enhance InLay's Lays performances (see Section 4.4). the third one stands for the core idea of indirection InLay. An ablation study on /ind will also be conducted in Section 4.4 to demonstrate the role of each element.
Initialization of yind may greatly affect the overall performance. To reduce this effect, we replace Vrind in Eq. (1) by (VVinl), where g/ R + R" is trainable 2-layer neural network applied to of Vind We also use multi-heade to compute the adjacency matrix so that local information of feature vectors is better utilized. The number of heads is tuned for each specific task.
3

---

Published as a conference paper at ICLR 2023
3
THEORETICAL ANALYSIS
3.1
BOUNDEDNESS WITH RESPECT TO THE CUT DISTANCE
Graph spectrum and Laplacian are important graph characteristics that can be computed entirely by graph adjacency matrices. From Definition 2.2, it follows that the indirection operator '. preserves graph spectrum and Laplacian, which means I preserves graph internal structure. To some extent, this agrees with the Structure-Mapping Theory (Gentner, 1983), which states that not the attributes but the internal relationships are transferred in an analogy. In other words, learning internal relationships may already be enough to capture the essence of situation. Further details for the Sruucture-Mapping Theory will be given in Section 5.
Next, investigate how distances between graphs may constrain distances between indirection representations. Before defining graph distance, we define isomorphism between graphs in Gx-
Definition 3.1. Given two graphs G = (V, F) E 9; and G' (V' FE' E GR with associated adjacency matrices Ag = ( and Agr = (d'y)..TT. We say G and G' are isomorphic, denote by G = G', if there exists bijection @ V - V' so that asj = d (((0)) for every i, V.
Two isomorphic graphs can be interpreted as being identical up to isomorphism, and thus graph distance defined on Gy should respect this property. i.c., the distance between two isomorphic graphs is O. One such distance is the cut distance d (Borgs et al., 2008), which is a useful tool to compare similarities betwen structures (Liu et al., 2018), and also for studying the convergence of sequence of graphs (Borgs et al., 2008). A formal dcfinition for om is given in Appendix A.
follows from the definition of ôn that 8n, G*) = if and only if G is isomorphic with G'. Moreover, if G1 = G2 then (G G") = ( G") G¹) for any G.. Since G = I(G), the indirection operator Z preserves du distance, i.e., GG) I(G')) for every G, G" E Gk-
We have shown that the indirection operator I admits invariant properties with respect to the graph spectrum, Laplacian and the cut graph distance &g. The following result shows that the distances between indirection representations are bounded by cut distances between corresponding graphs For each G E Gk. we denote TG A to be its associated indirection representation.
Theorem 3.2. For any two graphs G 9k and G' E Gk. the following inequality holds:
Ira-ralle lla k (2+ 12+ (G)
| 11o0
(2)
where |1-1loo is the matrix infinity norm (see Definition A.3 in Appendix A).
Proof. See Appendix B.
Note that even when (G) 0, ra may still be different from ray. This is because by design, InLay also takes into account the ordinal information of input sequence, which may be important in some specific use cases, e.g., when the input is sequence of image patches. Theorem 3,2 shows that G and G' are close, their indirection representations will not be far away from each other as well. This is an important property since the original vertex representations of G and G' may arbitrarily far though G and G" are isomorphic, e.g., two IQ problems with the same hidden rules but different images may be represented very differently. Theorem 3.2 also shows the necessity of training Vnd to obtain appropriate | Iloo: if || | || is too large, the bound in Incq. (2) is loose; conversely, [|Vind ooo is too small, the bound may be too strict so that indirection representations are not well separated enough. An empirical ablation study on Find will be given in Section 4.4.
3.2
CONNECTION BETWEEN INLAY AND STRUCTURAL ANALOGY
Current machine learning methods follow the manifold hypothesis and tend to interpolate on the learned manifold during testing. This ability of interpolation is usually referred as making value analogies, i.e., making analogies between data features. However, value analogy may not be enough in more extreme generalization cases when surface statistics of testing samples vastly differ from that of training data. Structural analogy is believed to be necessary for ML models to reach higher levels of generalization (Chollet, 2021). By making structural analogy, concrete information is partly ignored while structural information is compared, e.g., two IQ problems with the same hidden rules
4

---

Published as a conference paper at ICLR 2023
Rotation
Problem
Encoder
O
Answer Set
Encoded representations
K
?
In ay
Indirection representations
#2
P
+ D
Prediction model
B
C
Prediction
(a)
(a) Overall architecture of prediction model when equipped with InLay. (b) Left: A problem in FINE dataset with images from the Omniglot dataset and hidden rule is 90-degree rotation. Right: A Raven's ' Progressive Matrix problem from RAVEN dataset. Images adapted from original papers.
Figure 2:
are structurally analogous even though the data (e.g., images) are entirely different between the problems. In InLay, the structural information maintained in the form of adjacency matrices, which are computed based on data features. To some extent, InLay can be interpreted as a hybrid method of value analogy and structural analogy.
When it comes to structural analogy, one might need a metric to measure the similarities between structures. Among different metrics, the cut distance å is one of the few methods able to compare directed weighted graphs (Tantardini al., 2019). For instance, recent work by Liu et al. (2018) leverages the cut distance to compare complex networks, including artificial networks and real networks of chemical molecules. Theorem 3.2 draws a connection between InLay and the cut distance by showing that the distances between indirection representations are bounded by corresponding cut distances, and thus emphasizes the structural inductive bias InLay brings into deep learning models.
EXPERIMENTS
In this section, we conduct several experiments with different scenarios of OOD generalization to show that InLay can adapt to various models and improve their performances on various datasets. The OOD testing scenarios include IQ problems with unseen images and unseen rules, distorted image classification, and domain adaptation on few-shot NLP classification, all of which require the ability to understand the problem in systematic and symbolic way in order generalize OOD circumstances. Throughout these experiments, we show that InLay consistently helps models to perform better. We also provide ablation study the necessities of different design choices in Inlay, as well as a practical analysis of the success of Inl.y
InLay constructs indirection representations from either encoded model equipped with an encoder, InLay will sit between the encoder and prediction to transform encoded representations to indirection representations (see Fig. 2a for an illustration). When there is no encoder, e.g., when the prediction model is Vision Transformer, InLay directly constructs indirection representations from raw data. To be fair when comparing, models with or without InLay are all trained with the same training settings, including batch size, learning rate, number of training iterations, optimizer, etc., and we only report test results after the last iteration. Average results are reported in the main text; full results with standard deviation are given in Appendix D. More training details are also given in Appendix K.
data. If the prediction
In practice, we optionally use context normalization (Webb et al., 2020a) to further improve InLay. If context normalization is applied in InLay, there will two such layers: one to normalize the original representation X, and one to normalize the symbolic representation rx.
4.1 OUT-OF-DISTRIBUTTON IQ PROBLEMS
IQ problems are powerful testbeds for OOD generalization capability of deep learning models. Despite their simple appearances, IQ problems are challenging in the sense that they require models to understand the hidden nules instead of just surface features to solve new problems with unseen objects or even unseen (but related) rules. There have been evidences showing that current deep learning models may fail when facing problems with unseen objects (Webb et al., 2020b). In this experiment, we show that models coupled with InLay achieve better performances on two IQ datasets: FINE (Pham et al., 2022) and RAVEN (Zhang et al., 2019). Examples given in Fig. 2b.
5

---

Published as a conference paper at ICLR 2023
Train set Test set
CIFARTOO
MNIST
Omniglot
CIFARI00
Trans.
Rot.
Shear
Scale
Trans.
Rot.
Shear
Scale
NTM PrediNet
25.5/56.9
27.1/31.4
29.8/58.5
30.3/61.0
3
30.0/34.5
29.6/56.0
31.9/48.7
26.7/28.5
25.5/28.3
25.6/29.0
26.4/29.9
27.5/31.6
26.8/27.8
26.4/28.4
33.6/35,9
RelationNet
25.4/39.3
25.0/34.0
25.1/39.8
24.7/50.2
25.6/45.5
25.6/35.2
25.0/43.4
26.8/44.8
Transformer
26.9/63.3
27.2/40.4
28.3/65.3
30.6/62.0
37.8/63.9
32.0/36.1
30.2/53.5
29.2/48.1
Table 1: Average test accuracy (%)
without/with InLay on FINE dataset.
Train configuration
Up-Down
3x3Grid
Out-InGrid Out-InCenter
Average
Test configuration
Left-Right
2x2Grid
LSTM Transformer
28.8/43.9
19.5/25.1
42.1/48.6
30. 1/39.2
15.2/56.7
13.6/26.0
16.6/44.7
15. 1/4.55
RelationNet
12.7/58.5
12.4/28.9
12.3/51.7
12.5/46.4
PrediNet
13.7/16.5
13.6/14.3
14.2/15.9
13.8/15.6
Table
Average test accuracy (%) without/with Inl.y on RAVEN dataset.
4.1.1
FINE DATASET
FINE dataset consists of IQ problems with geometric transformations as hidden rules. To succeed in this dataset, models should treat objects as symbols and learn the relationship between these symbols. Here we consider one of the most challenging OOD scenarios: test problems include unseen objects and unseen rules. To be specific, images in train and test problems come from different datasets (train on CIFAR100 (Krizhevsky. 2009)- test on Omniglot (Lake et al., 2015) or train on MNIST (LeCun et al., 2010) - test on CIFAR 100), so the models need to understand the hidden rules instead of image features to solve test problems. Rules in test problems are also unseen during training; for instance, we train on IQ problems with rotation angle less than 180" and test on ones with rotation angles more than 180%; similarly, for translation, we train problems with translation to the left and test on ones with translation to the right. More details of other transformations will be given in Appendix. Models to be considered include the Neural Turing Machine (Graves et al., 2014), PrediNet (Shanahan et al., 2020), Relation Network (Sung et al., 2018), and Transformer (Vaswani et al., 2017), all of which have been shown be effective on different relational reasoning tasks. All models, with without InLay, are equipped with context normalization. Results are reported in Table 1.
Overall, models perform better when equipped with InLay, even in very extreme cases when models are trained on grayscale MNIST images and tested on RGB CIFAR 100 images. This shows clear advantage of InLay: indirection maps concrete features to symbolic space spanned by Vind thus helping models to be less dependent on concrete data. It can also be observed that PrediNet equipped with InLay improves less than other models. This is because PrediNet also constructs new symbolic data representations, and thus contains the inductive bias of symbolic representations itself. Again, this emphasizes the necessity of including symbolic inductive bias to improve OOD generalization.
4.1.2 RAVEN DATASET
RAVEN dataset (Zhang al., 2019) is inspired by Raven's Progressive Matrices, which challeng- ing IQ tests for humans. RAVEN IQ problems are complex in the sense that a single problem may consist of different shapes, each of which follows different rule. Inspired by the original paper, we conduct experiments to test models' capabilities to generalize on problems of unseen configurations. Specifically, we train and test on problems of different but related configurations. For example, Up-Down problems are related to Left-Right ones in the sense that Left-Right configuration can be viewed as a 90-degree "rotation" of Up-Down. In this experiment, the three train-test configuration pairs are UpDown-LeffRige normalization in all models. We further apply Dynamic Residual Tree as proposed in the original paper to capture the inherent structure of Raven's Progressive Matrices. Results are reported in Table A similar pattern can be observed: models equipped with InLay tend to perform better. In average, InLay helps improve LSTM by 9.1%. Transformer by 27. 27.4%, RelationNet by 33.9%, and PrediNet by 1.8%. This can be well explained by Theorem 3.2 and Theorem B.1 in the theoretical analysis: although the test configuration is unseen, it is still related to the train configuration and thus Lny Ly representations for test problems may still be close to ones of train problems. This helps models to have better chance to draw analogies between observed and unobserved configurations.
1.3Grid--xxGrria and ButlnGrid-Qutlneeen
We also apply context

---

Published as a conference paper at ICLR 2023
No data augmentation
With data augmentation
Dataset
Rot90
Grayscale Jitter
Avg.
Rot90
Grayscale Jitter
Avg.
SVHN
11.8/12.5
86.9/91.8
87.2/91.6
62.0/65.3
17.3/19.1
92.9/94.7
91.8/93,4
67.3/69.1
CIFARIO
25.7/27.9
48.3/62.7
46. 46.6/59.7
40.2/50.1
24.2/27.3
54.2/69.2
50.2/68.4
42.2/55.0
CIFAR 100
13.4/15.0
16.4/23.9
18. 1/25./
16.0/21.3
11.1/14.0
18.5/27.8
19.4/28.7
16.3/23.5
Table 3: Average test accuracy (%) without/with InLay on OOD classification task with VIT.
ProtoNet
SNAIL
GNN
MTB
5-way-1-shot
64.7/65.4
38.6/60.6
36.7/63.1
1/6.96
10 wsy---
49.1/41.7
17.3/34.9
27.1/43.3
52.9/54.1
Average
56.9/53.6
28.0/47.8
31.9/53.2
59.5/61.5
Table 4: Average validation accuracy (%) without/with InLay on FewRel 2.0.
4.2 OUT-OF-DISTRIBUTION CLASSIFICATION
Humans can consistently recognize objects in different positions, angles, or colors. Current deep learning models may not. Geirhos et al. (2018) show that when test images are injected with different kinds of distortions other than ones in training, deep neural networks may fail drastically on image classification tasks. We take inspiration from that result and conduct similar experiments to test whether InLay can help models improve their performances on OOD image classification tasks. We use vanilla 6-layer Vision Transformer (ViT) (Dosovitskiy et al., 2020) as the base model and test it, with or without InLay, on different datasets, namely the SVHN (Netzer et al., 201 I) and CIFAR108 100 (Krizhevsky, 2009). The models are trained on original images in cases: with and without data augmentation, and tested on images with various distortions, including image transformation (90-degree rotation) and color transformations (color jitter, grayscale). In the case of data augmentation, we use all other distortions for augmentation except one used for testing. If InLay is equipped, we divide each 32 x 32 image into overlapping patches of size 8 and stride 4. These patches are vertices of the graph that represents the current image. The patch indirection representations are reassembled form new image of the same size as the original one. This new image is then fed into ViT. Context normalization is not used in this task.
Results are shown in Table 3. As expected, VIT performs poorly when the images are distorted. In average, InLay helps to improve its performance by 3.3% on SVHN, 0.9% on CIFAR 10, and 5.3% on CIFARIO0 when there is no data augmentation and 1.8% on SVHN 12.8% on CIFARIO. and 7.2% on CIFAR 100 when data augmentation is included. We can also observe that 1. VIT with data augmentation but without InLay is still mostly worse than ViT with InLay but without data augmentation; and 2. InLay helps improve VIT in both cases of with and without data augmentation. Note that it should not be interpreted that adding InLay to ViT is equivalent to adding a Transformer layer. Empirically, performances of 7-layer ViT only slightly differ from 6-layer ViT (see Appendix E), while it is clear that adding InLay may boost performances significantly.
4.3
FEW-SHOT NLP DOMAIN ADAPTATION
Humans can handle NLP classification tasks given a small number of examples. While humans can quickly adapt to such new scenarios, deep language models may not. Gao et al. (2019) proposed the FewRel 2.0 dataset that consists of few-shot NLP classification tasks, where the domains of train and test tasks vastly differ. Specifically, the training texts are taken from the Wikipedia corpus, while texts for testing originate from the PubMed and UMLS databases that contain large amounts of biomedical literature and sciences. This creates a big obstacle for few-shot language models to adapt to: their performances drop drastically as reported in the original paper.
Inspired by this result, we conduct an experiment on FewRel 2.0 dataset to show that InLay works well for language models. Different few-shot models, including Prototypical Network (Snell et al., 2017). SNAIL (Mishra et al., 2017), Graph Neural Network (Garcia and Bruna, 2017), and MTB (Soares et al., 2019), are trained with BERT encoder (Devlin et al., 2018) on 5-way-1-shot and 10-way-1-shot tasks. All models are equipped with context normalization. Since the test set is not provided for the public, we only report the test results on validation set, which shares the same domain the test set. Results are shown in Table 4. Except ProtoNet, InLay helps other models improve: 19.8% for SNAIL, 21.3% for GNN, and 2.0% for MTB in average. The case of ProtoNet can be explained as follows: ProtoNet depends the distances between data instances, which is similar to the spirit of our InLay Because ProtoNet already has this inductive bias, InLay can not help to improve it.
7

---

Published as a conference paper at ICLR 2023
Sepenceet HARSA S0LESS
SVHN
CIFAR1O
CIFAR100
60
1.4
50
Text Acouney
4.4
-0
Relente
1:2
20
0.31
50
nore
no nlay
no mLa
Figure 3: (a) Ablation study. Test accuracies of ViT equipped with an on grayscale images when design
choice of Iny is replaced removed. (b) Relative distances between original and distorted representations with and without InLay in different testing cases.
4.4
ABLATION AND ANALYSIS
4.4.1
ABLATION ON INLAY DESIGN CHOICES
We conduct ablation experiments to study the necessities of different design choices of InLay. All experiments are conducted on OOD classification task (see Section 4.2) with ViT and grayscale testing images. In each experiment, we modify one design choice and keep others fixed. We consider three main design choices: activation function to compute adjacency matrices, projection on higher space compute dot products, and trainability and data-independence of Vind We also consider the case when the indirection representations are treated as relative positional encoding to be added to the original input. Results are reported in Fig. 3a.
In the ablation for activation function, replacing tanh with softmax significantly decreases the performance, while the result when no activation applied is only slightly lower. This is because softmax does not allow negative values; moreover, it imposes the constraint of summing-to-ore on edges of graph, which is unnecessary in the theoretical analysis. On the other side, projecting data onto higher dimensional spaces also plays vital role in InLay as it helps linearize the relations between objects so that dot products may manage to represent those relations, and not doing so may lead to drastic drop in performance. Maintaining trainable set of symbols yinnd is beneficial for InLay, and the performances with randomly sampled /ind from Gaussian tend to decrease when the standard deviations of the Gaussians increase. This be explained by Theorem 3.2: increase of standard deviations leads to bigger || b| which loosens the bound in Ineq. (2). Keeping Vind data-indar cata-independent is also important, and treating the indirection representations relative positional encoding is not efficient.
4.4.2 FURTHER PRACTICAL ANALYSIS
Besides theoretical analysis in Section 3, we further provide practical evidence showing why InLay may help models to generalize better. We again use the OOD classification tasks as a testbed. short, we would like to show that InLay reduces the distance between image and its distorted version, thus models may recognize the similarity between the two images more easily. Using the absolute distance may not be fair metric since scaling two vectors by the same factor may already reduce the distance between them. Instead, we compute the relative distances between vectors, i.c. the relative distance between u and v is 2 x |u-ell
|| Relative distances between images and their distorted versions are computed in two cases: with InLay and without InLay. Results are shown in Fig. 3b, and it is clear that the relative distances in InLay case are lower than those without InLay. This can be partly explained by Theorem 3.2: the original image corresponds with G, and the distorted image corresponds with G". Since the distorted image is closely related to the original one, the distance between their corresponding graphs is small, and thus the distance between their indirection representations na and TG also tends to be small according to Ineq. (2).
5 RELATED WORK
Systematic generalization has attracted attention recently in the deep neural networks community. One approach is to train a mixture of experts as functional modules, and these experts either compete (Parascandolo et al., 2018)
composed by attention mechanism (Rahaman al., 2021) to solve a task. Fedus et al. (2021) proposed the Switch Transformer to simplify routing algorithms in mixture-of-experts models to reduce communication and computational costs. Another approach is
8

---

Published as a conference paper at ICLR 2023
to design architectures that mimic human's ability to think and reason sequentially. One well-known early model following this approach is the Module Network (Andreas et al., 2016) which attacks the image-QA tasks by parsing the query into sequential sub-queries, each of which is solved by a module in the form of neural networks. The MAC recurrent network (Hudson and Manning, 2018) and the Neural State Machine (Hudson and Manning, 2019) follow similar idea, however, in MAC the query is explicitly and expressively decomposed by a sequence of RNN-type MAC cells, while Neural State Machine relies on probabilistic graphs representing underlying semantics to reason sequentially. Recently, Wei et al. (2022) proposed the idea of chain of thought to improve the ability of large language models to perform complex reasoning. Our InLay also follows the idea of injecting symbolic inductive bias, however, we focus representations instead of functional modules. Models equipped with Lny can be interpreted as 2-step reasoning: the low-level sensory data is first represented symbolically by Inlay, then processed by the following models.
Indirection one of the most useful ideas that has been long applied in different areas of computer science. One of the most illustrative examples for indirection is the concept of pointer. Recently, there have been works leveraging indirection to improve generalization capabilities of deep learning models. ESBN (Webb et al., 2020b) uses an RNN controller to sequentially produce a symbolic key for each object and reasons on keys only. The keys in ESBN are computed based on the controller and similarities between objects, which is similar to our Inl.yy; however, the keys are produced sequentially, which may increase the computational cost. Recently, Pham et al. (2022) proposed FINE, which is a fast-weight approach that utilizes indirection on functional spaces and has achieved promising performances on different OOD testing scenarios of IQ problems.
The idea of transferring relationships in InLay is inspired from the Structure Mapping Theory (SMT) (Gentner, 1983), which is a revolutionary theory of analogy in cognitive science. Analogy is a vital concept to explain human cognition, and it has been long argued that analogy-making underlies humans' ability to flexibly adapt to new situations (Gentner et al., 2001). Before SMT. it had been assumed that in a strong analogy, the base and the target should share several attributes in common (Tversky, 1977). SMT, in contrast, argues that not attributes but the relationships between objects are transferred in an analogy; in other words, the essence of a situation lies in internal relationships instead of concrete attributes. From this point of view, the theoretical results in Section 3 can be interpreted as a justification for SMT in the case of InLay: transferring relationships only does not lose significant information such as graph characteristics and graph topology.
is also worth noting that from few-shot learning perspective, our InLay can be categorized as fast-weight (Malsburg, 1994) embedding learning model, in which the attentional weight Agx is computed on-the-fly and the indirection representation r'x is computed accordingly.
The trainable set of symbols Vinnd can be interpreted positional encodings, and the output r'x of InLay is a relative positional encoding regarding the input X. The idea of relative positional encoding (Shaw et al., 2018), as a replacement for the absolute positional encoding in Transformer, has been widely investigated and several variants have been proposed (Dai et al., 2019; Huang et al., 201 8). worth noting that the relative positional encoding is added to the original input, while rx in InLay plays the role of the input for the following model. InLay thus should not be considered as a variant of a Transformer layer or relative positional encoding; instead, its design highlights the idea of indirection and symbolic representations.
6 CONCLUSION
In this paper, we propose InLay as a separate module that can be plugged into different models to improve OOD generalization. InLay leverages the idea of indirection redirect data representation based on a trainable set of symbols. Viewing each data point as a complete weighted graph, we prove theoretically that InLay preserves graph internal structure and graph topology, and the distances between refined representations are bounded by the distances between corresponding graphs. We show the effectiveness of Inlay through a comprehensive suite of experiments, including different OOD testing scenarios IQ problems, distorted image classification, and few-shot NLP domain adaptation classification tasks. We also conduct ablation experiments to study necessities of different design choices in InLay, as well as further practical analysis on the success of InLay.
InLay opens up several future directions. From the theoretical side, it is worth investigating how the manifold containing original data representations is transformed during InLay, and why this manifold transformation can help generalization. From the practical view, stacking multiple InLay's 's to form a hierarchical indirection network is promising idea.
9

---

Published as a conference paper at ICLR 2023
REFERENCES
Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Neural module networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 39-48, 2016.
Christian Borgs, Jennifer T Chayes, László Lovász, Vera T Sós, and Katalin Vesztergombi. Conver- gent sequences of dense graphs Subgraph frequencies, metric properties and testing. Advances in Mathematics, (9)16)8111-888) 2008.
Francois Chollet. Deep learning with Python. Simon and Schuster, 2021.
Taco Cohen and Max Welling. Group equivariant convolutional networks. In International conference on machine learning, pages 2990-2999, PMLR, 2016.
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc Le, and Ruslan Salakhutdi-- nov. Transformer-xl: Attentive language models beyond fixed-length context. arXiv preprint 19X1::9901.02600 2019.
Jacob Devlin, Ming-Wor Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:/810.0000 048000 2018.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition scale. arXiv preprini 0rXiv:2010.11990 2020.
William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity, 2021.
Tianyu Gao, Xu Han, Hao Zhu, Zhiyuan Liu, Peng Li, Maosong Sun, and Jie Zhou. Fewrel 2.0: Towards more challenging fhw-shot relation classification. arXiv preprint arXiv: arXiv:/910.07124, 2019.
Victor Garcia and Joan Bruna. Few-shot learning with graph neural networks. arXiv preprint arXiv:1711.04443 2017.
Robert Geirhos, Carlos RM Temme, Jonas Rauber, Heiko H Schütt, Matthias Bethge, and Felix Wichmann. Generalisation in humans and deep neural networks. Advances in neural information processing systems, 31, 2018
Dedre Gentner. Structure-mappingg A theoretical framework for analogy. Cognitive science, 7(2): 155-170, 1983.
Dedre Gentner, Keith J Holyoak, and Boicho N Kokinov. The analogical mind: cognitive science. MIT press, 2001.
Perspectives from
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. ArXiv, abs/1410.5401, 2014.
Cheng-Zhi Anna Huang, Ashish Vaswani, Jakob Uszkoreit, Noam Shazeer, Curtis Hawthorne, AM Dai, MD Hoffman, and D Eck. Music transformer: Generating music with long-term structure (2018). arXiv preprint arXiv:1809.044
2018.
Drew A. Hudson and Christopher D. Manning. Compositional attention networks for machine reasoning. ICLR, 2018
Drew A. Hudson and Christopher Manning. Learning by abstraction: The neural state machine. In NewrIPS, 2019.
Daniel Keysers. Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, et al. Measuring compo- sitional generalization: A comprehensive method realistic data. International Conference Learning Representations, 2020.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv: 1412.6980 2014.
10

---

Published as a conference paper at ICLR 2023
A. Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 350(6266): 1332 1-32-133,, 2015.
Brenden M Lake, Tomer D Ullman, Joshua Tenenbaum, and Samuel Gershman. Building machines that learn and think like people. Behavioral and brain sciences, 40, 2017.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yanm.. www.:lewwwn....eee.eeeeee cow/exdb/mniist 2, 2010.
Qun Liu, Zhishan Dong, and En Wang. Cut based method for comparing complex networks. Scientific reports, 8(1):1-11, 2018.
Christoph von der Malsburg. The correlation theory of brain function. In Models of neural networks, pages 95-119. Springer, 1994.
Nikhil Mishra, Mostafa Rohaninejad, Xi Chen, and Pieter Abbeel. A simple neural attentive meta- learner. arXiv preprint arXiv: 2017.
Melanie Mitchell. Abstraction and analogy-making in artificial intelligence. Annals of the New York Academy of Sciences, (505(1):7--001, 2021.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning, 2.11.
Giambattista Parascandolo, Niki Kilbertus, Mateo independent causal mechanisms. In International Conference on Machine Learning, pages 4036- 4044. PMLR, 2018.
and Bernhard Schölkopf. Learning
Kha Pham, Hung Le, Man Ngo, and Truyen Tran. Functional indirection neural estimator for better out-of-distribution generalization. NeurIPS, 2022.
Nasim Rahaman, Muhammad Waleed Gondal, Shruti Joshi, Peter Gehler, Yoshua Bengio, Francesco Locatello, and Bernhard Schölkopf. Dynamic inference with neural interpreters. Advances in Neural Information Processing Systems, 34: 14:15599-10098, 2021.
Murray Shanahan, Kyriacos Nikiforou, Antonia Creswell, Christos Kaplanis, David Barrett, and Marta Garelo.. An explicitly relational neural network architecture. In International Conference on Machine Learning, pages 8593-8603 PMLR, 2020.
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representations. arXiv preprint arXiv: 1803.02 011/8003.225555 155, 2018.
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. Advances in neural information processing systems, 30, 2017.
Livio Baldini Soares, Nicholas FitzGerald, Jeffrey Ling, and Tom Kwiatkowski. Matching the blanks: Distributional similarity for relation learning. arXiv preprint arXiv: arXivv/906.000 0900999666388 2019.
Flood Sung, Yongxin Yang, Li Zhang, Tao Xiang, Philip HS Torr, and Timothy M Hospedales. Learning to compare: Relation network for few-shot learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1199-1208, 2018.
Mattia Tantardini, Francesca Ieva, Lucia Tajoli, and Carlo Piccardi. Comparing methods for compar- ing networks. Scientific reports, 91)::1119, 2019.
Amos Tversky. Features of similarity. Psychological review, 84(4):327, 1977.
Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. NeurIPS, abs/1706 037662, 2017.
Taylor Webb, Zachary Dulberg, Steven Frankland, Alexander Petrov, Randall O' O'Reilly, and Jonathan Cohen. Learning representations that support extrapolation. In International conference on machine learning, pages 10136-10146. PMLR, 2020a.
11

---

Published as a conference paper at ICLR 2023
Taylor Whittington Webb, Ishan Sinha, and Jonathan Cohen. Emergent symbols through binding in external memory. In International Conference on Learning Representations, 2020b.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoc Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. arXiv preprint arXiv:2201. 19903 2022.
Chi Zhang, Feng Gao, Baoxiong Jia, Yixin Zhu, and Song-Chur Zhu. Raven: A dataset for relational and analogical visual reasoning. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition (CVPR), 2019.
12

---

Published as a conference paper at ICLR 2023
APPENDIX
A DEFINITION OF d AND 11-1|oo
We first define the distance da between graphs with the same set of vertices.
Definition A.1. (Borgs et al., 2008) Given two graphs G (V, E) E 9b and G' = (V, E') Gk with associated adjacency matrices Ag = (aig)i. Sijj-TT T,k and Agr = (a/y) i. The cut distance do between G and G' is fo(G,G") = max (S. - (S. T),
(3)
S 22
where
(c(
E ai and (S, Σ dig
iESJEET
IESJET
The distance dg can also interpreted as distance between the internal relationships (i.e., the adjacency matrices) of two graphs. However, one drawback of dc is that it is not invariant under isomorphism. The generalized cut distance & is proposed to overcome this drawback.
Definition A.2. (Borgs et al., 2008) Given two graphs G = (V, E) E G and G' = -V, E Gk with associated adjacency matrices Ag = (aia)i. 1, and Ag = (dly)igiT.. T,E The generalized cut distance dr between G and G' is computed as 6G, G') ming do G'), where & shares the of vertices with G'.
Next, we define the matrix infinity norm ||.I|s. from the vector max norm. Definition A.3. For a given matrix A = (aij) =,, its infinity norm is computed as ||
max ISTCK
asyl. In words, the matrix infinity norm is the max row sum
Proposition A.4. The matrix infinity norm sub-multipiccative, ie., ||AB|| S ||
B PROOF OF THEOREM 3.2 AND MORE THEORETICAL RESULTS
In this section, we provide proofs for theoretical results in the main text, illustration of theoretical results are given in Fig. 4.
Proof of Theorem 3.2. Denote (G G'). Since G = I(G) and G' ~ I(G'), it folows that (IG( Grnd E 9 so that Gind Z(G) and d_ I(G"))
GG G') e. From the definition of d (Definition A.2), there exists
&. Denote = Aç AI(())) where Agua and AI(G') are the adjacency matrices of Gind and I(G") respectively, it follows from the definition of d_ that ||_]oo ke (since the absolute value of each element of & is less than k2 due to Definition A. of dg, and the infinity matrix norm the max row sum where each row has elements). Finally, note that AI(G') Ace, have
||ro - -rG 1ox = |AaVVing AGr Vind
< ||AG A + @
||AZ(G) Ague + |
S (l|Aoll ||Agualles + ||]])0)) |
$ (2k + {>E)||[/ind] lo0
A(2 + ( loc.
Theorem 3.2 focuses on the distance between two single indirection representations. Now we move our attention to the distance between sets of indirection representations associated with isomorphic classes of graphs. For each G GE, denote RG (ra G Gr, G a G). According to
13

---

Published as a conference paper at ICLR 2023
RG
(G)
122 (G, G')l
Vind
ke V 1o0
G¹
Re
Figure 4: Illustration of Theorem 3.2 and Theorem B.1.
Theorem 3.2, diam RG S I for every G 9k. where diam stands for the diameter of a set. We now focus on the distance between Rg and Rg', and we use the popular Hausdorff metric to measure this distance. The distance between RG and Rey is meaningful in the sense that for any r' E Roy, we can find RG so that ir-r'll- I du RRg, Rg If du RR. Roy) is small and r is observed, then r' likely to be treated similarly as r. The following last theorem shows that the Hausdorff distance dæ with respect to the o1 norm between Rg and Ro also depends on the distance between and G'.
Theorem B.1. Given two graphs Gk and G' E Gb. The following inequality holds:
du(Re, Roy S 1lo
Moreover, if G and G' are not isomorphic and rank Vind = k. then Rg O RR = Ø.
Proof of Theorem B.1. Denote [G] = (ā E Gr G G}. We will prove that for every G1 E [G], G").
there exits G2 [G') so that ||ra, rG, bo I
Following the definition of 8n, for G1 [G]. there exists G2 [G'] that 8G G') do(G1, G2). On the other hand, since G1 = G, follows that (G G*) 8_ G'), and hence da (G1, G2) = (G) This leads to
||ra, -.
|AA, Vind Aci, Vind
S ||A., -Acz 1o /iod
I 1 do G2) (ie]|Ving gindlll
&G, G*) [ loo.
This means
d(rc,: Ro) = inf ||rG, - rall S k 6', vind GE(GY)
for every Gi E [G]. Similary, d(ro,, Ro) inf ||ro, - rall s k (G, for every õe(G]
G2 E [G']. This leads to du Roy) = max sup d(ra, Ray, sup d(rog Ra) G.E|G
k. | G*).
G2EGG
Finally, if rank Vind = and G and G' are not isomorphic, suppose there exists r Rg O Roy Since r E RG. there exists Gi E [G] so that rG, AG, Vind Similarly, there exists G2 E [G") so that r= Ac, Vind This leads to AG, yind Ag, Vind and since rank Vind = k, we obtain Ag; AGg- This means G1 2 G2, and hence G = G', which is contradiction. Hence Re n Ro Ø. 0
C WELL-DEHINDDNSSS OF INDIRECTION REPRESENTATION
In this section, we consider the case when the canonical assumption (see Remark 2. is not obeyed. First, need more general definition for the indirection operator (Definition 2.2).
14

---

Published as a conference paper at ICLR 2023
Definition C.1. Given input sequence X (I1, (211,,2,.... .2....,;2 and its corresponding graph Gx Gk. the indirection operator I is a mapping from Gg to 9% that maps Gx to I(Gx) so that 1. Agx Az(xx) and 2. if the i-th vertex of Gx represents for Ij. then the i-th vertex of I(Gx)
represents for o
Consider an input sequence X = (#1, Z2,.. .... mx) and its corresponding graph Gx with adjacency matrix AGx. which is computed based the assumption in Remark 2.1. The associated indirection representation computed by Eq. (1) is rx, i.e., the i-th element of rx the indirection representation for 3;;-
Now consider an arbitrary graph G'x that also represents with adjacency matrix Agx and set of vertices {r1, og....,,%h. This means there exists a permutation a (with an associated permutation matrix P) so that (s(s) represents for zy for all i, and AG's = PAGx PT. Suppose that G'x is mapped to I(G'x) with set of vertices {uí, u2z ....... u. By the definition of indirection operator (Definition (2.2)), vi is mapped to uf (so that Acx AI(Z)) and wa(() represents e!nd (since v (2(() represents for 2;). follows that the associated indirection representation r'x with respect G'x is computed as
r'x AGe PVind PAGG PT pyind = PAGx Vind Prx-
This means the (ii)-th element of r'x is the i-th element of rx. On the other hand, after graph propagation, (o(()) represents for the (i)-th element of r'x which the i-th element of rx. Since "x() represents for 2; and (o(() is mapped u ('(()) by the indirection operator I, it follows that the i-th element of rx is the indirection representation for Vú. This shows that the indirection representations of xy 's are unchanged when the vertices of Gx permute.
D FULL EXPERIMENTAL RESULTS
D.1 OOD IQ PROBLEMS
D.1.1 FINE DATASET
We report full results with standard deviations of experiments on FINE dataset with trainset CIFAR10 and testset Omniglot in Table 5.
Train set
CIFARTO0
Test set
Omniglot
Trans.
Rot.
Shear
Scale
NTM
25.5=1.7/5..945.0
27.1:0.6631.44117
2/.8
30.342..961.0-3..
PrediNet RelationNet
26.7-0../28.5.1.55
25.5.0../28.311.5
9//29.9 1.7 24.710.6/50.2 28.3+1.4/5.342.8
25.610..429.0011.
25.3.0.5/39..:1..
25.0:0.5534..11..4
25.110.22/9.811.1
Transformer 1.99-1..96...33.37
27/241.1
Table 5:
Test accuracy (%) without/with InLay on FINE dataset with trainset CIFAR10 and testset Omniglot.
We report full results with standard deviations of experiments on FINE dataset with trainset MNIST and testset CIFAR10 in Table 6.
Train set
MNIST
Test set
CIFAR 100
Trans.
Rot.
Shear
Scale
NTM PrediNet
35.2
1934
29.611.1156.017.4
31.914.7/48.777.88
473.-511431..55..11
26.8+1.4/27.8111.5
26.4+1.4/28.4H1
33.6+.2.5/3599-67
RelationNet Transformer
25.6+0..544.544..5
25.6:.0.633.24112
25.0:0.5543.4:1..
26.8:40.74448-4..11
37.8-2.7763.946.
32.0+11./36.1111..1
30.2+2.5/53.516.
29.2+3.6/48.127.
Table 6: Test accuracy (%) without/with InLay on FINE dataset.
D.1.2 RAVEN DATASET
We report full results with standard deviations of experiments on RAVEN dataset in Table 7.
15

---

Published as a conference paper at ICLR 2023
Train configuration
Up-Down
3x3Grid
Out-InGrri
Test configuration
Left-Right
2x2Grid
Out-InCenter
LSTM
28.
19.540.6/25.142.4
42.1=1.3/48.6
Transformer
15.2:40.3356.722.3
13.6:0..4/26.0:0.99
16.6:14.5/4..:1..6
RelationNet
1224:0.//2.940.44 12.7400.3/8.54-2.0 13.750../16.551099
12.3=
PrediNet
13.6:0.3/14334..6
14.2:0.6615.9:2.55
Table 7: Test accuracy (%) without/with InLay RAVEN dataset.
D.2 OOD IMAGE CLASSIFICATION
We report full results with standard deviations of OOD image classification experiments in Table 8.
No data augmentation
With data augmentation
Dataset
Ro10
Grayscale
Jitter
Ro19
Grayscale
Jitter
SVHN
0.
869910599180007 87.2:02//1..22..
1. 92.9:0.29441103 91.810.22434412
CIFARIO
2..7:0.1/2.
48.3-0.002.. 46.6::099999::...
222 54.2:04492:00 30.220.7708.4::0.
CIFARI00
13.4:4415020.2 16:400./23::004 28.1:02//50::0
111::055144:044 18.520.727.81055 19440.528..:0055
Table 8: Test accuracy (%) without/with Inlay OOD classification task with VIT.
D.3 FEW-SHOT NLP DOMAIN ADAPTATION
We report full results with standard deviations of few-shot NLP classification tasks on FewRel 2.0 dataset in Table
ProtoNet
SNAIL
GNN
MTB
5-way-1-sho (0-way-1-shot
38.61.2.9/00.6 4.9
36.7:2.9/63.1113 27.1/43.31..4
66. 66.111.7768.911.. 52.9:1..254.1111.
49.1=2.044..733.
17.3
Table Validation accuracy (%) without/with InLay FewRel 2.0.
E 6-LAYER VIT vs. 7-LAYER VIT
We report results of 6-layer VIT and 7-layer VIT, along with 6-layer ViT equipped with InLay, in OOD CIFAR1O classification tasks in Table 10. Overall, average performance of 6-layer VIT and 7-layer ViT is much different (38.2% and 38%, respectively), while 6-layer ViT equipped with InLay clearly improve performances with average accuracy of 43.1%.
F RUNNING TIME OF INLAY
We report running time (s/iter) of VIT and ViT+InLay on CIFARIO dataset. Models are trained on single Tesla V100-SXM2 GPU. Overall, ViT+InLay requires roughly 10% more computational time.
G MORE ABLATION STUDIES ON TANH ACTIVATION
Readers may observe in Fig. 3a that having no activation in InLay still achieves almost equal performance. However, that just special case; Table shows results of similar ablation experiments with NTM on the FINE dataset with different activation functions. Among all, the tanh activation achieves best average performance.
H ABOUT INPUT SEQUENCE LENGTH
H.1 WHEN THE SEQUENCE IS TOO LONG
When the number of nodes is large, graph neural networks usually suffer from the issue of over- smoothness, which is the phenomenon that all nodes become nearly the same after updated. However, show that Inl Lay may mildly suffer from this issue. In the OOD classification task, we increase
16

---

Published as a conference paper at ICLR 2023
Image transformation
Color transformation
Average
Rot90
VFlip
Jitter
Invert
Blur
Grayscale
6-layer VIT
25.7100.1
32.110.6
23.2.11.1
39.4.12.8
60.2.10.5
48.3.00.8
38.2
7-layer ViT
26.4 +0.5
31.5:10.3
2.24
38.6+3.2
60.8 -0666
48.3 =0.7
38
6-layer ViT + InLa
27.9+
35.0==0.9
24.9++..7
48.3+33.3
59,5+1.2
62.7++0.2
43.1
Table 10: Test accuracy (%) without/with InLay on OOD CIFARIO classification tasks with 6-layer VIT, 7-layer ViT, and 6-layer ViT equipped with InLay
No data augmentation
With data augmentation
VIT
0.095
0.100
Viy+
0.108
0.110
Table 11: Running time (s/iter) of ViT and ViT+Inlay CIFARIO dataset.
the number of nodes by duplicating each node times, resulting in a graph with 196 nodes. The results reported in Table 13. It can be observed that the test accuracy in the case of 196 nodes is not much different from the case of 49 nodes.
H.2 WHEN THE SEQUENCE LENGTH IS NOT FIXED
All input sequences in our experiments are of fixed length. The case of varying input sequence length can be treated as fixed-length case if the maximum sequence length is known: we can use empty nodes to fulfill any sequence to reach that maximum length. We conduct experiments on OOD classification task to illustrate this idea: for each image patches sequence, randomly remove some (2 to 6) patches, so that the resulting sequences have different lengths; we then use zero tensors for padding so that all sequences and test on images with grayscale distortion. The test accuracy is 61.4%, which is not much different from 62.7% of the fixed-length case.
have the same lengths. We train ViT+inLay CIFARI0 dataset
A more challenging scenario is when the lengths of testing sequences are longer than training ones. Current design of Inlay does not allow it to deal with this situation. We believe this is promising for future work.
1 COMPARISON WITH OTHER INDIRECTION APPROACHES
We compare InLay with different indirection approaches like ESBN (Webb et al., 2020b) and FINE (Pham et al., 2022) on FINE dataset. We incorporate InLay with Transformer performance among different models. For FINE, we use NICE backbone as suggested in the original paper. Results are shown in Table 14. Overall, Transformer+InLay shows competitive results with the best performances on 5/8 tasks and second-best performances on 2/8 tasks.
shows the best
J MORE ABLATION EXPERIMENTS ON CONTEXT NORMALIZATION
We further conduct ablation experiments to show the necessity of context normalization in InLay. Table 15 show performances of NTM and NTM+InLay. with and without context normalization. First, we may observe that InLay is really effective in the sense that NTM+InLay without context normalization is still far better than original NTM. both with and without context normalization. Second, context normalization helps to boost the performances of NTM+ by a large margin.
K TRAINING DETAILS
K.1
IQ OOD PROBLEMS
K.1.1 FINE DATASET
We use 3-yayer p4-CNN encoder (Cohen and Welling, 2016) with kernel size 3 and padding 1 to encode raw 32 x 32 images to feature vectors of size 128. This encoder help model adapt better
17

---

Published as a conference paper at ICLR 2023
Train
MNIST CIFAR 100
Test set
Trans.
Rot.
Shear
Scale
Avg.
NTM+ILLyy(aanh)
69.2
34.5
56.0
48.7
52.1
NTM+-ILay(mooee)
58.1
31.2
52.5
47.8
47.4
NTM++nn )
62.1
31.9
58.4
41.2
48.4
NTM+InLay (relu)
52.7
32.3
51.2
33.5
42.4
NTM
35.2
30.0
29.6
31.9
31.7
Table Average test accuracy (%) NTM (with without InLay) on FINE dataset with different activation functions.
VIT
ViT+inLay (49 nodes)
ViT+inLay (196 nodes)
Test accuracy (%)
48.3
62.7
62.5
Table 13: Experiment results of LiT+ with different number of graph nodes on OOD classification task on CIFARIO dataset. Test distortion is grayscale.
with transformed images. We Adam optimizer (Kingma and Ba, 2014) with learning rates ranging from
10 4, depending on specific model and transformation. We train all models with batch size 32 in 200 epochs. The indirection representations are computed in Eq. (1) with 1 attention head.
The training contains 5,000 IQ problems, while testing set contains 10,000 IQ problems of unseen images and unseen rules. Specifically:
With translation, models are trained on problems with translation vectors (a, with {0,3, 6, 9} and b E #3, 16, } and tested with E {-3. -9}. i.e., train on problems with translations the right and test on problems with translations to the left.
With rotation, models are trained {0", 15", "......, ,..., 180%) tested with 2195",210"... ,...,.
problems with rotation angle
With shear, models are trained on problems with shear angles (a, with {0, 30% 30" 45", 60"} and 3 E 11, +30", 1450, 160%, and tested with a E 1-150 -30% -5 -60)..
With scale, models are trained on problems with scale factor E {1, 1.25) and tested with a E (0.5,0.755) i.e. train with larger scale and test with smaller seale.
K.1.2 RAVEN DATASET
We 3-layer CNN encoder with kernel size and stride 2 to encode 80 80 images to feature vectors of size 256. We use Adam optimizer with learning rates ranging from 10-4 to 3 10-1 and gradient clipping All models are trained with batch size in 250 epochs. The indirection representations are computed as in Eq. (1) with attention head.
We apply the Dynamic Residual Tree (DRT) as follows: first apply DRT feature vectors, then pass resulting vectors through InLay to obtain indirection representations, then apply DRT once again and these final resulting vectors will be the input for prediction models. Other details are similar to the original paper and codes are also adapted from the original paper.
K.2 OOD IMAGE CLASSIFICATION
We use Adam optimizer with learning rate 14, All models are trained with batch size 32 200 epochs. The indirection representations are computed as in Eq. (1) with 32 attention heads.
We use 6-layer ViT with patch size 8, 16 attention heads and dropout rate 0.1. The dimension of feedforward layer is 2048.
K.3 FEW-SHOT NLP DOMAIN ADAPTATION
We use BERT to encode paragraphs to feature vectors of size 768. Models are trained with batch size 32 S-way-1-she tasks and batch size 16 on 10-way-1-shot tasks. We SGD optimizer with
18

---

Published as a conference paper at ICLR 2023
Train set
CIFARTOO
MNIST
Test set
Omniglot
CIFAR 100
Trans.
Rot.
Shear
Scale
Trans.
Rot.
Shear
Scale
FINE ESBN
27.3
37.6
18.7
19.5
47.7
45.2
48.8
26.6
53.5
39.9
56.6
45.2
54.1
50.3
70.7
58,8
Iransformer+Inl.ay
63.3
40.4
65.3
62.0
63.9
36.1
53.5
48.1 1
Table 14: Average test accuracy (%) without/with Inl.a FINE dataset.
Train set
MNIST CIFAR
Test
Trans.
Rot.
Shear
Scale
Avg.
NTM+tnLay(with context norm.)
69.2
34.5
56.0
48.7
$2.1
NTM+InLay (without context norm.)
44.0
41.3
43.6
36.3
41.3
NTM (with context norm.)
35.2
30.0
29.6
31.9
31.7
NTM (without context norm.)
33.9
28.7
32.3
37.1
Table 15: Average test accuracy (%) of NTM (with without InLay) FINE dataset with different activation functions.
learning 2- 10-5, The indirection representations computed as in Eq. (1) with 32 attention heads. Other details are similar to the original paper and codes are also adapted from the original paper.
19


Reviews:
[{"review_id": "yot9WlIzPYp", "reviewer": "Reviewer_JfzH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a generic module named Indirection Layer (InLay), which can be plugged into different models to improve out-of-distribution generalization. InLay leverages the idea of indirection to redirect data representation based on a trainable set of symbols.\nSpecifically, InLay takes a sequence of objects as input and transforms the sequence into a new graph-structured indirection representation that leverages indirection and data internal relationships. The authors demonstrate that InLay is consistently effective in improving out-of-distribution generalization throughout a comprehensive suite of experiments.\n", "summary_of_the_review": "The authors first propose a general module named Indirection Layer (InLay) for improving models’ generalization performance. \nSpecifically, the module maps the input sequences into the graph-structured indirection representations. The experiments show its powerfulness throughout some popular datasets. \nAlthough the module is a little similar to self-attention, InLay has the data-independent and trainable $V^{ind}$ that shows its novelty. \n\n", "strength_and_weaknesses": "Strength:\n1. The authors propose a generic module named Indirection Layer (Inlay), which can be plugged into different models to improve out-of-distribution generalization.\n2. Tens of percent performance improvement results demonstrate the powerfulness of InLay.\n3. The authors theoretically show the effectiveness of InLay which preserves the internal structures of graphs and the global structure of graph space.\n\nWeaknesses:\n1. The authors did not explain how to tackle the situations if the length of a sequence is not fixed.\n2. The authors may want to do some ablation experiments to show that the improvement is caused by InLayer, not the context normalization that is used with InLayer.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "uBI75MNvXYn", "reviewer": "Reviewer_r9MA", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors present an layer in a neural network called Indirection Layer (InLay). InLay takes\na sequence of objects as input and transforms the sequence into a new indirect graph-structured\nrepresentation. In this graph vertices are the objects, and edges are similarity scores in the range [-1,1] that are learned. The similarity weights are then used to modify a representation V_ind of the vertices which is not computed based on the data X (it is a different set of vectors). This representation, that is contextualized by other members of the sequence is than used for prediction. All in all this is very similar to self attention, however the attention scores are in [-1,1] and V_ind is not computed based on the data X.\nThe goal of InLay is that graph representations of different two sequences that have similar internal structure should be similar, and thus help in OOD generalization.\n\nInLay can be used as an additional layer on top of different architectures, e.g., Transformers or LSTMs.\nExperiments of InLay are done for the datasets FINE and RAVEN, where a sequence of images with an internal relation are shown and the model should predict which image should complete the sequence. For both datasets, substetianl improvement is achieved by using InLay. In addition, the method is applied to OOD image classification tasks and shows nice gains.", "summary_of_the_review": "InLay is a neural layer for representing objects in a sequence that share relations between them (e.g., rotation). InLay seems like a good direction towards capturing relations between objects that are useful for different classification tasks. The layer could be added in a simple manner on top of different architectures. Currently, the method is applies to synthetic tasks, and it is left for future work to find out whether the learned representation is useful in realistic settings. ", "strength_and_weaknesses": "Strength: The proposed method is easy to apply as it can be naturally added on top of representations by other base models. In addition, it shows nice boosts in appropriate settings and for OOD image classification.\n\nWeakness: Current experiments mostly involve applications to simple images in synthetic settings (like IQ tests), or synthetic transformations to images like rotations. It is not clear at this point whether InLay can capture implicit and complex relations between natural images. In addition, all in all the layer is very similar to a self-attention layer.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "gasHcG_RTL", "reviewer": "Reviewer_EM2y", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a new module named “InLay” that can be plugged into different models across multiple modalities to improve out of distribution performance. The work leverages the idea of “indirection” to learn *indirection representations* for a given sequence of inputs. The rationale behind the proposed method is the key findings of Structure Mapping Theory that relationships between the objects are transferred during analogy rather than the attributes. More concretely, each data sample is viewed as a complete weighted graph where the weights are computed using a simple kernel between the pairs of objects in the input. The authors highlight the subtle difference of this scheme compared to the attention mechanism in the use of “tanh”. The input graph is then mapped to a new graph where the vertex embeddings are obtained from a trainable dictionary $V^{ind}$. Subsequently, a propagation scheme is applied to generate the indirection representations, as shown in eq 1. They also highlight the subtle difference that $V^{ind}$ is not computed based on the given input sequence and rather a standalone dictionary that represents the training data distribution as a whole. Furthermore, they provide an upper bound on the $l_{\\infty}$ norm of the difference between indirectons representations based on a graph distance (the generalized rectangle distance) and $V^{ind}$. They also show that the indirection representation space is partitioned into disjoint subsets each of which correspond to a class of isomorphic graphs. Empirical evidence provided on different datasets across multiple modalities demonstrate the efficacy of the proposed method.\n", "summary_of_the_review": " Based on the questions, comments and concerns raised in the previous sections, I lean towards weak rejection of the work. I am willing to reconsider my score if the authors can answer the questions raised above.", "strength_and_weaknesses": "1. The results across the tables in the main paper demonstrate that the proposed method indeed helps in generalization.\n2. Figure 3 a) provides a satisfactory ablation of the proposed segments of InLay module. It is interesting to note that not having an activation layer to constrain the graph weights also performs almost equally well. Does this hold across other model-dataset pairs as well? \n3. Leveraging a complete graph can be highly inefficient. I believe there should be experimental settings where the input sequence is large. In such cases, the proposed method could also struggle to learn good representations due to issues such as oversmoothness. \n4. The computation of the adjacency matrix $a^{X}_{ij}$ in the first paragraph of page 3 doesn’t seem to be undirected.\n5. In most of the experimental settings, using invariant networks and data augmentation also achieves the same goal. It will be highly relevant in the context of the work to provide comparison against some recent techniques while simultaneously reporting the runtime comparisons (one can see inducing the InLay layer may not increase the runtime as drastically compared to say - data augmentation). Similarly, the comparison to ESBN and FINE baselines on the IQ benchmarks seem necessary.\n6. The standard deviation numbers provided in the appendix are fairly high across the board. It is evident that the InLay module makes the model predictions somewhat unstable. Do the authors have potential rectification/s for this?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "UbuKT2JE6R7", "reviewer": "Reviewer_ttym", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes InLay, a new layer module which claims to capture internal relationships between input objects. Ultimately, for each input sequence $X \\in \\mathbb R^{k \\times n}$ (interpreted as $k$ elements with $n$ features), the output of an InLay layer is given by\n$\\tanh\\left(\\frac{XQ(XK)^\\mathrm T}{\\sqrt{4n}}\\right) V^\\mathrm{ind},$\nwhere $Q, K \\in \\mathbb R^{n \\times 4n}$ are trainable weights and $V^\\mathrm{ind} \\in \\mathbb R^{k\\times n}$ are free parameters. The authors note the similarity of this operation to self-attention, with three mathematical distinctions: (1) $Q, K$ project into a higher-dimensional space, (2) $\\operatorname{softmax}$ is replaced by $\\tanh$, and (3) $V^\\mathrm{ind}$ are free parameters, not a linear transformation of $X$. The authors motivate the design decisions by interpreting the inputs as vertices of a directed weighted graph whose edge weights are given by the $\\tanh$ term in the layer, and thus the output of this layer can be viewed as propagating the (learned) features of $V^\\mathrm{ind}$ along these weighted edges. The decoupling of $V^\\mathrm{ind}$ from $X$ is intended to allow the layer to capture only internal relationships between objects, which is particularly beneficial for generalization in settings where the relationships between objects (eg. analogy, IQ test patterns) are the important factor. The authors evaluate on a large number of experiments of such tasks.", "summary_of_the_review": "The idea is reasonable, however I felt it was not presented well. Some aspects of the motivation were more confusing than helpful, and the level of rigor was inconsistent, with some aspects (eg. emphasis on the indirection operator) being more complicated than necessary while other aspects (eg. proofs of theorems) had technical flaws.", "strength_and_weaknesses": "### Strengths\n1. The paper presents a large number of evaluations on a variety of tasks, the vast majority of which exhibit improved (often substantial) performance of their proposed method.\n2. The authors perform an ablation study to analyze the impact of some (but not all, see point below) of the design decisions for InLay.\n3. The related work section seems quite comprehensive, which is particularly useful for certain aspects (eg. Structure Mapping Theory) which most readers may be unfamiliar.\n\n### Weaknesses\nThe most fundamental issue from a technical sense is that, to my understanding, there is an error in both proofs.\n#### **Errors in Proofs**\n1. The authors seem to rely on the idea that the max norm is sub-multiplicative, i.e. if $\\lVert A \\rVert = \\max_{ij} |a_{ij}|$ then the authors make use of the (incorrect) inequality $\\lVert AB \\rVert \\le \\lVert A \\rVert \\lVert B \\rVert$ in both proofs. I should note, it is not clear to me if this is actually the intended meaning of their max norm, since the statement of Theorem 3.2 says \"$\\lVert \\cdot \\rVert_\\infty$ is the max norm on $\\mathbb R^n$\", whereas the elements which the authors calculate the norm of are (to my understanding) in $\\mathbb R^{k \\times n}$. If I have understood it correctly, however, the inequality mentioned earlier is incorrect, as can be observed by considering $A = B = \\begin{bmatrix} 2 & 2 \\\\\\\\ 2 & 2\\end{bmatrix}$.\n2. In the proof of theorem 3.2, $f$ is not defined. I assume that it was intended that $f$ is the indirection operator, i.e. $f = \\mathcal I$, however in that case there are lines which do not make sense (eg. the author's statement \"From the definition of $\\hat{\\mathcal \\delta}_\\square$ there exists $G^\\mathrm{ind} \\in \\mathcal G_k^\\mathrm{ind}$ so that $G^\\mathrm{ind} \\cong f(G)$ and $d_\\square(G^\\mathrm{ind}, f(G'))=\\varepsilon$.\" is unnecessary, as $\\mathcal I(G) \\in \\mathcal G_k^\\mathrm{ind}$ already.)\n\n#### **General Theoretical Inconsistencies**\nThere were more general points of confusion throughout, most of which revolve around the theoretical formulation and motivation of the model.\n1. $\\mathcal G_k$ is defined as the space of all undirected weighted complete graphs $G$ with $k$ vertices, with edge weights belonging to $[-1,1]$, however the components of the adjacency matrix are clearly not symmetric. Perhaps it was intended that $\\mathcal G_k$ is the space of directed weighted complete graphs. The problem gets more involved, however, as expressed in the following.\n2. Throughout, the authors implicitly make use of a canonical indexing of vertices in a graph, but define things using a more standard representation of a graph (as a set of vertices and edges). This is most problematic in the definition of the indirection operator (Definition 2.1), which is ultimately not well-defined as currently described, which is as a map from $\\mathcal G_k$ to $\\mathcal G_k^\\mathrm{ind}$ but which implicitly assumes an ordering of nodes. To highlight the issue, consider the graph $G$ with vertices $V = \\\\{5,8\\\\}$ and $E = \\\\{(5,8)\\\\}$. (Note: here the vertices are in $\\mathbb R$, for simplicity in this example.) The definition of the indirection map requires an order on the vertices, but there is no inherent labeling - the vertices of a graph (both conventionally and as described in the paper) are a *set*. If we pick the labeling $x_1 = 5, x_2 = 8$ then the map takes $G$ to a graph with vertices $\\\\{v_1^\\mathrm{ind}, v_2^\\mathrm{ind}\\\\}$ and edge set $\\\\{(v_1, v_2)\\\\}$, however if we had labeled the vertices as $x_1 = 8, x_2 = 5$ then the image under $\\mathcal I$ would have edge $\\\\{(v_2, v_1)\\\\}$. Therefore we have a contradiction, and thus $\\mathcal I$ is not well-defined. There are two possibilities to remedy this situation. One is to instead consider not the set of graphs but rather the set of graphs with a given ordering, however this will add complexity and will become confusing as it is not classically how graphs are defined. The other is to reconsider whether this framework is really necessary. At the end of the day, the idea is simply that the output of InLay can be interpreted as having trainable value parameters which are decoupled from the data but combined using the pairwise similarity between input data. In my opinion, the existing framework seems unnecessarily complicated, and does not provide much insight. Either way, repairing this requires a substantial rewrite of sections 2 and 3.\n\n#### **No Ablation of Fundamental Difference with Self-Attention**\nThe authors highlight the three points mentioned in my summary above as distinctions between InLay and self-attention, with a further emphasis that the fundamental distinction is point (3), namely that the values are not related to the input data. They do include an ablation of various components of InLay, but not of this crucial distinguishing factor. The authors also mention another distinguishing factor is that the output replaces the input data, as opposed to being added to it, and this would similarly be useful to assess with an ablation.\n\n\n### Minor Issues / Typos / Suggestions\n1. Section 3, first line, I believe \"in the case of complete graphs\" is unnecessary, this is true for all graphs.\n2. Page 4, \"preserves any topology on $\\mathcal G_k$ induced from $\\hat \\delta_\\square$\" - this suggests that $\\mathcal I$ is a homeomorphism, which is not the case (since it is not a bijection). Perhaps what was intended was \"$\\mathcal I$ is continuous with respect to any topology on $\\mathcal G_k$ induced from $\\hat \\delta_\\square$\".\n3. Page 4, and throughout: the authors emphasize the invariant properties of the indirection operator, however if one understands the definitions these properties are not particularly novel or surprising, since the properties are all defined in terms of the adjacency matrix and the indirection operator preserves the adjacency matrix. (This is another way in which I feel the current presentation results in unnecessary complexity.)\n4. Page 4: \"we can find $r \\in R_G$\" - isn't this the case that the inequality which follows holds for all $r\\in R_G$?\n5. Page 4: \"it can be located close to some observed $r$\" - I don't believe this means that $r'$ can be located close to some observed $r$, but rather: given $r'$, the distance from $r'$ to any observed $r$ is bounded by $d_H(R_G, R_{G'}) + 2 ||V^{ind}||_\\infty$. (This bound of course depends on Theorem 3.2, whose proof currently has an error.)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster