where ny(y w) is the number of times w is labeled y in all its occurrences. The clique potential Cw **only depends**
on the counts of how many nodes get assigned a particular label. A useful special case of the function is when fw(y, y′) is positive only for the case that y = y′**, and zero otherwise.**

## 2.2 Hypertext Classification

In hypertext classification, the goal is to classify a document based on features derived from its content and labels of documents it points to. A common technique in statistical relational learning to capture the dependency between a node and the variable number of neighbors it might be related to, is to define fixed length feature vectors out of the neighbor's labels. In text classification, most previous approaches [24, 16, 7] have created features based on the counts of labels in its neighborhood. Accordingly, we can define the following set of potentials: a node-level potential φi(y) that depends on the content of the document i**, and a neighborhood**
potential f(**y, n**1(y Oi )**, . . . , n**m(y Oi )) that captures the dependency of the label of i **on the counts in the label**
vector y Oi **of its out-links.**

$$\sum_{i}(\phi_{i y_{i}}+f(y_{i},n_{1}({\bf y}^{O_{i}}),\ldots,n_{m}({\bf y}^{O_{i}})))$$ $$=\sum_{i}(\phi_{i y_{i}}+\sum_{y}{\rm C}_{y}(n_{1}({\bf y}^{O_{i}}),\ldots,n_{m}({\bf y}^{O_{i}}))[y=y_{i}])$$

[16] include several examples of such clique potentials, viz. the Majority potential Cy(n1, . . . nm) = φ(y, ymax)
where ymax = argmaxyny, and the Count potential Cy(n1, . . . nm) = Py
′:ny′ >0 φ(y′, y)ny′ **. Some of these**
potentials, for example, the Majority potential are not decomposable as sum of potentials over the edges of the clique. This implies that methods such as TRW and graph-cuts are not **applicable. [16] rely on the Iterated**
Conditional Modes (ICM) method that greedily selects the best label of each document in turn based on the label counts of its neighbors.

## 3 Symmetric Clique Potentials

As seen in the example scenarios, our associative clique potentials depend only on the number of clique vertices taking a value v, denoted by nv, and not on the identity of those vertices. In other words, these **potentials are**
invariant under any permutation of their arguments and derive their value from the histogram of counts {nv|∀v}.

We denote this histogram by the vector n**. Since the potentials only depend on the value counts, we also refer**
to them as cardinality-based clique potentials in this paper. If a cardinality-based clique potential is associative, then it is maximized when nv = n for some v**, i.e. one value is given to all the clique vertices.**
We have deliberately left the notion of a 'value' vague at this point. For existing collective models, e.g. those mentioned in Section 2, a value corresponds to a label. As we shall see, in our more general framework, a value refers to a particular member in the range of a property function. **For now, we can assume wlog that a** *value* is a member of some discrete finite set V .

We consider specific families of clique potentials, many of which are currently used in real-life tasks. In Section 6 we will look at various potential-specific exact and approximate clique inference algorithms that exploit the specific structure of the potential.

In particular, we consider the three types of clique potentials listed **in Table 2.**

## 3.1 Max **Clique Potentials**

These clique potentials are of the form:

$\mathrm{C}(n_{1},\ldots,n_{|V|})=\max_{v}f_{v}(n_{v})$
When $f_{\sigma}(n_{\sigma})\triangleq n_{\sigma}$, we get the
for arbitrary non-decreasing functions fv. When fv(nv) , nv**, we get the** *makespan* **clique potential which has**
roots in the job-scheduling literature.

In Section 6.1, we present an algorithm, called α**-pass, that solves the clique inference problem for** max potentials exactly. The algorithm runs in time O(|V |n log n), where n **is the clique size, Although** max **potentials**