This repository contains the full experimental pipeline for a systematic evaluation of whole-graph embedding methods on real-world graph classification benchmarks.
The project benchmarks unsupervised structural descriptors and supervised graph neural networks across multiple complementary tasks, following a unified and reproducible protocol.
The work was conducted in the context of the Information Systems course at NTUA and accompanies a detailed experimental report.
We compare three representative whole-graph embedding paradigms:
- Graph2Vec – unsupervised, subgraph-based embeddings
- NetLSD – unsupervised, spectral graph signatures
- GIN (Graph Isomorphism Network) – supervised graph neural network
Unsupervised embeddings are evaluated using downstream classifiers, while GIN is trained end-to-end.
Experiments are conducted on standard graph classification benchmarks from TUDataset:
- MUTAG
- ENZYMES
- IMDB-MULTI
These datasets span different domains (chemistry, biology, social networks) and vary in size and complexity.
Each embedding method is evaluated along four axes:
- Embeddings used as input to an SVM (Graph2Vec, NetLSD)
- End-to-end supervised learning (GIN)
- Metrics: Accuracy, Weighted F1-score, ROC-AUC
- Hyperparameter tuning with Optuna
- Multiple random seeds for robustness
- k-means and Spectral Clustering on graph embeddings
- Metrics: Adjusted Rand Index (ARI), Silhouette score
- Qualitative visualization with t-SNE and UMAP
- Controlled perturbations:
- Edge removal and addition
- Node attribute shuffling (for GIN)
- Metrics:
- Embedding stability (mean cosine similarity)
- Accuracy degradation under perturbations
- Fixed-seed, deterministic perturbation protocol
- Embedding generation time
- Training time
- Hyperparameter tuning overhead
- Graph2Vec, NetLSD: KarateClub
- GIN: PyTorch Geometric
- Classification & clustering: Scikit-learn
- Hyperparameter tuning: Optuna
- Execution environment: Google Colab (GPU for GIN)
All experiments use fixed random seeds to ensure reproducibility.
- GIN achieves the highest classification performance, especially on MUTAG and ENZYMES.
- NetLSD provides exceptional stability and robustness to structural perturbations.
- Graph2Vec serves as a lightweight and efficient baseline but is sensitive to corpus changes.
- Accuracy, clustering quality, efficiency, and robustness are not strongly correlated, highlighting important practical trade-offs.
All experiments are fully reproducible using the provided notebooks and fixed seeds.
Results reported in the accompanying report can be regenerated by executing the notebooks in the notebooks/ folder.
A detailed analysis of the experimental setup, results, and discussion is provided in the accompanying PDF report.
- Angeliki Spanou-Kapantoni
- Charalambos-Ioannis Sfiris
School of Electrical and Computer Engineering
National Technical University of Athens
-
A. Narayanan et al., Graph2Vec: Learning Distributed Representations of Graphs,
IEEE ICDM Workshops, 2017.
https://github.com/benedekrozemberczki/graph2vec -
A. Tsitsulin et al., NetLSD: Hearing the Shape of a Graph,
ACM KDD, 2018.
https://github.com/xgfs/NetLSD -
K. Xu et al., How Powerful are Graph Neural Networks?,
ICLR, 2019.
https://arxiv.org/abs/1810.00826 -
PyTorch Geometric: Graph Neural Network Library
https://pytorch-geometric.readthedocs.io/ -
Karate Club: Graph Representation Learning Library
https://karateclub.readthedocs.io/ -
C. Morris et al., TUDataset: A Collection of Benchmark Datasets for Learning with Graphs,
arXiv:2007.08663, 2020.
https://chrsmrrs.github.io/datasets/docs/datasets/