# Robust Graph Structure Learning via Multiple Statistical Tests

arXiv: https://arxiv.org/abs/2210.03956 · HTML: https://mlsanity.com/paper/2210.03956/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 84 references that are in the map.
- First posted on arXiv 8 Oct 2022.

## Builds on (most cited first, 30 of 37)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Heterogeneous Graph Attention Network](https://mlsanity.com/paper/1903.07293/) (2019)
- [MS-Celeb-1M: A Dataset and Benchmark for Large-Scale Face Recognition](https://mlsanity.com/paper/1607.08221/) (2016)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Heterogeneous Graph Transformer](https://mlsanity.com/paper/2003.01332/) (2020)
- [Deep Learning for Person Re-identification: A Survey and Outlook](https://mlsanity.com/paper/2001.04193/) (2020)
- [Person Transfer GAN to Bridge Domain Gap for Person Re-Identification](https://mlsanity.com/paper/1711.08565/) (2017)
- [TransReID: Transformer-based Object Re-Identification](https://mlsanity.com/paper/2102.04378/) (2021)
- [Graph Structure Learning for Robust Graph Neural Networks](https://mlsanity.com/paper/2005.10203/) (2020)
- [Re-ranking Person Re-identification with k-reciprocal Encoding](https://mlsanity.com/paper/1701.08398/) (2017)
- [Deep Convolutional Networks on Graph-Structured Data](https://mlsanity.com/paper/1506.05163/) (2015)
- [Learning Discrete Structures for Graph Neural Networks](https://mlsanity.com/paper/1903.11960/) (2019)
- [Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings](https://mlsanity.com/paper/2006.13009/) (2020)
- [Adaptive Graph Convolutional Neural Networks](https://mlsanity.com/paper/1801.03226/) (2018)
- [Retrieval-Augmented Generation for Code Summarization via Hybrid GNN](https://mlsanity.com/paper/2006.05405/) (2020)
- [Learning the Graphical Structure of Electronic Health Records with Graph Convolutional Transformer](https://mlsanity.com/paper/1906.04716/) (2019)
- [Differentiable Graph Module (DGM) for Graph Convolutional Networks](https://mlsanity.com/paper/2002.04999/) (2020)
- [Location-aware Graph Convolutional Networks for Video Question Answering](https://mlsanity.com/paper/2008.09105/) (2020)
- [A Pose-Sensitive Embedding for Person Re-Identification with Expanded Cross Neighborhood Re-Ranking](https://mlsanity.com/paper/1711.10378/) (2017)
- [Reinforcement Learning Based Graph-to-Sequence Model for Natural Question Generation](https://mlsanity.com/paper/1908.04942/) (2019)
- [Linkage Based Face Clustering via Graph Convolution Network](https://mlsanity.com/paper/1903.11306/) (2019)
- [Learning to Cluster Faces on an Affinity Graph](https://mlsanity.com/paper/1904.02749/) (2019)
- [Learning to Cluster Faces via Confidence and Connectivity Estimation](https://mlsanity.com/paper/2004.00445/) (2020)
- [GraphFlow: Exploiting Conversation Flow with Graph Neural Networks for Conversational Machine Comprehension](https://mlsanity.com/paper/1908.00059/) (2019)

## Built on by (most cited first, 3 of 3)

- [Face Clustering via Early Stopping and Edge Recall](https://mlsanity.com/paper/2408.13431/) (2024)
- [Enhancing Noise Resilience in Face Clustering via Sparse Differential Transformer](https://mlsanity.com/paper/2512.22612/) (2025)
- [Preserving Geometric Integrity in Graph Prompting via Measure-Constrained Optimal Transport](https://mlsanity.com/paper/2609.23547/) (2026)

## Abstract (arXiv)

Graph structure learning aims to learn connectivity in a graph from data. It is particularly important for many computer vision related tasks since no explicit graph structure is available for images for most cases. A natural way to construct a graph among images is to treat each image as a node and assign pairwise image similarities as weights to corresponding edges. It is well known that pairwise similarities between images are sensitive to the noise in feature representations, leading to unreliable graph structures. We address this problem from the viewpoint of statistical tests. By viewing the feature vector of each node as an independent sample, the decision of whether creating an edge between two nodes based on their similarity in feature representation can be thought as a it single statistical test. To improve the robustness in the decision of creating an edge, multiple samples are drawn and integrated by it multiple statistical tests to generate a more reliable similarity measure, consequentially more reliable graph structure. The corresponding elegant matrix form named B-Attention is designed for efficiency. The effectiveness of multiple tests for graph structure learning is verified both theoretically and empirically on multiple clustering and ReID benchmark datasets. Source codes are available at https://github.com/Thomas-wyh/B-Attention.