AURA Graphmatcher

Introduction

The AURA Graphmatcher is a technology that utilises the AURA library to implement neural relaxation by elimination to allow matching of one graph (connection of nodes and edges) against another.

Many forms of data can be represented as graphs although the main concentration of effort so far has been in representing three dimensional shapes as graphs. Here each node represents some feature of the three dimensional shape and the edges represent relationships between these features. An example might be the representation of a square in which the nodes might be used to represent the vertex features and the edges might be used to represent the distances between the vertices.

However the technqiues are not at all limited to matching shapes and apply to anything that can be represented as a graph.

Advantages

Fast speed of search
The ability to search in parallel over many targets of a large database.
The ability to allow approximate or fuzzy matches by eliminating the least plausible matches with a user-selectable tolerance/fuzziness.
The ability to encode the algorithm in dedicated hardware (see AURA and PRESENCE)

Implementation

Briefly, neural relaxation by elimination is a form of relaxation by elimination (RBE) in which an item may be only present or not present.

This has been implemented both in software as a C++ library, and also in dedicated neural-network acceleration hardware.

AURAMol

AURAMol is an implementation using the core library and hardware but with adapters designed to encode 3D representations of molecules as graphs.

A live implementation of is available at http://www.cs.york.ac.uk/auramol/

The live implementation runs on a Sun SPARC machine, utilisting two PRESENCE

cards for hardware acceleratio and allows the user to select a molecule from the trained database or load a user-defined molecule and then search against the stored database. The search is based on the 3D shape.