Efficient Signed Graph Sampling via
Balancing & Gershgorin Disc Perfect Alignment
Gene Cheung
York University
Toronto, Canada

July 28, 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: Sadid Sahami (NTHU), Fen Wang (Xidian)➢ Collaborators➢ 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)➢ Wei Hu (Peking Univ., China), Jin Zeng (Tongji Univ., China)➢ Chia-Wen Lin (NTHU, Taiwan)➢ Kazuya Kodama (NII, Japan)* September 2018 to June 2020.
2

Gene Cheung (genec@yorku.ca)

Outline••••

Overview of Graph Signal Processing (GSP)
Motivation, related work
Key Idea: Balanced Signed GraphFrequencies• 1D data kernel (DCT)• Positive line graph• Balanced signed graph• Graph Estimation• Signed Graph Sampling Strategy• Sampling objective• Gershgorin circle theorem, GDA-based sampling• 3-step signed graph sampling recipe• Results• Conclusion

3Gene 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.
4

Gene Cheung (genec@yorku.ca)

Motivation
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.
5

Gene Cheung (genec@yorku.ca)

Existing WorkExisting 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]
Gershgoring disc alignment (GDA) [6]Positive graphs only!
[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 Neumannseries,” 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.
6Gene Cheung (genec@yorku.ca)

Motivation 2• 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, 2].

+4-1 “No”

11−2-1+− 14−-1

3[1] W.-T. Su, G. Cheung, and C.-W. Lin, “Graph Fourier transform with negative edges for depth image coding,” IEEE ICIP, 2017, pp. 1682–1686.
[2] G. Cheung et al., “Robust semisupervised graph classifier learning with negative edge weights,” IEEE TSIPN, vol. 4, no. 4, pp. 712–726, 2018.
7

Gene Cheung (genec@yorku.ca)

Signed graphKey Idea
Balanced Signed Graph [1]: a signed graph with no cycles of odd number ofnegative edges.
• A natural definition of graph frequencies.
• more amenable to efficient sampling than unbalanced graphs.

[1] D. Easley and J. Kleinberg, “Networks, crowds, and markets: Reasoning about a Highly Connected World”, vol. 8, Cambridge university press, 2010.
8

Gene Cheung (genec@yorku.ca)

Outline••••

Overview of Graph Signal Processing (GSP)
Motivation, related work
Key Idea: Balanced Signed GraphFrequencies• 1D data kernel (DCT)• Positive line graph• Balanced signed graph• Graph Estimation• Signed Graph Sampling Strategy• Sampling objective• Gershgorin circle theorem, GDA-based sampling• 3-step signed graph sampling recipe• Results• Conclusion

9Gene Cheung (genec@yorku.ca)

Definitions in GSP• Adjacency matrix (W):

11Edge weight between node 𝑖 and node 𝑗• Diagonal Degree matrix (D):• Combinatorial graph Laplacian matrix (L):0 1
𝐖= 1 00 10
101 0
𝐃= 0 20 0300
1

1 −1 0
𝐋 = −1 2 −10 −1 11• Generalized graph Laplacian Matrix:

11To account for self-loops2
L = −10[1] A. Ortega et al., “Graph signal processing: Overview, challenges, and applications,” Proc. IEEE, vol. 106, no. 5, pp. 808–828, May 2018.
101

2

Gene Cheung (genec@yorku.ca)

12−1
2−10−113

Frequencies for 1D Regular Kernel
DCT-1

Discrete Cosine Transform (DCT)𝑎𝑐• Eigenvectors of 2nd difference matrices:
Minimize Rayleigh quotientboundary rows

• Two boundary conditions:• Dirichlet (signal 0 at boundary, anti-symmetric extension)• Neumann (derivative 0 at boundary, symmetric extension)• Two locations to apply conditions:• Midpoint (half-way bet’n discrete samples)• Meshpoint (at discrete samples)[1] G. Strang, “The discrete cosine transform,” SIAM review, vol. 41, no.1, pp. 135–147, 1999.
11Gene Cheung (genec@yorku.ca)

2 −2𝑏=−2 2
𝑑DCT-2
𝑎𝑐

1 −1
𝑏=
−1 1
𝑑DCT-3𝑎𝑐

2 −2
𝑏=−1 2𝑑DCT-4𝑎𝑐

1 −1
𝑏=−1 3𝑑Frequencies for Positive Line Graph• Graph Laplacian matrix:
0w0,1

1w1,2

2w2,3

3boundary rows

• Applying interior equation to node 1:• Dirichlet (signal 0 at boundary) at midpoint:

2w0,1

1An external node connected with weight w leads to a self-loopof weight 2w at corresponding boundary node.
Eigenvectors of a generalized graph Laplacian L for a positivegraph G with self-loops are graph frequency components.
12Gene Cheung (genec@yorku.ca)

w1,2

2

w2,3

3

Frequencies for Balanced Signed Graph• Cartwright-Harary Theorem [2]: A signed graph is balanced iff nodes can be colored to red andblue, s.t. a positive (negative) edge connects nodes of the same (different) color.

• Mapping bet’n balanced signed graph G and positive graph G’:• Graph Laplacians related by similarity transform: (same e-val)

Eigenvectors of a generalized graph Laplacian L for a balanced
signed graph G with self-loops are graph frequency components.
[1] D. Easley and J. Kleinberg, “Networks, crowds, and markets: Reasoning about a Highly Connected World”, vol. 8, Cambridge university press, 2010.
13

Gene Cheung (genec@yorku.ca)

Outline••••

Overview of Graph Signal Processing (GSP)
Motivation, related work
Key Idea: Balanced Signed GraphFrequencies• 1D data kernel (DCT)• Positive line graph• Balanced signed graph• Graph Estimation• Signed Graph Sampling Strategy• Sampling objective• Gershgorin circle theorem, GDA-based sampling• 3-step signed graph sampling recipe• Results• Conclusion

14

Gene Cheung (genec@yorku.ca)

Graph Laplacian Estimation• Given empirical covariance matrix, we computeusing GLASSO [1] formulation:• Solve via a variant of the Block Coordinate Descent (BCD) [2] algorithm.
• In general, solution L is generalized graph Laplacian for unbalanced signed graph.

[1] J. Friedman, T. Hastie, and R. Tibshirani, “Sparse inverse covariance estimation with the graphical lasso,” Biostatistics (Oxford, England), vol. 9, pp. 432–41, 08, 2008.
[2] S. J. Wright, “Coordinate descent algorithms,” Math. Program., vol. 151, no. 1, pp. 3–34, 2015.
15

Gene Cheung (genec@yorku.ca)

Signal Reconstruction from Samples
desired signal• Signal Model:
observed signal

noise
sampling matrix

Sample set {2, 4}• Reconstruct signal

from samples

Sampling matrix• System of Linear Equations for Solution:

16

Gene Cheung (genec@yorku.ca):Graph Laplacian Regularizer (GLR)

Sampling Objective
can be upper-bounded by a small value• Stability depends on the condition number:can be close to 0 if H is not carefully chosen• Upper bound of the condition number can be minimized by maximizing• Select H to maximize• Theorem: Maximizing.

sub-sampling budget

minimizes an MSE upper bound bet’n original and reconstructed signal [1].

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

Gene Cheung (genec@yorku.ca)

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

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

Gene Cheung (genec@yorku.ca)

GDA-based Sampling for Positive Graphs• We focus on maximizing:• Given Gershgorin disc left-ends of is at the same exact value,
GDA-based graph sampling [1]: Select samples to max smallest discleft-end of coefficient matrix B via:
• Disc shifting (choosing sample i).
• Disc scaling (estimating influence on neighbors given sample i).

❑ Challenge: Disc left-ends ofare not at the same exact value.

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

Gene Cheung (genec@yorku.ca)

Signed Graph Sampling
Theorem [1]: Gershgorin disc left-ends of a generalized graph Laplacian matrix
balanced graphcan be aligned exactly tovia similar trasnform, and v is the first eigenvector ofcorresponding to.

corresponding to a, whereSampling Strategy:

1. Approximate
following condition:with a balanced graph

2. Given balanced graph, perform similarity transform
are aligned exactly at.
3. Employ GDA sampling method [2] on
to maximize

while satisfying theso that disc left-ends of.

[1] C. Yang, G. Cheung, W. Hu, “Graph Metric Learning via Gershgorin Disc Alignment," IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1-15, 2021.
[2] Y. Bai, F.Wang, G. Cheung, Y. Y. Nakatsukasa, and W. Gao, “Fast graph sampling set selection using gershgorin disc alignment," IEEE Trans. Signal Process., 2020
20

Gene Cheung (genec@yorku.ca)

Graph Balancing Algorithm: Overview❑ Construct balanced graph by adding one node at a time to a balanced node set❑ At each iteration, choose a most beneficial nodeto add to

1-hop neighbors.

, while satisfying constraint

Balanced node set[1] C. Dinesh, S. Bagheri, G. Cheung, I. V. Bajic, "Linear-time Sampling on Signed Graphs via Gershgorin Disc Perfect Alignment," IEEE ICASSP, Singapore, May 2022.
21

Gene Cheung (genec@yorku.ca)

Outline••••Overview of Graph Signal Processing (GSP)
Motivation, related work
Key Idea: Balanced Signed GraphFrequencies• 1D data kernel (DCT)• Positive line graph• Balanced signed graph• Graph Estimation• Signed Graph Sampling Strategy• Sampling objective• Gershgorin circle theorem, GDA-based sampling• 3-step signed graph sampling recipe• Results• Conclusion

22

Gene Cheung (genec@yorku.ca)

Experimental Setup
Four datasets:
1. Canadian parliament voting records data from 2005 to 2021: voting records of 340 constituencies voted in3154 elections. The votes are recorded as −1 for “no” and 1 for “yes” and 0 for “abstain / absent”. A signal fora given vote is defined as.
2. US Senate voting records data from 2017 to 2020: voting records of 100 senators in 1320 elections.
3. Canadian Car Model Sales Dataset: Canada vehicle model monthly sales for 2019–2022.

4. Almanac of Minutely Power Dataset Version 2 (AMPds2): 2 years of ON/OFF status data sampled at 1minute intervals for 15 residential appliances in a Canadian household.
• Randomly selected 90% of signals from each dataset to learn a signed graph [1] and a positive graph [2].
• Remaining 10% were used to test sampling algorithms.
[1] J. Friedman, T. Hastie, and R. Tibshirani, “Sparse inverse covariance estimation with the graphical lasso,” Biostatistics (Oxford, England), vol. 9, pp. 432–41, 08 2008.
[2] H. E. Egilmez, E. Pavez, and A. Ortega, “Graph learning from data under Laplacian and structural constraints,” IEEE JSTSP, vol. 11, no. 6, pp. 825–841, Sep. 2017.
23

Gene Cheung (genec@yorku.ca)

Experimental Results

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

Gene Cheung (genec@yorku.ca)

Experimental Results 2

Similar trends can be observed.

25

Gene Cheung (genec@yorku.ca)

Outline••••

Overview of Graph Signal Processing (GSP)
Motivation, related work
Key Idea: Balanced Signed GraphFrequencies• 1D data kernel (DCT)• Positive line graph• Balanced signed graph• Graph Estimation• Signed Graph Sampling Strategy• Sampling objective• Gershgorin circle theorem, GDA-based sampling• 3-step signed graph sampling recipe• Results• Conclusion

26

Gene Cheung (genec@yorku.ca)

Conclusion• Graph Signal Processing (GSP) studies signals on graphs.
• Graph sampling is a fundamental problem in GSP.
• Balanced signed graph:• Natural frequency interpretation.
• Amenable to fast graph sampling:
1. Balance graph.
2. Align Gershgorin disc left-end via similarity transform [1].
3. Run GDA-based sampling algorithm [2].

• Future Work: Graph sampling for board applications.
• e.g., video summarization.

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[1] C. Yang, G. Cheung, W. Hu, “Graph Metric Learning via Gershgorin Disc Alignment," IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1-15, 2021.
[2] Y. Bai, F.Wang, G. Cheung, Y. Y. Nakatsukasa, and W. Gao, “Fast graph sampling set selection using gershgorin disc alignment," IEEE Trans. Signal Process., 202027

Gene Cheung (genec@yorku.ca)

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

Gene Cheung (genec@yorku.ca)