Spectral Graph Theory and its Applications

1 Spectral Graph Theoryand its ApplicationsDaniel A. SpielmanDept. of Computer ScienceProgram in Applied MathematicsYale UnviersityOutlineAdjacency matrix and LaplacianIntuition, Spectral Graph drawingPhysical intuitionIsomorphism testingRandom walksGraph Partitioning and clusteringDistributions of eigenvalues and compressionComputationWhat I m SkippingMatrix-tree of algebraic Graph graphs ( Cayley graphs).Connections to codes and of work by Adjacency Matrix1234 is eigenvalue and v is eigenvector ifThink of , or even better Symmetric -> n real eigenvalues andreal eigenvectors form orthonormal basis : invariant under : invariant under and Quadratic FormsView of A as an operator:View of A as quadratic form:if and then Laplacian: natural quadratic form on graphswhere D is diagonal matrix of degrees1234 Laplacian: fast factsso, zero is an eigenvalueIf k connected components, Fiedler ( 73) called algebraic connectivity of a Graph The further from 0, the more Graph in line (Hall 70)mapminimizetrivial solution: So, requireSolutionAtkins, Boman, Hendrickson 97:Gives correct embedding for graphs likeCourant-Fischer definition of eigvals/vecs(here ) Embedding Graph in plane (Hall 70)minimizemaptrivial solution.

2 Also require Solutionup to rotationSo, requiredegenerate solution:A GraphDrawing of the Graph using v2, v3 Plot vertex i at Spectral drawing of Streets in RomeSpectral drawing of Erdos Graph :edge between co-authors of papersDodecahedronBest embedded by first three eigenvectorsCondition for eigenvectorSpectral Graph drawing: Tutte justificationGivesfor all i small says x(i) near average of neighborsTutte 63: If fix outside face, and let everyother vertex be average of neighbors, getplanar embedding of planar 63 embedding of a outside -> at centerof mass of -> get planar embeddingFundamental modes: string with fixed endsFundamental modes: string with free endsEigenvectors of path graph1:2:3:4:17:Drawing of the Graph using v3, v4 Plot vertex i at Graph coloring from high eigenvectorsEmbedding of dodecahedron by 19thand 3-colorable random graphs [Alon-Kahale 97] Spectral Graph drawing: FEM justificationIf apply finite element method to solve Laplace s equation in the planewith a Delaunay triangulationWould get Graph Laplacian,but with some weights on edgesFundamental solutions are x and y coordinates(see Strang s Introduction to Applied Mathematics)Isomorphism testing1.

3 Different eigenvalues -> non-isomorphic2. If each vertex distinct in Spectral embedding, just need to line up eigvec determined up to testing 2= 3, eigvecs determined up to rotation Isomorphism testing 2= 3, eigvecs determined up to rotation Distinguish bynorm in embeddingIsomorphism testing: difficulties2. If ihas a high dimensional space, eigvecsonly determined up to basis rotations1. Many vertices can map to same place in Spectral embedding, if only use few Some pairs have an exponential number of : Strongly regular graphs with only 3 eigenvalues,of multiplicities 1, (n-1)/2 and (n-1)/2 Isomorphism testing: success[Babai-Grigoryev-Mount 82]If each eigenvalue has multiplicity O(1), can test in polynomial :Partition vertices into classes by norms in partitions using other vertex classes to split computational group Theory to fuse information,and produce description of all WalksRandom walks and PageRankAdjacency matrix of directed Graph :Walk transition matrix:Walk distribution at time t:PageRank vector p: Eigenvector of Eigenvalue 1 Random walks and PageRankPageRank vector p: Linear algebra issues:W is not symmetric, not similar to symmetric,does not necessarily have n eigenvaluesIf no nodes of out-degree 0,Perron-Frobenius Theorem.

4 Guarantees a unique, positive eigevec p ofeigenvalue there a theoretically interesting Spectral Theory ?Kleinberg and the singular vectorsConsider eigenvectors of largest eigenvalue ofandAre left and right singular values of , a more useful Theory than eigenvectors,when not symmetric.(see Strang s Intro. to Linear Algebra)Random walks on Undirected GraphsTrivial PageRank Vector:Not symmetric, but similiar to symmetrized walk matrixW and S have same eigvals, Random walk converges at rate 1/1- n-1 For lazy random walk (stay put with prob ):Where is the stable distributionFor symmetric SNormalized Laplacian [Chung]If consider 1- n-1should look at Relationship to cuts:Cheeger s Inequality (Jerrum-Sinclair 89)(Alon-Milman 85, Diaconis-Stroock 91) Cheeger s Inequality (Jerrum-Sinclair 89)(Alon-Milman 85, Diaconis-Stroock 91) Can find the cut by looking at for some tCan find the cut by looking at for some tOnly need approximate eigenvector(Mihail 89) GuaranteeLanczos CutAlternative definition of conductance [Lovasz 96 (?)]

5 ]This way, is a relaxation [see Hagen-Kahng 92].Equivalent to Normalized Cut [Shi-Malik 00] Spectral Image Segmentation (Shi-Malik 00)2004006008001000120010020030040050060 0700800900 Spectral Image Segmentation (Shi-Malik 00)24681012141624681012 Spectral Image Segmentation (Shi-Malik 00)24681012141624681012 Spectral Image Segmentation (Shi-Malik 00)24681012141624681012 Spectral Image Segmentation (Shi-Malik 00)24681012141624681012edge weightThe second eigenvector5010015020025030050100150200 Second Eigenvector s sparsest cut5010015020025030050100150200 Third Eigenvector50100150200250300501001502005 010015020025030050100150200 Fourth Eigenvector50100150200250300501001502005 010015020025030050100150200 Perspective on Spectral Image SegmentationIgnoring a lot we know about non-image data, gives good we fuse with what we know about images?Generally, can we fuse with other knowledge?What about better cut algorithms?

6 Improvement by Miller and Tolliver 0650100150200250300501001502005010015020 025030050100150200 Improvement by Miller and Tolliver 06 Idea: re-weight (i,j) byActually, re-weight by Prove: as iterate 2 > 0, get 2 componentsOne approach to fusing: Dirichlet EigenvaluesFixing boundary values to zero [Chung-Langlands 96]Fixing boundary values to non-zero. [Grady 06] Dominant mode by solving linear equation:computing electrical flow in resistor networkAnalysis of Spectral PartitioningFinite Element Meshes (eigvals right) [S-Teng 07]Planted partitions (eigvecs right) [McSherry 01]pqqp}}}}ABABProbA-A edge = pB-B edge = pA-B edge = qq < pOther planted problemsFinding cn1/2 clique in random Graph [Alon-Krivelevich-Sudakov 98]Color random sparse k-colorable Graph [Alon-Kahale 97]Asymmetric block structure (LSI and HITS)[Azar-Fiat-Karlin-McSherry-Saia 01]Partitioning with widely varying degrees[Dasgupta-Hopcroft-McSherry 04]Planted problem analysisSmall perturbations don t change eigenvalues too stable too, if well-separated from eigenvalues of random matrices[Furedi-Komlos 81, Alon-Krivelevich-Vu 01, Vu 05]pqqpSampled A as perturbation ofDistribution of eigenvalues of Random Graphs-10-505101520250200040006000800010 00012000 Histogram ofeigvals ofrandom40-by-40adjacencymatrices-10-505 10152025020004000600080001000012000 Distribution of eigenvalues of Random GraphsPredicted curve.

7 Wigner s Semi-Circle LawHistogram ofeigvals distributionsEigenvalues of walk matrix of 50-by-50 grid graphNumber greater than 1- proportional to distributionsNumber greater than 1- proportional to All these go to zerowhen take powersEigenvalues of walk matrix of 50-by-50 grid graphCompression of powers of graphs[Coifman, Lafon, Lee, Maggioni, Nadler, Warner, Zucker 05] If most eigenvalues of A and W bounded from eigenvalues of Atvery approximate Atby low-rank wavelets bases on linear equations and compute rigorous by taking Graph fromdiscretization of manifoldDiscretizing Manifoldedge weightEigenvalue distributionsEigenvalues of path Graph on 10k greater than 1- proportional toProof: can choose vertices to collapse so thatconductance becomes at least (like adding an expander on those nodes).New Graph has all eigvals at most 1- in abs rank change, so by Courant-FischerTheorem:If bounded degree, number eigenvalues greater than 1- is Theorem: Eigenvalue distributionsEigenvalue distributions of planar graphs?

8 For planar graphs, Colan de Verdiere s results implyHow big must the gap be?Must other gaps exist?ComputationNot rational, so only approximateIf exactly an eigenvalue,eigvecs = Null(A I)If close to just one eigenvalue iIf iclose to i+1is like i= i+1viand vi+1 can rotate with each otherGeneral Symmetric MatricesLocate any eigval in time1. Orthogonal similarity transform to tri-diagonalin time by elimination Given tri-diagonal matrix, count number eigenvalues in any intervalin time 3. Do binary search to locate eigenvalueLocate eigenvector: steps on tri-diagonal,time to map back to A Largest eigenvectors by power methodApply A to random vector r:In iters, expect x such thatUsing Lanczos, expect iters(better polynomial)Smallest eigenvectors by inverse power methodApply L-1to random vector r orthogonal to In iters, expect x such thatCompute in time[STeng04]if planar, in time [Koutis-Miller 06] SparsificationKey to fast A by sparse B for whichGeneralized eigenvalues provide notion ofapproximation in s inequality for other physical problems?

9 How to incorporate other data into Spectral methods?Make multilevel coarsening can we do with boundary conditions?What about generalized eigenvalue problems?