A Structural Feature-Based Approach for Comprehensive Graph Classification

Abstract

The increasing prevalence of graph-structured data across various domains has intensified greater interest in graph classification tasks. While numerous sophisticated graph learning methods have emerged, their complexity often hinders practical implementation. In this article, we address this challenge by proposing a method that constructs feature vectors based on fundamental graph structural properties. We demonstrate that these features, despite their simplicity, are powerful enough to capture the intrinsic characteristics of graphs within the same class. We explore the efficacy of our approach using three distinct machine learning methods, highlighting how our feature-based classification leverages the inherent structural similarities of graphs within the same class to achieve accurate classification. A key advantage of our approach is its simplicity, which makes it accessible and adaptable to a broad range of applications, including social network analysis, bioinformatics, and cybersecurity. Furthermore, we conduct extensive experiments to validate the performance of our method, showing that it not only reveals a competitive performance but in some cases surpasses the accuracy of more complex, state-of-the-art techniques. Our findings suggest that a focus on fundamental graph features can provide a robust and efficient alternative for graph classification, offering significant potential for both research and practical applications.

25 pages, 6 Figures

References in corpus (20)

• Emergence of scaling in random networks
• The structure and function of complex networks
• A Comprehensive Survey on Graph Neural Networks
• DeepWalk: Online Learning of Social Representations
• Graph Embedding Techniques, Applications, and Performance: A Survey
• Hierarchical Graph Representation Learning with Differentiable Pooling
• Graph Learning: A Survey
• A Survey on Graph Kernels
• Graph-Based Deep Learning for Medical Diagnosis and Analysis: Past, Present and Future
• Understanding the dynamics of biological and neural oscillator networks through exact mean-field reductions: a review
• Towards Sparse Hierarchical Graph Classifiers
• Subgraph Matching Kernels for Attributed Graphs
• ASGN: An Active Semi-supervised Graph Neural Network for Molecular Property Prediction
• Synchronization of complex human networks
• Subgraph Networks with Application to Structural Feature Space Expansion
• Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification
• KGNN: Harnessing Kernel-based Networks for Semi-supervised Graph Classification
• Understanding Isomorphism Bias in Graph Data Sets
• Discriminative structural graph classification
• Personalized graph feature-based multi-omics data integration for cancer subtype identification