Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes an approach to identify the null space of vision transformers (ViT). They divide this into two parts – (a) null space of patch embeddings, and, (b) null space for the self-attention module(s). The paper uses the above to study the robustness of ViT to null space noise, compare the impact on different architectures, and study its transfer properties. Finally, the null-space is used to apply perceptible watermarks to images without altering the test-time performance (of image classification).

strength_and_weaknesses: ## Strengths
- Investigation of null spaces of vision transformers is a good direction of research and of relevance to the ICLR and wider AI/ ML community. 
- There are some interesting ideas regarding finding perturbations in the input space to which the output of ViT is invariant and to use it for perceptible watermarking.

## Weaknesses

__(W.1) Importance__: The motivation and importance is not quite clear. The authors make an argument about inherent robustness (invariance) to certain perturbation in the input. It is quite obvious that by design, classification networks are sought to be invariant to tp intra-class differences and geometric and photometric transformations that are deemed not to result in changes in the class identity, leading to all kinds of data augmentations. That set of subspaces of inputs may lie in the nullspace is the key idea here but it is not clear what nontrivial value the authors provide in the paper. Please elaborate.

 __(W.2) Technical Approach__: I have several questions regarding the technical approach proposed in Section 4  (if I’m understanding it correctly):
- __(W.2.1)__: Equation (5) describes a set which is invariant to the input $\mathbf{u}$. However, the loss functional defined in equation (6) doesn’t reflect his invariance to the input $\mathbf{u}$. Is there an empirical expectation over the entire training dataset?
 - __(W.2.2)__: The loss in Equation (6) admits a trivial solution ($\tilde{\mathbf{v}}_\phi = 0$. There is no regularization which keeps the solution away from the trivial one. Even if empirically the minimization (perhaps through SGD) yields a solution that’s nontrivial, it can still be arbitrarily close, lying in a small non-isotropic neighborhood around $\mathbf{u}$ with the same output value. The non-isotropic nature (think elongated tubes, for example) will allow a random permutation of the perturbation to change the output. The existence of this small neighborhood is just a statement about local regularity (of data spaces) and smoothness (of functions) on it. How is this useful in the sense that you seek to exploit in the paper? 
- __(W.2.3)__: The solution of Eqn. (6) resulting in a  'nullspace' noise vector which is not arbitrarily close to __any input u__ while maintaining the same prediction as __u__ for every __u__ (i.e., it is independent of __u__) is not demonstrated or validated. At least on the training data, the % match predictions should be 100% for the definition to make sense. Is this the case?
- __(W.2.4)__: It seems like a single noise vector is learnt over the entire training dataset per training episode (for each random initialization of the noise vector $\tilde{v}_\phi$). This is rather inefficient for generating ‘infinite such perturbations’ as claimed in the motivation. Secondly, it’s unclear what the diversity of the set of noise vectors is.
- __(W.2.5)__:  Magnitude(v) should be shared and the significance of MSE(logit) should be explained. It is not clear what to make of the numbers on the y-axis (0-7000.0). How large are those numbers with respect to the magnitudes of the logits?
- __(W.2.6)__:  For classification networks, simple geometric transformations like translations, rotations, small scalings etc. should lead to the same classification output. How are the random perturbations found through equation (6) useful beyond the above?
- __(W.2.7)__:  The whole discussion in 5.2 about strided convolutions and intractability of determining a null space seems mathematically flawed (if we ignore the pointwise nonlinearity of the ReLU etc. which the authors don’t seem to be considering) since tensor multiplication is a linear operation. Kindly explain. [1’] below may be useful to take a look at. 

[1’] Zou, Dongmian, Radu Balan, and Maneesh Singh. "On lipschitz bounds of general convolutional neural networks." IEEE Transactions on Information Theory 66.3 (2019): 1738-1759. 

 __(W.3) Experimental Evaluation__: 
- __(W.3.1) Robustness__: In Figure 3(a), why should the scale of the features with respect to which the sampling limit is meaningful, be the same? 
- __(W.3.2) Robustness__: Comparison of robustness to noise across different networks makes sense when the performance degradation under the same perturbation of the input is analyzed. In the experiment in Figure (3), the learnt perturbation also varies and is from an optimization algorithm (which may fail to do what’s expected of it). In this ‘approximate’ setting, everything is so amorphous and the different factors are so entangled that it’s hard to have any takeaways from this experiment. Kindly explain. 
- __(W.3.3) Watermarking__: Equation (7) suggests that the transformed image should look like the target (watermark) and yet have the same classification semantics as the source. However, the transformed images in Figure (4) look more like the source images while images in Figure (5) look more like the target images. It is not clear what the goal of visible watermarking is and what kind of visual perturbations are considered to be of acceptable quality and for what purposes. Kindly clarify. 
- __(W.3.4) Watermarking__: Qualitative results provided in A.2 should be in the main paper. 
- __(W.3.5) Watermarking__: Only twenty images are used for evaluation. This is unsatisfactory. Since only the null space of the patch embeddings is considered ($v_\theta$), why should this be prohibitively expensive?
- __(W.3.6) Watermarking__: Finally, since by design, $v_\theta$ should not alter the representations by the network, should the classification accuracy be higher than 85%, and 100% if training images are used?
- __(W.3.7) Unconstrained Targeted Noise__: No quantitative results are provided.

clarity,_quality,_novelty_and_reproducibility: **Clarity**: The paper is mostly clear. There are some easily fixable typos.

**Quality**: Should be improved. I feel that the technical portion of the paper is not rigorous enough. The parallel between the concept of linear null spaces and that of a single additive perturbation to the input is stretching the concept too much. The technical framework appears artificial. Also, experimental evaluation needs to be improved. 

**Novelty**: Though I’m not aware of any work that analyzes the null space of patch embeddings in ViT, it is straightforward and well-known in classical literature. The extension to nonlinear parts of the network would be of interest but is ad hoc and does not add much value to the field.

**Reproducibility**:  Should be reproducible. 

summary_of_the_review: I’m not convinced of the merits of the paper. There are some interesting ideas. However, the technical framework appears artificial, somewhat ad hoc, and not rigorous enough. More extensive experimental validation is required. As a result, I don’t assess the current submission to be of publishable quality.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper presents an exploration of the concept of nullspaces for vision transformers. It presents an approach towards determining the nullspace vectors of the vision transformer: a deterministic non-trivial nullspace for linear projection components and an approximate nullspace for non-linear attention layers. Further, it explores its implications in 3 areas: robustness, watermarking and adversarial sample generation to fool models and interpretability methods. Finally, the paper shows that ViTs are more robust to higher amounts of nullspace-generated noise than state-of-the-art CNNs, and demonstrates the application of nullspace noises in watermark imposition and adversarial sample generation.
strength_and_weaknesses: Pros
	- The exploration of nullspace noise for analyzing the robustness of models is a novel application of the concept. I would love to see more exploration into the implications of nullspace noise on robustness.
	- The paper was very well written, and easy to follow.

Cons
	- The paper mainly discusses 3 areas: robustness, watermarking and adversarial generation.
		§ Robustness:
			§ I think this area requires more analysis in the paper. The introduction and conclusion sections imply that the existence of nullspace vectors, and the high amount of noise generated using this nullspace basis, has significant implications on the robustness of the vision transformer.
			§ Section 5 presents the question: "How robust are different architectures to nullspace noises." However, this seems a bit confusing. My understanding is, all architectures are, by definition, robust to their nullspace noises. Further, each network has its own nullspace noise distribution, depending on its architecture. The main question, I think, is more about the properties of the nullspace noises of a given model. A model is more robust if:
				□ Its nullspace has a high sampling limit (with a high threshold on accuracy or %match)
				□ The nullspace samples, as described by equation (4), have high accuracy too.
			§ Figure 3 (a) and (b) show that ViT have higher sampling limits than state-of-the-art CNNs. I think these results give evidence for the first property of robustness w.r.t nullspace noise as described above. However, I think it will be really helpful to analyse these results on more datasets, instead of just a single one.
			§ Figure 3(c) shows low transferability of noise between models, however, I don't think this particular graph makes any implications on which model is better. Since the noise vectors are obtained using ViT-S model, they are strongly biased against the CNNs. It's very likely that the ViT models will perform equally poorly on the noise vectors obtained using the CNNs. I think it would be helpful if this point is highlighted.
			§ Figure 3 doesn’t include any quantitative results for the 2nd property described above, regarding the accuracy of nullspace samples from equation (4). This can probably be done by presenting the deviation of accuracy at different nullspace noise vectors, and increasing the number of sampling limits considered.
			§ It would be helpful if the point about "lack of effective nullspace noise" in CNNs is elaborated a bit more. Does the difficulty in finding effective noise due to non-linearity necessarily mean lack of effective nullspace noise?
		§ Watermarking:
			§ In this application, a slightly different watermark will be applied on each image. It would be helpful if the implications of this are discussed. Would this significantly comprise the tasks for which the watermarks are being used for? I am curious to see if this has any practical implications.
		§ Adversarial Sample Generation:
			§ I think more results are required for this application. It would be really helpful if the following results are included:
				□ An accuracy score on a few datasets on the misclassifications, along with the qualitative examples, shown in Figure 5 (a).
				□ It would be helpful if the explainability attribution map mistakes are quantified in some manner, probably IoU/DICE etc, to get some quantitative results to support the qualitative results shown in Figure 5 (b).

Minor Edits
	- In section 2, paragraph starting with "A trivial nullspace, …", shouldn't "axiom 1" be used instead of "linear mapping as described in equation 1", and "equation 2" instead of "linear equations as described by equation 1"?
	- In section 3.1 Classification Stage, shouldn't it end with "project it through a linear classification layer, followed by a softmax layer" instead?
	- In equation (5), it would be more clear to add f_phi instead of just f.
	- Section 6 method details: typo at delta x_j -> "changed" to "change"
In section 7 line 3, helpful to write equation (7) instead of just 7.

clarity,_quality,_novelty_and_reproducibility: The paper was very well written and was very easy to follow. The authors did not mention that the code will be released upon publication. The exploration of nullspace noise for analyzing the robustness of models is a novel application of the concept. 
summary_of_the_review: Borderline reject. The paper definitely proposes a novel idea, however, I think a bit more analysis and results are required. If the author(s) are able to address the above comments, the decision will be reconsidered.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper explores the concept of nullspace for vision transformers (ViTs). The authors find that there usually exists non-trivial nullspace for vision transformers by finding the exact nullspace of their patch-embedding stages. Extending to the case of non-linear transformation where the nullspace is ill-defined, the authors look for an alternative set that adds any element in that set to the input, and the output of the transformation remains unchanged. The authors also study the robustness of ViTs with the nullspace noise perspective. In addition, they show that ViTs are more robust than CNN models under the noise generated via the nullspace. The authors also illustrate that nullspace noise can be used to impose perceptible watermarks on images.

strength_and_weaknesses: **Strong points:**

1. The paper addresses an interesting problem as finding the nullspace of ViT will tell us certain types of input perturbations to which the network is inherently robust.

2. The paper is well-written with illustrative figures.

**Weak points:**

1. In the nonlinear case where the nullspace is ill-defined, the authors “attempt to preserve the axiom of most interest to us, closeness under vector addition” and look for an alternative set that adds any element in that set to the input, and the output of the transformation remains unchanged. This approach lacks theoretical justification.

2. The relaxation to study an individual element of the nullspace in the nonlinear case (e.g. when deriving the nullspace for the self-attention stage) removes all interesting insights from studying the whole nullspace of ViT and makes the contribution of the paper mediocre.

3. For noise robustness application, I have a concern about the significance of the idea. Finding the nullspace noise only allows us to know a certain set of noise to which the ViT is robust. How does it help improve the generalization of ViT models? How to constrain other input permutations/corruptions to be in the approximated nullspace of the network?

4. For the applications relating to watermarking, the nullspace-noise-added images significantly decrease the quality of the original images, making them not useful in reality. For the applications on output-preserved image watermarking, the quality of the corrupted images is bad and much worse than the adversarial examples generated by adding adversarial noise into the original images.

**Additional Concerns and Questions for the Authors:**

1. $\tilde{v}\_{\phi}$ is learned by minimizing Eqn. 6. I am confused whether the authors learned one $\tilde{v}\_{\phi}$ or a set of $\tilde{v}\_{\phi}$ for each self-attention stage. In the first case, $\tilde{v}\_{\phi}$ will be input-independent, then it will no longer be a noise added to the input. 

2. The Eqn. 2 in the paper is not correct. \Delta should be a subspace, not vectors.

3. There is no discussion of related work on the nullspace of transformers, such as the work in [1].

**References:**

[1] Brunner, Gino, Yang Liu, Damian Pascual, Oliver Richter, Massimiliano Ciaramita, and Roger Wattenhofer. "On identifiability in transformers." arXiv preprint arXiv:[1] Brunner, Gino, Yang Liu, Damian Pascual, Oliver Richter, Massimiliano Ciaramita, and Roger Wattenhofer. "On identifiability in transformers." arXiv preprint arXiv:1908.04211 (2019). (2019).


clarity,_quality,_novelty_and_reproducibility: The paper is well-written. The quality and novelty are not high. There is no submitted code to reproduce the results.

summary_of_the_review: Overall, I vote for rejecting. The idea of approximating the nullspace noise of the Vision Transformer (ViT) model is interesting. However, my main concerns about the paper are: 1) the low significance of the proposed method to study the nullspace of ViTs in the paper, 2) the lack of theoretical justification of the proposed method in the nonlinear setting, and 3) the unconvincing applications of the proposed method.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper explores the nullspace ( adding an element on this space does not affect the output) for Vision Transformer. The authors first demonstrate that a non-trivial nullspace exists for the patch embedding matrices. This idea is extended to the non-linear layers of the vision transformer, which is learned via simple optimizations. 
The applications to image watermarks and unconstrained targeted noise are presented. 
strength_and_weaknesses: Strength

- The introduction of nullspace for analyzing ViT has originality. This paper investigates if the nullspace exists for the linear input layer (patch embedding layer) and non-linear layer (self-attention layer). The patch embedding layer's linear structure produces a larger nullspace than CNNs, as shown in Sec.5.2. 

- The watermark application and the targeted nullspace noise are interesting. They are largely different from conventional adversarial attacks. 

Weakness
- The results of watermark supervision and targeted nullspace noise are not visually attractive.

- Writing quality is not high. 

clarity,_quality,_novelty_and_reproducibility: 
Clarity 
- In the introduction section, the explanations of background and  ViT are long, and the number of references (6 pages) seems too large. The authors can reduce the number of papers for the introduction sections. 

- Figure 1 left bottom equation: What means $\eta$, $\beta_1$, $\beta_2$ is unclear. 

- Figure 1 caption. "right)" seems to be a typo. 

Quality

The application is evaluated only with the visualization of a few images. 
These applications might be evaluated quantitatively, e.g. recognition accuracy for the unconstraint targeted noise. 

Novelty

The introduction of nullspace for analyzing ViT is novel. The two applications are also novel and interesting.  

summary_of_the_review: This paper presents a nullspace analysis of ViT, which have originality. The two applications of nullspace are also interesting. Though it is understandable, the writing and evaluations are not high quality.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: All the reviewers find the problem studied, on the null space of neural networks, interesting. However they find the current draft to be preliminary and not sufficiently developed. In particular they note the following limitations.

1) The proposed approach to find null space vectors for nonlinear models lacks proper theoretical grounding and justification.
2) Not a clear application to improving robustness of the networks.
3) Reduced quality for the proposed watermark application.

Authors provide more intuition and some quantitative metrics during the discussion stage, but the fundamental weakness remain and all the reviewers remain unconvinced of the current draft. Hence I suggest rejection.
justification_for_why_not_higher_score: The paper results are preliminary and reviewers note the following weaknesses

1) The proposed approach to find null space vectors for nonlinear models lacks proper theoretical grounding and justification.
2) Not a clear application to improving robustness of the networks.
3) Reduced quality for the proposed watermark application.
Decision: Reject