Graph2vec Eval

graph2vec-eval

graph2vec: Learning Distributed Representations of Graphs — Narayanan et al. (2017) (arXiv:1707.05005, 2017)

What this evaluates

Evaluates the ability of graph representation learning methods to capture structural equivalence for downstream graph classification and clustering tasks. It probes whether learned embeddings can effectively distinguish between different graph classes or group structurally similar graphs without explicit supervision.

Datasets

• Benchmark Graph Classification Datasets (MUTAG, PTC, PROTEINS, NCI1, NCI109) — total 8882; splits: train (-1), test (-1)
• Android Malware Detection Dataset — total 10560; splits: train (-1), test (-1)
• AMD Malware Clustering Dataset — total 24650; splits: full (-1)

Metrics

• accuracy (primary) — range: percent
  • Average classification accuracy over 5 independent runs with random train-test splits. Computed as the fraction of correctly classified graphs multiplied by 100.
• Adjusted Rand Index (ARI) — range: percent
  • Standard clustering evaluation metric measuring the similarity between predicted clusters and ground-truth family labels, adjusted for chance. Reported as a percentage value.

Input / output format

Input: Graphs represented as adjacency structures with labeled nodes. Benchmarks use chemical/biological graphs; real-world tasks use Android API Dependency Graphs (ADGs) where nodes are instructions and edges are control flows.

Output: Fixed-dimensional graph embeddings (default 1024 dimensions). Embeddings are passed to an SVM classifier for classification or an Affinity Propagation algorithm for clustering.

Scoring recipe

# Classification
correct = sum(1 for p, g in zip(preds, gold) if p == g)
acc = (correct / len(gold)) * 100
final_acc = np.mean([acc for _ in range(5)])

# Clustering
ari = adjusted_rand_score(gold, preds)
ari_pct = ari * 100

Common pitfalls

• Trivially extending node-level embeddings (e.g., averaging node2vec outputs) to whole-graph tasks yields near-random accuracy on larger graphs.
• Pre-training/feature extraction time is a critical efficiency metric often overlooked; graph2vec's scalability differs significantly from handcrafted kernels like WL.
• Benchmark datasets are small (<5k graphs); performance on large real-world malware graphs (10k+ samples) can differ substantially and should be reported separately.

Evidence (verbatim from paper)

The experiment is repeated 5 times and the average accuracy is used to determine the effectiveness of classification. ... In order to quantitatively measure malware familial clustering accuracy, a standard clustering evaluation metric, namely, Adjusted Rand Index (ARI) is used. The ARI values lie in the range [-1, 1]. For the ease of understanding, we report the ARI as a percentage value.

Citation

@misc{narayanan2017graph2vec,
  title={graph2vec: Learning Distributed Representations of Graphs},
  author={Narayanan et al. (2017)},
  year={2017},
  note={arXiv:1707.05005}
}

• arXiv: 1707.05005