kernel regression on graphs; online learning on graphs; random Fourier features; stochastic gradient
Abstract :
[en] This work proposes an efficient batch-based implementation for kernel regression on graphs (KRG) using random Fourier features (RFF) and a low-complexity online implementation. Kernel regression has proven to be an efficient learning tool in the graph signal processing framework. However, it suffers from poor scalability inherent to kernel methods. We employ RFF to overcome this issue and derive a batch-based KRG whose model size is independent of the training sample size. We then combine it with a stochastic gradient-descent approach to propose an online algorithm for KRG, namely the stochastic-gradient KRG (SGKRG). We also derive sufficient conditions for convergence in the mean sense of the online algorithms. We validate the performance of the proposed algorithms through numerical experiments using both synthesized and real data. Results show that the proposed batch-based implementation can match the performance of conventional KRG while having reduced complexity. Moreover, the online implementations effectively learn the target model and achieve competitive performance compared to the batch implementations.
Disciplines :
Electrical & electronics engineering
Author, co-author :
Elias, Vitor R. M.
Gogenini, Vinay C.
Alves Martins, Wallace ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > SigCom
Werner, Stefan
External co-authors :
yes
Language :
English
Title :
Kernel Regression on Graphs in Random Fourier Features Space
Publication date :
2021
Event name :
IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP-2021)
Event date :
from 06-06-2021 to 11-06-2021
By request :
Yes
Audience :
International
Main work title :
IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP-2021), Toronto 6-11 June 2021
Peer reviewed :
Peer reviewed
European Projects :
H2020 - 742648 - AGNOSTIC - Actively Enhanced Cognition based Framework for Design of Complex Systems
A. Sandryhaila and J. M. F. Moura, “Big data analysis with signal processing on graphs: Representation and processing of massive data sets with irregular structure,” IEEE Signal Process. Mag., vol. 31, pp. 80-90, Sep. 2014.
D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains,” IEEE Signal Process. Mag., vol. 30, pp. 83-98, May 2013.
B. Boucher and S. Jenna, “Genetic interaction networks: better understand to better predict,” Front. in Genet., vol. 4, pp. 1-16, Dec. 2013.
W. Huang, T. A. W. Bolton, J. D. Medaglia, D. S. Bassett, A. Ribeiro, and D. Van De Ville, “A graph signal processing perspective on functional brain imaging,” Proc. IEEE, vol. 106, pp. 868-885, May 2018.
I. Jablonski, “Graph signal processing in applications to sensor networks, smart grids, and smart cities,” IEEE Sensors J., vol. 17, pp. 7659-7666, Dec. 2017.
A. Sandryhaila and J. M. F. Moura, “Discrete signal processing on graphs,” IEEE Trans. Signal Process., vol. 61, pp. 1644-1656, Apr. 2013.
A. Ortega, P. Frossard, J. Kovacevic, J. M. F. Moura, and P. Vandergheynst, “Graph signal processing: Overview, challenges, and applications,” Proc. IEEE, vol. 106, pp. 808-828, May 2018.
A. Sandryhaila and J. M. F. Moura, “Discrete signal processing on graphs: Graph filters,” in Proc. IEEE Int. Conf. Acoust., Speech, Signal Process., May 2013, pp. 6163-6166.
A. Gavili and X.-P. Zhang, “On the shift operator, graph frequency, and optimal filtering in graph signal processing,” IEEE Trans. Signal Process., vol. 65, pp. 6303-6318, Dec. 2017.
V. N. Ioannidis, D. Romero and G. B. Giannakis,”Inference of Spatio-Temporal Functions Over Graphs via Multikernel Kriged Kalman Filtering,” IEEE Trans. Signal Process., vol. 66, no. 12, pp. 3228-3239, June 2018.
D. Thanou, D. I. Shuman and P. Frossard, “Learning Parametric Dictionaries for Signals on Graphs,” IEEE Trans. Signal Process., vol. 62, no. 15, pp. 3849-3862, Aug 2014.
R. Nassif, C. Richard, J. Chen, and A. H. Sayed, “Distributed diffusion adaptation over graph signals,” in Proc. IEEE Int. Conf. Acoust., Speech, Signal Process., 2018, pp. 4129-4133.
F. Hua, R. Nassif, C. Richard, H. Wang and A. H. Sayed, “Online distributed learning over graphs with multitask graph-filter models,” IEEE Trans. Signal Inf. Process. Netw., vol. 6, pp. 63-77, Jan. 2020.
D. Romero, M. Ma, and G. B. Giannakis, “Kernel-based reconstruction of graph signals,” IEEE Trans. Signal Process., vol. 65, no. 3, pp. 764-778, Feb. 2017.
D. Romero, V. N. Ioannidis and G. B. Giannakis,”Kernel-based reconstruction of space-time functions on dynamic graphs,” IEEE J. Sel. Top. Signal Process., vol. 11, no. 6, pp. 856-869, Sep. 2017.
A. Venkitaraman, S. Chatterjee and P. Händel, “Predicting graph signals using kernel regression where the input signal is agnostic to a graph,” IEEE Trans. Signal Inf. Process. Netw., vol. 5, no. 4, pp. 698-710, Dec. 2019.
Y. Shen, G. Leus, and G. B. Giannakis, “Online graph-adaptive learning with scalability and privacy,” IEEE Trans. Signal Process., vol. 67, pp. 2471-2483, May 2019.
V. G. Gogineni, V. R. M. Elias, W. A. Martins and S. Werner, “Graph diffusion kernel LMS using random Fourier Features,” in Conf. Rec. Asilomar Conf. Signals Syst. Comput., pp. 1-5, Nov. 2020.
A. Rahimi and B. Recht, “Random features for large-scale kernel machines,” in Proc. Adv. Neural Inf. Process. Syst., pp. 1177-1184, 2007.
W. A. Gardner, “Learning characteristics of stochastic-gradient-descent algorithms: A general study, analysis, and critique,” Signal Process., vol 6, no. 2, pp. 113-133, 1984.
A. H. Sayed, Adaptive Filters. Wiley, Jan. 2008.
P. Di Lorenzo, S. Barbarossa, P. Banelli and S. Sardellitti, “Adaptive Least Mean Squares Estimation of Graph Signals,” IEEE Trans. Signal Inf. Process. Netw., vol. 2, no. 4, pp. 555-568, Dec. 2016.
“Reproducible Research | KTH”, https://www.kth.se/ise/research/reproducibleresearch-1. 433797, 2020. Accessed: 2020-08-18.
