Abstract class for methods that transform GED to LSAPE by using a SVM or a DNN to predict the cost of node edit operations. More...

#include <ml_based_method.hpp>

Inheritance diagram for ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >:

[legend]

Public Member Functions
double	predict (const GEDGraph &g, const GEDGraph &h, const NodeMap::Assignment &assignment)
	Predicts the type of a node assignment. More...

Public Member Functions inherited from ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >
virtual	~LSAPEBasedMethod ()=0
	Pure virtual destructor. More...

	LSAPEBasedMethod (const GEDData< UserNodeLabel, UserEdgeLabel > &ged_data)
	Constructor. More...

void	populate_instance_and_run_as_util (const GEDGraph &g, const GEDGraph &h, Result &result, DMatrix &lsape_instance)
	Runs the method with options specified by set_options() and provides access to constructed LSAPE instance. More...

void	populate_instance (const GEDGraph &g, const GEDGraph &h, DMatrix &lsape_instance)
	Populates the LSAPE instance. More...

Public Member Functions inherited from ged::GEDMethod< UserNodeLabel, UserEdgeLabel >
virtual	~GEDMethod ()=0
	Pure virtual destructor. More...

	GEDMethod (const GEDData< UserNodeLabel, UserEdgeLabel > &ged_data)
	Constructor. More...

void	set_options (const std::string &options)
	Sets the options of the method. More...

void	run (GEDGraph::GraphID g_id, GEDGraph::GraphID h_id)
	Runs the method with options specified by set_options(). More...

void	run_as_util (const GEDGraph &g, const GEDGraph &h, Result &result)
	Runs the method with options specified by set_options(). More...

void	init ()
	Initializes the method with options specified by set_options().

double	get_upper_bound () const
	Returns an upper bound. More...

double	get_lower_bound () const
	Returns a lower bound. More...

Seconds	get_runtime () const
	Returns the runtime. More...

Seconds	get_init_time () const
	Returns the initialization time. More...

const NodeMap &	get_node_map () const
	Returns a graph matching. More...

Protected Attributes
std::size_t	num_features_
	The size of the feature vectors.

Protected Attributes inherited from ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >
LSAPESolver::Model	lsape_model_
	Specifies model for optimal LSAPE solver.

LSAPESolver::GreedyMethod	greedy_method_
	Specifies method for greedy LSAPE solver.

bool	compute_lower_bound_
	Flag that should be set to `true` if and only if the method computes a lower bound.

bool	solve_optimally_
	Flag that equals `true` if an optimal LSAPE solver is used and `false` if a greedy method is employed.

std::size_t	num_threads_
	The number of threads to be used.

Protected Attributes inherited from ged::GEDMethod< UserNodeLabel, UserEdgeLabel >
bool	initialized_
	A flag that equals true if init() has been called and false otherwise.

const GEDData< UserNodeLabel, UserEdgeLabel > &	ged_data_
	The data on which the method is run.

Private Member Functions
virtual void	lsape_init_ () final
	Initializes the method after initializing the global variables for the graphs. More...

virtual void	lsape_pre_graph_init_ (bool called_at_runtime) final
	Initializes the method at runtime or during initialization before initializing the global variables for the graphs. More...

virtual void	lsape_populate_instance_ (const GEDGraph &g, const GEDGraph &h, DMatrix &master_problem) final
	Populates the LSAPE instance. More...

virtual std::string	lsape_valid_options_string_ () const final
	Returns string of all valid options that are not among the ones shared by all derived classes of ged::LSAPEBasedMethod. More...

virtual void	lsape_set_default_options_ () final
	Sets all options that are not among the ones shared by all derived classes of ged::LSAPEBasedMethod to default values. More...

virtual bool	lsape_parse_option_ (const std::string &option, const std::string &value) final
	Parses one option that is not among the ones shared by all derived classes of ged::LSAPEBasedMethod. More...

virtual void	lsape_init_graph_ (const GEDGraph &graph) final
	Initializes global variables for one graph. More...

virtual void	lsape_default_post_graph_init_ () final
	Default initializes the method at runtime after initializing the global variables for the graphs. More...

virtual void	ml_init_feature_variables_ (const GEDGraph &g, const GEDGraph &h, std::size_t num_threads)
	Initializes variables that are used for populating the feature vectors of assignments between two input graphs. More...

virtual std::string	ml_valid_options_string_ () const
	Returns string of all valid options that are not among the ones shared by all derived classes of ged::MLBasedMethod. More...

virtual bool	ml_parse_option_ (const std::string &option, const std::string &arg)
	Parses one option that is not among the ones shared by all derived classes of ged::MLBasedMethod. More...

virtual void	ml_set_default_options_ ()
	Sets all options that are not among the ones shared by all derived classes of ged::MLBasedMethod to default values. More...

virtual void	ml_init_ ()
	Initializes the method after initializing the global variables for the graphs. More...

virtual void	ml_init_graph_ (const GEDGraph &graph)
	Initializes global variables for one graph. More...

virtual std::size_t	ml_get_num_features_ ()
	Returns the number of features. More...

virtual void	ml_init_for_num_features_ ()
	Initializes the derived class for running with feature vectors of size ged::MLBasedMethod::num_features_. More...

virtual void	ml_populate_substitution_feature_vector_ (const GEDGraph &g, const GEDGraph &h, GEDGraph::NodeID i, GEDGraph::NodeID k, std::vector< double > &feature_vector)
	Computes substitution feature vector. More...

virtual void	ml_populate_deletion_feature_vector_ (const GEDGraph &g, GEDGraph::NodeID i, std::vector< double > &feature_vector)
	Computes deletion feature vector. More...

virtual void	ml_populate_insertion_feature_vector_ (const GEDGraph &h, GEDGraph::NodeID k, std::vector< double > &feature_vector)
	Computes insertion feature vector. More...

Detailed Description

template<class UserNodeLabel, class UserEdgeLabel>
class ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >

Abstract class for methods that transform GED to LSAPE by using a SVM or a DNN to predict the cost of node edit operations.

All derived classes support the following options in addition to the ones supported by ged::LSAPEBasedMethod:

`--<option> <arg>`	modified parameter	default	more information
`--load <filename>`	path to existing configuration file	not specified	must be specified, if the method is run without prior initialization
`--save <filename>`	path where to save configuration file	not specified	n.a.
`--load-train <filename>`	path to existing training data file	not specified	n.a.
`--save-train <filename>`	path where to save training data	not specified	n.a.
`--load-ground-truth <filename>`	path to existing ground truth data file	not specified	n.a.
`--save-ground-truth <filename>`	path where to save ground truth	not specified	n.a.
`--log <filename>`	path where to save log data	not specified	specify this option for output of accuracy, precision, and recall
`--ml-method DNN\|SVM\|ONE_CLASS_SVM`	employed machine learning method	`DNN`	if `DNN`, a fully connected neural network with one output neuron is used and the options `--svm-<suffix>` and `--one-class-svm-likelihood` have no effect if `SVM`, a two-class support vector machine with RBF kernel is used and the options `--dnn-<suffix>` and `--one-class-svm-likelihood` have no effect if `ONE_CLASS_SVM`, a one class support vector machine with RBF kernel is used and the options `--dnn-<suffix>` and `--svm-<suffix>` have no effect
`--ground-truth-method ANCHOR_AWARE_GED\|F1\|F2\|COMPACT_MIP\|IPFP`	method for computing the ground truth	`IPFP`	the methods F1, F2, and COMPACT_MIP are available only if GEDLIB is installed with Gurobi
`--ground-truth-options '[–<option> <arg>] [...]'`	options string passed to the ground truth method	`''`	ged::AnchorAwareGED, ged::F1, ged::F2, ged::CompactMIP, ged::IPFP
`--dnn-activation SIGMOID\|RELU[,SIGMOID\|RELU]`	activation functions for hidden layers	`SIGMOID,RELU`	if more than one function is specified, the best choice is determined via cross-validation during training
`--dnn-hidden-layers-range <smaller convertible to int greater 0>,<larger convertible to int greater 0>`	range that specifies possible number of hidden layers	`1,10`	if the range is larger than one, the best choice is determined via cross-validation during training
`--dnn-neurons-per-layer-range <smaller convertible to int greater 0>,<larger convertible to int greater 0>`	range that specifies possible number of neurons per hidden layer	`1,20`	if the range is larger than one, the best choice is determined via cross-validation during training
`--svm-gamma-exp-range <smaller convertible to int>,<larger convertible to int>`	range that specifies possible exponents to the basis 10 of the parameter $\gamma$ used by SVM	`-3,4`	if the range is larger than one, the best choice is determined via cross-validation during training
`--svm-c-exp-range <smaller convertible to int>,<larger convertible to int>`	range that specifies possible exponents to the basis 10 of the parameter used by SVM	`-3,4`	if the range is larger than one, the best choice is determined via cross-validation during training
`--one-class-svm-likelihood TRUE\|FALSE`	use likelihood to define probability estimates based on one class SVM output	`TRUE`	n.a.

Definition at line 55 of file ml_based_method.hpp.

Member Function Documentation

◆ lsape_default_post_graph_init_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >::lsape_default_post_graph_init_ ( )

finalprivatevirtual

Default initializes the method at runtime after initializing the global variables for the graphs.

Note: Must be overridden by derived classes of ged::LSAPEBasedMethod that require default initialization at runtime after initializing the global variables for the graphs.

Reimplemented from ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >.

Definition at line 527 of file ml_based_method.ipp.

◆ lsape_init_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >::lsape_init_ ( )

finalprivatevirtual

Initializes the method after initializing the global variables for the graphs.

Note: Must be overridden by derived classes of ged::LSAPEBasedMethod that require custom initialization.

Reimplemented from ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >.

Definition at line 111 of file ml_based_method.ipp.

◆ lsape_init_graph_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >::lsape_init_graph_ ( const GEDGraph & graph )

finalprivatevirtual

Initializes global variables for one graph.

Parameters

[in] graph Graph for which the global variables have to be initialized.

Note: Must be overridden by derived classes of ged::LSAPEBasedMethod that require to initialize custom global variables.

Reimplemented from ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >.

Definition at line 520 of file ml_based_method.ipp.

◆ lsape_parse_option_()

template<class UserNodeLabel , class UserEdgeLabel >

bool ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >::lsape_parse_option_	(	const std::string &	option,
		const std::string &	arg
	)

finalprivatevirtual

Parses one option that is not among the ones shared by all derived classes of ged::LSAPEBasedMethod.

Parameters

[in]	option	The name of the option.
[in]	arg	The argument of the option.

Returns: Returns true if option is a valid option name for the method and false otherwise.

Note: Must be overridden by derived classes of ged::LSAPEBasedMethod that have options that are not among the ones shared by all derived classes of ged::LSAPEBasedMethod.

Reimplemented from ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >.

Definition at line 277 of file ml_based_method.ipp.

◆ lsape_populate_instance_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >::lsape_populate_instance_	(	const GEDGraph &	g,
		const GEDGraph &	h,
		DMatrix &	lsape_instance
	)

finalprivatevirtual

Populates the LSAPE instance.

Parameters

[in]	g	Input graph.
[in]	h	Input graph.
[out]	lsape_instance	LSAPE instance of size (n + 1) x (m + 1), where n and m are the number of nodes in `g` and `h`. The last row and the last column represent insertion and deletion.

Note: Must be overridden by derived classes of ged::LSAPEBasedMethod.

Reimplemented from ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >.

Definition at line 168 of file ml_based_method.ipp.

◆ lsape_pre_graph_init_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >::lsape_pre_graph_init_ ( bool called_at_runtime )

finalprivatevirtual

Initializes the method at runtime or during initialization before initializing the global variables for the graphs.

Parameters

[in] called_at_runtime Equals true if called at runtime and false if called during initialization. Must be overridden by derived classes of ged::LSAPEBasedMethod that require default initialization at runtime before initializing the global variables for the graphs.

Reimplemented from ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >.

Definition at line 147 of file ml_based_method.ipp.

◆ lsape_set_default_options_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >::lsape_set_default_options_ ( )

finalprivatevirtual

Sets all options that are not among the ones shared by all derived classes of ged::LSAPEBasedMethod to default values.

Note: Must be overridden by derived classes of ged::LSAPEBasedMethod that have options that are not among the ones shared by all derived classes of ged::LSAPEBasedMethod.

Reimplemented from ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >.

Definition at line 245 of file ml_based_method.ipp.

◆ lsape_valid_options_string_()

template<class UserNodeLabel , class UserEdgeLabel >

std::string ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >::lsape_valid_options_string_ ( ) const

finalprivatevirtual

Returns string of all valid options that are not among the ones shared by all derived classes of ged::LSAPEBasedMethod.

Returns: String of the form "[--<option> <arg>] [...]".

Note: Must be overridden by derived classes of ged::LSAPEBasedMethod that have options that are not among the ones shared by all derived classes of ged::LSAPEBasedMethod.

Reimplemented from ged::LSAPEBasedMethod< UserNodeLabel, UserEdgeLabel >.

Definition at line 232 of file ml_based_method.ipp.

◆ ml_get_num_features_()

template<class UserNodeLabel , class UserEdgeLabel >

std::size_t ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >::ml_get_num_features_ ( )

privatevirtual

Returns the number of features.

Returns: Size of the feature vectors employed by the derived class.

Note: Must be overridden by derived classes.

Reimplemented in ged::BipartiteML< UserNodeLabel, UserEdgeLabel >, and ged::RingML< UserNodeLabel, UserEdgeLabel >.

Definition at line 1507 of file ml_based_method.ipp.

◆ ml_init_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >::ml_init_ ( )

privatevirtual

Initializes the method after initializing the global variables for the graphs.

Note: Must be overridden by derived classes of ged::MLBasedMethod that require custom initialization.

Reimplemented in ged::BipartiteML< UserNodeLabel, UserEdgeLabel >.

Definition at line 1497 of file ml_based_method.ipp.

◆ ml_init_feature_variables_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >::ml_init_feature_variables_	(	const GEDGraph &	g,
		const GEDGraph &	h,
		std::size_t	num_threads
	)

privatevirtual

Initializes variables that are used for populating the feature vectors of assignments between two input graphs.

Parameters

[in]	g	Input graph.
[in]	h	Input graph.
[in]	num_threads	The number of available threads.

Note: Must be overridden by derived classes that require initialization of variables used for populating the feature vectors of assignments between two input graphs.

Reimplemented in ged::BipartiteML< UserNodeLabel, UserEdgeLabel >, and ged::RingML< UserNodeLabel, UserEdgeLabel >.

Definition at line 1473 of file ml_based_method.ipp.

◆ ml_init_for_num_features_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >::ml_init_for_num_features_ ( )

privatevirtual

Initializes the derived class for running with feature vectors of size ged::MLBasedMethod::num_features_.

Note: Must be overridden by derived classes that can be set up with features vectors of various sizes.

Reimplemented in ged::RingML< UserNodeLabel, UserEdgeLabel >.

Definition at line 1514 of file ml_based_method.ipp.

◆ ml_init_graph_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >::ml_init_graph_ ( const GEDGraph & graph )

privatevirtual

Initializes global variables for one graph.

Parameters

[in] graph Graph for which the global variables have to be initialized.

Note: Must be overridden by derived classes that require to initialize custom global variables.

Reimplemented in ged::RingML< UserNodeLabel, UserEdgeLabel >.

Definition at line 1502 of file ml_based_method.ipp.

◆ ml_parse_option_()

template<class UserNodeLabel , class UserEdgeLabel >

bool ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >::ml_parse_option_	(	const std::string &	option,
		const std::string &	arg
	)

privatevirtual

Parses one option that is not among the ones shared by all derived classes of ged::MLBasedMethod.

Parameters

[in]	option	The name of the option.
[in]	arg	The argument of the option.

Returns: Returns true if option is a valid option name for the method and false otherwise.

Note: Must be overridden by derived classes that have options that are not among the ones shared by all derived classes of ged::MLBasedMethod.

Reimplemented in ged::BipartiteML< UserNodeLabel, UserEdgeLabel >, and ged::RingML< UserNodeLabel, UserEdgeLabel >.

Definition at line 1485 of file ml_based_method.ipp.

◆ ml_populate_deletion_feature_vector_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >::ml_populate_deletion_feature_vector_	(	const GEDGraph &	g,
		GEDGraph::NodeID	i,
		std::vector< double > &	feature_vector
	)

privatevirtual

Computes deletion feature vector.

Parameters

[in]	g	Input graph.
[in]	i	ID of node in `g` that has to be deleted.
[out]	feature_vector	Return variable. Empty when called. Must be of size ged::MLBasedMethod::num_features_ when exiting.

Note: Must be overridden by derived classes.

Reimplemented in ged::BipartiteML< UserNodeLabel, UserEdgeLabel >, and ged::RingML< UserNodeLabel, UserEdgeLabel >.

Definition at line 1524 of file ml_based_method.ipp.

◆ ml_populate_insertion_feature_vector_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >::ml_populate_insertion_feature_vector_	(	const GEDGraph &	h,
		GEDGraph::NodeID	k,
		std::vector< double > &	feature_vector
	)

privatevirtual

Computes insertion feature vector.

Parameters

[in]	h	Input graph.
[in]	k	ID of node in `h` that has to be inserted.
[out]	feature_vector	Return variable. Empty when called. Must be of size ged::MLBasedMethod::num_features_ when exiting.

Note: Must be overridden by derived classes.

Reimplemented in ged::BipartiteML< UserNodeLabel, UserEdgeLabel >, and ged::RingML< UserNodeLabel, UserEdgeLabel >.

Definition at line 1529 of file ml_based_method.ipp.

◆ ml_populate_substitution_feature_vector_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >::ml_populate_substitution_feature_vector_	(	const GEDGraph &	g,
		const GEDGraph &	h,
		GEDGraph::NodeID	i,
		GEDGraph::NodeID	k,
		std::vector< double > &	feature_vector
	)

privatevirtual

Computes substitution feature vector.

Parameters

[in]	g	Input graph.
[in]	h	Input graph.
[in]	i	ID of node in `g` that has to be substituted.
[in]	k	ID of node in `h` that has to be substituted.
[out]	feature_vector	Return variable. Empty when called. Must be of size ged::MLBasedMethod::num_features_ when exiting.

Note: Must be overridden by derived classes.

Reimplemented in ged::BipartiteML< UserNodeLabel, UserEdgeLabel >, and ged::RingML< UserNodeLabel, UserEdgeLabel >.

Definition at line 1519 of file ml_based_method.ipp.

◆ ml_set_default_options_()

template<class UserNodeLabel , class UserEdgeLabel >

void ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >::ml_set_default_options_ ( )

privatevirtual

Sets all options that are not among the ones shared by all derived classes of ged::MLBasedMethod to default values.

Note: Must be overridden by derived classes that have options that are not among the ones shared by all derived classes of ged::MLBasedMethod.

Reimplemented in ged::BipartiteML< UserNodeLabel, UserEdgeLabel >, and ged::RingML< UserNodeLabel, UserEdgeLabel >.

Definition at line 1492 of file ml_based_method.ipp.

◆ ml_valid_options_string_()

template<class UserNodeLabel , class UserEdgeLabel >

std::string ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >::ml_valid_options_string_ ( ) const

privatevirtual

Returns string of all valid options that are not among the ones shared by all derived classes of ged::MLBasedMethod.

Returns: String of the form "[--<option> <arg>] [...]".

Note: Must be overridden by derived classes that have options that are not among the ones shared by all derived classes of ged::MLBasedMethod.

Reimplemented in ged::BipartiteML< UserNodeLabel, UserEdgeLabel >, and ged::RingML< UserNodeLabel, UserEdgeLabel >.

Definition at line 1478 of file ml_based_method.ipp.

◆ predict()

template<class UserNodeLabel , class UserEdgeLabel >

double ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >::predict	(	const GEDGraph &	g,
		const GEDGraph &	h,
		const NodeMap::Assignment &	assignment
	)

Predicts the type of a node assignment.

Parameters

[in]	g	Input graph.
[in]	h	Input graph.
[in]	assignment	An assignment of a node in `g` or ged::dummy_node() to a node in `h` or ged::dummy_node().

Returns: A value between 0 and 1. If smaller than 0.5, the assignment is predicted to be good, otherwise it is predicted to be bad.

Definition at line 74 of file ml_based_method.ipp.

The documentation for this class was generated from the following files:

src/methods/ml_based_method.hpp
src/methods/ml_based_method.ipp

Public Member Functions

Protected Attributes

Private Member Functions

Detailed Description

template<class UserNodeLabel, class UserEdgeLabel> class ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >

Member Function Documentation

◆ lsape_default_post_graph_init_()

◆ lsape_init_()

◆ lsape_init_graph_()

◆ lsape_parse_option_()

◆ lsape_populate_instance_()

◆ lsape_pre_graph_init_()

◆ lsape_set_default_options_()

◆ lsape_valid_options_string_()

◆ ml_get_num_features_()

◆ ml_init_()

◆ ml_init_feature_variables_()

◆ ml_init_for_num_features_()

◆ ml_init_graph_()

◆ ml_parse_option_()

◆ ml_populate_deletion_feature_vector_()

◆ ml_populate_insertion_feature_vector_()

◆ ml_populate_substitution_feature_vector_()

◆ ml_set_default_options_()

◆ ml_valid_options_string_()

◆ predict()

template<class UserNodeLabel, class UserEdgeLabel>
class ged::MLBasedMethod< UserNodeLabel, UserEdgeLabel >