absurdist
Class Absurdist

java.lang.Object
  absurdist.Absurdist

public class Absurdist

extends java.lang.Object

Class Absurdist provides the ABSURDIST II graph matching algorithms to compute the correspondence between two concept systems, and finds the optimal mappings between them. The behavior of this class is affected by a number of parameters, which can be supplied as Java System Properties on the command line (java -Dname=value ...). For example, running java -DresetL=false -DL=0.01 -DmaxLoop=5000 driver.ApplicDriver will run the program with fixed L equal to 0.01, interrupting the loop at the 5000-th iteration, if the convergence has not been achieved. java -DresetL=true driver.ApplicDriver will adjust the learning rate at every step to 1/2 of the maximum safe rate. This is supposed to achieve fastest convergence. One can find all the parameters in the code by searching for 'prop.getOption'.

Nested Class Summary

(package private) static class	Absurdist.AllBest An auxiliary class used during the randm tie-breaking process in find2WayMap
(package private) static class	Absurdist.CoefMode Various ways of setting Beta and Chi.
static class	Absurdist.Results Used for reporting.

Field Summary

static boolean	adjBest If true, we'll find the optimal permutation (this may be very expensive!) and compare the quality of our permutation to it
double	alpha Coefficients for external similarity.
static double	alphaShare This flag determines the alpha/(alpha+beta) ratio to be used in adjustCoeff(); it only is used if useAlphaShare is true, and is ignored otherwise.
double	beta Coefficients for activation.
double	chi Coefficients for inhibition.
static double	cInit Intitial value for correspondence matrix.
static int	coefMode This parameter controls how chi and beta are initially set, and whether they are reset during the iterative process.
static int	CONVERGED Concept systems mapping iteration converged.
double[][][]	correspond Correspondence matrix C[step][row][col].
static int	CREATED Concept system created.
static double	cvgThresh Threshold for iteration convergence.
static int	dampingMode Damping mode.
static boolean	enforce1to1map If true, 1-1 mapping will be enforced.
double[][]	exSim External similarity E[row][col].
double[][][]	inhib Inhibitor I[step][row][col].
static int	INITIAL Initial status without concept system created.
double[][][]	inSim Internal similarity, also called activator, R[step][row][col].
static int	intLoop Sampling interval for plots.
static int	ITERATING Concept systems in mapping iteration.
static double	lRate Learning rate (this may be adjusted if resetL=true).
int[]	mapNO Mappings from systemN to systemO, recording indices of matched concepts.
int[]	mapON Mappings from systemO to systemN, recording indices of matched concepts.
static int	MAPPED Concept systems mapping completed.
static double	mapThresh Threshold for valid mapping.
static double	maxL The ceiling for adjustable learning rate.
static int	maxLoop Maximum number of iterations.
double[][][]	netIn Network input N[step][row][col].
int	nStep Actual number of steps being recorded during network iteration.
static ParseConfig	prop An empty property list -- just an interface to system properties
static boolean	resetL If true, we recompute the learning rate at each step, for fastest convergence.
Absurdist.Results	results
int	status Status of the system.
(package private) CSGI	sysN graph-style interface for systemN, if available.
(package private) CSGI	sysO graph-style interface for systemO if available.
ConceptSystem	systemN Target system for mapping.
ConceptSystem	systemO Source system for mapping.
boolean	systemsAreSimple This will be set to true in the constructor if both concept systems being matched are "binary", that is have no other relationship weights than 1 and 0.
boolean	useAlphaShare If true, the alphaShare parameter is used to set alpha via beta.
boolean	useAnchors If true, use anchors overlap for external similarity
static boolean	useExponential If true, use the exponential version of activator and inhibitor to compute netwoek input.
static boolean	useFastGeneral If true, use the "fast" (N^2 D^2) method for general (labeled, weighted) graphs.

Constructor Summary

Absurdist()
Creates an empty absurdist system.

Absurdist(ConceptSystem systemO, ConceptSystem systemN)
Creates an absurdist system containing the source and target concept systems and random external similarities.

Method Summary

protected void	adjustCoeff() Initial setting of the beta and chi coefficients according to the node number and edge fullness of the graph.
protected double	calcLinkSim(int io, int jo, int in, int jn) Computes the similarity between link (io, jo) in systemO and (in, jn) in systemN.
double	calcLinkSim(Link lo, Link ln) Computes the similarity between the two links.
(package private) void	describe() Prints out ABSURDIST parameters (if fixed), or rules for adjusting them (if adjustable)
void	evalMap() Evaluates the quality of the mapping in mapON[].
protected CorrespondenceVector	fastInhib(CorrespondenceVector c) inhib(q,x) = ( C(All-q,x) + C(q, All-x) ) /(n+m-2)
protected CorrespondenceVector	fastInSim(CorrespondenceVector c) Computes the internal similarity matrix fast (in O(N^2*D^2) time), for an unlabeled unweighted graph.
protected CorrespondenceVector	fastInSimGeneral(CorrespondenceVector c) Fast similarity calculation for a general graph.
protected void	find1WayMap() Find the one-way O-N and N-O mapping using the strongest correspondence in each row/column.
protected void	find2WayMap() Finds the symmetrical two-way mapping using the N global strongest valid correspondences.
void	initExSim() Initialize external similarity matrix to all 0's.
boolean	isConverged() Returns true if the network iteration is converged; otherwise false.
boolean	isCreated() Returns true if the two systems are already created; otherwise false.
boolean	isInitial() Returns true if the two systems have not yet been created; otherwise false.
boolean	isIterating() Returns true if the network iteration is going on; otherwise false.
boolean	isMapped() Returns true if the two systems are already mapped; otherwise false.
protected void	iterateNet() Iterate the network to comppute correspondence between unit pairs.
static Absurdist	loadSystems(java.lang.String fileName, int w, int h) Creates a new instance of Absurdist initialized with the 2 systems read from a file containing Java serialized objects.
(package private) double	lookupLinkSim(Link lo, Link ln) Access function for linkSimCache; retrieves the cached link similarity value.
void	mapSystem() Maps orginal concept system to the one with added noise, using exponenital/linear activator/inhibitor.
void	print() Prints the source and target concept systems, the correspondence matrix, and the final mappings.
void	printCorrespond() Prints the correspondence matrix to the standard output.
void	printExSim() Prints the external similarity matrix to the standard output.
void	printMap() Prints the mapping between systemO and systemN to the standard output.
void	printSystems() Prints the two systems to the standard output.
void	readjustChi(double[][] exSim, double[][] inSim, double[][] inhib) A normalization method that takes both exSim and inSim into account.
void	saveSystems(java.lang.String fileName) Writes out the concept systems as Java serialized objects intoa file.
(package private) void	setSafeL() Computes a safe learning rate for the current value of the chi and beta parameters.
void	setSystemN(ConceptSystem systemN) Sets the target concepts system to be mapped to.
void	setSystemO(ConceptSystem systemO) Sets the source concepts system to be mapped from.
void	setSystems(ConceptSystem systemO, ConceptSystem systemN) Sets the two concepts systems for mapping.
double	sumElem(double[][] a) Computes the sum of the elements in an array.
(package private) void	testNaN(double x, java.lang.String name) Checks if the value contains NaN, and aborts the program if so.
static void	turnOffHistory() Turn off the iteration history recording so that less memory will be used.
void	writeCorrespond(java.lang.String filename) Writes the correspondence matrix to a text file.
void	writeMap(java.lang.String filename) Writes the mapping between systemO and systemN to a text file.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

prop

public static ParseConfig prop

An empty property list -- just an interface to system properties

INITIAL

public static final int INITIAL

Initial status without concept system created.

See Also:

Constant Field Values

CREATED

public static final int CREATED

Concept system created.

See Also:

Constant Field Values

ITERATING

public static final int ITERATING

Concept systems in mapping iteration.

See Also:

Constant Field Values

CONVERGED

public static final int CONVERGED

Concept systems mapping iteration converged.

See Also:

Constant Field Values

MAPPED

public static final int MAPPED

Concept systems mapping completed.

See Also:

Constant Field Values

cInit

public static double cInit

Intitial value for correspondence matrix.

lRate

public static double lRate

Learning rate (this may be adjusted if resetL=true).

maxLoop

public static int maxLoop

Maximum number of iterations.

intLoop

public static int intLoop

Sampling interval for plots.

cvgThresh

public static double cvgThresh

Threshold for iteration convergence.

mapThresh

public static double mapThresh

Threshold for valid mapping.

coefMode

public static int coefMode

This parameter controls how chi and beta are initially set, and whether they are reset during the iterative process.

resetL

public static boolean resetL

If true, we recompute the learning rate at each step, for fastest convergence. (For compatibility with the 2003 code, set the default to false!)

maxL

public static double maxL

The ceiling for adjustable learning rate. If 0 or negative, it is ignored

dampingMode

public static int dampingMode

Damping mode. Should be 0 (= G & R 2002) or 1 (= Hard damping)

useFastGeneral

public static boolean useFastGeneral

If true, use the "fast" (N^2 D^2) method for general (labeled, weighted) graphs.

useExponential

public static boolean useExponential

If true, use the exponential version of activator and inhibitor to compute netwoek input.

enforce1to1map

public static boolean enforce1to1map

If true, 1-1 mapping will be enforced.

adjBest

public static boolean adjBest

If true, we'll find the optimal permutation (this may be very expensive!) and compare the quality of our permutation to it

systemsAreSimple

public boolean systemsAreSimple

This will be set to true in the constructor if both concept systems being matched are "binary", that is have no other relationship weights than 1 and 0. If this is the case, we can use faster algorithms for computing inhibition, excitation, etc.

useAnchors

public boolean useAnchors

If true, use anchors overlap for external similarity

useAlphaShare

public boolean useAlphaShare

If true, the alphaShare parameter is used to set alpha via beta. This is false by default.

alphaShare

public static double alphaShare

This flag determines the alpha/(alpha+beta) ratio to be used in adjustCoeff(); it only is used if useAlphaShare is true, and is ignored otherwise. If it is 1.0, then alpha will be set to 1.0 and beta to 0.

See Also:

adjustCoeff()

alpha

public double alpha

Coefficients for external similarity.

beta

public double beta

Coefficients for activation.

chi

public double chi

Coefficients for inhibition.

systemO

public ConceptSystem systemO

Source system for mapping.

systemN

public ConceptSystem systemN

Target system for mapping.

sysO

CSGI sysO

graph-style interface for systemO if available.

sysN

CSGI sysN

graph-style interface for systemN, if available.

nStep

public int nStep

Actual number of steps being recorded during network iteration.

status

public int status

Status of the system.

exSim

public double[][] exSim

External similarity E[row][col].

inSim

public double[][][] inSim

Internal similarity, also called activator, R[step][row][col].

inhib

public double[][][] inhib

Inhibitor I[step][row][col].

netIn

public double[][][] netIn

Network input N[step][row][col].

correspond

public double[][][] correspond

Correspondence matrix C[step][row][col].

mapON

public int[] mapON

Mappings from systemO to systemN, recording indices of matched concepts.

mapNO

public int[] mapNO

Mappings from systemN to systemO, recording indices of matched concepts.

results

public Absurdist.Results results

Constructor Detail

Absurdist

public Absurdist()

Creates an empty absurdist system.

Absurdist

public Absurdist(ConceptSystem systemO,
                 ConceptSystem systemN)

Creates an absurdist system containing the source and target concept systems and random external similarities.

Method Detail

setSystemO

public void setSystemO(ConceptSystem systemO)

Sets the source concepts system to be mapped from.

setSystemN

public void setSystemN(ConceptSystem systemN)

Sets the target concepts system to be mapped to.

setSystems

public void setSystems(ConceptSystem systemO,
                       ConceptSystem systemN)

Sets the two concepts systems for mapping.

initExSim

public void initExSim()

Initialize external similarity matrix to all 0's.

turnOffHistory

public static void turnOffHistory()

Turn off the iteration history recording so that less memory will be used. This is used if you don't need to keep the intermediate results during the iteration. This is important for saving memory, and should always be done when you don't use the GUI and don't need the "timeseries" graphs.

setSafeL

void setSafeL()

Computes a safe learning rate for the current value of the chi and beta parameters. This is supposed to be in the middle of the interval [0; maxL]. Here maxL = min(maxL1, maxL2); maxL1 is the maximum value of learning rate that ensures that the elements of the correspondence matrix stay in the [0;1] range; maxL2 is the maximum value of learning rate that guarantees convergence.

describe

void describe()

Prints out ABSURDIST parameters (if fixed), or rules for adjusting them (if adjustable)

adjustCoeff

protected void adjustCoeff()

Initial setting of the beta and chi coefficients according to the node number and edge fullness of the graph.

calcLinkSim

protected double calcLinkSim(int io,
                             int jo,
                             int in,
                             int jn)

Computes the similarity between link (io, jo) in systemO and (in, jn) in systemN.

calcLinkSim

public double calcLinkSim(Link lo,
                          Link ln)

Computes the similarity between the two links. Each link may be a "real" link (a pair of numbers), or the EMPTY link.

lookupLinkSim

double lookupLinkSim(Link lo,
                     Link ln)

Access function for linkSimCache; retrieves the cached link similarity value.

fastInSim

protected CorrespondenceVector fastInSim(CorrespondenceVector c)

Computes the internal similarity matrix fast (in O(N^2*D^2) time), for an unlabeled unweighted graph.

We use the following sparsity-exploiting transformation:

        R(q,x)*(n-1) = Sum_{r: r!=q} Sum_{y: y!=q} Sim(D(r,q), D(x,y)) =
        = C( Nei(q), Nei(x)) + C( All-q-Nei(q), All-x-Nei(x)) =
        = C(All,All) - C(All,x)  - C(q, All) + C(q,x) -
        - C(All,Nei(x)) - C(Nei(q),All) + C(q,Nei(x)) + C(Nei(q),x) +
        + 2*C(Nei(q), Nei(x)).

        Here, C(set1, set2) = sum_{r in set1, y in set 2} C(r,y);
        All = set of all nodes of the 1st or 2nd graph, as appropriate;
        Nei(q) = set of all nodes of the 1st graph connected to q;
        Far(q) = A - (Nei(q) + {q});
        set1 - set2 = difference of set1 and set2.
        

fastInSimGeneral

protected CorrespondenceVector fastInSimGeneral(CorrespondenceVector c)

Fast similarity calculation for a general graph.

        Here, C(set1, set2) = sum_{r in set1, y in set 2} C(r,y);
        All = set of all nodes of the 1st or 2nd graph, as appropriate;
        Nei(q) = set of all nodes of the 1st graph connected to q;
        Far(q) = A - (Nei(q) + {q});
        set1 - set2 = difference of set1 and set2.



        (n-1)*R(a,x)
        = sum_{b in A-{a}} sum_{y in B-{x}} ( Sim( a,b; x,y) C(b,y) ) 
        = S11(a,x) + S12(a,x) + S21(a,x) + S22(a,x),    with 

        S11(a,x)
        = sum_{b in Nei(a)} sum_{y in Nei(x)} ( Sim(a,b; x,y) C(b,y) )

        S12(a,x)
        = sum_{b in Nei(a)} sum_{y in B-Nei'(x)} (Sim(a,b; x,y) C(b,y))
        = sum_{b in Nei(a) } (Sim( a,b; nolink) C(b, ALL)) -
        sum_{b in Nei(a) } (Sim( a,b; nolink) C(b, Nei(x))) -
        sum_{b in Nei(a) } (Sim( a,b; nolink) C(b,x))  
        = sum_{b in Nei(a)} (Sim(a,b; nolink) C(b,Far(x))

        S21(a,x) 
        = sum_{b in A-Nei'(a) } sum_{y in B } (Sim( a,b; x,y) C(b,y))=
        = sum_{y in Nei(B) } (Sim(nolink; x,y) C(ALL,x)) -
        sum_{y in Nei(B) } (Sim(nolink; x,y) C(Nei(a),x)) -
        sum_{y in Nei(B) } (Sim(nolink; x,y) C(a,y)) 
        = sum_{y in B } (Sim(nolink; x,y) C(Far(a),y))=

        S22(a,x) 
        =  sum_{b in A-Nei'(a) } sum_{y in B-Nei'(x)} (Sim( a,b; x,y) C(b,y))
        = Sim(nolink, nolink) * [
        C(ALL,ALL)     - C(Nei(a), ALL)   - C(a,ALL) 
        - C(ALL, Nei(x)) + C(Nei(a),Nei(x)) + C(a,Nei(x)) 
        - C(ALL, x)      + C(Nei(a),x)      + C(a,x) ]
        = Sim(nolink, nolink) C(Far(a), Far(x))

        

readjustChi

public void readjustChi(double[][] exSim,
                        double[][] inSim,
                        double[][] inhib)

A normalization method that takes both exSim and inSim into account. The goal is to have sum_{a,b}( (alpha*exSim + beta*inSim - chi*inhib)[a][b]) = 0. Learning rate may be recomputed too.

sumElem

public double sumElem(double[][] a)

Computes the sum of the elements in an array.

fastInhib

protected CorrespondenceVector fastInhib(CorrespondenceVector c)

       inhib(q,x) = ( C(All-q,x) + C(q, All-x) ) /(n+m-2)
       

iterateNet

protected void iterateNet()

Iterate the network to comppute correspondence between unit pairs.

find2WayMap

protected void find2WayMap()

Finds the symmetrical two-way mapping using the N global strongest valid correspondences.

In this case 1-1 mapping is enforced, and if the two systems are of different size, there will be some concepts with no mappings.

find1WayMap

protected void find1WayMap()

Find the one-way O-N and N-O mapping using the strongest correspondence in each row/column.

In this case all concepts will be mapped even if the two systems are of different size, and it's possible to have 1-n or m-1 mapping.

evalMap

public void evalMap()

Evaluates the quality of the mapping in mapON[].

Note: mismapped concepts and relations only apply to mappings between a concept system and its noisy copy, assuming that the noise is small enough so that the mapping should be identity, i.e. Ci -> Ci'.

mapSystem

public void mapSystem()

Maps orginal concept system to the one with added noise, using exponenital/linear activator/inhibitor. systemO and systemN have to be set preceding to calling this method.

isInitial

public boolean isInitial()

Returns true if the two systems have not yet been created; otherwise false.

isCreated

public boolean isCreated()

Returns true if the two systems are already created; otherwise false.

isIterating

public boolean isIterating()

Returns true if the network iteration is going on; otherwise false.

isConverged

public boolean isConverged()

Returns true if the network iteration is converged; otherwise false.

isMapped

public boolean isMapped()

Returns true if the two systems are already mapped; otherwise false.

writeCorrespond

public void writeCorrespond(java.lang.String filename)
                     throws java.lang.Exception

Writes the correspondence matrix to a text file.

Throws:

java.lang.Exception

writeMap

public void writeMap(java.lang.String filename)
              throws java.lang.Exception

Writes the mapping between systemO and systemN to a text file.

Throws:

java.lang.Exception

printSystems

public void printSystems()

Prints the two systems to the standard output.

printExSim

public void printExSim()

Prints the external similarity matrix to the standard output.

printCorrespond

public void printCorrespond()

Prints the correspondence matrix to the standard output.

printMap

public void printMap()

Prints the mapping between systemO and systemN to the standard output.

print

public void print()
           throws java.lang.Exception

Prints the source and target concept systems, the correspondence matrix, and the final mappings.

Throws:

java.lang.Exception

loadSystems

public static Absurdist loadSystems(java.lang.String fileName,
                                    int w,
                                    int h)

Creates a new instance of Absurdist initialized with the 2 systems read from a file containing Java serialized objects. Such a file may have been produced with saveSystems(). For display purposes, both graph are to be fitted into a w-by-x panel, splitting it into 2 halves.

Parameters:

w - Width of the display area for the graphs.

h - Height of the display area for the graphs.

saveSystems

public void saveSystems(java.lang.String fileName)

Writes out the concept systems as Java serialized objects intoa file. This method can be used if you want to restore the data later from the file, using loadSystems().

testNaN

void testNaN(double x,
             java.lang.String name)

Checks if the value contains NaN, and aborts the program if so. You can use this method if you suspect that some values are corrputed. If the value is a NaN, an error message is printed and the program exits.

Parameters:

x - The value to check

name - The "name" of the variable we are checking, to print in an error message.