Mohamed Seif, profile picture
Uploaded byMohamed Seif
1,851 views

Big Data Analysis with Signal Processing on Graphs

This document discusses signal processing on graphs and big data analysis using graph theory concepts. It begins with introducing fundamental graph theory terms like nodes, edges, and adjacency matrices. It then explains how to define graph signals and how signal processing concepts like shifting, filtering, and Fourier transforms can be generalized to graphs. In particular, it describes how the graph shift replaces time shifts, graph filters are polynomials of the graph shift matrix, and the graph Fourier transform uses the eigenvectors of the graph shift matrix as the basis. The document concludes by discussing how eigenvalues represent frequencies on graphs and how filters affect the frequency content of graph signals.

Downloaded 88 times
Big Data Talks Nile University Talk 8 Big Data Analysis with Signal Processing on Graphs Introduction Fundamentals of Graph Theory DSP on Graphs Graph Products Applications Mohamed Seif m.seif@nu.edu.eg 8-1
Contents Introduction Fundamentals of Graph Theory DSP on Graphs Graph Products Applications Big Data Analysis with Signal Processing on Graphs 8-2
Introduction How to relate the Signal Processing Definitions with Graphs? Big Data Analysis with Signal Processing on Graphs 8-3
Introduction How to relate the Signal Processing Definitions with Graphs? Big Data Analysis with Signal Processing on Graphs 8-4
Contents Introduction Fundamentals of Graph Theory DSP on Graphs Graph Products Applications Big Data Analysis with Signal Processing on Graphs 8-5
What Is Graph? In graph theory, the graph G is defined as a tuple G = (V, E) where V = {v0, v1, . . . , vN−1} is the set of N nodes and E = {eij, ∀(i, j) ∈ {0, 1, . . . , N − 1}} is the set containing all links between the nodes. Example: V = {1, 2, 3, 4} E = {{1, 2}, {2, 3}, {3, 4}, {4, 1}} 1 2 3 4 Big Data Analysis with Signal Processing on Graphs 8-6
What Is Graph? In graph theory, the graph G is defined as a tuple G = (V, E) where V = {v0, v1, . . . , vN−1} is the set of N nodes and E = {eij, ∀(i, j) ∈ {0, 1, . . . , N − 1}} is the set containing all links between the nodes. Example: V = {1, 2, 3, 4} E = {{1, 2}, {2, 3}, {3, 4}, {4, 1}} 1 2 3 4 Big Data Analysis with Signal Processing on Graphs 8-7
What Is Graph? (cont’d) In graph theory, the graph G is defined as a tuple G = (V, E) where V = {v0, v1, . . . , vN−1} is the set of N nodes and E = {eij, ∀(i, j) ∈ {0, 1, . . . , N − 1}} is the set containing all links between the nodes. Big Data Analysis with Signal Processing on Graphs 8-8
What Is Graph? In graph theory, the graph G is defined as a tuple G = (V, E) where V = {v0, v1, . . . , vN−1} is the set of N nodes and E = {eij, ∀(i, j) ∈ {0, 1, . . . , N − 1}} is the set containing all links between the nodes. Big Data Analysis with Signal Processing on Graphs 8-9
Alternative Representation of Graphs 1. Adjacency matrix AN×N , defined as Ai,j =    1 if vi & vj are connected 0 o.w. 2. Laplacian graph LN×N , defined as L = D − A, where D is the degree matrix Li,j =    deg(vi) if i = j −1 if i = j & vi is adjacent to vj 0 o.w. Big Data Analysis with Signal Processing on Graphs 8-10
Contents Introduction Fundamentals of Graph Theory DSP on Graphs Graph Products Applications Big Data Analysis with Signal Processing on Graphs 8-11
Graph Signals Given the graph, the data set forms a graph signal, defined as a map s : V → C, vn → sn (1) It is convenient to write graph signals as vectors s = [s0, s1, . . . , sN−1] T ∈ CN×1 (2) Big Data Analysis with Signal Processing on Graphs 8-12
Graph Shift In DSP, a signal shift, implemented as a time delay ˜s = [ ˜s0, ˜s1, . . . , ˜sN−1] T = Cs (3) where C is the N × N cyclic shift matrix. DSP on Graphs extends the concept of shift to general graphs by defining the graph shift as a local operation that replaces a signal value sn at node vn by a linear combination of the values at neighbors of vn weighted by their edge weights: ˜sn = m∈Nn An,msm (4) Big Data Analysis with Signal Processing on Graphs 8-13
Graph Shift (cont’d) It can be interpreted as a first-order interpolation, weighted averaging, or regression on graphs, which is a widely used operation in graph regression, distributed consensus, telecommunications. Then, the graph shift is written as ˜s = [ ˜s0, ˜s1, . . . , ˜sN−1] T = As (5) Big Data Analysis with Signal Processing on Graphs 8-14
Graph Filters and Z-Transform In signal processing, a filter is a system H(.) that takes an input signal s and outputs a signal: ˜s = [ ˜s0, ˜s1, . . . , ˜sN−1] T = H(s) (6) Among the most widely used filters are linear shift-ivariant (LSI) ones. The z-transform provides a convenient representation for signals and filters in DSP. (In short) An alternative representation for the output signal is given by ˜s = h(C)s (7) where h(c) = N−1 n=0 hnCn (Resultant is a circulant matrix) Big Data Analysis with Signal Processing on Graphs 8-15
Graph Filters and Z-Transform In signal processing, a filter is a system H(.) that takes an input signal s and outputs a signal: ˜s = [ ˜s0, ˜s1, . . . , ˜sN−1] T = H(s) (6) Among the most widely used filters are linear shift-ivariant (LSI) ones. The z-transform provides a convenient representation for signals and filters in DSP. (In short) An alternative representation for the output signal is given by ˜s = h(C)s (7) where h(c) = N−1 n=0 hnCn (Resultant is a circulant matrix) Big Data Analysis with Signal Processing on Graphs 8-16
Graph Filters and Z-Transform In signal processing, a filter is a system H(.) that takes an input signal s and outputs a signal: ˜s = [ ˜s0, ˜s1, . . . , ˜sN−1] T = H(s) (6) Among the most widely used filters are linear shift-ivariant (LSI) ones. The z-transform provides a convenient representation for signals and filters in DSP. (In short) An alternative representation for the output signal is given by ˜s = h(C)s (7) where h(c) = N−1 n=0 hnCn (Resultant is a circulant matrix) Big Data Analysis with Signal Processing on Graphs 8-17
Graph Filters and Z-Transform In signal processing, a filter is a system H(.) that takes an input signal s and outputs a signal: ˜s = [ ˜s0, ˜s1, . . . , ˜sN−1] T = H(s) (6) Among the most widely used filters are linear shift-ivariant (LSI) ones. The z-transform provides a convenient representation for signals and filters in DSP. (In short) An alternative representation for the output signal is given by ˜s = h(C)s (7) where h(c) = N−1 n=0 hnCn (Resultant is a circulant matrix) Big Data Analysis with Signal Processing on Graphs 8-18
Graph Filters and Z-Transform (cont’d) DSP on Graphs extends the concept of filters to general graphs. Similarly to the extension of the time shift to the graph shift, filters are generalized to graph filters as polynomials in the graph shift , and all LSI graph filters have the form h(A) = L−1 l=0 hlAl (8) In analogy with signal filters, the graph filter output is given by ˜s = h(A)s (9) Big Data Analysis with Signal Processing on Graphs 8-19
Graph Fourier Transform Mathematically, a Fourier transform with respect to a set of operators is the expansion of a signal into a basis of the operators eigen functions. Since in signal processing the operators of interest are filters, DSPG defines the Fourier transform with respect to the graph filters. ˜s = [ ˜s0, ˜s1, . . . , ˜sN−1] T = GFT{s} (10) Big Data Analysis with Signal Processing on Graphs 8-20
Graph Fourier Transform Mathematically, a Fourier transform with respect to a set of operators is the expansion of a signal into a basis of the operators eigen functions. Since in signal processing the operators of interest are filters, DSPG defines the Fourier transform with respect to the graph filters. ˜s = [ ˜s0, ˜s1, . . . , ˜sN−1] T = GFT{s} (10) Big Data Analysis with Signal Processing on Graphs 8-21
Graph Fourier Transform (cont’d) For simplicity, assume that A is diagonalizable and its decomposition is A = V ΛV −1 (11) where the columns vn of the matrix V = [v0 · · · vN−1] ∈ CN×N are the eigenvectors of A and Λ = diag(λ0, . . . , λN−1) are eigenvalues of A In general A can be diagonalized using Jordan decomposition. Big Data Analysis with Signal Processing on Graphs 8-22
Graph Fourier Transform (cont’d) For simplicity, assume that A is diagonalizable and its decomposition is A = V ΛV −1 (11) where the columns vn of the matrix V = [v0 · · · vN−1] ∈ CN×N are the eigenvectors of A and Λ = diag(λ0, . . . , λN−1) are eigenvalues of A In general A can be diagonalized using Jordan decomposition. Big Data Analysis with Signal Processing on Graphs 8-23
Graph Fourier Transform (cont’d) The eigenfunctions of graph filters h(A) are given by the eigenvectors of the graph shift matrix A Since the expansion into the eigenbasis is given by the multiplication with the inverse eigenvector matrix, which always exists, the graph Fourier transform is well defined and computed as ˆs = [ ˆs0, ˆs1, . . . , ˆsN−1] T = V −1 s (12) = Fs (13) where F = V −1 is the graph Fourier transform matrix. Big Data Analysis with Signal Processing on Graphs 8-24
Graph Fourier Transform (cont’d) The eigenfunctions of graph filters h(A) are given by the eigenvectors of the graph shift matrix A Since the expansion into the eigenbasis is given by the multiplication with the inverse eigenvector matrix, which always exists, the graph Fourier transform is well defined and computed as ˆs = [ ˆs0, ˆs1, . . . , ˆsN−1] T = V −1 s (12) = Fs (13) where F = V −1 is the graph Fourier transform matrix. Big Data Analysis with Signal Processing on Graphs 8-25
Graph Fourier Transform (cont’d) The eigenfunctions of graph filters h(A) are given by the eigenvectors of the graph shift matrix A Since the expansion into the eigenbasis is given by the multiplication with the inverse eigenvector matrix, which always exists, the graph Fourier transform is well defined and computed as ˆs = [ ˆs0, ˆs1, . . . , ˆsN−1] T = V −1 s (12) = Fs (13) where F = V −1 is the graph Fourier transform matrix. Big Data Analysis with Signal Processing on Graphs 8-26
Graph Fourier Transform (cont’d) The inverse graph Fourier transform reconstructs the graph signal from is frequency content by combining graph frequency components weighted by the coefficients of the signal’s graph Fourier transform: s = ˆs0v0 + ˆs1v1 + · · · + ˆsN−1vN−1 (14) = F−1 s = V s (15) Big Data Analysis with Signal Processing on Graphs 8-27
Low and High Frequencies on Graphs The values ˆsn in (12) are the signal’s expansion in the eigenvector basis and represent the frequency content of the signal s. The eigenvalues λn of the shift matrix A represent graph frequency content, and the eigenvectors vn represent the corresponding graph frequency component. To conclude, the higher λn, the higher frequency content and vice versa. Big Data Analysis with Signal Processing on Graphs 8-28
Low and High Frequencies on Graphs The values ˆsn in (12) are the signal’s expansion in the eigenvector basis and represent the frequency content of the signal s. The eigenvalues λn of the shift matrix A represent graph frequency content, and the eigenvectors vn represent the corresponding graph frequency component. To conclude, the higher λn, the higher frequency content and vice versa. Big Data Analysis with Signal Processing on Graphs 8-29
Low and High Frequencies on Graphs The values ˆsn in (12) are the signal’s expansion in the eigenvector basis and represent the frequency content of the signal s. The eigenvalues λn of the shift matrix A represent graph frequency content, and the eigenvectors vn represent the corresponding graph frequency component. To conclude, the higher λn, the higher frequency content and vice versa. Big Data Analysis with Signal Processing on Graphs 8-30
Low and High Frequencies on Graphs The values ˆsn in (12) are the signal’s expansion in the eigenvector basis and represent the frequency content of the signal s. The eigenvalues λn of the shift matrix A represent graph frequency content, and the eigenvectors vn represent the corresponding graph frequency component. To conclude, the higher λn, the higher frequency content and vice versa. Big Data Analysis with Signal Processing on Graphs 8-31
Frequency Response of Graph Filters In addition to expressing the frequency content of graph signals, the graph Fourier transform also characterizes the effect of filters on the frequency content of signals. The filtering operation ˜s = h(A)s can be written using h(A) = L−1 l=0 hlAl and ˆs = V −1 s as follows ˜s = h(A)s = h(F−1 AF)s = F−1 h(Λ)Fs (16) where h(Λ) is a diagonal matrix with values h(λn) = L−1 l=0 hlλl n As a result, ˜s = h(A)s ⇔ Fs = h(Λ)s (17) Big Data Analysis with Signal Processing on Graphs 8-32
Frequency Response of Graph Filters In addition to expressing the frequency content of graph signals, the graph Fourier transform also characterizes the effect of filters on the frequency content of signals. The filtering operation ˜s = h(A)s can be written using h(A) = L−1 l=0 hlAl and ˆs = V −1 s as follows ˜s = h(A)s = h(F−1 AF)s = F−1 h(Λ)Fs (16) where h(Λ) is a diagonal matrix with values h(λn) = L−1 l=0 hlλl n As a result, ˜s = h(A)s ⇔ Fs = h(Λ)s (17) Big Data Analysis with Signal Processing on Graphs 8-33
Frequency Response of Graph Filters In addition to expressing the frequency content of graph signals, the graph Fourier transform also characterizes the effect of filters on the frequency content of signals. The filtering operation ˜s = h(A)s can be written using h(A) = L−1 l=0 hlAl and ˆs = V −1 s as follows ˜s = h(A)s = h(F−1 AF)s = F−1 h(Λ)Fs (16) where h(Λ) is a diagonal matrix with values h(λn) = L−1 l=0 hlλl n As a result, ˜s = h(A)s ⇔ Fs = h(Λ)s (17) Big Data Analysis with Signal Processing on Graphs 8-34
Frequency Response of Graph Filters (cont’d) That is, the frequency content of a filtered signal is modified by multiplying its frequency content element-wise by h(λn) . These values represent the graph frequency response of the graph filter. The relation is a generalization of the classical convolution theorem to graphs: filtering a graph signal in the graph domain is equivalent in the frequency domain to multiplying the signal spectrum by the frequency response of the graph filter. ˜s = h(A)s ⇔ Fs = h(Λ)s Big Data Analysis with Signal Processing on Graphs 8-35
Frequency Response of Graph Filters (cont’d) That is, the frequency content of a filtered signal is modified by multiplying its frequency content element-wise by h(λn) . These values represent the graph frequency response of the graph filter. The relation is a generalization of the classical convolution theorem to graphs: filtering a graph signal in the graph domain is equivalent in the frequency domain to multiplying the signal spectrum by the frequency response of the graph filter. ˜s = h(A)s ⇔ Fs = h(Λ)s Big Data Analysis with Signal Processing on Graphs 8-36
Contents Introduction Fundamentals of Graph Theory DSP on Graphs Graph Products Applications Big Data Analysis with Signal Processing on Graphs 8-37
Product Graphs Consider two graphs G1 = (V1, A1) and G2 = (V2, A2) with |V1| = N1 and |V2| = N2 nodes, respectively. The product graph, denoted by , of G1 and G2 is the graph G = G1 G2 = (V, A ) (18) with |V| = N1N2 and dim(A ) = N1N2 × N1N2. Big Data Analysis with Signal Processing on Graphs 8-38
Common Product Graphs Types 1. Kronecker product A⊗ = A1 ⊗ A2 (19) Example: If we have two matrices B ∈ CM×N and C ∈ CK×L , then the Kronecker product is defined as follows B ⊗ C =     b1,1C ... bM,1C · · · ... · · · b1,M C ... bM,M C     ∈ CMK×NL (20) Big Data Analysis with Signal Processing on Graphs 8-39
Common Product Graphs Types 1. Cartesian product A× = A1 ⊗ IN2 + IN1 ⊗ A2 (21) 2. Strong product A = A1 ⊗ A2 + A1 ⊗ IN2 + IN1 ⊗ A2 (22) Big Data Analysis with Signal Processing on Graphs 8-40
Examples on Product Graphs Big Data Analysis with Signal Processing on Graphs 8-41
Examples on Product Graphs Big Data Analysis with Signal Processing on Graphs 8-42
Examples on Product Graphs Big Data Analysis with Signal Processing on Graphs 8-43
Notes on Product Graphs Big Data Analysis with Signal Processing on Graphs 8-44
Signal Processing on Product Graphs The computation of filtering and Fourier transform on graphs and improve algorithms, data storage, and memory access for large data sets can modularized thanks to graph products. Such as Filtering Computation complexity: O(N2 ) =⇒ O(N(N1 + N2)) Fourier transform Computation complexity: O(N3 ) =⇒ O(N3 1 + N3 2 ) Big Data Analysis with Signal Processing on Graphs 8-45
Signal Processing on Product Graphs The computation of filtering and Fourier transform on graphs and improve algorithms, data storage, and memory access for large data sets can modularized thanks to graph products. Such as Filtering Computation complexity: O(N2 ) =⇒ O(N(N1 + N2)) Fourier transform Computation complexity: O(N3 ) =⇒ O(N3 1 + N3 2 ) Big Data Analysis with Signal Processing on Graphs 8-46
Signal Processing on Product Graphs The computation of filtering and Fourier transform on graphs and improve algorithms, data storage, and memory access for large data sets can modularized thanks to graph products. Such as Filtering Computation complexity: O(N2 ) =⇒ O(N(N1 + N2)) Fourier transform Computation complexity: O(N3 ) =⇒ O(N3 1 + N3 2 ) Big Data Analysis with Signal Processing on Graphs 8-47
Contents Introduction Fundamentals of Graph Theory DSP on Graphs Graph Products Applications Big Data Analysis with Signal Processing on Graphs 8-48
Applications Like-wise traditional DSP problems: Data compression Fourier transform or through wavelet expansions, or adaptive filter design Detection of corrupted data High pass filter Big Data Analysis with Signal Processing on Graphs 8-49
Applications Like-wise traditional DSP problems: Data compression Fourier transform or through wavelet expansions, or adaptive filter design Detection of corrupted data High pass filter Big Data Analysis with Signal Processing on Graphs 8-50
Applications Like-wise traditional DSP problems: Data compression Fourier transform or through wavelet expansions, or adaptive filter design Detection of corrupted data High pass filter Big Data Analysis with Signal Processing on Graphs 8-51
Challenges of Big Data While there is no single, universally agreed upon set of properties that define big data. Some of the commonly mentioned ones are volume, velocity, and variety of data. Big Data Analysis with Signal Processing on Graphs 8-52
Challenges of Big Data While there is no single, universally agreed upon set of properties that define big data. Some of the commonly mentioned ones are volume, velocity, and variety of data. Big Data Analysis with Signal Processing on Graphs 8-53
Challenges of Big Data Some of the commonly mentioned ones are volume, velocity, and variety of data. First of all, the sheer volume of data to be processed requires efficient distributed and scalable storage, access, and processing. High velocity of new data arrival demands fast algorithms to prevent bottlenecks and explosion of the data volume and to extract valuable information from the data and incorporate it into the decision-making process in real time. (FFT in DSP) Finally, collected data sets contain information in all varieties and forms, including numerical, textual, and visual data. To generalize data analysis techniques to diverse data sets, we need a common representation framework for data sets and their structure. Big Data Analysis with Signal Processing on Graphs 8-54
Challenges of Big Data Some of the commonly mentioned ones are volume, velocity, and variety of data. First of all, the sheer volume of data to be processed requires efficient distributed and scalable storage, access, and processing. High velocity of new data arrival demands fast algorithms to prevent bottlenecks and explosion of the data volume and to extract valuable information from the data and incorporate it into the decision-making process in real time. (FFT in DSP) Finally, collected data sets contain information in all varieties and forms, including numerical, textual, and visual data. To generalize data analysis techniques to diverse data sets, we need a common representation framework for data sets and their structure. Big Data Analysis with Signal Processing on Graphs 8-55
Challenges of Big Data Some of the commonly mentioned ones are volume, velocity, and variety of data. First of all, the sheer volume of data to be processed requires efficient distributed and scalable storage, access, and processing. High velocity of new data arrival demands fast algorithms to prevent bottlenecks and explosion of the data volume and to extract valuable information from the data and incorporate it into the decision-making process in real time. (FFT in DSP) Finally, collected data sets contain information in all varieties and forms, including numerical, textual, and visual data. To generalize data analysis techniques to diverse data sets, we need a common representation framework for data sets and their structure. Big Data Analysis with Signal Processing on Graphs 8-56
Challenges of Big Data Some of the commonly mentioned ones are volume, velocity, and variety of data. First of all, the sheer volume of data to be processed requires efficient distributed and scalable storage, access, and processing. High velocity of new data arrival demands fast algorithms to prevent bottlenecks and explosion of the data volume and to extract valuable information from the data and incorporate it into the decision-making process in real time. (FFT in DSP) Finally, collected data sets contain information in all varieties and forms, including numerical, textual, and visual data. To generalize data analysis techniques to diverse data sets, we need a common representation framework for data sets and their structure. Big Data Analysis with Signal Processing on Graphs 8-57
Thank You! Big Data Analysis with Signal Processing on Graphs 8-58

More Related Content

PDF
A review on structure learning in GNN
bytuxette
 
PDF
Yuri Boykov — Combinatorial optimization for higher-order segmentation functi...
byYandex
 
PPTX
Pixelrelationships
byHarshavardhan Reddy
 
PDF
Core–periphery detection in networks with nonlinear Perron eigenvectors
byFrancesco Tudisco
 
PDF
Optimal L-shaped matrix reordering, aka graph's core-periphery
byFrancesco Tudisco
 
PDF
Gradient Estimation Using Stochastic Computation Graphs
byYoonho Lee
 
PDF
k-MLE: A fast algorithm for learning statistical mixture models
byFrank Nielsen
 
PDF
A Hough Transform Based On a Map-Reduce Algorithm
byIJERA Editor
 
A review on structure learning in GNN
bytuxette
 
Yuri Boykov — Combinatorial optimization for higher-order segmentation functi...
byYandex
 
Pixelrelationships
byHarshavardhan Reddy
 
Core–periphery detection in networks with nonlinear Perron eigenvectors
byFrancesco Tudisco
 
Optimal L-shaped matrix reordering, aka graph's core-periphery
byFrancesco Tudisco
 
Gradient Estimation Using Stochastic Computation Graphs
byYoonho Lee
 
k-MLE: A fast algorithm for learning statistical mixture models
byFrank Nielsen
 
A Hough Transform Based On a Map-Reduce Algorithm
byIJERA Editor
 

What's hot

PDF
Lec17 sparse signal processing & applications
byUnited States Air Force Academy
 
PDF
Lec-08 Feature Aggregation II: Fisher Vector, AKULA and Super Vector
byUnited States Air Force Academy
 
DOCX
Digtial Image Processing Q@A
byChung Hua Universit
 
PDF
International Journal of Managing Information Technology (IJMIT)
byIJMIT JOURNAL
 
PDF
An improved spfa algorithm for single source shortest path problem using forw...
byIJMIT JOURNAL
 
PDF
An improved spfa algorithm for single source shortest path problem using forw...
byIJMIT JOURNAL
 
PDF
From RNN to neural networks for cyclic undirected graphs
bytuxette
 
PDF
Polyhedral computations in computational algebraic geometry and optimization
byVissarion Fisikopoulos
 
PDF
Lec07 aggregation-and-retrieval-system
byUnited States Air Force Academy
 
PPTX
rit seminars-privacy assured outsourcing of image reconstruction services in ...
bythahirakabeer
 
PDF
master thesis presentation
byCheng (Sophia) Gao
 
PDF
Training and Inference for Deep Gaussian Processes
byKeyon Vafa
 
PDF
Solving The Shortest Path Tour Problem
byNozir Shokirov
 
PDF
Lec12 review-part-i
byUnited States Air Force Academy
 
PDF
QMC Program: Trends and Advances in Monte Carlo Sampling Algorithms Workshop,...
byThe Statistical and Applied Mathematical Sciences Institute
 
PDF
Graph Neural Network in practice
bytuxette
 
PDF
Dic rd theory_quantization_07
bywtyru1989
 
PDF
13 fourierfiltrationen
byhoailinhtinh
 
PDF
Elliptic curve scalar multiplier using karatsuba
byIAEME Publication
 
PDF
Graph Kernels for Chemical Informatics
byMukund Raj
 
Lec17 sparse signal processing & applications
byUnited States Air Force Academy
 
Lec-08 Feature Aggregation II: Fisher Vector, AKULA and Super Vector
byUnited States Air Force Academy
 
Digtial Image Processing Q@A
byChung Hua Universit
 
International Journal of Managing Information Technology (IJMIT)
byIJMIT JOURNAL
 
An improved spfa algorithm for single source shortest path problem using forw...
byIJMIT JOURNAL
 
An improved spfa algorithm for single source shortest path problem using forw...
byIJMIT JOURNAL
 
From RNN to neural networks for cyclic undirected graphs
bytuxette
 
Polyhedral computations in computational algebraic geometry and optimization
byVissarion Fisikopoulos
 
Lec07 aggregation-and-retrieval-system
byUnited States Air Force Academy
 
rit seminars-privacy assured outsourcing of image reconstruction services in ...
bythahirakabeer
 
master thesis presentation
byCheng (Sophia) Gao
 
Training and Inference for Deep Gaussian Processes
byKeyon Vafa
 
Solving The Shortest Path Tour Problem
byNozir Shokirov
 
Lec12 review-part-i
byUnited States Air Force Academy
 
QMC Program: Trends and Advances in Monte Carlo Sampling Algorithms Workshop,...
byThe Statistical and Applied Mathematical Sciences Institute
 
Graph Neural Network in practice
bytuxette
 
Dic rd theory_quantization_07
bywtyru1989
 
13 fourierfiltrationen
byhoailinhtinh
 
Elliptic curve scalar multiplier using karatsuba
byIAEME Publication
 
Graph Kernels for Chemical Informatics
byMukund Raj
 

Viewers also liked

PPTX
What is Big Data?
byBernard Marr
 
PDF
Nile University Recruitment | 2016
byMohamed Seif
 
PDF
Case study : Backing Australia's Ability
byMohamed Seif
 
PDF
A glimpse on the academic scholar
byMohamed Seif
 
PDF
Interference management in spectrally and energy efficient wireless networks
byMohamed Seif
 
PDF
KnowledgeNow Software App
byMohamed Seif
 
PDF
PIMRC 2016 Presentation
byMohamed Seif
 
PDF
Sparse Spectrum Sensing in Infrastructure-less Cognitive Radio Networks via B...
byMohamed Seif
 
PPTX
Free Space Optics
byMohamed Seif
 
PDF
Interference Management with Limited Channel State Information in Wireless Ne...
byMohamed Seif
 
PPTX
Lrz kurs: big data analysis
byFerdinand Jamitzky
 
PDF
5 g communications
byMohamed Seif
 
PDF
Achievable Degrees of Freedom of the K-user MISO Broadcast Channel with Alter...
byMohamed Seif
 
PPTX
Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
bySOYEON KIM
 
PPTX
Big Data with Not Only SQL
byPhilippe Julio
 
PDF
Label propagation - Semisupervised Learning with Applications to NLP
byDavid Przybilla
 
PDF
Iris data analysis example in R
byDuyen Do
 
PPTX
What is big data?
byDavid Wellman
 
PPTX
Big data ppt
byThirunavukkarasu Ps
 
PPT
Big Data
byNGDATA
 
What is Big Data?
byBernard Marr
 
Nile University Recruitment | 2016
byMohamed Seif
 
Case study : Backing Australia's Ability
byMohamed Seif
 
A glimpse on the academic scholar
byMohamed Seif
 
Interference management in spectrally and energy efficient wireless networks
byMohamed Seif
 
KnowledgeNow Software App
byMohamed Seif
 
PIMRC 2016 Presentation
byMohamed Seif
 
Sparse Spectrum Sensing in Infrastructure-less Cognitive Radio Networks via B...
byMohamed Seif
 
Free Space Optics
byMohamed Seif
 
Interference Management with Limited Channel State Information in Wireless Ne...
byMohamed Seif
 
Lrz kurs: big data analysis
byFerdinand Jamitzky
 
5 g communications
byMohamed Seif
 
Achievable Degrees of Freedom of the K-user MISO Broadcast Channel with Alter...
byMohamed Seif
 
Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
bySOYEON KIM
 
Big Data with Not Only SQL
byPhilippe Julio
 
Label propagation - Semisupervised Learning with Applications to NLP
byDavid Przybilla
 
Iris data analysis example in R
byDuyen Do
 
What is big data?
byDavid Wellman
 
Big data ppt
byThirunavukkarasu Ps
 
Big Data
byNGDATA
 

Similar to Big Data Analysis with Signal Processing on Graphs

PDF
Cdt guest lecture_gsp
bynagarajusonti123
 
PDF
Vertex frequency
byVanessa Brischi Olivatto
 
PDF
GraphSignalProcessingFinalPaper
byChiraz Nafouki
 
PDF
The Power of Graphs in Immersive Communications
bytonizza82
 
PDF
Graph Signal Processing for Machine Learning A Review and New Perspectives - ...
bylauratoni4
 
PDF
An Introduction to Spectral Graph Theory
byjoisino
 
PPT
Signals and classification
bySuraj Mishra
 
PDF
Graph Signal Processing for Machine Learning A Review and New Perspectives - ...
bylauratoni4
 
PPT
introduction to digital signal processing
bykomminenisruthi1
 
PDF
(Ebook) Foundations of Signal Processing by Martin Vetterli; Jelena Kovačević...
byainnigbts
 
PPT
Sns slide 1 2011
bycheekeong1231
 
PDF
Digital Filters Design For Signal And Image Processing Momamed Najim
bykasalwalereg
 
PDF
Use of eigenvalues and eigenvectors to analyze bipartivity of network graphs
bycsandit
 
PDF
Applied Digital Signal Processing And Applications Othman Omran Khalifa
byvlxpnnmj1145
 
PDF
Introduction to Digital Signal Processing (DSP) - Course Notes
byAhmed Gad
 
PDF
DSP 2.pdf
byRamilDTolentino
 
PPTX
Signals and Systems-Unit 1 & 2.pptx
bySelamawitHadush1
 
PDF
Note 0
byMukesh Gupta
 
PDF
Graphical Model Selection for Big Data
byAlexander Jung
 
PDF
Module 1 (1).pdf
byMohamedshabana38
 
Cdt guest lecture_gsp
bynagarajusonti123
 
Vertex frequency
byVanessa Brischi Olivatto
 
GraphSignalProcessingFinalPaper
byChiraz Nafouki
 
The Power of Graphs in Immersive Communications
bytonizza82
 
Graph Signal Processing for Machine Learning A Review and New Perspectives - ...
bylauratoni4
 
An Introduction to Spectral Graph Theory
byjoisino
 
Signals and classification
bySuraj Mishra
 
Graph Signal Processing for Machine Learning A Review and New Perspectives - ...
bylauratoni4
 
introduction to digital signal processing
bykomminenisruthi1
 
(Ebook) Foundations of Signal Processing by Martin Vetterli; Jelena Kovačević...
byainnigbts
 
Sns slide 1 2011
bycheekeong1231
 
Digital Filters Design For Signal And Image Processing Momamed Najim
bykasalwalereg
 
Use of eigenvalues and eigenvectors to analyze bipartivity of network graphs
bycsandit
 
Applied Digital Signal Processing And Applications Othman Omran Khalifa
byvlxpnnmj1145
 
Introduction to Digital Signal Processing (DSP) - Course Notes
byAhmed Gad
 
DSP 2.pdf
byRamilDTolentino
 
Signals and Systems-Unit 1 & 2.pptx
bySelamawitHadush1
 
Note 0
byMukesh Gupta
 
Graphical Model Selection for Big Data
byAlexander Jung
 
Module 1 (1).pdf
byMohamedshabana38
 

More from Mohamed Seif

PDF
Sequential Probability Ratio Test for Sparse Signals
byMohamed Seif
 
PDF
Stopping Problems
byMohamed Seif
 
PDF
Interference Management for Multi-hop Networks
byMohamed Seif
 
PDF
VTC 2016 Fall Poster
byMohamed Seif
 
PDF
MIMO Vehicle to Vehicle Channels: An Experimental Study
byMohamed Seif
 
PDF
Stability Analysis in a Cognitive Radio System with Cooperative Beamforming
byMohamed Seif
 
PDF
Stability Analysis in a Cognitive Radio System with Cooperative Beamforming
byMohamed Seif
 
PDF
Optimal Relay Selection and Beamforming in MIMO Cognitive Multi-Relay Networks
byMohamed Seif
 
PDF
Optimal Relay Selection and Beamforming in MIMO Cognitive Multi-Relay Networks
byMohamed Seif
 
PDF
Spatial techniques in WiFi 802.11ac
byMohamed Seif
 
PDF
Short survey for Channel estimation using OFDM systems
byMohamed Seif
 
PPTX
Binary consensus
byMohamed Seif
 
Sequential Probability Ratio Test for Sparse Signals
byMohamed Seif
 
Stopping Problems
byMohamed Seif
 
Interference Management for Multi-hop Networks
byMohamed Seif
 
VTC 2016 Fall Poster
byMohamed Seif
 
MIMO Vehicle to Vehicle Channels: An Experimental Study
byMohamed Seif
 
Stability Analysis in a Cognitive Radio System with Cooperative Beamforming
byMohamed Seif
 
Stability Analysis in a Cognitive Radio System with Cooperative Beamforming
byMohamed Seif
 
Optimal Relay Selection and Beamforming in MIMO Cognitive Multi-Relay Networks
byMohamed Seif
 
Optimal Relay Selection and Beamforming in MIMO Cognitive Multi-Relay Networks
byMohamed Seif
 
Spatial techniques in WiFi 802.11ac
byMohamed Seif
 
Short survey for Channel estimation using OFDM systems
byMohamed Seif
 
Binary consensus
byMohamed Seif
 

Recently uploaded

PDF
What is Surface Mount Technology (SMT).pdf
bysproworkstech
 
PDF
How Are Learning-Based Methods Reshaping Trajectory Planning in Autonomous D...
byimagnejane
 
PPTX
Why Did The submarine Kursk Sink? What went wrong?
byBob Mayer
 
PPTX
Introduction of gdg and info session on study jam.pptx
byDeepakkumarSingh415123
 
PDF
Replacing react with hotwire - Scot Ruby September 2025
bypythonandchips
 
PDF
Evolution of MQ Messaging to Distributed Data Pipeline
byPeerapat Asoktummarungsri
 
PPTX
LNG Basics by Choi SPE Introductory Liquefaction Lecture
byRobertWaters35
 
PPTX
INDUSTRIAL ERGONOMICS.pptx-MCN 401 -MODULE 3
byVinayB68
 
PPT
P N Junction Diode Theory 1111111111.ppt
byHarshal Vaidya
 
PDF
SE APPIA LIFE VOL 2-3GR for service manual.pdf
bytroneelektrik
 
PDF
The Electric Power Engineering Handbook - 12 - Power System Operation And Con...
byislammuddinilsevar
 
PPTX
Electrical_Draftsman_AutoCAD_Mastery_Roadmap.pptx
byKen Felix Lubega
 
PDF
AppiaII-Manual-2-3Gr for service technician.pdf
bytroneelektrik
 
PPTX
MET 305 MOD 5.pptx-ENTERPRISE RESOURCE PLANNING
byVinayB68
 
PPTX
Claude Skills Presentation - Instructions, Scripts and Resources
byRick Hightower
 
PDF
Design of a high frequency low voltage CMOS operational amplifier
byVLSICS Design
 
PDF
Turbo Machinery Control by CCC updated from Previous Presentations by Honeywell
byRobertWaters35
 
PDF
kubernets: Kubernetes (often abbreviated as K8s) is an open-source platform f...
bysafaetulahasan1
 
PDF
SMT PCB Assembly Process -Manufacturing Ebook.pdf
bysproworkstech
 
PDF
An architecture to build high performance infrastructures on cloud computing ...
byTELKOMNIKA JOURNAL
 
What is Surface Mount Technology (SMT).pdf
bysproworkstech
 
How Are Learning-Based Methods Reshaping Trajectory Planning in Autonomous D...
byimagnejane
 
Why Did The submarine Kursk Sink? What went wrong?
byBob Mayer
 
Introduction of gdg and info session on study jam.pptx
byDeepakkumarSingh415123
 
Replacing react with hotwire - Scot Ruby September 2025
bypythonandchips
 
Evolution of MQ Messaging to Distributed Data Pipeline
byPeerapat Asoktummarungsri
 
LNG Basics by Choi SPE Introductory Liquefaction Lecture
byRobertWaters35
 
INDUSTRIAL ERGONOMICS.pptx-MCN 401 -MODULE 3
byVinayB68
 
P N Junction Diode Theory 1111111111.ppt
byHarshal Vaidya
 
SE APPIA LIFE VOL 2-3GR for service manual.pdf
bytroneelektrik
 
The Electric Power Engineering Handbook - 12 - Power System Operation And Con...
byislammuddinilsevar
 
Electrical_Draftsman_AutoCAD_Mastery_Roadmap.pptx
byKen Felix Lubega
 
AppiaII-Manual-2-3Gr for service technician.pdf
bytroneelektrik
 
MET 305 MOD 5.pptx-ENTERPRISE RESOURCE PLANNING
byVinayB68
 
Claude Skills Presentation - Instructions, Scripts and Resources
byRick Hightower
 
Design of a high frequency low voltage CMOS operational amplifier
byVLSICS Design
 
Turbo Machinery Control by CCC updated from Previous Presentations by Honeywell
byRobertWaters35
 
kubernets: Kubernetes (often abbreviated as K8s) is an open-source platform f...
bysafaetulahasan1
 
SMT PCB Assembly Process -Manufacturing Ebook.pdf
bysproworkstech
 
An architecture to build high performance infrastructures on cloud computing ...
byTELKOMNIKA JOURNAL
 

Big Data Analysis with Signal Processing on Graphs

  • 1.
    Big Data TalksNile University Talk 8 Big Data Analysis with Signal Processing on Graphs Introduction Fundamentals of Graph Theory DSP on Graphs Graph Products Applications Mohamed Seif m.seif@nu.edu.eg 8-1
  • 2.
    Contents Introduction Fundamentals of GraphTheory DSP on Graphs Graph Products Applications Big Data Analysis with Signal Processing on Graphs 8-2
  • 3.
    Introduction How to relatethe Signal Processing Definitions with Graphs? Big Data Analysis with Signal Processing on Graphs 8-3
  • 4.
    Introduction How to relatethe Signal Processing Definitions with Graphs? Big Data Analysis with Signal Processing on Graphs 8-4
  • 5.
    Contents Introduction Fundamentals of GraphTheory DSP on Graphs Graph Products Applications Big Data Analysis with Signal Processing on Graphs 8-5
  • 6.
    What Is Graph? Ingraph theory, the graph G is defined as a tuple G = (V, E) where V = {v0, v1, . . . , vN−1} is the set of N nodes and E = {eij, ∀(i, j) ∈ {0, 1, . . . , N − 1}} is the set containing all links between the nodes. Example: V = {1, 2, 3, 4} E = {{1, 2}, {2, 3}, {3, 4}, {4, 1}} 1 2 3 4 Big Data Analysis with Signal Processing on Graphs 8-6
  • 7.
    What Is Graph? Ingraph theory, the graph G is defined as a tuple G = (V, E) where V = {v0, v1, . . . , vN−1} is the set of N nodes and E = {eij, ∀(i, j) ∈ {0, 1, . . . , N − 1}} is the set containing all links between the nodes. Example: V = {1, 2, 3, 4} E = {{1, 2}, {2, 3}, {3, 4}, {4, 1}} 1 2 3 4 Big Data Analysis with Signal Processing on Graphs 8-7
  • 8.
    What Is Graph?(cont’d) In graph theory, the graph G is defined as a tuple G = (V, E) where V = {v0, v1, . . . , vN−1} is the set of N nodes and E = {eij, ∀(i, j) ∈ {0, 1, . . . , N − 1}} is the set containing all links between the nodes. Big Data Analysis with Signal Processing on Graphs 8-8
  • 9.
    What Is Graph? Ingraph theory, the graph G is defined as a tuple G = (V, E) where V = {v0, v1, . . . , vN−1} is the set of N nodes and E = {eij, ∀(i, j) ∈ {0, 1, . . . , N − 1}} is the set containing all links between the nodes. Big Data Analysis with Signal Processing on Graphs 8-9
  • 10.
    Alternative Representation ofGraphs 1. Adjacency matrix AN×N , defined as Ai,j =    1 if vi & vj are connected 0 o.w. 2. Laplacian graph LN×N , defined as L = D − A, where D is the degree matrix Li,j =    deg(vi) if i = j −1 if i = j & vi is adjacent to vj 0 o.w. Big Data Analysis with Signal Processing on Graphs 8-10
  • 11.
    Contents Introduction Fundamentals of GraphTheory DSP on Graphs Graph Products Applications Big Data Analysis with Signal Processing on Graphs 8-11
  • 12.
    Graph Signals Given thegraph, the data set forms a graph signal, defined as a map s : V → C, vn → sn (1) It is convenient to write graph signals as vectors s = [s0, s1, . . . , sN−1] T ∈ CN×1 (2) Big Data Analysis with Signal Processing on Graphs 8-12
  • 13.
    Graph Shift In DSP,a signal shift, implemented as a time delay ˜s = [ ˜s0, ˜s1, . . . , ˜sN−1] T = Cs (3) where C is the N × N cyclic shift matrix. DSP on Graphs extends the concept of shift to general graphs by defining the graph shift as a local operation that replaces a signal value sn at node vn by a linear combination of the values at neighbors of vn weighted by their edge weights: ˜sn = m∈Nn An,msm (4) Big Data Analysis with Signal Processing on Graphs 8-13
  • 14.
    Graph Shift (cont’d) Itcan be interpreted as a first-order interpolation, weighted averaging, or regression on graphs, which is a widely used operation in graph regression, distributed consensus, telecommunications. Then, the graph shift is written as ˜s = [ ˜s0, ˜s1, . . . , ˜sN−1] T = As (5) Big Data Analysis with Signal Processing on Graphs 8-14
  • 15.
    Graph Filters andZ-Transform In signal processing, a filter is a system H(.) that takes an input signal s and outputs a signal: ˜s = [ ˜s0, ˜s1, . . . , ˜sN−1] T = H(s) (6) Among the most widely used filters are linear shift-ivariant (LSI) ones. The z-transform provides a convenient representation for signals and filters in DSP. (In short) An alternative representation for the output signal is given by ˜s = h(C)s (7) where h(c) = N−1 n=0 hnCn (Resultant is a circulant matrix) Big Data Analysis with Signal Processing on Graphs 8-15
  • 16.
    Graph Filters andZ-Transform In signal processing, a filter is a system H(.) that takes an input signal s and outputs a signal: ˜s = [ ˜s0, ˜s1, . . . , ˜sN−1] T = H(s) (6) Among the most widely used filters are linear shift-ivariant (LSI) ones. The z-transform provides a convenient representation for signals and filters in DSP. (In short) An alternative representation for the output signal is given by ˜s = h(C)s (7) where h(c) = N−1 n=0 hnCn (Resultant is a circulant matrix) Big Data Analysis with Signal Processing on Graphs 8-16
  • 17.
    Graph Filters andZ-Transform In signal processing, a filter is a system H(.) that takes an input signal s and outputs a signal: ˜s = [ ˜s0, ˜s1, . . . , ˜sN−1] T = H(s) (6) Among the most widely used filters are linear shift-ivariant (LSI) ones. The z-transform provides a convenient representation for signals and filters in DSP. (In short) An alternative representation for the output signal is given by ˜s = h(C)s (7) where h(c) = N−1 n=0 hnCn (Resultant is a circulant matrix) Big Data Analysis with Signal Processing on Graphs 8-17
  • 18.
    Graph Filters andZ-Transform In signal processing, a filter is a system H(.) that takes an input signal s and outputs a signal: ˜s = [ ˜s0, ˜s1, . . . , ˜sN−1] T = H(s) (6) Among the most widely used filters are linear shift-ivariant (LSI) ones. The z-transform provides a convenient representation for signals and filters in DSP. (In short) An alternative representation for the output signal is given by ˜s = h(C)s (7) where h(c) = N−1 n=0 hnCn (Resultant is a circulant matrix) Big Data Analysis with Signal Processing on Graphs 8-18
  • 19.
    Graph Filters andZ-Transform (cont’d) DSP on Graphs extends the concept of filters to general graphs. Similarly to the extension of the time shift to the graph shift, filters are generalized to graph filters as polynomials in the graph shift , and all LSI graph filters have the form h(A) = L−1 l=0 hlAl (8) In analogy with signal filters, the graph filter output is given by ˜s = h(A)s (9) Big Data Analysis with Signal Processing on Graphs 8-19
  • 20.
    Graph Fourier Transform Mathematically,a Fourier transform with respect to a set of operators is the expansion of a signal into a basis of the operators eigen functions. Since in signal processing the operators of interest are filters, DSPG defines the Fourier transform with respect to the graph filters. ˜s = [ ˜s0, ˜s1, . . . , ˜sN−1] T = GFT{s} (10) Big Data Analysis with Signal Processing on Graphs 8-20
  • 21.
    Graph Fourier Transform Mathematically,a Fourier transform with respect to a set of operators is the expansion of a signal into a basis of the operators eigen functions. Since in signal processing the operators of interest are filters, DSPG defines the Fourier transform with respect to the graph filters. ˜s = [ ˜s0, ˜s1, . . . , ˜sN−1] T = GFT{s} (10) Big Data Analysis with Signal Processing on Graphs 8-21
  • 22.
    Graph Fourier Transform(cont’d) For simplicity, assume that A is diagonalizable and its decomposition is A = V ΛV −1 (11) where the columns vn of the matrix V = [v0 · · · vN−1] ∈ CN×N are the eigenvectors of A and Λ = diag(λ0, . . . , λN−1) are eigenvalues of A In general A can be diagonalized using Jordan decomposition. Big Data Analysis with Signal Processing on Graphs 8-22
  • 23.
    Graph Fourier Transform(cont’d) For simplicity, assume that A is diagonalizable and its decomposition is A = V ΛV −1 (11) where the columns vn of the matrix V = [v0 · · · vN−1] ∈ CN×N are the eigenvectors of A and Λ = diag(λ0, . . . , λN−1) are eigenvalues of A In general A can be diagonalized using Jordan decomposition. Big Data Analysis with Signal Processing on Graphs 8-23
  • 24.
    Graph Fourier Transform(cont’d) The eigenfunctions of graph filters h(A) are given by the eigenvectors of the graph shift matrix A Since the expansion into the eigenbasis is given by the multiplication with the inverse eigenvector matrix, which always exists, the graph Fourier transform is well defined and computed as ˆs = [ ˆs0, ˆs1, . . . , ˆsN−1] T = V −1 s (12) = Fs (13) where F = V −1 is the graph Fourier transform matrix. Big Data Analysis with Signal Processing on Graphs 8-24
  • 25.
    Graph Fourier Transform(cont’d) The eigenfunctions of graph filters h(A) are given by the eigenvectors of the graph shift matrix A Since the expansion into the eigenbasis is given by the multiplication with the inverse eigenvector matrix, which always exists, the graph Fourier transform is well defined and computed as ˆs = [ ˆs0, ˆs1, . . . , ˆsN−1] T = V −1 s (12) = Fs (13) where F = V −1 is the graph Fourier transform matrix. Big Data Analysis with Signal Processing on Graphs 8-25
  • 26.
    Graph Fourier Transform(cont’d) The eigenfunctions of graph filters h(A) are given by the eigenvectors of the graph shift matrix A Since the expansion into the eigenbasis is given by the multiplication with the inverse eigenvector matrix, which always exists, the graph Fourier transform is well defined and computed as ˆs = [ ˆs0, ˆs1, . . . , ˆsN−1] T = V −1 s (12) = Fs (13) where F = V −1 is the graph Fourier transform matrix. Big Data Analysis with Signal Processing on Graphs 8-26
  • 27.
    Graph Fourier Transform(cont’d) The inverse graph Fourier transform reconstructs the graph signal from is frequency content by combining graph frequency components weighted by the coefficients of the signal’s graph Fourier transform: s = ˆs0v0 + ˆs1v1 + · · · + ˆsN−1vN−1 (14) = F−1 s = V s (15) Big Data Analysis with Signal Processing on Graphs 8-27
  • 28.
    Low and HighFrequencies on Graphs The values ˆsn in (12) are the signal’s expansion in the eigenvector basis and represent the frequency content of the signal s. The eigenvalues λn of the shift matrix A represent graph frequency content, and the eigenvectors vn represent the corresponding graph frequency component. To conclude, the higher λn, the higher frequency content and vice versa. Big Data Analysis with Signal Processing on Graphs 8-28
  • 29.
    Low and HighFrequencies on Graphs The values ˆsn in (12) are the signal’s expansion in the eigenvector basis and represent the frequency content of the signal s. The eigenvalues λn of the shift matrix A represent graph frequency content, and the eigenvectors vn represent the corresponding graph frequency component. To conclude, the higher λn, the higher frequency content and vice versa. Big Data Analysis with Signal Processing on Graphs 8-29
  • 30.
    Low and HighFrequencies on Graphs The values ˆsn in (12) are the signal’s expansion in the eigenvector basis and represent the frequency content of the signal s. The eigenvalues λn of the shift matrix A represent graph frequency content, and the eigenvectors vn represent the corresponding graph frequency component. To conclude, the higher λn, the higher frequency content and vice versa. Big Data Analysis with Signal Processing on Graphs 8-30
  • 31.
    Low and HighFrequencies on Graphs The values ˆsn in (12) are the signal’s expansion in the eigenvector basis and represent the frequency content of the signal s. The eigenvalues λn of the shift matrix A represent graph frequency content, and the eigenvectors vn represent the corresponding graph frequency component. To conclude, the higher λn, the higher frequency content and vice versa. Big Data Analysis with Signal Processing on Graphs 8-31
  • 32.
    Frequency Response ofGraph Filters In addition to expressing the frequency content of graph signals, the graph Fourier transform also characterizes the effect of filters on the frequency content of signals. The filtering operation ˜s = h(A)s can be written using h(A) = L−1 l=0 hlAl and ˆs = V −1 s as follows ˜s = h(A)s = h(F−1 AF)s = F−1 h(Λ)Fs (16) where h(Λ) is a diagonal matrix with values h(λn) = L−1 l=0 hlλl n As a result, ˜s = h(A)s ⇔ Fs = h(Λ)s (17) Big Data Analysis with Signal Processing on Graphs 8-32
  • 33.
    Frequency Response ofGraph Filters In addition to expressing the frequency content of graph signals, the graph Fourier transform also characterizes the effect of filters on the frequency content of signals. The filtering operation ˜s = h(A)s can be written using h(A) = L−1 l=0 hlAl and ˆs = V −1 s as follows ˜s = h(A)s = h(F−1 AF)s = F−1 h(Λ)Fs (16) where h(Λ) is a diagonal matrix with values h(λn) = L−1 l=0 hlλl n As a result, ˜s = h(A)s ⇔ Fs = h(Λ)s (17) Big Data Analysis with Signal Processing on Graphs 8-33
  • 34.
    Frequency Response ofGraph Filters In addition to expressing the frequency content of graph signals, the graph Fourier transform also characterizes the effect of filters on the frequency content of signals. The filtering operation ˜s = h(A)s can be written using h(A) = L−1 l=0 hlAl and ˆs = V −1 s as follows ˜s = h(A)s = h(F−1 AF)s = F−1 h(Λ)Fs (16) where h(Λ) is a diagonal matrix with values h(λn) = L−1 l=0 hlλl n As a result, ˜s = h(A)s ⇔ Fs = h(Λ)s (17) Big Data Analysis with Signal Processing on Graphs 8-34
  • 35.
    Frequency Response ofGraph Filters (cont’d) That is, the frequency content of a filtered signal is modified by multiplying its frequency content element-wise by h(λn) . These values represent the graph frequency response of the graph filter. The relation is a generalization of the classical convolution theorem to graphs: filtering a graph signal in the graph domain is equivalent in the frequency domain to multiplying the signal spectrum by the frequency response of the graph filter. ˜s = h(A)s ⇔ Fs = h(Λ)s Big Data Analysis with Signal Processing on Graphs 8-35
  • 36.
    Frequency Response ofGraph Filters (cont’d) That is, the frequency content of a filtered signal is modified by multiplying its frequency content element-wise by h(λn) . These values represent the graph frequency response of the graph filter. The relation is a generalization of the classical convolution theorem to graphs: filtering a graph signal in the graph domain is equivalent in the frequency domain to multiplying the signal spectrum by the frequency response of the graph filter. ˜s = h(A)s ⇔ Fs = h(Λ)s Big Data Analysis with Signal Processing on Graphs 8-36
  • 37.
    Contents Introduction Fundamentals of GraphTheory DSP on Graphs Graph Products Applications Big Data Analysis with Signal Processing on Graphs 8-37
  • 38.
    Product Graphs Consider twographs G1 = (V1, A1) and G2 = (V2, A2) with |V1| = N1 and |V2| = N2 nodes, respectively. The product graph, denoted by , of G1 and G2 is the graph G = G1 G2 = (V, A ) (18) with |V| = N1N2 and dim(A ) = N1N2 × N1N2. Big Data Analysis with Signal Processing on Graphs 8-38
  • 39.
    Common Product GraphsTypes 1. Kronecker product A⊗ = A1 ⊗ A2 (19) Example: If we have two matrices B ∈ CM×N and C ∈ CK×L , then the Kronecker product is defined as follows B ⊗ C =     b1,1C ... bM,1C · · · ... · · · b1,M C ... bM,M C     ∈ CMK×NL (20) Big Data Analysis with Signal Processing on Graphs 8-39
  • 40.
    Common Product GraphsTypes 1. Cartesian product A× = A1 ⊗ IN2 + IN1 ⊗ A2 (21) 2. Strong product A = A1 ⊗ A2 + A1 ⊗ IN2 + IN1 ⊗ A2 (22) Big Data Analysis with Signal Processing on Graphs 8-40
  • 41.
    Examples on ProductGraphs Big Data Analysis with Signal Processing on Graphs 8-41
  • 42.
    Examples on ProductGraphs Big Data Analysis with Signal Processing on Graphs 8-42
  • 43.
    Examples on ProductGraphs Big Data Analysis with Signal Processing on Graphs 8-43
  • 44.
    Notes on ProductGraphs Big Data Analysis with Signal Processing on Graphs 8-44
  • 45.
    Signal Processing onProduct Graphs The computation of filtering and Fourier transform on graphs and improve algorithms, data storage, and memory access for large data sets can modularized thanks to graph products. Such as Filtering Computation complexity: O(N2 ) =⇒ O(N(N1 + N2)) Fourier transform Computation complexity: O(N3 ) =⇒ O(N3 1 + N3 2 ) Big Data Analysis with Signal Processing on Graphs 8-45
  • 46.
    Signal Processing onProduct Graphs The computation of filtering and Fourier transform on graphs and improve algorithms, data storage, and memory access for large data sets can modularized thanks to graph products. Such as Filtering Computation complexity: O(N2 ) =⇒ O(N(N1 + N2)) Fourier transform Computation complexity: O(N3 ) =⇒ O(N3 1 + N3 2 ) Big Data Analysis with Signal Processing on Graphs 8-46
  • 47.
    Signal Processing onProduct Graphs The computation of filtering and Fourier transform on graphs and improve algorithms, data storage, and memory access for large data sets can modularized thanks to graph products. Such as Filtering Computation complexity: O(N2 ) =⇒ O(N(N1 + N2)) Fourier transform Computation complexity: O(N3 ) =⇒ O(N3 1 + N3 2 ) Big Data Analysis with Signal Processing on Graphs 8-47
  • 48.
    Contents Introduction Fundamentals of GraphTheory DSP on Graphs Graph Products Applications Big Data Analysis with Signal Processing on Graphs 8-48
  • 49.
    Applications Like-wise traditional DSPproblems: Data compression Fourier transform or through wavelet expansions, or adaptive filter design Detection of corrupted data High pass filter Big Data Analysis with Signal Processing on Graphs 8-49
  • 50.
    Applications Like-wise traditional DSPproblems: Data compression Fourier transform or through wavelet expansions, or adaptive filter design Detection of corrupted data High pass filter Big Data Analysis with Signal Processing on Graphs 8-50
  • 51.
    Applications Like-wise traditional DSPproblems: Data compression Fourier transform or through wavelet expansions, or adaptive filter design Detection of corrupted data High pass filter Big Data Analysis with Signal Processing on Graphs 8-51
  • 52.
    Challenges of BigData While there is no single, universally agreed upon set of properties that define big data. Some of the commonly mentioned ones are volume, velocity, and variety of data. Big Data Analysis with Signal Processing on Graphs 8-52
  • 53.
    Challenges of BigData While there is no single, universally agreed upon set of properties that define big data. Some of the commonly mentioned ones are volume, velocity, and variety of data. Big Data Analysis with Signal Processing on Graphs 8-53
  • 54.
    Challenges of BigData Some of the commonly mentioned ones are volume, velocity, and variety of data. First of all, the sheer volume of data to be processed requires efficient distributed and scalable storage, access, and processing. High velocity of new data arrival demands fast algorithms to prevent bottlenecks and explosion of the data volume and to extract valuable information from the data and incorporate it into the decision-making process in real time. (FFT in DSP) Finally, collected data sets contain information in all varieties and forms, including numerical, textual, and visual data. To generalize data analysis techniques to diverse data sets, we need a common representation framework for data sets and their structure. Big Data Analysis with Signal Processing on Graphs 8-54
  • 55.
    Challenges of BigData Some of the commonly mentioned ones are volume, velocity, and variety of data. First of all, the sheer volume of data to be processed requires efficient distributed and scalable storage, access, and processing. High velocity of new data arrival demands fast algorithms to prevent bottlenecks and explosion of the data volume and to extract valuable information from the data and incorporate it into the decision-making process in real time. (FFT in DSP) Finally, collected data sets contain information in all varieties and forms, including numerical, textual, and visual data. To generalize data analysis techniques to diverse data sets, we need a common representation framework for data sets and their structure. Big Data Analysis with Signal Processing on Graphs 8-55
  • 56.
    Challenges of BigData Some of the commonly mentioned ones are volume, velocity, and variety of data. First of all, the sheer volume of data to be processed requires efficient distributed and scalable storage, access, and processing. High velocity of new data arrival demands fast algorithms to prevent bottlenecks and explosion of the data volume and to extract valuable information from the data and incorporate it into the decision-making process in real time. (FFT in DSP) Finally, collected data sets contain information in all varieties and forms, including numerical, textual, and visual data. To generalize data analysis techniques to diverse data sets, we need a common representation framework for data sets and their structure. Big Data Analysis with Signal Processing on Graphs 8-56
  • 57.
    Challenges of BigData Some of the commonly mentioned ones are volume, velocity, and variety of data. First of all, the sheer volume of data to be processed requires efficient distributed and scalable storage, access, and processing. High velocity of new data arrival demands fast algorithms to prevent bottlenecks and explosion of the data volume and to extract valuable information from the data and incorporate it into the decision-making process in real time. (FFT in DSP) Finally, collected data sets contain information in all varieties and forms, including numerical, textual, and visual data. To generalize data analysis techniques to diverse data sets, we need a common representation framework for data sets and their structure. Big Data Analysis with Signal Processing on Graphs 8-57
  • 58.
    Thank You! Big DataAnalysis with Signal Processing on Graphs 8-58