Method, program, and system for converting part of graph data to data structure as an image of homomorphism

A method for converting at least a part of graph data including nodes and edges to a data structure as an image of a homomorphism thereof by using at least one kernel pattern for graph matching, the method comprising the steps of:

• providing a kernel pattern including one representative node variable, the representative node variable having a first constraint that at most one node in the graph data matches the representative node variable and the node is prohibited from matching a node variable in another kernel pattern, wherein the kernel pattern includes at least one node variable of a second type and has a second constraint that a node in the graph data matching the second-type node variable has to uniquely correspond to the node in the graph data matching the representative node variable in the kernel pattern;
• performing matching between the graph data and the kernel pattern to obtain a matching result that does not violate constraints including the first constraint, wherein the step of performing matching includes the steps of:
• obtaining, as the matching result, information on a subset of the graph data that matches the kernel pattern;
• and
• removing, from the matching result information on any subset of the graph data that violates the constraints;
• and
• generating a data structure corresponding to the matching result that does not violate the constraints.

A computer readable program stored on a non transitory computer-readable storage medium for converting at least a part of graph data including nodes and edges to a data structure as an image of a homomorphism thereof by using at least one kernel pattern for graph matching, wherein the computer readable program when executed on a computer causes the computer to perform the steps of:

• providing a kernel pattern including one representative node variable, the representative node variable having a first constraint that at most one node in the graph data matches the representative node variable and the node is prohibited from matching a node variable in another kernel pattern, wherein the kernel pattern includes at least one node variable of a second type and has a second constraint that a node in the graph data matching the second-type node variable has to uniquely correspond to the node in the graph data matching the representative node variable in the kernel pattern;
• performing matching between the graph data and the kernel pattern to obtain a matching result that does not violate constraints including the first constraint;
• and
• generating a data structure corresponding to the matching result that does not violate the constraints.