Graph Signal Processing: Theory and Applications to
Imaging & Machine Learning
Gene Cheung
York University, Toronto, Canada

June 27, 2023

Acknowledgement• Graph and Image Signal Processing (GISP) Lab (York University, Toronto, Canada)➢ Post-docs: Cheng Yang*, Xue Zhang*, Chinthaka Dinesh➢ Grad students: Saghar Bagheri, Tam Thuc Do, Yeganeh Gharedaghi, Niruhan Viswarupan➢ Co-supervised student: Yasaman Parhizkar➢ Visiting researchers: Sadid Sahami (NTHU), Fen Wang* (Xidian), Fei Chen* (Fudan)➢ Collaborators➢ Michael Brown, Andrew Eckford, Pirathayini Srikantha (York Univ., Canada)➢ Ivan V. Bajic (Simon Fraser Univ., Canada)➢ Antonio Ortega (Univ. of Southern California, USA)
➢ Stanley Chan (Purdue Univ., USA)➢ Wai-Tian Tan (Cisco, USA)➢ Phil Chou (Google, USA)➢ Tim Eadie (Growers Edge, USA)➢ Wei Hu (Peking Univ., China), Jin Zeng (Tongji Univ., China)➢ Vicky H. Zhao (Tsinghua Univ., China)➢ Chia-Wen Lin (NTHU, Taiwan)➢ Kazuya Kodama (NII, Japan), Yuichi Tanaka (Osaka Univ. Japan)* September 2018 to June 2020.

2

Gene Cheung (genec@yorku.ca)

Outline• GSP overview• Graph frequencies from eigen-pairs• Graph Learning• Positive, signed, directed, Hermitian graphs• Graph Filtering• Graph Sampling• GSP Analysis for GCNs
• Conclusion

3

Gene Cheung (genec@yorku.ca)

Outline• GSP overview• Graph frequencies from eigen-pairs• Graph Learning• Positive, signed, directed, Hermitian graphs• Graph Filtering• Graph Sampling• GSP Analysis for GCNs
• Conclusion

4

Gene Cheung (genec@yorku.ca)

Graph Signal Processing
Frequency analysis+

Graph kernels=

Graph Signal Processing

signal on graph kernel

Graph Signal Processing (GSP) studies spectral
analysis tools for signals residing on graphs.
[1] A. Ortega, P. Frossard, J. Kovacevic, J. M. F. Moura, and P. Vandergheynst, “Graph signal processing: Overview, challenges, and applications,” Proceedings ofthe IEEE, vol. 106, no. 5, pp. 808–828, 2018.
5

Gene Cheung (genec@yorku.ca)

Graph Spectrum
Graph Fourier modes: eigenvectors of graph Laplacian matrix L = D - W.
eigenvalues along diagonal

L= VV

T

1

w1, 2

1
2

1
3

4

Graph Fourier Transform (GFT)

eigenvectors in columns

2nd eigenvector

GFT defaults to DCT for un-weighted connected line.
GFT defaults to DFT for un-weighted connected circle.
1. Eigenvectors are (global) aggregates of (local) edge weights.

▪ More variations for larger eigenvalues.
2. Eigenvalues (≥ 0) as graph frequencies.

[1] G. Cheung, E. Magli, Y. Tanaka, M. Ng, "Graph Spectral Image Processing," Proceedings of the IEEE, vol. 106, no. 5, pp. 907-930, May 2018. .
6

Gene Cheung (genec@yorku.ca)…

8Graph Frequency Examples (US Temperature)
Weather stations from 100 most populated cities.
Graph connections from Delaunay Triangulation*.
Edge weights inverse proportional to distance.

location diff.
 − l −l 2 
 i j 2wi , j = exp
2

 




Edge weights

V1: DC component*https://en.wikipedia.org/wiki/Delaunay triangulation
7

Gene Cheung (genec@yorku.ca)

Graph Frequency Examples (US Temperature)
Weather stations from 100 most populated cities.
Graph connections from Delaunay Triangulation*.
Edge weights inverse proportional to distance.

location diff.
 − l −l 2 
 i j 2wi , j = exp
2

 




Edge weights

V2: 1st AC component

8

Gene Cheung (genec@yorku.ca)

Graph Frequency Examples (US Temperature)
Weather stations from 100 most populated cities.
Graph connections from Delaunay Triangulation*.
Edge weights inverse proportional to distance.

location diff.
 − l −l 2 
 i j 2wi , j = exp
2

 




Edge weights

V3: 2nd AC component

9

Gene Cheung (genec@yorku.ca)

Graph Frequency Examples (US Temperature)
Weather stations from 100 most populated cities.
Graph connections from Delaunay Triangulation*.
Edge weights inverse proportional to distance.

location diff.
 − l −l 2 
 i j 2wi , j = exp
2

 




Edge weights

V4: 9th AC component

10

Gene Cheung (genec@yorku.ca)

GSP and Graph-related Research
GSP: SP framework that unifies concepts from multiple fields.
Partial Differential
Eq’ns

MachineLearning

Laplace equation,
Diffusiongraphical model,
manifold learning,classifier learning

LaplaceBeltrami
operator

Graph Signal
Processing* (GSP)DSP
Max cut, graphtransformation

Combinatorial
Graph Theory
11

Computer Graphics

Gene Cheung (genec@yorku.ca)

spectral Computerclustering

Visioneigen-analysis ofgraph Laplacian,adjacency matrices

SpectralGraph Theory

Outline• GSP overview• Graph frequencies from eigen-pairs• Graph Learning• Positive, signed, directed, Hermitian graphs• Graph Filtering• Graph Sampling• GSP Analysis for GCNs
• Conclusion

12

Gene Cheung (genec@yorku.ca)

What is a good graph?
• Graph captures pairwise relationships.
1. Domain knowledge.
2. Correlations.
3. Feature distance.
• Graph Learning from Data:
1. Learn sparse inverse covariance matrix fromobservations [1].
▪

Graphical Lasso, CLIME.

2. Learn metric to determine feature distance [2].
[1] S. Bagheri, G. Cheung, A. Ortega, F. Wang, "Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO and
Projection," IEEE International Conference on Acoustics, Speech and Signal Processing, Toronto, Canada, June 2021 (best student paper finalist).
[2] C. Yang, G. Cheung, W. Hu, "Signed Graph Metric Learning via Gershgorin Disc Alignment," IEEE TPAMI, 2022.

13

Gene Cheung (genec@yorku.ca)

Signed Graphs• Previous works designed for positive graphs.
Temperature sensor network

3D geometry• Voting records in a Parliament

.

“Yes”

2

1
1

-1 “No”

“Yes”

1
3

2D image pixels

anti-correlation represented as negative edges [1].

+4
-1 “No”

1
1

−

2
-1
+

− 1

4

−

Signed graph-1

3[1] Chinthaka Dinesh, Saghar Bagheri, Gene Cheung, Ivan V. Bajic, "Linear-time Sampling on Signed Graphs via Gershgorin Disc Perfect Alignment," ICASSP’22, Singapore, May 2022.

14

Gene Cheung (genec@yorku.ca)

Directed Graphs(a) Following Network in Twitter(b) Paper Citation Network[1] Yuejiang Li, H. Vicky Zhao, Gene Cheung, "Eigen-Decomposition-Free Directed Graph Sampling via Gershgorin Disc Alignment," ICASSP’23, Rhodes, Greece, June 2023.

15

Gene Cheung (genec@yorku.ca)

Sparse Precision Matrix Estimation: GLASSO• Given empirical covariance matrix Σ, Graphical Lasso
computes positive-definite (PD) precision matrix Θ:• 1st and 2nd terms are likelihood.
• 3rd term promotes sparsity.
• Solved via block coordinate descent (BCD) algorithm.

[1] Friedman J, Hastie T, Tibshirani R. “Sparse inverse covariance estimation with the graphical lasso,” Biostatistics. 2008; 9(3): 432-441.

16

Gene Cheung (genec@yorku.ca)

Graph Laplacian Estimation• Assume precision matrix is:• Generalized graph Laplacian (GGLs),• Diagonally dominant generalized graph Laplacian (DDGLs), or• Combinatorial graph Laplacian (CGLs).
NOTE: Interpret precision
matrix as graph Laplacian• Given empirical covariance matrix S, computes Laplacian Θ:• K = S + H, H is regularization matrix.
• Lg(A) ensures Θ is GGL.
• Solved via block coordinate descent (BCD) algorithm.
[1] H. E. Egilmez, E. Pavez and A. Ortega, "Graph Learning From Data Under Laplacian and Structural Constraints," in IEEE
Journal of Selected Topics in Signal Processing, vol. 11, no. 6, pp. 825-841, Sept. 201717

Gene Cheung (genec@yorku.ca)

Graph Laplacian Estimation w/ Eigen-Structure Constraint• Key Assumption: graph Laplacian matrix L has
chosen first K eigenvectors.

1. Side info to derive first K e-vectors.
2. Fast computation of first K e-vectors.
3. Desire eigen-structure.

• Define convex coneof PSD matrices with same first K eigenvectors.
• Design projection operator toinspired by Gram-Schmidt procedure.
ത computes graph Laplacian 𝐋:• Given empirical covariance matrix 𝐂,• Solve via alternating BCD and projection algorithm.

[1] S. Bagheri, G. Cheung, A. Ortega, F. Wang, "Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO and
Projection," IEEE International Conference on Acoustics, Speech and Signal Processing, Toronto, Canada, June 2021 (best student paper finalist).

18

Gene Cheung (genec@yorku.ca)

Graph Laplacian Estimation for Complex Graph Signals• Complex graph signal: each node i has complex value 𝑥𝑖 ∈ ℂ.
• Hermitian Graph: directed graph with complex conjugate weights on opposite
directed edges between each node-pair.
• Hermitian adjacency, graph Laplacian matrices, w/ REAL eigenvalues (frequencies).

• Complex graph Laplacian
Learning (generalize CLIME):• Linear program to solve:• Define auxiliary var. to account for
real-/imaginary-parts.
[1] Chinthaka Dinesh, Junfei Wang, Gene Cheung, Pirathayini Srikantha, "Complex Graph Laplacian Regularizer for Inferencing Grid States," submitted toIEEE International Conference on Communications, Control, and Computing Technologies for Smart Grids (SmartGridComm), Glasgow, Scotland, October 2023.
[2] T. Cai, W. Liu, and X. Luo, “A constrained L1 minimization approach to sparse precision matrix estimation,” Journal of the American Statistical
Association, vol. 106, no. 494, pp. 594–607, 2011.

19

Gene Cheung (genec@yorku.ca)

Application: Image Coding• Transform Coding is integral component in image compression.
• Problem: DCT is fixed transform and does not adapt locally.

• Existing Work 1: Asymmetric Discrete Sine Transform(ADST) fits better prediction residuals [1].
• Existing Work 2: Karhunen-Loeve transform (KLT) adapts
well iff ∃ reliable empirical covariance matrix 𝐂ത [2].

[1] J. Han, A. Saxena, V. Melkote, and K. Rose, “Jointly optimized spatial prediction and block transform for video and image coding,” in IEEE Transactions on
Image Processing, April 2012, vol. 21, no.4, pp. 1874–1884.
[2] Ian Blanes and Joan Serra-Sagrista, “Pairwise orthogonal transform for spectral image coding,” IEEE Transactions on Geoscience and Remote Sensing, vol. 49,
no.3, pp. 961–972, 2011.

20

Gene Cheung (genec@yorku.ca)

Application: Image Coding• Key Idea: derive first K e-vectors from model, compute N-K e-vectors from data.
• Advantages:
1. Reduce degree of freedom when empirical covariance 𝐂ത is unreliable.
2. Parameter K is tunable depending on covariance reliability.
reference blocks
3. Reduce computation cost for first K transform coefficients.

• Disadvantage:
1. Larger computation cost than DCT.

target block[1] Saghar Bagheri, Tam Thuc Do, Gene Cheung, Antonio Ortega, “Hybrid Model-based / Data-driven Graph Transform for Image Coding,” IEEE Conference on Image
Processing, 2022.

21

Gene Cheung (genec@yorku.ca)

Image Coding: results (energy compaction)• Setting: WebP image codec [1]. DC4 intra-prediction mode. Improve prediction
residual coding of 4x4 block over default DCT.

Hybrid has medium
energy compaction[1] https://developers.google.com/speed/webp

22

Gene Cheung (genec@yorku.ca)

Outline• GSP overview• Graph frequencies from eigen-pairs• Graph Learning• Positive, signed, directed, Hermitian graphs• Graph Filtering• Graph Sampling• GSP Analysis for GCNs
• Conclusion

23

Gene Cheung (genec@yorku.ca)

Spectral Graph Filter for Image Denoising• Graph Laplacian Regularizer (GLR) 𝐱 𝑇 𝐋𝐱 is a smoothness measure.
• Denoising has simplest formation model 𝐲 = 𝐱 + 𝐳, thus formulation

min 𝐲 − 𝐱 22 + 𝜇 𝐱 𝑇 𝐋𝐱
𝐱𝐱 𝑇 𝐋𝐱 =𝐈 + 𝜇𝐋 𝐱 ∗ = 𝐲𝐱∗ =෍ 𝑤𝑖,𝑗 𝑥𝑖 − 𝑥𝑗(𝑖,𝑗)∈𝐸

𝐈 + 𝜇𝐋 −1 𝐲smooth signal

2= ෍ 𝜆𝑘 𝑥෤𝑘 2
𝑘low-pass signal

𝐱 ∗ = 𝐕diag 1 + 𝜇𝜆1 , 1 + 𝜇𝜆2 , … −1 𝐕 𝑇 𝐲low-pass filter!
[1] J. Pang, G. Cheung, "Graph Laplacian Regularization for Image Denoising: Analysis in the Continuous Domain," IEEE TIP, vol. 26, no.4, pp.1770-1785, April 2017.
[2] C. Tomasi and R. Manduchi, “Bilateral filtering for gray and color images,” IEEE ICCV, 1998.

24

Gene Cheung (genec@yorku.ca)

Spectral Graph Filter for Image Denoising• Graph Laplacian Regularizer (GLR) 𝐱 𝑇 𝐋𝐱 is a smoothness measure.
• Denoising has simplest formation model 𝐲 = 𝐱 + 𝐳, thus formulation

min 𝐲 − 𝐱 22 + 𝜇 𝐱 𝑇 𝐋𝐱𝐱

𝐈 + 𝜇𝐋 𝐱 ∗ = 𝐲pixel intensity diff.

pixel location diff.

 − x − x 2   − l −l 2 
 i j 2  i j 2wi , j = exp
exp
2
2


 1
  2   filter weights
Bilateral• To promote Piecewise Smoothness (PWS), 𝐋 𝐱 is signal-dependent:• Fix L and solve unconstrained QP each iteration.

min 𝐲 − 𝐱 22 + 𝜇 𝐱 𝑇 𝐋 𝐱 𝐱𝐱

Signal-dependent GLR[1] J. Pang, G. Cheung, "Graph Laplacian Regularization for Image Denoising: Analysis in the Continuous Domain," IEEE TIP, April 2017.
[2] C. Tomasi and R. Manduchi, “Bilateral filtering for gray and color images,” IEEE ICCV, 1998.

25

Gene Cheung (genec@yorku.ca)

OGLR Denoising Results: visual comparison• Subjective comparisons (  I = 40 )Original

Noisy, 16.48 dB

K-SVD, 26.84 dB

BM3D, 27.99 dB

PLOW, 28.11 dB

OGLR, 28.35 dB[1] J. Pang, G. Cheung, "Graph Laplacian Regularization for Image Denoising: Analysis in the Continuous Domain," IEEE TIP, vol. 26, no.4, pp.1770-1785, April 2017.

26

Gene Cheung (genec@yorku.ca)

OGLR Denoising Results: visual comparison• Subjective comparisons (  I = 30 )Original

Noisy, 18.66 dB BM3D, 33.26 dB NLGBT, 33.41dB OGLR, 34.32 dB[1] J. Pang, G. Cheung, "Graph Laplacian Regularization for Image Denoising: Analysis in the Continuous Domain," IEEE TIP, vol. 26, no.4, pp.1770-1785, April 2017.

27

Gene Cheung (genec@yorku.ca)

Point Cloud Denoising: Graph filter design

Method:• Construct similarity graphbased on surface normals.
• Optimize graph filter
based on noise statistics.

[1] C. Dinesh, G. Cheung, I. Bajic, "Point Cloud Denoising via Feature Graph Laplacian Regularization," vol. 29, pp. 4143-4158, IEEE TIP, January 2020..
28

Gene Cheung (genec@yorku.ca)

Point Cloud Video Super-Resolution• Problem: Acquired point cloud
video has low point density.
• Solution:• Find similar 3D patches inconsecutive frames.
• Super-resolve patches inconsecutive frames via GLR.

[1] Chinthaka Dinesh, Gene Cheung, Ivan V. Bajic, "Point Cloud Video Super-Resolution via Partial Point Coupling and Graph Smoothness," IEEE TIP, June 2022.
29

Gene Cheung (genec@yorku.ca)

Point Cloud Video Super-Resolution[1] Chinthaka Dinesh, Gene Cheung, Ivan V. Bajic, "Point Cloud Video Super-Resolution via Partial Point Coupling and Graph Smoothness," IEEE Transactions
on Image Processing, vol. 31, pp.4117-4132, June 2022.
30

Gene Cheung (genec@yorku.ca)

Point Cloud Video Super-Resolution[1] Chinthaka Dinesh, Gene Cheung, Ivan V. Bajic, "Point Cloud Video Super-Resolution via Partial Point Coupling and Graph Smoothness," IEEE Transactions
on Image Processing, vol. 31, pp.4117-4132, June 2022.
31

Gene Cheung (genec@yorku.ca)

Outline• GSP overview• Graph frequencies from eigen-pairs• Graph Learning• Positive, signed, directed, Hermitian graphs• Graph Filtering• Graph Sampling• GSP Analysis for GCNs
• Conclusion

32

Gene Cheung (genec@yorku.ca)

Motivation: graph sampling
Graph sampling [1]: Choose a node subset, so that theentire signal can be reconstructed.
graph signal• Graph sampling strategies extend Nyquist samplingto graph data kernel.
nodes• Bandlimited or smooth signal assumption.

edges[1] Y. Tanaka et al., “Sampling signals on graphs: From theory to applications,” IEEE Signal Process. Mag., vol. 37, no. 6, pp. 14–30, 2020.

33

Gene Cheung (genec@yorku.ca)

Existing Work: graph frequencies• Mainly focus on undirected graph.
• Symmetric Graph Laplacian 𝐋 = 𝐔𝚲𝐔⊤
• Categories• Bandlimited prior[1-3]: 𝐱 = σ𝑀
෥𝑖 𝐮𝑖
𝑖=1 𝑥
• Smoothness prior[4-5]: smaller 𝐱 ⊤ 𝐋𝐱

Not obvious for directed graphs!
• Directed graph → Asymmetric 𝐋• Complex graph frequency

Im

Frequency - 1

Different Frequencies
Re with same magnitude!
Frequency - 2• Meaningless quadratic form 𝐱 ⊤ 𝐋𝐱

[1] S. Chen, R. Varma, A. Sandryhaila, and J. Kovacevic, “Discrete signal processing on graphs: Sampling theory,” TSP, vol. 63, no. 24, pp. 6510– 6523, 2015.
[2] A. Anis, A. Gadde, and A. Ortega, “Efficient sampling set selection for bandlimited graph signals using graph spectral proxies,” TSP, vol. 64, no. 14, pp. 3775–3789, 2016.
[3] A. Sakiyama, Y. Tanaka, T. Tanaka, and A. Ortega, “Eigendecomposition-free sampling set selection for graph signals,” TSP, vol. 67, no. 10, pp. 2679–2692, 2019.
[4] Y. Tanaka and Y. C. Eldar, “Generalized sampling on graphs with subspace and smoothness priors,” TSP, vol. 68, pp. 2272–2286, 2020.
[5] Y. Bai, F. Wang, G. Cheung, Y. Nakatsukasa, and W. Gao, “Fast graph sampling set selection using Gershgorin disc alignment,” TSP, vol. 68, pp. 2419–2434, 2020.

34

Gene Cheung (genec@yorku.ca)

Existing Work: computation
Existing graph sampling methods

Eigen-decomposition-based methods [1,2]Computational expensive

eigen-decomposition-free methods
Spectral proxies (SP) [3]
Neumann series (NS) [4]Localization operator (LO) [5]
Gershgorin disc alignment (GDA) [6]Fast method for graph sampling!
[1] M. Tsitsvero, S. Barbarossa, and P. Di Lorenzo, “Signals on graphs: Uncertainty principle and sampling,” IEEE TSP, vol. 64, no. 18, pp. 4845–4860, 2016.
[2] S. Chen, R. Varma, A. Sandryhaila, and J. Kovavcevic, “Discrete signal processing on graphs: Sampling theory,” IEEE TSP, vol. 63, no. 24, pp. 6510–6523, 2015.
[3] A. Anis et al., “Efficient sampling set selection for bandlimited graph signals using graph spectral proxies,” IEEE TSP, vol. 64, no. 14, pp.3775–3789, 2016.
[4] F. Wang et al., “Low-complexity graph sampling with noise and signal reconstruction via Neumann series,” IEEE TSP, vol. 67, no. 21, pp. 5511–5526, 2019.
[5] A. Sakiyama, Y. Tanaka, T. Tanaka, and A. Ortega, “Eigendecomposition-free sampling set selection for graph signals,” IEEE TSP, vol. 67, no. 10, pp. 2679–2692, 2019.
[6] Y. Bai, F. Wang, G. Cheung, Y. Nakatsukasa, and W. Gao, Fast graph sampling set selection using Gershgorin disc alignment,” IEEE TSP, vol. 68, pp. 2419–2434, 2020.

35

Gene Cheung (genec@yorku.ca)

Signal Reconstruction from Samples▪ Signal Model:

observation

sampling matrix
desired signal

𝐲 = 𝐇𝐱 + 𝐯

noise▪ Signal prior is graph Laplacian regularizer (GLR):
2𝑇
𝐱 Lx = ෍ 𝑤𝑖,𝑗 𝑥𝑖 − 𝑥𝑗 = ෍ 𝜆𝑘 𝑥෤𝑘2𝑖,𝑗𝑘
signal smooth w.r.t. graph▪ MAP Formulation:
signal priorfidelity term

1

2

1
4

3

Sample set {2, 4}
𝐇=signal contains
mostly low graph freq.

1

1

0 1 0
0 0 0

0
0
𝐇T𝐇 =
0
0

0
1
0
0

0
0
0
0

min 𝐲 − 𝐇𝐱 22 + 𝜇 𝐱 𝑇 𝐋𝐱
𝐱

𝐇𝑇𝐇 + 𝜇𝐋 𝐱 ∗ = 𝐲linear system of eqn’s solved using conjugate gradient[1] Y. Bai, F. Wang, G. Cheung, Y. Nakatsukasa, W. Gao, "Fast Graph Sampling Set Selection Using Gershgorin Disc Alignment,"
vol. 68, pp. 2419-2434, IEEE Transactions on Signal Processing, March 2020.
36

Gene Cheung (genec@yorku.ca)

0
1
0
0
0
1

Stability of Linear System• Examine solution’s linear system:

1

𝐇𝑇𝐇 + 𝜇𝐋 𝐱 ∗ = 𝐲coefficient matrix B• Stability depends on condition number (λmax/ λmin) of B.
• λmax is upper-bounded by 1+μ2*dmax.

1𝜆𝑚𝑖𝑛 𝐁

෥
𝐋 𝐱+𝐧

2+

෥ 2
𝐧

2

[1] Y. Bai, F. Wang, G. Cheung, Y. Nakatsukasa, W. Gao, "Fast Graph Sampling Set Selection Using Gershgorin Disc Alignment,"
vol. 68, pp. 2419-2434, IEEE Transactions on Signal Processing, March 2020.
37

Gene Cheung (genec@yorku.ca)

2

1
4

3

1 −1 00−1 2 −1 0𝐋=
0 −1 2 −1
0
0 −1 1

Goal: select H to maximize 𝜆min 𝐁 (E-optimality criterion)
Also minimizes worst-case MSE:𝐱ො − 𝐱 2 ≤ 𝜇

1

1

0
0
𝐇T𝐇 =
0
0

0
1
0
0

0
0
0
0

0
0
0
1

Sample set {2, 4}

Gershgorin Circle Theorem• GCT relates matrix entries to bounds of eigenvalues.

is lower-bounded by the smallest left-end of Gershgorin discs:[1] R. S. Varga, Gershgorin and his circles, Springer, 2004.

38

Gene Cheung (genec@yorku.ca)

GDA Sampling for Positive Graphs• We focus on maximizing 𝜆−min 𝐁 :
maxT

𝐇,𝐒 | Tr 𝐇 𝐇 ≤𝐾

−1
𝜆−min 𝐒𝐁𝐒diagonal scaling matrix• Given Gershgorin disc left-ends of is at the same exact value,
GDA graph sampling [1]: Select samples to max smallest disc leftend 𝜆−min 𝐁 of coefficient matrix B via:
• Disc shifting (choosing sample i).
• Disc scaling (estimating influence on neighbors given sample i).

[1] Y. Bai, F.Wang, G. Cheung, Y. Nakatsukasa, and W. Gao, “Fast graph sampling set selection using gershgorin disc alignment," IEEE TSP, 2020.

39

Gene Cheung (genec@yorku.ca)

Results: positive graph sampling (speed)• Running time comparisons on two different graphs.
(a) Random sensor raph. (b) Community graph.

40

Gene Cheung (genec@yorku.ca)

Results: community graph sampling• Visualization of selected nodes on the community graph (N = 500,K = 11). Black circles denotesampled nodes. (a) Original graph. (b) Random [28].(c) E-optimal [25]. (d) SP [16]. (e) MFN [23].
(f) MIA [20]. (g) Ed-free [9]. (h) The proposed BS-GDA.

41

Gene Cheung (genec@yorku.ca)

Results: signed graph sampling

For the Canadian dataset, our scheme reduced the lowest MSE among competitor schemes by
22.2%, 18.2%, 13.5%, 10.4%, for sampling budget 10, 20, 30, 40.
[1] Chinthaka Dinesh, Saghar Bagheri, Gene Cheung, Ivan V. Bajic, "Linear-time Sampling on Signed Graphs via Gershgorin Disc Perfect Alignment," ICASSP, 2022.

42

Gene Cheung (genec@yorku.ca)

Results: directed graph sampling(a) Reconstruction MSE on Erdös-Rényi
Random Graph. GS = Diffusion Signal(b) Running Time on Erdös-Rényi Random Graph• GDA-Direct achieves lowest Recon. MSE• Decreases MSE by 11.9%• GDA-Direct is the fastest method• Speeds up by 1.4 times.

[1] Yuejiang Li, H. Vicky Zhao, Gene Cheung, "Eigen-Decomposition-Free Directed Graph Sampling via Gershgorin Disc Alignment," ICASSP’23, Rhodes, Greece, June 2023.

43

Gene Cheung (genec@yorku.ca)

Graph Sampling Application 1: video summarization• Problem: Select Keyframes to summarize short video.
• Solution: Construct path graph from GoogLeNet features, choose graph samples.

[1] S. Sahami, G. Cheung, C.-W. Lin, "Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment," IEEE ICASSP, May 2022.
44

Gene Cheung (genec@yorku.ca)

Graph Sampling Application 2: matrix completion• Pre-select a subset of matrix entries for sampling to maximize matrix completion fidelity.
• Challenge: select sampling set Ω to maximize λmin ofgraph Laplacians for row / column graphs• RMSE of different sampling methods for MC on Synthetic Netflix. The matrix was completed using
the double graph smoothness based method.

[1] F. Wang, Y. Wang, G. Cheung, C. Yang, "Graph Sampling for Matrix Completion Using Recurrent Gershgorin Disc Shift," vol.
68, pp. 1814-2829, IEEE Transactions on Signal Processing, April 2020.
45

Gene Cheung (genec@yorku.ca)

Graph Sampling Application 3: 3D point cloud sub-sampling• Reduce 3D point cloud size by sub-sampling while preserving the overall object shape.
• Challenge: select sampling matrix H to maximize λmin ofgeneralized graph Laplacian• SR reconstruction results from diff. methods of sub-sampled Bunny under 0.2 sub-sampling ratio.

[1] C. Dinesh, G. Cheung, I. V. Bajic, "Point Cloud Sampling via Graph Balancing and Gershgorin Disc Alignment," IEEE
Transactions on Pattern Analysis and Machine Intelligence, January 2023.
46

Gene Cheung (genec@yorku.ca)

Outline• GSP overview• Graph frequencies from eigen-pairs• Graph Learning• Positive, signed, directed, Hermitian graphs• Graph Filtering• Graph Sampling• GSP Analysis for GCNs
• Conclusion

47

Gene Cheung (genec@yorku.ca)

Motivation: graph sparsification
Signal samples

Edges
Nodes

Crop Yield Prediction:• Reduce price fluctuation.
• Stabilize food supply.
• Minimize uncertainty for farmers.

SOTA methods use GCNs:• Dense underlying graph kernel can be used.
• Requires long training and execution time.

[1] Saghar Bagheri, Gene Cheung, Timothy Eadie, "Graph Sparsification for GCN towards Optimal Crop Yield Prediction," International Geoscience and Remote
Sensing Symposium (IGARSS), Pasadena, CA, July 2023.

48

Gene Cheung (genec@yorku.ca)

Graph Sparsification: Fiedler number
Fiedler number:• Second smallest eigenvalue 𝜆2 of the Laplacian matrix L.
• Known to quantify “connectedness” of underlying graph.

Fast method:• In each iteration, remove edge that induces min change in 𝜆2 .
ሚ = 𝐋 + 𝐄 𝑚,𝑛 with edge (m, n) removed.
• Modified Laplacian 𝐋• Choose edge such that

[1] Saghar Bagheri, Gene Cheung, Timothy Eadie, "Graph Sparsification for GCN towards Optimal Crop Yield Prediction," International Geoscience and Remote
Sensing Symposium (IGARSS), Pasadena, CA, July 2023.

49

Gene Cheung (genec@yorku.ca)

Motivation: graph learning with spectrum prior
Stacking more GCN layers → node representations become indistinguishable [1]Q: How to alleviate over-smoothing?

Layer 1

Layer 2

Layer 5Layer 7Layer 15t-SNE visualization of output features from GCNs[2] w/ different layers for Cora dataset[1] Qimai Li, Zhichao Han, and Xiao-Ming Wu, “Deeper insights into graph convolutional networks for semi-supervised learning,” AAAI, 2018.
[2] Thomas N. Kipf and Max Welling, “Semi-supervised lassification with graph convolutional networks,” ICLR, 2017.
[3] Jin Zeng, Yang Liu, Gene Cheung, Wei Hu, "Sparse Graph Learning with Spectrum Prior for Deep Graph Convolutional Networks," ICASSP, June 2023.

50

Gene Cheung (genec@yorku.ca)

Oversmoothing in GCNs
Multilayer GCN• 𝒢: Undirected graph with 𝑁 nodes• Output from GCN associated with 𝒢 with 𝐿 layers: 𝑓 = 𝑓𝐿 ∘ ⋯ ∘ 𝑓1
• 𝑙-th layer output with input 𝐗: 𝑓𝑙 𝐗 ≜ 𝜎( 𝐏 𝐗 𝚯 𝑙 )Activation Graph
operator operator

FilterweightOver-smoothing in GCNሚ =𝐈−𝐏• ℳ: subspace spanned by 1st eigenvectors of normalized graph Laplacian 𝐋• More GCN layers → 𝑓 𝐗 converges to ℳ[1]Uninformative signals

dℳ 𝑓𝑙 𝐗
L2 distance to ℳ

≤ 𝑟 ∗ dℳ 𝐗
Convergence ratecharacterized by graph spectrum[1] Kenta Oono and Taiji Suzuki, “Graph neural networks exponentially lose expressive power for node classification,” ICLR, 2020.

51

Gene Cheung (genec@yorku.ca)

Sparse Graph Learning with Spectrum Prior
SGL-GCN: Sparse Graph Learning with Spectrum Prior for GCN
min Tr 𝐋𝐂 − logdet 𝐋 + ρ||𝐋||1 + σTr(𝐋)•σσ = ln52

𝐗 smooth wrt L

dℳ = 0

σ=0
1+𝑀 S
1−𝑀 S

frequency

frequency component

GLASSO
Intensity of

frequency component

Weight σ:Intensity of𝐋≥𝟎Spectrum prior•

𝐗 unsmooth wrt L…
large dℳ frequency
large σwhere 𝑀 S is smoothness, S is given data
Gene Cheung (genec@yorku.ca)

Solve via block
coordinate
descent (BCD)
Use output L for
GCN

Results: robust graph learning
Validation of weight computation

METR-LA Dataset
•

•

✗Acc

Task: predict traffic speed given
past 50 mins data (sampled
every 5 mins)
C: observations in training data

9.33e-3@Layer4✔ Over-smoothing✔ Acc
9. 51e-3@Layer7✔ Over-smoothing✗ Acc

Proposed SGL-GCN••

Validated weight 𝜎Higher acc w/ deeper GCN

[1]

[2]

[1] Yu Rong, Wenbing Huang, et al.,“Dropedge: Towards deep graph convolutional networks on node classification,” ICLR, 2020.
[2] Kenta Oono and Taiji Suzuki, “Graph neural networks exponentially lose expressive power for node classification,” ICLR, 2020.

53

9.43e-3@Layer2✗Over-smoothing

Gene Cheung (genec@yorku.ca)

Outline• GSP overview• Graph frequencies from eigen-pairs• Graph Learning• Positive, signed, directed, Hermitian graphs• Graph Filtering• Graph Sampling• GSP Analysis for GCNs
• Conclusion

54

Gene Cheung (genec@yorku.ca)

Conclusion• GSP analyzes and processes discrete signals on graphs.
• Graphs captures pairwise relationships:• Positive, signed, directed, Hermitian graphs.
• Graph Learning• Statistical sparse graph learning, metric learning• Graph Filtering• Spectral filters in graph spectrum• Graph Sampling• Fast algorithms based on Gershgorin circle theorem• GSP analysis for GCNs
• Graph spectrum affects performance, oversmoothing

55

Gene Cheung (genec@yorku.ca)

Applications:
Image coding,denoising, deblurring,interpolation, contrast
enhancement, lightfield image denoising,
3D point cloud
denoising, subsampling, superresolution, matrix
completion, semisupervised classifier
learning, video
summarization, crop
yield prediction

Contact Info
• Homepage:https://www.eecs.yorku.ca/~genec/index.html• E-mail:genec@yorku.ca• New book:
G. Cheung, E. Magli, (edited) Graph Spectral
Image Processing, ISTE/Wiley, August 2021.
56

Gene Cheung (genec@yorku.ca)