|
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. Introduction Graph signal processing (GSP) is an emerging field in data science, and it has received much attention in many fields, such as classifying cancer types, temporal brain data, theoretical chemistry, social network analysis, computer networks (such as the Internet) and distributed systems, etc. Analyzing graph signal data will help us understand the behavior patterns in the network, which is crucial in several application areas, including sensor network data, processing and analysis of biological data, and applications of image processing and machine learning [1], etc. Many powerful tools have been proposed for studying graph signals, e.g., the graph Fourier transform (GFT) [2], [3], [4], [5], and the windowed graph Fourier transform (WGFT) [6], [7]. However, these methods can not capture local relationships of graph signals well and fail to identify abrupt signal changes. Due to its multiresolution advantages, the spectral graph wavelet transforms (SGWT) proposed by Hammond et al. [8] and Shuman et al. [6], [9], [10] is an improved tool to perform visualization analysis, detect and characterize the attributes of signals, and play an important role in node classifications. For instance, Mohan et al. [11] take the vehicle speed as signals and apply SGWT to detect the occurrence, propagation, and span of destructive events such as traffic congestion, to guide and plan traffic routes. Other applications include community mining [12], visual analysis [13], surface denoising [14], research on manifolds [15], etc. The following entities are involved in the definitions of graphs: V (a set of nodes), E (a set of edges), f (signals defined on nodes), and w (weights defined on edges). A dynamic graph is obtained when any of these four entities change over time [16]. Graphs in many real-world applications are inherently dynamic, such as data-packet traffic on the Internet, disease spreading on social networks, temperature changes in an area, users in e-commerce platforms continuing to interact with new items and connections established in a communication network over time, etc. Because of the time-varying property of dynamic graphs, existing GSP methods are severely hampered, and tools such as GFT, WGFT, and SGWT cannot be directly applied to dynamic graphs. One could use the graph product structure to obtain a static graph. The three well-known graph products are the Kronecker product, the Cartesian product, and the strong product. These methods are useful in studying discrete temporal graphs, where the graph time slices G t have identical nodes and edges, see [8], [13], [17], [18], [19], [20]. Fig. 1 (a), (b) and (c) depict the three graph products using the path graph1 of three nodes as an example. Another method is to perform GFT by expressing the Laplace of the dynamic graph as a tensor, and obtaining the transformed basis function by Tucker decomposition of the tensor [21]. Alternatively, the Laplace operator of the dynamic graph is represented as a discrete second-order derivative in time, and then GFT and SGWT are performed [22]. All these methods are designed to deal with graph signals on sequences of graph slices with the same nodes or topology. Recently, an important attempt was made in [23], where the authors manually added some additional isolated points on graph time slices, to ensure all graph time slices have identical nodes, see Fig. 1 (d) (The dotted line circle is a manually added node). They then connected these graphs by Cartesian product and used SGWT for the visual analysis of signals. However, in real-world applications, this process can be rather expensive and unrealistic, as it not only adds time edges that carry no information (such as on those manually added, isolated nodes) but also needs to change the previous topology connection every time a new graph time slice is added. Another issue is that by adding the extra temporal edges of the same nodes in adjacent graph time slices, the underlying diffusion mechanism changes as if there are self-loops in each graph time slice. To overcome these difficulties and effectively capture the temporal evolution of signals in dynamic graphs, inspired by the attention mechanism introduced by Bahdanau et al. [24] in machine learning for language processing, we propose to add time edges that capture the best information similarity carried by nodes in adjacent graph time slices. We call this way of adding temporal edges the temporal-attention product. As a result, a discrete dynamic graph with T graph time slices (snapshots) { G t , t = 1 , ⋯ , T } is transformed into a static graph G T , which is called a transformed graph. The nested transformed graphs { G t , t = 1 , ⋯ , T } accurately capture both the spatial and temporal structure of the first T discrete dynamic graph snapshots { G t , t = 1 , ⋯ T } , and are also suited for studying the dynamic evolution process of the graph signals. We can define a filtration of σ -algebra { F t , t ≥ 1 } generated by graph signals on { G t , t ≥ 1 } . The transformed graph G t also provides a general mathematical tool for modeling graph signal processes using advanced methods in probability theory (including diffusion and martingale processes, etc.). Furthermore, this new construction is inductive: to construct G t + 1 at each new time step, t + 1 , one only adds temporal edges for nodes between G t and G t + 1 based on the graph structure of G t . The detailed construction of the transformed graphs can be found in section 2. The weighted adjacency matrix W T of the transformed graph is a generic symmetrical block tridiagonal matrix. The block tridiagonal matrix can be found in many applications in the finite difference method [25], [26], discrete Sturm-Liouville operators [27], discrete transport problem simulation and electronic structure calculations [28], [29], [30], random walks and birth-and-death processes [31], [32], scattering theory [33], computational fluid dynamics [34], signal processing [25], [35], [36] and so on. It is convenient to study the spectrum of the transformed graphs since the properties of block tridiagonal matrices have been extensively studied. A widely used direct method is to compute eigenvalues and eigenvectors based on divide-and-conquer [37], [38], [39], [40], [41], [42], or twisted block factorizations [43], [44]. For some special cases, the relationship between tridiagonal matrices and orthogonal polynomials can be used to obtain eigenvalues and eigenvectors [45], [46], [47], [48], [49]. In this paper, we will give some spectral properties of the weighted adjacency matrix of the transformed graph and some recursive formulas for GSP on the transformed graph. SGWT is powerful in our transformed graph G t , enabling spatio-temporal anomaly detection and multi-resolution visual signal analysis. Two real-world datasets are used to show that SGWT coefficients on the transformed graph accurately capture the spatio-temporal dynamic changes of the signals. In one of our applications, we only have multivariate time series. The underlying graph for these time series is unknown prior and can not be constructed preliminarily through the topology of nodes of the graph. In this paper, we explore a deep learning method to learn the graph link weights. More precisely, we apply the graph attention neural network (GAT), a powerful graph neural network that introduces the attention mechanism to refine the convolution process in a generic graph convolutional neural network [50]. This paper is organized as follows: In section 2, we introduce the temporal-attention product on dynamic graphs. In section 3, we give the spectral properties of undirected dynamic graphs. In section 4, we discuss GFT and SGWT on dynamic graphs. In section 5, we introduce the classification method based on SGWT coefficients. In section 6, we analyze two real-world datasets using spectral graph wavelet visualization. We close with a conclusion section. Table 1 lists the notations used in the graph time slice G t and the transformed graph G t . Section snippets The temporal-attention product on dynamic graphs Signal processing on static graphs is an important research topic and has been applied in many tasks over the years. However, most networks are dynamic in real applications, and their structures or properties are constantly changing over time. Possible changes include the insertion and deletion of nodes (objects), insertion and deletion of edges (relationships), and modification of attributes (for example, the node's signal or the weight of the edge). A discrete dynamic graph consists of T Spectral properties for weighted dynamic graph network We consider a discrete undirected dynamic graph network, which is represented by a sequence of graph time slices { G t = ( V t , E t ) , t = 1 , ⋯ , T } with a weighted adjacency matrix W t = ( w ( v , w , t ) ) . The element w ( v , w , t ) ∈ R + is the weight relationship between ( v , t ) and ( w , t ) . In particular, if a ( v , w , t ) = 0 , we have w ( v , w , t ) = 0 . By the temporal-attention product, we have a transformed graph G T = ( E T , V T ) with a weighted adjacency matrix W T = ( w ( v i , v j ) ) . The element w ( v i , v j ) ∈ R + encodes how strong the relationship between v i Signal processing on the dynamic graph We consider a time-dependent graph signal f defined on a discrete dynamic graph network, which is represented by a sequence of time-varying graphs { G t = ( V t , E t ) , t = 1 , ⋯ , T } . The definition of the graph signal is f : ∪ t V t → R . By applying the temporal-attention product, we get the transformed graph G T = ( E T , V T ) with node set V T = { v 1 , ⋯ , v N T # } , and edge set E T . Furthermore, we assume that G T is connected and undirected. Then, we generalize graph Fourier transforms (GFT) and spectral graph wavelet transforms Classification method based on SGWT coefficients SGWT coefficients contain rich information about the graph signal; however, it remains a big challenge to interpret them properly for non-experts. In this section, we will introduce the classification and visualization methods based on SGWT coefficients, mainly based on the literature [23], [54]. Spectral graph wavelet visual analysis on dynamic graphs In this section, we implement SGWT on two real datasets. By classifying nodes based on wavelet coefficients, it is shown that implementing SGWT on the transformed graph can catch abnormal events based on signal changes and accurately find interesting key information. We use Matlab to perform fast SGWT and visualization. In the case study 1, we use two types of signals, and calculating the wavelet coefficients takes 0.762323 and 0.737458 seconds, respectively. In the case study 2, it costs Conclusion In this paper, we propose a new method for modeling spatio-temporal dynamic graphs, by introducing the temporal-attention product, which better reflects the evolution of the signal concerning the surrounding environment over time. Especially, for dynamic networks with topological changes, this connection method fully considers the spatial and temporal topological connections. The newly added temporal edges will not affect the previous spatial graph structures. This method is robust, scalable, References (70) D.I. Shuman et al. Vertex-frequency analysis on graphs Appl. Comput. Harmon. Anal. (2016) D.K. Hammond et al. Wavelets on graphs via spectral graph theory Appl. Comput. Harmon. Anal. (2011) B. Dong et al. Multiscale representation of surfaces by tight wavelet frames with applications to denoising Appl. Comput. Harmon. Anal. (2016) F. Harary et al. Dynamic graph models Math. Comput. Model. (1997) D.E. Petersen et al. Block tridiagonal matrix inversion and fast transmission calculations J. Comput. Phys. (2008) S. Iida et al. Statistical scattering theory, the supersymmetry method and universal conductance fluctuations Ann. Phys. (1990) G. König et al. Computing eigenvectors of block tridiagonal matrices based on twisted block factorizations J. Comput. Appl. Math. (2012) W.N. Gansterer et al. On twisted factorizations of block tridiagonal matrices Proc. Comput. Sci. (2010) A.J. Duran et al. Orthogonal matrix polynomials: zeros and Blumenthal's theorem J. Approx. Theory (1996) R.M. Anderson et al. How will country-based mitigation measures influence the course of the Covid-19 epidemic? Lancet (2020) R.A. Middelburg et al. Covid-19: how to make between-country comparisons Int. J. Infect. Dis. (2020) M. Rafiq et al. University libraries response to Covid-19 pandemic: a developing country perspective J. Acad. Librariansh. (2021) I. Djekic et al. Covid-19 pandemic effects on food safety-multi-country survey study Food Control (2021) H. Zhou et al. Ast-gnn: an attention-based spatio-temporal graph neural network for interaction-aware pedestrian trajectory prediction Neurocomputing (2021) A. Ortega et al. Graph signal processing: overview, challenges, and applications Proc. IEEE (2018) S. Itani et al. A graph signal processing framework for the classification of temporal brain data G. Taubin A signal processing approach to fair surface design A. Agaskar et al. A spectral graph uncertainty principle IEEE Trans. Inf. Theory (2013) A. Sandryhaila et al. Discrete signal processing on graphs: frequency analysis IEEE Trans. Signal Process. (2014) R. Balan et al. The analysis and design of windowed Fourier frame based multiple description source coding schemes IEEE Trans. Inf. Theory (2000) D.I. Shuman et al. The emerging field of signal processing on graphs: extending high-dimensional data analysis to networks and other irregular domains IEEE Signal Process. Mag. (2013) D.I. Shuman et al. Spectrum-adapted tight graph wavelet and vertex-frequency frames IEEE Trans. Signal Process. (2015) D.M. Mohan et al. Wavelets on graphs with application to transportation networks N. Tremblay et al. Graph wavelets for multiscale community mining IEEE Trans. Signal Process. (2014) P. Valdivia et al. Wavelet-based visualization of time-varying data on graphs G.W. Yu et al. Tight framelets and fast framelet transforms on manifolds Appl. Comput. Harmon. Anal. (2016) S. Moreno et al. Tied Kronecker product graph models to capture variance in network populations S.I. Moreno et al. Learning mixed Kronecker product graph models with simulated method of moments A. Sandryhaila et al. Big data analysis with signal processing on graphs: representation and processing of massive data sets with irregular structure IEEE Signal Process. Mag. (2014) A.D. Col et al. Wavelet-based visual analysis for data exploration Comput. Sci. Eng. (2017) M. Villafañe-Delgado et al. Dynamic graph Fourier transform on temporal functional connectivity networks F. Grassi et al. Tracking time-vertex propagation using dynamic graph wavelets A. Dal Col et al. Wavelet-based visual analysis of dynamic networks IEEE Trans. Vis. Comput. Graph. (2017) D. Bahdanau et al. End-to-end attention-based large vocabulary speech recognition A. Asif et al. Data assimilation in large time-varying multidimensional fields IEEE Trans. Image Process. (1999) View more references Cited by (0) Recommended articles (6) Research article Worst case tractability of linear problems in the presence of noise: Linear information Journal of Complexity, Volume 79, 2023, Article 101782 Show abstract We study the worst case tractability of multivariate linear problems defined on separable Hilbert spaces. Information about a problem instance consists of noisy evaluations of arbitrary bounded linear functionals, where the noise is either deterministic or random. The cost of a single evaluation depends on its precision and is controlled by a cost function. We establish mutual interactions between tractability of a problem with noisy information, the cost function, and tractability of the same problem, but with exact information. Research article Modewise operators, the tensor restricted isometry property, and low-rank tensor recovery Applied and Computational Harmonic Analysis, Volume 66, 2023, pp. 161-192 Show abstract Recovery of sparse vectors and low-rank matrices from a small number of linear measurements is well-known to be possible under various model assumptions on the measurements. The key requirement on the measurement matrices is typically the restricted isometry property, that is, approximate orthonormality when acting on the subspace to be recovered. Among the most widely used random matrix measurement models are (a) independent subgaussian models and (b) randomized Fourier-based models, allowing for the efficient computation of the measurements. For the now ubiquitous tensor data, direct application of the known recovery algorithms to the vectorized or matricized tensor is memory-heavy because of the huge measurement matrices to be constructed and stored. In this paper, we propose modewise measurement schemes based on subgaussian and randomized Fourier measurements. These modewise operators act on the pairs or other small subsets of the tensor modes separately. They require significantly less memory than the measurements working on the vectorized tensor, provably satisfy the tensor restricted isometry property and experimentally can recover the tensor data from fewer measurements and do not require impractical storage. Research article Riesz transform associated with the fractional Fourier transform and applications in image edge detection Applied and Computational Harmonic Analysis, Volume 66, 2023, pp. 211-235 Show abstract The fractional Hilbert transform was introduced by Zayed [30, Zayed, 1998] and has been widely used in signal processing. In view of its connection with the fractional Fourier transform, Chen, the first, second and fourth authors of this paper in [6, Chen et al., 2021] studied the fractional Hilbert transform and other fractional multiplier operators on the real line. The present paper is concerned with a natural extension of the fractional Hilbert transform to higher dimensions: this extension is the fractional Riesz transform and is given by multiplication which a suitable chirp function on the fractional Fourier transform side. In addition to a thorough study of the fractional Riesz transform, in this work we also investigate the boundedness of singular integral operators with chirp functions on rotation invariant spaces, chirp Hardy spaces and their relation to chirp BMO spaces, as well as applications of the theory of fractional multipliers in partial differential equations. Through numerical simulation, we provide physical and geometric interpretations of high-dimensional fractional multipliers. Finally, we present an application of the fractional Riesz transforms in edge detection which verifies a hypothesis insinuated in [26, Xu et al., 2016] . In fact our numerical implementation confirms that amplitude, phase, and direction information can be simultaneously extracted by controlling the order of the fractional Riesz transform. Research article A progressive learning classifier based on dynamic differential weighted network for feature identification of brain network series Knowledge-Based Systems, Volume 274, 2023, Article 110661 Show abstract A great effort has been dedicated to investigating resting-state functional connectivity (rs-FC). Recent evidence insinuates that dynamic functional connectivity (dFC) may be a more sensitive marker than rs-FC. Although electroencephalography (EEG) with millisecond temporal resolution has the potential to capture the dynamic evolutionary patterns of the human brain, EEG-based dynamic functional connectivity has not been sufficiently studied. Thus, we propose a progressive learning classifier based on dynamic differential weighted networks (PLC-DWN) to identify EEG-based dynamic functional brain networks efficiently. In PLC-DWN, dynamic differential weighted brain networks are first constructed to capture the temporal evolutionary properties of brain network series more efficiently. Furthermore, a Laplacian network embedding and mapping method is proposed in PLC-DWN to automatically extract the gradient features of eigen sub-networks in a brain network via local attribute embedding and global gradient mapping. Compared with the mainstream graph theoretical analysis, the gradient features extracted automatically can more comprehensively depict the dynamic connection information. To identify time-variant gradient features accurately, a progressive learning classifier developed in PLC-DWN progressively intensifies its performance via concise extreme learning machines (ELMs) and a self-adapting learning structure. The PLC-DWN has simultaneously been applied to epilepsy prediction and emotion recognition tasks involving nearly 943 h of EEG signals from 66 subjects. Exhaustive experiments demonstrate that PLC-DWN outperforms state-of-the-art methods in terms of accuracy, sensitivity, and specificity. Furthermore, multiple comparative models were constructed to verify the effectiveness of each innovative module within PLC-DWN. Research article Graph filter design by ring-decomposition for 2-connected graphs Signal Processing, Volume 201, 2022, Article 108725 Show abstract The graph filter is an essential part of graph signal processing. And the design of filters is booming in various applications. However, most previous works on graph filter design consider the entire graph as their object and concentrate on global processing. That causes less efficiency and little attention to some detailed information hidden in graph signals. This paper proposes a framework to design graph filters, named Ring-Decomposition-based Filter (RDF), on 2-connected graphs constructed from a ring by adding paths. The approach designs ring filters to capture small-scale features after decomposing the given graph into a set of rings. Experimental results show that the proposed graph filters outperform the baselines on synthetic and real-world graph signals for denoising and outlier detection tasks. In addition, a computational cost analysis is given to illustrate the efficiency of the proposed graph filters. Research article Approximating the span of principal components via iterative least-squares Applied and Computational Harmonic Analysis, Volume 63, 2023, pp. 84-92 Show abstract Over of the last century, Principal Component Analysis (PCA) has become one of the pillars of modern scientific methods. Although PCA is typically viewed as a statistical tool aiming at finding orthogonal directions on which the variance is maximized, its first introduction by Pearson at 1901 was in the framework of the non-linear least-squares minimization problem of fitting a plane to scattered data points. Since linear least-squares regression also fits a plane to scattered data points, PCA and linear least-squares regression have thus a natural kinship, which we explore in this paper. In particular, we present an iterated linear least-squares approach, yielding a sequence of subspaces that converges to the space spanned by the leading principal components. The key observation, by which we establish our result, is that each iteration of the Power (or Subspace) Iterations, applied to the covariance matrix, can be interpreted as a solution to a linear least-squares problem. ☆ YX Gao is partially supported by NSFC grants ( 11871140 , 12071065 ) and National Key R&D Program of China ( 2020YFA0714102 ). HK Zhang is partially supported by Simons Foundation Collaboration Grants for Mathematicians ( 706383 ). J Zu is partially supported by NSFC grants ( 11971096 , 11971095 ). View full text © 2023 Elsevier Inc. All rights reserved. About ScienceDirect Remote access Shopping cart Advertise Contact and support Terms and conditions Privacy policy We use cookies to help provide and enhance our service and tailor content and ads. By continuing you agree to the use of cookies . Copyright © 2023 Elsevier B.V. or its licensors or contributors. ScienceDirect® is a registered trademark of Elsevier B.V. ScienceDirect® is a registered trademark of Elsevier B.V.
|
