Gene Cheung
National Institute of Informatics
15th May, 2017

Semi-Supervised Graph Classifier
Learning with Negative Edge Weights.
Torino Visit 05/15/2017

1

Acknowledgement
Collaborators:• Y. Ji, M. Kaneko (NII, Japan)• A. Ortega (USC, USA)• D. Florencio (MSR, USA)
• P. Frossard (EPFL, Switzerland)• J. Liang, I. Bajic (SFU, Canada)• V. Stankovic (U of Strathclyde, UK)• X. Wu (McMaster U, Canada)• P. Le Callet (U of Nantes, France)• X. Liu (HIT, China)• W. Hu, J. Liu, Z. Guo (Peking U., China)• L. Fang (HKUST, HK)• C.-W. Lin (National Tsing Hua University, Taiwan)
Torino Visit 05/15/2017

2

NII Overview• National Institute of Informatics• Chiyoda-ku, Tokyo, Japan.
• Government-funded research lab.

• Offers graduate courses & degrees
through The Graduate University for
Advanced Studies (Sokendai).
• 60+ faculty in “informatics”:
quantum computing, discretealgorithms, database, machinelearning, computer vision, speech &audio, image & video processing.
• Get involved!
• 2-6 month Internships.
• Short-term visits via
MOU grant.
• Lecture series,
Sabbatical.
3Introduction to APSIPA and APSIPA DL

APSIPA Mission: To promote broad spectrum of research and education
activities in signal and information processing in Asia Pacific
APSIPA Conferences: ASPIPA Annual Summit and Conference
APSIPA Publications: Transactions on Signal and Information Processingin partnership with Cambridge Journals since 2012; APSIPA Newsletters
APSIPA Social Network: To link members together and to disseminate
valuable information more effectively
APSIPA Distinguished Lectures: An APSIPA educational initiative to reachout to the community

APSIPA Distinguished Lecture Series
www.apsipa.org

4Outline• Graph Signal Processing• Graph spectrum• Semi-supervised Graph Classifier• Smoothness prior & MAP formulation• Graph construction• Graph Laplacian perturbation• Lower bound min eigenvalue computation• IRLS algorithm• Experimental Results• Conclusion
Torino Visit 05/15/20175Outline• Graph Signal Processing• Graph spectrum• Semi-supervised Graph Classifier• Smoothness prior & MAP formulation• Graph construction• Graph Laplacian perturbation• Lower bound min eigenvalue computation• IRLS algorithm• Experimental Results• Conclusion
Torino Visit 05/15/2017

6

Graph Signal Processing• Signals on irregular data kernels described bygraphs.
• Graph: nodes and edges.
• Edges reveals node-to-node relationships.

example graph-signal

1. Data domain is naturally a graph.
• Ex: ages of users on social networks.

2. Underlying data structure unknown.
• Ex: images: 2D grid → structured graph.

Graph Signal Processing (GSP) addresses the problem ofprocessing signals that live on graphs.
[1] D. I. Shuman et al.,”The Emerging Field of Signal Processing on Graphs: Extending High-dimensional Data Analysis to Networks
and other Irregular Domains,” IEEE Signal Processing Magazine, vol.30, no.3, pp.83-98, 2013.

7

Graph Signal Processing
Research questions*:• Sampling: how to efficiently acquire /sense a graph-signal?

nodeedge• Graph sampling theorems.

• Representation: Given graph-signal, how
to compactly represent it?
• Transforms, wavelets, dictionaries.

• Signal restoration: Given noisy and/or
partial graph-signal, how to recover it?
• Graph-signal priors.

* Graph Signal Processing Workshop, Philadelphia, US, May 25-27, 2016.
https://alliance.seas.upenn.edu/~gsp16/wiki/index.php?n=Main.Program

8

undirected graph

Graph Fourier Transform (GFT)• Adjacency Matrix A: entry Ai,j has non-negativeedge weight wi,j connecting nodes i and j.

• Degree Matrix D: diagonal matrix w/ entry Di,i being
sum of column entries in row i of A.

Di ,i   Ai , jj

• Combinatorial Graph Laplacian L: L = D-A• L is symmetric (graph undirected).
• L is a high-pass filter.
• L is related to 2nd derivative.

11234

 0wA   1, 2
 0
 0w1, 20 0
1 0
0 1

1 0

 w1, 2
 0D
 0

 00 0
w1, 2  1 0 0
02 0

00 1

1

Graph Laplacian:w1, 2 w1, 2 w
L   1, 2
 0

 00
100

 w1, 20
w1, 2  1  1 0 
12  10
1 1 0

L3,: x   x2  2 x3  x4
f x  h   2 f x   f x  h f  x   limh 0h2

Torino Visit 05/15/2017*https://en.wikipedia.org/wiki/Second_derivative9Graph Spectrum from GFT• Graph Fourier Transform (GFT) is eigen-matrix of graph Laplacian L.
w1, 2 1
1eigenvalueL ui  i ui

12

34…

8eigenvector
1st AC eigenvector

1. Edge weights affect shapes of eigenvectors.
2. Eigenvalues (≥ 0) as graph frequencies.
• Constant eigenvector is DC.
• # zero-crossings increases as λ increases.
• GFT defaults to DCT for un-weighted connected line.
• GFT defaults to DFT for un-weighted connected circle.
Torino Visit 05/15/2017
10Variants of Graph Laplacians• Graph Fourier Transform (GFT) is eigen-matrix of graph Laplacian L.

L ui  i ui

eigenvalueeigenvector• Other definitions of graph Laplacians:• Normalized graph Laplacian:Ln  D 1 / 2 LD 1 / 2  I  D 1 / 2 AD 1 / 2• Random walk graph Laplacian:1

1Lrw  D L  I  D A• Generalized graph Laplacian [1]:Lg  L  D*Characteristics:• Normalized.
• Symmetric.
• No DC component.
• Normalized.
• Asymmetric.
• Eigenvectors not orthog.
• Symmetric.
• L plus self loops.
• Defaults to DST, ADST.

[1] Wei Hu, Gene Cheung, Antonio Ortega, "Intra-Prediction and Generalized Graph Fourier Transform for Image Coding," IEEESignal Processing Letters, vol.22, no.11, pp. 1913-1917, November 2015.

11

Outline• Graph Signal Processing• Graph spectrum• Semi-supervised Graph Classifier• Smoothness prior & MAP formulation• Graph construction• Graph Laplacian perturbation• Lower bound min eigenvalue computation• IRLS algorithm• Experimental Results• Conclusion
Torino Visit 05/15/2017

12Semi-Supervised Graph Classifier Learning• Binary Classifier: given feature vector xi ofdimension K, compute f(xi) ∊ {0,1}.
• Classifier Learning: given partial / noisy labels(xi, yi), train classifier f(xi).

• GSP Approach [1]:example graph-based classifier

1. Construct similarity graph with +/- edges.
2. Pose MAP graph-signal restoration problem.
3. Perturb graph Laplacian to ensure PSD.
4. Solve num. stable MAP as sparse lin. system.
[1] Yu Mao, Gene Cheung, Chia-Wen Lin, Yusheng Ji, “Image Classifier Learning from Noisy Labels via Generalized GraphSmoothness Priors,” IEEE IVMSP Workshop, Bordeaux, France, July 2016. (Best student paper award)[2] G. Cheung, W.-T. Su, Y. Mao, C.-W. Lin, "Robust Semi-Supervised Graph Classifier Learning with Negative Edge Weights," submittedto Special Issue on "Graph Signal Processing" in IEEE Journal on Selected Topics of Signal Processing, November 2016. (arXiv)

13

Graph-Signal Smoothness Prior• Smoothness: signal “consistent” w/ underlying graph.
• Q1: how to define smoothness w.r.t. graph with +/- edges?
• Q2: is signal smoothness prior robust to errs?
• Q3: is signal smoothness prior easy to solve?

Torino Visit 05/15/2017
14

Graph-Signal Smoothness Prior:
Candidate 1

w=-1• Shift-based Smoothness Prior [1]:shifted version of signal• Prior minimizes sums of sample values despite negative edges!

[1] S. Chen, A. Sandryhaila, J. Moura, and J. Kovacevic, “Signal recovery on graphs: Variation minimization,” IEEE
Transactions on Signal Processing, vol. 63, no.17, September 2015, pp. 4609–4624.

15

Graph-Signal Smoothness Prior:
Candidate 2

w=1• Total Variation (TV) [1] on graph:degree 0 at node 2• Prior minimizes diffs in every pair!

[1] L. Rudin, S. Osher, and E. Fatemi, “Nonlinear total variation based noise removal algorithms,” Physica D, vol. 60,
no.1-4, November 1992, pp. 259–268.

16

Graph-Signal Smoothness Prior:
Candidate 3

w=1• Graph Laplacian Regularizer [1]:GFT coeff

eigenvalues / graph freqs• Promote large / small inter-node differences depending onedge signs.

Promote large difference

Promote small difference• Sensible, but numerically unstable.
[1] J. Pang and G. Cheung, “Graph Laplacian regularization for image denoising: Analysis inn the continuous
domain,” in IEEE Transactions on Image Processing, vol. 26, no.4, April 2017, pp. 1770–1785.

17

MAP Problem Formulation• Label Noise Model: uniform noise model [1]• Probability of observing noisy y given ground truth x:• MAP formulation:

fidelity term

perturbation matrix
to ensure PSD!

graph-signal
smoothness prior[1] A. Brew, D. Greene, and P. Cunningham, “The interaction between supervised learning and crowdsourcing,”Computational Social Science and the Wisdom of Crowds Workshop at NIPS, Whistler, Canada, December 2010.

18

Graph Construction: add positive edges• Given feature vector per sample in high dim. space.
• First to construct (dis)similarity graph with +/- edges fromfeatures.
• Positive edge weights reflect inter-node similarity:inter-nodefeature distance• Optimization of feature weights in [1].

[1] J. Z. Huang, M. K. Ng, H. Rong, and Z. Li, “Automated variable weighting in k-means type clustering,” IEEE
Transactions on Pattern Analysis and Machine Intelligence, vol. 27, no.5, May 2005, pp. 657–668.

19

Graph Construction: add negative edges
Centroid-based: add
negative edge connecting
cluster centroids.
• Robust, not precise.
Boundary-based: add negative edges connecting boundary
nodes of two clusters.
• Precise, not robust.

Idea: use convex combination as we iterate:

L*   L1  1  1    L2  2

Torino Visit 05/15/201720

Example: 10-node graphw=0.1, or -1• Centroid-based 1st e-vector: peaks at neg. edge endpoints.

• Boundary-based 1st e-vector: same level @ boundary nodes.
• Low graph frequencies of indefinite L are useful in restoration [1].

[1] A. Knyazev, “Signed Laplacian for spectral clustering revisited,” January 2017, https://arxiv.org/abs/1701.01394.

21

Finding Perturbation Matrix:min norm

• Minimum norm criteria: smallest △ to ensure PSD:

• Sol’n is special case of Thm 5.1 in [1]:assume has p negative
eigenvalues• Observations:
1. L+△ is PSD (good).
2. L+△ preserves same eigen-vectors (good).
3. Eigenvalue 0 has p+1 eigen-vectors (bad).
[1] A. N. Higham and S. H. Cheng, “Modifying the inertia of matrices arising in optimization,” ELSEVIER LinearAlgebra and its Applications, vol. 275-279, May 1998, pp. 261–279.

22

Finding Perturbation Matrix:
eigen-structure preservation• Perturb to ensure PSD while preserving frequency components(eigenvectors) and frequency preferences.

• One sol’n is △=λmin I, i.e. shift all eigenvalues up by η=λmin.
• Intuition: signal variations + signal energies

signal variations

signal energies• Q: computed lower-bound for λmin w/o eigen-decomposition?
Torino Visit 05/15/201723

Lower Bound λmin
• Matrix Inertia:• Haysworth Inertia Additivity:•EvalBound (Lt, t)

Schur complement• Step 1: divide Nt nodes in Lt into r and Nt – r nodes.
• Eigen-decompose Lt1,1 to find smallest eigenvalue λt1,1.
• Perturb Lt by augmented eigenvalue κtmin

Ensure Lt1,1 is PD.
[1] G. Cheung et al., "Robust Semi-Supervised Graph Classifier Learning with Negative Edge Weights," submitted toSpecial Issue on "Graph Signal Processing" in IEEE Journal on Selected Topics of Signal Processing, November 2016.

24

Lower Bound λmin
• Haysworth Inertia Additivity:• Step 2: ensure SC of Lt1,1 is PSD:
• if Nt – r ≤ r,
• eigen-decompose Lt / Lt1,1 to find smallest eigenvalue λt2.

• Compute lower bound:• if Nt – r > r,
• Define

Complexity O(N2 r).

• Recursively call
• Return[1] G. Cheung et al., "Robust Semi-Supervised Graph Classifier Learning with Negative Edge Weights," submitted toSpecial Issue on "Graph Signal Processing" in IEEE Journal on Selected Topics of Signal Processing, November 2016.

25

IRLS Optimization• MAP formulation:• Iterative Recursive Least Square (IRLS) [1]:• Replace L0-norm with weighted L2-norm, solve iteratively.

diagonal matrix w/ weights b’s• Sparse linear system of equations:mimics L0-norm• Solve via conjugate gradient instead of matrix inversion.

[1] I. Daubechies, R. Devore, M. Fornasier, and S. Gunturk, “Iteratively re-weighted least squares minimization forsparse recovery,” Communications on Pure and Applied Mathematics, vol. 63, no.1, January 2010, pp. 1–38.

26

Outline• Graph Signal Processing• Graph spectrum• Semi-supervised Graph Classifier• Smoothness prior & MAP formulation• Graph construction• Graph Laplacian perturbation• Lower bound min eigenvalue computation• IRLS algorithm• Experimental Results• Conclusion
Torino Visit 05/15/201727

Experimental Setup• KEEL database [1], face gender dataset [2].

• Features extracted for each sample; ex., local binary pattern (LBP).
• 70% / 30% are training / testing data.
• Graph construction:• kNN for positive edges (k=3).
• Centroid / boundary-based negative edges.

• Comparison schemes:
1. Linear SVM, SVM with RBF kernel
2. RobustBoost
3. Graph-Pos, Graph-MinNorm
4. Graph-Bandlimited, Graph-AdjSmooth, Graph-Wavelet[1] J. A.-F. et al., “Keel: A software tool to assess evolutionary algorithms to data mining problems,” Soft Computing, vol. 13,no.3, February 2009, pp. 307–318.
[2] L. Spacek, “Face recognition data, university of essex, uk,” http://cswww.essex.ac.uk/mv/allfaces/faces94.html, Feb. 2007.

28

Experimental Results• Comparisons w/ other classifiers:

Torino Visit 05/15/201729

Experimental Results• Comparisons w/ other classifiers:

Torino Visit 05/15/201730

Experimental Results• Comparisons w/ other classifiers:

Torino Visit 05/15/201731

Experimental Results• λmin versus computed lower bound:

Torino Visit 05/15/2017

32

Conclusion• Graph Signal Processing (GSP)• Tools to process signals that live on graphs.

• Graph-based binary classifier• Similarity graph with +/- edges, given features.
• Perturbed graph Laplacian that is PSD.
• Fast computation of min eigenvalue lower bound.

• Fast MAP solver via IRLS, conjugate gradient.

Torino Visit 05/15/2017

33

Other GSP Works• Coding of LF, spectral image [1], 3D point cloud w/ GFT.
• Coding of graph data w/ graph wavelets.
• Political leaning estimation [2].
• Wireless signal / power estimation [3].
[1] J. Zeng, G. Cheung, Y.-H. Chao, I. Blanes, J. Serra-Sagrista, A. Ortega, "Hyperspectral
Image Coding using Graph Wavelets," accepted to IEEE International Conference on
Image Processing, Beijing, China, September, 2017.

[2] B. Renoust et al., "Estimation of Political Leanings via Graph-Signal Restoration,"submitted to IEEE International Conference on Acoustics, Speech and Signal Processing,New Orleans, USA, March, 2017[3] M. Kaneko, G. Cheung, W.-t. Su, C.-W. Lin, "Graph-based Joint Signal / Power
Restoration for Energy Harvesting Wireless Sensor Networks," submitted to IEEE
Globecom, Singapore, December, 2017.

34

Q&A

• Email: cheung@nii.ac.jp• Homepage: http://research.nii.ac.jp/~cheung/

Torino Visit 05/15/201735