In this talk, I will describe the use of approximation algorithms for
intractable graph problems as "experimental probes" of large informatics
graphs.  These graphs, e.g., extremely large social and information
networks that are ubiquitous in modern internet applications, have
numerous subtle and counterintuitive properties, and determining even
basic structural properties (aside from very simple statistics like
degree distributions and the probability of closing triangles) in a
reliable manner can be surprisingly difficult.  Significantly for the
method I will describe, approximation algorithms, in particular those
taking advantage of randomization, do not in general return the
combinatorial optimum, but instead they return an ensemble of solutions,
the properties of which depend sensitively on the details of the
algorithm.  Moreover, approximation algorithms with a geometric flavor
can often be viewed as implicitly smoothing or providing regularization,
a feature which can aid in interpreting their output.

As an application of this method, I will describe results from
"experimentally probing" large informatics graphs with approximation
algorithms for the graph partitioning problem.  This problem is of wide
interest in scientific computing, data analysis, and machine learning,
and it is intimately related to questions of clustering and
classification in those application domains.  Moreover, there exists a
rich suite of approximation algorithms, both theoretical and practical,
the relative strengths and weaknesses of which are well known, for
approximating the solution to this problem.  I will describe results
from spectral and flow-based algorithms, recently-developed theoretical
algorithms combining ideas from both of these classical methods, as well
as commonly-used heuristics like Metis.  In addition, I will describe
the use of these methods to ask questions such as whether informatics
graph are even consistent with the manifold hypothesis commonly made in
machine learning and data analysis.