On Using Classification Datasets to Evaluate Graph Outlier Detection: Peculiar Observations and New Insights

Area of Science:

• Data Mining
• Machine Learning
• Graph Analytics

Background:

• Outlier detection models are often evaluated using repurposed classification datasets.
• Graph-level outlier detection (GLOD) is an understudied area with significant real-world potential.
• Current practices repurpose graph classification datasets for GLOD by down-sampling one class to create outlier samples.

Purpose of the Study:

• To identify and analyze an issue with repurposing graph classification datasets for GLOD.
• To investigate the causes of performance variations in GLOD models.
• To question the appropriateness of current GLOD evaluation methodologies.

Main Methods:

• Investigated the impact of down-sampling different classes on ROC-AUC performance for GLOD.
• Analyzed graph embedding spaces generated by propagation-based models.
• Examined various graph embedding methods and downstream outlier detectors.

Main Results:

• A significant "performance flip" was observed, where model performance drastically changes (from high to worse-than-random) depending on the down-sampled class.
• Performance gaps were amplified by propagation in certain models.
• Disparity in within-class densities and overlapping class supports in embedding spaces were identified as key factors.
• The performance flip issue persists across different embedding methods, though the specific down-sampled version yielding higher performance may vary.

Conclusions:

• The identified performance flip issue raises concerns about the validity of averaging GLOD performance across different down-sampled dataset versions.
• There is a need to develop improved graph embedding methods to mitigate the observed performance flip.
• Further research is required to establish robust evaluation protocols for GLOD.