Subgraph2vec Eval

subgraph2vec-eval

subgraph2vec: Learning Distributed Representations of Rooted Sub-graphs from Large Graphs — Narayanan et al. (2016) (arXiv:1606.08928, 2016)

What this evaluates

Evaluates the quality of distributed subgraph representations learned by subgraph2vec on graph classification and clustering tasks. It probes the model's ability to capture structural and semantic similarities in chemical/biological graphs and Android application control-flow graphs.

Datasets

• MUTAG — total 188; splits: train (-1), test (-1)
• PTC — total 344; splits: train (-1), test (-1)
• PROTEINS — total ?; splits: train (-1), test (-1)
• NCI1 — total ?; splits: train (-1), test (-1)
• NCI109 — total ?; splits: train (-1), test (-1)
• CLONE260 — total 260; splits: all (260)
• TRAIN10K — total 10000; splits: train (10000)
• TEST10K — total 10000; splits: test (10000)

Metrics

• Accuracy (primary) — range: [0, 1]
  • Proportion of correctly classified graphs out of the total test set. Reported as mean ± standard deviation over 5 random train/test splits.
• Adjusted Rand Index (ARI) — range: [-1, 1]
  • Standard clustering evaluation metric measuring the similarity between predicted cluster assignments and ground-truth clusters, adjusted for chance.

Input / output format

Input: Graphs represented as adjacency structures or Inter-procedural Control Flow Graphs (ICFGs) with nodes labeled by Android APIs or chemical structures.

Output: Class labels (e.g., mutagenic/benign, enzyme/non-enzyme, malware/benign) or cluster assignments for each graph.

Scoring recipe

def compute_accuracy(preds, gold):
    return sum(1 for p, g in zip(preds, gold) if p == g) / len(gold)

def compute_ari(pred_clusters, gold_clusters):
    from sklearn.metrics import adjusted_rand_score
    return adjusted_rand_score(gold_clusters, pred_clusters)

# For benchmarks: repeat 5 times with 90/10 split, average accuracy.
# For clone detection: compute ARI on full dataset clustering.

Common pitfalls

• Benchmark datasets like MUTAG/NCI can be solved with trivial features (e.g., node count), so they do not fully test real-world performance.
• Pre-training duration is reported alongside accuracy, but efficiency comparisons should account for different kernel computation costs and dataset sizes.
• The clone detection task is unsupervised clustering; ground-truth clusters must strictly match the 100 sets identified by the original dataset authors.

Evidence (verbatim from paper)

The experiment is repeated 5 times and the average accuracy (along with std. dev.) is used to determine the effectiveness of classification. A standard clustering evaluation metric, namely, Adjusted Rand Index (ARI) is used to determine clone detection accuracy. The ARI values lie in the range [-1, 1].

Citation

@misc{narayanan2016subgraph2vec,
  title={subgraph2vec: Learning Distributed Representations of Rooted Sub-graphs from Large Graphs},
  author={Narayanan et al. (2016)},
  year={2016},
  note={arXiv:1606.08928}
}

• arXiv: 1606.08928