Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a graph structure learning for images that have no graph structure naturally. Instead of simply computing the pairwise similarity of images to form the edge, This paper proposes to leverage a single statistical test to form the edges between images, namely Sim-S.  In addition, this paper proposed to leverage the multiple statistical tests for robust graph structure learning, namely Sim-M.  Bttention is also proposed to craft the proposed method into an elegant and efficient matrix form for efficacy in real-world tasks. The experiments demonstrate the effectiveness of the proposed method, Sim-S, Sim-M, and Bttention. 
strengths_and_weaknesses: **Strengths**

1. This paper is well-motivated. Since the simple similarity between images can not often capture the relation between the image pairs, thus a more accurate way to compute the similarity between image pairs is needed. 
2. The proposed method is technically sound.  The effectiveness of the single test and multiple tests is well supported by the theoretical analysis in  Proposition 1 and Theorem 1.  The proposed method is also practical since it provides an elegant and efficient matrix form.
3. The experimental results are convincing to me. Sections 3.3 and 3.4 show the effectiveness of the proposed methods, also the robustness of Sim-M to noise.  Table 3 shows the superiority of the proposed methods for clustering tasks. This paper also demonstrates the superiority of the proposed method on downstream tasks.
4. The paper is well organized and easy to follow. The proposed method is easy to implement and reproduce.

**Weaknesses**

1. Although the proposal is simple and practical, fourth-order statistics of features are used in Bttention. Such an operation would be time-consuming.
2. As “Better performance can not be achieved by enlarging k values for MSMT17, as its average sample amount 251 for each individual is only 31” (Line 251) said,  the performance of Bttention will go bad in some cases, and this paper didn’t provide the insightful analysis for this phenomenon.
3. The Preliminary part lacks the introduction of  Statistical Tests. And the Chernoff Bounds part in the section is not clear. The usage and advantages of this term should be discussed.

questions: 1. I would like to see the potential solution to reduce the time of the fourth-order statistics in the **Weaknesses 1** 
2. As footnote 1 said, “all the datasets used in this paper are feature vectors” (Page 5).  Thus I wonder how the proposed method performs while it uses the original features. Since the learned features would be meaningful and less noisy than the original features. 
3.  I would like to see some case studies to show the results of the proposed method, for example, a small graph learned in the real-world graph.
4. I would suggest that there should be more introduction to Statistical Tests in Section 2.1.

limitations: None
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper attempts to build a robust graph structure learning approach over images from the viewpoint of multiple statistical tests. The method is novel and proven theoretically according to the Chernoff Bounds. The corresponding elegant matrix form of that method, named Bttention, is designed for efficiency. The experimental results are solid, and the analysis and conclusions are very sufficient. The story sounds interesting and meaningful. It is a fundamental research to the NeurIPS community.
strengths_and_weaknesses: Strengths:
(1) The effectiveness of multiple tests for graph structure learning is verified both theoretically and empirically on multiple clustering and ReID benchmark datasets. The originality is sufficient.
(2) The Bttention is well-designed in the elegant matrix form which is easy to implement. A high quality contribution on technology.
(3) The logical flow is clear. It first indicates the unreliability of pairwise similarity, then proposes their Sim-M and Bttention in Section 2. Finally, it validates their robustness to noise and shows SOTA performances on downstream tasks in Section 3.
(4) The experiments are very sufficient and well organized. It significantly outperforms previous SOAT methods in clustering and ReID tasks. These results can support the conclusions.

Weaknesses:
(1) This method cannot be adapted to various datasets. As proven in Section 2.2 and empirically shown in Section 3.3, it is only advantageous when the number of samples in each category is large enough in the dataset.
(2) The performance of Bttention will degrade when with too large ENR as discussed in Section 3.3.

questions: (1) How to choose the optimal k value for new datasets?
(2) The reviewer is concerned about whether the code will be made public.

limitations: The authors have discussed the limitations of this paper in detail in the appendix, which is already comprehensive.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The core target of this paper aims to use GCNs with the common neighbor sets to alleviate the impact of noises in expectation, through modeling the vision tasks as the *node classification*. 

At first, the authors theoretically show that using the common node set $\mathcal V_{ij}$ to compute the similarity of $v_i$ and $v_j$,  would help to reduce the variance of the estimation of pairwise nodes. Then, similar to the popular self-attention (which is widely used in Transformer), two graph matrices, $A_{band}$ and $A_{self}$, are designed. Some experiments of ReID and clustering are conducted. 
strengths_and_weaknesses: ### Pros: 

1. The paper is well-written and easy to follow.  
2. The motivation is technically sound. Using more nodes/points to reduce the variance is a reliable scheme. 

### Cons: 

1. As the vision task is viewed as the *node classification*, the size of graph would increase with the size of the dataset. It indicates that the inefficiency problem is an inescapable (and severe) problem. However, there is no discussion in Eq. 8-11. It seems that the model computes a dense similarity matrix, while the authors also claim that the graph is constructed by $k$NN. What's the connection between Eq. 10 and $k$NN? Does it compute $A_{band}$ firstly and then find a $k$NN-approximation matrix that only retains the $k$  largest entries?  Besides, $A_X=XX^T$ is already time-consuming.  It would be better if the authors provide the pseudo-code of the whole procedure in the appendix. 

2. Although the motivation to reduce the impact of noises is convincing, the design in Section 2.3 seems to imitate the self-attention mechanism. In other words, it seems a little irrelevant to Section 2.2 since Eq. 8-11 seems not to be strongly driven by the theoretical results. It looks like Theorem 1 is the explanation of Eq. 8-11, rather than the motivation. 

3. The conclusion of Theorem 1 should be more formal. In other words, it should be described mathematically. What's more, Line 79-81 should appear as a lemma.   

4. The GCN formulation in Eq. 1 is not standard. The authors should clarify it.  

5. I suggest using $\mathcal{Q}$-Attention and $\mathcal B$-Attention. 

Overall, my main concerns come from two aspects, the inefficiency problem and the weak connection between Sections 2.2 and 2.3. I would like to update my score after reading other reviews and the response.    
questions: 1. What's the connection between Eq. 10 and $k$NN? How does the model obtain the sparse graph (as the authors claim in Line 179)? 

2. Is the model expensive, from both time and space perspectives? It is indeed an intrinsic problem of graph models, but the authors should also consider the negative impact. 

3. Could the authors please clarify the connection between Section 2.2 and Section 2.3 more formally? 
limitations: It has been discussed in the appendix.
review_title: null

Meta-review: metareview: All reviews are quite positive and raised concerns have been addressed. 

Accept.
confidence: Certain
Decision: Accept