Adapted and Oversegmenting Graphs: Application to Geometric Deep Learning

Alberto Gomez, Veronika A. Zimmer, Bishesh Khanal, Nicolas Toussaint, Julia A. SchnabelarXiv 2018 · arXiv

TL;DR

This paper introduces a novel iterative method to transform images into sparse, feature-aligned graphs. By adapting a mesh to image boundaries and deriving a dual "oversegmenting" graph, the authors create a representation that significantly improves the performance of Geometric Deep Learning (GDL) on tasks like image classification, achieving state-of-the-art results on MNIST for graph-based methods.

What Problem Does This Paper Address?

Standard Convolutional Neural Networks (CNNs) excel at processing images because they exploit the regular grid structure of pixels. However, this grid is often redundant and doesn't explicitly capture the underlying topology of image features (like edges and shapes).

Geometric Deep Learning (GDL) aims to apply deep learning to non-Euclidean data like graphs. While images can be treated as graphs (where each pixel is a node), this results in massive, computationally expensive graphs that don't add new structural information. Existing alternatives, like using superpixels as nodes, often lack a mechanism to ensure edges represent meaningful topological relations. The authors address this gap by proposing a way to build graphs that are both sparse and structurally descriptive of the image content.

Methods

The proposed approach involves an iterative two-step process to create an Adapted Graph:

  1. Salient Point Detection: Starting with a uniform triangular mesh, the algorithm searches along each edge to find a "salient point"—a location where the edge intersects an image feature (boundary). The paper proposes two search strategies:
  2. SLIC-based: Inspired by superpixel clustering, it uses a weighted sum of spatial and color distance.
  3. Robust Feature Detection: A new method that uses "sided integrated intensity" to find boundaries even in very noisy images.
  4. Iterative Adaptation: Graph nodes are moved to the centroid of the salient points found on their connected edges. This process repeats until the graph stabilizes, effectively "wrapping" the mesh around image features.

From this adapted graph, they derive a Dual Graph (or oversegmenting graph). In this version, the nodes are the salient points themselves, and edges connect them along image boundaries.

Figure 1: Summary of the proposed oversegmenting graph method. Figure 1a shows an input image taken from the BSDS300 database. The rectangle indicates the zoomed region that is shown in the other figures for better appre- ciation. Initially, a uniform triangulated graph is placed in the image (Fig. 1b). This graph is adapted to the im- age so that edges intersect with image boundaries (Fig. 1c) at salient points, indicated as black dots in Fig. 1d. To obtain an oversegmenting graph, where edges run along image boundaries, we obtain the dual of the adapted graph by connecting salient points (Fig. 1e). The result, coded by saliency in grayscale (white is no salient, black is most salient), is shown in Fig. 1f.

The entire process is computationally efficient ($O(|V|)$ complexity) and fully parallelizable, as calculations for each edge are independent.

Datasets

The authors evaluated their method across three distinct types of data:

  • Synthetic Images: Simple geometric shapes (circles, squares, donuts) with varying levels of Gaussian noise (up to 100% of max intensity) to test robustness.
  • BSDS300 (Berkeley Segmentation Data Set): 200 natural images used to evaluate how well the salient points adhere to real-world boundaries.
  • MNIST: The classic handwritten digit dataset, used to test the representation power of the graphs in a classification task using a GDL architecture (SplineCNN).

Key Insights and Ideas

  • Topology Matters: Unlike standard superpixels which group pixels, this method focuses on the edges. By finding salient points on edges and adapting the mesh, the graph topology becomes a direct reflection of image structure.
  • Robustness to Noise: The "Robust" saliency measure (based on integrated intensity) significantly outperforms standard intensity-difference methods in noisy conditions.
  • Saliency as a Feature: The adaptation process naturally produces a "saliency measure" for every edge and node. Using this saliency as a node feature in a neural network—either alone or alongside raw intensity—provides a powerful signal for classification.
  • 1D Search in ND Space: Even for 3D or higher-dimensional data, the search for salient points remains a 1D problem along graph edges, making the method highly scalable.

Key Results

  • Boundary Adherence: The salient points achieved an average boundary recall of over 90% on both synthetic and natural images.
  • Noise Resistance: In synthetic tests, the robust saliency measure achieved 50-70% higher recall than the SLIC-based method at high noise levels.
  • State-of-the-Art Classification: On MNIST, using the adapted graphs with SplineCNN achieved 97.86% accuracy.
  • Efficiency: The method outperformed previous graph-based approaches while using fewer nodes (e.g., 64 nodes vs. 75 superpixels). Combining both intensity and saliency features yielded the best results.
Comparison of salient point search strategies under increasing noise.

Limitations and Future Work

  • Fixed Initial Topology: The method currently starts with a uniform triangular mesh. While the nodes move, the connectivity (which node is connected to which) remains fixed. Future work could explore dynamic topology where edges are added or removed during adaptation.
  • Color and 3D: While the theory supports color (RGB) and 3D data, the experimental validation focused primarily on 2D grayscale images.
  • Parallel Implementation: Although the algorithm is theoretically parallelizable, the authors noted that a high-performance parallel implementation was left for future work.

Summary updated

Abstract

We propose a novel iterative method to adapt a a graph to d-dimensional image data. The method drives the nodes of the graph towards image features. The adaptation process naturally lends itself to a measure of feature saliency which can then be used to retain meaningful nodes and edges in the graph. From the adapted graph, we also propose the computation of a dual graph, which inherits the saliency measure from the adapted graph, and whose edges run along image features, hence producing an oversegmenting graph. The proposed method is computationally efficient and fully parallelisable. We propose two distance measures to find image saliency along graph edges, and evaluate the performance on synthetic images and on natural images from publicly available databases. In both cases, the most salient nodes of the graph achieve average boundary recall over 90%. We also apply our method to image classification on the MNIST hand-written digit dataset, using a recently proposed Deep Geometric Learning architecture, and achieving state-of-the-art classification accuracy, for a graph-based method, of 97.86%.
BibTeX
@misc{gomez2018adapted,
  author = {Alberto Gomez and Veronika A. Zimmer and Bishesh Khanal and Nicolas Toussaint and Julia A. Schnabel},
  title = {{Adapted and Oversegmenting Graphs: Application to Geometric Deep Learning}},
  year = {2018},
  eprint = {1806.00411},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1806.00411},
}
Figure