Multigraph Transformer for Free-Hand Sketch Recognition

Peng Xu, Chaitanya K. Joshi, Xavier BressonIEEE TNNLS 2022 · OpenReview

TL;DR

This paper introduces the Multi-Graph Transformer (MGT), a novel neural network architecture that represents free-hand sketches as multiple, sparsely connected graphs. By capturing both local and global geometric stroke structures, MGT significantly outperforms existing RNN-based models for sketch recognition and offers a faster inference time than CNNs, paving the way for real-time sketch applications.

What Problem Does This Paper Address?

Free-hand sketches are notoriously difficult to interpret by machines. Unlike regular images, sketches are sparse, abstract, and inherently sequential, formed by a series of strokes over time. Traditional approaches have tried to tackle this by treating sketches as static images (using Convolutional Neural Networks - CNNs) or as temporal sequences (using Recurrent Neural Networks - RNNs). However, these methods have limitations: CNNs struggle with the sparsity and temporal nature, while RNNs can be challenging to train at scale and may not fully capture the rich geometric relationships within strokes. The authors aim to bridge this gap by proposing a new representation that leverages the inherent graph-like structure of sketches.

Methods

The core innovation is the Multi-Graph Transformer (MGT). Instead of a single, fully connected graph representation (which Transformers typically use for sequential data like text), MGT models sketches using multiple, sparsely connected graphs. These graphs are designed to capture different aspects of the sketch:

  • Intra-stroke graphs: These focus on the local geometry within individual strokes, using K-hop connections (e.g., 1-hop, 2-hop) to represent how points in a stroke are related to their immediate neighbors.
  • Extra-stroke graphs: These capture global and temporal relationships between strokes, specifically looking at connections between consecutive strokes.

The MGT architecture itself is a Transformer variant adapted to handle these multiple graph inputs. It uses a Multi-Graph Multi-Head Attention (MGMHA) mechanism that allows the model to attend to information from different graph structures simultaneously. This is combined with standard Transformer components like feed-forward layers and residual connections. The input to the model is a multi-modal representation of each stroke point, including its spatial coordinates, pen state (start, end, or continuation of a stroke), and temporal position.

Datasets

The primary dataset used is Google QuickDraw [1]. The authors created a subset of 414,000 sketches, split into training, validation, and test sets. For efficient training of sequential models like RNNs and MGT, sketches were truncated or padded to a uniform length of 100 key points.

The paper also mentions using the SemEval-2010 task 8 dataset for relation extraction to demonstrate the generalizability of their multi-graph approach to other domains like Natural Language Processing (NLP).

Key Insights and Ideas

  • Sketches as Graphs: The fundamental idea that sketches can be effectively represented as multiple, sparsely connected graphs is a novel contribution. This moves beyond treating sketches as just images or simple sequences.
  • Domain-Specific Graphs for Transformers: Standard Transformers excel with fully connected graphs (like word graphs in NLP). However, for sketches, injecting domain-specific graph structures (like K-hop or stroke-connectivity graphs) provides crucial inductive bias, leading to better performance.
  • Multi-Graph Attention is Key: The ability of MGT to simultaneously process information from different graph structures (intra-stroke, extra-stroke) is crucial for capturing both fine-grained local details and broader global context.
  • Sparsity is Beneficial: Unlike dense, fully-connected graphs, sparse graphs derived from sketch geometry are more robust and lead to better performance, especially for Transformer architectures.
  • Real-time Sketch Applications: The MGT's efficiency and effectiveness make it a strong candidate for real-time sketch-based human-computer interaction (HCI) systems.

Key Results

  • Superior RNN Performance: MGT significantly outperforms state-of-the-art RNN baselines (LSTM and GRU) by 3-5% in accuracy, highlighting the importance of both geometric and temporal stroke information.
  • Competitive CNN Performance: MGT achieves a small recognition gap (72.80% vs. 74.22% accuracy) compared to the best CNN models, which are considered an upper bound for coordinate-based methods.
  • Faster Inference: MGT infers significantly faster than CNN baselines like Inception V3 and MobileNet V2, making it suitable for real-time applications.
  • Ablation Studies:
    • Using multiple graphs (specifically 3 graphs: A¹-hop, A²-hop, and A<0xE2><0x82><0x91>lobal) yields better performance than single-graph models.
  • Domain-specific graphs (like A¹-hop) perform much better than generic fully-connected or random graphs for Transformers.
  • Concatenating multi-modal inputs (coordinates, flag bits, position encoding) is more effective than simple summation or using only coordinates.
  • Cross-Domain Transfer: The multi-graph Transformer concept shows promise in NLP tasks like relation extraction, outperforming CNNs.

Limitations and Future Work

  • Dataset Size: While Google QuickDraw is large, the authors created a subset. Future work could explore the full dataset or other large sketch datasets.
  • GNN Library Support: The authors note that GNNs and GTs for sparse graph formats are not natively supported by PyTorch, which can impact efficiency. They suggest that using specialized GNN libraries could further speed up inference.
  • Generalization: While promising results were shown on relation extraction, further exploration of MGT's applicability to other modalities and tasks is suggested.
  • Real-time HCI: The paper highlights the potential for real-time sketch-based HCI, and future work will focus on applying MGT to various sketch tasks for this purpose.
  • Code Availability: The authors have made their code and trained models publicly available, which is a significant contribution to the research community.

Summary updated

Abstract

Learning meaningful representations of free-hand sketches remains a challenging task given the signal sparsity and the high-level abstraction of sketches. Existing techniques have focused on exploiting either the static nature of sketches with convolutional neural networks (CNNs) or the temporal sequential property with recurrent neural networks (RNNs). In this work, we propose a new representation of sketches as multiple sparsely connected graphs. We design a novel graph neural network (GNN), the multigraph transformer (MGT), for learning representations of sketches from multiple graphs, which simultaneously capture global and local geometric stroke structures as well as temporal information. We report extensive numerical experiments on a sketch recognition task to demonstrate the performance of the proposed approach. Particularly, MGT applied on 414k sketches from Google QuickDraw: 1) achieves a small recognition gap to the CNN-based performance upper bound (72.80% versus 74.22%) and infers faster than the CNN competitors and 2) outperforms all RNN-based models by a significant margin. To the best of our knowledge, this is the first work proposing to represent sketches as graphs and apply GNNs for sketch recognition. Code and trained models are available at <uri xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">https://github.com/PengBoXiangShang/multigraph_transformer</uri> .
BibTeX
@article{xu2022multigraph,
  author = {Peng Xu and Chaitanya K. Joshi and Xavier Bresson},
  title = {{Multigraph Transformer for Free-Hand Sketch Recognition}},
  journal = {IEEE Trans. Neural Networks Learn. Syst.},
  year = {2022},
  url = {https://openreview.net/forum?id=bYKonn0c4-},
}
Figure