Comparison and Contrast of Custom Structural Graph Kernels and GraKeL Kernels

This repository contains a comprehensive benchmark evaluation framework comparing custom structural heuristics (Cycle and DAG kernels) against state-of-the-art graph kernels from the GraKeL library. The analysis is performed across five standard node-classification and graph benchmark datasets: Cora, Citeseer, Pubmed, Amazon Computers, and Amazon Photos.

---

Achievements

• Windows Deployment: Configured a portable Python 3.11 environment solving native C++ compilation blockages of the grakel package on Windows.
• Multiprocessing Safety: Resolved process recursion lockups on Windows caused by parallel memory profiling loops.
• Runtime Optimization: Refactored duplicate computation passes, achieving a 2x execution speedup without losing any similarity context.
• Pragmatic Directory Structure: Isolated raw dataset downloads into .gitignore and separated heatmap visuals into a distinct results/ folder for clean version control.

---

Theory and Methodology

Graph kernels measure similarity between graphs. While standard graph kernels often compute similarities over entire node feature spaces or node color transitions, this project extracts local structures using a Random Walk-based Subgraph Extraction method (5 walks of length 10 per graph).

On these subgraphs, we compare two custom heuristic kernels with five standard GraKeL kernels:

1. Custom Cycle Kernel: Constructs feature vectors by finding the count of cycles of length 3 to 6 in the subgraph, using networkx's cycle basis algorithms.
2. Custom DAG Kernel: Fits BFS trees rooted at each node of the subgraph to calculate the maximum Depth of Directed Acyclic Graph (DAG) structures, creating a depth histogram vector.
3. Weisfeiler-Lehman (WL) Kernel: Computes node similarities based on iterative label refinement.
4. Neighborhood Hash (NH) Kernel: Measures local neighbor label transition distributions.
5. Pyramid Match (PM) Kernel: Maps graph elements to multi-resolution histograms to find matching hierarchies.
6. WL Optimal Assignment (WL-OA) Kernel: Evaluates similarities using optimal assignment alignments between refined WL labels.
7. Propagation (Prop) Kernel: Leverages continuous attribute propagation steps to compute node-similarity scores.

---

Key Experimental Results

The table below shows the exact similarity scores computed between Subgraph 1 and Subgraph 3 (Index 0 vs Index 2) across the five evaluated datasets.

Graph Kernel	Cora	Citeseer	Pubmed	Amazon Computers	Amazon Photos
custom_cycle	0.0000	0.0000	0.0000	16.0000	36.0000
custom_dag	8.0000	0.0000	0.0000	4.0000	6.0000
weisfeiler_lehman	0.1782	0.0962	0.1242	0.1581	0.1667
neighborhood_hash	0.0238	0.0000	0.0000	0.0392	0.0175
pyramid_match	0.5093	0.0889	0.3429	0.5516	0.6467
weisfeiler_lehman_optimal_assignment	0.1782	0.0962	0.1242	0.1581	0.1667
propagation	0.1977	0.1155	0.0804	0.1897	0.1969

Analysis of Findings

• Structural Heuristics: The custom_cycle and custom_dag kernels represent raw count statistics. For sparse subgraphs (such as in Citeseer where subgraphs contain only 2 to 5 nodes), these heuristics output 0.0000 as no cycles of length $\ge 3$ or deep DAG structures exist. For dense Amazon subgraphs, they map larger values due to high connectivity.
• GraKeL Label Alignment: Kernels like weisfeiler_lehman and weisfeiler_lehman_optimal_assignment behave identically because the nodes are labeled identically.
• Pyramid Match Robustness: The pyramid_match kernel consistently yields the highest similarity values across all datasets because it finds similarity alignments at multiple resolutions of the node label space.

---

Visual Heatmap Plots

A complete $5 \times 5$ similarity matrix heatmap is generated for each dataset and saved under the results/ folder:

• Cora Heatmap: results/cora_kernels.png
• Citeseer Heatmap: results/citeseer_kernels.png
• Pubmed Heatmap: results/pubmed_kernels.png
• Amazon Computers Heatmap: results/amazon_computers_kernels.png
• Amazon Photos Heatmap: results/amazon_photos_kernels.png

---

Setup and Execution

Requirements

• Python 3.11 (highly recommended for pre-compiled Windows wheels)

Install the dependencies from the requirements.txt file:

pip install -r requirements.txt

Run the Analysis

Execute the comparison script from the root folder:

python comparing_a_contrasting_simple_graph_kernels.py

Note: Benchmarks datasets will automatically download into the local data/ directory (git-ignored) during execution.

---

License

This project is licensed under the MIT License - see the LICENSE file for details.