Global Optimization of Graph Filters with Multiple Shift Matrices

Using graphs to represent data sets that reside on irregular and complex structures can bring special advantages. Graph signal processing (DSP_G) 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, DSP_G 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.