Geometric graph-Based methods for high dimensional data

Andrea Bertozzi

University of California, Los Angeles

​

​

Former students: Tijana Kostic (Microsoft), Cristina Garcia (LANL), Justin Sunu (CGU), Huiyi Hu (Google) , Ekaterina Murkerjev (UCSD)

​

Current students: Michael Luo, Gloria Meng, Zach Boyd

​

Former Postdoc: Y. van Gennip (Nottingham), B. Osting (Utah), N. Guillen (U Mass)

​

Collaborators: Arjuna Flenner (China Lake), Allon Percus (CGU), Mason Porter (Oxford), Thomas Laurent (Loyola Marymount),

​

Inspiration: earlier work of Stan Osher, Chris Anderson, Luminita Vese, and Tony Chan

Thanks to NSF, ONR, AFOSR for support.

Mumford-Shah segmentation model 1989 CPAM

Variational Functionals for Image Segmentation - sharp interfaces with penalty function restricting regularity of interface

Terzopoulos snakes, Lagrangian curve attracted to edges, F is an environmental function that attracts to edges, Kass-Witkin-Terzopoulos IJCV 1987

Chan-Vese Segmentation – binary with sharp interface Gamma between regions,

IEEE Trans. Imag. Proc. 2001. Solved using level sets and the TV functional via a gradient flow.

An Example (from IPOL P. Getreuer 2012)

Total Variation, isoperimetric problems, and

diffuse interfaces

Ginzburg-Landau functional

Data f

Diffuse interface Equations and their sharp interface limit

Allen-Cahn equation. Famous in materials science. Now useful for data science.

Motion by Mean Curvature

Gradient descent of GL function:

MBO Scheme (1992)

Merriman, Bence, Osher

Heat equation

Threshold

iterate

Extended to Piecewise Constant Mumford-Shah Model by Esedoglu-Tsai 2006

From

Euclidean space to similarity graphs

for large data

• Minimal surface problem
• Laplace operator
• Pseudo-spectral methods
• Fast Fourier Transform
• Uses all the modes

• Graph mincut problem
• Graph Laplacian
• Projection to eigensubspace of graph Laplacian
• Nystrom extension/Rayleigh-Chebyshev
• Often only needs a small percentage of spectral modes.

​

​

​

​

Weighted graphs for “big data”

In a typical application we have data supported on the graph, possibly high dimensional. The above weights represent comparison of the data.

​

Examples include:

​

voting records of US Congress – each person has a vote vector associated with them.

​

Nonlocal means image processing – each pixel has a pixel neighborhood that can be compared with nearby and far away pixels.

Graph Cuts and Total Variation

Minimum cut

Maximum cut

Total Variation of function f defined on nodes of a weighted graph:

​

Min cut problems can be reformulated as a total variation minimization problem

for binary/multivalued functions defined on the nodes of the graph.

Nonlocal means graphs and total variation

• Buades Coll and Morel (2006)– introduced the NL Means functional for imaging applications – patch comparisons between pixels
• Osher and Gilboa (2007-8)– developed the Nonlocal TV functional for imaging applications- very effective for image inpainting applications with texture
• Drawback with Osher-Gilboa is slowness of algorithm
• We will accomplish these results with much faster run time and extend to general Machine Learning problems
• Suggests an alternative to the NL means calculus of Gilboa-Osher

​

Related work on cheeger cuts

Xavier Bresson, Xue-Cheng Tai, Tony F. Chan, Arthur Szlam,

Multi-class Transductive Learning Based on 1 Relaxations

of Cheeger Cut and Mumford-Shah-Potts Model, JMIV 2013

​

Szlam, A., Bresson, X.: Total variation and cheeger cuts. In: Proceedings

of the 27th International Conference on Machine Learning,

pp. 1039–1046 (2010).

​

X. Bresson, T. Laurent, D. Uminsky, J. H. von Brecht. . Advances in Neural Information Processing Systems 25 (NIPS 2012), pp.1394--1402, 2012.

Diffuse interface methods on graphs

Bertozzi and Flenner MMS 2012.

Arjuna Flenner

China Lake

SIAM Oustanding Paper Prize 2014

Convergence of graph GL functional

van Gennip and ALB Adv. Diff. Eq. 2012

Yves

Van Gennip

Diffuse interfaces on graphs

An Example: two moons

​

Replaces Laplace operator with a weighted graph Laplacian in the

Ginzburg Landau Functional

​

Allows for segmentation using L1-like metrics due to connection with GL

​

Comparison with Hein-Buehler 1-Laplacian

2010.

US House of Representatives voting Record classification of party affiliation from voting record

98^th US Congress 1984

Assume knowledge of party affiliation of 5 of the 435 members of the House

Infer party affiliation of the remaining 430 members from voting records

Gaussian similarity weight matrix for vector of votes (1, 0, -1)

Machine learning identification of similar regions in images

High dimensional fully connected graph – use Nystrom extension methods for fast computation methods.

Recall Convex Splitting Schemes

Schoenlieb and Bertozzi, Comm. Math. Sci. 2011

Analysis of convex splitting schemes for higher order

PDE in image processing

Basic idea:

Project onto Eigenfunctions of the gradient (first variation) operator

For the GL functional the operator is the graph Laplacian

Carola

Schoenlieb

Remove the diffuse interface:

MBO scheme on graphs

• 1) propagation by graph heat equation + forcing term

​

• 2) thresholding

​

​

​

• Simple! And often converges in just a few iterations (e.g. 4 for MNIST dataset)

​

Merkurjev, Kostic, and ALB, SIIMS 2013

Algorithm

• I) Create a graph from the data, choose a weight function and then create the symmetric graph Laplacian.
• II) Calculate the eigenvectors and eigenvalues of the symmetric graph Laplacian. It is only necessary to calculate a portion of the eigenvectors*.
• III) Initialize u.
• IV) Iterate the two-step scheme described above until a stopping criterion is satisfied.
• *Fast linear algebra routines are necessary – either Raleigh-Chebyshev procedure or Nystrom extension.

Two Moons Segmentation

Second eigenvector segmentation

Our method’s segmentation

Image segementation

Original image 1

Original image 2

​

Handlabeled grass region

Grass label transferred

Image Segmentation

Handlabeled sky region

Handlabeled cow region

Sky label transferred

Cow label transferred

Generalization MULTICLASS Machine Learning Problems (MBO)

Garcia, Merkurjev, Bertozzi, Percus, Flenner, IEEE TPAMI, 2014

​

Semi-supervised learning

Instead of double well we have N-class well with

Minima on a simplex in N-dimensions

MNIST Database

Comparisons

Semi-supervised learning

Vs Supervised learning

​

We do semi-supervised with

only 3.6% of the digits as the

Known data.

​

Supervised uses 60000 digits for training and tests on 10000 digits.

We use local rescaled graph as

in Zelnik-Manor&Perona

Performance on Coil WebKB

Nystrom Extension

Fowlkes Belongie Chung and Malik, IEEE T. PAMI 2004.

Hyperspectral Video Segmentation

– semi supervised

Eigenfunctions computed using Nystrom

“ground truth obtained from thresholding eigenfunctions; random initialization otherwise

Four class hyperspectral pixel segmentation of gas plume, ground, mountain, and sky

Merkurjev, Sunu, and Bertozzi, 2014, ICIP Paris 2014

eigenfunctions

Training data from thresholding eigenfunctions

Initialization (random)

clasification

Comparison to Kmeans and spectral clustering - unsupervised

EMMCVPR 2015 Hu, Sunu, and ALB

K-means

And

Spectral

Clustering

​

C-V segmentation on graphs

using MBO scheme for unsupervised clustering of hyperspectral pixels

Multiclass

MBO

with different

Initializations.

​

7 video frames

280K pixels

​

Each pixel is

128 dimensions

​

EMMCVPR 2015 Hu, Sunu, and ALB

​

Community Detection –

modularity Optimization

Joint work with Huiyi Hu (UCLA), Thomas Laurent (Loyola Marymount),

and Mason Porter (Oxford) SIAP 2013.

[w_ij] is graph adjacency matrix

P is probability nullmodel (Newman-Girvan) P_ij=k_ik_j/2m

k_i = sum_j w_ij (strength of the node)

Gamma is the resolution parameter

g_i is group assignment

2m is total volume of the graph = sum_i k_i = sum_ij w_ij

​

This is an optimization (max) problem. Combinatorially complex – optimize over all possible group assignments. Very expensive computationally.

Newman, Girvan, Phys. Rev. E 2004.

The modularity of a partition measures the fraction of total edge weight within each community minus the edge weight expected if edges were placed randomly using some null model.

Bipartition of a graph

Given a subset A of nodes on the graph define

​

Vol(A) = sum _{i in A} k_i

​

​

Then maximizing Q is equivalent to minimizing

Given a binary function on the graph f taking values +1, -1 define A to be the set where f=1, we can define:

Equivalence to L1 compressive sensing

Thus modularity optimization restricted to two

groups is equivalent to

This generalizes to n class optimization quite naturally

Because the TV minimization problem involves functions with values on the simplex we can directly use the MBO scheme to solve this problem.

Modularity optimization moons and clouds

MNIST digit classification using modularity – unsupervised

Binary segmentation of 4 and 9:

13782 handwritten digits. Graph created based on similarity score

between each digit. Weighted graph with 194816 connections.

Full multiclass

Segmentation

of all 70K digits

4-9 MNIST Segmentation

LFR Benchmark

Lancichinetti, Fortunato, Radicchi, Phys Rev E 2008

​

Synthetic graphs with powerlaw distribution of community size

​

Mixing parameter – fraction of edges shared with other communities vs own community

​

​

​

​

Global method

Global binary optimization on graphs for classification of high dimensional data

Ekaterina Merkurjev, Egil Bae, Andrea L. Bertozzi, Xue-Cheng Tai

​

Conclusions and future work

Yves van Gennip, Nestor Guillen, Braxton Osting, and Andrea L. Bertozzi, Mean curvature, threshold dynamics, and phase field theory on finite graphs, 2013.

​

Diffuse interface formulation provides competitive algorithms for machine learning applications including nonlocal means imaging

​

Extends PDE-based methods to a graphical framework

​

Future work includes community detection algorithms (very computationally

expensive)

​

Speedup includes fast spectral methods and the use of a small subset of

eigenfunctions rather than the complete basis

​

Competitive or faster than split-Bregman methods and other L1-TV based

methods

​

Extension of work to convex optimization methods (joint work with Egil Bae and Ekaterina Merkurjev)

Nestor Braxton

Preprints and Reprints

• A. L. Bertozzi and A. Flenner, Multiscale Modeling and Simulation, 10(3), 2012.
• Tijana Kostic and Andrea Bertozzi, J. Sci Comp., 2012
• Y van Gennip and ALB Adv. Diff. Eq. 2012
• H. Hu, Y. van Gennip, B. Hunter, A.L. Bertozzi, M.A. Porter, IEEE ICDM'12, 2012.
• Y. van Gennip et al SIAP (spectral clustering gang data) 2013
• E. Merkurjev, T. Kostic, and A. L. Bertozzi, SIAM J. Imag. Proc. 2013.
• Huiyi Hu, Thomas Laurent, Mason A. Porter, Andrea L. Bertozzi, SIAM J. Appl. Math., 2013.
• C. Garcia-Cardona, E. Merkurjev, A. L. Bertozzi, A. Flenner and A. G. Percus,, IEEE Trans. PAMI 2014
• Y. van Gennip, N. Guillen, B. Osting, and A. L. Bertozzi, Mean curvature, threshold dynamics, and phase field theory on finite graphs, Milan J. Math. 2014.
• Huiyi Hu, Justin Sunu, and Andrea L. Bertozzi, Multi-class Graph Mumford-Shah Model for Plume Detection using the MBO scheme, Proc. EMMCVPR Hong Kong 2015, pp. 209-222.
• E. Merkurjev, E. Bae, A. L. Bertozzi, X-C. Tai, Global binary optimization on graphs for classification of high dimensional data, JMIV 2015.
• X. Luo and A. L. Bertozzi, Convergence Analysis of the Graph Allen-Cahn Scheme, preprint 2016.
• E. Merkurjev, A. Bertozzi, X. Yan, and K. Lerman, Modified Cheeger and Ratio Cut Methods Using the Ginzburg-Landau Functional for Classification of High-Dimensional Data, submitted 2016.
• Bertozzi and Flenner – SIGEST paper to appear 2016.

​

​

​

​