JP7807992B2 - Graph integration system and method - Google Patents

Description

The present invention generally relates to graph integration.

Technologies related to graph integration are known, for example, from Patent Documents 1 and 2. According to the technology disclosed in Patent Document 1, graphs are integrated according to rules that correspond to the type of difference between graphs (for example, insertion errors, omission errors, substitution errors). According to the technology disclosed in Patent Document 2, graphs are integrated according to rules that correspond to the frequency of overlap between graphs, etc.

JP2010-32919 WO2012/035754

The technologies disclosed in both Patent Documents 1 and 2 mechanically determine which nodes (or edges) in a graph are related to each other. For example, nodes or edges that use the same property value for the same property item (e.g., name) are determined to be related to each other.

However, when graphs are created by multiple different entities (e.g., individuals or organizations) for the same object or for multiple objects with overlapping portions, the representation of the same object or overlapping portions will not necessarily be the same between the graphs. For example, the same property items and property values may not be used for the same object elements (elements in the object) that are treated as nodes or edges. Also, the number of nodes or edges for the same object or overlapping portions may differ, or a node as a branch may only exist on one side. For these reasons, it is not always possible to mechanically distinguish between nodes or edges that are related to each other between graphs.

A graph integration system accepts the specification of a partition group pair, which is a pair of a first partition group and a second partition group that overlaps the first partition group. The partition group pair is domain knowledge. The first partition group is one or more first partitions in a first graph. The second partition group is one or more second partitions in a second graph. The first graph is a graph composed of a plurality of first graph elements, which are first nodes and first edges. A first partition is a set of one or more sequential first edges and/or first nodes at both ends of each of the one or more first edges. Each first graph element is associated with one or more first property items and a first property value for each of the one or more first property items. The second graph is a graph composed of a plurality of second graph elements, which are second nodes and second edges. A second partition is a set of one or more sequential second edges and/or second nodes at both ends of each of the one or more second edges. Each second graph element is associated with one or more second property items and a second property value for each of the one or more second property items.

The graph integration system constructs a group of one or more rules based on a property relationship between one or more first property values among one or more first property values belonging to a first group of partitions and one or more second property values among one or more second property values belonging to a second group of partitions. Each of the one or more rules is either a rule for identifying an overlapping portion of the first and second graphs or a rule for integrating the first and second graphs. The graph integration system integrates the first and second graphs based on the constructed group of rules.

This invention makes it possible to integrate graphs even if the graphs express the same object or overlapping parts differently.

An example of two graphs and their overlapping areas is shown below. An example of the configuration of a subgraph belonging to the overlapping portion of one of the graphs is shown below. An example of the configuration of a subgraph belonging to the overlapping portion of the other graph is shown below. 1 illustrates an example of the configuration of a graph integration system according to an embodiment of the present invention. 10 shows an example of functional blocks of a graph integration unit. 10 shows an example of a UI displayed in preprocessing. 10 shows an example of a UI displayed in overlapping domain knowledge acquisition. 10A and 10B show an outline of an example of rule group construction. 10 shows an example of a UI displayed in overlapping domain knowledge acquisition. 10 shows an example of a UI displayed during integration target extraction. 10 shows an example of a UI displayed in integrated domain knowledge acquisition. 10 shows an example of a UI displayed in integrated domain knowledge acquisition. 10 shows an example of a UI displayed in graph integration. 10 shows an example of a UI displayed in post-processing. An example of multiple routes is shown below. 1 shows an example of a route list. An example of the overall system configuration including the graph integration system is shown below.

In the following description, an "interface apparatus" may refer to one or more interface devices. The one or more interface devices may be at least one of the following:
An I/O interface device is one or more I/O (Input/Output) interface devices. The I/O (Input/Output) interface devices are interface devices for at least one of an I/O device and a remote display computer. The I/O interface device for the display computer may be a communications interface device. The at least one I/O device may be a user interface device, for example, either an input device such as a keyboard and a pointing device, or an output device such as a display device.
A communication interface apparatus that is one or more communication interface devices. The one or more communication interface devices may be one or more homogeneous communication interface devices (e.g., one or more NICs (Network Interface Cards)) or two or more heterogeneous communication interface devices (e.g., a NIC and an HBA (Host Bus Adapter)).

In the following description, "memory" refers to one or more memory devices, which are an example of one or more storage devices, and may typically be a primary storage device. At least one memory device in the memory may be a volatile memory device or a non-volatile memory device.

In the following description, a "persistent storage device" may refer to one or more persistent storage devices, which are an example of one or more storage devices. A persistent storage device may typically be a non-volatile storage device (e.g., an auxiliary storage device), and more specifically, may be, for example, a hard disk drive (HDD), a solid state drive (SSD), a non-volatile memory express (NVME) drive, or a storage class memory (SCM).

Also, in the following description, "storage device" may refer to at least memory, including memory and persistent storage devices.

In the following description, a "processor" may refer to one or more processor devices. The at least one processor device may typically be a microprocessor device such as a CPU (Central Processing Unit), but may also be another type of processor device such as a GPU (Graphics Processing Unit). The at least one processor device may be single-core or multi-core. The at least one processor device may also be a processor core. The at least one processor device may also be a broader processor device such as a circuit that is a collection of gate arrays written in a hardware description language that performs some or all of the processing (e.g., an FPGA (Field-Programmable Gate Array), a CPLD (Complex Programmable Logic Device), or an ASIC (Application Specific Integrated Circuit)).

Furthermore, the following explanation may refer to data that produces an output in response to an input, but this data may be data of any structure (for example, structured data or unstructured data), or may be a learning model such as a neural network, genetic algorithm, or random forest that generates an output in response to an input.

In the following description, functions may be described using the expression "yyy unit," but the functions may be realized by one or more computer programs being executed by a processor, by one or more hardware circuits (e.g., FPGA or ASIC), or by a combination of these. When a function is realized by a program being executed by a processor, the specified processing is performed using a storage device and/or interface device, etc., as appropriate, and therefore the function may be considered to be at least part of the processor. Processing described using a function as the subject may be processing performed by a processor or a device having that processor. A program may be installed from program source. The program source may be, for example, a program distribution computer or a computer-readable storage medium (e.g., a non-transitory storage medium). The description of each function is an example, and multiple functions may be combined into a single function, or a single function may be divided into multiple functions.

In the following description, the graph data representing a graph as a set of nodes and edges is in json format, but other formats are also acceptable. The graph may be a directed graph or an undirected graph. For each graph, the graph data may include the following:
・Graph ID
For each node, node data representing the node. The node data may include the node ID, the IDs of the edges connected to the node, one or more property items related to the node, and a property value for each property item.
Edge data representing each edge. The edge data may include the ID of the edge, the IDs of the nodes at both ends connected to the edge (if the edge is a directed edge, the IDs of the start node and end node), one or more property items related to the edge, and a property value for each property item.

One embodiment of the present invention will be described below with reference to the drawings.

Figure 1 shows the structure of graph data prepared in one embodiment of the present invention.

An example of the first graph data is power supply station A equipment data. The power supply station A equipment data represents graph 105A, which is an example of the first graph. Graph 105A represents power network A, which is the subject of monitoring and/or control by power supply station A.

An example of the second graph data is power supply station B equipment data. The power supply station B equipment data represents graph 105B, which is an example of the second graph. Graph 105B represents power network B, which is the target of monitoring and/or control by power supply station B.

Each of power networks A and B includes multiple power lines and multiple electrical equipment. In each of graphs 105A and 105B, nodes correspond to electrical equipment, and edges correspond to power lines or portions thereof. Nodes and edges are collectively referred to as "graph elements." A graph element is a node or an edge.

Both graphs 105A and 105B may be single-layer graphs or multi-layer graphs. Multi-layer graphs may be composed of an upper-level graph and one or more lower-level graphs. An upper-level graph may be a graph belonging to an upper layer and may be composed of multiple upper-level nodes and one or more upper-level edges (both ends of each upper-level edge may be upper-level nodes). A lower-level graph may be a graph belonging to a lower layer and is a detailed version of one upper-level edge and may be composed of multiple lower-level nodes and multiple lower-level edges (one end of each lower-level edge may be a lower-level node, and the other end may be a lower-level node or an upper-level node).

Graphs 105A and 105B illustrated in FIG. 1 may each be an example of a higher-level graph. Graphs 200A and 200B illustrated in FIG. 2A and FIG. 2B may each be an example of a lower-level graph. According to FIG. 2A, graph 200A is a lower-level graph that represents a detailed configuration of the higher-level edge "LA01" of graph 105A. According to FIG. 2B, graph 200B is a lower-level graph that represents a detailed configuration of the higher-level edge "LB01" of graph 105B.

The "multiple layers" of a graph may refer to multiple logical layers, and more specifically, may be realized by, for example, making the property value of a certain property item of a graph element multi-level. For example, a graph element with a property value of "1" for a certain property item may be an upper node or an upper edge, and a graph element with a property value of "2" for a certain property item may be a lower node or an lower edge.

For example, in the power transmission and distribution business, applications that provide services such as power supply and demand forecasts and facility planning for wide-area areas refer to graph data for wide-area areas in order to provide these services.

However, it is difficult for a single administrator to prepare graphs for a wide area. For each of the multiple regions within a wide area, the administrator for that region can create a graph for that region, and then these graphs can be integrated to prepare a graph for the wide area.

The integration of graphs 105A and 105B can be achieved by integrating subgraphs belonging to the overlapping portion 101 (the same range) of power networks A and B. However, the representation of the subgraph in the overlapping portion 101 of graph 105A may differ from the representation of the subgraph in the overlapping portion 101 of graph 105B. For example, even though these subgraphs represent the overlapping portion 101, which is the same power network portion, a node serving as a branch point on a power line may exist in only one of the subgraphs, or a node serving as a branch point may exist in both subgraphs but the property items or property values of the node may be different. This makes at least one of the following difficult:
- Integration of graphs 105A and 105B.
Identifying subgraphs in the overlapping portions of graphs 105A and 105B.

In this embodiment, even if the overlapping portion 101 is expressed differently between graphs 105A and 105B, it is possible to identify the subgraphs in the overlapping portion 101 of both graphs 105A and 105B and integrate the subgraphs in the overlapping portion 101.

Figure 3 shows an example configuration of a graph integration system according to one embodiment of the present invention.

In this embodiment, the graph integration system 300 is a physical computer system (one or more physical computers), but it may alternatively be a logical computer system based on a physical computer system (e.g., a virtual machine or a cloud computing service).

The graph integration system 300 comprises an interface device 301, a memory device 303, and a processor 304 connected thereto.

A communication network (not shown) and an input/output device 302 are connected to the interface device 301. The input/output device 302 may be provided in the graph integration system 300, or may be a remote device connected via a communication network. For example, the graph integration system 300 may be a server system, and the input/output device 302 may be a client system. The input/output device 302 may include a keyboard and display, or a touch panel. A UI (User Interface) is provided and displayed on the input/output device 302. The UI here may typically be a GUI (Graphical User Interface).

The storage device 303 stores data and computer programs. Examples of the data stored include an original graph dataset 331, a property dataset 332, a manipulation judgment dataset 333, extraction rule data 334, extracted subgraph data 335, integrated rule data 336, integrated subgraph data 337, and integrated graph data 338.

The original graph dataset 331 is a set of graph data representing each original graph (a graph that can be integrated). Graphs 105A and 105B shown in FIG. 1 are examples of original graphs. The property dataset 332 is a set of property data (a set of pairs of property items and property values) for each graph. The processing judgment dataset 333 is a set of processing rule data and judgment rule data. The extraction rule data 334 is data representing a set of rules for extracting subgraphs (identifying overlapping portions). The extracted subgraph data 335 is graph data representing subgraphs that are all or part of the original graph that have been extracted. The integration rule data 336 is data representing a set of rules for integration. The integrated subgraph data 337 is graph data representing an integrated subgraph (a graph that is the result of integrating subgraphs). The integrated graph data 338 is graph data representing an integrated graph (a graph that is the result of integrating original graphs).

The processor 304 reads and executes a computer program from the storage device 303, thereby realizing functions such as the graph integration unit 30. As shown in FIG. 4, the graph integration unit 30 includes functions such as a UI provision unit 401, domain knowledge acquisition unit 402, rule construction unit 403, graph processing unit 404, and integrated data output unit 405. The graph integration unit 30 performs pre-processing (S341), overlapping domain knowledge acquisition (S342), integration target extraction (S343), integrated domain knowledge acquisition (S344), graph integration (S345), and post-processing (S346). The processes of S341 to S346 are explained in detail below. Note that, to avoid confusion, elements related to graph 105A may be referred to as "first," and elements related to graph 105B may be referred to as "second."

<Preprocessing (S341)>

As shown in FIG. 3, the UI providing unit 401 displays a UI on the input/output device 302 that accepts the specification of the original graph to be read. The UI providing unit 401 reads the graph data and property data of the original graph (e.g., the ID of the original graph) specified via the UI from the original graph dataset 331 and the property dataset 332. Hereinafter, the original graphs to be read are assumed to be graphs 105A and 105B illustrated in FIG. 1. Therefore, the graph data read out is assumed to be power supply station A equipment data and power supply station B equipment data.

As shown in FIG. 5, the UI providing unit 401 displays the UI 500 on the input/output device 302. The UI 500 has display areas 510A and 510B.

Display area 510A displays graph 105A represented by the A power supply station equipment data and property list 512A represented by the property data of graph 105A. Property list 512A is composed of property entries for each first edge of graph 105A. For each edge, the property entry includes multiple first property items (edge ID, attribute value 1, attribute value 2, ...) associated with the first edge and a first property value for each first property item.

Display area 510B displays graph 105B represented by the B power supply station equipment data and property list 512B represented by the property data of graph 105B. Property list 512B is made up of property entries for each second edge of graph 105B. For each edge, the property entry includes multiple second property items associated with the second edge and a second property value for each second property item. In the example shown in FIG. 5, all property items are the same between graphs 105A and 105B, but the property values are different.

The user checks the displayed graph 105A, property list 512A, graph 105B, and property list 512B, and presses button 521 on UI 500. When button 521 is pressed, preprocessing ends.

Note that at least one of property lists 512A and 512B may have entries for each node instead of or in addition to entries for each edge. Also, the property items may differ between graphs 105A and 105B. Also, at least one of graphs 105A and 105B may have only one property item.

<Acquire overlapping domain knowledge (S342)>

When button 521 on UI 500 illustrated in FIG. 5 is pressed, the UI providing unit 401 displays UI 600 on the input/output device 302. UI 600 has a display area 610A for graph 105A and a display area 610B for graph 105B.

The domain knowledge acquisition unit 402 accepts the designation of a partition group pair via the UI 600. A partition group pair is a pair consisting of a first partition group and a second partition group that overlaps with the first partition group.

The first partition group is one or more first partitions in graph 105A (an example of a first graph). A first partition is a set of one or more sequential first edges and/or first nodes at both ends of each of the one or more first edges. "One or more sequential first edges" may be referred to as a "first path." As described above, each first graph element in graph 105A is associated with one or more first property items and a first property value for each of the one or more first property items.

The second partition group is one or more second partitions in graph 105B (an example of a second graph). A second partition is a set of one or more sequential second edges and/or second nodes at both ends of each of the one or more second edges. "One or more sequential second edges" may be referred to as a "second path." As described above, each second graph element in graph 105B is associated with one or more second property items and a second property value for each of the one or more second property items.

A partition group pair is domain knowledge. Specifically, the partition group pair specified in this "Overlap Domain Knowledge Acquisition (S342)" is domain knowledge for identifying the overlapping portion (a pair of overlapping partition groups in graphs 105A and 105B). That is, the domain knowledge acquisition unit 402 accepts from the user the specification of the first and second partition groups that belong to the overlapping portion of graphs 105A and 105B. Even if the representations of the subgraphs that belong to the overlapping portion between graphs 105A and 105B are different, the graph integration unit 30 can determine the first and second partition groups that belong to the overlapping portion. In the example of Figure 6, the first edge "LA01" is specified as the first partition group, and the UI provision unit 401 replaces the property list 512A with a property list 612A that consists only of property entries for the specified first edge "LA01." The second edge "LB02" is specified as the second partition group, and the UI provision unit 401 replaces the property list 512B with a property list 612B consisting only of property entries for the specified second edge "LB02."

The user checks the displayed property lists 612A and 612B and presses button 621 on UI 600. When button 621 is pressed, overlapping domain knowledge acquisition ends.

Specifying overlapping domain knowledge is easy for the user, as it only requires specifying overlapping sections known to the user among the graphs 105A and 105B arranged on the UI 600.

<Integration Target Extraction (S343)>

When button 621 of the UI 600 illustrated in FIG. 6 is pressed, integration target extraction (S343) begins. The rule construction unit 403 constructs a rule group, which is one or more rules, based on the property relationship, which is the relationship between one or more first property values among one or more first property values belonging to a first partition group in the specified domain knowledge (here, overlapping domain knowledge) and one or more second property values among one or more second property values belonging to a second partition group in the domain knowledge. Here, each of the "one or more rules" is either a rule for identifying overlapping portions of graphs 105A and 105B or a rule for integrating the first and second graphs. Furthermore, the "property relationship" refers to which of multiple judgment conditions is satisfied among multiple combinations of multiple first property values belonging to the first partition group, multiple second property values belonging to the second partition group, and multiple processing methods related to the property values. An example of property relationships and rule group construction will be described with reference to FIG. 7.

As shown in FIG. 7, the property data set 332 contains property data for each graph. For each graph element of the graph, the property data includes data for one or more property sets associated with that graph element. A property set is a pair of a property item and a property value. For each property set, the data represents the identification number of the property set (an example of an ID), Key (property item), Type (type of property value), and Value (property value).

As shown in FIG. 7 , the processing judgment data set 333 is a set of processing rule data 720 and judgment rule data 730. The processing rule data 720 includes, for each processing method, data representing the identification number of the processing method and the processing method (e.g., the processing name and the details of the processing). The judgment rule data 730 includes, for each judgment condition, data representing the identification number of the judgment condition and the judgment condition (e.g., the judgment name and the details of the judgment condition).

In the example shown in Figure 7, the specified domain knowledge is a pair of a first edge "LA01" and a second edge "LB02". For the graphs 105A and 105B to be integrated, the rule construction unit 403 reads property data 710A of the first edge "LA01" and property data 710B of the second edge "LB02" from the property dataset 332. The rule construction unit 403 constructs a group of rules using the property data 710A of the first edge "LA01", the property data 710B of the second edge "LB02", the processing rule data 720, and the judgment rule data 730. Specifically, for example, the rule construction unit 403 generates processing result data 740 that indicates, for each of all possible combinations of the property set of the first edge "LA01," the property set of the second edge "LB02," the processing method, and the judgment condition, the combination and whether the judgment condition for that combination is satisfied. In the processing result data 740, for each combination, the "A attribute value" indicates the identification number of property set A (the property set to which the property item of the first edge "LA01" belongs) in that combination, "A processing" indicates the identification number of the processing method applied to the property value in that property set A, the "B attribute value" indicates the identification number of property set B (the property set to which the property item of the second edge "LB02" belongs) in that combination, "B processing" indicates the identification number of the processing method applied to the property value in that property set B, and "YES?" indicates whether the judgment condition for that combination is satisfied.

The rule construction unit 403 constructs rules based on combinations that include satisfied judgment conditions, and displays a UI 800 displaying a list 801 of the constructed rules on the input/output device 302, as shown in FIG. 8. The rules constructed in this "integration target extraction (S343)" (rules displayed on UI 800) are rules for identifying overlapping portions of graphs 105A and 105B, and the one or more rules represented by list 801 are an example of a group of overlapping rules for identifying overlapping portions. The rule construction unit 403 constructs rules based on which judgment conditions are satisfied when which processing method is applied to which property set A and which processing method is applied to which property set B.

As shown in FIG. 8, a priority may be set for each rule. The priority may be determined in the order in which the rules are constructed or in some other order, and may be determined by the rule construction unit 403 or set by the user via the UI 800. If one or more constructed rules conflict with each other, the rule with the highest priority among the conflicting rules may be used to identify overlapping portions. The UI 800 may also have a tool that accepts from the user requests to edit or delete constructed rules, or a tool that accepts from the user requests to add rules for identifying overlapping portions.

Through the above process, a set of rules for identifying overlapping portions is constructed (the set of rules is finalized). The user checks the set of rules and presses button 821 on UI 800.

When button 821 on UI 800 is pressed, graph processing unit 404 saves extraction rule data 334 (see FIG. 3 ) representing the constructed set of rules in storage device 303, and uses the set of rules to extract the objects to be integrated from graphs 105A and 105B (i.e., identifies the graph elements of the subgraphs belonging to the overlapping portion). Specifically, graph processing unit 404 identifies a graph element combination (a combination of graph elements of graph 105A and graph elements of graph 105B) that corresponds to one of the rules in the constructed set of rules (the rule with the highest priority if there are conflicting rules). Specifically, the "graph element combination that corresponds to a rule" is as follows:
- One or more graph elements α of graph 105A are associated with property item A specified in the rule regarding the first edge "LA01", and one or more graph elements β of graph 105B are associated with property item B specified in the rule regarding the second edge "LB02".
- The relationship between value A obtained by applying the processing method specified in the rule for the first edge "LA01" to the property value of property item A of one or more graph elements α and value B obtained by applying the processing method specified in the rule for the second edge "LB02" to the property value of property item B of one or more graph elements β satisfies the judgment condition specified in the rule.
In this case, a set of one or more graph elements α and a set of one or more graph elements β are sets that overlap each other.

The graph processing unit 404 displays a UI 900 representing the extracted combination targets on the input/output device 302, as shown in FIG. 9. According to the example shown in FIG. 9, the "graph element combinations that satisfy the rule" include the domain knowledge specified by the user (the combination of the first edge "LA01" and the second edge "LB02") as well as the combination of the first edge "LA02" and the second edge "LB01". The UI providing unit 401 highlights the graph elements (edges and their end nodes) that belong to the identified graph element combination among graphs 105A and 105. The UI providing unit 401 also displays property lists 912A and 912B of the graph elements that belong to the identified graph element combination on the UI 900. The user checks the subgraphs that belong to the overlapping portion and presses button 921 on the UI 900. When button 921 is pressed, extracted subgraph data 335 (see Figure 3) representing the subgraphs belonging to the overlapping portion for each of graphs 105A and 105B is saved in storage device 303, and integration target extraction is completed.

As described above, a rule that is satisfied by the specified domain knowledge (partition group pair) is constructed, a graph element combination (another partition group pair) that satisfies the constructed rule is identified, and the specified domain knowledge and the graph element combination identified starting from it are extracted as a subgraph belonging to the overlapping portion. The constructed rule is based on the satisfied judgment condition, the processing method that belongs to the combination that satisfies the judgment condition, and the property item of the property value processed by the processing method. This makes it possible to extract a subgraph belonging to the overlapping portion even if the expression of the subgraph belonging to the overlapping portion is different between graphs 105A and 105B. Furthermore, it is expected that the subgraph will be extracted even if the user does not know the entire extent of the subgraph that belongs to the overlapping portion between graphs 105A and 105B.

<Integrated Domain Knowledge Acquisition (S344)>

When button 921 of UI 900 illustrated in FIG. 9 is pressed, UI providing unit 401 displays UI 1000 illustrated in FIG. 10 on input/output device 302. UI 1000 has display area 1010A for a subgraph extracted from graph 105A and display area 1010B for a subgraph extracted from graph 105B. For example, display area 1010A displays subgraph 1011A (an example of a subgraph) belonging to first edge "LA01." Display area 1010B displays subgraph 1011B belonging to second edge "LB02," which overlaps with first edge "LA01." In other words, subgraphs are lined up in UI 1000. Note that in this example, it is assumed that there is no subgraph (subgraph) belonging to the first edge "LA02" and second edge "LB01," which are a different graph element combination.

As shown in Figure 10, the representations (specifically, configurations) of subgraphs 1011A and 1011B, which should represent the same object in the overlapping portion, are different. Even though the representations of subgraphs 1011A and 1011B are different, in this embodiment, subgraphs 1011A and 1011B can be integrated.

Specifically, the domain knowledge acquisition unit 402 receives the specification of a partition group pair as integrated domain knowledge (domain knowledge for integration) via the UI 1000. As described above, a partition group pair is a pair of a first partition group and a second partition group that overlap (match) each other. In the example shown in FIG. 10, subgraph 1011A specifies a single first edge "EA01" as the first partition group, and subgraph 1011B specifies two consecutive second edges "EB01" and "EB02" as the second partition group. Therefore, based on the property data of graphs 105A and 105B, the UI provision unit 401 displays, on the UI 1000, a property list 1012A for the first edge "EA01" as the first partition group and a property list 1012B for the second edges "EB01" and "EB02" as the second partition group.

The user checks the displayed property lists 1012A and 1012B and presses button 1021 on UI 1000. When button 1021 is pressed, integrated domain knowledge acquisition ends.

The integrated domain knowledge can be specified simply by specifying the overlapping sections known to the user among the subgraphs 1011A and 1011B arranged on the UI 1000, making it easy for the user to specify domain knowledge.

<Graph Integration (S345)>

When button 1021 on the UI 1000 illustrated in FIG. 10 is pressed, the rule construction unit 403 constructs a set of rules for integration in the same manner as a set of rules for identifying overlapping portions. In other words, the set of rules constructed based on overlapping domain knowledge (an example of a first partition group pair) is a set of rules for identifying overlapping portions, while the set of rules constructed based on integrated domain knowledge (an example of a second partition group pair) is a set of integrated rules for integration.

In the example shown in Figure 10, the specified integrated domain knowledge is a pair of the first edge "EA01" and the second edges "EB01" and "EB02". For the subgraphs 1011A and 1011B to be integrated, the rule construction unit 403 reads the property data of the first edge "EA01" and the property data of the second edges "EB01" and "EB02" from the property dataset 332. The rule construction unit 403 constructs a group of rules using the property data of the first edge "EA01", the property data of the second edges "EB01" and "EB02", the processing rule data 720, and the judgment rule data 730. Specifically, for example, the rule construction unit 403 generates processing result data for each of all possible combinations of the property set of the first edge "EA01," the property sets of the second edges "EB01" and "EB02," the processing methods, and the judgment conditions, indicating whether the combination satisfies the judgment conditions for that combination. The rule construction unit 403 constructs rules based on combinations that include satisfied judgment conditions, and, as shown in FIG. 11, displays a UI 1100 on the input/output device 302 that displays a list 1101 of the constructed rules. The rules constructed in this "Graph Integration (S345)" (the rules displayed on the UI 1100) are rules for integrating subgraphs 1011A and 1011B, and the one or more rules represented by the list 1101 are an example of a group of rules for integration.

As with the group of rules for identifying overlapping portions, a priority may be set for each rule, as shown in FIG. 11. The priority may be determined in the order in which the rules are constructed or in some other order, and may be determined by the rule construction unit 403 or set by the user via the UI 1100. If there is a conflicting rule among one or more constructed rules, the rule with the highest priority among those conflicting rules may be used to identify overlapping portions. The UI 1100 may also have a tool that accepts from the user requests to edit or delete constructed rules, or a tool that accepts from the user requests to add rules for identifying overlapping portions.

Through the above process, a set of rules for integration is constructed (the set of rules is finalized). The user checks the set of rules and presses button 1121 on UI 1100.

When button 1121 on UI 1100 is pressed, graph processing unit 404 saves integrated rule data 336 (see FIG. 3 ) representing the constructed set of rules in storage device 303, and integrates subgraphs 1011A and 1011B using the constructed set of rules. Specifically, graph processing unit 404 identifies a graph element combination (a combination of graph elements of subgraph 1011A and graph elements of subgraph 1011B) that corresponds to one of the rules in the constructed set of rules (the rule with the highest priority if there are conflicting rules). Specifically, the "graph element combination that corresponds to a rule" is as follows:
- One or more graph elements α of subgraph 1011A are associated with property item A specified in the rule for the first edge "EA01", and one or more graph elements β of subgraph 1011B are associated with property item B specified in the rule for at least one of the second edges "EB01" and "EB02".
- The relationship between value A obtained by applying the processing method specified in the rule for the first edge "EA01" to the property value of property item A of one or more graph elements α and value B obtained by applying the processing method specified in the rule for at least one of the second edges "EB01" and "EB02" to the property value of property item B of one or more graph elements β satisfies the judgment condition specified in the rule.
In this case, a set of one or more graph elements α and a set of one or more graph elements β are sets that overlap each other.

The graph processing unit 404 stores integrated subgraph data 337 (see Figure 3) representing the integrated subgraph, which is the graph resulting from integrating subgraphs 1101A and 1101B, in the storage device 303, and displays a UI 1200 representing the integrated subgraph 1211 on the input/output device 302, as shown in Figure 12. The UI 1200 displays a property list 1212 for the integrated subgraph 1211. The property list 1212 has a property entry for each graph element of the integrated subgraph 1211. As illustrated in Figure 12, the graph processing unit 404 changes the IDs of the graph elements of subgraph 1011A and subgraph 1011B in accordance with a pre-defined naming rule to avoid the occurrence of graph elements with duplicate IDs in the integrated subgraph 1211, and then integrates subgraphs 1011A and 1011B.

The user checks the integrated subgraph 1211 and property list 1212 and presses button 1221 on UI 1200. When button 1221 is pressed, graph integration is completed.

The common challenge between identifying overlapping parts (extracting integration targets) and integrating graphs is determining which property values between graphs should be compared and how to identify which graph elements are related. The input required to solve this common challenge is domain knowledge. For this reason, in this embodiment, it is possible to standardize the processing methods and judgment conditions between identifying overlapping parts (extracting integration targets) and integrating graphs. Sharing these can reduce the amount of data and also makes it easier to maintain the processing methods and judgment conditions.

In addition, by adding or editing processing methods and judgment conditions as appropriate, it is expected that the accuracy of identifying overlapping parts and integrating graphs will be improved. Furthermore, since the processing methods and judgment conditions are versatile, they can be expected to be applied to a variety of purposes.

As described above, rules satisfied by the specified integrated domain knowledge are constructed, graph element combinations that satisfy the constructed rules are identified, and the specified integrated domain knowledge and the graph element combinations identified based on the constructed rules are integrated. The constructed rules are based on the satisfied judgment conditions, the processing methods that belong to the combinations that satisfy the judgment conditions, and the property items of the property values processed by the processing methods. This allows subgraphs 1011A and 1011B to be integrated even if the expressions of overlapping partition groups are different between subgraphs 1011A and 1011B. Furthermore, subgraphs 1011A and 1011B can be integrated even if the user does not know all of the graph element combinations that overlap between subgraphs 1011A and 1011B.

For example, in FIG. 10 (for subgraphs 1011A and 1011B), an edge may be a section (between electrical equipment), attribute values 1 and 2 may be the IDs of the electrical equipment (e.g., towers) at both ends of the section, attribute value 3 may be the ID of the power transmission line to which the section belongs, and attribute value 4 may be an electrical characteristic value (impedance value). In rule construction based on integrated domain knowledge, a satisfied judgment condition is identified: the sum of impedances of one or more consecutive transmission sections that are a group of transmission sections is the same. As a result, a rule based on the satisfied judgment condition is one (rules with priorities "1" and "2" illustrated in FIG. 11) that indicates that the electrical equipment at one end of both transmission section groups with the same sum of impedances is the same, and that the electrical equipment at the other end of both transmission section groups is the same. In integration based on a rule group including such rules, the graph processing unit 404 identifies multiple section pairs between subgraphs 1011A and 1011B. A section pair is a pair of sections with the same sum of impedances. For each section pair, the graph processing unit 404 determines that one end node of the section pair is the same node and the other end nodes of the section pair are the same node. The integration of subgraphs 1011A and 1011B is based on the integration between section pairs.

<Post-processing (S346)>

When button 1221 of UI 1200 illustrated in FIG. 12 is pressed, the graph processing unit 404 integrates graphs 105A and 105B. Specifically, the graph processing unit 404 connects the subgraphs of graph 105A other than integrated subgraph 1211 to integrated subgraph 1211, and also connects the subgraphs of graph 105B other than integrated subgraph 1211. As shown in FIG. 13, the graph processing unit 404 displays UI 1300 on the input/output device 302, which represents integrated graph 1310, which is the graph resulting from the integration of graphs 105A and 105B. A property list 1311 of integrated graph 1310 is displayed on UI 1300.

The user checks the integrated graph 1310 and property list 1311 and presses button 1321 on the UI 1300. When button 1321 is pressed, post-processing ends. When button 1321 is pressed, the integrated data output unit 405 saves integrated graph data 338 (see Figure 3) including the graph data and property data of the integrated graph 1310 in the storage device 303.

As shown in FIG. 15, the graph integration system 300 (interface device 301 of the system 300) according to this embodiment may be connected to one or more external computer systems. Examples of external computer systems include an existing system 1501A as a data source for power supply station A equipment data, an existing system 1501B as a data source for power supply station B equipment data, and an application system 1551 (a computer system that executes at least one application). The power supply station A equipment data and the power supply station B equipment data in the original graph dataset 331 (see FIG. 3) of the graph integration system 300 may be graph data input from the existing systems 1501A and 1501B via or without a UI.

The application system 1551 may include, for example, application system 1551A that executes application 1553A for creating an electrical equipment installation plan by referencing integrated graph data 338, and application system 1551B that executes application 1553B for predicting power supply and demand by referencing integrated graph data 338. The integrated data output unit 405 of the graph integration unit 30 may send the integrated graph data 338 to at least one of application systems 1551A and 1551B. For example, when application system 1551A receives the integrated graph data 338, application 1553A may create an electrical equipment installation plan by referencing integrated graph data 338 and output plan data representing the electrical equipment installation plan. Furthermore, for example, when application system 1551B receives the integrated graph data 338, application 1553B may perform a power supply and demand prediction by referencing integrated graph data 338 and output data representing the prediction result (e.g., time series data).

As described above, by constructing an integrated information infrastructure such as that illustrated in Figure 15, which provides integrated graph data 338 to application 1553, it becomes possible to plan and analyze a wide area.

The above-described embodiment meets the need to quickly analyze graph data within a required range regardless of region (for example, to develop countermeasures limited to the affected area in the event of a disaster). This is because, even if cross-regional graph data could be created manually, it would take time to divide such graph data into graph data within the required range, analyze it, and then integrate it into the original graph data. In this embodiment, graphs are created for each region, making it easy to narrow down analyses, and because graph integration is possible even if the graphs are expressed differently, analysis of wide areas spanning regions is also possible.

Although one embodiment has been described above, this is merely an example for the purpose of explaining the present invention, and is not intended to limit the scope of the present invention to only these embodiments. The present invention can also be implemented in various other forms.

For example, as illustrated in FIG. 14A, there may be multiple paths between nodes. In this case, it may be difficult or impossible to identify overlapping sections between subgraphs. Therefore, for each of graphs 105A and 105B, the graph data may include, for each path between at least one node, the ID of one end node of the path, the ID of the other end node of the path, and the IDs of one or more edges that make up the path. Alternatively, when the graph processing unit 404 receives from the user a designation of two nodes from at least one original graph or subgraph, it may identify all possible paths between the nodes based on the graph data of the original graph or subgraph, and the UI providing unit 401 may display, on a UI (e.g., at least one of UIs 600 and 1000), the ID of one end node of the path, the ID of the other end node of the path, and the IDs of one or more edges that make up the path. For example, the route list shown in FIG. 14B (a list showing, for each route, the ID of one end node of the route, the ID of the other end node of the route, and the IDs of one or more edges that make up the route) may be displayed. This allows overlapping routes to be specified or identified when the user specifies overlapping sections or when the graph integration unit 30 identifies them.

For example, in the above-described embodiment, rule construction is performed at each of the two stages of identifying overlapping portions and integrating graphs. However, rule construction may be performed only for either identifying overlapping portions or integrating graphs. For example, if the overlapping portions are determined in advance (e.g., if the user specifies all domain knowledge regarding the overlapping portions), rules may be constructed only for integrating graphs. In other words, the first graph may be all or a portion of the first overall graph, and the second graph may be all or a portion of the second overall graph that overlaps with the first graph, and the set of rules may be one or more rules for integrating the first and second graphs.

Furthermore, for example, the present invention can be applied to any object that can be represented by a graph. For example, the present invention can be applied not only to a group of devices connected by a network, but also to the integration of graphs that systematically represent some kind of knowledge (for example, graphs that represent experimental procedures or maintenance procedures).

300: Graph Integration System

Claims (10)

a domain knowledge acquisition unit that receives a designation of a partition group pair that is a pair of a first partition group and a second partition group that overlaps the first partition group;
The partition group pairs are domain knowledge,
the first group of partitions is one or more first partitions in a first graph;
the second group of partitions is one or more second partitions in the second graph;
the first graph is a graph configured with a plurality of first graph elements, which are first nodes and first edges;
the first partition is a set of one or more sequential first edges and/or first nodes at both ends of each of the one or more first edges;
each first graph element is associated with one or more first property items and a first property value for each of the one or more first property items;
the second graph is a graph composed of a plurality of second graph elements, which are second nodes and second edges;
the second partition is a set of one or more sequential second edges and/or second nodes at both ends of each of the one or more second edges;
each second graph element is associated with one or more second property items and a second property value for each of the one or more second property items;
a rule construction unit that constructs a rule group, which is one or more rules, based on a property relationship that is a relationship between one or more first property values among the one or more first property values belonging to the first partition group and one or more second property values among the one or more second property values belonging to the second partition group;
each of the one or more rules is either a rule for identifying an overlapping portion of the first and second graphs or a rule for integrating the first and second graphs;
a graph processing unit that integrates the first and second graphs based on the constructed set of rules. the property relationship is a determination as to which of a plurality of determination conditions is satisfied among a plurality of combinations of a plurality of first property values belonging to the first partition group, a plurality of second property values belonging to the second partition group, and a plurality of processing methods related to the property values;
Each of the one or more rules is based on a satisfied judgment condition, a processing method belonging to a combination that satisfies the judgment condition, and a property item of a property value that is processed by the processing method.
The graph integration system of claim 1 . at least one first node and at least one second node represent electrical equipment;
the at least one first edge and the at least one second edge represent a transmission section;
the first property value of the at least one first edge and the second property value of the at least one second edge are impedances;
The satisfied determination condition is that the sum of impedances of one or more consecutive transmission sections that are a group of transmission sections is the same,
The rule based on the satisfied determination condition is a rule that means that the electrical equipment at one end of both transmission section groups having the same sum of impedance is the same, and that the electrical equipment at the other end of both transmission section groups is the same.
The graph integration system of claim 2 . an integrated data output unit that transmits the integrated graph data to at least one of a system that executes an application for developing an installation plan for electrical equipment by referring to integrated graph data, which is data representing a graph in which the first and second graphs are integrated, and a system that executes an application for predicting power supply and demand by referring to the integrated graph data, for at least one of developing an installation plan for electrical equipment and predicting power supply and demand;
The graph integration system of claim 3 further comprising: the domain knowledge acquisition unit accepts designation of a first partition group pair as a pair of overlapping partition groups of the first and second graphs;
the rule construction unit constructs, based on a property relationship of the first partition group pair, an overlap rule set that is a rule set for identifying an overlapping portion of the first and second graphs, including the first partition group pair;
the graph processing unit identifies the overlapping portion based on the overlapping rule group;
the overlapping portion of the first graph is a first subgraph composed of one or more first graph elements of the first graph,
the overlapping portion in the second graph is a second subgraph composed of one or more second graph elements of the second graph,
the domain knowledge acquisition unit accepts designation of a second partition group pair as a pair of overlapping partition groups of the first and second subgraphs for the identified overlapping portion;
the rule construction unit constructs an integration rule set, which is a rule set for integrating the first and second subgraphs, based on a property relationship of the second partition group pair;
the graph processing unit constructs an integrated subgraph by integrating the first and second subgraphs based on the constructed group of integration rules, and constructs an integrated graph by integrating the first and second graphs by integrating the subgraph other than the overlapping portion of the first graph and the subgraph other than the overlapping portion of the second graph into the integrated subgraph;
The graph integration system of claim 2 . the first graph is a whole or part of a first overall graph,
the second graph is a graph that is a whole or a part of a second overall graph and overlaps with the first graph,
the set of rules is one or more rules for integrating the first and second graphs;
The graph integration system of claim 1 . a UI providing unit that provides a UI (User Interface) that displays the first graph represented by the first graph data and the second graph represented by the second graph data;
the domain knowledge acquisition unit accepts designation of the partition group pair via the UI;
the designation of the partition group pair includes a designation of a first partition group in the first graph and a designation of a second partition group in the second graph;
The graph integration system of claim 1 . the UI providing unit displays, for each of the first and second graphs, an ID of one end node of the path, an ID of the other end node of the path, and IDs of one or more edges constituting the path;
The graph integration system of claim 7. The computer receives a designation of a partition group pair that is a pair of a first partition group and a second partition group that overlaps the first partition group;
The partition group pairs are domain knowledge,
the first group of partitions is one or more first partitions in a first graph;
the second group of partitions is one or more second partitions in the second graph;
the first graph is a graph configured with a plurality of first graph elements, which are first nodes and first edges;
the first partition is a set of one or more sequential first edges and/or first nodes at both ends of each of the one or more first edges;
each first graph element is associated with one or more first property items and a first property value for each of the one or more first property items;
the second graph is a graph composed of a plurality of second graph elements, which are second nodes and second edges;
the second partition is a set of one or more sequential second edges and/or second nodes at both ends of each of the one or more second edges;
each second graph element is associated with one or more second property items and a second property value for each of the one or more second property items;
a computer constructing a rule group, which is one or more rules, based on a property relationship that is a relationship between one or more first property values among the one or more first property values belonging to the first group of partitions and one or more second property values among the one or more second property values belonging to the second group of partitions;
each of the one or more rules is either a rule for identifying an overlapping portion of the first and second graphs or a rule for integrating the first and second graphs;
A graph integration method in which a computer integrates the first and second graphs based on the constructed set of rules. Accepting a designation of a partition group pair that is a pair of a first partition group and a second partition group that overlaps the first partition group;
The partition group pairs are domain knowledge,
the first group of partitions is one or more first partitions in a first graph;
the second group of partitions is one or more second partitions in the second graph;
the first graph is a graph configured with a plurality of first graph elements, which are first nodes and first edges;
the first partition is a set of one or more sequential first edges and/or first nodes at both ends of each of the one or more first edges;
each first graph element is associated with one or more first property items and a first property value for each of the one or more first property items;
the second graph is a graph composed of a plurality of second graph elements, which are second nodes and second edges;
the second partition is a set of one or more sequential second edges and/or second nodes at both ends of each of the one or more second edges;
each second graph element is associated with one or more second property items and a second property value for each of the one or more second property items;
constructing a rule group, which is one or more rules, based on a property relationship, which is a relationship between one or more first property values among the one or more first property values belonging to the first group of partitions and one or more second property values among the one or more second property values belonging to the second group of partitions;
each of the one or more rules is either a rule for identifying an overlapping portion of the first and second graphs or a rule for integrating the first and second graphs;
A computer program that causes a computer to integrate the first and second graphs based on the constructed set of rules.