Benchmark dataset for graph classification

This repository contains datasets to quickly test graph classification algorithms, such as Graph Kernels and Graph Neural Networks.

The purpose of this dataset is to make the features on the nodes and the adjacency matrix to be completely uninformative if considered alone. Therefore, an algorithm that relies only on the node features or on the graph structure will fail to achieve good classification results.

Dataset details

The dataset consists of graphs belonging to 3 different classes. The number of nodes in each graph is variable and the feature vector on each node is a one-hot vector of size 5, which encodes the color of the node. The class is determined by the relative position of the colors on the graph.

There are 4 versions of the dataset

• small_easy: 100 graphs per class, number of nodes varying in 40 and 80. Highly connected graphs.
• easy: 600 graphs per class, number of nodes varying in 100 and 200. Highly connected graphs.
• small_hard: 100 graphs per class, number of nodes varying in 40 and 80. Sparse graphs.
• hard: 600 graphs per class, number of nodes varying in 100 and 200. Sparse graphs.

In the hard dataset, it is necessary to consider higher order neighborhoods to understand the correct class and the graphs might be disconnected.

Format

The dataset is already split in training, validation and classification sets. Each set contains:

• the list of adjacency matrices in csr_matrix format,
• the list of node features as numpy arrays,
• the class labels contained in a numpy array,

The following code snippet shows how to load the data

import numpy as np

loaded = np.load('datasets/hard.npz', allow_pickle=True)

X_train = loaded['tr_feat'] # node features
A_train = list(loaded['tr_adj']) # list of adjacency matrices
y_train = loaded['tr_class'] # class labels

X_val = loaded['val_feat'] # node features
A_val = list(loaded['val_adj']) # list of adjacency matrices
y_val = loaded['val_class'] # class labels

X_test = loaded['te_feat'] # node features
A_test = list(loaded['te_adj']) # list of adjacency matrices
y_test = loaded['te_class'] # class labels

# OPTIONAL - Convert to networkx format
import networkx as nx

G_train = []
for a, x in zip(A_train, X_train):
    G = nx.from_scipy_sparse_matrix(a)
    x_tuple = tuple(map(tuple, x))
    nx.set_node_attributes(G, dict(enumerate(x_tuple)), 'features')
    G_train.append(G)
    
G_val = []
for a, x in zip(A_val, X_val):
    G = nx.from_scipy_sparse_matrix(a)
    x_tuple = tuple(map(tuple, x))
    nx.set_node_attributes(G, dict(enumerate(x_tuple)), 'features')
    G_val.append(G)
    
G_test = []
for a, x in zip(A_test, X_test):
    G = nx.from_scipy_sparse_matrix(a)
    x_tuple = tuple(map(tuple, x))
    nx.set_node_attributes(G, dict(enumerate(x_tuple)), 'features')
    G_test.append(G)

Results

Classification results obtained by using Graph Kernels and other techniques are reported below.

Feel free to send a pull request if you have results you'd like to share!

Graph Kernels

The Graph Kernels are computed with the GraKeL library. After each kernel is computed, an SVM that uses as precomputed kernel the Graph Kernel is trained and then evaluated on the test data. As SVM implementation, the sklearn.svm module was used. The code used to generate the results can be found in the notebook of this repository.

Dependecies to run the notebook:

• scikitlearn pip install sklearn
• networkx pip install networkx
• grakel pip install grakel-dev

Graph Neural Networks

Results obtained with the following GNN architecture: MP(32)-Pool-MP(32)-Pool-MP(32)-GlobalPool-Dense(Softmax). MP is a message-passing architecture. A Chebyshev convolutional layer [1] with K=1 and 32 hidden units was used here. Results refer to different graph pooling layers: Graclus [2], Node Decimation Pooling (NDP) [3], DiffPool [4], Top-K pooling [5], SAGpool [6] and MinCutPool [7].

Embedding Simplicial Complexes (ESC)

Techniques proposed in [8].

Hypergraph kernels

Techniques proposed in [9].

References

[1] Defferrard, M., Bresson, X., & Vandergheynst, P. (2016). Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems

[2] Dhillon, I. S., Guan, Y., & Kulis, B. (2007). Weighted graph cuts without eigenvectors a multilevel approach. IEEE transactions on pattern analysis and machine intelligence

[3] Bianchi, F. M., Grattarola, D., Livi, L., & Alippi, C. (2019). Hierarchical Representation Learning in Graph Neural Networks with Node Decimation Pooling

[4] Ying, Z., You, J., Morris, C., Ren, X., Hamilton, W., & Leskovec, J. (2018). Hierarchical graph representation learning with differentiable pooling. In Advances in neural information processing systems

[5] Gao, H., & Ji, S., Graph u-nets, ICML 2019

[6] Lee, J., Lee, I., & Kang, J., Self-attention graph pooling, ICML 2019

[7] F. M. Bianchi, D. Grattarola, C. Alippi, Spectral Clustering with Graph Neural Networks for Graph Pooling, ICML 2020

[8] Martino A, Giuliani A, Rizzi A., (Hyper) Graph Embedding and Classification via Simplicial Complexes. Algorithms. 2019 Nov; 12(11):223

[9] Martino A. and Rizzi A., (Hyper)graph kernels over simplicial complexes. 2020. Pattern Recognition

License

The dataset and the code are released under the MIT License. See the attached LICENSE file.