CNN2Graph: Building Graphs for Image Classification

Vivek Trivedy, Longin Jan LateckiWACV 2023

TL;DR

This paper introduces CNN2GNN and CNN2Transformer, novel methods that build explicit graph structures between image data points to improve classification. By leveraging Graph Neural Networks (GNNs) and Transformer attention mechanisms, these models capture inter-example relationships, overcoming the limitations of traditional i.i.d. assumptions in deep learning.

What Problem Does This Paper Address?

Traditional image classification models, including Convolutional Neural Networks (CNNs) and Vision Transformers, typically treat each image independently during training and inference. This "i.i.d. assumption" means they learn representations within each image but fail to explicitly model relationships between different images in the dataset. This can be a significant limitation, especially in scenarios where understanding these inter-image connections is crucial for accurate classification. Existing methods for building graphs from image data often rely on non-differentiable steps (like k-nearest neighbors) or struggle with inductive inference (applying a trained model to new, unseen data). The authors aim to bridge this gap by proposing a differentiable, end-to-end framework that constructs a graph representation of image relationships, enabling better classification and inductive inference.

Methods

The core of the proposed methods, CNN2GNN and CNN2Transformer, involves constructing a complete bipartite graph between training examples and a fixed set of "proxy" and "anchor" examples.

  • Proxy and Anchor Sets:
    • Proxies: These are learnable parameters, initialized with the same dimension as the image embeddings. They are intended to act as global class representatives, partitioning the latent space.
  • Anchors: These are fixed images sampled uniformly from each class in the training dataset. They serve as stable, class-specific reference points.
  • Graph Construction: A complete bipartite graph is formed between each mini-batch of training images and the proxy set. This means every training image is connected to every proxy.
  • Cross-Attention: The key mechanism for learning inter-example relationships is cross-attention.
  • CNN2GNN: Uses Graph Attention Networks (GATs) to compute attention scores between input image embeddings and the proxy set. This allows the model to selectively attend to relevant class representatives.
  • CNN2Transformer: Leverages Transformer-style cross-attention. Input images act as queries, while anchors and proxies act as keys and values. This results in weighted representations of anchors and proxies that are then aggregated with the original image embeddings.
  • Loss Function: To prevent "proxy collapse" (where learnable proxies are ignored or become degenerate), the authors combine:
  • Cross-Entropy Loss: Applied to both input images, anchors, and proxies for direct classification.
  • Contrastive Losses: Including triplet and contrastive losses applied to combinations of images, anchors, and proxies. These losses encourage similar examples to cluster together and push proxies towards their respective classes.
  • End-to-End Differentiability & Inductive Inference: The graph construction and attention mechanisms are designed to be fully differentiable, allowing for end-to-end training. For inference, new images are simply connected to the fixed proxy set, enabling efficient O(1) inductive inference.

Datasets

The models were trained and evaluated on the following datasets:

  • CIFAR-10
  • CIFAR-100
  • STL-10
  • SVHN
  • ImageNet-1k

Key Insights and Ideas

  • Inter-example relationships are crucial: Explicitly modeling connections between images, rather than just within them, can significantly boost classification performance.
  • Differentiable graph construction is key: Moving away from non-differentiable methods like KNN for graph building allows for true end-to-end learning.
  • Proxies and anchors provide a stable framework: Learnable proxies and fixed anchors offer a structured way to represent class information and guide the learning process.
  • Combined loss prevents proxy collapse: A simple combination of cross-entropy and contrastive losses effectively grounds proxies and prevents them from becoming degenerate.
  • Transformer attention scales better: For larger datasets and more classes, Transformer-style attention demonstrates superior scalability compared to GAT attention.

Key Results

  • Improved Accuracy: Both CNN2GNN and CNN2Transformer consistently outperform baseline models across various datasets. CNN2Transformer, in particular, shows strong performance on ImageNet-1k.
  • Efficiency: The proposed methods enable efficient inductive inference with an O(1) complexity for new data points.
  • Attention Analysis: The paper provides visualizations of attention matrices, showing how CNN2Transformer examples attend to proxies corresponding to their labels, while CNN2GNN shows more varied attention patterns.
  • Scalability: Empirical investigations suggest that Transformer attention scales better than GAT attention with increasing dataset size and number of classes.

Limitations and Future Work

  • Computational Cost of Proxies: The number of proxies scales linearly with the number of classes, which can lead to significant computational resource requirements for datasets with many classes.
  • Future Directions: The authors suggest exploring novel graph structures, aggregation schemes, and proxy learning strategies. They also propose relaxing the class constraint on proxies and investigating the use of their cross-attention framework for multimodal data.

Summary updated

BibTeX
@inproceedings{trivedy2023cnn,
  author = {Vivek Trivedy and Longin Jan Latecki},
  title = {{CNN2Graph: Building Graphs for Image Classification}},
  booktitle = {IEEE/CVF Winter Conference on Applications of Computer Vision},
  year = {2023},
}
Figure