Artificial Intelligence and Quantum Computing for Advanced Wireless Networks. Savo G. Glisic
Читать онлайн книгу.
(5): The statement about Lsym follows from (1), and then the statement about Lrw follows from (2).
Appendix 5.B Graph Fourier Transform
Graph signals: A graph signal is a collection of values defined on a complex and irregular structure modeled as a graph. In this appendix, a graph is represented as
N‐dimensional vector f = [f(1), f(2), …, f(N)]T ∈ ℂN, where f(i) is the value of the graph signal at node i and
Directed Laplacian: As discussed in Appendix 5.A, the graph Laplacian for undirected graphs is a symmetric difference operator L=D − W, where D is the degree matrix of the graph, and W is the weight matrix of the graph. In the case of directed graphs (or digraphs), the weight matrix W of a graph is not symmetric. In addition, the degree of a vertex can be defined in two ways: in‐degree and out‐degree. The in‐degree of a node i is estimated as
(5.B.1)
where Din= diag
Figure 5.B.1 A directed graph and the corresponding matrices.
Graph Fourier transform based on directed Laplacian: Using Jordan decomposition, the graph Laplacian is decomposed as
where J, known as the Jordan matrix, is a block diagonal matrix similar to L, and the Jordan eigenvectors of L constitute the columns of V. We define the graph Fourier transform (GFT) of a graph signal f as
(5.B.3)
Here, V is treated as the graph Fourier matrix whose columns constitute the graph Fourier basis. The inverse graph Fourier transform can be calculated as
(5.B.4)
In this definition of GFT, the eigenvalues of the graph Laplacian act as the graph frequencies, and the corresponding Jordan eigenvectors act as the graph harmonics. The eigenvalues with a small absolute value correspond to low frequencies and vice versa. Before discussing the ordering of frequencies, we consider a special case when the Laplacian matrix is diagonalizable.
Diagonalizable Laplacian matrix: When the graph Laplacian is diagonalizable, Eq. (5.B.2) is reduced to
(5.B.5)
Here, Λ ∈ ℂN × N is a diagonal matrix containing the eigenvalues λ0, λ1 , …, λN − 1 of L, and V = [v0, v1, …, vN − 1] ∈ ℂN × N is the matrix with columns as the corresponding eigenvectors of L. Note that for a graph with real non‐negative edge weights, the graph spectrum will lie in the right half of the complex frequency plane (including the imaginary axis).
Undirected graphs: For an undirected graph with real weights, the graph Laplacian matrix L is real and symmetric. As a result, the eigenvalues of L turn out to be real, and L constitutes orthonormal set of eigenvectors. Hence, the Jordan form of the Laplacian matrix for undirected graphs can be written as
(5.B.6)
where VT = V−1, because the eigenvectors of L are orthogonal in th undirected case. Consequently, the GFT of a signal f can be given as
References
1 1 Scarselli, F., Gori, M., Tsoi, A.C. et al. (2009). The graph neural network model. IEEE Trans. Neural Netw. 20 (1): 61–80.
2 2 Khamsi, M.A. and Kirk, W.A. (2011). An Introduction to Metric Spaces and Fixed Point Theory, vol. 53. Wiley.
3 3 M. Kampffmeyer, Y. Chen, X. Liang, H. Wang, Y. Zhang, and E. P. Xing, “Rethinking knowledge graph propagation for zero‐shot learning,” arXiv preprint arXiv:1805.11724, 2018.
4 4 Y. Zhang, Y. Xiong, X. Kong, S. Li, J. Mi, and Y. Zhu, “Deep collective classification in heterogeneous information networks,” in WWW 2018, 2018, pp. 399–408.
5 5 X. Wang, H. Ji, C. Shi, B. Wang, Y. Ye, P. Cui, and P. S. Yu, “Heterogeneous graph attention network,” WWW 2019, 2019.
6 6 D. Beck, G. Haffari, and T. Cohn, “Graph‐to‐sequence learning using gated graph neural networks,” in ACL 2018, 2018, pp. 273–283.
7 7 M. Schlichtkrull, T. N. Kipf, P. Bloem, R. van den Berg, I. Titov, and M. Welling, “Modeling relational data with graph convolutional networks,” in ESWC 2018. Springer, 2018, pp. 593–607
8 8 Y. Li, R. Yu, C. Shahabi, and Y. Liu, “Diffusion convolutional recurrent neural network: Data‐driven traffic forecasting,” arXiv preprint arXiv:1707.01926, 2017.
9 9 B. Yu, H. Yin, and Z. Zhu, “Spatio‐temporal graph convolutional networks: A deep learning framework for traffic forecasting,” arXiv preprint arXiv:1709.04875, 2017. 20
10 10 A. Jain, A. R. Zamir, S. Savarese, and A. Saxena, “Structural‐rnn: Deep learning on spatio‐temporal graphs,” in CVPR 2016, 2016, pp. 5308–5317.
11 11 S. Yan, Y. Xiong, and D. Lin, “Spatial temporal