We will use F(v1, . . . , vn) to denote the clique inference objective. As short-hand, we will denote F(v1**, . . . , v**n)
by F(v) = ψ(v)+ C(v) where ψ(v) is the vertex score of v **and the second term is the clique score. Wlog assume**
that the vertex potentials are positive. Otherwise a constant can **be added to all of them and that will not affect**
the maximization. The best value assignment will be denoted by v∗, and vˆ **will denote an approximate solution.**

## 6.1 Α**-Pass Algorithm**

We begin with max **potentials. These potentials are not used in practice, but clique inference for** max **potentials** gives rise to the α**-pass algorithm which has very interesting properties. Recall that** a max **potential is of the**
form C({v1, . . . , vn}) = maxv fv(nv). The α**-pass algorithm is described in Algorithm 1.**
Input: Vertex Potentials ψ, Clique Potential C, set R′p **of allowed values**
Output: Value assignment v1**, . . . , v**n Best = −∞;
vˆ **= nil;**
foreach *Value* α ∈ R′p do Sort the vertices by the metric ψjα − maxv∈R′p,v6=α ψjv; foreach k ∈ {1**, . . . , n**} do Assign the first k **sorted vertices the value** α; Assign the remaining vertices their individual best non-α **value;**
s ← **score of this assignment;**
if s > *Best* **then**
Best ← s; vˆ ← **current assignment;**
end end end return vˆ;
Algorithm 1: The α**-pass algorithm**
For each (α, k) combination, the α-pass algorithm computes the best k vertices to get the value α**. Let** vˆ
αk denote the complete assignment in the (**α, k**)
th step. Then it is easy to see that α-pass runs in O(|R′p|n log n)
time by incrementally computing F(vˆ
αk**) from** F(vˆ
α(k−1)). We now look at properties of α**-pass.**
Claim 6.1. *Assignment* vˆ
αk has the maximum vertex score over all v where k vertices are assigned α*, that is,*
ψ(vˆ
αk) = maxv:nα(v)=kψ(v).

Proof. **This is easily seen by contradiction. If some other assignment** v 6= vˆ
αk **has the best vertex score, then**
it differs from vˆ
αk in the assignment of at least two vertices, one of which is assigned α in v **and non-**α in vˆ
αk.

The converse holds for the other differing vertex. By swapping their assignments, it is possible to increase the vertex score of v**, a contradiction.**
Claim 6.2. For max *potentials, C*(vˆ
αk) ≥ fα(k).

Proof. This is because the value α has a count of k **and the** max **potential considers the maximum over all**
counts.

Theorem 6.1. The α*-pass algorithm finds the MAP for* max *clique potentials.*
Proof. Let v∗ be the optimal assignment and let β = argmaxvfv(nv(v∗)), ℓ = nβ(v∗). Let vˆ **be the assignment**