Exploration of Kernel Parameters in Signal GBF-PUM Approximation on Graphs

Cavoretto, R.; De Rossi, A.; Mereu, S.

doi:10.2478/caim-2024-0004

Abstract

The application of the Partition of Unity Method (PUM) to signal approximation on graphs represents a recent advancement of this versatile and efficient interpolation technique. Given the novelty of this approach, little is yet known regarding the role of kernel parameters employed in constructing the associated Graph Basis Functions (GBFs). In order to shed light on this aspect, this study proposes several numerical tests obtained using GBFs generated by heat kernels and variational spline kernels.

References

A. Ortega, P. Frossard, J. Kovačević, J. M. F. Moura, and P. Vandergheynst, Graph signal processing: Overview, challenges, and applications, Proceedings of the IEEE, vol. 106, no. 5, pp. 808–828, 2018.
Search in Google Scholar Back to article
I. Z. Pesenson and M. Z. Pesenson, Graph signal sampling and interpolation based on clusters and averages, Journal of Fourier Analysis and Applications, vol. 27, no. 39, 2021.
Search in Google Scholar Back to article
I. Z. Pesenson, Sampling in Paley-Wiener spaces on combinatorial graphs, Transactions of the American Mathematical Society, vol. 360, no. 10, 2008.
Search in Google Scholar Back to article
R. S. Strichartz, Half sampling on bipartite graphs, Journal of Fourier Analysis and Applications, vol. 22, p. 1157–1173, 2016.
Search in Google Scholar Back to article
X. Wang, P. Liu, and Y. Gu, Local-set-based graph signal reconstruction, IEEE Transactions on Signal Processing, vol. 63, no. 9, pp. 2432 – 2444, 2015.
Search in Google Scholar Back to article
J. P. Ward, F. J. Narcowich, and J. D. Ward, Interpolating splines on graphs for data science applications, Applied and Computational Harmonic Analysis, vol. 49, no. 2, pp. 540—-557, 2020.
Search in Google Scholar Back to article
X. Wang, J. Chen, and Y. Gu, Local measurement and reconstruction for noisy bandlimited graph signals, Signal Processing, vol. 129, pp. 119–129, 2016.
Search in Google Scholar Back to article
I. D. Irawati, A. B. Suksmono, and I. J. M. Edward, An interpolation comparative analysis for missing internet traffic data, in Proceedings of the 3rd International Conference on Electronics, Communications and Control Engineering, p. 26–30, New York, NY, USA: Association for Computing Machinery, 2020.
Search in Google Scholar Back to article
H. Katayama, S. Yasuda, and T. Fuse, Comparative validation of spatial interpolation methods for traffic density for data-driven travel-time prediction, International Journal of Intelligent Transportation Systems Research, vol. 20, pp. 830–837, 2022.
Search in Google Scholar Back to article
R. Cavoretto, A. De Rossi, and W. Erb, Partition of unity methods for signal processing on graphs, Journal of Fourier Analysis and Applications, vol. 27, no. 66, pp. 342–346, 2021.
Search in Google Scholar Back to article
R. Cavoretto, A. De Rossi, S. Lancellotti, and F. Romaniello, Node-bound communities for partition of unity interpolation on graphs, Applied Mathematics and Computation, vol. 467, p. 128502, 2024.
Search in Google Scholar Back to article
N. Aronszajn, Theory of reproducing kernels, Transactions of the American Mathematical Society, vol. 68, pp. 337–404, 1950.
Search in Google Scholar Back to article
W. Erb, Graph signal interpolation with positive definite graph basis functions, Applied and Computational Harmonic Analysis, vol. 60, pp. 368–395, 2022.
Search in Google Scholar Back to article
D. Romero, M. Ma, and G. B. Giannakis, Kernel-based reconstruction of graph signals, IEEE Transactions on Signal Processing, vol. 65, no. 3, pp. 764 – 778, 2016.
Search in Google Scholar Back to article
R. Cavoretto, S. De Marchi, A. De Rossi, E. Perracchione, and G. Santin, Partition of unity interpolation using stable kernel-based techniques, Applied Numerical Mathematics, vol. 116, pp. 95–107, 2017.
Search in Google Scholar Back to article
W. Erb, Semi-supervised learning on graphs with feature-augmented graph basis functions, arXiv:2003.07646, 2020.
Search in Google Scholar Back to article
J. P. Ward, F. J. Narcowich, and J. D. Ward, Interpolating splines on graphs for data science applications, Applied and Computational Harmonic Analysis, vol. 49, no. 2, pp. 540–577, 2020.
Search in Google Scholar Back to article
R. Kondor and J. D. Lafferty, Diffusion kernels on graphs and other discrete input spaces, in Proc. of the 19th. International Conference on Machine Learning, ICML02, 2002.
Search in Google Scholar Back to article
R. K. A.J. Smola, Kernels and regularization on graphs, in Lecture Notes in Computer Science(), vol 2777, Springer, Berlin, Heidelberg, 2003.
Search in Google Scholar Back to article
L. Stankovic, M. Dakovic, and E. Sejdic, Introduction to Graph Signal Processing, pp. 3–108. Cham: Springer International Publishing, 2019.
Search in Google Scholar Back to article
C. Godsil and G. Royle, Algebraic Graph Theory. Springer, 2001.
Search in Google Scholar Back to article
F. Chung, Spectral Graph Theory. American Mathematical Society, 1997.
Search in Google Scholar Back to article
W. Erb, Shapes of uncertainty in spectral graph theory, IEEE Transactions on Information Theory, vol. 67, pp. 1291–1307, 2019.
Search in Google Scholar Back to article
G. Fasshauer, Positive definite kernels: Past, present and future, Dolomites Research Notes on Approximation, vol. 4, pp. 21–63, 2011.
Search in Google Scholar Back to article
R. A. Horn and C. R. Johnson, Matrix Analysis. Cambridge University Press, 1985.
Search in Google Scholar Back to article
S. De Marchi and R. Schaback, Stability of kernel-based interpolation, Advances in Computational Mathematics, vol. 32, no. 2, pp. 155–161, 2010.
Search in Google Scholar Back to article
I. Pesenson, Variational splines and Paley–Wiener spaces on combinatorial graphs, Constructive Approximation, vol. 29, pp. 1–21, 2009.
Search in Google Scholar Back to article
M. Newman, Networks: An Introduction. Oxford University Press, 2010.
Search in Google Scholar Back to article
T. F. Gonzalez, Clustering to minimize the maximum intercluster distance, Theoretical Computer Science — Journal, vol. 38, pp. 293–306, 1985.
Search in Google Scholar Back to article
D. S. Hochbaum and D. B. Shmoys, A best possible heuristic for the k-center problem, Mathematics of Operations Research, vol. 10, no. 2, pp. 180–184, 1985.
Search in Google Scholar Back to article
S. Fortunato, Community detection in graphs, Physics Reports, vol. 486, pp. 75–174, 2010.
Search in Google Scholar Back to article
R. Cavoretto, A. De Rossi, and W. Erb, GBFPUM - a MATLAB package for partition of unity based signal interpolation and approximation on graphs, Dolomites Research Notes on Approximation, vol. 15, no. 2, pp. 25–34, 2022.
Search in Google Scholar Back to article
R. Rossi and N. Ahmed, The network data repository with interactive graph analytics and visualization, Proceedings of the AAAI Conference on Artificial Intelligence, vol. 29, Mar. 2015.
Search in Google Scholar Back to article

Exploration of Kernel Parameters in Signal GBF-PUM Approximation on Graphs

Abstract

Paradigm

My account