Source-linked AI summary
A Simple Baseline Algorithm for Graph Classification
Nathan de Lara, Edouard Pineau
TL;DR
Graph classification needs methods that capture graph structure without relying on complex mathematics or heavy computation. The paper uses normalized-Laplacian eigenvalues as spectral graph features, classifies them with standard models, and reports competitive performance with fast experiments.
Problem
Existing graph-classification approaches offer different strengths and weaknesses but often involve complex mathematics or substantial computational requirements.
Method
The method represents each graph with selected positive normalized-Laplacian eigenvalues, zero-padding shorter graphs and applying a user-chosen standard classifier.
Results
The model achieves the best result on five of six datasets and runs the described experiments in less than 5 minutes.
Takeaways & Limitations
Normalized-Laplacian eigenvalues provide an easy-to-extract representation that can be combined with other graph representations to improve model performance.
Takeaways & Limitations
The representation does not resolve graph isomorphism, which remains an open problem for spectral decomposition.
Abstract
from arXiv · showhide
Graph classification has recently received a lot of attention from various fields of machine learning e.g. kernel methods, sequential modeling or graph embedding. All these approaches offer promising results with different respective strengths and weaknesses. However, most of them rely on complex mathematics and require heavy computational power to achieve their best performance. We propose a simple and fast algorithm based on the spectral decomposition of graph Laplacian to perform graph classification and get a first reference score for a dataset. We show that this method obtains competitive results compared to state-of-the-art algorithms.
1 Introduction
Graph classification methods can be grouped into kernel, sequential, and embedding approaches that use graph structure without node features. These methods differ in how they compare or represent variable-sized graphs, and the paper’s model uses spectral graph features.
- Graph classification methods fall into graph kernels, sequential methods, and embedding methods when using structural information alone.
- Kernel methods: Kernel methods compare graph pairs through a similarity matrix and typically apply classifiers such as SVMs, often using Nyström approximations for scalability.
- Sequential methods: Sequential methods represent graphs as node sequences, but must design both node embeddings and the order in which they are processed.
- Embedding methods: Embedding methods derive fixed-length graph features compatible with standard classifiers, and the paper’s model uses spectral features.
2 Model
The model represents each graph with selected normalized-Laplacian eigenvalues, using zero padding for small graphs and a classifier chosen by the user. The ordered spectrum is node-indexing invariant, while graph-isomorphism characterization remains open.
- 2 Model: Graphs are assumed undirected and unweighted, and disconnected graphs are reduced to their largest connected component before constructing the normalized Laplacian.
- 2 Model: The model uses the k smallest positive normalized-Laplacian eigenvalues as a fixed-dimensional graph representation, with right zero padding when graphs have fewer than k nodes.The representation is called spectral features (SF).
- 2 Model: The ordered spectrum does not depend on node indexing, unlike eigenvectors, making it suitable for graph representation.
- Some Laplacian eigenvalues properties: Normalized-Laplacian eigenvalues lie between 0 and 2, while eigenvalue zero reflects connected components and eigenvalue 2 denotes a bipartite structure.
- 2 Model: Connecting spectral decomposition to graph isomorphism remains an open problem, limiting what the representation is known to establish.
- 2 Model: The classifier is left to the user; experiments use a random forest because it offers a computational speed-versus-accuracy trade-off.
3 Experiments
The experiments evaluate the spectral-feature model on six standard molecular graph datasets using stratified cross-validation and compare it with established graph-classification methods. The model achieves strong accuracy with a shared classifier and completes the full experiment quickly.
- Datasets: Evaluation covered six molecular graph datasets: MT, PTC, EZ, PF, DD, and NCI1, representing chemical compounds or protein structures with binary or multiclass labels.Nodes represent molecular substructures and edges represent chemical bonds or spatial proximity; dataset statistics are reported in Table 1.
- Experimental setup: Each dataset used ten stratified folds for cross-validation, with results averaged over testing folds and a fixed random seed for reproducibility.One fold served as testing data while the remaining folds formed the training data.
- Results: The model achieved the best result on five of six datasets—MT, PTC, EZ, PF, and NCI1—against the compared state-of-the-art methods.The comparison used results from Earth Mover’s Distance, Pyramid Match, Feature-Based, Dynamic-Based Features, and Stochastic Graphlet Embedding methods.
- Experimental setup: The experiments used one shared random-forest classifier configuration across datasets rather than intensive per-dataset hyperparameter tuning.The embedding dimension was set to each dataset’s average number of nodes, with classifier hyperparameters selected through randomized cross-validation.
- Computation analysis: The complete set of described experiments took less than 5 minutes, including approximately 3 minutes for graph embedding and under 1 minute for random-forest training and testing.Some kernel methods could not run within one day on DD, highlighting the computational contrast reported by the authors.
- Conclusion: The authors conclude that normalized Laplacian eigenvalues are useful graph-classification features and can be combined with other graph representations.They identify permutation-invariant classifiers as a possible continuation for incorporating eigenvector information.
A Results for different classifiers
The study compares several standard classifiers applied to the spectral embedding. Random forests perform best on every dataset except DD, where the multilayer perceptron is slightly better.
- Classifier comparison: Random forests provide the best results for all datasets except DD, where the multilayer perceptron reaches 75.6% accuracy versus 75.4% for random forests.The evaluated alternatives include k-nearest neighbors, a two-layer ReLU perceptron, a one-versus-one SVM, and ridge regression.
- Classifier comparison: The authors suggest that random forests suit the embedding because decision trees threshold the sequence of spectral energy levels.This interpretation links classifier behavior to whether embedding values fall above or below meaningful levels.
B Results for different embedding dimensions
The study evaluates RFC with spectral-feature embeddings of different dimensions, finding that small embeddings already classify non-trivially while k = 5 is competitive and k = 50 approaches the average graph size.
- B Results for different embedding dimensions: The embedding-dimension experiment evaluates k ∈{1, 5, 10, 25, 50} with the same hyperparameters as the main setup.
- B Results for different embedding dimensions: k = 5 provides results competitive with the state of the art, while k = 50 produces results relatively similar to k = avg(|V |).The comparison uses RF with spectral-feature embeddings across different dimensions.
- B Results for different embedding dimensions: Even the first energy level is sufficient to obtain non-trivial classification results.
- B Results for different embedding dimensions: Embedding all graphs with k = 50 took less than a minute in the experimental setting.
C Hyper parameters search and robustness analysis
The robustness analysis varies four RFC hyperparameters while fixing the random-forest seed, and finds that the method remains robust except for highly improper parameter settings.
- C Hyper parameters search and robustness analysis: RFC is very robust against variability in its hyperparameters.The analysis measures marginal accuracy variation while fixing other parameters and the random-forest seed.
- C Hyper parameters search and robustness analysis: Outliers in the box plots arise from highly improper settings such as n_estimators = 1 and max_depth = 1.
- C Hyper parameters search and robustness analysis: Table 5 defines the RFC parameter grid and identifies the experimental reference values used for robustness analysis.
- C Hyper parameters search and robustness analysis: The robustness analysis examines classification-accuracy distributions across four RFC hyperparameters using box plots of quartiles, confidence, and outliers.