Random Graph Modeling and Discovery

Abstract

In the first part of this thesis, we present a general class of models for random graphs that is applicable to a broad range of problems, including those in which graphs have complicated edge structures. These models need not be conditioned on a fixed number of vertices, as is often the case in the literature, and can be used for problems in which graphs have attributes associated with their vertices and edges. To allow structure in these models, a framework analogous to graphical models is developed for random graphs.

In the second part of this thesis, we consider the situation in which there is an unknown graph that one wants to determine. This is a common occurrence since, in general, entities in the world are not directly observable, but must be inferred from some signal. We consider a general framework for uncovering these unknown graphs by a sequence of ‘tests’ or ‘questions’. We refer to this framework as graph discovery.

In the third part of this thesis, we apply graph discovery to a problem in computer vision. To evaluate how well vision systems perform, their interpretations of imagery must be compared to the true ones. Often, image interpretations can be expressed as graphs; for example, vertices can represent objects and edges can represent relationships between objects. Thus, an image, before it is interpreted, corresponds to an unknown graph, and the interpretation of an image corresponds to graph discovery. In this work, we are interested in the evaluation of vision systems when these representation graphs are complex. We propose a visual Turing test for this purpose.