1 Introduction↩︎

Deep learning models such as Convolutional Neural Networks (CNNs) [1] and Vision Transformer(ViTs) [2] have shown remarkable capability in image classification performance and have been adopted across several fields, including geophysics [3], bioinformatics [4] and remote sensing [5]. These deep learning models mainly operate on dense grid-based representations of images, requiring computation over large regions that may contain limited task-relevant information. In particular, CNNs often struggle to capture long range dependencies because of their local receptive fields. Consequently, there is a requirement to increase depth of the network. Although ViTs propose solutions for capturing long range dependencies, they are challenged with quadratic computational requirements due to the self-attention mechanism [6].

To alleviate such computational challenges associated with images, researchers have explored grouping structurally correlated pixels into compact regions known as superpixels [7]–[11]. A superpixel is defined as a group of adjacent pixels demonstrating similar characteristics such as color and intensity. An image can be represented as a graph with superpixels as nodes while edges are constructed by heuristics such as \(k\)-nearest neighbors or region adjacency. [12]. Such a representation preserves key characteristics while reducing the pixel-level redundancy. Such graphs open a new direction in image classification capable of harnessing the popular graph-based models such as Graph Neural Network (GNN) [7]–[11]. Although GNNs have shown impressive capabilities in solving many problems for graph-based datasets, they are inherently limited in capturing long-range dependencies due to over-smoothing [13] and over-squashing [14], [15]. However, for image classification, the superpixel graphs may possess semantically important superpixels far apart and may require modeling the long-range dependencies. Consequently, many recent graph learning methods have adopted Graph Transformers [16]–[19], which leverage the attention mechanism to allow each node to attend to all other nodes in the graph. Although GNN frameworks exploiting Graph Transformers seem to capture structural characteristics as well as global relatedness, to the best of our knowledge, they have not been used for superpixel-based image classification.

Graph Transformers (GTs) are one form of GNNs designed to capture long-range dependencies while maintaining permutation equivariance at the node level and permutation invariance in graph level representations [16]. However, GTs and GNNs do not inherently preserve translation or rotation invariance in graph level representations, which are important characteristics to be preserved for image classification. To the best of our knowledge, existing GNN-based frameworks for superpixel-based image classification do not explicitly preserve translation and rotation invariance [7]–[11]. Thus, we arrive at the following research question: how can GTs be utilized on superpixel graphs for image classification while preserving translation and rotation invariance?

To answer the above question, this paper attempts to incorporate translation invariance with GTs using mean centering of the spatial node features. Moreover, we utilize a Principal Component Analysis (PCA) [20]-based approach which is capable of preserving translation and rotation invariant simultaneously. We evaluate the proposed mechanism that preserves translation and rotation invariance within a Graph Transformer framework for the image classification using superpixel graphs constructed from CIFAR-10 dataset [21]. We refer to the proposed approach as SuperGT ¹ in the subsequent parts of the paper. We compare the performance of SuperGT to the state-of-the-art GNN-based models. We note that the SuperGT yields comparable results with respect to the state-of-the-art model, namely, ShapeGNN [7]. However, for the experiments considering varying percentages of available training samples, we observe a lower and unstable performance by ShapeGNN in comparison to SuperGT and other GNN-based models.

In summary, this paper has the following contributions:

1. We propose a framework SuperGT for image classification using Graph Transformers capable of capturing global relatedness along with preserving translation and rotation invariance.

2. We propose to utilize Principal Component-based pre-processing scheme to preserve both translation and rotation invariance simultaneously and can be applied to any superpixel-based image classification frameworks.

3. We conduct extensive experiments demonstrating the effectiveness of SuperGT against standard GNN-based methods and state-of-the-art superpixel based image classification frameworks. Furthermore, we provide critical analysis to the observed performances using the lens of variations in availability of the training samples.

The remainder of the paper is organized as follows: Section 2 discusses the related works in the direction of image classification using superpixel-based graphs and GNNs. Section 3 discusses the image to graph transformation procedure, the PCA-based pre-processing scheme, and the GT backbone. Section 4 discusses the best positional and structural augmentation of graphs, the efficacy of SuperGT compared to popular GNN and state-of-the-art models in the literature, and the ablation study of SuperGT.

2 Related Works↩︎

This section discusses some of the related works that exploit superpixel graphs for image classification using graph-based machine learning. In particular, we focus mainly on studies exploiting graph neural networks as recently, such methods have shown remarkable performance for image classification [7]–[11].

To construct superpixel graphs, most studies follow two paradigms for edge construction for a given set of superpixel nodes: (i) the edges are constructed between two nodes if their corresponding superpixels are adjacent to each other in the image, commonly referred to as a Region Adjacency Graph (RAG) [7], [9]; or (ii) the edges are constructed between two nodes based on node feature similarity often measured by K-Nearest Neighbors (KNN) [8], [10], [11]. Using the first paradigm of superpixel graph construction, Avelar et al. [9] proposed utilizing Graph Attention Networks [22] on RAG of the image for classification. We refer to this as RAG-GAT in our work. Long et al. [8] proposed HGNN, a framework uses the KNN approach for graph construction and showed an improvement in image classification by overcoming over-smoothing issues by using residual connections. Linh and Youn et al. [11] proposed DISCO-GCN that treats superpixels as point clouds and dynamically reconstructs graphs after every convolution layer using KNN technique. Bae et al. [10] proposed IMGCN-LPE framework that initializes node positions using random walks and updates them during the training cycle for addressing the limitations of fixed positional encodings.

Recently, Cosma et al. [7] proposed ShapeGNN which evaluates with both paradigms of graph construction and empirically achieved a better result with RAG-based method. ShapeGNN incorporated superpixel shape information into the feature vector and produced shape encoding using GNNs over superpixel boundary. Presently, to the best of our knowledge ShapeGNN is the state-of-the-art method proposed for superpixel-based image classification.

All the above studies focused on improving the classification performance by exploiting a graph construction paradigm along with an efficient GNN-based model. However, this paper focuses on understanding basic limitations with GNNs exploiting superpixel-based graphs for image classification task. Moreover, this paper attempts to revisit the preservation of fundamental properties such as translation and rotation invariance critical in image classification task.

3 Methodology↩︎

This section discusses the methodologies along with key techniques used for the proposed framework SuperGT. Firstly, we revisit the approach used to build the superpixel graph which is followed by proposed methodologies to preserve the translation and rotation invariance for superpixel-based image classification. Finally, we discuss the GT backbone used in SuperGT.

3.1 Image to Graph Transformation↩︎

The aim of superpixel segmentation algorithms is to cluster pixels of a given image that share various properties such as color and spatial location. There are many algorithms for segmenting images into superpixels. Among these methods, Simple Linear Iterative Clustering (SLIC)[23] is the most widely used. We utilize SLIC in our framework for generating the main results. The resulting superpixel graph encodes node’s attribute/feature in terms of mean color, color variance, fraction of region covered by the superpixel in the image, and cartesian coordinates of the centroid of the superpixel. Therefore, the node feature vector has a total of nine dimensions. All node features are normalized to the range [0,1]. As discussed in Section 2, a superpixel-based image representation can be constructed as RAG or KNN graph. We employ RAG approach as demonstrated in the Figure 1.

3.2 Geometric Invariance↩︎

Ideally, for image classification, the framework should be invariant to the rotations and translations of the underlying image. To the best of our knowledge, none of the superpixel-based image classification frameworks explicitly provide either translation or rotation invariance. Recently, a notable attempt was made by Cosma et al. [7], who explored geometric invariance through the proposed ShapeGNN framework. In particular, they considered replacing the GNN backbone of ShapeGNN with an EGNN [24] to incorporate geometrical equivariance. Further, they also investigated simple pre-processing strategies to introduce rotation invariance. However, these approaches resulted in reduction of the classification performance. These observations highlight the challenges of incorporating invariance into superpixel-based image classification frameworks while maintaining classification performance.

3.2.1 Preserving Geometrical Invariance using Principal Component Analysis (PCA) [20]↩︎

For superpixel-based image classification preserving geometrical invariance, we propose to utilize a PCA-based pre-processing scheme that can incorporate both translation and rotation invariance. Let \(G_i\) be a graph that corresponds to the image \(I_i\). Let \(F_i\) denote the node feature matrix of \(G_i\) where \(F_i \in \mathbb{R}^{n \times 9}\), and \(n\) denotes the number of nodes in the graph. Let \(C_i \in \mathbb{R}^{n \times 2}\) be the submatrix of \(F_i\) which carries the centroid coordinates of the superpixels. Presuming the image segmentation algorithm is translation and rotation invariant, such actions on \(I_i\) would only transform the \(C_i\) matrix while remaining node attributes are unchanged.

Principal Component Analysis (PCA) is primarily used for dimensionality reduction in machine learning. It can be shown that the PCA transformation of a given data point is invariant to rotation and translation of the input set of data points. Several approaches leveraging this property have been proposed in point cloud analysis [26], [27]. We apply PCA with 2 principal components to the matrix \(C_i\), considering each centroid row as an input data point. The mean centroid is defined as \(\mu = \frac{1}{n}\sum_{i=1}^{n} c_i\), where \(c_i \in \mathbb{R}^2\) denotes the \(i\)-th row of \(C_i\). The canonical representation for a centroid \(z_i\) is given by: \[z_i = \begin{pmatrix} v_1^\top (c_i - \mu) \\ v_2^\top (c_i - \mu) \end{pmatrix} \label{eq:1}\tag{1}\] where \(v_1, v_2 \in \mathbb{R}^2\) are the first and second principal components (eigenvectors of the covariance matrix \(\Sigma = \frac{1}{n}\tilde{C}_i^\top \tilde{C}_i\), with \(\tilde{C}_i = C_i - \mathbf{1}_n\mu^\top\)), ordered by descending eigenvalue. We will now formally show that PCA is capable of preserving both translation and rotation invariance properties.

3.2.1.1 Translation Invariance

Here, let \(z'_i\) denote the canonical representation obtained after applying a translation to the image. Let each centroid be translated by \(t \in \mathbb{R}^2\), i.e.\(c' = c + t\). The new mean will be \(\mu' = \mu + t\). Substituting these in Equation 1 : \[z'_i = \begin{pmatrix} v_1^\top (c'_i - \mu') \\ v_2^\top (c'_i - \mu') \end{pmatrix} = \begin{pmatrix} v_1^\top (c_i + t - \mu - t) \\ v_2^\top (c_i + t - \mu - t) \end{pmatrix} = \begin{pmatrix} v_1^\top (c_i - \mu) \\ v_2^\top (c_i - \mu) \end{pmatrix} = z_i\] Therefore, \(z'_i = z_i\) for all centroids, establishing the translation invariance of the canonical representation.

3.2.1.2 Rotation Invariance

Here, let \(z'_i\) denote the canonical representation obtained after applying a rotation to the image. Let each centroid be rotated by a \(2{\times}2\) rotation matrix \(R\), where \(RR^\top = I\). The transformed centroid is given by \(c'_i = Rc_i\), and the corresponding mean becomes \(\mu' = R\mu\). The centered coordinates transform as \(\tilde{C}_i' = \tilde{C}_iR^\top\),and therefore the covariance matrix becomes \(\Sigma'=\frac{1}{n}\tilde{C}_i'^\top\tilde{C}_i'=R\Sigma R^\top\). Let \(v_k\) be an eigenvector of \(\Sigma\) with eigenvalue \(\lambda_k\). Then \(\Sigma'(Rv_k)=R\Sigma R^\top Rv_k=R\Sigma v_k=\lambda_k(Rv_k)\), showing that \(Rv_k\) is an eigenvector of \(\Sigma'\) with the same eigenvalue. Hence, the principal components rotate together with the data, i.e., \(v_k' = Rv_k\) for \(k=1,2\). We resolve this sign ambiguity of eigenvectors by checking the sign of its \(y\)-component and replacing \(v_k\) with \(-v_k\) if \(v_{k,y} < 0\), and leaving as it is otherwise.

Substituting into Equation 1 , \[z'_i = \begin{pmatrix} v_1'^\top (c'_i-\mu')\\ v_2'^\top (c'_i-\mu') \end{pmatrix} = \begin{pmatrix} (Rv_1)^\top(Rc_i-R\mu)\\ (Rv_2)^\top(Rc_i-R\mu) \end{pmatrix} = \begin{pmatrix} v_1^\top(c_i-\mu)\\ v_2^\top(c_i-\mu) \end{pmatrix} = z_i.\] Therefore, \(z'_i = z_i\) for all \(i\), establishing the rotation invariance of the canonical representation.

In essence, mean-centering is responsible for translation invariance, and as the principal components are equivariant with respect to rotations of the input set of data points, resolving a data point with respect to them produces a rotation invariant representation.

3.2.1.3 Empirical Remarks

During empirical evaluation, we found that PCA-based scheme preserving translation and rotation invariance simultaneously resulted with a slight decrease in accuracy for image classification. Thus, in this paper, all the subsequent experiments employ only mean-centering of centroid coordinates, thereby preserving only the translation invariance.

3.3 Graph Transformers↩︎

Motivated with the capabilities and research gaps with recently proposed GNNs for superpixel-based image classification, this paper uses Graph Transformer (GT), a GNN replacing traditional message passing framework with self-attention mechanism capturing local and global dependencies between relevant nodes in the graph [16]–[19]. GTs are capable of harnessing both structural and positional information and thus are more expressive at capturing long-range dependencies.

3.3.0.1 Positional and Structural Encoding

GTs usually treat the input graph as a fully connected graph. This leads to loss of structural information (adjacency) that is inherent with the graph [28]. For this purpose, positional encoding (PE) and structural encoding (SE) are concatenated with the original node features so that the structural biases can be reintroduced. PE/SE aids in identifying the structural and semantic properties of nodes in the graph and the subgraph respectively [16], [18]. Although there are abundant number of PEs have been proposed in past, we evaluate a commonly used PE based on eigenvectors of the Laplacian matrix (LapPE) [17], [29]. Moreover, we also evaluate a Laplacian-based positional encoding (ElstaticPE) derived from electrostatic interactions between nodes [17], [30]. For SE, a commonly used approach is the diagonal of the \(m\)-step random walk matrix (RWSE) [31]. We explore such traditional PE/SE with the superpixel graph along with representations from Graph Positional and Structural Encoder (GPSE) [30], a pre-trained foundational model for producing rich structurally informed node embeddings.

3.3.0.2 Architecture:

In recent past, several architectures of GTs have been proposed [16], [18], [19], [32]–[34]. This paper uses the GT framework proposed by Rampášek et al. (GraphGPS)[18] to build the graph transformer layer for SuperGT model. A layer in SuperGT can be defined by the following equations:

\[\begin{align} \mathbf{X}_{M}^{\ell+1} &= \text{MPNN}^{\ell}\left(\mathbf{X}^{\ell}, \mathbf{A}\right) \\ \mathbf{X}_{T}^{\ell+1} &= \text{GlobalAttn}^{\ell}\left(\mathbf{X}^{\ell}\right) \\ \mathbf{X}^{\ell+1} &= \text{MLP}^{\ell}\left(\mathbf{X}_{M}^{\ell+1} + \mathbf{X}_{T}^{\ell+1}\right) \end{align}\]

For \(l_{th}\) layer, \(\mathbf{X}^{\ell}\) denotes the input nodes features along with the PE/SE. \(\mathbf{A}\) denotes the adjacency matrix of the input graph. We utilize GAT [22] convolution policy for the \(\text{MPNN}^{\ell}\). The \(\text{GlobalAttn}^{\ell}\) denotes the global attention that allows the nodes to attend all the other nodes. Our model uses 7 such layers to derive rich node embeddings which are then pooled and passed into a neural network for the final multi-class prediction. We summarize the SuperGT framework in Figure 2.

3.4 Training SuperGT↩︎

We train the model with the pre-defined training split of CIFAR-10 [21], which contains 50K images, i.e., 500 images for each class. We evaluate on test split, which contains 10K images. We utilize AdamW [35] with a weight decay of 7.7e-04. We use the cosine annealing scheduler proposed by Loshchilov et al. [36] with initial learning rate as 9.0e-04 and minimum learning rate as 2.5e-05. We use cross entropy loss with a label smoothing factor of 5e-02 to improve generalization over the data with a batch size of 512. The training was conducted for 150 epochs. The hyperparameter search for learning rate, dropout, weight decay and batch size were determined using a Bayesian optimization framework namely, Optuna [37]. For this search, 10K images were sampled from the training split while respecting the class distribution, i.e., 100 images for each class.

4 Experiments↩︎

We evaluate the efficacy of SuperGT on CIFAR-10 dataset [21] against standard GNN architecture and state-of-the-art segmentation-based GNNs for image classification with the aim of answering the following questions:

• Which positional and structural encoding (PE/SE) scheme is the most effective for SuperGT?

• How does SuperGT compare to existing models in literature for superpixel based graph classification and how does its performance change under limited training data?

• How robust is SuperGT to noisy data during inference?

While the main results uncover the above questions, we also perform some ablation studies considering PCA-based preprocessing, KNN graph construction, and incorporating shape encoding using Hu-moment [38].

4.1 Optimal PE/SE↩︎

As discussed in Section 3.3, we consider LapPE, ElstaticPE, RWSE and GPSE variants for finding an optimal PE/SE for image classification task using superpixel graphs and graph transformer. For each PE/SE, we experiment with two types of \(\text{GlobalAttn}^{\ell}\): (i) Transformer [6], and (ii) Performer [39]. Table 1 presents a comparison for the results obtained using these models. We notice a marginal improvement in performance by using PE/SE compared to using none. Interestingly, the similar trend has been observed in previous works on CIFAR-10 KNN superpixel graphs [18], [30]. The plausible reason for such observation indicates that \(\text{MPNN}^{\ell}\) in the layer might be able to capture the inherent structural information of the superpixel graph.

Nevertheless, we record that the three best performing PE/SE augmentations under the Performer mechanism belong to the GPSE [30] family. This is favorable because the Performer attention mechanism and the GPSE [30] scale linearly with the number of nodes. In contrast to Laplacian-based encodings such as LapPE [17], [29], GPSE [30] embeddings are outputs of a pre-trained GNN and do not require computationally expensive matrix decompositions. Among all the variants, GPSE [30] pretrained on GEOM [40] achieves the best performance. Therefore, we used this particular combination in all subsequent experiments using the proposed model, namely, SuperGT.

4.2 Performance of SuperGT compared to the baselines↩︎

We compare SuperGT with popular GNN models such as GCN [41], GAT [22], GATv2 [42], GraphSAGE [43], PNA [44] and GIN [45] along with several segmentation-based GNNs such as DISCO-GCN [11], RAG-GAT [9], HGNN [8], IMGCN-LPE [10] and ShapeGNN [7]. Furthermore, we also consider a simple Multi-Layer Perceptron (MLP). The results are shown in Table 2.

It is evident from Table 2 that simple MLP performs better than message passing GNNs such as GAT, GCN, GIN, GATv2, and GraphSAGE. This suggests that local message passing may be insufficient for effectively modeling RAGs, motivating the exploration of more complex graph learning models. However, PNA and GraphSAGE shows considerably better performance than simple MLP.

SuperGT demonstrates a strong performance when compared to the best in standard GNN, i.e., PNA and appropriate baselines for superpixel-based image classification except ShapeGNN. Although SuperGT performs comparable to ShapeGNN, it should be noted that unlike ShapeGNN, SuperGT is invariant to translations of the underlying image and does not require coordinates of the boundary points of each superpixel. The superior performance of SuperGT can be attributed to the ability of \(\text{GlobalAttn}^{\ell}\) to capture long-range dependencies.

4.2.0.1 Performance under limited training data

Now we evaluate SuperGT on the same test split while training it on different sizes of training samples. For each training set size, we generate different training subsets using 5 random seeds and evaluate the resulting models on the fixed test set, allowing us to estimate the mean and variability of model performance. We perform this experiment for ShapeGNN and two top performing GNN baselines, PNA and GraphSAGE. We show the results in Figure 3 (a) and it is evident that SuperGT outperforms other models across different sizes of training data. ShapeGNN exhibits noticeably higher performance variance at smaller training set sizes. This indicates high sample efficiency and high robustness of SuperGT to limited supervision.

4.3 Robustness to structural noise↩︎

We evaluate the robustness of models under three types of structural noise applied to the test graphs: (i) randomly adding edges, where the number of added edges is a fraction \(f\) of existing edges, (ii) randomly removing nodes with probability \(p\) using samples from a Bernoulli distribution, (iii) randomly removing edges with probability \(p\) using samples from a Bernoulli distribution. We show the results for each type in Figures 3 (b),3 (c) and 3 (d) respectively. To isolate the effect of structural perturbations, we omit PE/SE in this experiment. We observe that for each of these experiments, our model outperforms other models across all values of \(p\) and \(f\). Furthermore, the performance of SuperGT degrades more gracefully as the noise level increases. This can be attributed to the fact that GNNs rely mainly on the local structural information whereas SuperGT can leverage global information using the \(\text{GlobalAttn}^{\ell}\).

4.4 Ablation Studies↩︎

4.4.0.1 Effect of PCA-based pre-processing

We proposed a PCA based pre-processing approach in Section 3.2.1 to incorporate both rotation and translation invariance with respect to the underlying image. Table 3 demonstrates performance by PCA-based processing. Surprisingly, using this pre-processing leads to decrease in performance by 2.5% when compared to simple node centering-based pre-processing. However, we note that this approach indeed performs better than multiple existing graph-based baselines in Table 2.

4.4.0.2 Traditional shape encoding degrades performance

Instead of using PE/SE, we explore utilizing shape encoding defined by the boundary of each superpixel. Hu moments [46] generate a 7 dimensional representation for a given shape that is translation, rotation and scale invariant. To reduce boundary noise introduced by the segmentation algorithm, we simplify superpixel contours using a polygon approximation algorithm, Douglas–Peucker algorithm [47], and then compute Hu moments [46] to obtain the shape descriptor. As demonstrated by Table 3, this method led to a marginal performance decrease of 0.3%. This marginal decrease doesn’t allow for a proper assessment of using this shape encoding.

4.4.0.3 Spatial coordinates improve performance

We ablate the spatial coordinates in the node attributes. This is a simple way to introduce rotation and translation invariance with respect to the underlying image. This led to a drastic decrease in performance of 5.7%. A probable reason for this is that without the spatial information the model will be unable to differentiate between structurally similar superpixel connectivity that differ only in their scale or shear within the image, which might be critical for resolving visually ambiguous classes. This observation is consistent with the findings of Rodrigues et al. [12].

4.4.0.4 KNN graphs degrade performance

We now evaluate SuperGT on KNN graphs derived from CIFAR-10 dataset following the procedure proposed by Dwivedi et al [29]. This led to a drastic decrease in performance of 4.8% when compared to the proposed SuperGT model where graphs are constructed using RAG.

5 Conclusion↩︎

In this work, we proposed SuperGT, a graph transformer-based framework that addresses the long range dependency limitation for superpixel-based image classification. As the traditional image classifiers like CNNs preserve translation invariance, we revisit and propose pre-processing techniques which can preserve translation and rotation invariance in superpixel-based graphs. In particular, we present a Principal Component Analysis (PCA)-based framework capable of preserving both of the invariance simultaneously. We utilize graph transformer to capture long range information and evaluate the proposed framework SuperGT on CIFAR-10 benchmark data. With suitable experiments, we show that SuperGT achieves state-of-the-art performance (comparable to previous state-of-the-art with marginal improvement) when models are trained on all the training samples. We demonstrate that SuperGT demonstrates stronger performance than state-of-the-art when subjected to different variance of training samples. Thus, we conclude that Graph Transformers can serve as an effective alternative to message-passing GNNs for superpixel-based image classification while incorporating desirable geometric invariance properties.

References↩︎

---

1. Our code is available at: https://github.com/SarabeshwarBalaji/SuperGT↩︎