A Neural Computation paper on graph isomorphism

[Marcello Pelillo]

The following paper, accepted for publication in Neural Computation,
is accessible at the following www site:

      http://www.dsi.unive.it/~pelillo/papers/nc98.ps.gz

A shorter version of it has just been presented at NIPS*98, and can be
accesses at:

      http://www.dsi.unive.it/~pelillo/papers/nips.ps.gz

(files are gzipped postscripts)


Comments and suggestions are welcome!

Best regards,
Marcello Pelillo


========================
Replicator Equations, Maximal Cliques, and Graph Isomorphism

Marcello Pelillo
University of Venice, Italy

ABSTRACT

We present a new energy-minimization framework for the graph isomorphism
problem which is based on an equivalent maximum clique formulation.  The
approach is centered around a fundamental result proved by Motzkin and
Straus in the mid-1960s, and recently expanded in various ways, which
allows us to formulate the maximum clique problem in terms of a standard
quadratic program.  The attractive feature of this formulation is that a
clear one-to-one correspondence exists between the solutions of the
quadratic program and those in the original, combinatorial problem.  To
solve the program we use the so-called ``replicator'' equations, a class
of straightforward continuous- and discrete-time dynamical systems
developed in various branches of theoretical biology.  We show how,
despite their inherent inability to escape from local solutions, they
nevertheless provide experimental results which are competitive with those
obtained using more elaborate mean-field annealing heuristics.

====================


________________________________________________________________________
                                                        Marcello Pelillo
                                             Dipartimento di Informatica
                                      Universita' Ca' Foscari di Venezia
                             Via Torino 155, 30172 Venezia Mestre, Italy

                                                   Tel: (39) 41 2908.440
                                                   Fax: (39) 41 2908.419
                                            E-mail: pelillo at dsi.unive.it
                                   URL: http://www.dsi.unive.it/~pelillo