A Short Tutorial on Graph Laplacians, Laplacian Embedding ...

1 A Short Tutorial on Graph Laplacians, LaplacianEmbedding, and Spectral ClusteringRadu HoraudINRIA Grenoble Rhone-Alpes, HoraudGraph Laplacian TutorialIntroductionThespectral Graph theorystudies the properties of graphs viathe eigenvalues and eigenvectors of their associated graphmatrices: theadjacency matrixand thegraph Laplacianandits matrices have been extremely well studied from analgebraic point of Laplacian allows a natural link between discreterepresentations, such as graphs, and continuousrepresentations, such as vector spaces and most important application of the Laplacian isspectralclusteringthat corresponds to a computationally tractablesolution to thegraph partitionning application isspectral matchingthat solves HoraudGraph Laplacian TutorialApplications of spectral Graph theorySpectral partitioning: automatic circuit placement for VLSI(Alpert et al 1999), image segmentation (Shi & Malik 2000),Text mining and web applications.

2 Document classificationbased on semantic association of words (Lafon & Lee 2006),collaborative recommendation (Fouss et al. 2007), textcategorization based on reader similarity (Kamvar et al. 2003).Manifold analysis: Manifold Embedding , manifold learning,mesh segmentation, HoraudGraph Laplacian TutorialBasic Graph notations and definitionsWe considersimple graphs(no multiple edges or loops),G={V,E}:V(G) ={v1,..,vn}is called thevertex setwithn=|V|;E(G) ={eij}is called theedge setwithm=|E|;An edgeeijconnects verticesviandvjif they are adjacent orneighbors. One possible notation for adjacency isvi vj;The number of neighbors of a nodevis called thedegreeofvand is denoted byd(v),d(vi) = vi vjeij.

3 If all the nodes ofa Graph have the same degree, the Graph isregular; Thenodes of anEuleriangraph have even Graph iscompleteif there is an edge between every pair HoraudGraph Laplacian TutorialSubgraph of a graphHis asubgraphofGifV(H) V(G)andE(H) E(G);a subgraphHis aninduced subgraphofGif two vertices ofV(H)are adjacent if and only if they are adjacent a complete subgraph of a is a sequence ofkdistinct vertices suchthat consecutive vertices are a connected subgraph where every vertex hasexactly two Graph containing no cycles is aforest. A connected forest HoraudGraph Laplacian TutorialA k-partite graphA Graph is calledk-partiteif its setof vertices admits a partition intokclasses such that the vertices of thesame class are not example of HoraudGraph Laplacian TutorialThe adjacency matrix of a graphFor a Graph withnvertices, the entries of then nadjacencymatrix are defined by:A:= Aij= 1if there is an edgeeijAij= 0if there is no edgeAii= 0A= 0 1 1 01 0 1 11 1 0 00 1 0 0 Radu HoraudGraph Laplacian TutorialEigenvalues and eigenvectorsAis a real-symmetric matrix: it hasnreal eigenvalues and itsnreal eigenvectors form an orthonormal { 1.}

4 , i,.., r}be the set eigenspaceSicontains the eigenvectors associated with i:Si={x Rn|Ax= ix}For real-symmetric matrices, the algebraic multiplicity is equalto the geometric multiplicity, for all the dimension ofSi(geometric multiplicity) is equal to themultiplicity of i6= jthenSiandSjare mutually HoraudGraph Laplacian TutorialReal-valued functions on graphsWe consider real-valued functions on the set of the Graph svertices,f:V R. Such a function assigns a real numberto each Graph a vector indexed by the Graph s vertices, hencef :f= (f(v1),..,f(vn)) = (f(1),..,f(n)).The eigenvectors of the adjacency matrix,Ax= x, can beviewed HoraudGraph Laplacian TutorialMatrixAas an operator and quadratic formThe adjacency matrix can be viewed as an operatorg=Af;g(i) = i jf(j)It can also be viewed as a quadratic form:f>Af= eijf(i)f(j)Radu HoraudGraph Laplacian TutorialThe incidence matrix of a graphLet each edge in the Graph have an arbitrary but fixedorientation.

5 The incidence matrix of a Graph is a|E| |V|(m n) matrixdefined as follows:5:= 5ev= 1ifvis the initial vertex of edgee5ev= 1ifvis the terminal vertex of edgee5ev= 0ifvis not ine5= 1 1 0 01 0 1 00 1 1 00 1 0 +1 Radu HoraudGraph Laplacian TutorialThe incidence matrix: A discrete differential operatorThe mappingf 5fis known as theco-boundarymappingof the Graph .(5f)(eij) =f(vj) f(vi) f(2) f(1)f(1) f(3)f(3) f(2)f(4) f(2) = 1 1 0 01 0 1 00 1 1 00 1 0 +1 f(1)f(2)f(3)f(4) Radu HoraudGraph Laplacian TutorialThe Laplacian matrix of a graphL=5>5(Lf)(vi) = vj vi(f(vi) f(vj))Connection between the Laplacian and the adjacency matrices:L=D AThe degree matrix:D:=Dii=d(vi).

6 L= 2 1 1 0 1 3 1 1 1 1 2 00 1 0 1 Radu HoraudGraph Laplacian TutorialThe Laplacian matrix of an undirected weighted graphWe considerundirected weighted graphs: Each edgeeijisweighted bywij> Laplacian as an operator:(Lf)(vi) = vj viwij(f(vi) f(vj))As a quadratic form:f>Lf=12 eijwij(f(vi) f(vj))2 Lis symmetric and positive , real-valued eigenvalues:0 = 1 2 .. HoraudGraph Laplacian TutorialThe Laplacian of a 3D discrete surface (mesh)A Graph vertexviis associated with a 3D weight of an edgeeijis defined by the Gaussian kernel:wij= exp( vi vj 2/ 2)0 wmin wij wmax 1 Hence, the geometric structure of the mesh is encoded in weighting functions were proposed in the HoraudGraph Laplacian TutorialThe Laplacian of a cloud of points3-nearest neighbor Graph -radius graphKNN may guarantee thatthe Graph is connected(depends on theimplementation) -radius does notguarantee that the graphhas one connectedcomponentRadu HoraudGraph Laplacian TutorialThe Laplacian of a Graph with one connected componentLu= , 1= 0is the smallest :1n= ( )>.

7 0 =u>Lu= ni,j=1wij(u(i) u(j)) any two vertices are connected by a path, thenu= (u(1),..,u(n))needs to be constant at all vertices suchthat the quadratic form vanishes. Therefore, a Graph with oneconnected component has the constant vectoru1=1nas theonly eigenvector with HoraudGraph Laplacian TutorialA Graph withk >1connected componentsEach connected component has an associated , we can write matrixLas ablock diagonal matrix:L= The spectrum ofLis given by the union of the spectra block corresponds to a connected component, henceeach matrixLihas an eigenvalue0with multiplicity spectrum ofLis given by the union of the spectra eigenvalue 1= 0has HoraudGraph Laplacian TutorialThe eigenspace of 1= 0with multiplicitykThe eigenspace corresponding to 1=.

8 = k= 0isspanned by thekmutually orthogonal vectors:u1= (0000111110000)> RnThese vectors are theindicator vectorsof the Graph sconnected that1L1+..+1Lk=1nRadu HoraudGraph Laplacian TutorialThe Fiedler vector of the Graph LaplacianThe first non-null eigenvalue k+1is called the Fiedler corresponding eigenvectoruk+1is called the multiplicity of the Fiedler eigenvalue is always equal Fiedler value is thealgebraic connectivity of a Graph , thefurther from0, the more Fidler vector has been extensively used forspectralbi-partioningTheoretical results are summarized in Spielman & Teng 2007: HoraudGraph Laplacian TutorialEigenvectors of the Laplacian of connected graphsu1=1n,L1n= thethe Fiedler vectorwith multiplicity eigenvectors form an orthonormal basis:u>iuj= any eigenvectorui= (ui(v1).)

9 Ui(vn))>,2 i n:u>i1n= 0 Hence the components ofui,2 i nsatisfy:n j=1ui(vj) = 0 Each component is bounded by: 1<ui(vj)<1 Radu HoraudGraph Laplacian TutorialLaplacian Embedding : Mapping a Graph on a lineMap a weighted Graph onto a line such that connected nodesstay as close as possible, , minimize ni,j=1wij(f(vi) f(vj))2, or:arg minff>Lfwith:f>f= 1andf>1= 0 The solution is the eigenvector associated with the smallestnonzero eigenvalue of the eigenvalue problem:Lf= f,namely the Fiedler more details on this minimization see Golub & Van LoanMatrix Computations, chapter 8 (The symmetric eigenvalueproblem).Radu HoraudGraph Laplacian TutorialExample of mapping a Graph on the Fiedler vectorRadu HoraudGraph Laplacian TutorialLaplacian embeddingEmbed the Graph in ak-dimensional Euclidean space.

10 Theembedding is given by then kmatrixF= [ ]where thei-th row of this matrix f(i) corresponds to theEuclidean coordinates of thei-th Graph need to minimize (Belkin & Niyogi 03):arg i,j=1wij f(i) f(j) 2with:F>F= solution is provided by the matrix of eigenvectorscorresponding to theklowest nonzero eigenvalues of theeigenvalue problemLf= HoraudGraph Laplacian TutorialSpectral Embedding using theunnormalizedLaplacianCompute the eigendecompositionL=D theksmallest non-null eigenvalues 2 .. k+1 k+2 k+1= obtain then kmatrixU= [ +1]:U= u2(v1)..uk+1(v1)..u2(vn)..uk+1(vn) u>iuj= ij(orthonormal vectors), henceU>U= (2 i k+ 1) of this matrix is a mapping on HoraudGraph Laplacian TutorialExamples of one-dimensional mappingsu2u3u4u8 Radu HoraudGraph Laplacian TutorialEuclidean L- Embedding of the Graph s vertices(Euclidean)L- Embedding of a Graph :X= 12kU>= [ ]The coordinates of a vertexvjare:xj= u2(vj) +1(vj) k+1 Radu HoraudGraph Laplacian TutorialJustification for choosing the L-embeddingBoththecommute-time distance(CTD) andtheprincipal-component analysisof a Graph ( Graph PCA)are two important concepts; They allow to reason statistically ona Graph .