# Generalized Collective Inference With Symmetric Clique Potentials

Rahul Gupta Sunita Sarawagi Ajit A. Diwan {grahul,sunita,aad}@cse.iitb.ac.in Indian Institute of Technology, Bombay, India

## Abstract

Many tasks like image segmentation, web page classification, and information extraction can be cast as joint inference tasks in collective graphical models. Such models exploit any inter-instance associative dependence to output more accurate labelings. However existing collective models support very limited kind of associativity - like associative labeling of different occurrences of the same word in a text corpus. This restricts accuracy gains from using such models.

In this work we make two major contributions. First, we propose a more general collective inference framework that encourages various data instances to agree on a set of properties **of their labelings. Agreement**
is encouraged through symmetric clique potential functions. We show that known collective models are specific instantiations of our framework with certain very simple properties. We demonstrate that using non-trivial properties can lead to bigger gains, and present a systematic inference procedure in our framework for a large class of such properties. In our inference procedure, we perform message passing on the cluster graph, where property-aware messages are computed with cluster specific **algorithms. Ordinary property-oblivious message** passing schemes are intractable in such setups. We show that **property conformance, as encouraged in our** framework, provides an inference-only solution for domain **adaptation. Our experiments on bibliographic**
information extraction illustrate significant test error reduction over unseen domains.

Our second major contribution is a suite of algorithms to compute messages from clique clusters to other clusters for a variety of symmetric clique potentials (the clique inference **problem). Our algorithms are exact**
for arbitrary cardinality-based clique potentials on binary labels and for max-like and majority-like clique potentials on multiple labels. For majority-like potentials, we also provide an efficient Lagrangian Relaxation based algorithm that compares favorably with the exact algorithm. Moving towards more complex potentials, we show that clique inference becomes NP-hard for cliques with homogeneous Potts potentials. We present a 13 15 **-approximation algorithm with runtime sub-quadratic in the clique size. In contrast, the best known**
previous guarantee for graphs with Potts potentials is only 12

. We perform empirical comparisons on real and synthetic data, and show that our proposed methods for Potts **potentials are an order of magnitude faster** than the well-known Tree-based re-parameterization (TRW) **and graph-cut algorithms. We demonstrate that**
our Lagrangian Relaxation based algorithm for majority potentials beats the best applicable heuristic, ICM,
in a variety of scenarios.

## 1 Introduction

A variety of structured tasks such as image segmentation, information extraction, part of speech tagging, text chunking, and named entity recognition are modeled using Markov Random Fields (MRFs). For example, in information extraction, each sentence is treated as a MRF that captures the dependency in the labels assigned to adjacent words in the sentence.

An example of such a setup is given in Figure 1 for the task of named-entity extraction (NER). The base model in Figure 1(b) assigns a named-entity label such as Person, Location, or Other independently to each word in the input. The structured model goes one step ahead and imposes a dependency between labels of adjacent words, shown in Figure 1(c) via chain-shaped MRF models. The model, **however, ignores long range and intersentence dependencies. The collective model of Figure 1(d) encourages the labels of different occurrences of the**
same word to be the same. This is captured by connecting those occurrences with blue cliques that encode associative dependencies. Variants of these collective models have **been proposed in the past few years for a** variety of information extraction tasks [22, 6, 15, 9, 10]. We look at other applications of collective graphical models in Section 2.

1