Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors present an layer in a neural network called Indirection Layer (InLay). InLay takes
a sequence of objects as input and transforms the sequence into a new indirect graph-structured
representation. 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.
The 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.

InLay can be used as an additional layer on top of different architectures, e.g., Transformers or LSTMs.
Experiments 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.
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.

Weakness: 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.
clarity,_quality,_novelty_and_reproducibility: Clear writing. Assuming the implementation will be open, other folks could find the layer useful.
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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
$\tanh\left(\frac{XQ(XK)^\mathrm T}{\sqrt{4n}}\right) V^\mathrm{ind},$
where $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.
strength_and_weaknesses: ### Strengths
1. 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.
2. The authors perform an ablation study to analyze the impact of some (but not all, see point below) of the design decisions for InLay.
3. The related work section seems quite comprehensive, which is particularly useful for certain aspects (eg. Structure Mapping Theory) which most readers may be unfamiliar.

### Weaknesses
The most fundamental issue from a technical sense is that, to my understanding, there is an error in both proofs.
#### **Errors in Proofs**
1. 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}$.
2. 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.)

#### **General Theoretical Inconsistencies**
There were more general points of confusion throughout, most of which revolve around the theoretical formulation and motivation of the model.
1. $\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.
2. 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.

#### **No Ablation of Fundamental Difference with Self-Attention**
The 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.


### Minor Issues / Typos / Suggestions
1. Section 3, first line, I believe "in the case of complete graphs" is unnecessary, this is true for all graphs.
2. 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$".
3. 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.)
4. 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$?
5. 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.)
clarity,_quality,_novelty_and_reproducibility: Overall, I found the paper somewhat unclear, with significant technical issues which would need to be addressed before this paper is ready for publication. The idea is somewhat novel, but due to some of the aforementioned technical issues I am not confident that one could reproduce the results from the paper alone, and I was unable to find a code reference.
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.

strength_and_weaknesses: 1. The results across the tables in the main paper demonstrate that the proposed method indeed helps in generalization.
2. 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? 
3. 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. 
4. The computation of the adjacency matrix $a^{X}_{ij}$ in the first paragraph of page 3 doesn’t seem to be undirected.
5. 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.
6. 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?

clarity,_quality,_novelty_and_reproducibility: The writeup of the paper is very clear. The hyperparameter details along with the empirical evidence presented suggest that the results are likely to be reproducible. The authors strongly emphasize that the proposed method is subtly different from self-attention and also demonstrate that it is empirically superior in appendix table 10. More results on this will help analyse the contributions of the work better. 

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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
Specifically, 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.

strength_and_weaknesses: Strength:
1. The authors propose a generic module named Indirection Layer (Inlay), which can be plugged into different models to improve out-of-distribution generalization.
2. Tens of percent performance improvement results demonstrate the powerfulness of InLay.
3. The authors theoretically show the effectiveness of InLay which preserves the internal structures of graphs and the global structure of graph space.

Weaknesses:
1. The authors did not explain how to tackle the situations if the length of a sequence is not fixed.
2. 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.

clarity,_quality,_novelty_and_reproducibility: The paper is well-written and expresses its point clearly. 

The authors first propose a general module that maps the input sequence into the graph-structured indirection representation, significantly improving the model generalization performance. 

Although the module is a little similar to self-attention, InLay has the data-independent and trainable $V^{ind}$ that shows its novelty. 

I think the module, InLay, proposed in this article is reproducible, but the author did not give the implementation code. I hope the authors can provide the codes in the future. 

All in all, I think the outcomes and the writing are of high quality.

summary_of_the_review: The authors first propose a general module named Indirection Layer (InLay) for improving models’ generalization performance. 
Specifically, the module maps the input sequences into the graph-structured indirection representations. The experiments show its powerfulness throughout some popular datasets. 
Although the module is a little similar to self-attention, InLay has the data-independent and trainable $V^{ind}$ that shows its novelty.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors propose a new layer that improves generalization to out-of-distribution samples. 
Strengths: clear work, nice improvements across many experiments
Weaknesses: Evaluation on real end tasks and some disagreement about the theoretical formulation.

justification_for_why_not_higher_score: Mostly due to the absence of more downstream evaluations. Overall scores are positive but not excited enough to merit a spotlight or oral.
justification_for_why_not_lower_score: The paper should be accepted as 3/4 voted for acceptance and the last reviewer mostly wanted to encourage authors to hash out some final technical details in the theoretical formulation.
Decision: Accept: poster