A Robust Framework for Graph Construction in Vision Graph Neural Networks - Elsharkawi, Ismael (AUC Knowledge Fountain, 2025)
In Computer Vision, the method of representing an image has a profound effect on the performance of a model. Traditionally speaking, an image is treated as a grid of pixels and can be processed via Convolution Neural Net- works (CNN). An image can also be treated as a sequence of patches. Vision Transformers and MLP-Mixers (Multi-Layer Perceptron Mixers) are two types of models that process an image as a sequence. A more generic representation than grids and sequences would be graphs. That is why Vision Graph Neural Network (ViG) construct a graph for an image and process the image as a graph of patches. However, graph construction is based on K-Nearest Neighbors (k-NN). Using k-NN to construct a graph could lead to missing important edges while enforcing other less important edges in order to satisfy the ”k” constraint on each node’s neighborhood. To overcome this challenge, we present two graph construction methodologies. The first is called Similarity Thresholded Graph Construction (STGC), while the other is called Learnable Reparameterized Graph Construction (LRGC). In STGC, an edge is picked if it has a normalized similarity score higher than a pre-defined threshold. In addition, to fight oversmoothing, we present a decreasing threshold framework. Using STGC, we show experimentally that our model outperforms the State Of The Art graph-based models on ImageNet image classification without introducing a computational overhead. For LRGC, which does not need any hyper-parameter tuning, similarity scores are replaced by learnable attention scores and the threshold for each layer becomes learnable. We prove that LRGC achieves a similar performance to the best hyper-parameter combination of STGC on Imagenette without the need for tuning hyper-parameters.