Classifying Graphs as Images with Convolutional Neural Networks

Antoine Jean-Pierre Tixier, Giannis Nikolentzos, Polykarpos Meladianos, Michalis VazirgiannisarXiv 2017 · OpenReview

TL;DR

This paper proposes a novel method to represent graphs as multi-channel images, allowing standard 2D Convolutional Neural Networks (CNNs) to classify them. This approach achieves state-of-the-art or competitive results on several real-world graph classification tasks while being significantly faster than traditional graph kernel methods.

What Problem Does This Paper Address?

Graph classification is a crucial task in many domains, from bioinformatics to social network analysis, where the goal is to assign a category to an entire graph. Historically, graph kernels have been the dominant approach. However, graph kernels suffer from significant limitations: high computational complexity, especially for large datasets and graphs, and a disconnect between feature extraction (kernel computation) and classification (SVM training), meaning features aren't optimized for the specific task. While graph CNNs offer an alternative, they often require complex, specialized architectures. This paper aims to bridge this gap by enabling the use of simple, off-the-shelf 2D CNNs for graph classification, overcoming the limitations of graph kernels.

Methods

The core innovation lies in transforming graphs into image-like representations. This is achieved in three steps:

  1. Graph Node Embeddings: Nodes within a graph are first embedded into a lower-dimensional space. The paper explores two methods: spectral embeddings (using eigenvectors of the adjacency matrix) and node2vec (a more advanced technique that learns embeddings based on biased random walks).
  2. Alignment and Compression with PCA: Since node embedding methods can be stochastic, Principal Component Analysis (PCA) is used to align and compress the embedding spaces across different graphs. This ensures comparability and reduces dimensionality.
  3. 2D Histograms as Image Channels: The compressed embedding space is then sliced into 2D planes. Each plane is discretized into a fixed number of bins, and a 2D histogram is computed, counting the number of nodes falling into each bin. These histograms form the channels of the resulting "image." For graphs with continuous node attributes, these attributes are also embedded, compressed, and used to form additional channels.

This process results in a fixed-size image representation for each graph, regardless of its original size, making it directly compatible with standard 2D CNN architectures.

Datasets

The paper evaluates its method on a combination of synthetic and real-world datasets:

  • Synthetic Datasets: A synthetic 5-class dataset was created using the Stochastic Block Model and the Barabási-Albert model to generate graphs with varying community structures and scale-free properties.
  • Real-World Datasets: Experiments were conducted on six real-world datasets:
  • Social network datasets: REDDIT-B, REDDIT-5K, REDDIT-12K, COLLAB, and IMDB-B.
  • Bioinformatics dataset: PROTEINS_full, which includes continuous node attributes.

Key Insights and Ideas

  • Reversing the Problem: Instead of developing new graph CNN architectures, the authors ingeniously adapt existing image-based CNNs by transforming graphs into images. This leverages the maturity and efficiency of image processing pipelines.
  • Spatial Dependence Property: The key challenge in applying CNNs to graphs is that adjacency matrices don't inherently satisfy the "spatial dependence property" (nearby elements are more related than distant ones), which is fundamental to CNNs. Node embeddings create a space where this property holds, and the histogram representation then captures this spatial structure in an image format.
  • Fixed-Size Representation: The histogram-based image representation ensures that all graphs, regardless of their size (number of nodes/edges), are mapped to a fixed-size input for the CNN. This is a significant advantage over methods that struggle with variable-sized inputs.
  • Leveraging Node Attributes: The method seamlessly integrates continuous node attributes by treating them as additional channels in the image representation, demonstrating its flexibility.

Key Results

  • Accuracy: The proposed method achieved state-of-the-art or competitive accuracy on 4 out of 6 real-world datasets. Specifically, it outperformed all baselines on REDDIT-12K (by 6.81%) and REDDIT-B (by 2.82%), and also achieved best performance on REDDIT-5K and PROTEINS_full.
  • Time Complexity: The approach offers a significant speedup over graph kernels. While graph kernel matrix computation can be quadratic in the number of graphs, the proposed method has constant time complexity per instance and linear complexity per dataset, making it much more scalable. For example, kernel matrix computation for REDDIT-12K took over 20,000 seconds for WL kernel, while the 2D CNN took only 52 seconds per epoch.
  • Flexibility: The method demonstrated its ability to leverage both graph topology and continuous node attributes effectively.

Limitations and Future Work

  • Parameter Tuning: Finding the optimal parameters for node embedding algorithms (like node2vec) can require effort, especially for dense graphs. The authors hypothesize that their slightly lower performance on COLLAB and IMDB-B might be due to default node2vec parameters not being ideal for these dense structures.
  • Data Augmentation: While a smoothed bootstrap data augmentation technique was explored, its performance improvement was marginal on REDDIT-B and not successful on other datasets. Further research is needed to make data augmentation more effective for this graph-to-image representation.
  • Embedding Method Choice: The performance can depend on the choice of node embedding method and its parameters. The paper explored spectral embeddings and node2vec, with node2vec generally yielding better results.

Future work could focus on more systematic ways to optimize node embedding parameters for different graph structures and further developing effective data augmentation strategies.

Summary updated

Abstract

Graph learning is currently dominated by graph kernels, which, while powerful, suffer some significant limitations. Convolutional Neural Networks (CNNs) offer a very appealing alternative, but processing graphs with CNNs is not trivial. To address this challenge, many sophisticated extensions of CNNs have recently been introduced. In this paper, we reverse the problem: rather than proposing yet another graph CNN model, we introduce a novel way to represent graphs as multi-channel image-like structures that allows them to be handled by vanilla 2D CNNs. Experiments reveal that our method is more accurate than state-of-the-art graph kernels and graph CNNs on 4 out of 6 real-world datasets (with and without continuous node attributes), and close elsewhere. Our approach is also preferable to graph kernels in terms of time complexity. Code and data are publicly available.
BibTeX
@misc{tixier2017classifying,
  author = {Antoine Jean-Pierre Tixier and Giannis Nikolentzos and Polykarpos Meladianos and Michalis Vazirgiannis},
  title = {{Classifying Graphs as Images with Convolutional Neural Networks}},
  year = {2017},
  eprint = {1708.02218},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1708.02218},
}

Loading related content...

Figure