In spite of the very successful use of graphs in low-level vision and image processing, more complicated structures that appear in higher-level vision have been eluding such abstraction. In particular, handling higher-order relationships between data points seem to require something more than, or in addition to, graph.
One problem with higher-order cliques is that there are too many of them, since the number of possible cliques grows exponentially with its size. Yet those cliques in which we are interested are only a small fraction of the possible ones.
For example, while a clique formed by the points on a line would tend to be more important than random cliques of the same size, such cliques form a tiny minority.
Moreover, such important cliques tend to be describable in a compact manner, e.g., by the equation of the line. In this talk, I will describe an ongoing effort to utilize a sparse description, or representation, of structures to organize higher- order relations between data points, as well as some related optimization problems that arise in the process.