Beyond Augmentation: Leveraging Inter-Instance Relation in Self-Supervised Representation Learning

AI summary

Overview

• Research area: Self-supervised visual representation learning, combining contrastive/self-distillation pretraining with graph theory and Graph Neural Networks (GNNs).
• Technical level: Advanced — the paper assumes familiarity with teacher-student self-distillation, k-nearest neighbor (KNN) retrieval in latent space, and GNN message passing.
• Scope: The paper proposes a framework that retains augmentation-based intra-instance supervision while adding inter-instance relationships through KNN graphs built for both teacher and student streams, followed by a GNN-based representation refinement phase.

Authors: Ali Javidani and Babak Nadjar Araabi (University of Tehran), Mohammad Amin Sadeghi (Qatar Computing Research Institute, Hamad bin Khalifa University). arXiv:2510.22322v1 [cs.CV], 25 Oct 2025. Code is available at https://github.com/alijavidani/SSL-GraphNNCLR.

What This Paper Is About

Most self-supervised methods create positive pairs by applying artificial augmentations (color jitter, cropping, Gaussian blur) to a single image, which captures intra-sample variation but ignores relationships between different images. The paper's goal is to capture inter-instance relationships by building k-nearest neighbor (KNN) graphs over samples in both the teacher and student streams, then refining the learned embeddings with Graph Neural Networks so that information propagates across multiple hops of neighbors.

Key Contributions

1. Dual KNN graph construction during pretraining. The method builds a separate directed KNN graph for the teacher stream and the student stream, where nodes are dataset samples (training and validation, so |V| = N) and edges encode inter-sample similarity. Edges are stored and refreshed over the most recent w epochs using a circular queue implemented as a 2 × (N × k × w) array, so each node accumulates k × w directed edges.
2. A representation refinement phase driven by GNNs. After pretraining, GNN layers perform message passing so each node aggregates information from immediate, second-, and third-hop neighbors across three GNN layers, producing broader contextual integration.
3. Graph-based self-supervision without artificial graph augmentation. Instead of augmenting a graph (e.g., edge dropping or feature perturbation) as in SelfGNN and BGRL, the framework uses the naturally arising teacher and student KNN graphs as two complementary views, aligned by minimizing cosine distance, with the teacher updated by an exponential moving average of the student.
4. Empirical validation across three benchmarks. Linear evaluation on CIFAR-10, ImageNet-100, and ImageNet-1K reports 89.7%, 83.8%, and 72.8% accuracy, which the abstract describes as improvements of 7.3%, 3.2%, and 1.0% respectively over state-of-the-art methods.

Main Findings

• Linear evaluation accuracy (Table II): Using a logistic regression classifier on refined backbone features (with the MLP projector omitted), the method reaches 89.7% on CIFAR-10, 83.8% on ImageNet-100, and 72.8% on ImageNet-1K. Listed comparators are SimCLR (76.1 / 75.4 / 68.9), NNCLR (78.5 / 77.3 / 70.9), DINO (78.6 / 77.2 / 71.3), AdaSim (81.1 / 78.4 / 71.8), EsViT (81.2 / 78.7 / 72.5), and MSBReg (82.4 / 80.6 / 70.5).
• Abstract-reported gains: 7.3% on CIFAR-10, 3.2% on ImageNet-100, and 1.0% on ImageNet-1K over state-of-the-art methods.
• Sparse graphs with fewer neighbors generalize better (Table III): The best results occur with low k and high w. With k = 1 and w = 15 (15 edges per node), accuracy is 89.7% on CIFAR-10 and 83.8% on ImageNet-100. Increasing k at a fixed w degrades accuracy: k = 2 with w = 8 (16 edges) gives 89.2% / 82.9%; k = 3 with w = 5 (15 edges) gives 88.4% / 80.3%; k = 4 with w = 5 (20 edges) gives 87.5% / 78.4%.
• GCN outperforms other GNN architectures (Table IV, k = 1, w = 15): On CIFAR-10, GCN reaches 89.7%, GAT 86.5%, GraphSAGE 71.6%, and GIN 62.4%. On ImageNet-100, GCN reaches 83.8%, GAT 83.1%, GraphSAGE 81.1%, and GIN 68.9%. The authors attribute this to GCN's mean aggregation and GAT's attention-weighted mean being more stable under noisy, self-supervised graph construction, whereas GraphSAGE's complex aggregation and GIN's sum aggregation tend to amplify noise.
• Jumping Knowledge helps (Table V): With k = 1 and w = 15, disabling JK yields 85.9% on CIFAR-10 and 82.6% on ImageNet-100, while JK with concatenation yields 89.7% and 83.8%. The table also reports JK(Sum) at 85.0% / 83.2% and JK(Max) at 84.5% / 83.1%. The text states that concatenation outperformed the other aggregation strategies.
• Design rationale for graph density: Sparse graphs may fail to capture sufficient inter-sample information, while overly dense graphs risk connecting dissimilar samples; a smaller k with a larger w is therefore reported as the more effective strategy.

Methodology in Plain English

1. Two augmented views, two networks. An image is augmented twice. One view goes to a student encoder and the other to a teacher encoder, following the DINO self-distillation setup. As in AdaSim, an adaptive mechanism decides whether the teacher receives a second augmented view (when the network is not yet mature) or a sample drawn from the nearest-neighbor distribution (when it is mature). Maturity is assessed by checking whether the nearest neighbor of a sample is the sample itself.
2. Neighbor similarity over recent epochs. For each sample, the method collects the top e nearest neighbors per epoch by cosine similarity, aggregates similarity scores over the w most recent epochs using an indicator function, and normalizes them with a softmax to form a probability distribution over candidate neighbors.
3. Graph construction. Before projection, a directed KNN graph G = (V, E) is built per stream: an edge (v_i, v_j) exists if v_j is among the top k nearest neighbors of v_i (assuming k < e). Self-loops are avoided by selecting the next closest node if a sample appears among its own top-k neighbors.
4. Projection and alignment loss. Features from both networks pass through a 3-layer MLP projector into a higher-dimensional space. The teacher output is centered and sharpened; the student output is only sharpened. A cross-entropy loss aligns the two distributions.
5. Refinement with GNNs. In the refinement phase, separate GNNs process the teacher and student graphs. Each layer aggregates neighbor embeddings (sum, mean, or max) into a message and updates the node embedding with a linear or MLP transformation plus a non-linear activation. Jumping Knowledge aggregates outputs from multiple layers via concatenation, summation, or maximization. Alignment is enforced by minimizing cosine distance between student and teacher node embeddings, and the teacher is updated by an exponential moving average of the student parameters.
6. Training setup. The backbone is ViT-Base producing 768-dimensional embeddings, with other hyperparameters following the DINO and AdaSim implementations. Refinement uses a learning rate of 0.0001 and momentum of 0.99, with GNN layers configured at 768 units trained for 1000 epochs.

Why This Matters

Impact on research. The work reframes self-supervision as a graph problem: instead of relying only on hand-designed augmentations, it treats each sample's relationship to many other samples as a supervision signal. It also shows that the teacher and student graphs can replace the artificial graph augmentation used in label-free graph learning methods such as SelfGNN and BGRL, connecting the self-supervised vision literature with self-supervised graph node representation learning. The reported gains are largest on the smaller benchmark (7.3% on CIFAR-10) and smallest on the largest (1.0% on ImageNet-1K per the abstract), suggesting a scaling question that future work would need to address.

Real-world applications (the paper does not evaluate downstream applications directly; these follow from the general transferability claims made in the introduction):

• Pretraining vision backbones for domains where labels are scarce or expensive.
• Image retrieval and similarity search, since the method explicitly models nearest-neighbor structure in embedding space.
• Remote sensing object detection, which the introduction cites as an area where structured and adversarial self-supervised formulations have been explored for robustness.
• General feature extraction pipelines that need transferable representations across tasks.

Industry relevance. Many production vision systems depend on a pretrained backbone whose quality determines downstream performance. A method that improves linear-probe accuracy without labels addresses the labeling bottleneck directly, and the refinement phase is a post-pretraining step that operates on already-computed embeddings.

Future Directions

The paper does not present an explicit future work section; the following are open questions the work raises:

1. Scaling to larger datasets and backbones. The abstract-reported improvement shrinks from 7.3% on CIFAR-10 to 1.0% on ImageNet-1K, so it is unclear how the approach behaves at larger data scales or with architectures beyond ViT-Base.
2. Cost of graph construction and maintenance. Building graphs over datasets with N samples and maintaining k × w edges per node with a circular queue implies memory and compute costs that the paper does not analyze or report.
3. Sensitivity to GNN design choices. The large spread across architectures (GCN 89.7% versus GIN 62.4% on CIFAR-10) and the variation across Jumping Knowledge strategies raise questions about how robust the gains are to architectural choices not tested here.
4. Interaction between the refinement phase and downstream tasks. Evaluation is limited to linear classification; the paper does not report transfer to detection, segmentation, or other downstream tasks, nor does it report results for other evaluation protocols.

Target Audience

Researchers and graduate students working on self-supervised learning, contrastive and self-distillation methods, and graph representation learning. It is also relevant to practitioners who pretrain vision backbones on unlabeled image collections, and to readers interested in how GNN message passing can be integrated into non-graph pretraining pipelines. Readers should be comfortable with KNN retrieval in embedding space, DINO-style teacher-student training, and GNN aggregation/update mechanics.

Authors’ abstract

This paper introduces a novel approach that integrates graph theory into self-supervised representation learning. Traditional methods focus on intra-instance variations generated by applying augmentations. However, they often overlook important inter-instance relationships. While our method retains the intra-instance property, it further captures inter-instance relationships by constructing k-nearest neighbor (KNN) graphs for both teacher and student streams during pretraining. In these graphs, nodes represent samples along with their latent representations. Edges encode the similarity between instances. Following pretraining, a representation refinement phase is performed. In this phase, Graph Neural Networks (GNNs) propagate messages not only among immediate neighbors but also across multiple hops, thereby enabling broader contextual integration. Experimental results on CIFAR-10, ImageNet-100, and ImageNet-1K demonstrate accuracy improvements of 7.3%, 3.2%, and 1.0%, respectively, over state-of-the-art methods. These results highlight the effectiveness of the proposed graph based mechanism. The code is publicly available at https://github.com/alijavidani/SSL-GraphNNCLR.