Spectral Graph Learning: Algorithm and Application
to Image Coding & Graph Convolutional Nets
Gene Cheung
York UniversityToronto, Canada

February 23, 2022

Acknowledgement• Graph and Image Signal Processing (GISP) Lab (York University, Toronto, Canada)➢ Post-docs: Cheng Yang*, Xue Zhang, Chinthaka Dinesh➢ Grad students: Saghar Bagheri, Fengbo Lan, Huy Vu, Tam Thuc Do➢ Visiting researchers: Weng-tai Su, Sadid Sahami (NTHU), Fen Wang (Xidian)➢ Collaborators➢ Richard Wildes, Michael Brown (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)
➢ Jiahao Pang, Dong Tian (InterDigital, USA)➢ Phil Chou (Google, USA)
➢ Yuji Nakatsukasa (Oxford Univ., UK)➢ Thomas Maugey (Inria, France)➢ Wei Hu (Peking Univ., China), Jin Zeng (Tongji Univ., China)➢ Chia-Wen Lin (NTHU, Taiwan)➢ Kazuya Kodama (NII, Japan)➢ Yonina C. Eldar (Weizmann Inst. of Science, Israel)* September 2018 to June 2020.
2Gene Cheung (genec@yorku.ca)

Graph Signal ProcessingFrequency 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.
3

Gene Cheung (genec@yorku.ca)

Graph Spectrum
degree matrix
adjacency matrix

Graph Fourier modes: eigenvectors of graph Laplacian matrix L = D - W.
eigenvectors 𝐯𝑘 in columns

eigenvalues 𝜆𝑘 along diagonal
1𝐋 = 𝐕𝚵𝐕 𝑇 = ෍ 𝜆𝑘 𝐯𝑘 𝐯𝑘𝑇Graph Fourier Transform (GFT)

w1, 2

12

1
3

4

sum of rank-1 matrices𝑘

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].

[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. .
4

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
5

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

6

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

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

V4: 9th AC component

8

Gene Cheung (genec@yorku.ca)

What is a good graph?
• Graph captures pairwise relationships.
1. Domain knowledge.
2. Correlations.
3. Feature distance.
• Approaches:
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 andProjection," 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, June 2021.
9Gene 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.
10Gene 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 precisionmatrix 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. 201711

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 andProjection," IEEE International Conference on Acoustics, Speech and Signal Processing, Toronto, Canada, June 2021 (best student paper finalist).
12Gene Cheung (genec@yorku.ca)

Preliminaries: inner product, Hilbert Space• Define a vector space of real, symmetric matrices 𝑺 = 𝐋 ∈ R𝑁×𝑁 |𝐋𝑇 = 𝐋 .
• Define inner product for 𝐀, 𝐁 ∈ 𝑺:

• Hilbert space 𝑯 is vector space 𝑺 with inner product.
• Define subspace 𝑯+ of positive semi-definite (PSD) matrices:convex cone𝐾+• Define subspace 𝑯+𝐮 ⊂ 𝑯 PSD matrices sharing first K eigenvectors 𝐮𝑘 𝑘=1 .

convex cone

13

Gene Cheung (genec@yorku.ca)

Projection to Convex Cone 𝑯+𝐮: 𝒊 ≤ 𝑲ഥGiven empirical covariance matrix 𝐂,• 1st eigenvector 𝐮1 of Laplacian 𝐋:• Compute last eigenvalue 𝜇𝑁 for target 𝐂 = 𝐋−𝟏 asത 𝐮1 𝐮1𝑇
𝜇𝑁 = 𝐂,Thus, 1st eigen-pair

1, 𝐮1𝜇𝑁for L• Compute residual 𝐄𝑁 = 𝐂ത − 𝜇𝑁 𝐮1 𝐮1𝑇•

2nd eigenvector 𝐮2 of 𝐋:• Compute second last eigenvalue 𝜇𝑁−1 for target 𝐂 as

𝜇𝑁−1 = min 𝐄𝑁 , 𝐮2 𝐮𝑇2 , 𝜇𝑁
• Compute residual 𝐄𝑁−1 = 𝐄𝑁 − 𝜇𝑁−1 𝐮2 𝐮𝑇2
14

Gene Cheung (genec@yorku.ca)

Thus, 2nd eigen-pair

1𝜇𝑁−1, 𝐮2 for L

Projection to Convex Cone 𝑯+𝐮 :𝒊>𝑲
• Compute next eigenvector 𝐯𝑖 for 𝐋:
s.t. 𝐯𝑖𝑇 𝐮𝑘 = 0,𝑇max 𝐄𝑁−𝑖+2 , 𝐯𝑖 𝐯𝑖𝑇𝐯𝑖 𝐯𝑗 = 0,𝐯𝑖𝐯𝑖 = 1

𝑘 = 1, … , 𝐾
𝑗 = 𝐾 + 1, … , 𝑖 − 1• NP-hard. See [1] for fast approx.

• Compute eigenvalue 𝜇𝑁−𝑖+1 :𝜇𝑁−𝑖+1 = min𝐄𝑁−𝑖+2 , 𝐯𝑖 𝐯𝑖𝑇 , 𝜇𝑁−𝑖+2Thus, ith eigen-pair

1𝜇𝑁−𝑖+1• Compute residual: 𝐄𝑁−𝑖+1 = 𝐄𝑁−𝑖+2 − 𝜇𝑁−𝑖+1 𝐯𝑖 𝐯𝑖𝑇[1] S. Bagheri, G. Cheung, A. Ortega, F. Wang, "Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO andProjection," IEEE International Conference on Acoustics, Speech and Signal Processing, Toronto, Canada, June 2021 (best student paper finalist).
15Gene Cheung (genec@yorku.ca), 𝐯𝑖 for LGLASSO + Projection• Modify GLASSO to• Dual of GLASSO is• Algorithm:
1. Iteratively updating one row / column of 𝑪.
2. Project 𝐋 = 𝐂−1 to convex cone 𝑯+𝐮 using projection operator.
3. Repeat till convergence.
[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: results• Randomly located 20 nodes in 2D space. Use Erdos-Renyi model to determine connectivity withprobability 0.6. Compute edge weights using Gaussian kernel. Remove weights <0.75. Flip sign ofeach edge with probability 0.5. K=1.
• (a) Ground Truth Laplacian L , (b) Proposed Proj-Lasso with K = 1, (c) GLASSO, (d) DDGL and (e)GL-SigRep .

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

Application 1: 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 onImage 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.
18

Gene Cheung (genec@yorku.ca)

Application 1: 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.

• Disadvantages:
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,” submitted to IEEE
Conference on Image Processing, 2022.
19

Gene Cheung (genec@yorku.ca)

Image Coding: results 1 (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
20

Gene Cheung (genec@yorku.ca)

Image Coding: results 2 (error variance)• Setting: WebP image codec [1]. DC4 intra-prediction mode. Improve prediction
residual coding of 4x4 block over default DCT.
smaller error variancethan KLT
smallest error variance[1] https://developers.google.com/speed/webp
21

Gene Cheung (genec@yorku.ca)

Application 2: Filter Training in GCN• Graph convolutional nets (GCN) performs graph filtering and pointwise nonlinear operation (e.g., ReLU) in a sequence of neural layers.
• Problem: GCN starts to oversmooth as the number of layers grows [1].
• Analysis: GCN output approaches a subspace spanned by 1st eigenvector ofሚ with convergence rate ∝ “eigen-gap” [2].
normalized graph Laplacian 𝐋• Existing Solution: randomly drop edges at layers for sparse graph [3].
[1] G. Li, M. Muller, A. Thabet, and B. Ghanem, “DeepGCNs: Can GCNs go as deep as CNNs?” in Proceedings of the IEEE/CVF ICCV, 2019, pp. 9267–9276.
[2] K. Oono and T. Suzuki, “Graph neural networks exponentially lose expressive power for node classification,” in International Conf. on Learning Rep., 2020.
[3] Y. Rong et al., “DropEdge: Towards deep graph convolutional networks on node classification,” in International Conf. on Learning Rep., 2020.
22

Gene Cheung (genec@yorku.ca)

Spectral Graph Learning for Filter Training in GCN• Key Idea: learn Laplacian 𝐋 from empirical covariance 𝐂ത w/ desired eigen-gap.
• Algorithm:
1. Compute last eigenvalue 𝜇𝑁 for target 𝐂 = 𝐋−𝟏 asത 𝐱𝐱 𝑇𝜇𝑁 = 𝐂,avg. signalThus, 1st eigen-pair

1,𝐱𝜇𝑁for L

2. Compute residual 𝐄𝑁 = 𝐂ത − 𝜇𝑁 𝐱1 𝐱1𝑇3. Approximate 2nd eigenvector 𝐯2max 𝐄𝑁 , 𝐯2 𝐯2𝑇𝐯2s.t. 𝐯2𝑇 𝐱 = 0𝐯2 =1

4. Compute 2nd last eigenvalue 𝜇𝑁−1 for target 𝐂 = 𝐋−𝟏 as

𝜇𝑁−1 = max 𝐄𝑁 , 𝐯2 𝐯2𝑇 , 𝜇𝑁 − 𝜅eigen-gap!

[1] Jin Zeng, Saghar Bagheri, Yang Liu, Gene Cheung, Wei Hu, "Sparse Graph Learning with Eigen-gap for Spectral Filter Training in Graph Convolutional
Networks," submitted to EUSIPCO'22, Belgrade, Serbia, August 2022.
23

Gene Cheung (genec@yorku.ca)

GCN Training: results 1• Data: METR-LA contains traffic speed data in 4 months from 207 sensors in LA County.
• Task: predict current traffic speed using speed data from 50 to 5 minutes ago as input.

• Smaller gap, larger optimal layer.
• Smaller gap, small loss value.

24

Gene Cheung (genec@yorku.ca)

GCN Training: results 2• Compare Gap=1 to DropEdge [1] with drop rate = 0, 0.3, 0.5.

• SGL has larger optimal layer.
• SGL has small loss value.

[1] Y. Rong et al., “Dropedge: Towards deep graph convolutional networks on node classification,” in International Conf. on Learning Rep., 2020.
25

Gene Cheung (genec@yorku.ca)

Conclusion• Graph Signal Processing (GSP) studies signals on graphs.
• Graph learning is crucial first step for GSP.

• Spectral graph learning can optimize eigen-structures.
• Image coding.
• Filtering training in GCN.
• Future work:• Tighter integration between GSP and GCN/GNN.

26

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.
27

Gene Cheung (genec@yorku.ca)