Finding Dense Structures in Graphs and Matrices

Abstract

We will study several questions with a common theme of finding "structure" in graphs and matrices. In particular, in graphs we study problems related to finding dense induced subgraphs. Many of these questions have been studied extensively, such as the problem of finding large cliques in a graph, and more recently, the small-set-expansion conjecture. Problems of this nature also arise in many contexts in practice, such as in finding 'communities' in social networks, and in understanding properties of the web graph.

We then study questions related to the spectra of matrices. Singular values of matrices are used extensively to 'extract structure' from matrices (for instance, in principal component analysis). We will study a generalization of the maximum singular value, namely the "q to p" norm of a matrix A, and the complexity of approximating this quantity. This question turns out to have many flavors for different values of p and q, which we will explore in detail.

The technical contributions of the thesis can be summarized as follows:

We study in detail the so-called densest k-subgraph problem. Given a graph G, the aim is to find an induced subgraph on k vertices with as many edges as possible. The approximability of densest k-subgraph is a notorious open problem, with the best algorithms having a "polynomial" approximation ratio, i.e., n^c for some constant c, while the best hardness results rule out a small constant factor (roughly 1.4) approximation.

In the thesis, we will present the best known algorithm for the problem, which gives roughly an n^{1/4} factor approximation. Further, our algorithm and its analysis point to a simple average case (or "planted") version of the problem, which seems beyond our current algorithmic techniques.

Next, we explore the complexity of computing the q-to-p norm of a matrix for different ranges of the parameters p,q. For p le q, we develop a better understanding of the complexity: in particular, for an important special case in which A has non-negative entries, we give a polynomial time algorithm to compute the norm up to any precision. We also prove that without such a restriction, the problem is hard to approximate to an "almost polynomial" factor.

For p >q, these quantities are called "hypercontractive" norms, and computing these would have applications to questions such as certifying the `restricted isometry property', and to certifying small-set expansion.

Finally, we propose and study a problem which can be seen as a `matrix variant' of the so-called maximum density subgraph problem for graphs. We will call this 'QP-Ratio' -- a ratio version of the familiar quadratic programming problem. The problem is a close cousin of many questions we study in the thesis, and it seems to highlight the difficulty in capturing the constraint $x_i in {-1,0,1}$ using convex programming relaxations.