Efficient Inference with Cardinality-based Clique Potentials

Efficient Inference with Cardinality-based Clique Potentials
Rahul Gupta - IBM Research Lab, New Delhi, India Ajit A. Diwan - IIT Bombay, India Sunita Sarawagi - IIT Bombay, India
Many collective labeling tasks require inference on graphical models where the clique potentials depend only on the number of nodes that get a particular label. We design efficient inference algorithms for various families of such potentials. Our algorithms are exact for arbitrary cardinality-based clique potentials on binary labels and for max-like and ma jority-like clique potentials on multiple labels. Moving towards more complex potentials, we show that inference becomes NPhard even on cliques with homogeneous Potts potentials. We present a 13 -approximation 15 algorithm with runtime sub-quadratic in the clique size. In contrast, the best known previous guarantee for graphs with Potts potentials is only 0.5. We perform empirical comparisons on real and synthetic data, and show that our proposed methods are an order of magnitude faster than the well-known Tree-based re-parameterization (TRW) and graph-cut algorithms.

Rahul Gupta - IBM Research Lab, New Delhi, India
Ajit A. Diwan - IIT Bombay, India
Sunita Sarawagi - IIT Bombay, India

Many collective labeling tasks require inference on graphical models where the clique potentials depend only on the number of nodes that get a particular label. We design efficient inference algorithms for various families of such potentials. Our algorithms are exact for arbitrary cardinality-based clique potentials on binary labels and for max-like and ma jority-like clique potentials on multiple labels. Moving towards more complex potentials, we show that inference becomes NPhard even on cliques with homogeneous Potts potentials. We present a 13 -approximation 15 algorithm with runtime sub-quadratic in the clique size. In contrast, the best known previous guarantee for graphs with Potts potentials is only 0.5. We perform empirical comparisons on real and synthetic data, and show that our proposed methods are an order of magnitude faster than the well-known Tree-based re-parameterization (TRW) and graph-cut algorithms.