Introduction
Graphs provide a powerful framework for representing complex data structures, ranging from chemical molecules to social networks. However, most statistical learning tools require data to be represented as fixed-length numeric vectors. This process, known as graph embedding, often results in extremely high-dimensional and sparse vectors. These vectors frequently contain redundant or irrelevant features that introduce noise, hindering the performance of classification tasks.
This paper presents an enhancement to Fuzzy Multilevel Graph Embedding (FMGE) by introducing a supervised feature selection step. By utilizing the Relief algorithm, the researchers rank and select only the most discriminating structural features, significantly boosting classification accuracy while reducing computational complexity.
The FMGE Framework
The FMGE method extracts structural information from graphs across three distinct scales to ensure a comprehensive representation:
- Graph Level (Macro): Captures global properties such as the total number of nodes (order) and edges (size).
- Structural Level (Intermediate): Focuses on local topology, including node degrees and "subgraph homogeneity"—a measure of how similar a node is to its immediate neighbors.
- Elementary Level (Micro): Records granular details from individual node and edge attributes.
To handle continuous numeric data without significant information loss, FMGE employs fuzzy histograms. These overlapping intervals allow for a more nuanced mapping of structural measurements into discrete vector slots compared to traditional rigid binning.
Innovation: Supervised Feature Selection
The core contribution of this research is the application of the Relief algorithm for dimensionality reduction. Unlike unsupervised methods like Principal Component Analysis (PCA), which reduce features based solely on data variance, Relief is a supervised ranking method. It evaluates each feature based on its ability to distinguish a sample from its "near-hit" (the closest neighbor in the same class) versus its "near-miss" (the closest neighbor in a different class).
By selecting only the top-ranked features, the authors create a more "compact" and "potent" representation, adhering to the "less is more" principle: adding too many features eventually introduces noise that degrades classifier performance.
Experimental Setup and Datasets
The proposed method was evaluated using three standard benchmarks from the IAM Graph Database Repository:
- Letter LOW: Graphs representing 15 capital letters of the Roman alphabet.
- GREC: Graphs representing 22 different symbols from architectural and electronic drawings.
- Fingerprint: Graphs derived from fingerprint images, where nodes represent ridge endings and bifurcations.
Key Results
Testing the optimized FMGE with a $k$-nearest neighbor ($k$-NN) classifier yielded substantial improvements across all datasets. Notably, the dimensionality of the feature vectors was reduced by approximately 40-50% while accuracy increased.
| Dataset | Full FMGE Vector (Acc %) | FMGE + Relief Selection (Acc %) | Dimensionality Reduction |
|---|---|---|---|
| Letter LOW | 96.5% | 99.2% | 58 to 37 features |
| GREC | 97.2% | 99.8% | 79 to 47 features |
| Fingerprint | 76.6% | 85.5% | 127 to 61 features |
In the GREC and Fingerprint datasets, the Relief-optimized FMGE outperformed several state-of-the-art reference systems. The reduction in vector size also led to faster classification times, demonstrating the efficiency of the approach.
Conclusion
The integration of supervised feature selection via the Relief algorithm significantly enhances the robustness of Fuzzy Multilevel Graph Embeddings. By filtering out non-discriminative structural noise, the method achieves higher accuracy with more compact data representations. Future work will explore more sophisticated feature selection techniques and evaluate the scalability of this approach on large-scale networks.
Summary updated