Using graphs to represent data sets that reside on irregular and complex structures can bring special advantages. Graph signal processing (DSPG) converts traditional DSP operators, such as time shift, linear filters and Fourier transform, from time and frequency domain to the graph domain. In machine learning applications, DSPG provides an approach for semi-supervised classification. Different from conventional graph-filter-based classifiers, we propose a new graph filter with multiple graph shift matrices that can provide better classification performance when the feature quality is uneven. To solve the resulting non-convex problem, a tight and efficient convex relaxation approach is introduced. Through a branch and bound optimization method, we can find the mapping from the optimum relaxed parameter set to original parameter set, which technically provides the globally optimum solution. Simulation experiments corroborate our results.

Original languageEnglish (US)
Title of host publicationConference Record - 53rd Asilomar Conference on Circuits, Systems and Computers, ACSSC 2019
EditorsMichael B. Matthews
PublisherIEEE Computer Society
Number of pages5
ISBN (Electronic)9781728143002
StatePublished - Nov 2019
Event53rd Asilomar Conference on Circuits, Systems and Computers, ACSSC 2019 - Pacific Grove, United States
Duration: Nov 3 2019Nov 6 2019

Publication series

NameConference Record - Asilomar Conference on Signals, Systems and Computers
ISSN (Print)1058-6393


Conference53rd Asilomar Conference on Circuits, Systems and Computers, ACSSC 2019
Country/TerritoryUnited States
CityPacific Grove


  • global optimization
  • graph filter
  • graph signal processing
  • semi-supervised classification

ASJC Scopus subject areas

  • Signal Processing
  • Computer Networks and Communications


Dive into the research topics of 'Global Optimization of Graph Filters with Multiple Shift Matrices'. Together they form a unique fingerprint.

Cite this