Large Graphs: Modeling, Algorithms, and Applications

Large data sets emerge in a variety of applications, from signal processing to web search and recommendation engines to biological assays. In many cases, these data sets may be naturally modeled as a graph. For example:

1. A graph structure can be used to model static or dynamic interactions on a network substrate (e.g., the traffic on a network, gene activation in gene networks, chemical reactions in a biochemical network, interactions among friends in a social network, etc.);


2. A graph structure can be used to model the dynamics of a network changing in time (e.g., a physical network such as an electric grid, the web or internet as it evolves in time; a growing social network, etc.);


3. A graph structure may capture geometric information about the data itself (e.g., similarity graphs constructed from point clouds representing data sets and are routinely used in machine learning and in data-driven statistical models);


4. A graph structure may underlie statistical models for the data (e.g., graphical models are commonly used to model conditional independence structure between random variables).

The focus of the workshop will be on the mathematical, algorithmic, and statistical questions that arise in graph-based machine learning and data analysis, with an emphasis on graphs that arise in the above settings, as well as the corresponding algorithms and motivating applications. Thus, this workshop will be an opportunity for researchers from diverse fields to get together and share problems and techniques for handling these graphs structures. The connections — mathematical, computational, and practical — that arise between these seemingly-diverse problems and approaches will be emphasized. In light of this, particular topics that will be emphasized will include: computational techniques (randomized and online algorithms, fast simplification algorithms, etc.) that are needed when the graph considered are very large; function approximation (by, e.g., using kernels on graphs) and its applications to traditional machine learning methods; graph-based topological methods for the study of the geometry of data and networks; issues that arise with graph-based statistical modeling and associated algorithmic issues.