# Math/CSC 870 Spring 2007 Cutting complete weighted graphs

Math/CSC 870 Spring 2007 Cutting complete weighted graphs Jameson Cahill Ido Heskia 1 Let G V , E be a weighted graph with an

Adjacency weight matrix W Our goal: Partition V into two disjoint sets A and B such that the nodes in A (resp. B) are strongly connected (=similar) to each other, but we would also like to have that the nodes In A are not strongly connected to the Nodes in B. (Then we can continue partition A and B in the same fashion). 2 To do this we will use the normalized cut Criterion: Cut A, B

w a, b a A,bB asso A,V w a, v a A, vV

(We normalize in order to deal with the cuts which favor small isolated sets of points.) 3 Normalized Cut Criterion: cut A, B cut A, B NCut A, B asso A,V asso B,V We wish to minimize this quantity across all

Partitions V A B 4 asso A, A asso B, B If we let: Nasso A, B asso A,V asso B,V Then a straightforward calculation shows that Ncut A, B 2 Nasso A, B

(since cut A,V A asso A,V asso A, A ) So Minimizing Ncut(A,B) simultaneously Maximizes Nasso(A,B)! 5 Bad News: Prop. (Papadimitrou, `97): Normalized Cut for a graph on regular grids is NP hard!! However, good approximate solutions can be found in O(mn) (n=# of nodes, m=max # of matrix-vector computations required) (Use Lanczos Algorithm to find eigen vectors)

(linear programming vs. integer programming) 6 Algorithm: Input: Weighted adjacency matrix (or data file to weigh into an adjacency matrix). Suppose V v1 , , vn Define a diagonal matrix D by D i, i w vi , v j j (the degree Of node i)

D i, j 0 for i j For notational convenience we will write D i, i Di 7 Let x be an nx1 vector where 1 vi A x i 1 vi B Now define:

Ncut x wij xi x j xi 0, x j 0 D i xi 0

wij xi x j xi 0, x j 0 D i xi 0

So we are looking for the x vector that minimizes this quantity. 8 Through a straightforward (but hairy) calculation, Shi and Malik show that this Boils down to finding a vector y that T y D W y minimizes: y T Dy Where the components of y may take on real

Values. This is why our solution is Only approximate (and not NP hard). 9 The above expression is knows as a Rayleigh quotient and is equivalent to finding a y that minimizes: D W y Dy Which we can rewrite as: D

1 2 D W D 1 2 z z 1

2 Where z D y (Makes sense, since diagonal & pos. entries) 10 Thus, we just need to find the eigen vector Corresponding to the smallest nonzero 1 2 Eigen value of the matrix D D W D

1 2 Thresholding: For each we have y where 1 if y i y i 1 if y i 11

We are using this code for the Normalized cut: function [NcutDiscrete,NcutEigenvectors,NcutEigenvalues] = ncutW(W,nbcluster); % [NcutDiscrete,NcutEigenvectors,NcutEigenvalues] = ncutW(W,nbcluster); % % Calls ncut to compute NcutEigenvectors and NcutEigenvalues of W with nbcluster clusters % Then calls discretisation to discretize the NcutEigenvectors into NcutDiscrete % Timothee Cour, Stella Yu, Jianbo Shi, 2004 % compute continuous Ncut eigenvectors [NcutEigenvectors,NcutEigenvalues] = ncut(W,nbcluster); % compute discretize Ncut vectors [NcutDiscrete,NcutEigenvectors] =discretisation(NcutEigenvectors);

12 Example: Cutting a K5 graph. W: Pair-wise similarity matrix Change all weights into 0 and 1 in order to Draw the graph (for matlab). but bad output for large number of nodes) drawgraph(garden).bmp only 400 vertices Transform indicator matrix into adjacency matrix in order to graph. (adjancy_2.m) 0 1 1 1 1 0 9 10 W 1 9 0 10

1 10 10 0 10 1 2 1 10 1 2 1 Load: 0 Desktop\cluster\cluster\matgraph\matgraph\ \example.fig

run: load Example.txt; drawgraph(Example); drawgraph_2(Example) 13 Example.fig 14 Cut Example: 15 Bad output format for many nodes (heres example

for just 400 nodes and 79,800 edges): 16 Lets Cut the Forest Tropical Rain Forest Pasoh Forest Reserve, Negeri Sembilan, Malaysia. Complete survey of all species of trees for each 5x5 meter square. 17 The Data File: (cluster\bci5\bci5.dat)

20,000 rows, 303 columns. 1st 2 columns are x,y coords. 301 columns of species. Every 100 rows, x incremented. 200x100 squares each is a 5x5 meters. (1000x500 meter forest) 18 A piece of the data file: 19 Model

Each square is a node (vector of coords and 301 species). Create an adjacency matrix and the weight w(i,j) Quantifies how similar the nodes are. 20 Similarity indices Pick your favorite weighting function: Weight_1.m Weight_can.m

Source: [7] 21 Trying to weigh a 20,000x20,000 matrix takes a really long time!!! So we decided between 2 options (until finding a REAL machine): 1)Cut a much smaller piece. +(learn about presenting output) 2) Change the resolution. +(cut the whole thing) 22

Cutting a smaller piece (a garden) Change the original data file to 400 rows (nodes) instead of 20000. By the way the rows are ordered cant just take the first 400 rows (otherwise you get a thin strip of 100X4 squares). Take 20 rows and jump by 80 rows until you get 400 rows). (littleforest.dat) 23 Result: (load garden.txt) or littleforest+weigh+diagonal cut_garden = Ncutw(garden,2) [p1,p2]=firstcut(garden) (coords vector

400x2) [v1,v2]=vector(p1)(1 vector rep. row, 2 nd vector rep. column) [v3,v4]=vector(p2) Scatter(v1,v2,b), hold on, scatter(v3,v4,m) 24 2 regions:

25 Four regions (using different weighting function): 26 reweigh_3(cut_garden,garden) 4 regions [a1,a2,a3,a4,a5,a6,a7,a8] = reweigh_3(Cut,weighted_matrix) So we can make it work for 20x20. Quite easy to generalize it, so number of regions is a parameter. Now we wanted to cut the whole forest and

analyze our results. 27 2) Change of resolution In-stead of looking at 5x5 squares, we can look at a 10x10 meter square (not so bad resolution) and cut the whole forest? So well have a 5,000x5,000 matrix. From original file: add any 2 consecutive Rows and basically jump by 100 to add next row (resolution.m) 28

Weighting takes only a few hours now, but the RAM fails to deliver! Cant keep the 5,000x5,000 matrix and do operations on it. (just changing diagonal to 0 takes a long time). (A.txt) Still cant cut it get memory errors!!! (cant even perform the check for symmetry of matrix) 29 Sensitivity analysis/other stuff to do

Somehow cut the whole forest. Compare the cuts we get with the original data. Do the regions indeed consist of similar nodes? Which weight function gave us the best cut (compared to the actual data)? 30 Average out the regions, and see if they are really different than the other Regions.

After deciding what was the best cut, we want to start throwing off data (change resolution for example) And see how far from the desired cut we get (next survey, how accurate should it be?) 31 Assuming our results are good: Take another look at the data file. Anything special about it that made it Possible to apply image segmentation Techniques on it?

What properties of the data file made it segmentable using this method? 32 References: [1] IEEE Transactions on patterns analysis and machine intelligence vol. 22 no. 8 Normalized cuts and Image Segmentation. By Jianbo Shi and Jitendra Malik [2] Fast Multiscale Image Segmentation. By Eitan Sharon, Achi Brandt and Ronen Basri. [3] Nature Hierarchy and adaptivity in segmenting visual scenes. By Eitan Sharon, Meirav Galun, Dahlia Sharon, Ronen Basri and Achi

Brandt 33 [4]Tutorial Graph Based Image Segmentation Jianbo Shi, David Martin, Charless Fowlkes, Eitan Sharon http://www.cis.upenn.edu/~jshi/GraphTutorial/Tutorial-ImageSegmentationGraphcut1-Shi.pdf [5]Normalized Cut image segmentation and data clustering MATLAB code http://www.cis.upenn.edu/~jshi/ [6]Scale dependence of tree abundance and richness in a tropical rain forest, Malaysia. Fangliang He, James V.LaFrankie Bo Song [7] Choosing the Best Similarity Index when Performing Fuzzy Set Ordination on Abundance Data Richard L. Boyce

34

## Recently Viewed Presentations

• The Division Algorithm. Algorithm 4.8.1 Division Algorithm : [Given . a nonnegative integer a and a positive integer d, the aim of the algorithm is to find integers q and r that satisfy the conditions. subtracting d repeatedly from a....
• Explore- marine ecosystems project. The ocean covers more than 70% of our Blue Planet. Includes many different ecosystems that range from the depths of the deep to the sunny surface, close to shore to thousands of miles away from the...
• Write down some questions you have.
• Example. 1,000 people in the city. 1 is a terrorists, and we have their pictures. Thus the . base rate. of terrorists is 1/1000. Suppose we have a new terrorist facial recognition system that is 99% accurate.
• 10 Target Date Responsibility Task GOSUD Meeting 2-4 May, 2006 Next meeting Keeley, Delcroix, SAMOS Develop details of how SAMOS and GOSUD will cooperate 17 Apr, 2005 Rickards, Keeley, Petit de la Villeon, Delcroix Prepare poster for IODE meeting and...
• The trespass doctrine requires only that the trespasser intended to enter onto the land as a matter of free choice, not that he had a subjective intent to trespass or even knew he was trespassing. Entry - Although trespass always...
• What is the circumference of a circle that has an area of 113.04 square inches? What is the area of a circle that has a circumference of 12.56 feet? Task Cards- Work with partner - show all work
• Advancing to the full POLS major. Satisfying the lower division POLS courses + gpa (2.6Or higher) 5. Core courses in a sub field. 1 . Course - each - in two other sub fields. 3. Courses in any of the...