Improving Fuzzy Multilevel Graph Embedding through Feature Selection Technique

Muhammad Muzzamil Luqman, Jean-Yves Ramel, Josep Lladós

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:

  1. Graph Level (Macro): Captures global properties such as the total number of nodes (order) and edges (size).
  2. 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.
  3. Elementary Level (Micro): Records granular details from individual node and edge attributes.
The three levels of information extracted by the FMGE framework: Macro, Intermediate, and Micro.

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.
Statistical characteristics of the Letter LOW, GREC, and Fingerprint datasets used for evaluation.

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

Abstract

Graphs are the most powerful, expressive and convenient data structures but there is a lack of efficient computational tools and algorithms for processing them. The embedding of graphs into numeric vector spaces permits them to access the state-of-the-art computational efficient statistical models and tools. In this paper we take forward our work on explicit graph embedding and present an improvement to our earlier proposed method, named “fuzzy multilevel graph embedding - FMGE”, through feature selection technique. FMGE achieves the embedding of attributed graphs into low dimensional vector spaces by performing a multilevel analysis of graphs and extracting a set of global, structural and elementary level features. Feature selection permits FMGE to select the subset of most discriminating features and to discard the confusing ones for underlying graph dataset. Experimental results for graph classification experimentation on IAM letter, GREC and fingerprint graph databases, show improvement in the performance of FMGE.
BibTeX
@inproceedings{luqman2012improving,
  author = {Muhammad Muzzamil Luqman and Jean-Yves Ramel and Josep Lladós},
  title = {{Improving Fuzzy Multilevel Graph Embedding through Feature Selection Technique}},
  booktitle = {SSPR/SPR},
  year = {2012},
  doi = {10.1007/978-3-642-34166-3\_27},
}
Figure