Graph topology inference benchmarks for machine learning

Carlos Lassance, Vincent Gripon, Gonzalo Mateos

Abstract

Graphs are nowadays ubiquitous in the fields of signal processing and machine learning. As a tool used to express relationships between objects, graphs can be deployed to various ends: I) clustering of vertices, II) semi-supervised classification of vertices, III) supervised classification of graph signals, and IV) denoising of graph signals. However, in many practical cases graphs are not explicitly available and must therefore be inferred from data. Validation is a challenging endeavor that naturally depends on the downstream task for which the graph is learnt. Accordingly, it has often been difficult to compare the efficacy of different algorithms. In this work, we introduce several ease-to-use and publicly released benchmarks specifically designed to reveal the relative merits and limitations of graph inference methods. We also contrast some of the most prominent techniques in the literature.

Introduction

In many real-world scenarios, data is available without an explicit map of its underlying connections. For instance, gene expression levels may be known without a clear gene-regulatory network, or sensor readings may exist without a physical map of the sensors. To leverage Graph Neural Networks (GNNs) or Graph Signal Processing (GSP) tools, one must first perform graph topology inference—the process of discovering hidden relationships (edges) between data points (vertices).

Historically, evaluation has relied on synthetic data or non-transferable tasks, lacking a common ground for fair comparison. This paper addresses this gap by proposing a diverse set of benchmarks testing inferred graphs in practical machine learning pipelines.

Methodology and Datasets

The authors evaluate three main categories of graph inference:

  1. Naive Baselines: Simple $k$-nearest neighbor ($k$-NN) graphs using standard similarity measures like Cosine similarity or RBF kernels.
  2. Sparsity-based (NNK): Non-Negative Kernel regression, representing each node as a sparse linear combination of its neighbors.
  3. Smoothness-based (Kalofolias): An optimization framework assuming signals change slowly across connected edges.

These methods are tested on three downstream tasks: Unsupervised Clustering (UCV), Semi-Supervised Classification (SSCV), and Denoising (DGS). The benchmarks utilize real-world datasets including Flowers102 (images), ESC-50 (audio), Cora (citations), and Toronto Traffic (sensor data).

Key Insights and Results

A primary finding of this work is that there is no universal "silver bullet" algorithm; performance is highly task-dependent. Notably, simple naive baselines are remarkably robust, often matching or exceeding complex optimization methods.

Table 4: Semi-supervised classification accuracy. Graph-based methods like SGC significantly outperform Logistic Regression on datasets like Cora.

In classification tasks, the Naive baseline with SGC achieved 67.19% accuracy on the Cora dataset, a substantial improvement over the 46.84% achieved by Logistic Regression. Similarly, in clustering tasks on ESC-50, Naive and NNK methods reached an Adjusted Mutual Information (AMI) of 0.66, beating the C-means baseline of 0.59.

Table 3: Best SNR for denoising on the Toronto Traffic dataset. The inferred Kalofolias graph outperforms the physical road graph.

In the denoising task, the Kalofolias method achieved the highest Signal-to-Noise Ratio (10.41), outperforming the "ground truth" physical road map (10.32). This suggests that physical connections are not always the optimal way to model signal flow.

Limitations and Future Work

Despite these advances, challenges remain. Inference methods struggle with binary features, such as the Bag-of-Words in Cora. Furthermore, sparse inferred graphs often break into disconnected components, which can hinder semi-supervised learning. Future work should explore discrete observation models and active learning strategies specifically designed for inferred topologies.

Summary updated

Abstract

Graphs are nowadays ubiquitous in the fields of signal processing and machine learning. As a tool used to express relationships between objects, graphs can be deployed to various ends: I) clustering of vertices, II) semi-supervised classification of vertices, III) supervised classification of graph signals, and IV) denoising of graph signals. However, in many practical cases graphs are not explicitly available and must therefore be inferred from data. Validation is a challenging endeavor that naturally depends on the downstream task for which the graph is learnt. Accordingly, it has often been difficult to compare the efficacy of different algorithms. In this work, we introduce several ease-to-use and publicly released benchmarks specifically designed to reveal the relative merits and limitations of graph inference methods. We also contrast some of the most prominent techniques in the literature.
BibTeX
@inproceedings{lassance2020graph,
  author = {Carlos Lassance and Vincent Gripon and Gonzalo Mateos},
  title = {{Graph topology inference benchmarks for machine learning}},
  booktitle = {MLSP},
  year = {2020},
  doi = {10.1109/mlsp49062.2020.9231794},
}
Figure