Model selection-inspired coefficients optimization for polynomial-kernel graph learning

Yang, Cheng and Wang, Fen and Ye, Minxiang and Zhai, Guangtao and Zhang, Xiao-Ping and Stankovic, Vladimir and Stankovic, Lina; (2022) Model selection-inspired coefficients optimization for polynomial-kernel graph learning. In: 2021 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC). 2021 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC) . IEEE, JPN. ISBN 978-988-14768-9-0

[thumbnail of Yang-etal-APSIPA-2021-Model-selection-inspired-coefficients-optimization-for-polynomial-kernel]
Preview
 Text. Filename: Yang_etal_APSIPA_2021_Model_selection_inspired_coefficients_optimization_for_polynomial_kernel.pdf
Accepted Author Manuscript
Download (708kB)| Preview

Abstract

Graph learning has been extensively investigated for over a decade, in which the graph structure can be learnt from multiple graph signals (e.g., graphical Lasso) or node features (e.g., graph metric learning). Given partial graph signals, existing node feature-based graph learning approaches learn a pair-wise distance metric with gradient descent, where the number of optimization variables dramatically scale with the node feature size. To address this issue, in this paper, we propose a low-complexity model selection-inspired graph learning (MSGL) method with very few optimization variables independent with feature size, via leveraging on recent advances in graph spectral signal processing (GSP). We achieve this by 1) interpreting a finite-degree polynomial function of the graph Laplacian as a positive-definite precision matrix, 2) formulating a convex optimization problem with variables being the polynomial coefficients, 3) replacing the positive-definite cone constraint for the precision matrix with a set of linear constraints, and 4) solving efficiently the objective using the Frank-Wolfe algorithm. Using binary classification as an application example, our simulation results show that our proposed MSGL method achieves competitive performance with significant speed gains against existing node feature-based graph learning methods.

ORCID iDs

Yang, Cheng, Wang, Fen, Ye, Minxiang, Zhai, Guangtao, Zhang, Xiao-Ping, Stankovic, Vladimir ORCID logoORCID: https://orcid.org/0000-0002-1075-2420 and Stankovic, Lina ORCID logoORCID: https://orcid.org/0000-0002-8112-1976;
CORE (COnnecting REpositories)