vertexedgekernel.java

a molecular graph kernel based on iterative graph similarity and optimal assignments

/**
 * ISOAK - Iterative similarity optimal assignment kernel.
 * 
 * Written by Matthias Rupp 2006-2007.
 * Copyright (c) 2006-2007, Matthias Rupp, Ewgenij Proschak, Gisbert Schneider.
 * 
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met:
 * 
 *  * The above copyright notice, this permission notice and the following disclaimers
 *    shall be included in all copies or substantial portions of this software.
 *  * The names of the authors may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 * 
 * Please cite
 * 
 * Matthias Rupp, Ewgenij Proschak, Gisbert Schneider:
 * A Kernel Approach to Molecular Similarity Based on Iterative Graph Similarity,
 * Journal of Chemical Information and Molecular Modeling, 47(6): 2280-2286, 2007, 
 * DOI http://dx.doi.org/10.1021/ci700274r.
 *
 * if you use this software.
 */

package info.mrupp.isoak1;

import info.mrupp.isoak1.MolecularGraph;

/**
 * No vertex/edge kernel.
 * 
 * Returns 1, effectively removing the subkernel from the equation.
 * 
 * No parameters.
 */

class VertexEdgeKernelNone implements IVertexEdgeKernel {
    public VertexEdgeKernelNone(float[] params) {
        assert params.length == 0: String.format("Invalid number of arguments for unity vertex/edge kernel (expected none but got %d)", params.length);
    }
    
	public float eval(MolecularGraph molA, int i, MolecularGraph molB, int j) {
        return 1.f; 
    }
    
    public String name() { return "none"; }
}

/**
 * Vertex degree kernel.
 * 
 * Returns 1 - abs(deg(v)-deg(v'))/tau, where deg(v) is the degree of vertex v
 * and tau is the maximum degree over all input graphs.
 * 
 * No parameters. 
 */

class VertexEdgeKernelTopologyV implements IVertexEdgeKernel {
	public VertexEdgeKernelTopologyV(float[] params) {
		assert params.length == 0: String.format("Invalid number of arguments for Topology vertex kernel (expected none but got %d)", params.length);
	}
	
	public float eval(MolecularGraph molA, int i, MolecularGraph molB, int j) {
		return ( 1.f - Math.abs( molA.numNeighbours(i) - molB.numNeighbours(j) ) / (float)MolecularGraph.MAX_DEGREE );
	}

    public String name() { return "topology"; }
}

/**
 * Dirac kernel on vertices.
 * 
 * Returns one if the atom descriptor matches, zero otherwise. 
 * First parameter is the index of the atom descriptor.
 * Second parameter is the tolerance for the absolute floating point comparison.
 */

class VertexEdgeKernelDiracV implements IVertexEdgeKernel {
	final int index;	// Index of atom descriptor.
	final float tol; 	// Tolerance for floating point comparison.
	
	public VertexEdgeKernelDiracV(float[] params) {
		assert params.length == 2 : String.format("Invalid number of arguments for Dirac vertex kernel (expected 2 but got %d)", params.length);
		index = (int) params[0]; assert (float)index == params[0] : String.format("First parameter to Dirac vertex kernel was not an integer (got %g)", params[0]); 
		tol = params[1]; assert tol > 0.0 : String.format("Second parameter to Dirac vertex kernel was not positive (got %g)", params[1]);
	}

	public float eval(MolecularGraph molA, int i, MolecularGraph molB, int j) {
        assert i < molA.numAtoms() : String.format("Invalid atom index %d, number of atoms %d", i, molA.numAtoms());
        assert j < molB.numAtoms() : String.format("Invalid atom index %d, number of atoms %d", j, molB.numAtoms());
		if (Math.abs( molA.atomDescriptor(i, index) - molB.atomDescriptor(j, index) ) > tol) return 0.f; else return 1.f;
	}
    
    public String name() { return String.format("dirac [%d, %f]", index, tol); }
}

/**
 * Dirac kernel on edges.
 * 
 * Returns one if the bond descriptor matches, zero otherwise. 
 * First parameter is the index of the bond descriptor.
 * Second parameter is the tolerance for the floating point comparison.
 */
class VertexEdgeKernelDiracE implements IVertexEdgeKernel {
	final int index;	// Index of atom descriptor.
	final float tol; 	// Tolerance for floating point comparison.
	
	public VertexEdgeKernelDiracE(float[] params) { 
		assert params.length == 2 : String.format("Invalid number of arguments for Dirac edge kernel (expected 2 but got %g)", params.length);
		index = (int) params[0]; assert (float)index == params[0] : String.format("First parameter to Dirac edge kernel was not an integer (got %g)", params[0]); 
		tol = params[1]; assert tol > 0.0 : String.format("Second parameter to Dirac edge kernel was not positive (got %g)", params[1]);
	} 

	public float eval(MolecularGraph molA, int i, MolecularGraph molB, int j) {
        assert i < molA.numBonds() : String.format("Invalid bond index %d, number of bonds is %d", i, molA.numBonds());
        assert j < molB.numBonds() : String.format("Invalid bond index %d, number of bonds is %d", j, molB.numBonds());
		if (Math.abs( molA.bondDescriptor(i, index) - molB.bondDescriptor(j, index)) > tol) return 0.f; else return 1.f;
	}
    
    public String name() { return String.format("dirac [%d, %f]", index, tol); }
}

/**
 * Sigmoid kernel on vertices.
 * 
 * Returns exp(-abs(x-y)^2 / 2*sigma^2) for two values x, y of an atom descriptor.
 * Equal descriptor values return 1, with exponential decay.
 * First parameter is the index of the atom descriptor.
 * Second parameter is the standard deviation sigma.
 */

class VertexEdgeKernelExpV implements IVertexEdgeKernel {
	final int index;        // Index of atom descriptor.
	final double variance;  // Variance of exponential distribution. Determines rate of decay.
	
	public VertexEdgeKernelExpV(float[] params) {
		assert params.length == 2 : String.format("Invalid number of arguments for exponential vertex kernel (expected 2 but got %d)", params.length);
		index = (int) params[0]; assert (float)index == params[0] : String.format("First parameter to exponential vertex kernel was not an integer (got %g)", params[0]);
		variance = params[1]*params[1]; assert variance > 0.f : String.format("Second parameter to exponential vertex kernel must be positive (got %g)", params[1]);
	}
	
	public float eval(MolecularGraph molA, int i, MolecularGraph molB, int j) {
		return (float) Math.exp( -Math.pow( molA.atomDescriptor(i, index) - molB.atomDescriptor(j, index), 2.) / (2.*variance) );
	}

    public String name() { return String.format("gaussian [%d, %f]", index, variance); }
}

/**
 * Sigmoid kernel on edges.
 * 
 * Returns exp(-abs(x-y)^2 / 2*sigma^2) for two values x, y of a bond descriptor.
 * Equal descriptor values return 1, with exponential decay.
 * First parameter is the index of the bond descriptor.
 * Second parameter is the standard deviation sigma.
 */

class VertexEdgeKernelExpE implements IVertexEdgeKernel {
    final int index;        // Index of bond descriptor.
    final double variance;  // Variance of exponential distribution. Determines rate of decay.
    
    public VertexEdgeKernelExpE(float[] params) {
        assert params.length == 2 : String.format("Invalid number of arguments for exponential edge kernel (expected 2 but got %d)", params.length);
        index = (int) params[0]; assert (float)index == params[0] : String.format("First parameter to exponential edge kernel was not an integer (got %g)", params[0]);
        variance = params[1]*params[1]; assert variance > 0.f : String.format("Second parameter to exponential edge kernel must be positive (got %g)", params[1]);
    }
    
    public float eval(MolecularGraph molA, int i, MolecularGraph molB, int j) {
        return (float) Math.exp( -Math.pow( molA.bondDescriptor(i, index) - molB.bondDescriptor(j, index), 2.) / (2.*variance) );
    }

    public String name() { return String.format("gaussian [%d, %f]", index, variance); }
}

/**
 * Available vertex and edge subkernels.
 * 
 * Vertex and edge kernels implement the same interface {@link info.mrupp.isoak1.IVertexEdgeKernel}.
 * This class provides information about all available vertex and edge kernels and acts
 * as a factory for them.
 */

public enum VertexEdgeKernel {
	/** No vertex/edge kernel. Returns 1, effectively removing the subkernel from the equation. No parameters. */
	NONE		(0, "none", "Always returns 1.")
	{ public IVertexEdgeKernel create(float[] params) { return new VertexEdgeKernelNone(params); } },
	
	/** 
     * Topological vertex subkernel.
     * 
     * Returns 1 - |deg(v)-deg(v')|/tau, where deg(v) is the degree of vertex v
     * and tau is the maximum degree over all input graphs. 
     * No parameters.
	 */
	TOPOLOGY	(0, "topol", "Returns a value in [0,1] scaling linearly with the difference in the vertex degrees.")
	{ public IVertexEdgeKernel create(float[] params) { return new VertexEdgeKernelTopologyV(params); } },

    /**
     * Dirac kernel on vertices.
     * 
     * Returns one if the atom descriptor matches, zero otherwise. 
     * First parameter is the index of the atom descriptor.
     * Second parameter is the tolerance for the absolute floating point comparison.
     */
	DIRACV      (2, "diracv", "Returns 1 if the atom descriptor (first parameter) matches with a given tolerance (second parameter), 0 otherwise.")
	{ public IVertexEdgeKernel create(float[] params) { return new VertexEdgeKernelDiracV(params); } },
	
    /**
     * Dirac kernel on edges.
     * 
     * Returns one if the edge descriptor matches, zero otherwise. 
     * First parameter is the index of the edge descriptor.
     * Second parameter is the tolerance for the absolute floating point comparison.
     */
	DIRACE      (2, "dirace", "Returns 1 if the bond descriptor (first parameter) matches with a given tolerance (second parameter), 0 otherwise.")
	{ public IVertexEdgeKernel create(float[] params) { return new VertexEdgeKernelDiracE(params); } },
	
    /**
     * Gaussian (sigmoid) kernel on vertices.
     * 
     * Returns exp(-|x-y|^2/2*sigma^2) for two values x and y of a vertex descriptor.
     * The Gaussian kernel as described by Cristianini & Shawe-Taylor, 2004, pp. 296.
     * Equal descriptor values return 1, with exponential decay.
     * First parameter is the index of the vertex descriptor.
     * Second parameter is the standard deviation sigma.
     */
    EXPV        (2, "expv", "Returns exponential kernel on an atom descriptor (first parameter) with given standard deviation (second parameter).")
    { public IVertexEdgeKernel create(float[] params) { return new VertexEdgeKernelExpV(params); } },
        
    /**
     * Gaussian (sigmoid) kernel on edges.
     * 
     * Returns exp(-|x-y|^2/2*sigma^2) for two values x and y of a bond descriptor.
     * The Gaussian kernel as described by Cristianini & Shawe-Taylor, 2004, pp. 296.
     * Equal descriptor values return 1, with exponential decay.
     * First parameter is the index of the bond descriptor.
     * Second parameter is the standard deviation sigma.
     */
    EXPE        (2, "expe", "Returns exponential kernel on a bond descriptor (first parameter) with given standard deviation (second parameter).")
    { public IVertexEdgeKernel create(float[] params) { return new VertexEdgeKernelExpE(params); } };
        
	private final int numArgs;
	private final String argName; 
	private final String description;
		
	VertexEdgeKernel(int numArgs, String argName, String description) { this.numArgs = numArgs; this.argName = argName; this.description = description; }
		
    /** Number of arguments needed for construction of vertex/edge kernel. */
	public int numArgs() { return numArgs; }
    
    /** Short name of vertex/edge kernel. */
	public String argName() { return argName; }
    
    /** Human readable description of vertex/edge kernel. */
	public String description() { return description; }
	
	/** Retrieve vertex/edge kernel by short name. */
	public static VertexEdgeKernel fromString(String str) {  
		for (VertexEdgeKernel vek : VertexEdgeKernel.values()) {
			if (vek.argName().equals(str)) { return vek; }
		}
		throw new IllegalArgumentException("Unknown argument name for vertex or edge kernel.");
	}
	
    /** Creates a new vertex/edge kernel with given parameters. */
	abstract public IVertexEdgeKernel create(float[] params);
}