Fair Benchmark for Unsupervised Node Representation Learning

Zhihao Guo, Shengyuan Chen, Xiao Huang, Zhiqiang Qian, Chunsing Yu, Yan Xu, Fang Ding

TL;DR

This paper introduces FURL, a novel framework for fairly and comprehensively evaluating unsupervised node representation learning (NRL) algorithms. By standardizing hyperparameter tuning and employing three diverse downstream tasks, FURL provides a robust benchmark to rank existing NRL methods and guide future research.

What Problem Does This Paper Address?

Node representation learning (NRL) aims to learn low-dimensional vector representations for nodes in a network, preserving topological structures and side information. While numerous NRL algorithms exist, comparing them is challenging due to varying experimental settings, hyperparameter tuning strategies, and evaluation tasks. This lack of a fair and comprehensive benchmark makes it difficult for researchers and practitioners to identify the most effective algorithms for specific scenarios. The paper addresses this by proposing a standardized framework to bridge this gap.

Methods

The core contribution is the Fair and Comprehensive Evaluation Algorithm (FURL). FURL addresses fairness by:

  • Standardized Hyperparameter Tuning: All algorithms are tuned using a random search within a fixed time budget for each task and dataset.
  • Consistent Environment: Experiments are conducted on the same hardware and software setup.

Comprehensiveness is achieved through three distinct evaluation tasks:

  1. Classification Fine Tuned via a Validation Set: NRL models are trained, hyperparameters are tuned using a validation set, and then evaluated on a test set for node classification.
  2. Link Prediction Fine Tuned in the First Run: NRL models are trained, hyperparameters are tuned based on link prediction performance, and then evaluated on link prediction.
  3. Classification Fine Tuned via Link Prediction: NRL models are trained, hyperparameters are tuned using link prediction performance, and then the resulting embeddings are used for node classification.

An integration schema based on rank products is used to compute an overall rank for each algorithm across all tasks and datasets.

Datasets

The paper evaluates algorithms on eight publicly available real-world attributed networks:

  • Cora
  • Flickr
  • BlogCatalog
  • Citeseer
  • Pubmed
  • Chameleon
  • Film
  • Squirrel

These datasets vary in size, number of nodes and edges, and attribute dimensionality.

Key Insights and Ideas

  • The Need for Standardization: The paper strongly emphasizes that inconsistent evaluation settings are a major bottleneck in advancing NRL research. FURL directly tackles this by imposing strict controls on tuning time and methodology.
  • Task Diversity Matters: Evaluating NRL algorithms across multiple downstream tasks (classification and link prediction) reveals different strengths and weaknesses. An algorithm that excels at one task might not perform as well on another.
  • Hyperparameter Tuning Efficiency is Key: More efficient algorithms, capable of performing more tuning rounds within the fixed time budget, often achieve better results. This highlights the interplay between algorithm design and practical performance.
  • Label-Based Tuning Advantage: Tuning hyperparameters using labeled data (Task 1) generally leads to better performance compared to unsupervised tuning (Tasks 2 and 3), suggesting that leveraging available labels, even for tuning, can be beneficial.
  • Algorithm Specialization: Some algorithms, like SDNE, are specifically designed for link prediction and perform poorly on classification tasks, underscoring the importance of algorithm specialization.

Key Results

  • Top Performers: For pure networks, ProNE ranked first overall. For attributed networks, CAN achieved the top rank.
  • Consistency: Generally, algorithms that performed well overall also ranked highly across individual tasks, though some exceptions like NetSMF showed task-specific variations.
  • Hyperparameter Tuning Rounds: Efficient algorithms like ProNE and DeepWalk were able to perform significantly more hyperparameter tuning rounds, contributing to their strong performance. FeatWalk, for instance, tuned hyperparameters 338 times on the BlogCatalog dataset.
  • Random Search Sufficiency: The paper found that random search for hyperparameter tuning yielded results comparable to more sophisticated methods like Tree-structured Parzen Estimator (TPE), justifying its use in FURL for simplicity and efficiency.

Limitations and Future Work

  • Hardware Dependency: The paper acknowledges that fairness can be affected by whether methods employ GPUs, as this can lead to performance disparities. They suggest that a method's ability to utilize GPU resources is an advantage.
  • Hyperparameter Search Space: The continuous nature of some hyperparameters and the fixed tuning time pose a challenge. The authors addressed this by discretizing search spaces for commonly used parameters.
  • Future Work: The authors plan to extend FURL by including more NRL algorithms and larger datasets. They also aim to incorporate efficiency metrics (parameter efficiency, memory efficiency, learning efficiency) and analyze algorithm performance scaling with graph size to better understand generalization abilities.

Summary updated

Abstract

Most machine-learning algorithms assume that instances are independent of each other. This does not hold for networked data. Node representation learning (NRL) aims to learn low-dimensional vectors to represent nodes in a network, such that all actionable patterns in topological structures and side information can be preserved. The widespread availability of networked data, e.g., social media, biological networks, and traffic networks, along with plentiful applications, facilitate the development of NRL. However, it has become challenging for researchers and practitioners to track the state-of-the-art NRL algorithms, given that they were evaluated using different experimental settings and datasets. To this end, in this paper, we focus on unsupervised NRL and propose a fair and comprehensive evaluation framework to systematically evaluate state-of-the-art unsupervised NRL algorithms. We comprehensively evaluate each algorithm by applying it to three evaluation tasks, i.e., classification fine tuned via a validation set, link prediction fine-tuned in the first run, and classification fine tuned via link prediction. In each task and each dataset, all NRL algorithms were fine-tuned using a random search within a fixed amount of time. Based on the results for three tasks and eight datasets, we evaluate and rank thirteen unsupervised NRL algorithms.
BibTeX
@article{guo2022fair,
  author = {Zhihao Guo and Shengyuan Chen and Xiao Huang and Zhiqiang Qian and Chunsing Yu and Yan Xu and Fang Ding},
  title = {{Fair Benchmark for Unsupervised Node Representation Learning}},
  journal = {Algorithms},
  year = {2022},
  doi = {10.3390/a15100379},
}
Figure