Graph signal processing on dynamic graphs based on temporal-attention product. (English) Zbl 1521.94012
Summary: Signal processing is an important research topic. This paper aims to provide a general framework for signal processing on arbitrary dynamic graphs. We propose a new graph transformation by defining a temporal-attention product. This product transforms the sequence of graph time slices with arbitrary topology and number of nodes into a static graph, effectively capturing graph signals’ spatio-temporal dynamic evolution process. The temporal-attention product graph provides a solid mathematical foundation to model the time-dependent graph signal processes as martingales. The weighted adjacency matrix obtained by temporal-attention products is a block tridiagonal matrix, which has been extensively studied. Therefore, it is general and convenient to perform graph signal processing on this new static graph. We apply two real datasets to illustrate the effectiveness of spectral graph wavelet transform based on temporal-attention product. For one of the datasets with no graph structure, we learn the graph weights through a neural network.
MSC:
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
| 05C90 | Applications of graph theory |
| 42A38 | Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type |
| 42C40 | Nontrigonometric harmonic analysis involving wavelets and other special systems |
Keywords:
time-varying data; signal processing; spectral graph wavelet transform; visual analysis; graph Fourier transform; graph attention neural network; dynamic networksSoftware:
OPQReferences:
| [1] | Ortega, A.; Frossard, P.; Kovačević, J.; Moura, J. M.; Vandergheynst, P., Graph signal processing: overview, challenges, and applications, Proc. IEEE, 106, 5, 808-828 (2018) |
| [2] | Itani, S.; Thanou, D., A graph signal processing framework for the classification of temporal brain data, (2020 28th European Signal Processing Conference (2021), IEEE), 1180-1184 |
| [3] | Taubin, G., A signal processing approach to fair surface design, (Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques (1995)), 351-358 |
| [4] | Agaskar, A.; Lu, Y. M., A spectral graph uncertainty principle, IEEE Trans. Inf. Theory, 59, 7, 4338-4356 (2013) · Zbl 1364.94103 |
| [5] | Sandryhaila, A.; Moura, J. M., Discrete signal processing on graphs: frequency analysis, IEEE Trans. Signal Process., 62, 12, 3042-3054 (2014) · Zbl 1394.94498 |
| [6] | Shuman, D. I.; Ricaud, B.; Vandergheynst, P., Vertex-frequency analysis on graphs, Appl. Comput. Harmon. Anal., 40, 2, 260-291 (2016) · Zbl 1403.94031 |
| [7] | Balan, R.; Daubechies, I.; Vaishampayan, V., The analysis and design of windowed Fourier frame based multiple description source coding schemes, IEEE Trans. Inf. Theory, 46, 7, 2491-2536 (2000) · Zbl 0998.94011 |
| [8] | Hammond, D. K.; Vandergheynst, P.; Gribonval, R., Wavelets on graphs via spectral graph theory, Appl. Comput. Harmon. Anal., 30, 2, 129-150 (2011) · Zbl 1213.42091 |
| [9] | Shuman, D. I.; Narang, S. K.; Frossard, P.; Ortega, A.; Vandergheynst, P., The emerging field of signal processing on graphs: extending high-dimensional data analysis to networks and other irregular domains, IEEE Signal Process. Mag., 30, 3, 83-98 (2013) |
| [10] | Shuman, D. I.; Wiesmeyr, C.; Holighaus, N.; Vandergheynst, P., Spectrum-adapted tight graph wavelet and vertex-frequency frames, IEEE Trans. Signal Process., 63, 16, 4223-4235 (2015) · Zbl 1394.94540 |
| [11] | Mohan, D. M.; Asif, M. T.; Mitrovic, N.; Dauwels, J.; Jaillet, P., Wavelets on graphs with application to transportation networks, (17th International IEEE Conference on Intelligent Transportation Systems (2014), IEEE), 1707-1712 |
| [12] | Tremblay, N.; Borgnat, P., Graph wavelets for multiscale community mining, IEEE Trans. Signal Process., 62, 20, 5227-5239 (2014) · Zbl 1394.94602 |
| [13] | Valdivia, P.; Dias, F.; Petronetto, F.; Silva, C. T.; Nonato, L. G., Wavelet-based visualization of time-varying data on graphs, (2015 IEEE Conference on Visual Analytics Science and Technology (2015), IEEE), 1-8 |
| [14] | Dong, B.; Jiang, Q.; Liu, C.; Shen, Z., Multiscale representation of surfaces by tight wavelet frames with applications to denoising, Appl. Comput. Harmon. Anal., 41, 2, 561-589 (2016) · Zbl 1346.42039 |
| [15] | Yu, G. W.; Zhuang, X., Tight framelets and fast framelet transforms on manifolds, Appl. Comput. Harmon. Anal., 48, 1, 64-95 (2016) · Zbl 1447.42033 |
| [16] | Harary, F.; Gupta, G., Dynamic graph models, Math. Comput. Model., 25, 7, 79-87 (1997) · Zbl 0879.68085 |
| [17] | Moreno, S.; Kirshner, S.; Neville, J.; Vishwanathan, S., Tied Kronecker product graph models to capture variance in network populations, (2010 48th Annual Allerton Conference on Communication, Control, and Computing (2010), IEEE), 1137-1144 |
| [18] | Moreno, S. I.; Neville, J.; Kirshner, S., Learning mixed Kronecker product graph models with simulated method of moments, (Acm Sigkdd International Conference on Knowledge Discovery and Data Mining (2013)), 1052-1060 |
| [19] | Sandryhaila, A.; Moura, J. M., Big data analysis with signal processing on graphs: representation and processing of massive data sets with irregular structure, IEEE Signal Process. Mag., 31, 5, 80-90 (2014) |
| [20] | Col, A. D.; Valdivia, P.; Petronetto, F.; Dias, F.; Silva, C. T.; Nonato, L. G., Wavelet-based visual analysis for data exploration, Comput. Sci. Eng., 19, 5, 85-91 (2017) |
| [21] | Villafañe-Delgado, M.; Aviyente, S., Dynamic graph Fourier transform on temporal functional connectivity networks, (2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (2017), IEEE), 949-953 |
| [22] | Grassi, F.; Perraudin, N.; Ricaud, B., Tracking time-vertex propagation using dynamic graph wavelets, (2016 IEEE Global Conference on Signal and Information Processing (GlobalSIP) (2016), IEEE), 351-355 |
| [23] | Dal Col, A.; Valdivia, P.; Petronetto, F.; Dias, F.; Silva, C. T.; Nonato, L. G., Wavelet-based visual analysis of dynamic networks, IEEE Trans. Vis. Comput. Graph., 24, 8, 2456-2469 (2017) |
| [24] | Bahdanau, D.; Chorowski, J.; Serdyuk, D.; Brakel, P.; Bengio, Y., End-to-end attention-based large vocabulary speech recognition, (2016 IEEE International Conference on Acoustics, Speech and Signal Processing (2016), IEEE), 4945-4949 |
| [25] | Asif, A.; Moura, J. M., Data assimilation in large time-varying multidimensional fields, IEEE Trans. Image Process., 8, 11, 1593-1607 (1999) |
| [26] | Galligani, E.; Ruggiero, V., A polynomial preconditioner for block tridiagonal matrices, Parallel Algorithms Appl., 3, 3-4, 227-237 (1994) · Zbl 1049.68957 |
| [27] | Braeutigam, I.; Polyakov, D. M., Asymptotics of eigenvalues of infinite block matrices, Ufa Math. J., 11, 3, 11-28 (2019) · Zbl 1463.47059 |
| [28] | Casati, G.; Guarneri, I.; Izrailev, F. M.; Molinari, L.; Życzkowski, K., Periodic band random matrices, curvature, and conductance in disordered media, Phys. Rev. Lett., 72, 17, 2697 (1994) |
| [29] | Kramer, B.; MacKinnon, A., Localization: theory and experiment, Rep. Prog. Phys., 56, 12, 1469 (1993) |
| [30] | Petersen, D. E.; Sørensen, H. H.B.; Hansen, P. C.; Skelboe, S.; Stokbro, K., Block tridiagonal matrix inversion and fast transmission calculations, J. Comput. Phys., 227, 6, 3174-3190 (2008) · Zbl 1135.65318 |
| [31] | Dette, H.; Reuther, B.; Studden, W.; Zygmunt, M., Matrix measures and random walks with a block tridiagonal transition matrix, SIAM J. Matrix Anal. Appl., 29, 1, 117-142 (2007) · Zbl 1133.60339 |
| [32] | Grünbaum, F. A., The Karlin-Mcgregor formula for a variant of a discrete version of Walsh’s spider, J. Phys. A, Math. Theor., 42, 45, Article 454010 pp. (2009) · Zbl 1187.37094 |
| [33] | Iida, S.; Weidenmüller, H.; Zuk, J., Statistical scattering theory, the supersymmetry method and universal conductance fluctuations, Ann. Phys., 200, 2, 219-270 (1990) |
| [34] | Anderson, J. D.; Wendt, J., Computational Fluid Dynamics, vol. 206 (1995), Springer · Zbl 0834.76002 |
| [35] | Kavcic, A.; Moura, J. M., Matrices with banded inverses: inversion algorithms and factorization of Gauss-Markov processes, IEEE Trans. Inf. Theory, 46, 4, 1495-1509 (2000) · Zbl 0998.65037 |
| [36] | Moura, J. M.; Balram, N., Recursive structure of noncausal Gauss-Markov random fields, IEEE Trans. Inf. Theory, 38, 2, 334-354 (1992) · Zbl 0742.60051 |
| [37] | Gansterer, W. N.; Ward, R. C.; Muller, R. P., An extension of the divide-and-conquer method for a class of symmetric block-tridiagonal eigenproblems, ACM Trans. Math. Softw., 28, 1, 45-58 (2002) · Zbl 1072.65050 |
| [38] | Bai, Y.; Gansterer, W. N.; Ward, R. C., Block tridiagonalization of ‘effectively’ sparse symmetric matrices, ACM Trans. Math. Softw., 30, 3, 326-352 (2004) · Zbl 1073.65027 |
| [39] | Gansterer, W. N.; Ward, R. C.; Muller, R. P.; Goddard, W. A., Computing approximate eigenpairs of symmetric block tridiagonal matrices, SIAM J. Sci. Comput., 25, 1, 65-85 (2003) · Zbl 1038.65031 |
| [40] | Gansterer, W. N., Computing orthogonal decompositions of block tridiagonal or banded matrices, (International Conference on Computational Science (2005), Springer), 25-32 · Zbl 1129.65311 |
| [41] | Gansterer, W. N.; Zottl, J., Parallelization of divide-and-conquer eigenvector accumulation, (European Conference on Parallel Processing (2005), Springer), 847-856 |
| [42] | Bai, Y.; Ward, R. C., A parallel symmetric block-tridiagonal divide-and-conquer algorithm, ACM Trans. Math. Softw., 33, 4, Article 25-es (2007) · Zbl 1365.65090 |
| [43] | König, G.; Moldaschl, M.; Gansterer, W. N., Computing eigenvectors of block tridiagonal matrices based on twisted block factorizations, J. Comput. Appl. Math., 236, 15, 3696-3703 (2012) · Zbl 1245.65044 |
| [44] | Gansterer, W. N.; König, G., On twisted factorizations of block tridiagonal matrices, Proc. Comput. Sci., 1, 1, 279-287 (2010) |
| [45] | Askey, R., Orthogonal Polynomials and Special Functions (1975), SIAM · Zbl 0298.26010 |
| [46] | Gautschi, W., Orthogonal Polynomials: Computation and Approximation (2004), OUP: OUP Oxford · Zbl 1130.42300 |
| [47] | Sandryhaila, A.; Kovacevic, J.; Puschel, M., Algebraic signal processing theory: 1-d nearest neighbor models, IEEE Trans. Signal Process., 60, 5, 2247-2259 (2012) · Zbl 1393.94423 |
| [48] | Duran, A. J.; Lopez-Rodriguez, P., Orthogonal matrix polynomials: zeros and Blumenthal’s theorem, J. Approx. Theory, 84, 1, 96-118 (1996) · Zbl 0861.42016 |
| [49] | Sandryhaila, A.; Moura, J. M., Eigendecomposition of block tridiagonal matrices (2013), arXiv preprint |
| [50] | Veličković, P.; Cucurull, G.; Casanova, A.; Romero, A.; Lio, P.; Bengio, Y., Graph attention networks, (International Conference on Learning Representations (2018)) |
| [51] | Yueh, W.-C., Eigenvalues of several tridiagonal matrices, Appl. Math. E-Notes [electronic only], 5, 66-74 (2005) · Zbl 1068.15006 |
| [52] | Laub, A. J., Matrix Analysis for Scientists and Engineers, vol. 91 (2005), SIAM · Zbl 1077.15001 |
| [53] | Gansterer, W. N.; Bai, Y.; Day, R. M.; Ward, R. C., Framework for approximating eigenpairs in electronic structure computations, Comput. Sci. Eng., 6, 5, 50-59 (2004) |
| [54] | Geng, R.; Gao, Y.; Zhang, H.; Zu, J., Analysis of the spatio-temporal dynamics of Covid-19 in Massachusetts via spectral graph wavelet theory, IEEE Trans. Signal Inf. Process. Netw. (2022) |
| [55] | Müller, A. C.; Guido, S., Introduction to Machine Learning with Python: a Guide for Data Scientists (2016), O’Reilly Media, Inc. |
| [56] | Yao, H.; Jiang, C.; Qian, Y., Developing Networks Using Artificial Intelligence (2019), Springer |
| [57] | Sharpnack, J. L.; Krishnamurthy, A.; Singh, A., Near-optimal anomaly detection in graphs using Lovasz extended scan statistic, Adv. Neural Inf. Process. Syst., 26 (2013) |
| [58] | Sricharan, K.; Das, K., Localizing anomalous changes in time-evolving graphs, (Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (2014)), 1347-1358 |
| [59] | Génois, M.; Barrat, A., Can co-location be used as a proxy for face-to-face contacts?, EPJ Data Sci., 7, 1, Article 11 pp. (2018) |
| [60] | Anderson, R. M.; Heesterbeek, H.; Klinkenberg, D.; Hollingsworth, T. D., How will country-based mitigation measures influence the course of the Covid-19 epidemic?, Lancet, 395, 10228, 931-934 (2020) |
| [61] | Middelburg, R. A.; Rosendaal, F. R., Covid-19: how to make between-country comparisons, Int. J. Infect. Dis., 96, 477-481 (2020) |
| [62] | Balmford, B.; Annan, J. D.; Hargreaves, J. C.; Altoè, M.; Bateman, I. J., Cross-country comparisons of Covid-19: policy, politics and the price of life, Environ. Resour. Econ., 76, 4, 525-551 (2020) |
| [63] | Rafiq, M.; Batool, S. H.; Ali, A. F.; Ullah, M., University libraries response to Covid-19 pandemic: a developing country perspective, J. Acad. Librariansh., 47, 1, Article 102280 pp. (2021) |
| [64] | Tarkar, P., Impact of Covid-19 pandemic on education system, Int. J. Adv. Sci. Technol., 29, 9, 3812-3814 (2020) |
| [65] | Phan, D. H.B.; Narayan, P. K., Country responses and the reaction of the stock market to Covid-19—a preliminary exposition, Emerg. Mark. Finance Trade, 56, 10, 2138-2150 (2020) |
| [66] | Djekic, I.; Nikolić, A.; Uzunović, M.; Marijke, A.; Liu, A.; Han, J.; Brnčić, M.; Knežević, N.; Papademas, P.; Lemoniati, K., Covid-19 pandemic effects on food safety-multi-country survey study, Food Control, 122, Article 107800 pp. (2021) |
| [67] | Gu, W.; Gao, F.; Lou, X.; Zhang, J., Link prediction via graph attention network (2019), arXiv preprint |
| [68] | Tang, C.; Sun, J.; Sun, Y.; Peng, M.; Gan, N., A general traffic flow prediction approach based on spatial-temporal graph attention, IEEE Access, 8, 153731-153741 (2020) |
| [69] | Zhou, H.; Ren, D.; Xia, H.; Fan, M.; Yang, X.; Huang, H., Ast-gnn: an attention-based spatio-temporal graph neural network for interaction-aware pedestrian trajectory prediction, Neurocomputing, 445, 298-308 (2021) |
| [70] | Zhang, Z.; Huang, J.; Tan, Q., Sr-hgat: symmetric relations based heterogeneous graph attention network, IEEE Access, 8, 165631-165645 (2020) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
