\documentstyle{article}
\topmargin -1.0in
\textheight 9.7in
\textwidth 7.0in
\hoffset -1.0in
\title{\bf Efficiently Approximating {\em Max-Clique} \\ 
in a Hopfield-style Network 
\footnote{To be Orally Presented at: {\em International Joint Conference on Neural Networks '92 Baltimore}. Will appear in Proceedings as is.}
}
\author{Arun Jagota (jagota@cs.buffalo.edu)\\ 
Department Of Computer Science,\\
State University Of New York At Buffalo 
}
\date{}
\begin{document}
\maketitle
\begin{abstract}
In a graph, a {\em clique} is a set of vertices such that every pair
is connected by an edge. MAX-CLIQUE is the optimization problem of 
finding the largest clique in a given graph, and is {\em NP}-complete.
Several real-world and theory problems can be modeled as MAX-CLIQUE.
In this paper, we efficiently approximate MAX-CLIQUE in a special case 
of the Hopfield Network whose stable states are maximal cliques. 
We present several energy-descent optimizing 
dynamics; both discrete and continuous. One of these
emulates, as special cases, two well known greedy algorithms for approximating 
MAX-CLIQUE. We report on detailed 
empirical comparisons on random graphs. Mean-Field Annealing---an efficient approximation
to Simulated Annealing---is the narrow but clear winner. 
All dynamics approximate much better than one which emulates
a ``naive'' greedy heuristic.
\end{abstract}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{defn}{Definition}
\newtheorem{corollary}{Corollary}
\newtheorem{remark}{Remark}
\newtheorem{conjecture}{Conjecture}
\newtheorem{fact}{Fact}
\newtheorem{NEG}{Negative Result}
%-\section{The MAX-CLIQUE Optimization Problem}
\subsection*{The MAX-CLIQUE Optimization Problem}
%%-DEFINE CLIQUE, MAXIMAL, MAXIMUM
In a graph with undirected edges, a {\em clique} is a set of vertices such that every pair
is connected by an edge. 
A clique is {\bf maximal} if no strict 
superset of it is also a clique. 
A clique is {\bf maximum} if it is the largest clique. In Figure 1,
the vertex sets: \{b,c,e\}, \{a,b,d\},\{c,d,e\}, and \{a,b,d,e\} are
not clique, non-maximal clique, maximal-but-not-maximum clique,
and maximum clique (size 4) respectively.
\begin{center}
\setlength{\unitlength}{0.0125in}
\begin{picture}(194,105)(45,705)
\thicklines
\put(229,769){\circle{20}}
\put( 55,795){\circle{20}}
\put(150,795){\circle{20}}
\put( 55,745){\circle{20}}
\put(150,745){\circle{20}}
\put( 65,750){\line( 2, 1){ 80}}
\put( 65,790){\line( 2,-1){ 80}}
\put(160,745){\line( 3, 1){ 60}}
\put(160,790){\line( 3,-1){ 60}}
\put(150,785){\line( 0,-1){ 30}}
\put( 55,785){\line( 0,-1){ 30}}
\put( 65,795){\line( 1, 0){ 75}}
\put( 65,745){\line( 1, 0){ 75}}
\put(120,715){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlsf Graph}}}
\put( 55,715){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twlbf Figure 1 - }}}
\put(150,790){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt e}}}
\put(225,765){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt c}}}
\put( 55,790){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt a}}}
\put( 55,740){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt b}}}
\put(150,740){\makebox(0,0)[lb]{\raisebox{0pt}[0pt][0pt]{\twltt d}}}
\end{picture}
\end{center}
%%-MAX-CLIQUE, ITS NP-COMPLETENESS, AND HARDNESS OF APPROXIMATION
MAX-CLIQUE is the optimization problem of 
finding a maximum clique in a given graph. This problem is 
{\em NP}-complete (see \cite{kn:GaJ79}). That is, with high
probability (i.e. unless {\em P=NP}) there is no algorithm that, for {\em every} given
graph, can find a maximum clique tractably (i.e. in time polynomial 
in the size of the graph). Recent theoretical results 
\cite{kn:FGLSS91,kn:CFS91} strongly suggest 
that the problem of approximating MAX-CLIQUE well may also be
intractable. That is, with high probability there is no algorithm that,
for {\em every} given graph, can find 
even a sufficiently close to maximum (e.g. within constant factor) 
clique in polynomial time.
\par
%%-APPLICATIONS OF MAX-CLIQUE AND ITS APPROXIMATION 
Several problems can be efficiently reduced to MAX-CLIQUE,
and thus solved by algorithms for MAX-CLIQUE.
For example, there are reductions of
satisfiability of Boolean Formulae to MAX-CLIQUE
(see \cite{kn:GaJ79,kn:CFS91}). 
Many other problems are in principle efficiently
reducible to MAX-CLIQUE because of its {\em NP}-completeness. 
Some---but not all---reductions also preserve approximability.
In such cases, reduced problems can also be approximated,
by approximating MAX-CLIQUE; this being easier. 
MAX-SAT, the optimization problem of finding the largest number of 
simultaneously satisfiable clauses, is one such problem
\cite{kn:CFS91}. \par
Several real-world problems can also be modeled as exactly-solving or 
approximating MAX-CLIQUE. These include Constraint 
Satisfactions Problems \cite{kn:Jag91} 
(used 
in AI, see \cite{kn:Mac87}) (e.g. $N$-queens, graph coloring), object 
recognition modeled as subgraph isomorphism \cite{kn:BaY86}, and 
information retrieval \cite{kn:AuM70}. Our own
work on associative memories with cliques \cite{kn:tr9002,kn:wordrec}
leads to applications of MAX-CLIQUE: find the largest stored memory. 
These also include problems 
modeled as Maximum Independent Set (Maximum Clique in complement graph)
(e.g. RNA secondary structure prediction \cite{kn:TCLH90}).
%-\section{Hopfield-clique Network}
\subsection*{Hopfield-clique Network}
%%-HN
The Hopfield Network \cite{kn:Hop82,kn:Hop84} is a recurrent $N$-unit network closely
related to Ising Spin Models. Units are connected with symmetric 
real-valued weights ($w_{ij}$). 
%%-DHN
In the discrete Hopfield Network \cite{kn:Hop82}, unit states are:
$S_i \in \{0,1\}$ (a different formulation has $\{-1,1\}$). $S_i$ are 
updated via thresholds on weighted sums of states of other units. 
State updates minimize
the following energy function \cite{kn:Hop82}: 
\begin{equation}
E = -\frac{1}{2} \sum_{i j} w_{ij} S_i S_j \label{eq:HcN1}
\end{equation}
thereby guaranteeing convergence to a discrete local minimum of 
Equation~\ref{eq:HcN1}. 
%%-CHN
\newcommand{\Sigmoid}[2]{\mbox{$\frac{1}{1~+~e^{-#2 #1}}$}}
In the continuous Hopfield Network \cite{kn:Hop84}, units are
continuous:
$S_i \in [0,1]$ (a different formulation has $[-1,1]$). $S_i$ are 
updated via a continuous nonlinear dynamics, described later, 
which minimizes the following energy function \cite{kn:Hop84}: 
\begin{equation}
E = -\frac{1}{2} \sum_{i j} w_{ij} S_i S_j 
+ \sum_{i} \int_{0}^{S_i} g_{\lambda}^{-1}(S) d S \label{eq:HcN2}
\end{equation}
where $g_{\lambda}(x) \equiv \Sigmoid{x}{\lambda}$ is a sigmoid
and $\lambda$ its gain. Convergence to a continuous local
minimum of Equation~\ref{eq:HcN2} is thus guaranteed.
%%-RELATING DISCRETE AND CONTINOUS LOCAL MINIMA
Hopfield \cite{kn:Hop84} also related the continuous local minima
of Equation~\ref{eq:HcN2} to the discrete local minima of
Equation~\ref{eq:HcN1}.
He observed that the continuous and discrete local minima
of the first term of Equation~\ref{eq:HcN2} are the same
and showed that the contribution of the second term fades as $\lambda$ is
increased. Thus, as $\lambda$ is increased, the continuous local minima of 
Equation~\ref{eq:HcN2} monotonically approach the discrete local 
minima of Equation~\ref{eq:HcN1}.
This result will be significant in this paper. \par
%%-HcN and G_N
The Binary-weights Hopfield-clique Network (HcN) \cite{kn:tr9002,kn:tr9025} is a {\em
fully-connected} special case
of the Hopfield Network with the following restriction on weights:
$w_{ij} \in \{ \rho,1\},~i \neq j$ and $\rho < 0$. There are no
self-weights ($w_{ii} = 0$). 
We characterize
the weight matrix of 
HcN as a graph $G_N=(V,E)$ whose vertices are the units and (undirected) edges
are the positive weights ($w_{ij} = w_{ji} = 1$). That is, $\{v_i,v_j\} \in E(G_N)$ if and 
only if $w_{ij} = 1$. We say that $G_N$ is the graph {\em underlying} HcN. \par
\par
%%-DISCRETE HcN 
The discrete HcN has $S_i \in \{0,1\}$.
The network state vector $\bar{S} = (S_i) \in \{0,1\}^N$
is the characteristic membership vector of some $V' \subseteq V$. 
We will use the latter set notation to denote a discrete state vector.
$S$ is a locally
minimum (stable) state of the energy function of Equation~\ref{eq:HcN1} 
if the energy of every state neighboring 
$S$ (Hamming distance of $1$ from $s$) is greater than or equal to that of $S$. 
The empty set (characteristic vector $\bar{0}$) is a stable state of DHcN. 
\begin{lemma}
\label{lemHcN1}
{\em (\cite{kn:tr9002,kn:Jag91})}
For $\rho < -N$, the stable states of DHcN---other than
$\bar{0}$---are
exactly the maximal cliques of the $G_N$ underlying it.
\end{lemma}
By Lemma~\ref{lemHcN1}, the stable states of the DHcN whose underlying
graph is the one in Figure 1 are: \{\}, \{a,b,d,e\}, \{c,d,e\}.
The third stable state is: units c,d,e are ON; the rest OFF.
Lemma~\ref{lemHcN1} is the basis for applying the discrete HcN to 
MAX-CLIQUE.
\par
%%-CONTINUOUS HcN 
The continuous HcN has $S_i \in [0,1]$. Combining the Hopfield 
result relating continuous and discrete minima with 
Lemma~\ref{lemHcN1} gives:
``As $\lambda$ is increased, the stable states of a CHcN
monotonically approach (characteristic vectors of) maximal cliques
of its underlying $G_N$''.
This is the basis for applying CHcN to MAX-CLIQUE.
\par
%%-ASSOCIATIVE MEMORY STORAGE RULE
The following storage rule, developed earlier and used 
for associative memories (see \cite{kn:tr9002,kn:Jag91}),
can be used to make any given graph $G$ the graph underlying HcN.
We present 
this rule because it is on-line, may have efficient implementations, 
and is a single mechanism for storing associative memories and graphs.
The initial weight state is: For all $i \neq j$,
$w_{ij}(0)  =  \rho$.
Any set of vertices $V' \subseteq V$ is stored in HcN at time $t$ as follows. For all $i \neq j$,
\begin{equation}
w_{ij}(t+1)~:=~
\left\{
\begin{array}{rl}
1 & \mbox{if $S_i,~S_j~\in V'$} \\
w_{ij}(t) & \mbox{otherwise}
\end{array}
\right.
\end{equation}
%-\subsection{Discrete Descent Dynamics}
\subsection*{Discrete Descent Dynamics}
\label{DDD}
%%-SD IDEA
{\underline{\bf Steepest Descent:}}
One discrete dynamics that we will use to approximate MAX-CLIQUE is
serial-update steepest energy-descent (SD).
In every cycle,
exactly one unit $i$---the one whose switch would maximally decrease 
the energy---is first picked and then switched. We describe SD in 
a form convenient---though not its most efficient
one (see \cite{kn:tr9002})---for computer implementation. \par
%%-SD Details
Given the network state $\bar{S}(t)$, first, for each
unit $S_i$, the 
quantities $n_i, V_i$ and $\Delta E_i$ are computed simultaneously
(in parallel) as follows. 
\begin{eqnarray}
n_i(t+1) & := & \sum_{j \neq i} w_{ij}  S_j(t) \\ \label{eq:HcN3}
V_i(t+1) & := &
\left\{ 
\begin{array}{rl}
1 & \mbox{if $n_i(t+1) > 0$ and $S_i(t) = 0$} \nonumber \\
-1 & \mbox{if $n_i(t+1) < 0$ and $S_i(t) = 1$} \nonumber \\
0 & \mbox{otherwise}
\end{array} 
\right. \nonumber \\
\Delta E_i(t+1)  &  =  &- V_i(t+1) n_i(t+1) \label{eq:HcN4} 
\end{eqnarray}
where $n_i(t+1)$ is the net input into $S_i$, $V_i$
is the direction $S_i$ is allowed to switch in, and $\Delta E_i$
is the change in energy a switch would cause. 
Next, 
a unit $S_s$ that maximally decreases the energy is picked 
and if $\Delta E_s < 0$ then switched as below.
If $\Delta E_s \geq 0$ then no unit is switched.
\begin{eqnarray}
s & = & \mbox{postion\_of\_min}(\bar{\Delta E}) \label{eq:HcN5} \\
S_s(t+1)  & = &
\left\{ 
\begin{array}{rl}
1 & \mbox{if $V_s(t+1) = ~~1$} \\
0 & \mbox{if $V_s(t+1) = -1$} \\
\end{array} 
\right. 
\end{eqnarray}
%\subsubsection*{Greedy Algorithm}
With $\rho < -2 N$, SD 
emulates the following 
greedy clique-finding algorithm on $G_N$ \cite{kn:tr9025}. \newline
\rule{6.8in}{0.01in}
\begin{center}
\begin{enumerate}
\item $G_i \leftarrow G_N[S_a(0)]$;
\item \underline{while} $V(G_i)$ is not a clique \underline{do}
\begin{enumerate}
\item Pick {\bf a} $v \in V(G_i)$ with minimum degree, that is: $d_{G_{i}}(v) = \delta(G_i)$;
~~~~(b) $G_i \leftarrow G_i~-~\{v\}$;
\end{enumerate}
\item \underline{end};
\item \underline{while} $\exists x \in V(G_N)~-~V(G_i)$ such that $V(G_i) \cup \{x\}$ is a clique \underline{do}
\begin{enumerate}
\item Pick {\bf a} $y \in V(G_N)~-~V(G_i)$ such that $V(G_i) \cup \{y\}$ is a clique;
~~~~(b) $G_i \leftarrow G_i \cup \{y\}$;
\end{enumerate}
\item \underline{end};
\end{enumerate}
\end{center}
\rule{3.2in}{0.01in}
~~SD~~
\rule{3.2in}{0.01in}
%\rule{6.8in}{0.01in}
%\centerline{\bf SD}
From $S_a(0)$, the initial state, this algorithm does all the switch 
OFF's before any switch ON's.
Step 2a switches a unit OFF that is inhibited by the 
{\em largest} number of ON units. 
Step 4a switches a unit ON if it is currently OFF and receives 
excitation from {\em all} the ON units. 
With $S_a(0) \leftarrow V(G_N)$ (initial state: all units ON),
this algorithm becomes a well known 
greedy one to find a large clique. This special case, and SD in
general, converge
in $\Theta(N)$ cycles. \newline
\vspace*{0.05in}
\newline
%-\subsubsection{{\bf $\rho$}-annealing}
{\underline{\bf $\rho$-annealing:}}
The second discrete dynamics that we will use on MAX-CLIQUE is applicable only 
to HcN and is based on annealing (varying) $\rho$ while performing
SD.
We term it $\rho$-annealing. 
In $\rho$-annealing we (1) start from the 
initial state: all vertices ON, with a small setting of $|\rho|$, 
(2) reach a stable state by SD,
and (3) increase $|\rho|$. We repeat Steps 2,3---using the stable state
of the previous Step 2 as the initial state of the next Step 2---until 
$\rho$ is sufficiently negative. 
%The algorithm is described below. 
\newline
%-RHO-ANNEALING ALGORITHM
\rule{6.8in}{0.01in}
\newline
$Sa(0) \leftarrow V(G_N)$; $\rho \leftarrow -\epsilon$     (small $|\rho|$);\newline
\begin{verbatim}
REPEAT
\end{verbatim}
\begin{enumerate}
\item $S_f \leftarrow $ SD; 2. Decrease $\rho$; 3. $S_a(0) \leftarrow S_f$;
\end{enumerate}
\begin{verbatim}
UNTIL Sf is a maximal clique of Gn
\end{verbatim}
\rule{3.0in}{0.01in}
~~$\rho$-annealing~~
\rule{3.0in}{0.01in}
At every $\rho$, convergence is guaranteed by the Hopfield convergence 
theorem \cite{kn:Hop82}.
At small $|\rho|$, the stable states are expected to
satisfy the constraints only weakly and therefore not be cliques.
As $|\rho|$ is increased, constraints will become tighter until
the stable states eventually become cliques (Lemma~\ref{lemHcN1}).
Annealing on $\rho$ is motivated by the hope that---in analogy with 
Simulated Annealing---a progression of stable states with 
monotonically tightening constraints will eventually lead to a large clique. \par
%-RELATION TO SD
Our empirical comparisons of $\rho$-annealing and SD led to
the surprising observation that on many occasions, on the same
graph, both dynamics 
exhibited identical behavior (switch decisions) upto certain points. 
This 
led to the following result, stated here without proof. 
Ties are broken lexicographically
in $\rho$-annealing and SD. 
\begin{lemma}
Let $S_a(0) \leftarrow V(G_N)$. From this initial state, {\bf if}
$\rho$-annealing and SD, both, switch units OFF in the first $k$ cycles,
{\bf then}
they both switch the same units OFF in these cycles.
\end{lemma}
%-RUNNING TIME
The analytical running time of 
$\rho$-annealing has not yet been derived. Our empirical observations 
are that almost all $\rho$-annealing cycles
involve switch OFFs; thus convergence is in $O(N)$ cycles. These empirical observations
suggest that $\rho$-annealing is quite efficient.
%-\subsection{Continuous Descent Dynamics}
\subsection*{Continuous Descent Dynamics}
\label{CDD}
%-\subsubsection{Continuous Hopfield Network}
{\underline{\bf Continuous Hopfield Dynamics: }}
The third HcN dynamics that we will use to approximate MAX-CLIQUE
is the continuous energy-descent dynamics (CHD) of Hopfield \cite{kn:Hop84} (see also
\cite{kn:HKP91}). 
It is
described, in one form, by the system of $N$ coupled nonlinear 
differential equations:
\begin{equation}
\frac{d S_i}{d t} = -S_i + g_{\lambda}(\Sigma_{j} w_{ij} S_j) \label{eq:CDD1}
\end{equation}
The fixed points satisfy $S_i = g_{\lambda}(\Sigma_{j} w_{ij} S_j)$.
CHD minimizes the energy function of Equation~\ref{eq:HcN2}
and so
on HcN---for sufficiently large $\lambda$---the fixed points approximate
characteristic vectors of maximal cliques of the underlying $G_N$.
The choice of $g$ as a sigmoid is also convenient for analog circuit 
implementations.
The sigmoid is also related to the Boltzmann distribution; the 
significance of which is discussed in the next paragraph. 
CHD is a special case of Mean Field Annealing (see below). CHD 
is realizable in
simple analog circuit implementations \cite{kn:Hop84} (also see \cite{kn:HKP91}).
It can also be solved (integrated) numerically in fully parallel 
form, as illustrated below.
\begin{equation}
\bar{S}_{n+1} := \bar{S}_{n} + \gamma (- \bar{S}_{n} + \bar{g}_{\lambda}(W \bar{S}_{n})) \label{eq:CDD2}
\end{equation}
where $\bar{g}(\bar{x})$ is notational shorthand for $(g(x_i))$.
$\gamma$ is the step size.
One iteration of Equation~\ref{eq:CDD2} can be done in 
$N$ $g$-evaluation, $\Theta(N^2)$ multiplication, and $\Theta(N)$ 
addition steps with $1$ processor;
$1$ $g$-evaluation, $\Theta(N)$ multiplication, and $\Theta(N Log N)$ 
addition steps with $N$ processors; and
$1$ $g$-evaluation, $\Theta(1)$ multiplication, and $\Theta(Log N)$ 
addition steps with $N^2$ processors. \newline
\vspace*{0.05in}
\newline
%-\subsubsection{Mean Field Annealing}
{\underline{\bf Mean Field Annealing: }}
\label{MFA}
The fourth dynamics that we will use to approximate MAX-CLIQUE is
Mean Field Annealing (MFA) \cite{kn:BMM89,kn:PeS89}, an efficient approximation to 
Simulated Annealing (SA) \cite{kn:KGV83}. When applied to a Hopfield Network,
MFA can be viewed as a generalization of CHD in which
the parameter $T = \frac{1}{\lambda}$ is annealed (varied). \par
%-STOCHASTIC HOPFIELD NETWORK
We review a Stochastic Hopfield Network (SHN); then its Mean
Field approximation; then MFA.
SHN (see \cite{kn:HKP91}) is a stochastic
version of DHN in which the units are discrete,
but the update rule is stochastic:
\begin{equation}
Prob[S_i = 1] = 
g_{\frac{1}{T}}(\Sigma_{j} w_{ij} S_j) 
\label{eq:MFA1}
\end{equation}
where the choice of update function as $g_{\frac{1}{T}}$ makes the energy Boltzmann-distributed.
Units are updated until thermal equilibrium is reached. That is,
the averages $<S_i>$ stop changing. 
SA is a generalization
of SHN in which $T$ is annealed. \par
%-MEAN FIELD APPROXIMATION
The Mean Field approximation to Equation~\ref{eq:MFA1}
equates the average $<S_i>$ in terms of the averages 
$<S_j>$:
\begin{equation}
<S_i> = g_{\frac{1}{T}}(\Sigma_{j} w_{ij} <S_j>) 
\label{eq:MFA2}
\end{equation}
Equation~\ref{eq:MFA2} simplifies analysis of 
SHN and SA. 
As important, with continuous units representing $<S_i>$,
CHD (Equation~\ref{eq:CDD1})
evolves to a fixed point satisfying
Equation~\ref{eq:MFA2}). 
Thus CHD, an efficient energy-descent-only dynamics, is a Mean Field 
approximation to the relatively inefficient SHN dynamics. 
MFA is a generalization of CHD in which
$T = \frac{1}{\lambda}$ is annealed. Thus, MFA is an
efficient Mean Field approximation to 
SA. 
\par
%-THE MFA ALGORITHM
In MFA we (1) start
at a high temperature $T$ (small $\lambda$), (2) reach a fixed
point by CHD, and (3) decrease $T$. We repeat Steps 2,3---using
the fixed point of the previous Step 2 as the initial state of
the next Step 2---until $T$ is sufficiently small.
The prescription for decreasing $T$ is called the
annealing schedule. A parallel numerical implementation of MFA 
is: \newline
\rule{6.8in}{0.01in}
\newline
$T \leftarrow  T_0 $;  Initialize $\bar{S}_0$ \newline
\underline{repeat} \underline{repeat} 
$\bar{S}_{n+1} := \bar{S}_n + \gamma (-\bar{S}_n + \bar{g}_{\lambda}(W \bar{S}_n))$  
\underline{until} fixed point is reached; 
\hspace*{0.3in} Decrease $T$; 
$\bar{S}_0 \leftarrow \bar{S}_{n+1}$ \newline
\underline{until} $T$ is sufficiently small \newline
\rule{3.1in}{0.01in}
~~MFA~~
\rule{3.1in}{0.01in}
\subsection*{Approximating MAX-CLIQUE in HcN: Results}
%%-BRIEF OVERVIEW OF SECTION
The various HcN dynamics are applied to MAX-CLIQUE and 
their empirical approximation performance is compared.
%%-TEST SETS AS RANDOM GRAPHS
Our primary test sets are random graphs; they represent a large
uniform class of replicable (in average sense) graphs. 
They also allow 
our results to be interpreted as empirical estimates of average-case 
performance of our algorithms, making average-case comparisons with other
algorithms (e.g. \cite{kn:BaY86}) possible.
%-MATULA'S THEOREM
Random graphs are also useful because 
a surprising result, discovered
and proved by Matula (see \cite{kn:Pal85}, pg 76), holds for them.
A $p$-random graph is one in which a
pair of vertices is connected by an edge with probability $p$.
Let 
$d(N) \equiv 2 \log_{\frac{1}{p}} N~-~2 \log_{\frac{1}{p}} \log_{\frac{1}{p}} N + 1 + 2 \log_{\frac{1}{p}} \frac{e}{2}$.
Matula's
theorem says that the maximum clique size in (almost all) $p$-random $N$-vertex
graphs is either $\lfloor d(N) \rfloor$ or $\lceil d(N) \rceil$.
We shall use Matula's theorem to estimate the maximum clique size in
our test graphs.
\par
%%-LARGE-CLIQUE GRAPHS
Our secondary test sets are $k$-random-cliques graphs.
They are generated as follows. $k$ random
subsets of $V(G_N)$ of size $1$ through $\frac{N}{2}$ are selected, interpreted as complete
graphs, and their labeled union is taken, that is, 
the HcN storage rule is applied to these sets.
The resulting graph ($G_N$ if storage rule is applied)
is a $k$-random-cliques graph. 
$k$-random-cliques graphs have cliques of many more different sizes 
than $p$-random graphs do.
\par
%%-PRELIMINARY ANALYSIS OF ALGORITHMS ON RANDOM GRAPHS
We shall make SD emulate another well known large-clique-finding algorithm
with a ``naive'' greedy heuristic. 
This requires adding the
term $- \Sigma_i w_0 S_i$ in Equation~\ref{eq:HcN1} and adding $w_0$
to the computation of $n_i$ in Equation~\ref{eq:HcN3}, where $w_0$
is a sufficiently small ($w_0 \leq 1$ will suffice) positive value that does not interfere with
the normal operation of HcN but does force it to move away from
the initial state $\Phi$ ($\bar{0}$). With these additions,
from the initial state:$S_a(0) \leftarrow \Phi$, SD emulates this ``naive''
greedy heuristic (second loop of SD algorithm, pg 3; skip first loop). 
Karp \cite{kn:Kar76} combined a result of \cite{kn:GrM75} and, once again,
Matula's theorem to note 
that on random graphs, this algorithm almost always finds a clique
that is (nearly) half the size of the maximum clique; thus showing
that MAX-CLIQUE is well-approximable (constant factor $\frac{1}{2}$)
on random graphs. 
\par
%%-PARAMETER SETTINGS FOR rho-annealing, CHD, MFA
Table I summarizes the experimental approximation
performance of the different HcN dynamics on MAX-CLIQUE. 
The last column is the size of the 
MAX-CLIQUE estimated by Matula's theorem; this is meaningful only for 
random graphs 
\footnote{There is a discrepancy between
$<$MC$>$ and our empirical results (see $p=0.909$ rows; also 
compare SD($\Phi$), the ``naive'' heuristic with $<$MC$>$).
We have no explanation as yet. Primitive tests for randomness of
our graphs were successfully done}.
%-\input table.tex
{\small
\begin{center}
Table I -
Performance (Average size of retrieved clique) of various algorithms, \\
on $p$-random graphs and $k$-random-cliques graphs
\end{center}
\begin{center}
\begin{tabular}{ccc|ccccc|c}
\multicolumn{3}{c|}{Test Set Parameters} &
\multicolumn{5}{c|}{Performance of Algorithms} & $<$M-C$>$ \\ \hline
Dist Par & $|V|$& \# G & SD($V(G_N)$) & SD($\Phi$) & $\rho$-A & CHD & MFA 
\\ \hline
\multicolumn{9}{c}{$p$-random graphs} \\ \hline 
$p=0.5$    & 100 & 15   & 8      &   6.53   &  8.3     & 8.20& 8.53& 9.7 \\ 
           & 400 & 15   & 9.73   &   8.46   &  10.2    & 9.93& --- & 12.94 \\ 
           & 800 & 15   & 10.34  &   9.53   &  11      &10.87& --- & 14.63 \\ \hline 
$p=0.909$  & 100 & 15   & 29.8   &  24.93   &  29.8    & --- &31.4 & 22.70* \\ 
           & 400 & 15   & 47.13  &  39.2    &  47.4    & 45.2&53.2 & 46.24* \\ 
           & 800 & 15   & 55.47  &  46.2    &  57      &53.7 &59.13& 58.48* \\ \hline 
\multicolumn{9}{c}{$k$-random-cliques graphs} \\ \hline 
$k=20$        &100  & 19   & 49.2   &  33.47   &   49.58  &47.0 &50.3 & \\ 
$k=80$        &400  & 11   & 276.1  &  137.27  &  276.1   &272.2&278.2& \\ 
$k=100$       &800  & 5    & 547    &  244.2   &   547.4  &541.6&---\\ \hline 
\end{tabular}
\end{center}
}
SD is insensitive to the exact value of $\rho$ as long as it is 
$< -N$.
The algorithms $\rho$-annealing, CHD, and MFA, represented by columns
6-8 respectively, have sensitive parameters whose experimental settings were
as follows.
The $\rho$-annealing schedule was geometric:
\fbox{$ \rho_{n} = 2 \rho_{n-1};~~\rho_{0} = -\frac{1}{8} $}
and operated until $\rho_{n} < -N$ inclusive.
CHD was operated at $\rho = -10 N,~T = \frac{1}{\lambda} = 1, \gamma = 0.1$, and
\# iterations = $N$. The initial state was $S_a(0) = (0.5 + \delta)^N$
where $\delta$ is random noise in $[-0.05,0.05]$.
The initial state to MFA was the same as to CHD. $\rho$ was also the
same.
For every fixed $T$, MFA
was operated with $\gamma=0.1$ and \# iterations-per-$T~=~N$.
The MFA annealing schedule was geometric:
\fbox{$ T_{n} = a_{n-1} T_{n-1};~~T_{0} = \frac{2}{3} (1-p) N |\rho| $}
where  $a_n = 0.9; n \leq 3$, $a_n = 0.5; n > 3$. The
schedule was operated until $T_n=1$ inclusive. Owing to space limitations,
we will not justify these settings here. The MFA settings are robust
to graph size scaling (see Table I); MFA also appears robust at
least to
small variations (e.g. to annealing schedule) to these settings. \par
All dynamics exhibit trade-offs between implementation (analog or digital)
feasibility and cost, running time, and approximation
performance. On approximation performance,
Table I shows that MFA 
\footnote{On some $k$-random-cliques graphs, CHD and MFA fail to 
converge to a clique. No satisfactory analysis yet.}
is the narrow but clear winner in every applicable
test (Table I rows). Further improvements to MFA performance 
may be possible by adopting a slower annealing schedule.
The improvement attributable to annealing is clearly apparent by row-wise
comparisons of CHD and MFA columns. Contrary to what might be
expected, SD($V(G_N)$)---a discrete dynamics---performs slightly better than CHD.
In fact $\rho$-annealing---another discrete dynamics---is the runner-up
to MFA and significantly more efficient. SD($\Phi$) performs the worst,
especially on $k$-random-cliques graphs.
\par
On a SUN Sparc-station, the time to find a clique is roughly,
depending on $N$ ($100$ to $800$),
seconds to a few minutes 
for SD and $\rho$-annealing,
minutes to less than an hour for CHD, and
less than an hour to a few hours for MFA.
Though all dynamics are inherently parallel, parallel implementation
of MFA should provide the greatest speed-up. \par
The author expresses sincere thanks to Dr. Kenneth Regan, his advisor, for several
discussions and the specific suggestion to test on graphs 
containing large cliques (which led to $k$-random-cliques graphs). 
\begin{thebibliography}{160}
{\small
\bibitem [AuM70] {kn:AuM70} Gary Augustson and Jack Minker, 
An Analysis of Some Graph Theoretical Cluster Techniques,
{\em Journal of the Association for Computing Machinery, Vol. 17, No. 4,
October 1970, pp. 571-588}
\bibitem [BMM89] {kn:BMM89} G. Bilbro, R. Mann, T.K. Miller, W. E. Snyder,
D. E. Van den Bout, \& M. White.
Optimization by Mean Field Annealing, 
{\em Advances in Neural Information Processing Systems I - D. Touretzky (Ed), 1989}.
\bibitem [CFS91] {kn:CFS91} 
Crescenzi P., Fiorini C., and Silvestri R.,
A Note on the Approximation of the MAXCLIQUE Problem,
To appear in {\em Information Processing Letters}.
\bibitem [BaY86] {kn:BaY86} 
Egon Balas and Chang Sung Yu,
Finding a Maximum Clique in an Arbitrary Graph,
{\em Siam J. Comput. 15-4, November 1986}.
\bibitem [FGLSS91] {kn:FGLSS91} 
U. Freige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy 
Approximating clique is almost NP-Complete,
To appear in {\em Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS), Puerto Rico, 1991}.
\bibitem [GaJ79] {kn:GaJ79} M. R. Garey, \& D.S. Johnson, 
Computers and Intractability---A Guide to the Theory of NP-Completeness,
W.H. Freeman and Company, 1979.
\bibitem [GrM75] {kn:GrM75} 
Grimmett G.R. and McDiarmid C.J.H,
On Colouring Random Graphs,
{\em Math. Proc. Camb. Phil. Soc. 77, 313-324, 1975}.
\bibitem [HKP91] {kn:HKP91} J. Hertz, A. Krogh, and R. Palmer, 
Introduction to the theory of Neural Computation, Lecture Notes Vol-I,
Santa Fe Institute, Addison-Wesley, 1991.
\bibitem [Hop82] {kn:Hop82} Hopfield J.J., 
Neural networks and physical systems with emergent computational
properties,
{\em Proceedings of the National Academy of Sciences, USA, 79, 2554-2558}.
\bibitem [Hop84] {kn:Hop84} Hopfield J.J., 
Neurons with graded response have collective computational properties like
those of two-state neurons,
{\em Proceedings of the National Academy of Sciences, USA, 81, 3088-3092}.
\bibitem [HT85] {kn:HT85} Hopfield J.J. \& Tank D.W., 
Neural computations of decisions in optimization problems,
{\em Biological Cybernetics, 52:141-152}.
\bibitem [Jag90a] {kn:tr9002} Arun Jagota, 
A new Hopfield-style network for content-addressable memories, 
{\em TR 90-02, Dept Of Computer Science,
State University Of New York At Buffalo, NY 14260 }
\bibitem[Jag90b] {kn:wordrec} Arun Jagota, 
Applying a Hopfield-style network to Degraded Text Recognition,
{\em Proceedings of the International Joint Conference on Neural
Networks, San Diego, 1990}.
\bibitem [Jag90c] {kn:tr9025} Arun Jagota, 
The Hopfield-style Network as a Maximal Clique Graph Machine,
{\em TR 90-25, Dept Of Computer Science,
State University Of New York At Buffalo, NY 14260 }
\bibitem [Jag91] {kn:Jag91} Arun Jagota, 
Combinatorial Problem Solving in a Hopfield-style Network,
Submitted to {\em IEEE Transactions on Neural Networks}.
\bibitem [Kar76] {kn:Kar76} 
R.M. Karp,
The Probabilistic Analysis of some Combinatorial Search Algorithms,
{\em Algorithms and Complexity: New Directions and Recent Results, 
Academic Press (1976), Ed-J.F. Traub}.
\bibitem [KGV83] {kn:KGV83} S. Kirkpatrick, C.D. Gelatt Jr., \& M.P. Vecchi,
Optimization by Simulated Annealing,
{\em Science 220:671-680}.
\bibitem[Mac87] {kn:Mac87}
A. K. Mackworth, In
{\em Encyclopedia of Artificial Intelligence Vol-I, Ed- S.C. Shapiro, p.205-211, 1987}.
\bibitem[Pal85] {kn:Pal85}
Palmer E.M.,
Graphical Evolution, 
{\em Wiley, 1985}.
\bibitem[PeS89] {kn:PeS89}
Carsten Peterson, Bo Soderberg, 
A new method for mapping Optimization Problems onto Neural Networks,
{\em International Journal of Neural Systems, Vol. 1, No. 1 (1989) 3-22}.
\bibitem[TCLH90] {kn:TCLH90}
Y. Takefuji, L. Chen, K. Lee, and J. Huffman,
Parallel Algorithms for Finding a Near-Maximum Independent Set of
a Circle Graph,
{\em IEEE Transactions on Neural Networks, 1-3, 263-67, Sept. 1990}
}
\end{thebibliography}
\end{document}