This edition first published 2013

© 2013 John Wiley & Sons, Ltd

Registered office

John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, United Kingdom

For details of our global editorial offices, for customer services and for information about how to apply for permission to reuse the copyright material in this book please see our website at www.wiley.com.

The right of the author to be identified as the author of this work has been asserted in accordance with the Copyright, Designs and Patents Act 1988.

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by the UK Copyright, Designs and Patents Act 1988, without the prior permission of the publisher.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books.

Designations used by companies to distinguish their products are often claimed as trademarks. All brand names and product names used in this book are trade names, service marks, trademarks or registered trademarks of their respective owners. The publisher is not associated with any product or vendor mentioned in this book.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. It is sold on the understanding that the publisher is not engaged in rendering professional services and neither the publisher nor the author shall be liable for damages arising herefrom. If professional advice or other expert assistance is required, the services of a competent professional should be sought.

Library of Congress Cataloging-in-Publication Data

Bolla, Marianna.

Spectral clustering and biclustering: learning large graphs and contingency tables / Marianna Bolla.

pages cm

Includes bibliographical references and index.

ISBN 978-1-118-34492-7 (hardback)

1. Multivariate analysis. 2. Contingency tables. 3. Graph theory. I. Title.

QA278.B65 2013

515′.35–dc23

2013011891

A catalogue record for this book is available from the British Library.

ISBN: 978-1-118-34492-7

To my son and students

Preface

When dealing with networks, statisticians want to explore the structure of the actual data set whatever it is. Meanwhile, we realized that statistical methods are not immediately applicable for graphs, as graph theory is mainly concerned with special structures which are too sensitive to minor changes. Therefore, we decided to bridge, at least partially, the gap between statistics and graph theory with ideas on how graphs and contingency tables can be considered as statistical data and how they can be treated by methods reminiscent of classical and modern techniques of multivariate statistical analysis. We want to provide answers to the demanding questions which arise when statisticians are confronted with large weighted graphs or rectangular arrays like microarrays. In contemporary data analysis, experts are striving to recover the structure of communication, social, and biological networks, or in other situations, to compare networks of different sizes and classify them based on a training sample. In the case of large data sets, random effects and measurement errors also have to be treated.

We plan to use existing knowledge on graph spectra and experiences in analyzing real-world data in the form of hypergraphs, weighted graphs, and contingency tables. At the end of the 1980s, together with my PhD advisor, Gábor Tusnády, we used spectral methods for a binary clustering problem, where the underlying matrix turned out to be the generalization of the graphs' Laplacian to hypergraphs. Then we defined the Laplacian for multigraphs and edge-weighted graphs, and went beyond the expanders by investigating gaps within the spectrum and used eigenvectors corresponding to some structural eigenvalues to find clusters of vertices. We also considered minimum multiway cuts with different normalizations that were later called ratio-and normalized cuts. In the 1990s, spectral clustering became a fashionable area and a lot of papers in this topic appeared, sometimes redefining or modifying the above notions, sometimes having a numerical flavor and suggesting algorithms without rigorous mathematical explanation.

At the turn of the millennium, thanks to the spread of the World Wide Web and the human genome project, there was a rush to investigate evolving graphs and random situations different from the classical Erds–Rényi one. Graph theorists, for example, László Lovász and co-authors, considered convergence of graph sequences and testable graph parameters, bringing –without their volition –statistical concepts into this discrete area. They also started to consider noisy graph and contingency table sequences, and testability of some balanced versions of the already defined minimum multiway cut densities. Meanwhile, physicists introduced other measures of characterizing a community structure of networks. In this book we discuss some penalized versions of the Newman–Girvan modularity and regular cuts which are present in situations when the network has clusters of vertices with a homogeneous information flow within or between them.

A wide array of classical and modern statistical methods are presented and adapted to weighted graphs and contingency tables. We recommend algorithms for recovering the structure of large networks burdened with random noise, further to clustering and classifying them. Through representations, we establish a common outline structure for the contents of each algorithm along with various fundamental elements which are combined via unified notions and principles. We only give a general treatment to the problems exposed; for more examples we refer to papers and also the supporting website (www.wiley.com/go/spectral) of the book. Hence, the book is a resource for professionals mining large datasets related to communication, social, biological, or industrial networks, and for students learning statistical methods applicable to networks.

Throughout the book we use advanced linear algebra, probability, and multivariate statistics. A collection of frequently used facts in these fields is to be found in the Appendices. However, a basic knowledge of graph theory and computer sciences suffices as we only consider statistical graph properties which are unaffected by minor perturbations of the vertex-or edge-weights, and we just touch upon the computational complexity of the proposed algorithms. We also discuss possible applications to real-life networks. However, the main contribution of this book is the well-motivated presentation and comparison of a great variety of statistical methods applicable to large networks or network sequences. Well-known facts from former books concerning graph spectra are not proven (references are given), but all other propositions and theorems are proven with mathematical precision. Therefore the book is suitable for a one-semester graduate course on this topic. For those who are interested only in the algorithms, these proofs can be skipped.

Marianna Bolla

Budapest, December 2012

Acknowledgements

I wish to express gratitude to persons whose books, papers, and lectures on spectral graph theory and multivariate statistics turned my interest to this field: F. Chung, D. M. Cvetkovic, M. Fiedler, A. J. Hoffman, B. Mohar, and C. R. Rao.

I am indebted to my PhD advisor, Gábor Tusnády with whom I have worked on several projects and applied statistical methods in real-life problems. I am grateful to László Lovász for valuable discussions on the spectral graph and graph convergence topics. I wish to thank many colleagues for their useful comments on the related research and applications: László Babai, András Benczur, Endre Boros, Imre Csiszár, Vill Csiszár, Zoltán Füredi, Ferenc Juhász, János Komlós, Vilmos Komornik, Tamás Lengyel, Nathan Linial, András Lukács, Péter Major, György Michaletzky, Dezs Miklós, Tamás F. Móri, Dénes Petz, Tomaz Pisanski, András Prékopa, András Recski, Lídia Rejt, Tamás Rudas, András Simonovits, Miklós Simonovits, Vera T. Sós, Domokos Szász, Gábor J. Székely, Endre Szemerédi, András Telcs, László Telegdi, Bálint Tóth, György Turán, and Katalin Vesztergombi. I am particularly indebted to Katalin Friedll, András Krámli, and János Tóth for promotive discussions, to Ákos Csizmadia for helping me to present the references of this book in a unified form; further, to Ibolya Barna, Miklós Gergi, and Péter István for their technical help.

I would like to thank my students at the Budapest University of Technology and Economics, Central European University, and Budapest Semester of Mathematics, who worked on the spectral clustering topic and helped me with questions, calculations, and processing computer programs: Andrea Bán, Erik Bodzsár, Brian Bullins, Sorathan Chaturapruek, Shiwen Chen, Ahmed Elbanna, Max Del Giudice, Haris Khan, Tamás Kói, Anett Lovas, Gábor Molnár–Sáska, Ildikó Priksz, Viktor Szabó, Zsolt Szabó, Joan Wang, and László Nagy who actually assisted me with preparing some figures for this book.

I am grateful to Károly Simon for encouraging me to write this book and letting me go on sabbatical two years ago when I assembled the pieces of this material together. The related research was partly supported by the Hungarian National Research Grant OTKA-KTIA 77778; and by the TÁMOP-4.2.2.C-11/1/KONV-2012-0001 project, sponsored by the European Union.

List of Abbreviations

Notational Abbreviations

General

set of complex numbers

set of real numbers

scalars (real or complex numbers)

vectors of real coordinates (column vectors)

vector of all 0 coordinates

vector of all 1 coordinates

matrices of real entries

means that B − A is positive semidefinite (A and B are symmetric matrices)

matrix of all zero entries

n × n identity matrix

transpose of the vector a or matrix A

Kronecker-sum of the matrices A and B

Kronecker-product of the matrices A and B

Schur or Hadamard product of the matrices A and B

Euclidean norm of the vector a

spectral norm of the matrix A (its maximal singular value)

determinant of the matrix A

Frobenius norm of the matrix A (squareroot of the sum of the squares of its singular values)

Schatten 4-norm of the matrix A (fourth root of the sum of the fourth powers of its singular values)

cut-norm of the matrix A

trace of the matrix A

‘little o’ of f(n), i.e., a function of n such that

‘big O’ of f(n), i.e., a function of n such that with some constant C, independent of n

a function of n such that Ω(f(n)) ≥ cf(n) with some constant c, independent of n

is and Ω(f(n)) at the same time

set of the k-partitions of {1, ..., n} (into disjoint, non-empty subsets)

Probability and Statistics

real-valued random variables

random vectors (column vectors)

expectation of the random variable X (scalar)

expectation of the random vector X (column vector)

covariance between the random variables X and Y

correlation between the random variables X and Y

variance of the random variable X (nonnegative scalar)

covariance matrix of the random vector X (symmetric, positive semidefinite matrix)

p-dimensional normal distribution with expectation (vector) μ and covariance matrix C

k-variance of the row vectors of matrix X

weighted k-variance of the row vectors of matrix X

Graphs

edge-weighted graph on vertex-set V and symmetric edge-weight matrix W of nonnegative entries (especially, for simple G, W is the adjacency matrix)

hypergraph with vertex-set V and set of hyper-edges E

number of edges emanating from the vertex-subset U of a simple graph

number of edges connecting the vertex subsets U and T of a simple graph

weighted cut between the vertex subsets U and T of an edge-weighted graph

generalized degree of vertex i of an edge-weighted graph G = (V, W)

degree vector comprised of the generalized degrees of vertices of an edge-weighted graph

=

degree matrix, i.e., diagonal matrix containing the generalized degrees in its main diagonal

Laplacian of the edge-weighted graph G = (V, W)

normalized Laplacian of the edge-weighted graph G = (V, W)

modularity matrix of the edge-weighted graph G = (V, W), when =1

normalized modularity matrix of the edge-weighted graph G = (V, W), when =1

Volume of the vertex subset U of an edge-weighted graph

k-way partition cut of the edge-weighted graph G = (V, W)

k-way normalized cut of the edge-weighted graph G = (V, W)

k-way Newman–Girvan modularity of the edge-weighted graph G = (V, W)

k-way balanced Newman–Girvan modularity of the edge-weighted graph G = (V, W)

k-way normalized Newman–Girvan modularity of the edge-weighted graph G = (V, W)

cut-norm of the graphon W

Contingency Tables

row-and columnn-sets of a contingency table C of nonnegative real entries

cut between the subsets R and C of the rows and columns of a contingency table

ith row-sum of the m × n contingency table C

jth column-sum of the m × n contingency table C

diagonal row-sum matrix

diagonal column-sum matrix

normalized contingency table or correspondence matrix

volumes of the row-and column-subsets U and T of a contingency table

normalized k-way bicut of the contingency table C

cut-norm of the contingon C

Verbal Abbreviations

cumulative distribution function

distance between vectors and/or subspaces

identically distributed (random variables)

independent, identically distributed (random variables)

probability density function

such that

Analysis of variance

Multivariate analysis of variance

spectral decomposition (of a symmetric matrix)

singular value decomposition (of a matrix)

Introduction

‘Happy families are all alike; every unhappy family is unhappy in its own way.’

Leo Tolstoy: Anna Karenina

Graphs with a small spectral gap can be very different by their nature, indeed. Those with a large spectral gap have been frequently studied since Metropolis et al. (1953); Nash-Williams (1959) and Cheeger (1970), establishing a lot of equivalent or near equivalent advisable features of them. There are beautiful results about the relation between this gap and the expanding properties of the graph (see e.g., Hoory, Linial and Widgerson (2006)), including a random walk view of Azran and Ghahramani (2006); Diaconis and Stroock (1991) and connectivity (the first results are due to Fiedler (1973) and Hoffman (1970)). Roughly speaking, graphs with a large spectral gap are good expanders; the random walk goes through them very quickly with a high mixing rate and short commute time, see for example Lovász (1993); Lovász and Winkler (1995); they are also good magnifiers as their vertices have many neighbors; in other words, their vertex subsets have a large boundary compared to their volumes characterized by the isoperimetric number: see Mohar (1988); equivalently, they have high conductance and show quasirandom properties discussed in Chung, Graham and Wilson (1989) and Chung and Graham (2008). Because of these favorable characteristics, they are indispensable in communication networks; further, there is basically one eigenvalue responsible for this property.

However, less attention has been paid to graphs with a small spectral gap, when several cases can occur: among others, the graph can be a bipartite expander (see Alon (1986)) or its vertices can be divided into two sparsely connected clusters, but the clusters themselves can be good expanders (see Ng et al. (2001) and Newman (2003)). In the case of several clusters of vertices the situation is even more complicated. The pairwise relations between the clusters and the within-cluster relations of vertices of the same cluster show a great variety; not surprisingly, there is more than one eigenvalue responsible for these versatile properties. Depending on the number and sign of the so-called structural eigenvalues of the normalized modularity matrix, defined in Bolla (2011), we help enable the reader to decide the number of underlying clusters and the type of connection between them.

Given a graph –simple or edge-weighted –that does not belong to the well manageable family of expanders, our task is to survey the numerous possibilities for this graph according to which it may have a structure. We wouldn't say that every such graph has its own structure, but there are types of relations between its vertices according to which they may form clusters. We prove and illustrate through random examples that based on the structural eigenvalues of the normalized modularity matrix, how the main types of intra-and inter-cluster relations can be established and the clusters themselves recovered via the corresponding eigenvectors. Our examples are mainly from the class of generalized random graphs. We deal with dense graphs as a statistical sample. Sparse graphs (like path, grid, or hypercube) are frequently used as examples where the minimum spectral gap shows up; however there are no sensible ways to divide their vertices into any number of clusters. Our methods are rather applicable to real-life situations when the number of edges is proportional to the square of the number of vertices; or in the edge-weighted graph setup, at least a linear number of weights in each row of the weight matrix differ from zero.

Spectra of graphs together with their application was discussed by several authors, for example, Biggs (1974); Chung (1997); Cvetkovic, Doob and Sachs (1979); von Luxburg (2007); Spielman (2007). There are quick numerical algorithms to find spectral or singular value decomposition (SD or SVD) of the graph or contingency table based matrix with normalization adopted to the objective function. Most of these algorithms use the k smallest (normalized or unnormalized) Laplacian eigenvalues which are capable to reveal a sparse k-way cut (see Lee et al. (2012); Louis et al. (2011)). We will not confine ourselves to the bottom of the Laplacian spectrum, but take into consideration the top eigenvalues as well, which together form the large absolute value (structural) eigenvalues of the normalized modularity matrix, introduced just for this convenience. As a statistician, I believe there must be a structure in each network. Theoretical results (like the Szemerédi's regularity lemma, see Komlós et al. (2002)) also support this, though sometimes with an enormously large number of clusters. There is a lot of knowledge about how some specific structures can be characterized by means of spectra, but little is known about how to recognize the structure itself. Sometimes the same continuous relaxation is used to optimize different types of cuts (see Ding et al. (2003)), sometimes it is noted that the result of the Laplacian-based clustering depends on the graph itself (see von Luxburg et al. (2008)). I plan to approach this problem from the opposite direction: first to be acquainted with the graph so as to apply the best possible clustering to it. This means that based on the spectrum (gaps between the structural and the bulk eigenvalues and the sign of the structural ones) we use the most appropriate eigenvectors for representation and clustering. We consider the graph as statistical data itself, find out which structure is expected, and then select the method.

Though spectral graph theory seems to be a versatile endless tale, we speak about it in the framework of a moderate length book. Of course, we cannot discuss all the details, but what we discuss is compatible with unified notation, and we just touch upon subjects (e.g., random walk view) that have been thoroughly discussed by other authors. However, there is reality behind every tale, and facing it helps us to unveil the problem. We learn, for example, that the reality behind the diabolic kernel trick – when using reproducing kernel Hilbert spaces – is the century old Riesz–Fréchet representation theorem, according to which linear functionals over a Hilbert space are in one-to-one correspondence with the space itself; here it is extended to non-linear functionals that are related to the elements of a more complicated Hilbert space (not the original one). Knowing this, the trick becomes a simple tool as to how the selection of an appropriate kernel helps us in discovering non-linearities in our data and separate clusters that cannot otherwise be separated by simply applying the k-means algorithm to it. We start the sections with a brief exposition of the problems and roughly explain the solution, but later on we encounter all the definitions and facts belonging to the issue. We elucidate everything with full precision and also point in new directions. The following explains the contents of the strongly interwined chapters.

Chapter 1 is devoted to multivariate analysis techniques for representing edge-weighted graphs and contingency tables. Different kinds of graph-based matrices are introduced together with spectra and spectral subspaces which optimize different quadratic placement problems subject to different constraints. Our purpose here is to develop tools for the unique treatment of the multiway cut problems of Chapter 2. These methods are reminiscent of classical methods of multivariate statistical analysis, like principal component analysis, correspondence analysis, or analysis of variance. As a result, we get low dimensional representation of the graph's vertices or rows and columns of the contingency table so that the representation somehow favors the classification criteria of Chapter 2. Non-linearities are treated by mapping the data into a feature space (reproducing kernel Hilbert space), which is a useful technique if we build a graph on given data points. We also generalize the notion of representation for joint distributions, and use it in Chapter 4 when convergence of normalized spectra is discussed.

In Chapter 2, minimum ratio and normalized multiway cut problems are presented together with modularity cuts. Since the optima of the corresponding objective functions are taken on partition vectors belonging to the hidden clusters, via Chapter 1, they are related to Laplacian, normalized Laplacian, or modularity spectra, whereas the precision of the estimates depends on the distance between the subspaces spanned by the corresponding eigenvectors and partition vectors. By an analysis of variance argument, this distance is the sum of the inner variances of the underlying clusters, the objective function of the k-means clustering. Therefore, instead of speaking about continuous relaxation of the discrete optimization tasks, we rather solve the combinatorial problems by using the same linear algebra machinery as in Chapter 1. In this way, estimates for minimal or maximal multiway cuts are obtained by relating the overall minima or maxima to those taken on partition vectors.

Chapter 3 applies the results of Chapters 1 and 2 for spectral clustering of large networks. Networks are modeled either by edge-weighted graphs or contingency tables, and usually subject to random errors due to their evolving and flexible nature. Asymptotic properties of SD and SVD of the involved matrices are discussed when not only the number of the graph's vertices or that of the rows and columns of the contingency table tends to infinity, but the cluster sizes also grow proportionally with them. Mostly, perturbation results for the SD and SVD of blown-up matrices—burdened with a Wigner-type error matrix—are investigated. Conversely, given a weight-matrix or rectangular array of nonnegative entries, we look for the underlying block-structure. We show that under very general circumstances, clusters of a large graph's vertices and simultaneously those of the rows and columns of a large contingency table can be identified with high probability. In this framework, so-called volume regular cluster pairs are also considered with homogeneous information flow within the clusters and between pairs of them; and their pairwise discrepancies are related to spectra.

In Chapter 4, the theory of convergent graph sequences and graphons, elaborated by graph theorists, is used for vertex-and edge-weighted graphs and contingency tables. The convergence can be formulated in terms of the cut-distance, and limit objects are defined. Testable parameters are nonparametric statistics defined on graphs and contingency tables that can be consistently estimated based on a smaller sample selected randomly from the underlying huge network. Real-word graphs or rectangular arrays are sometimes considered as samples from a large network, and we deduce the network's parameters from the same parameters of its smaller parts. The theory guarantees that this can be done if the investigated parameter is testable. We prove that certain balanced multiway cut densities are indeed testable, and the increasing noisy graph sequences of Chapter 3 converge in this sense too.

Chapter 5 presents parametric and nonparametric statistical methods to find the underlying clusters of a given network or to classify graphs or contingency tables given some distinct prototypes. In fact, the minimum multiway cuts or bicuts and maximum modularities of Chapter 2 are nonparametric statistics that are estimated by means of spectral methods. Algorithms for the representation-based spectral clustering are reviewed together with recommendations about the choice of the eigenvectors which are best capable to reveal the underlying structure. A special algorithm for finding disjoint clusters of the edges, and not necessarily disjoint clusters of the vertices of a hypergraph, is also presented. We also discuss parametric models and give maximum likelihood estimation for the parameters. Eventually, we discuss possible applications of discriminant analysis for classifying graphs and contingency tables.

Frequently used facts about linear operators, random matrices, and multivariate statistical methods are collected in the Appendices. We have relatively few illustrations as believe that instead of visualization, the step by step comprehension, rather than the delusive view, can lead to a deeper understanding of the topic.

References

Alon N. (1986) Eigenvalues and expanders. Combinatorica 6, 83–96.

Azran A. and Ghahramani Z. 2006 Spectral methods for automatic multiscale data clustering. Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2006), New York NY, (eds Fitzgibbon A., Taylor C.J. and Lecun Y.), IEEE Computer Society, Los Alamitos, California, pp. 190–197.

Biggs N.L. 1974 Algebraic Graph Theory, Cambridge University Press, Cambridge.

Bolla M. 2011 Penalized versions of the Newman–Girvan modularity and their relation to multi-way cuts and k-means clustering. Phys. Rev. E 84, 016108.

Cheeger J. 1970 A lower bound for the smallest eigenvalue of the Laplacian, in Problems in Analysis (ed. R. C. Gunning), Princeton Univ. Press, Princeton NJ, pp. 195–199.

Chung F. 1997 Spectral Graph Theory, CBMS Regional Conference Series in Mathematics 92. American Mathematical Society, Providence RI.

Chung F, Graham R.L. and Wilson R.K. 1989 Quasi-random graphs. Combinatorica 9, 345–362.

Chung F. and Graham R. 2008 Quasi-random graphs with given degree sequences, Random Struct. Algorithms 12, 1–19.

Cvetkovic D.M., Doob M. and Sachs H. 1979 Spectra of Graphs, Academic Press, New York.

Diaconis P. and Stroock D. 1991 Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab. 1, 36–62.

Ding C., He X., Zha H., Gu M. and Simon H.D. 2003 A Minmax Cut Spectral Method for Data Clustering and Graph Partitioning. Technical Report 54111, Lawrence Berkeley National Laboratory.

Fiedler M. 1973 Algebraic connectivity of graphs. Czech. Math. J. 23 (98), 298–305.

Hoffman A.J. 1970 On eigenvalues and colorings of graphs. In Graph Theory and its Applications (ed. Harris B), pp. 79–91. Academic Press, New York.

Hoory S., Linial N. and Widgerson A. 2006 Expander graphs and their applications. Bull. Amer. Math. Soc. (N. S.) 43 (4), 439–561.

Komlós J., Shokoufanden A., Simonovits M. and Szemerédi E. 2002 Szemerédi's Regularity Lemma and its Applications in Graph Theory, in Lecture Notes in Computer Science, Springer, Berlin, vol 2292, pp. 84–112.

Lee J.R., Gharan S.O. and Trevisan L. 2012 Multi-way spectral partitioning and higher-order Cheeger inequalities, in Proc. 44th Annual ACM Symposium on the Theory of Computing (STOC 2012), New York NY, pp. 1117–1130.

Louis A., Raghavendra P., Tetali P. and Vempala S. 2011 Algorithmic extension of Cheeger's inequality to higher eigenvalues and partitions, in Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science (eds Goldborg LA, Jansen K, Ravi R and Rolim JDP), Vol. 6845, Springer, pp. 315–326.

Lovász L. 1993 Random walks on graphs: a survey, in Combinatorics, Paul Erds is Eighty. János Bolyai Society, Mathematical Studies, Keszthely, Hungary, vol. 2, pp. 1–46.

Lovász L. and Winkler P. 1995 Exact mixing in an unknown Markov chain. Electron. J. Comb. 2, Paper R15, 1–14.

Metropolis N., Rosenblut A., Rosenbluth M., Teller A. and Teller E. 1953 Equation of state calculation by fast computing machines. J. Chem. Physics 21, 1087–1092.

Mohar B. 1988 Isoperimetric inequalities, growth and the spectrum of graphs. Linear Algebra Appl. 103, 119–131.

Nash-Williams CStJA 1959 Random walks and electronic currents in networks. Proc. Cambridge Phil. Soc. 55, 181–194.

Newman M.E.J 2003 Mixing patterns in networks. Phys. Rev. E 67, 026126.

Ng A.Y. Jordan M.I. and Weiss Y. 2001 On spectral clustering: analysis and an algorithm. Proc. 14th Neural Information Processing Systems Conference (NIPS 2001) (Dietterich T.G., Becker S. and Ghahramani Z. eds), MIT Press, Cambridge, MA, pp. 849–856.

Spielman D.A. 2007 Spectral graph theory and its applications. Proc. 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), Providence, RI, IEEE Computer Society, Los Alamitos, California, pp. 29–38.

von Luxburg U 2007 A tutorial on spectral clustering. Stat. Comput. 17 (4), 395–416.

von Luxburg U., Belkin M. and Bousquet O. 2008 Consistency of spectral clustering. Ann. Stat. 36 (2), 555–586.

1

Multivariate Analysis Techniques for Representing Graphs and Contingency Tables

Graph spectra have been used for about 40 years to recover the structure of graphs. Different kinds of spectra are capable of finding multiway cuts corresponding to different optimization criteria. While eigenvalues give estimates for the objective functions of the discrete optimization problems, eigenvectors are used to find clusters of vertices which approximately solve the problems. These methods are reminiscent of some classical methods of multivariate statistical analysis (see Appendix C). Throughout this chapter, methods of principal component analysis and correspondence analysis are used to solve quadratic placement tasks on weighted graphs and contingency tables. As a result, we get low dimensional representation of the graph's vertices or rows and columns of the contingency table by means of linear methods so that the representation somehow favors our classification criteria. Non-linearities are treated by mapping the data into a feature space (reproducing kernel Hilbert space). We also generalize the notion of representation for joint distributions.

1.1 Quadratic Placement Problems for Weighted Graphs and Hypergraphs

In multivariate statistical analysis, principal component analysis and factor analysis (see Section C.1) are crucial methods for reducing the dimensionality of the data via representing them by a smaller number of 3 independent factors. The representation also gives rise to clustering the data in the factor space. Given an n × n positive definite covariance matrix C of a random vector, the principal components are determined successively, and they are the maximum variance normalized linear combinations of the components of the underlying random vector conditioned on the uncorrelatedness (in the Gaussian case, independence) of them.

Now, our data matrix corresponds to a graph. First, let G = (V, E) be a simple graph on the vertex-set V and edge-set E with |V| = n and |E| ≤ nchoose2. Thus, the |E| × n data matrix B has 0-1 entries, the rows correspond to the edges, the columns to the vertices, and bij is 1 or 0 depending on whether the edge i contains the vertex j as an endpoint or not. The Gram-matrix (see Definition A.3.6) C = BTB is the non-centralized covariance matrix based on the data matrix B, and is both positive definite (provided there are no multiple edges) and a Frobenius-type matrix with nonnegative entries to which Theorem A.3.30 is applicable. Sometimes the matrix C is called signless Laplacian (see Cvetkovi et al. (1997)) and its eigenspaces are used to compare cospectral graphs. It is easy to see that C = D + A, where A = (aij) is the usual adjacency matrix of G (it is symmetric and aij is 1 or 0 depending on whether vertices i and j are connected or not; aii = 0, i = 1, ..., n), while D is the so-called degree-matrix, that is, diagonal matrix, containing the vertex degrees in its main diagonal. A being a Frobenius-type matrix (see Theorem A.3.30), its maximum absolute value eigenvalue is positive, and by Proposition A.3.33, it is at most the maximum vertex-degree, and apart from the trivial case –when there are no edges at all –it is indefinite, as the sum of its eigenvalues, that is, the trace of A, is zero.

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!