Graph-Based Classification With Multiple Shift Matrices
- 13 January 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal and Information Processing over Networks
- Vol. 8, 160-172
Abstract
Due to their effectiveness in capturing similarities between different entities, graphical models are widely used to represent datasets that reside on irregular and complex manifolds. Graph signal processing offers support to handle such complex datasets. In this paper, we propose a novel graph filter design method for semi-supervised data classification. The proposed design uses multiple graph shift matrices, one for each feature, and is shown to provide improved performance when the feature qualities are uneven. We introduce three methods to optimize for the graph filter coefficients and the graph combining coefficients. The first method uses the alternating minimization approach. In the second method, we optimize our objective function by convex relaxation that provides a performance benchmark. The third method adopts a genetic algorithm, which is computationally efficient and better at controlling overfitting. In our simulation experiments, we use both synthetic and real datasets with informative and non-informative features. Monte Carlo simulations demonstrate the effectiveness of multiple graph shift operators in the graph filters. Significant improvements in comparison to conventional graph filters are shown, in terms of average error rate and confidence scores. Furthermore, we perform cross validation to show how our approach can control overfitting and improve generalization performance.Keywords
Funding Information
- National Science Foundation (I/UCRC 1540040)
- Arizona State University
This publication has 47 references indexed in Scilit:
- Semi-Supervised Multiresolution Classification Using Adaptive Graph Filtering With Application to Indirect Bridge Structural Health MonitoringIEEE Transactions on Signal Processing, 2014
- Multiple Graph Label Propagation by Sparse IntegrationIEEE Transactions on Neural Networks and Learning Systems, 2013
- Online Semi-Supervised Discriminative Dictionary Learning for Sparse Representation2013
- Graph spectral image smoothing using the heat kernelPattern Recognition, 2008
- Graph Cuts and Efficient N-D Image SegmentationInternational Journal of Computer Vision, 2006
- Fast protein classification with multiple networksBioinformatics, 2005
- Using gini-style indices to evaluate the spatial patterns of health practitioners: Theoretical considerations and an application based on Alberta dataSocial Science & Medicine, 1994
- Jointly Constrained Biconvex ProgrammingMathematics of Operations Research, 1983
- Implementing Quicksort programsCommunications of the ACM, 1978
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problemsMathematical Programming, 1976