Manifold Learning and Graph Kernels

Comparing SVM classification performance on graph data with and without manifold learning dimensionality reduction, using Weisfeiler-Lehman graph kernels on protein and shape datasets.

Problem

Graph kernels like Weisfeiler-Lehman (WL) are effective for measuring similarity between graphs, but the resulting kernel matrices are high-dimensional and can be noisy for downstream classification. This project tests whether applying manifold learning — Isomap and Locally Linear Embedding (LLE) — to reduce that dimensionality actually improves classification accuracy, or whether it just adds complexity for no real gain.

Approach

• Implemented the Weisfeiler-Lehman subtree kernel from scratch: iterative node relabeling via neighbor aggregation, label compression, and normalized kernel matrix computation
• Applied two manifold learning techniques to the resulting kernel matrices: Isomap (geodesic distance preservation) and LLE (local linearity preservation)
• Evaluated on two real datasets: PPI (protein-protein interaction networks, 86 graphs, 2 classes) and SHOCK (2D shape skeletons, 150 graphs, 5 classes)
• Classified using a linear SVM with 10-fold stratified cross-validation
• Compared WL-only performance against WL+Isomap and WL+LLE to isolate the effect of manifold learning

Results

Dataset	Method	Accuracy	Parameters
PPI	WL only	0.82 ± 0.05	—
PPI	WL + Isomap	0.87 ± 0.03	k=12, d=5
SHOCK	WL only	0.76 ± 0.08	—
SHOCK	WL + LLE	0.83 ± 0.06	k=18, d=4

Manifold learning improved accuracy on both datasets — a 5-point gain on PPI with Isomap, and a 7-point gain on SHOCK with LLE — while also reducing variance across folds.

Tech Stack

Python, NumPy, SciPy, Scikit-learn (SVC, cross_val_score, Isomap, LocallyLinearEmbedding), Matplotlib

How to Run

pip install numpy scipy scikit-learn matplotlib

mkdir dataset
wget -P dataset/ http://www.dsi.unive.it/~atorsell/AI/graph/{PPI,Shock}.mat

# Compute WL kernel
python -c "
from wl_kernel import WeisfeilerLehman
wl = WeisfeilerLehman(graphs, h=4)
K = wl.run()
"

# Apply manifold learning and evaluate
python main.py

---

Contributor: Khushbu Mahendra Patil