Abstract: NN Optimization on Compressible Graphs

[Jagota Arun Kumar]

Dear Connectionists:

I announce a cleaner version of a paper I announced back in 1992. It is 
essentially unchanged in other aspects.

------------------------------------------------------------------------
             Performance of Neural Network Algorithms for 
             Maximum Clique On Highly Compressible Graphs

                 Arun K. Jagota and Kenneth W. Regan 

The problem of finding the size of the largest clique in an undirected graph 
is NP-hard, even to approximate well. Simple algorithms work quite well 
however on random graphs. It is felt by many, however, that the uniform
distribution u(n) does not accurately reflect the nature of instances that 
come up in practice. It is argued that when the actual distribution is 
unknown, it is more appropriate to suppose that instances come from the 
Solomonof-Levin or universal distribution m(x) instead, which assigns higher 
weight to instances with shorter descriptions. Because m(x) is neither 
computable nor samplable, we employ a realistic analogue q(x) which lends 
itself to efficient empirical testing. We experimentally evaluate how well 
certain neural network algorithms for Maximum Clique perform on graphs drawn 
from q(x), as compared to those drawn from u(n). The experimental results are 
as follows. All nine algorithms we evaluated performed roughly equally-well on 
u(n), whereas three of them---the simplest ones---performed markedly poorer 
than the other six on q(x). Our results suggest that q(x), while postulated 
as a more realistic distribution to test the performance of algorithms than 
u(n), is also one that discriminates their performance better. Our q(x) 
sampler can be used to generate compressible instances of any discrete problem.
------------------------------------------------------------------------

Send requests by e-mail to          jagota at cs.unt.edu

I use this mechanism to get some indication of the amount of interest, if
any, there is in this type of work.

Arun Jagota