WIXLIB

Our Datasetconsists of 130 RGCs each of which in turn consists ofA sequence of 3D sample points along dendrite arbors obtained byNeurolucida R (requires intensive human interaction)Connectivity and branching information by the same softwareEach soma is represented as a sequence of points traced along itsboundary (circular/ring shape)saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM12 / 40

Our Datasetconsists of 130 RGCs each of which in turn consists ofA sequence of 3D sample points along dendrite arbors obtained byNeurolucida R (requires intensive human interaction)Connectivity and branching information by the same softwareEach soma is represented as a sequence of points traced along itsboundary (circular/ring shape)saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM12 / 40

Our Datasetconsists of 130 RGCs each of which in turn consists ofA sequence of 3D sample points along dendrite arbors obtained byNeurolucida R (requires intensive human interaction)Connectivity and branching information by the same softwareEach soma is represented as a sequence of points traced along itsboundary (circular/ring shape)saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM12 / 40

Our Datasetconsists of 130 RGCs each of which in turn consists ofA sequence of 3D sample points along dendrite arbors obtained byNeurolucida R (requires intensive human interaction)Connectivity and branching information by the same softwareEach soma is represented as a sequence of points traced along itsboundary (circular/ring shape) Constructing a graph representing dendrite structures per RGC is verynatural and simple! In fact, we constructed a tree (i.e., a connected graphwithout cycles/loops) by replacing the soma ring by a single vertexrepresenting a center of the soma.saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM12 / 40

Our Dataset Treessaito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM13 / 40

Our Dataset Trees . . .Let G be a graph (in fact a tree) representing an RGC.Let V V (G ) {v1 , . . . , vn } where vk R3 , be a set of verticesrepresenting sample points along dendrite arbors. n ranges between565 and 24474 depending on the RGCs.Let E E (G ) {e1 , . . . , em } be a set of edges where ek (vi , vj )represents an edge (or line segment) connecting between adjacentvertices vi , vj for some 1 i, j n. Note that E (G ) V (G ) 1since G is a tree.Let d(vk ) dvk be the degree of the vertex vk . In our dataset,max max d(vk ) 8,130 cellskmin max d(vk ) 3.130 cellskIn principle, we should consider the weighted graph with weightswek : kvi vj k 1 . But for simplicity, we only consider theunweighted graphs/trees here. (One could justify this by resamplingthe dendrite coordinates with a uniform sampling rate.)saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM14 / 40

Our Dataset Trees . . .Let G be a graph (in fact a tree) representing an RGC.Let V V (G ) {v1 , . . . , vn } where vk R3 , be a set of verticesrepresenting sample points along dendrite arbors. n ranges between565 and 24474 depending on the RGCs.Let E E (G ) {e1 , . . . , em } be a set of edges where ek (vi , vj )represents an edge (or line segment) connecting between adjacentvertices vi , vj for some 1 i, j n. Note that E (G ) V (G ) 1since G is a tree.Let d(vk ) dvk be the degree of the vertex vk . In our dataset,max max d(vk ) 8,130 cellskmin max d(vk ) 3.130 cellskIn principle, we should consider the weighted graph with weightswek : kvi vj k 1 . But for simplicity, we only consider theunweighted graphs/trees here. (One could justify this by resamplingthe dendrite coordinates with a uniform sampling rate.)saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM14 / 40

Our Dataset Trees . . .Let G be a graph (in fact a tree) representing an RGC.Let V V (G ) {v1 , . . . , vn } where vk R3 , be a set of verticesrepresenting sample points along dendrite arbors. n ranges between565 and 24474 depending on the RGCs.Let E E (G ) {e1 , . . . , em } be a set of edges where ek (vi , vj )represents an edge (or line segment) connecting between adjacentvertices vi , vj for some 1 i, j n. Note that E (G ) V (G ) 1since G is a tree.Let d(vk ) dvk be the degree of the vertex vk . In our dataset,max max d(vk ) 8,130 cellskmin max d(vk ) 3.130 cellskIn principle, we should consider the weighted graph with weightswek : kvi vj k 1 . But for simplicity, we only consider theunweighted graphs/trees here. (One could justify this by resamplingthe dendrite coordinates with a uniform sampling rate.)saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM14 / 40

Our Dataset Trees . . .Let G be a graph (in fact a tree) representing an RGC.Let V V (G ) {v1 , . . . , vn } where vk R3 , be a set of verticesrepresenting sample points along dendrite arbors. n ranges between565 and 24474 depending on the RGCs.Let E E (G ) {e1 , . . . , em } be a set of edges where ek (vi , vj )represents an edge (or line segment) connecting between adjacentvertices vi , vj for some 1 i, j n. Note that E (G ) V (G ) 1since G is a tree.Let d(vk ) dvk be the degree of the vertex vk . In our dataset,max max d(vk ) 8,130 cellskmin max d(vk ) 3.130 cellskIn principle, we should consider the weighted graph with weightswek : kvi vj k 1 . But for simplicity, we only consider theunweighted graphs/trees here. (One could justify this by resamplingthe dendrite coordinates with a uniform sampling rate.)saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM14 / 40

Our Dataset Trees . . .Let G be a graph (in fact a tree) representing an RGC.Let V V (G ) {v1 , . . . , vn } where vk R3 , be a set of verticesrepresenting sample points along dendrite arbors. n ranges between565 and 24474 depending on the RGCs.Let E E (G ) {e1 , . . . , em } be a set of edges where ek (vi , vj )represents an edge (or line segment) connecting between adjacentvertices vi , vj for some 1 i, j n. Note that E (G ) V (G ) 1since G is a tree.Let d(vk ) dvk be the degree of the vertex vk . In our dataset,max max d(vk ) 8,130 cellskmin max d(vk ) 3.130 cellskIn principle, we should consider the weighted graph with weightswek : kvi vj k 1 . But for simplicity, we only consider theunweighted graphs/trees here. (One could justify this by resamplingthe dendrite coordinates with a uniform sampling rate.)saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM14 / 40

Outline1Motivations2Our Dataset3Our Strategy4Why Graph Laplacians?5Preliminary Results6Conclusions & Future edu (UC Davis)Graph Laplacians on DendritesIPAM15 / 40

Our StrategyStep 1: Construct the Laplacian matrix (often called thecombinatorial Laplacian matrix)L(G ) : D(G ) A(G )D(G ) : diag(dv1 , . . . , dvn )the degree matrixA(G ) (aij ) the adjacency matrix where(1 if vi vj ;aij : 0 otherwise.Step 2: Compute the eigenvalues of L(G );Step 3: Construct features using these eigenvalues;Step 4: Repeat the above steps for all the RGCs and feed thesefeature vectors to clustering algorithms.saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM16 / 40

Our StrategyStep 1: Construct the Laplacian matrix (often called thecombinatorial Laplacian matrix)L(G ) : D(G ) A(G )D(G ) : diag(dv1 , . . . , dvn )the degree matrixA(G ) (aij ) the adjacency matrix where(1 if vi vj ;aij : 0 otherwise.Step 2: Compute the eigenvalues of L(G );Step 3: Construct features using these eigenvalues;Step 4: Repeat the above steps for all the RGCs and feed thesefeature vectors to clustering algorithms.saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM16 / 40

Our StrategyStep 1: Construct the Laplacian matrix (often called thecombinatorial Laplacian matrix)L(G ) : D(G ) A(G )D(G ) : diag(dv1 , . . . , dvn )the degree matrixA(G ) (aij ) the adjacency matrix where(1 if vi vj ;aij : 0 otherwise.Step 2: Compute the eigenvalues of L(G );Step 3: Construct features using these eigenvalues;Step 4: Repeat the above steps for all the RGCs and feed thesefeature vectors to clustering algorithms.saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM16 / 40

Our StrategyStep 1: Construct the Laplacian matrix (often called thecombinatorial Laplacian matrix)L(G ) : D(G ) A(G )D(G ) : diag(dv1 , . . . , dvn )the degree matrixA(G ) (aij ) the adjacency matrix where(1 if vi vj ;aij : 0 otherwise.Step 2: Compute the eigenvalues of L(G );Step 3: Construct features using these eigenvalues;Step 4: Repeat the above steps for all the RGCs and feed thesefeature vectors to clustering algorithms.saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM16 / 40

Outline1Motivations2Our Dataset3Our Strategy4Why Graph Laplacians?5Preliminary Results6Conclusions & Future edu (UC Davis)Graph Laplacians on DendritesIPAM17 / 40

Why Graph Laplacians?Eigenvalues of L(G ) reflect various intrinsic geometric informationabout the graph includingconnectivity or the number of separated componentsdiameter (the maximum distance over all pairs of vertices)mean distance, . . .Fan Chung: Spectral Graph Theory, AMS, 1997is an intertwined tale of eigenvalues and their use inunlocking a thousand secrets about graphs.Eigenvectors of L(G ) also play a useful role to understand a graph(e.g., the discrete nodal domain theorem useful for grouping vertices;see Bıyıkoğlu, Leydold, & Stadler, LNM, Springer, 2007)saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM18 / 40

Why Graph Laplacians?Eigenvalues of L(G ) reflect various intrinsic geometric informationabout the graph includingconnectivity or the number of separated componentsdiameter (the maximum distance over all pairs of vertices)mean distance, . . .Fan Chung: Spectral Graph Theory, AMS, 1997is an intertwined tale of eigenvalues and their use inunlocking a thousand secrets about graphs.Eigenvectors of L(G ) also play a useful role to understand a graph(e.g., the discrete nodal domain theorem useful for grouping vertices;see Bıyıkoğlu, Leydold, & Stadler, LNM, Springer, 2007)saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM18 / 40

Why Graph Laplacians?Eigenvalues of L(G ) reflect various intrinsic geometric informationabout the graph includingconnectivity or the number of separated componentsdiameter (the maximum distance over all pairs of vertices)mean distance, . . .Fan Chung: Spectral Graph Theory, AMS, 1997is an intertwined tale of eigenvalues and their use inunlocking a thousand secrets about graphs.Eigenvectors of L(G ) also play a useful role to understand a graph(e.g., the discrete nodal domain theorem useful for grouping vertices;see Bıyıkoğlu, Leydold, & Stadler, LNM, Springer, 2007)saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM18 / 40

Why Graph Laplacians?Eigenvalues of L(G ) reflect various intrinsic geometric informationabout the graph includingconnectivity or the number of separated componentsdiameter (the maximum distance over all pairs of vertices)mean distance, . . .Fan Chung: Spectral Graph Theory, AMS, 1997is an intertwined tale of eigenvalues and their use inunlocking a thousand secrets about graphs.Eigenvectors of L(G ) also play a useful role to understand a graph(e.g., the discrete nodal domain theorem useful for grouping vertices;see Bıyıkoğlu, Leydold, & Stadler, LNM, Springer, 2007)saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM18 / 40

Why Graph Laplacians?Eigenvalues of L(G ) reflect various intrinsic geometric informationabout the graph includingconnectivity or the number of separated componentsdiameter (the maximum distance over all pairs of vertices)mean distance, . . .Fan Chung: Spectral Graph Theory, AMS, 1997is an intertwined tale of eigenvalues and their use inunlocking a thousand secrets about graphs.Eigenvectors of L(G ) also play a useful role to understand a graph(e.g., the discrete nodal domain theorem useful for grouping vertices;see Bıyıkoğlu, Leydold, & Stadler, LNM, Springer, 2007)saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM18 / 40

Why Graph Laplacians?Eigenvalues of L(G ) reflect various intrinsic geometric informationabout the graph includingconnectivity or the number of separated componentsdiameter (the maximum distance over all pairs of vertices)mean distance, . . .Fan Chung: Spectral Graph Theory, AMS, 1997is an intertwined tale of eigenvalues and their use inunlocking a thousand secrets about graphs.Eigenvectors of L(G ) also play a useful role to understand a graph(e.g., the discrete nodal domain theorem useful for grouping vertices;see Bıyıkoğlu, Leydold, & Stadler, LNM, Springer, 2007)saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM18 / 40

Why Graph Laplacians?Eigenvalues of L(G ) reflect various intrinsic geometric informationabout the graph includingconnectivity or the number of separated componentsdiameter (the maximum distance over all pairs of vertices)mean distance, . . .Fan Chung: Spectral Graph Theory, AMS, 1997is an intertwined tale of eigenvalues and their use inunlocking a thousand secrets about graphs.Eigenvectors of L(G ) also play a useful role to understand a graph(e.g., the discrete nodal domain theorem useful for grouping vertices;see Bıyıkoğlu, Leydold, & Stadler, LNM, Springer, 2007)saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM18 / 40

Aside: Graph Laplacian of a Line DCT Type II Basis 1 1 1 2 1 1 2 1 L(G ) . . 1 . . 2 1 1 1The eigenvectors of this matrix are exactly the DCT Type II basis vectorsused for the JPEG image compression standard! (See e.g., Strang, SIAMReview, 1999).saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM19 / 40

Some Properties of Graph LaplaciansLet f L2 (V ). ThenL(G )f (u) du f (u) Xf (v ),v ui.e., this is a generalization of the finite difference approximation tothe Laplace operator.Eigenvalues of L(G ) cannot uniquely determine the graph G . Kac (1966): “Can one hear the shape of a drum?” Gordon,Webb, & Wolpert (1992): “One cannot hear the shape of a drum.”An example of “isospectral” graphs (Tan, 1998; Fujii & Katsuda,1999):saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM20 / 40

Some Properties of Graph LaplaciansLet f L2 (V ). ThenL(G )f (u) du f (u) Xf (v ),v ui.e., this is a generalization of the finite difference approximation tothe Laplace operator.Eigenvalues of L(G ) cannot uniquely determine the graph G . Kac (1966): “Can one hear the shape of a drum?” Gordon,Webb, & Wolpert (1992): “One cannot hear the shape of a drum.”An example of “isospectral” graphs (Tan, 1998; Fujii & Katsuda,1999):saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM20 / 40

Some Properties of Graph LaplaciansLet f L2 (V ). ThenL(G )f (u) du f (u) Xf (v ),v ui.e., this is a generalization of the finite difference approximation tothe Laplace operator.Eigenvalues of L(G ) cannot uniquely determine the graph G . Kac (1966): “Can one hear the shape of a drum?” Gordon,Webb, & Wolpert (1992): “One cannot hear the shape of a drum.”An example of “isospectral” graphs (Tan, 1998; Fujii & Katsuda,1999):saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM20 / 40

Some Properties of Graph LaplaciansLet f L2 (V ). ThenL(G )f (u) du f (u) Xf (v ),v ui.e., this is a generalization of the finite difference approximation tothe Laplace operator.Eigenvalues of L(G ) cannot uniquely determine the graph G . Kac (1966): “Can one hear the shape of a drum?” Gordon,Webb, & Wolpert (1992): “One cannot hear the shape of a drum.”An example of “isospectral” graphs (Tan, 1998; Fujii & Katsuda,1999):saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM20 / 40

Some Properties of Graph Laplacians . . .However, certain classes of graphs can be completely determined bytheir Laplacian spectra: starlike trees (Omidi & Tajbakhsh, 2007),centipedes (Boulet, 2008), . . . some attempts to reconstruct graphs from their Laplacian spectravia combinatorial optimization (e.g., Comellas & Diaz-Lopez, 2008)Nothing prevents us from using the Laplacian spectra forcharacterizing dendrite patterns!saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM21 / 40

Some Properties of Graph Laplacians . . .However, certain classes of graphs can be completely determined bytheir Laplacian spectra: starlike trees (Omidi & Tajbakhsh, 2007),centipedes (Boulet, 2008), . . . some attempts to reconstruct graphs from their Laplacian spectravia combinatorial optimization (e.g., Comellas & Diaz-Lopez, 2008)Nothing prevents us from using the Laplacian spectra forcharacterizing dendrite patterns!saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM21 / 40

Some Properties of Graph Laplacians . . .However, certain classes of graphs can be completely determined bytheir Laplacian spectra: starlike trees (Omidi & Tajbakhsh, 2007),centipedes (Boulet, 2008), . . . some attempts to reconstruct graphs from their Laplacian spectravia combinatorial optimization (e.g., Comellas & Diaz-Lopez, 2008)Nothing prevents us from using the Laplacian spectra forcharacterizing dendrite patterns!saito@math.ucdavis.edu (UC Davis)Graph Laplacians on DendritesIPAM21 / 40

Some Properties of Graph Laplacians . . .However, certain classes of graphs can be completely determined bytheir Laplacian spectra: starlike trees (Omidi & Tajbakhsh, 2007),centipedes (Boulet, 2008), . . . some attempts to reconstruct graphs from their Laplacian spectravia combinatorial optimization (e.g., Co

Cells in Retina (from Hubel: Eye, Brain, and Vision, 1995) saito@math.ucdavis.edu (UC Davis) Graph Laplacians on Dendrites IPAM 5 / 40. . representing a center of the soma. saito@math.ucdavis.edu (UC Davis) Graph Laplacians on Dendrites IPAM 12 / 40. Our Dataset consists of 130 RGCs each of which in turn consists of