Generalizing the Motzkin-Straus Theorem to Edge-Weighted Graphs, with Applications to Image Segmentation

Massimiliano Pavan, Marcello Pelillo

Abstract

The Motzkin-Straus theorem is a remarkable result from graph theory that has recently found various applications in computer vision and pattern recognition. Given an unweighted undirected graph G with adjacency matrix A, it establishes a connection between the local/global solutions of the following quadratic program: $$ maximize x^T A x / 2 $$ $$subject to e^T x=1, x \in \mathbb{R}_+^n $$ where e = (1,...,1) T , and the maximal/maximum cliques of G. Given an edge-weighted undirected graph G and the corresponding weight matrix A, in this paper we address the following question: What kind of (combinatorial) structures of G are associated to the (continuous) local solutions of our quadratic program? We show that these structures correspond to a “weighted” generalization of maximal cliques, thereby providing a first step towards an edge-weighted generalization of the Motzkin-Straus theorem. Moreover, we show how these structures can be relevant in clustering as well as image segmentation problems. We present experimental results on real-world images which show the effectiveness of the proposed approach.
BibTeX
@inproceedings{pavan2003generalizing,
  author = {Massimiliano Pavan and Marcello Pelillo},
  title = {{Generalizing the Motzkin-Straus Theorem to Edge-Weighted Graphs, with Applications to Image Segmentation}},
  booktitle = {EMMCVPR},
  year = {2003},
  doi = {10.1007/978-3-540-45063-4\_31},
}

Loading related content...

Figure