Almost Free Inductive Embeddings Out-Perform Trained Graph Neural Networks in Graph Classification in a Range of Benchmarks
To train or not to train — that is not the question
(Anonymous)
Untrained Graph Convolutional Network [1] (uGCN) with randomly assigned weights has been my primary baseline encoder for a range of tasks on graph data due to extremely low cost, simplicity of implementation, and quite obvious elegance. Yet no one (to the best of my knowledge) had reported benchmarks for actual performance of this simple model against it’s big sister — a fully grown (end-to-end trained) Graph Convolutional Network (CGN) in supervised setting. And so I did.
Motivation: to find out whether or not uGCN produces high quality representations that can be used in a range of downstream tasks on graphs in the inductive setting, so that trained models can generalize to previously unseen data (inspired by recently reported results [2] for the transductive setup).
Results were entertaining. In the worst case scenario simple models (uGCN + degree kernel + random forest) scored 54:90 vs end-to-end trained GCNs, while a more realistic scenario resulted in devastating 93:51, suggesting that we can have almost free embeddings that outperform or closely match end-to-end trained GCNs in graph classification tasks at a fraction of cost. Tiny models took only ~10 minutes to train while the whole experiment lasted ~4 hours. Let’s proceed into details and find out what has happened!
Just in case your reading preferences favour code over essays, please feel free to experiment with the accompanying colab notebook.
Preliminaries
Many important real-world datasets come in the form of graphs or networks: social networks, knowledge graphs, protein-interaction networks, the World Wide Web, etc. (just to name a few) [1].
A Graph usually written as G=(V, E) is a mathematical model consisting of a set of vertices V and a set of edges E — pairwise connections e(i, j) between vertices i and j. An extension of Graph is a Labeled Property Graph that allows for feature vectors xi assigned to vertices vi (we also can assign features to edges, yet this is beyond the scope of today’s experiment).
A Graph Neural Network [3] (GNN) is a machine learning model (a parametric function that adjusts, or in other words learns, parameters from data) that extends a well known family of biologically inspired algorithms into a domain of unstructured graph data. IMHO, message passing is the simplest intuition for the mechanics of GNNs and it is reasonable to refer to the mnemonic rule ‘tell me who is your friend and I will tell you who you are’. Graph Convolutional Networks (GCNs) are very well described by their inventor here (https://tkipf.github.io/graph-convolutional-networks/) and I find it challenging to tell the story better.
Data
Let’s run a series of experiments on publicly available data. We are going to (i) get data from TUDatasets [4] (a collection of benchmark datasets), and (ii) restrict our exercise to binary classification (property prediction) of small molecules. Yet another limitation in our endeavour is (iii) use of graphs with labeled vertices.
Induced constraints leave us with a list of datasets widely used to benchmark novel algorithms. These are: AIDS, BZR, COX2, DHFR, MUTAG, and PROTEINS. All these data are already available as a part of Pytorch Geometric [5] (a library for deep learning on graphs) in two versions: original and cleaned of duplicates [6]. That leaves us with 12 datasets at hand.
AIDS Antiviral Screen Data [7]
The DTP AIDS Antiviral Screen has checked tens of thousands of compounds for evidence of anti-HIV activity. Available are screening results and chemical structural data on compounds that are not covered by a confidentiality agreement. Original dataset contains 2000 molecules, and its cleaned version leaves us with 1110 data points.
Benzodiazepine receptor (BZR) ligands [8]
Original dataset contains 405 molecules, and its cleaned version leaves us with 276 data points.
Cyclooxygenase-2 (COX-2) inhibitors [8]
Original dataset contains 467 molecules, and its cleaned version leaves us with 237 data points.
Dihydrofolate reductase (DHFR) inhibitors [8]
Original dataset contains 756 molecules, and its cleaned version leaves us with 578 data points.
MUTAG [9]
The MUTAG dataset consists of 188 chemical compounds divided into two classes according to their mutagenic effect on a bacterium. Its cleaned version leaves us with 135 structures.
PROTEINS [10]
Protein graphs from protein files of the protein data bank (PDB) — a dataset of enzymes and not-enzymes. Original dataset contains 1113 molecules, and its cleaned version leaves us with 975 data points.
Experiment Design
Tournament be it!
For every dataset we run 12 rounds of training and testing.
For every round we:
I
Make randomized 80/20 split in Pytorch Geometric (starting with random seed = 42 and incrementing the seed by 1 for every following round), so that 80% of data points (graphs) are assigned into the training set, while the rest 20% go into the test set;
II
Train models on the training set and assess accuracy on the test set.
For tiny models that means preprocessing in order to generate features fed into a classifier.
For GCNs we run 200 epochs of training and testing with learning rate = 0.01 and report:
(A) average accuracy for the 10 final epochs — a realistic scenario;
(B) best accuracy achieved along the training process (as if we saved intermediate states in order to pick the best performing model) — best case scenario for GCNs (and worst for our tiny models);
III
Best model gets 1 point;
IV
If there’s a tie situation the point goes to the tiniest model.
There are 288 points to be awarded: 12 datasets * 12 rounds * 2 scenarios.
Models
Degree kernel (DK) — a histogram of node degrees (number of edges incident to a particular vertex), normalized to a number of nodes in a given graph (so that a feature vector for every graph consists of fraction sizes for nodes with particular number of connections — these sum to 1).
import networkx as nx
import numpy as np
from scipy.sparse import csgraph # g - a NetworkX graph
numNodes = len(g.nodes)
degreeHist = nx.degree_histogram(g)
# normalize
degreeKernel = [x/numNodes for x in degreeHist]
Untrained Graph Convolutional Network (uGCN) — a feed forward Graph Convolutional Network with randomly assigned weights for 3 layers with ReLU activations in between. We apply global mean pooling to the output 64-dimensional vectors (node embeddings) in order to obtain representations for graphs.
# INPUT
# g - a NetworkX graph
# X - node features of a graph g (np.array)
# W0, W1, W2 - randomly assigned weights# PREPROCESSING
# A - adjacency matrix of a graph g
A = nx.convert_matrix.to_scipy_sparse_matrix(g)
# D - normalized laplacian matrix of a graph g derived from A
D = sparse.csgraph.laplacian(A, normed=True) # GRAPH CONVOLUTIONAL NETWORK - FORWARD PASS
# Layer 0
Xc = D @ X @ W0
# ReLU
Xc = Xc * (Xc>0)
# concatenation of node features with those aggregated of neighbors
Xn = np.hstack((X, Xc))
# Layer 1
Xc = D @ Xn @ W1
# ReLU
Xc = Xc * (Xc>0)
Xn = np.hstack((Xn, Xc))
# Layer 2 - node embeddings
Xc = D @ Xn @ W2
# global mean pooling - graph embedding
embedding = Xc.sum(axis=0) / Xc.shape[0]
A combination of DK and uGCN (Mix) — concatenation of graph representations obtained by DK and uGCN models.
mix = degreeKernel + list(embedding)Random Forest (RF) classifier (from Scikit-learn [11] package) of 100 trees with maximum depth 17 is trained on the above.
Graph Convolutional Network (CGN) — an end-to-end classifier consisting of 3 convolution layers (64-dimensional) with ReLU activations in between, a global mean pooling layer (until this moment GCN closely matches uGCN), followed by a dropout layer and a linear classifier. We are going to refer to the models in best case scenario (B) as GCN-B, and to the models in the realistic scenario (A) as GCN-A. We are going to use the reference implementation of GCN for Pytorch Geometric in order to make the tournament as fair as possible.
Results
After 144 rounds (12 datasets * 12 rounds) of benchmarking between simple models and end-to-end trained GCNs the grand total of 288 points distributed as:
147:141
Accuracy on test sets varied between splits and there were situations where tiny models dominated over the complex contenders.
For example, the degree kernel took all the 48 points on the AIDS dataset demonstrating 10+ percent better accuracy than an end-to-end trained GCN.
Points collected:
90 — GCN-B;
71 — DK;
51 — GCN-A;
21 — uGCN.
Clean wins:DK in all versions of AIDS dataset in both scenarios (48 points);
GCN-B (scenario B) has championed in cleaned BZR (12), COX2 (24) and PROTEINS (24) - all versions;The rest of the points distributed as follows.-----------------
Dataset: BZR, cleaned: yes
Scenario: A
DK 0
uGCN 3
Mix 1
GCN 8-----------------
Dataset: BZR, cleaned: no
Scenario: A
DK 4
uGCN 1
Mix 4
GCN 3-----------------
Dataset: BZR, cleaned: no
Scenario: B
DK 1
uGCN 0
Mix 1
GCN 10-----------------
Dataset: COX2, cleaned: yes
Scenario: A
DK 0
uGCN 3
Mix 1
GCN 8-----------------
Dataset: COX2, cleaned: no
Scenario: A
DK 0
uGCN 1
Mix 1
GCN 10-----------------
Dataset: DHFR, cleaned: yes
Scenario: A
DK 1
uGCN 1
Mix 4
GCN 6-----------------
Dataset: DHFR, cleaned: yes
Scenario: B
DK 0
uGCN 0
Mix 3
GCN 9-----------------
Dataset: DHFR, cleaned: no
Scenario: A
DK 2
uGCN 4
Mix 5
GCN 1-----------------
Dataset: DHFR, cleaned: no
Scenario: B
DK 0
uGCN 1
Mix 5
GCN 6-----------------
Dataset: MUTAG, cleaned: yes
Scenario: A
DK 2
uGCN 3
Mix 6
GCN 1-----------------
Dataset: MUTAG, cleaned: yes
Scenario: B
DK 1
uGCN 2
Mix 5
GCN 4-----------------
Dataset: MUTAG, cleaned: no
Scenario: A
DK 5
uGCN 0
Mix 7
GCN 0-----------------
Dataset: MUTAG, cleaned: no
Scenario: B
DK 5
uGCN 0
Mix 6
GCN 1-----------------
Dataset: PROTEINS, cleaned: yes
Scenario: A
DK 2
uGCN 1
Mix 0
GCN 9-----------------
Dataset: PROTEINS, cleaned: no
Scenario: A
DK 0
uGCN 1
Mix 6
GCN 5-----------------
Please check out the colab notebook for a detailed report of performance or refer to this summary of rounds (csv) or this Google Spreadsheet.
Overall, performance consistently varied between cleaned and original versions of datasets. That reminds of the value of having high quality data for reasonably good benchmarks. After all, the data is small and this might be the reason why we have such unstable results. The good news is that there is a trend in the research community to address the issue and a great deal of work is done in order to enable fair benchmarking.
Conclusion
As we see, the experiment proves the conjecture that in the graph property prediction setting for small molecules we can have almost free embeddings that outperform or closely match end-to-end trained GCNs in graph classification tasks at a fraction of cost. These findings are in line with the results of [2] in that conceptually Label Propagation is very much alike the message passing in Graph Convolutional Networks. An explanation of such a good performance, perhaps, is rooted in the dilemma: whether we should adjust spectral filter parameters so that output embeddings become linearly separable, or just opt for a more robust classifier as we just did.
Variance of performance between rounds yet again reminds that every benchmark is uneasy. It is worth mentioning the Free Lunch Theorem and state that use of several models is highly likely a good choice. Also worth noticing that splits do affect performance — for the same dataset the same models demonstrate significantly different quality of decisions made. That is why when benchmarking between models, please make sure you do train and test these on identical data. Besides, setting random seeds is not a panacea…
Next steps could be benchmarking on bigger datasets. Also it is worth exploring different problems, such as: link prediction, node and link classification, regression on graphs and so on — Graph Convolutional Networks (trained and not that much) — are very capable models.
Afterword
I first publicly spoke about uGCN as of one-size-almost-for-all solution over two years ago at PyData-Lisbon Meetup, naming it A Royal Majestic Shortcut Through The Fourier Space, and assembled the first pipeline for graph classification around that time in order to demonstrate the power of graph convolutions to a girl eager to launch her aerospace startup. This essay is a spin-off of a real experiment (on private data) where we could insignificantly exceed performance set by tiny models after many hours of training.
Nowadays, as Machine Learning on Graphs has turned into a celebrity, new architectures for Graph Neural Networks emerge every week. However, there is relatively little understanding of why GNNs are successful in practice and whether they are necessary for good performance [2].
Before you step into the wonderful world of Machine Learning on Graphs, please get familiar with the basics. There’s great effort put into making the latest findings (as well as classical methods) available to a wider audience free of charge. To name just a few of many endeavors worth attention: cs224w curriculum and lectures, Open Graph Benchmark [14], and a recent work on foundations of Geometric Deep Learning [15] that provides a clear framework for making new architectures yet to be developed. One more thing — do always start with simple baselines like kernel methods or Unsupervised Graph Convolutional Networks — quite often these tiny models excel.
Be sustainable, use efficient algorithms. Sometimes not learning is power.
References
[1] Kipf & Welling, Semi-Supervised Classification with Graph Convolutional Networks (2017), International Conference on Learning Representations;
[2] Huang et al., Combining Label Propagation and Simple Models out-performs Graph Neural Networks (2021), International Conference on Learning Representations;
[3] Scarselli et al., The Graph Neural Network Model (2009), IEEE Transactions on Neural Networks ( Volume: 20, Issue: 1, Jan. 2009);
[4] Morris et al.,TUDataset: A collection of benchmark datasets for learning with graphs (2020), ICML 2020 Workshop on Graph Representation Learning and Beyond;
[5] Fey & Lenssen, Fast Graph Representation Learning with PyTorch Geometric (2019), ICLR Workshop on Representation Learning on Graphs and Manifolds;
[6] Ivanov, Sviridov & Burnaev, Understanding isomorphism bias in graph data sets (2019), arXiv preprint arXiv:1910.12091;
[7] Riesen & Bunke, IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning (2008), In: da Vitora Lobo, N. et al. (Eds.), SSPR&SPR 2008, LNCS, vol. 5342, pp. 287–297;
[8] Sutherland et al., Spline-fitting with a genetic algorithm: a method for developing classification structure-activity relationships (2003), J. Chem. Inf. Comput. Sci., 43, 1906–1915;
[9] Debnath et al., Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds (1991), J. Med. Chem. 34(2):786–797;
[10] Dobson & Doig, Distinguishing enzyme structures from non-enzymes without alignments (2003), J. Mol. Biol., 330(4):771–783;
[11] Pedregosa et al., Scikit-learn: Machine Learning in Python (2011), JMLR 12, pp. 2825–2830;
[12] Waskom, seaborn: statistical data visualization (2021), Journal of Open Source Software, 6(60), 3021;
[13] Hunter, Matplotlib: A 2D Graphics Environment (2007), Computing in Science & Engineering, vol. 9, no. 3, pp. 90–95;
[14] Hu et al., Open Graph Benchmark: Datasets for Machine Learning on Graphs (2020), arXiv preprint arXiv:2005.00687;
[15] Bronstein et al., Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges (2021), arXiv preprint arXiv:2104.13478.
