Is an Image Also Worth 16x16=256 Superpixels? A Framework for Attentional Image Classification Pedro Henrique da Costa Avelar∗,ufrgs,uom , Anderson R. Tavaresufrgs , and Luı́s C. Lambufrgs
arXiv:2605.27144v1 [cs.CV] 26 May 2026
ufrgs
Institute of Informatics, Federal University of Rio Grande do Sul (UFRGS), 91501-970, Porto Alegre, Rio Grande do Sul, Brazil uom Division of Informatics, School of Health Sciences, Imaging and Data Science, Faculty of Biology, Medicine and Health, University of Manchester, M13 9GB, Vaughan House, Portsmouth St, Manchester, United Kingdom
Abstract
cross-domain generalization and future innovations in hybrid attentional frameworks, and showing that an image can also be worth 16 × 16 superpixels.
Superpixel-based image classification has traditionally leveraged graph neural networks (GNNs) for processing irregular image representations. Recent advances in computer vision, driven by Vision Transformers (ViTs), have introduced new paradigms in self-attentional models, surpassing convolutional neural networks (CNNs) in various tasks. However, a synergistic connection between GNNs, superpixels, and transformers remains unexplored. In this work, we propose Superpixel Transformers (SPT), a novel framework that unifies superpixel-based image classification and ViTs. SPT generalizes the Superpixel Image Classification with Graph Attention Networks (SICGAT) model and ViT to support arbitrary superpixel-based chunking strategies, connectivity graphs, and positional encodings. We introduce refinements including a multidimensional sinecosine positional encoding and an enriched patch data structure that fully incorporates superpixel shape and color information. By testing SPT across datasets such as CIFAR10, FashionMNIST, and Imagenette, with various superpixel generation and graph connectivity strategies, we demonstrate that SPT achieves superior performance compared to previous superpixel-based GNN methods and remains competitive with ViTs. Notably, our approach addresses the limitations of SICGAT, such as information loss during pixel aggregation, and shows how constrained graph connectivity can enhance ViT performance. SPT bridges the gap between superpixelbased and transformer models, opening avenues for
1
Introduction
Although superpixel-like segmentation algorithms have been used together with Neural Networks for processing images since 2005 [9], it was only in 2017 that modern iterations of Graph Neural Networks started using superpixel algorithms to generate image graphs [28]. This scheme has been worked on and improved throughout many iterations throughout the years. In particular, using a Graph Neural Network kernel with an attentional mechanism [4] greatly improved performance from previous works even when using a more restrictive adjacency matrix, which the authors claim makes the problem harder to solve. Shortly after this development of using attention mechanisms and Superpixels for image processing, the uncontested leadership of Convolutional Neural Networks (CNNs) in Computer Vision was upended by another attention-based approach: Vision Transformers [16]. Vision Transformers have since become a staple in Computer Vision and, despite being notoriously data-hungry, they have surpassed CNNs in many applications, including image classification, object detection and semantic image segmentation [34]. To the best of our knowledge, no previous work has yet linked Vision Transfomers with GNN- and Superpixel-based image classification. In this paper we will bridge the gap between Superpixel Image Classification and Vision Transformers and put
∗ This work was developed entirely at UFRGS.
1
them into a framework of attentional image classification. We attempt to ablate which components are crucial for better performance and generalisability in an attempt to challenge the notion that Graph Neural Networks cannot be deep and unify both fields. We do so by proposing a framework that generalises both the Superpixel Image Classification with Graph Attention Networks (SICGAT) model proposed in [5] as well as the Vision Transformer (ViT) model [16], while providing a framework that can work with multiple patch types and allowing for arbitrary graph connectivities. We include tests with both grid-patches like in ViT and also extend SICGAT’s superpixels into a patch-like data-structure that fully utilises the information from both the superpixel’s shape as well as the colour information of each component superpixel. We test our models with three common graph strategies from the literature [28, 5, 16, 30] and show that Vision Transformers might benefit from a more constrained connectivity graph between its patches. Finally, we propose an extension of the Sine-Cosine positional embedding from [38] to an arbitrary number of dimensions, which we show to be highly beneficial for working in a superpixel environment. We hope that these developments will allow the areas of Superpixel Image Classification to be unified with those of mainstream Computer Vision and that these models spur further investigation on different superpixel formats for future ViT work.
2
Background
2.1
Image superpixels
pixels. Distances between cluster means and respective and pixels are calculated as the L2 norm of the two normalised Euclidean distance vectors: one for the colour component and one for the spatial component, normalised by the expected maximum spatial distance (S) and the maximum expected colour distance, which is usually represented by a manuallyselected constant m2 . While the usual representation for images – a grid/tensor of pixels – can already be seen as a regular grid graph (a lattice), superpixels induce a more natural graph representation of an image [28, 5]. This is due to the fact that, since superpixels are usually irregular, the connectivity between superpixels requires a more abstract structure than a simple grid or hypercube. Thus, superpixels which have bordering pixels become connected between themselves. Therefore, a superpixel-based representation is more suitable for processing with Graph Neural Networks (Section 2.2).
2.2
Graph Neural Networks
Graph Neural Networks (GNNs), pioneered by [31], have had considerable impact on Machine Learning [7]. This is due, in part, to the Graph Convolutional Network of [25], which made GNNs accessible in modern deep learning frameworks. This has been followed shortly by demonstrations of the power of GNN to model inductive biases of a problem by carefully crafting graphs that matched the structure of the problem [19, 7]. A notable example in this line was the development of NeuroSAT, which modelled a boolean satisfiability (SAT) instance into a bipartite graph between literals and clauses, allowing communication to flow between these iteratively until the neural “solver” reaches equilibrium [33]. GNNs can be interpreted through many different lenses, of which the most common are either a generalization of convolutions and convolutional neural networks [28, 25, 18], or by interpreting GNNs as what are called “Message-Passing Neural Networks” (MPNN) [19, 33]. In summary, under the MPNN framework, a simple graph neural network will receive a graph G = {V, E} composed of a set of vertices v ∈ V and edges e ∈ E, with edges connecting a source s ∈ V and a target node t ∈ V e = (s, t). The neural network will first embed the attributes of each of the nodes through a usually learned function so that we have x0v = f (v) and then propagate the information between the nodes using the adjacencies defined through the edges. Under the MPNN
Superpixels are groups of pixels in semantically similar areas of an image. A number of techniques exist to generate superpixels from images, such as SLIC [1], SNIC [3], SEEDS [37], ETPS [47], and SH [42]. Out of these techniques, SLIC is widely thought of as one of the most stable and is still recommended over other state-of-the-art algorithms [35]. SLIC is a modified version of the k-means clustering algorithm, which only attempts to assign points to cluster centroids if these points are inside a 2Ssized square centred in the centroid, where S = N/k, with N being the number of pixels in the image and k the desired number of superpixels. It works by initialising k cluster means Cj composed of a colour component cCj and a spatial component sCj , and then iteratively assigning pixels to clusters, and updating the cluster means based on their component 2
framework, this is seen as each of the nodes u being a neural computer g with state xu which then exchanges messages mtu = g t (xtu ) at a discrete time step t (which can also be interpreted as a layer). These messages then are aggregated through some, usually order-invariant, function a on the node’s neighbourhood N (u) to form the basis of the next time steps’ state xt+1 = a({mt+1 u v , v ∈ N (u)})
widespread was that of using Bidirectional Encoder Representations from Transformers (BERT) [15], allowing all elements to attend to all others, and using a learned positional embedding instead, which was deemed more appropriate for the vision context and used in the Vision Transformer paper [16]. 2.3.1
Graph Attention Networks
Graph Attention Networks (GATs) [39] were origi-
2.3
Self-attention in Sequences, Im- nally developed in 20171 after a surge of interest in Graph-based neural networks [7] due to in part to ages and Graphs the Graph Convolutional Network model [25] making graph neural networks accessible in modern deep learning frameworks. Graph attention networks function in a very similar way to other GNN architectures, except that they mediate the message-passing between neighbours through a self-attention mechanism, allowing the network to learn how to prioritise information flow depending on the each node’s information content. This architecture was further refined to allow for the attentional mechanism to be utilised to a higher potential [10]. Is is possible, however, to draw a relationship between GATs and Transformers. In fact, if we assume that a Transformer’s attention mask can be treated as the adjacency matrix in a GAT, it is clear that both architectures work in a similar way, with a layer transforming each input/node, and then having self-attention mediating the information between non-masked inputs/neighbours. GATs differs from Transformers almost only through the lack of specific layers in the update block, such as residual/skip connections and layer/batch normalisation of the input. This similarity has been exploited to develop graphspecific transformer architectures through adopting a graph-specific positional embedding using Laplacian eigenvectors [17].
Self-attention establishes connections between different positions of a sequence or set to construct representations, and one of the most successful earlier applications was to provide a learned mapping from sentences between different languages during machine translation [6]. This approach was then successfully applied in many different tasks, including providing approximations to NP-Complete problems such the Travelling Salesperson Problem [40]. However, most of these earlier methods still used other architectural patterns, mostly RNNs, whose input was mediated through attention. Soon after the development of self-attentional mechanisms to mediate the sequences generated through RNNs, the development of the Transformer model [38] showcased the power behind attentional mechanisms. The Transfomer exclusively uses selfattention to mediate the exchange of information between elements of a sequence, which mitigated common RNN issues, such as challenges with long-time dependencies [32, 20] and the inherent lack of parallelism [38]. This new architectural pattern has then been widely adopted and has had applications ranging from Natural Language Processing [29], to Computational Chemistry [43, 21, 41], Computational Biology [11, 13] and, of course, has also recently been widely applied in image processing through the development of the Vision Transformer [16]. The self-attention mechanism in text-based networks are often mediated both through a positional embedding, as well as an attention mask which limits which values in the sequence an element can attend to. The original Transformer, due to its language model purpose, limits the attention mechanism so that elements can only attend to those before it, and uses a Sine-Cosine expansion depending on the position of the element in the sequence to help the attention heads to identify the distance between two attended elements. Another option which also became
3
Related Work
While an image is usually represented as a grid of pixels, as mentioned above, if one were to work using superpixels instead, a graph representation becomes required due to the irregular connectivity pattens between superpixels, and has been widely used together with Graph Neural Networks for Superpixel Image Classification [28, 18, 5, 30]. However, to allow for such general connectivity patterns, GNN-based 1 Arxiv version released in 2017 https://arxiv.org/abs/ 1710.10903
3
methods often aggregate a node’s neighbourhood us- 4 Superpixel Transformers: A ing the same weight for every neighbour. This imGeneral Framework for Atplies that simple GNNs would have a lower representational power than convolutional neural networks, tentional Learning in Images since CNNs allow for a different weight to be used for each value in the “neighbourhood” (the convolution In this section we provide the definition of our model window). In fact, a pixel-grid-based GNN was tested that generalises the SICGAT model the ViT architecture. We first start by providing a step-by-step in [28] and had a worse performance than a CNN. description of the differences between SICGAT and the ViT architectures, and then we follow with a description of a concrete formalisation of our model. The model presented in Superpixel Image Classification with Graph Attention Networks, here onwards referred to as SICGAT, [5] expanded on pre- 4.1 Key differences between Supervious work to allow for a GNN that enables a pixel Image Classification and Vipseudo-convolutional representational power. This sion Transformers was achieved through using multiple attention heads to mediate the information transfer between nodes Figure 1 shows a comparison of the SICGAT and ViT in a graph, which allows different “soft”-weights to architectures. From this, we identify the main differbe learned by the network when aggregating between ences between these two approaches: (1) Chunking neighbourhoods. Surprisingly, however, the perfor- strategy, (2) pixel information aggregation, (3) pomance of these models reached its limit with a much sitional embeddings, (4) architectural differences besmaller amount of attention heads than the medium tween a GAT and a Transformer block, (5) differences connectivity in the superpixel graph they built (which in chunk connectivity, and (6) pooling vs virtual clasis a Region Adjacency Graph). In this paper we sification node. We discuss in depth each of these will provide a generalisation of their method and differences next. show that our model has better results even than Chunking Strategy The first and most obvious their “hard” baseline of using a VGG architecture difference between the two models is the fact that that only has access to a superpixel-segmented image while SICGAT uses a superpixel algorithm to chunk where each superpixel’s pixels have their RGB values the image into superpixels, ViT chunks images into set to their common average. Our model also over- equally-sized rectangles. However, this scheme had comes the information loss they show in Figure 3. also previously been used in other superpixel image classification algorithms, such as in MoNET [28], and the approach followed by SICGAT could easily be Recently there has also been a comparative study adapted to also use equally sized chunks. The main on the best graph construction method for GCNs [30], reason, however, why SICGAT performs better when which showed an improved performance on [5]’s work chunking the image into superpixels instead of regular even when using a GNN with a lower representational patches is due to the pixel information aggregation power [46]. They provide a thorough study show- scheme. Pixel Information Aggregation Most supering an ablation of various parameters used to build a GNN for SIC and argue that performance was capped pixel image classification methods aggregated the inat very shallow layer-depths. In this paper we will formation from all of a chunk’s pixels into a single also perform a thorough exploration of an attention- value, such as taking the average value of pixel inbased GNN model which, thus, has a higher represen- tensities around the pixel. This was also followed by tational power than GCNs and is at least as powerful SICGAT, and it was shown to cause heavy informaas a Weissfeiler-Lehman test [46]. Through our ab- tion loss, as can be seen in Figure 3. ViTs mitigate lation, we show that, although more layers did not this by making a linear projection of the flattened always cause better performance, the layer depth of pixel inputs for each chunk, which allows the netour best-performing model often reached our cap for work to learn to use the information from every pixel the number of layers (12), which allows for networks in a chunk, mitigating the information loss present in four times as deep as the ones used in (author?) [5] SICGAT and other methods such as MoNet. and (author?) [30]. Positional Embeddings Another difference be4
Average pixel intensity and position
Linear Projection
* 0
1
2
3
4
5
6
7
8
9
GAT Encoder
Transformer Encoder
MLP Head
Graph Pooling
MLP Head
Class Predictions
Class Predictions
Figure 1: The ViT architecture [16] (left) and the SICGAT architecture [5] (right). Note that, apart from the main self-attention encoding layer, the adjacency graph masking and the fact that SICGAT compresses all input through averaging the channel information of the superpixel instead of having access to all pixels, both architectures are remarkably similar.
5
and immediately follows it with a linear/MLP block to update a node’s information. The transformer layer instead first norms information before either the multi-head attention or MLP blocks, and then uses a residual approach to update the information instead of directly editing it, which has been shown to be an easier problem to solve and, thus, more efficient parameter-wise. Chunk Connectivity Another difference is how connectivity is handled. Many of the earlier works in Superpixel Image Classification followed the same connectivity scheme as done by MoNet: a KNN graph based on chunk position. SICGAT tested their architecture only on a more restricted version of the problem, using instead a Region Adjacency Graph (RAG), arguing that it was both a harder problem as well as being closed conceptually to a convolution block, since only chunks that were physically connected would be also connected in this scheme. ViTs eschew this altogether and treat the image as a fully connected graph, leaving for the attentional mechanism to route the information flow between chunks. Pooling vs virtual classification node Finally, the last major difference between these two models is that, while SICGAT average-pools the information in all nodes before feeding it into a classification head, ViTs again followed the traditional Transformer approach of addeding a virtual classification node, which is then passed to the classification head. This would be equivalent to adding a virtual graph node, which is also another commonly used way to perform graph classification in Graph Neural Networks. In this paper we will follow the original ViT paper and work mainly with the concept of the classification, however it is worthy of note that more recent papers claim better performance by classifying and pooling over every single patch instead [8]. With these differences in mind, we can then build a generalisation that allows for both models to be represented under the framework, which we’ll describe in the following sections.
Embedded Patches
Embedded Patches L×
L×
Norm
Multi-Head Attention
Multi-Head Attention
+
Norm
MLP
MLP
+
Figure 2: The Transformer Encoder [38] used on the ViT model [16] (left) and an equivalent view of a GAT encoder [39] used on the SICGAT model [5] (right). Using an attention mask on a transformer encoder would then be equivalent to using an adjacency amtrix on a GAT encoder, with the only exception being the inner normalisation layers and residual connections. tween these approaches is how positional information is treated. Earlier superpixel image classification models such as MoNet used positional information only as a weighting factor when performing neighbourhood aggregation, simply using this information as an inductive bias for the network. SICGAT extended this by appending each node’s positional information to the node’s features, treating the positional information in the same way as its pixel information. ViTs follow similarly but with two major differences: first, instead of appending the positional information to the pixel information, ViTs follow the previous standard used by Transformers and sums the positional information with the pixel information; lastly, due to the fact that ViTs uses a fixed number of equidistant patches, it encodes the positional information directly through a patch’s index instead of as a transformation of its xy coordinates. Architectural differences A GAT layer and a Transformer layer have significant differences in their architectural components, with GATs being, in a sense, a simpler form of a Transformer Layer, which can be seen in Figure 2. Firstly, The GAT layer using in SICGAT only performs multi-head attention
4.2
The Superpixel Model
Transformer
We define here our framework called Superpixel Transformers (SPT) (Figure 4), which are an attempt at generalising (mostly attentional) SIC models and bridging the gap between these models and Vision Transformers, which see use in mainstream computer vision. Our framework is composed of 6 steps di6
Figure 3: The information loss that happens when converting an image to a superpixel representation and then to its equivalent graph representation.
7
Average Superpixel Position Encoding
Linear Projection
*
Graph-Masked Transformer Encoder
MLP Head
Class Predictions
Figure 4: Our proposed Superpixel Transformer (SPT) architecture. Differently from SICGAT [5] we use the full superpixel information through the patch data structure built in Algorithm 1 and use a variety of superpixel positional encodings to build the input for our encoder network instead of encoding the position together with the patch informaiton in the first GAT layer. Different from ViT [16] we allow for arbitrary superpixel algorithms and also use our model with a variety of adjacency graphs which constrain and help information flow better through the model. Also, due to the superpixel patches possibly having different shapes and positions, we extend and allow for encodings that use the xy coordinates of the superpixel/patch.
8
vided into preprocessing and on how to use the input for the network architecture. In the preprocessing stage, given an image I, we use a chunking strategy fS to divide the image into its chunks/superpixels S that contain information about both the superpixel’s content Sc and its position Sp on the image, then we use a connectivity strategy fG to build a connectivity graph G between the superpixels. Then, the superpixels S and input graph G are passed first encoded through a positional encoding strategy P and a content encoding strategy C, to be passed through a self-attention module (e.g. Transformer Encoder) that will finally be used to produce a classification. We’ll discuss the particular choices for each step below.
For the graph-generation strategies we tested three strategies: 1. Using a fully connected graph fcg, similar to what a Vision Transfomer uses [16]; 2. Using a graph build through a positional k-nearest neighbours knn [28]; 3. And using a Region-Adjacency graph rag, as defined in [5]. These strategies encompass most of the strategies used in previous models. After producing our data structures it is then fed to our end-to-end model, which encode the chunk’s with single fully connected layer as is done with the original ViT [16]. Although our model can also be trained using convolutional stems [45], we do not do so for this paper. We test three different strategies for encoding a node’s position: 1. The original learned positional embedding used in the ViT [16] and proposed by [15]; 2. a simple Linear layer that maps the xy coordinates to the size of the embedding; and 3. an adaptation of the Sine-Cosine positional embedding originally used in [38], but expanded to work with multiple dimensions, the algorithm for which can be see in A. We then apply a transformer encoder network using the adjacency graph to define the attention mask, as well as an extra classification token added which connects to all other tokens. We chose the transformer encoder architecture instead of a GAT encoder due to both more mature Transformer implementations and the fact that the Transformer Encoder includes normalisation layers which are known to help stabilise training. Finally, we extract the classification token to pass on to a classification MLP.
In the preprocessing part we choose two specific chunking strategies: A grid-based chunking (similar to what was done in [16]) that we define precisely in Algorithm A and which returns a Zh×w integer mask showing which superpixel each pixel belongs to, and SLIC0 [2, 1] (here onwards also referred to as SLIC), which provides a similar output but follows a spatiocontent kmeans variation to divide pixels into superpixels. Specifically, we used the implementation in scikit-image version 0.24. After obtaining the mask from a superpixel strategy, such as one of the two above, we use the segment mask to construct a neighbourhood graph G and use both the image and the segment mask into an algorithm that builds out superpixel patch data structure. The data structure we use is composed of three major components: An Rk×2 tensor containing the xy Environment positions of each superpixel, an Rk×3×hchunk ×wchunk 5 tensor that contains the superpixel’s RGB content, and an {0, 1}k×1×hchunk ×wchunk mask that contains We train all of our models from scratch, taking most the superpixel’s shape content. We originally used a of the hyperparameters from [34], with different valhchunk = wchunk = kchunk × S with kchunk = 2 since ues marked by *: that is the search limit on the SLIC algorithm [2], • Learning Rate: 1e-3 but the SLIC implementation we used allowed superpixels with dimensions larger than 2S, therefore • Learning Rate Scheduler*: We Reduce the LR we set kchunk = 3. To allow for batching we proon a plateau by a factor of with a patience of vide a fixed-size superpixel chunk tensor, and thus 20% the number of epochs we also provide a {0, 1}k mask to inform the trans• Dropout = 0.1 former which chunks contain information. The full procedure to build this data structure can be seen in • Global Gradient Clipping = 1.0 for FashionMAlgorithm 1. Note that while we define our model NIST and Imagenette here for 2-dimensional data with 3 channels, it can easily be adapted to more dimensions and a different • Weight Decay: 1e-4 number of channels. For simplicity’s sake we transform any image with only a single channel to a 3• Optimiser: Adam [24], using β1 = 0.9 and β2 = channel grayscale image. 0.999 9
Algorithm 1 Get Superpixel Patches Require: image ∈ RC×h×w , segments ∈ Zh×w , max patches ∈ Z, patch shape ∈ Z2 Require: search patch size ∈ Z, background fill strategy Ensure: spixpresent, spixcenters, spixpatches, spixpatchpresent 1: Initialize spixpresent, spixcenters, spixpatches, and spixpatchpresent if not provided ▷ Default: all zeros 2: Fill spixpatches according to a background fill strategy 3: Mark segments with data: spixpresent[: segments.max() + 1] ← 1 4: for i ← 0 to segments.max() do 5: spixpos ← positions where segments = i 6: spixmins, spixmaxs ← min(spixpos), max(spixpos) 7: spixcenters[i] ← spixmins + spixmaxs−spixmins 2 size 8: y0 , x0 ← ⌊(spixcenters[i] − search patch )⌋ 2 search patch size )⌋ 9: y1 , x1 ← ⌊(spixcenters[i] + 2 10: spixpos ← positions within box [y0 , y1 , x0 , x1 ] 11: Update spixpatches by copying colour information from the i-th superpixel’s component pixels 12: Update spixpatchpresent as a binary mask showing which pixels in spixpatches are contained in i-th the superpixel 13: end for return spixpresent, spixcenters, spixpatches, spixpatchpresent • Due to instabilities on FashionMNIST, we do not backpropagate any batches that cause invalid gradients. Due to compute constraints, we evaluate our models only on 4 datasets: FashionMNIST [44], CIFAR10 [26], Imagenette [22], and Resisc45 [12], which are described in Table 1. We have to limit the batch size, setting it as 512 for the MNIST and CIFAR10 datasets, 64 for the TinyImagenet and 32 for the Resisc dataset. We train Ti-sized models on all datasets except on Resisc45, where we train a B-sized model. We use k=15 for all KNN graphs. Whenever a superpixel would violate a patch’s bounds, we clip it to fit the patch by keeping the centermost pixels, and we used patch of size 3 × S.
6
Results
We trained Ti-sized models [34] using all combinations of graph connectivity strategies, patch building strategies, and superpixel building strategy, for 7 possible layer sizes: 1, 2, 4, 6, 8, 10, and 12. The layer size which provided the best validation accuracy out of the 7 test is shown for each of the combinations in Table 3 and in 5. The best result of the SLIC-based model from this table is shown in 2 as our model, even though we had a better performing model using the grid superpixel generation strategy. The ViT model (Grid-BERT-fcg combination)
achieved a slightly higher but comparable validation performance to our best SLIC model on the CIFAR10 dataset and a slightly lower but comparable performance in the FashionMNIST dataset. Our proposed graph connectivity strategies also boosted the validation performance of the Grid-based superpixel models when compared to the fully connected graphs, and all of our trained models (including the ViT) outperformed the Graph Superpixel Image Classification baselines in all datasets. We trained an SPT-Ti (12 layers, Sine-Cosine, fcg) and a ViT-Ti (12 layers, BERT, fcg) model on the Imagenette dataset to provide a result for which the image was not too small, and both models were comparable and, while no previous SIC work has provided results on higher-resolution images, we believe that due the information loss shown in [5] would make it very hard for these models to perform anywhere close to our models. We trained our SPT-B model with patch size of S ≈ 10 for about 150 on the Resisc45 dataset using a NVIDIA GTX 1070m, after which it achieved a validation accuracy of 53.5%, which only slightly lower performance to that reported for the much larger ViT-B with a patch size of 16 trained from scratch for a similar amount of hours on a higher-end GPU. When testing our model on the Imagenette dataset a SLIC-based Ti model with Sine-Cosine positional embedding achieved 67.7% test accuracy while a gridbased Sine-Cosine model achieved 67.3%.
10
Dataset
Training
Validation
Test
Total
C,W,H
FashionMNIST [44] CIFAR10[26] Imagenette [14, 22] Resisc45 [12]
*54,000 *47,500 *8,996 28350
*6,000 *2,500 *473 3150
10,000 10,000 3,925 †
70,000 60,000 13,394 31500
1, 28, 28 3,32,32 3, 160, 160 3, 256, 256
#Classes
S
10 10 10 45
4 4 10 10
Table 1: The description of the datasets used. C,W,H stand for the number of Channels, Width, and Height of the images. * Original development split was split randomly into train and validation, † No test set provided, results are shown for validation
FashionMNIST Valid Test
Model
CIFAR10 Valid Test
Imagenette Valid Test
VGG-16 [36] VGG-16 SLIC [5]
-
92.0 -
-
77.2 62.9
83.3 -
83.5 -
SICGAT [5] gSLICr-GCN (l=12) [36] bestGCN [30]
-
83.1 81.9 84.2
53.4 -
45.9 59.5 58.5
-
-
86.5 87.9
85.6 87.3
70.6 67.0
69.0 63.3
-
67.9 67.7
ViT [16] (our results) SPT-slic (ours)
Table 2: Results for the three main datasets we tested our models in. Due to compute limitations we did not re-train models and instead use other author’s claimed results. For our models we limit ourselves to using only SPT models using SLIC superpixels and we use the test results of whichever model provided the best valid accuracy in our ablation study. For the ViT model we only consider its original implementation’s hyperparameters: Fully-connected graph with a BERT embedding. For the Imagenette result we use fully connected graphs with the Sine-Cosine positional embedding. For the VGG-16 architecture we use results reported in [36, 27, 23].
g = fcg
g = knn
g = rag
g = fcg
g = rag
0.4 0.2 0
10
Epoch
20
30
0
10
Epoch
20
30
0
10
Epoch
20
0.6 0.4 0.2
0.8
30
0.6
p xyLinear xySinCos BERT l 1 2 4 6 8 10 12
s = grid
s = grid
0.6
Validation Accuracy
0.2
l 2 4 6 8 10 12 p xyLinear xySinCos BERT
Validation Accuracy
0.4
s = slic
0.6
0.8 Validation Accuracy
g = knn
0.8 s = slic
Validation Accuracy
0.8
0.4 0.2 0
10
Epoch
20
30
0
10
Epoch
20
30
0
10
Epoch
20
30
Figure 5: Plots highlighting the Validation Accuracy throughout the epochs for all the configurations we trained on the FashionMNIST dataset. One can see from graph on the left that the number of layers seemed to have little to no impact for the FashionMNIST dataset, except for the Linear positional embedding based on the xy coordinates. From the graph on the right it’s possible to see that the Linear embedding caused an extremely unstable training and sometimes even failed to reach similar accuracy levels.
11
S
P
G
Valid Acc (%) Best Last
Epochs Best Last
Layers
FashionMNIST Linear
SLIC
SinCos
BERT
Linear
Grid
SinCos
BERT
fcg knn rag fcg knn rag fcg knn rag
80.0 77.2 80.2 86.3 87.7 87.0 87.4 87.5 *87.9
79.2 76.5 79.8 86.3 87.4 87.0 87.3 87.5 87.8
30 28 31 32 31 32 25 32 31
32 32 32 32 32 32 32 32 32
1 12 12 6 4 12 12 12 4
fcg knn rag fcg knn rag fcg knn rag
10.9 80.2 70.5 86.0 87.2 87.0 †86.5 *87.9 87.2
9.5 79.6 69.5 85.9 87.2 86.8 86.5 87.9 87.2
3 31 27 24 32 23 32 32 31
32 32 32 32 32 32 32 32 32
6 6 1 8 4 10 2 8 2
CIFAR10 SinCos SLIC BERT
SinCos Grid BERT
fcg knn rag fcg knn rag
*67.0 67.0 66.4 60.8 61.9 65.2
64.4 65.7 65.0 59.9 59.6 64.2
221 185 279 162 172 504
279 187 308 271 198 506
10 2 4 6 10 4
fcg knn rag fcg knn rag
70.8 72.2 74.3 †70.6 71.7 *75.5
69.4 71.8 73.1 69.5 69.5 72.2
388 450 272 479 253 492
418 475 420 512 260 512
10 12 8 6 6 8
Table 3: Ablation Study for each superpixel generation strategy S, each positional embedding P , and each graph connectivity strategy G for the FashionMNIST and CIFAR10 datasets. We mark the best and second best validation accuracies for each dataset. The best SLIC-based model and non-ViT grid-based is marked with *, and the original ViT model is marked with †. For the CIFAR10 dataset Linear embeddings were failing and thus were cancelled to save compute time.
12
200 Epoch
400
0
200 Epoch
400
0
200 Epoch
0.7 0.6 0.5 0.4 0.3 0.2 0.1
400
g = knn
g = rag
p xyLinear xySinCos BERT l 1 2 4 6 8 10 12
s = grid
0
Validation Accuracy
l 2 4 6 8 10 12 p xyLinear xySinCos BERT
Validation Accuracy
g = fcg 0.7 0.6 0.5 0.4 0.3 0.2 0.1
s = slic
Validation Accuracy
g = rag
s = grid
0.7 0.6 0.5 0.4 0.3 0.2 0.1
g = knn
s = slic
Validation Accuracy
g = fcg 0.7 0.6 0.5 0.4 0.3 0.2 0.1
0
200 Epoch
400
0
200 Epoch
400
0
200 Epoch
400
Figure 6: Plots highlighting the Validation Accuracy throughout the epochs for all the configurations we trained on the CIFAR10 dataset. One can see from graph on the left that the number of layers seemed to be more relevant for this dataset than the FashionMNIST dataset, possibly due to this dataset requiring a higher model capacity. Higher numbers of layers, however, often had a diminishing returns effect and sometime even negatively affected performance. For the slic model, the BERT encoding often fared worse than the SineCosine embedding based on the xy coordinates. This is likely due to the fact that the superpixel embeddings have variable xy coordinates and thus the fixed learned positional encoding cannot work properly. Due to resource-sharing on HPC many models ran for fewer epochs, an analysis of time complexity and time per iteration can be see in Table A1 and Figure A1 where we analyse based on the FashionMNIST dataset, which ran on a more controlled environment. The linear xy positional embedding exhibited inconsistent performance and was dropped from further experiments early on.
7
Conclusion
In this paper we proposed a generalisation of the Vision Transformer model to accept arbitrary superpixel formats and graph connectivities, bridging the gap between using Vision Transformers and the Superpixel-based Image Classification literature. We’ve tested our models with two different Superpixel generation strategies, three graph connectivity strategies, and three positional embedding strategies, showing through this ablation study that our proposed multidimensional SinCos worked better for both, and that graph connectivity strategies produce different results in different datasets. Furthermore, we validated our model against three previous works on Superpixel Image Classification and show better performance than these baselines, showing that even when constrained to working under a superpixel framework (e.g. if one wants to transfer between euclidean and non-euclidean images as was proposed in [5], one could use a similar approach to ours and would only need to adapt the initial embedding head, keeping the transformer core of the model. We test our model on datasets with different image sizes and sample contents, showing that our model can adapt to these different circumstances. Our model, however, does not come without com-
promises. To be able to fully utilise the superpixel information an extra channel was needed during the patch embedding and the lack of search distance limitations on the SLIC implementation used meant that our patches could have sizes above the 2S limit defined in the original SLIC/SLIC0 algorithm [2]. Furthermore, since the number of superpixels is dynamic and might be different than the value specified, it was necessary to provide padding on the input sequences. These issues, however, did not constitute a major resource consumption increase in our model. Our experiments were also heavily limited due to the compute available to us, which we hope to overcome on future work with access to better compute. Future work can address some of the abovementioned weaknesses of our models and can also attempt to use convolutional cores in the patch embedding heads [45], as these would allow the model to better identify the superpixel’s component parts and take full advantage of the superpixel’s shape and colour information. Finally, future work could also focus on pre-training a Superpixel-based model, since pretraining is known to be a much better strategy for training transformer-based image models [34], this would also allow one to attempt transferring models between euclidean and non-euclidean domains as mentioned above, which our model is naturally more
13
suitable for due to its flexible learning pattern, even though our results are only comparable to a standard ViT model.
Acknowledgements This work was partially funded by CAPES Finance code (001) and CNPq. Some of the HPC used in this work was funded by Petrobras call TC 5900.0111175.19.9, 2020/00182-5, and FAPERGS call 16/2551-0000348-8 to Lucas Melo Schnorr. Some experiments in this work used the PCAD infrastructure, http://gppd-hpc.inf.ufrgs.br, at INF/UFRGS. We would like to thank Dylan Alexander Slavin Hillier for his help proofreading this paper.
Authors’ contributions PHdCA did experiment and model design, implementation, and execution, and wrote and reviewed the article. ART and LCL, interacted in discussions, wrote, and reviewed the article.
References [1] R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, and Sabine Süsstrunk. SLIC Superpixels Compared to State-of-the-Art Superpixel Methods. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(11):2274–2282, November 2012. [2] Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine Süsstrunk. SLIC Superpixels: SLICO, June 2010.
Workshop and Special Sessions, volume 11731, pages 701–715. Springer International Publishing, Cham, 2019. Series Title: Lecture Notes in Computer Science. [5] Pedro H. C. Avelar, Anderson R. Tavares, Thiago L. T. da Silveira, Cláudio R. Jung, and Luis C. Lamb. Superpixel Image Classification with Graph Attention Networks. In 2020 33rd SIBGRAPI Conference on Graphics, Patterns and Images (SIBGRAPI), pages 203–209, Recife/Porto de Galinhas, Brazil, November 2020. IEEE. [6] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural Machine Translation by Jointly Learning to Align and Translate. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, Conference Track Proceedings, San Diego, CA, USA,, May 2015. [7] Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song, Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks, October 2018. arXiv:1806.01261 [cs, stat]. [8] Lucas Beyer, Xiaohua Zhai, and Alexander Kolesnikov. Better plain ViT baselines for ImageNet-1k, May 2022. arXiv:2205.01580 [cs]. [9] M. Bianchini, M. Maggini, L. Sarti, and F. Scarselli. Recursive neural networks learn to localize faces. Pattern Recognition Letters, 26(12):1885–1895, September 2005.
[3] Radhakrishna Achanta and Sabine Susstrunk. Superpixels and Polygons Using Simple Noniterative Clustering. In 2017 IEEE Conference on Computer Vision and Pattern Recognition [10] Shaked Brody, Uri Alon, and Eran Yahav. How (CVPR), pages 4895–4904, Honolulu, HI, July Attentive are Graph Attention Networks? In 2017. IEEE. The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, [4] Pedro Avelar, Henrique Lemos, Marcelo Prates, April 2022. OpenReview.net. and Luis Lamb. Multitask Learning on Graph Neural Networks: Learning Multiple Graph Cen- [11] Jiawei Chen, Hao Xu, Wanyu Tao, Zhaoxiong trality Measures with a Unified Network. In Chen, Yuxuan Zhao, and Jing-Dong J. Han. Igor V. Tetko, Věra Kůrková, Pavel Karpov, Transformer for one stop interpretable cell type and Fabian Theis, editors, Artificial Neural Netannotation. Nature Communications, 14(1):223, works and Machine Learning – ICANN 2019: January 2023. 14
[12] Gong Cheng, Junwei Han, and Xiaoqiang Lu. [19] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Remote Sensing Image Scene Classification: Riley, Oriol Vinyals, and George E. Dahl. NeuBenchmark and State of the Art. Proceedings ral Message Passing for Quantum Chemistry. of the IEEE, 105(10):1865–1883, October 2017. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference [13] Haotian Cui, Chloe Wang, Hassaan Maan, Kuan on Machine Learning, ICML 2017, volume 70 Pang, Fengning Luo, and Bo Wang. scGPT: Toof Proceedings of Machine Learning Research, wards Building a Foundation Model for Singlepages 1263–1272, Sydney, NSW, Australia, AuCell Multi-omics Using Generative AI. preprint, gust 2017. PMLR. Bioinformatics, May 2023. [20] Alex Graves, Santiago Fernández, and Jürgen Schmidhuber. Bidirectional LSTM Networks for [14] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Improved Phoneme Classification and RecogniKai Li, and Li Fei-Fei. ImageNet: A large-scale tion. In Wlodzislaw Duch, Janusz Kacprzyk, hierarchical image database. In 2009 IEEE ConErkki Oja, and Slawomir Zadrozny, editors, Arference on Computer Vision and Pattern Recogtificial Neural Networks: Formal Models and nition, pages 248–255, Miami, FL, June 2009. Their Applications - ICANN 2005, 15th InterIEEE. national Conference, Warsaw, Poland, September 11-15, 2005, Proceedings, Part II, volume [15] Jacob Devlin, Ming-Wei Chang, Kenton Lee, 3697 of Lecture Notes in Computer Science, and Kristina Toutanova. BERT: Pre-training pages 799–804, Warsaw, Poland, September of Deep Bidirectional Transformers for Language 2005. Springer. Understanding. In Jill Burstein, Christy Doran, and Thamar Solorio, editors, Proceedings of the 2019 Conference of the North American Chapter [21] Shion Honda, Shoi Shi, and Hiroki R. Ueda. SMILES Transformer: Pre-trained Molecular of the Association for Computational LinguisFingerprint for Low Data Drug Discovery. 2019. tics: Human Language Technologies, NAACLPublisher: arXiv Version Number: 1. HLT 2019, volume 1, pages 4171–4186, Minneapolis, MN, USA, July 2019. Association for [22] Jeremy Howard and Imagenette Contributors. Computational Linguistics. fastai/imagenette, November 2024. originaldate: 2019-03-06T01:58:45Z. [16] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua [23] Kasen. VGG model construction and Imagenette Zhai, Thomas Unterthiner, Mostafa Dehghani, image recognition based on PyTorch, September Matthias Minderer, Georg Heigold, Sylvain 2024. Gelly, Jakob Uszkoreit, and Neil Houlsby. An Image is Worth 16x16 Words: Transformers for [24] Diederik P. Kingma and Jimmy Ba. Adam: A Image Recognition at Scale. In 9th International Method for Stochastic Optimization. In Yoshua Conference on Learning Representations, ICLR Bengio and Yann LeCun, editors, 3rd Interna2021, Virtual Event, Austria, May 2021. Opentional Conference on Learning Representations, Review.net. ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. [17] Vijay Prakash Dwivedi and Xavier Bresson. A Generalization of Transformer Networks to [25] Thomas N. Kipf and Max Welling. SemiGraphs, January 2021. arXiv:2012.09699 [cs]. Supervised Classification with Graph Convolutional Networks. In 5th International Conference [18] Matthias Fey, Jan Eric Lenssen, Frank Weon Learning Representations, ICLR 2017, Conichert, and Heinrich Muller. SplineCNN: Fast ference Track Proceedings, Toulon, France, April Geometric Deep Learning with Continuous B2017. OpenReview.net. Spline Kernels. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, [26] Alex Krizhevsky. Learning multiple layers of feapages 869–877, Salt Lake City, UT, June 2018. tures from tiny images. Master’s thesis, UniverIEEE. sity of Toronto, Toronto, Canada, April 2009. 15
[27] Shreyasi Mandal. VGG16 on MNIST and Fashion mnist, November 2023. [28] Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M. Bronstein. Geometric Deep Learning on Graphs and Manifolds Using Mixture Model CNNs. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5425–5434, Honolulu, HI, July 2017. IEEE. [29] OpenAI, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, Red Avila, Igor Babuschkin, Suchir Balaji, Valerie Balcom, Paul Baltescu, Haiming Bao, Mo Bavarian, Jeff Belgum, Irwan Bello, Jake Berdine, Gabriel Bernadett-Shapiro, Christopher Berner, Lenny Bogdonoff, Oleg Boiko, Madelaine Boyd, Anna-Luisa Brakman, Greg Brockman, Tim Brooks, Miles Brundage, Kevin Button, Trevor Cai, Rosie Campbell, Andrew Cann, Brittany Carey, Chelsea Carlson, Rory Carmichael, Brooke Chan, Che Chang, Fotis Chantzis, Derek Chen, Sully Chen, Ruby Chen, Jason Chen, Mark Chen, Ben Chess, Chester Cho, Casey Chu, Hyung Won Chung, Dave Cummings, Jeremiah Currier, Yunxing Dai, Cory Decareaux, Thomas Degry, Noah Deutsch, Damien Deville, Arka Dhar, David Dohan, Steve Dowling, Sheila Dunning, Adrien Ecoffet, Atty Eleti, Tyna Eloundou, David Farhi, Liam Fedus, Niko Felix, Simón Posada Fishman, Juston Forte, Isabella Fulford, Leo Gao, Elie Georges, Christian Gibson, Vik Goel, Tarun Gogineni, Gabriel Goh, Rapha Gontijo-Lopes, Jonathan Gordon, Morgan Grafstein, Scott Gray, Ryan Greene, Joshua Gross, Shixiang Shane Gu, Yufei Guo, Chris Hallacy, Jesse Han, Jeff Harris, Yuchen He, Mike Heaton, Johannes Heidecke, Chris Hesse, Alan Hickey, Wade Hickey, Peter Hoeschele, Brandon Houghton, Kenny Hsu, Shengli Hu, Xin Hu, Joost Huizinga, Shantanu Jain, Shawn Jain, Joanne Jang, Angela Jiang, Roger Jiang, Haozhun Jin, Denny Jin, Shino Jomoto, Billie Jonn, Heewoo Jun, Tomer Kaftan, Lukasz Kaiser, Ali Kamali, Ingmar Kanitscheider, Nitish Shirish Keskar, Tabarak Khan, Logan Kilpatrick, Jong Wook Kim, Christina Kim, Yongjik Kim, Hendrik Kirchner, Jamie Kiros, Matt Knight, Daniel Kokotajlo, Lukasz 16
Kondraciuk, Andrew Kondrich, Aris Konstantinidis, Kyle Kosic, Gretchen Krueger, Vishal Kuo, Michael Lampe, Ikai Lan, Teddy Lee, Jan Leike, Jade Leung, Daniel Levy, Chak Ming Li, Rachel Lim, Molly Lin, Stephanie Lin, Mateusz Litwin, Theresa Lopez, Ryan Lowe, Patricia Lue, Anna Makanju, Kim Malfacini, Sam Manning, Todor Markov, Yaniv Markovski, Bianca Martin, Katie Mayer, Andrew Mayne, Bob McGrew, Scott Mayer McKinney, Christine McLeavey, Paul McMillan, Jake McNeil, David Medina, Aalok Mehta, Jacob Menick, Luke Metz, Andrey Mishchenko, Pamela Mishkin, Vinnie Monaco, Evan Morikawa, Daniel Mossing, Tong Mu, Mira Murati, Oleg Murk, David Mély, Ashvin Nair, Reiichiro Nakano, Rajeev Nayak, Arvind Neelakantan, Richard Ngo, Hyeonwoo Noh, Long Ouyang, Cullen O’Keefe, Jakub Pachocki, Alex Paino, Joe Palermo, Ashley Pantuliano, Giambattista Parascandolo, Joel Parish, Emy Parparita, Alex Passos, Mikhail Pavlov, Andrew Peng, Adam Perelman, Filipe de Avila Belbute Peres, Michael Petrov, Henrique Ponde de Oliveira Pinto, Michael, Pokorny, Michelle Pokrass, Vitchyr Pong, Tolly Powell, Alethea Power, Boris Power, Elizabeth Proehl, Raul Puri, Alec Radford, Jack Rae, Aditya Ramesh, Cameron Raymond, Francis Real, Kendra Rimbach, Carl Ross, Bob Rotsted, Henri Roussez, Nick Ryder, Mario Saltarelli, Ted Sanders, Shibani Santurkar, Girish Sastry, Heather Schmidt, David Schnurr, John Schulman, Daniel Selsam, Kyla Sheppard, Toki Sherbakov, Jessica Shieh, Sarah Shoker, Pranav Shyam, Szymon Sidor, Eric Sigler, Maddie Simens, Jordan Sitkin, Katarina Slama, Ian Sohl, Benjamin Sokolowsky, Yang Song, Natalie Staudacher, Felipe Petroski Such, Natalie Summers, Ilya Sutskever, Jie Tang, Nikolas Tezak, Madeleine Thompson, Phil Tillet, Amin Tootoonchian, Elizabeth Tseng, Preston Tuggle, Nick Turley, Jerry Tworek, Juan Felipe Cerón Uribe, Andrea Vallone, Arun Vijayvergiya, Chelsea Voss, Carroll Wainwright, Justin Jay Wang, Alvin Wang, Ben Wang, Jonathan Ward, Jason Wei, C. J. Weinmann, Akila Welihinda, Peter Welinder, Jiayi Weng, Lilian Weng, Matt Wiethoff, Dave Willner, Clemens Winter, Samuel Wolrich, Hannah Wong, Lauren Workman, Sherwin Wu, Jeff Wu, Michael Wu, Kai Xiao, Tao Xu, Sarah Yoo, Kevin Yu, Qiming
Yuan, Wojciech Zaremba, Rowan Zellers, Chong Zhang, Marvin Zhang, Shengjia Zhao, Tianhao Zheng, Juntang Zhuang, William Zhuk, and Barret Zoph. GPT-4 Technical Report, December 2023. arXiv:2303.08774 [cs]. [30] Júlia Rodrigues and Joel Carbonera. Graph Convolutional Networks for Image Classification: Comparing Approaches for Building Graphs from Images. In Proceedings of the 26th International Conference on Enterprise Information Systems, volume 1, pages 437–446, Angers, France, 2024. SCITEPRESS - Science and Technology Publications.
SEEDS: Superpixels Extracted via EnergyDriven Sampling. In David Hutchison, Takeo Kanade, Josef Kittler, Jon M. Kleinberg, Friedemann Mattern, John C. Mitchell, Moni Naor, Oscar Nierstrasz, C. Pandu Rangan, Bernhard Steffen, Madhu Sudan, Demetri Terzopoulos, Doug Tygar, Moshe Y. Vardi, Gerhard Weikum, Andrew Fitzgibbon, Svetlana Lazebnik, Pietro Perona, Yoichi Sato, and Cordelia Schmid, editors, Computer Vision – ECCV 2012, volume 7578, pages 13–26. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. Series Title: Lecture Notes in Computer Science.
[38] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is All you Need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and [32] M. Schuster and K.K. Paliwal. Bidirectional reRoman Garnett, editors, Advances in Neural Incurrent neural networks. IEEE Transactions on formation Processing Systems 30: Annual ConSignal Processing, 45(11):2673–2681, November ference on Neural Information Processing Sys1997. tems 2017, December 4-9, 2017, Long Beach, [33] Daniel Selsam, Matthew Lamm, Benedikt Bünz, CA, USA, pages 5998–6008, 2017. Percy Liang, Leonardo de Moura, and David L. Dill. Learning a SAT Solver from Single-Bit Su- [39] Petar Velickovic, Guillem Cucurull, Arantxa pervision. In 7th International Conference on Casanova, Adriana Romero, Pietro Liò, and Learning Representations, ICLR 2019, New OrYoshua Bengio. Graph Attention Networks. leans, LA, USA, May 6-9, 2019, New Orleans, In 6th International Conference on Learning LA, USA, May 2019. OpenReview.net. Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference [34] Andreas Peter Steiner, Alexander Kolesnikov, Track Proceedings, Vancouver, BC, Canada, Xiaohua Zhai, Ross Wightman, Jakob UszkorMay 2018. OpenReview.net. eit, and Lucas Beyer. How to train your ViT? Data, Augmentation, and Regularization in Vi- [40] Oriol Vinyals, Meire Fortunato, and Navdeep sion Transformers. Transactions on Machine Jaitly. Pointer Networks. In Corinna Cortes, Learning Research, 2022. Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Ad[35] David Stutz, Alexander Hermans, and Bastian vances in Neural Information Processing SysLeibe. Superpixels: An evaluation of the statetems 28: Annual Conference on Neural Informaof-the-art. Computer Vision and Image Undertion Processing Systems 2015, December 7-12, standing, 166:1–27, January 2018. 2015, Montreal, Quebec, Canada, pages 2692– 2700, 2015. [36] Tinglong Tang, Xiaowang Chen, Yirong Wu, Shuifa Sun, and Mei Yu. Image Classification Based on Deep Graph Convolutional Net- [41] Sheng Wang, Yuzhi Guo, Yuhong Wang, Hongmao Sun, and Junzhou Huang. SMILESworks. In 2022 IEEE 9th International ConferBERT: Large Scale Unsupervised Pre-Training ence on Data Science and Advanced Analytics for Molecular Property Prediction. In Proceed(DSAA), pages 1–6, Shenzhen, China, October ings of the 10th ACM International Conference 2022. IEEE. on Bioinformatics, Computational Biology and [37] Michael Van Den Bergh, Xavier Boix, Gemma Health Informatics, pages 429–436, Niagara Falls Roig, Benjamin De Capitani, and Luc Van Gool. NY USA, September 2019. ACM. [31] F. Scarselli, M. Gori, Ah Chung Tsoi, M. Hagenbuchner, and G. Monfardini. The Graph Neural Network Model. IEEE Transactions on Neural Networks, 20(1):61–80, January 2009.
17
[42] Xing Wei, Qingxiong Yang, Yihong Gong, Narendra Ahuja, and Ming-Hsuan Yang. Superpixel Hierarchy. IEEE Transactions on Image Processing, 27(10):4838–4849, October 2018. [43] Fang Wu, Dragomir Radev, and Stan Z. Li. Molformer: Motif-Based Transformer on 3D Heterogeneous Molecular Graphs. Proceedings of the AAAI Conference on Artificial Intelligence, 37(4):5312–5320, June 2023. [44] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms, September 2017. arXiv:1708.07747 [cs, stat]. [45] Tete Xiao, Mannat Singh, Eric Mintun, Trevor Darrell, Piotr Dollár, and Ross B. Girshick. Early Convolutions Help Transformers See Better. In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 614, 2021, virtual, pages 30392–30400, December 2021. [46] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, New Orleans, LA, USA, May 2019. OpenReview.net. [47] Jian Yao, Marko Boben, Sanja Fidler, and Raquel Urtasun. Real-time coarse-to-fine topologically preserving segmentation. In 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2947–2955, Boston, MA, USA, June 2015. IEEE.
18
Appendix A Algorithm A1 Square Grid Superpixel Require: image ∈ RC×h×w , patch size ∈ Z Ensure: segments ∈ Zh×w √ Ensure: n segments ∈ Z Ensure: H mod patch size = 0 Ensure: H = W √ 1: num patches per line ← n segments 2: Initialize segments ← zeros(H, W ) 3: for i ← 0 to n segments − 1 do 4: iy ← ⌊i/num patches per line⌋ 5: ix ← i mod num patches per line 6: Assign segment index i to region in segments 7: segments[iy × patch size . . . (iy + 1) × patch size, ix × patch size . . . (ix + 1) × patch size] ← i 8: end for 9: return segments
Algorithm A2 Sine-Cosine Coordinate Encoding Require: hidden dim ∈ Z, n axes ∈ Z Ensure: pos emb ∈ Rb×s×h , where b is batch size, s is sequence length, h is hidden dimension 1: Initialize div term = exp([0 . . . h] · (− log(10000)/h)) 2: Initialize mixer = W ∈ Rh×h 3: procedure Encode(pos, x) ▷ pos is Rb×s×d , x is Rb×s×h 4: d ← min(n axes, pos.shape[2]) 5: Initialize pos emb ← zeros like(x) 6: for i ← 0 to d − 1 do ▷ Build sin-cos for each dimension 7: Select all indices for cosine as jcos = {i, i + 2d, i + 4d, . . .} up to h 8: Select all indices for sine as jsin = {i + 1, i + 1 + 2d, i + 1 + 4d, . . .} up to h 9: pos emb[:, :, jcos ] ← cos(pos[:, :, i] · div term[jcos ]) 10: pos emb[:, :, jsin ] ← sin(pos[:, :, i] · div term[jsin ]) 11: end for 12: return mixer(pos emb) 13: end procedure
19
S
P
G
slic
slic
xyLinear xySinCos BERT xyLinear xySinCos BERT xyLinear xySinCos BERT xyLinear xySinCos BERT xyLinear xySinCos BERT xyLinear xySinCos BERT xyLinear xySinCos BERT xyLinear xySinCos BERT *
grid
*
*
fcg
fcg fcg fcg rag rag rag knn knn knn fcg fcg fcg rag rag rag knn knn knn * * * * * * fcg rag knn fcg rag knn xyLinear xySinCos BERT xyLinear xySinCos BERT xyLinear xySinCos BERT * * * * * fcg rag knn
grid
slic
grid
rag
knn
slic grid *
* * xyLinear xySinCos BERT *
µ(b)
σ(b)
2191.445 2163.883 2163.673 3018.270 2890.867 2945.360 3665.725 3784.874 3622.777 2308.859 2198.941 2127.548 2927.251 2820.486 2860.717 3547.717 3590.628 3636.872 2958.480 2946.541 2910.603 2927.942 2870.018 2875.046 2173.000 2951.499 3691.125 2211.783 2869.485 3591.739 2250.152 2181.412 2145.611 2972.761 2855.677 2903.039 3606.721 3687.751 3629.824 2938.542 2891.002 2943.211 2908.280 2892.825 2192.391 2910.492 3641.432
79.985 56.462 91.721 67.750 59.136 97.905 59.916 75.899 38.381 53.799 40.184 68.252 51.175 32.625 70.748 97.029 77.070 133.942 252.643 274.293 244.672 251.979 252.923 261.837 40.673 42.239 43.873 35.102 30.399 56.513 52.541 40.801 54.348 45.539 40.709 66.223 55.538 71.164 65.661 144.431 143.395 174.740 183.329 175.366 28.569 29.785 36.430
Table A1: Table showing the average and standard deviation of the intercepts for linear regression models build on a certain combination of Superpixel, Positional Embedding and Graph Adjacency method. We can see that the Graph Adjacency method has the biggest impact on performance. Values for slopes are not included since most slopes had a non-significant p-value, and the comparison between intercepts yielded more significant p-values.
20
4000
S = slic | P = xyLinear
S = slic | P = xySinCos
S = slic | P = BERT
r=0.17, p=0.69
r=0.19, p=0.66
r=0.25, p=0.55
r=-0.25, p=0.54
r=0.31, p=0.46
r=0.18, p=0.68
r=0.23, p=0.58
r=0.50, p=0.2
r=0.37, p=0.37
3750 3500
Time (s)
3250 3000 2750 2500 2250 2000 4000
S = grid | P = xyLinear
S = grid | P = xySinCos
G
S = grid | P = BERT
r=0.39, p=0.34
r=0.20, p=0.64
r=0.17, p=0.68
r=-0.30, p=0.47
r=0.19, p=0.65
r=-0.07, p=0.87
r=-0.73, p=0.039
r=-0.41, p=0.32
r=0.42, p=0.3
fcg rag knn
3750 3500
Time (s)
3250 3000 2750 2500 2250 2000
2
4
6
8
l
10
12
2
4
6
8
l
10
12
2
4
6
l
8
10
4000
4000 4000
3750
2750
slic grid
3250
r=0.02, p=0.88 r=-0.01, p=0.96 r=0.04, p=0.79
P xyLinear xySinCos BERT
3000 2750
Time (s)
3250
S
3000
Time (s)
Time (s)
3500
3500
r=0.03, p=0.79 r=0.00, p=0.97
2500
2500
2250
2250
4
6
l
8
10
12
2000
2000 2
4
6
l
8
10
12
G
2750
2250 2
r=0.01, p=0.95
3000
2500
2000
r=0.19, p=0.21
3750
3750
3500 3250
12
fcg rag knn
r=0.09, p=0.53
2
4
6
l
8
10
12
Figure A1: Figures showing regression plots (with person r and p values) between the number of layers and the time taken for the process to finish training and testing. The top figure shows results separated by each of the variables, and most results show a positive r but a not-significant p, with the only significant p having a negative r, which we believe to be spurious. Only when we look at each variable individually on the bottom figures that we are able to find significant differences between variables, and the graph building algorithm is has the biggest difference.
21