Software > ABSURDIST
Description | Pros
and Cons | Applications | Details
| Usage Hints | References
ABSURDIST (Aligning Between Systems Using Relations Derived
Inside Systems for Translation) is a computational algorithm that uses
within-system relations to find between-system translations (Feng,
Y, et. al, 2004, Goldstone, R., 2002). In
addition to performing simple string match of node labels, this algorithm
also uses network structure information to identify the overlap between
two given networks.
Within a network, a node is treated as a concept. ABSURDIST
derives semantic similarity information for different concepts embedded
within each network. The algorithm uses these internal semantic structure
by itself, or in combination with external information about similarities
between concepts to establish mapping of concepts that exists within two
given networks. It supports networks with multiple types of weighted or
unweighted, directed or unidrected relations between concepts. The algorithm
exploits graph sparsity to improve computational efficiency. Parameters
for running the algorithm are optimized to achieve better mapping results,
as well as improve noise tolerance, iteration speed, and scalability.
The algorithm consists of the following steps:
1. Represent both
source and target system as attributed graphs
2. Initialize the correspondence matrix C, compute the external
similarity matrix E
3. Iterate through the following steps until a convergence threshold
3.1 Compute excitation matrix R(C)
3.2 Compute inhibition matrix I(C)
3.3 Compute the net input N from E, R, and I
3.4 Apply the some damping function and learning rate on
N and Update C with N.
3.5 If the result converges, i.e., update to C is smaller
than a threshold, go to step 4, otherwise, go back to step 3
4. Generate final mapping from C according to user request (1-to-1
More details on the algorithm are available in the papers (Feng,
Y, et. al, 2004, Goldstone, R., 2002, 2005).
Pros & Cons
ABSURDIST is an inexact graph matching algorithm.
The advantages of the algorithm are:
- It considers the graph attributes (e.g., edge weight) as variables
to establish a concept based match between two network systems.
- The algorithms supports flexible matching by aligning two graphs based
on node labels alone, graph topology, or a combination of both.
The disadvantages of this algorithm are:
- The algorithm only scales to about 100 nodes.
- The quality of mapping greatly drops as the graph size increases (
size > 100 nodes)
- The algorithm does not always produce an optimum match for isomorphic
networks or sparse networks.
Though originally developed for conceptual system alignment, as a general
graph matching algorithm, ABSURDIST could be used in many other applications:
In general, it can be used to map any systems that can be represented as
graphs. As a sample application, we've developed an applet/application
that allows users to input their conceptual systems, or generate random
systems as they specify, and map the two systems, as well as visualize the
- Ontology mapping
- Database schema matching
- Analogical reasoning and similarity
ABSURDIST II is implemented purely in Java. The most up-to-date version
of ABSURDIST (version 2.2) is available for download.
The package includes both an applet version and an application version.
The applet version lets users generate random systems with randomly introduced
noise, specified by the user. The application version also lets users
input the source and target systems from files in a specially designed
Besides the major source code implementing the algorithm, the download
zip file also includes packages for various tests which were used to produce
the experimental results presented in our papers. Instructions for how
to use the code are provided in the readme
file included in the download package.
ABSURDIST (version 2.2) can be downloaded here
For more information, visit ABSURDIST
Please read the readme file before using the package.
After downloading abs2.zip and unziping it,
1) Put the unziped files into a base directory, say abs2
2) Create a directory classes/ under abs2/
3) Type either "ant" or "make" command
abs2% mkdir classes
- As application
abs2% make runapplic
Upon execution of the above command, the absurdist interface that is used
to upload the network files and find match between two networks opens.
In the above interface, the import button on the left and right hand side
can be used to load the network files. Each concept in the two network
is given a unique color. The 'Map Systems' button can be used to execute
the ABSURDIST algorithm to identify the overlap between the two networks.
'External Similarity' slider can be used to customize the algorithm to
perform match based on pure structure (slider pointer to left); based
purely on node labels (slider pointer to right) or an equal combination
of both (slider at 0.5). The results of the mapping can be exported using
the Export button or File > Export Results option.
The program exports two output files: .map (node mapping
information) and .cor (containing the correspondence matrix information).
ABSURDIST has its own input file format. The scripts below convert the
pajek file to ABSURDIST format and vice-versa.
For example, the two network files in pajek format: network1
and network2 are coverted
to a ABSURDIST input format by using p_pajekToABS.pl. Using the absurdist
format generated files in ABSURDIST, a map of overlapping networks is
identified. Using the export option, a .map
file is obtained from the interface. Further a combination of original
pajek files along with a .map file is used as input to p_ABSToPajek.pl
to generate a pajek file
containing information about the overlap between the two networks. A sample
pajek visualization showsnetwork1
in green and network2
in orange. Matching nodes as identified by ABSURDIST are connected by
- Ying Feng and Robert L. Goldstone and Vladimir Menkov, ABSURDIST
II: A Graph Matching Algorithm and its Application to Conceptual
System Translation, FLAIR 2004.
- Ying Feng and Robert L. Goldstone and Vladimir Menkov, 2004, The ABSURDIST
algorithm for matching concept systems as a converging optimization
method. Versions of algorithm are accessible at http://www.cs.indiana.edu/~yingfeng/ABSURDIST/.
- Robert L. Goldstone and Brian J. Rogosky, Using
relations within conceptual systems to Translate Across Conceptual Systems,
Cognition, 84, p. 295-320. 2002.
- Robert L. Goldstone, Ying Feng, and Brian J. Rogosky. Connecting
concepts to each other and the world. In Diane Pecher and Rolf Zwaan,
editors, Grounding cognition: The role of perception and action in memory,
language, and thinking . Cambridge University Press, 2005.
ABSURDIST II was implemented by Ying Feng, a PhD student at Computer
Science Department, with the help of Dr. Vladimir Menkov, a previous PhD
student at the CS deparment, under the supervision of Dr. Robert Goldstone
and Concepts Laboratory at IU.
This research was partially supported by a grant from the Lockheed Martin
Corporation. We would like to thank Todd Hughes, Brian Rogosky,
and Ben Ashpole for helpful comments.
The documentation was compiled by Ketan Mane, Ying Feng and Katy Börner.
Information Visualization Cyberinfrastructure
@ SLIS, Indiana University
Last Modified March 10, 2005