Graph Classification Accuracy Eval

graph-classification-accuracy-eval

A simple yet effective baseline for non-attributed graph classification — Cai et al. (2018) (arXiv:1811.03508, 2018)

What this evaluates

Evaluates the ability of graph representation models to correctly classify entire graphs based on their structural topology and, optionally, node or edge attributes. It probes whether local structural summaries or complex neural architectures can capture discriminative patterns for tasks like social network or chemical compound categorization.

Datasets

• IMDB BINARY — total ?; splits: (unstated)
• IMDB MULTI — total ?; splits: (unstated)
• COLLAB — total ?; splits: (unstated)
• REDDIT BINARY — total ?; splits: (unstated)
• REDDIT 5K — total ?; splits: (unstated)
• REDDIT 12K — total ?; splits: (unstated)
• ENZYMES — total ?; splits: (unstated)
• PROTEINS — total ?; splits: (unstated)
• D&D — total ?; splits: (unstated)
• MUTAG — total ?; splits: (unstated)
• PTC — total ?; splits: (unstated)
• NCI1 — total ?; splits: (unstated)

Metrics

• accuracy (primary) — range: percent
  • Standard classification accuracy: the proportion of correctly predicted graph labels out of the total number of graphs in the dataset, reported as a percentage.

Input / output format

Input: Graph structures represented as adjacency matrices or edge lists, optionally with node degree features or label histograms. For non-attributed graphs, only topology is used; for chemical/protein graphs, node labels may be ignored or appended as extra features.

Output: A single discrete class label representing the graph's category.

Scoring recipe

def compute_accuracy(predictions, gold_labels):
    correct = sum(1 for p, g in zip(predictions, gold_labels) if p == g)
    return (correct / len(gold_labels)) * 100

Common pitfalls

• The baseline uses a linear SVM on handcrafted local features rather than end-to-end learning, making direct performance comparisons with data-hungry GNNs potentially misleading due to dataset size limitations.
• Chemical/protein datasets contain rich node labels, but the baseline intentionally ignores or hacks them, causing unfair disadvantage on label-rich graphs compared to label-aware kernels.
• Many reported GNN results in the tables are missing, indicating incomplete benchmarking across all datasets and models.

Evidence (verbatim from paper)

Comparing with GNN, although many accuracy data is not available, we can still clearly see that the state-of-the-art GNNs do not show significant improvement over our baseline. It is well known that neural networks are data hungry, so one possible explanation is that the size of the current dataset is limiting the representation power of GNNs.

Citation

@misc{cai2018simple,
  title={A simple yet effective baseline for non-attributed graph classification},
  author={Cai et al. (2018)},
  year={2018},
  note={arXiv:1811.03508}
}

• arXiv: 1811.03508