WO2025126251A1 - Information processing device and information processing method - Google Patents

Abstract

An information processing device (100) comprises: a graph data acquisition unit (10) that acquires first graph data indicating a first graph (G1) having an original node (n13) including first information and second information, a first edge (e11) connected to the original node (n13) in association with the first information, and a second edge (e12) connected to the original node (n13) in association with the second information; and a graph generation unit (30) for generating second graph data indicating a second graph (G1') in which the original node (n13) is replaced in a partial graph (g1') having a plurality of nodes including a first node (n15) corresponding to the first information in the first graph (G1) and a second node (n16) corresponding to the second information in the first graph (G1). The graph generation unit (30) generates the second graph data such that the first edge (e15) is connected to the first node (n15) and the second edge (e12) is connected to the second node (n16) in the second graph (G1').

Description

Information processing device and information processing method

This disclosure relates to an information processing device and an information processing method.

　A method has been disclosed in which graph data including multiple nodes and multiple edges connecting the nodes is acquired, and the graph is simplified based on the number of edges connected to the nodes (see Patent Document 1).

JP 2020-77299 A

Generally, when processing a graph, such as transforming, optimizing, or averaging adjacent nodes, if a node in the graph has multiple pieces of information corresponding to the multiple edges to which it is connected, there is a problem that some of the information contained in the graph may be lost, resulting in degradation of the information.

The present disclosure aims to solve the above problem by providing an information processing device and information processing method that can suppress degradation of graph information.

The information processing device according to the present disclosure includes a graph data acquisition unit that acquires first graph data indicating a first graph having an original node having first information and second information, a first edge associated with the first information and connected to the original node, and a second edge associated with the second information and connected to the original node, and a graph generation unit that generates second graph data indicating a second graph in which the original node has been replaced with a subgraph having a plurality of nodes in the first graph, including a first node corresponding to the first information and a second node corresponding to the second information, and edges connecting the plurality of nodes to each other, and the graph generation unit generates the second graph data such that in the second graph, the first edge is connected to the first node and the second edge is connected to the second node.

According to the present disclosure, when a node in a graph has multiple pieces of information, data is generated that shows a graph in which the node has been replaced with a subgraph having multiple nodes that correspond to the multiple pieces of information, thereby suppressing degradation of information when processing the graph.

1 is a block diagram showing a configuration of an information processing device according to a first embodiment. FIG. 2 is a block diagram showing an example of a hardware configuration of the information processing device according to the first embodiment. FIG. 2 is a block diagram showing an example of a hardware configuration of the information processing device according to the first embodiment. 4 is a flowchart showing a process performed by the information processing device according to the first embodiment. 4 is a flowchart showing an example of processing performed by the information processing device according to the first embodiment. FIG. 6A shows a first graph as an example of a graph network represented by first graph data acquired by an information processing device according to embodiment 1, and FIG. 6B shows a second graph as an example of a graph network represented by second graph data generated by an information processing device according to embodiment 1. 11 is a second graph as an example of a graph network represented by second graph data generated by the information processing device according to the first embodiment. 11 is a second graph as an example of a graph network represented by second graph data generated by the information processing device according to the first embodiment. FIG. 9A shows a first graph as an example of a graph network represented by first graph data acquired by an information processing device according to embodiment 1, and FIG. 9B shows a second graph as an example of a graph network represented by second graph data generated by an information processing device according to embodiment 1. 10A and 10B are diagrams showing a second graph as an example of a graph network represented by second graph data generated by an information processing device according to embodiment 1. FIG. 10C is a second graph as a modified example of the graph network of FIG. 10B shown by the second graph data generated by the information processing device according to the first embodiment. 9C is a second graph as a modified example of the graph network of FIG. 9B shown by second graph data generated by the information processing device according to embodiment 1. 9C is a second graph as a modified example of the graph network of FIG. 9B shown by second graph data generated by the information processing device according to embodiment 1. FIG. 14A shows a first graph as an example of a graph network represented by first graph data acquired by an information processing device according to embodiment 1, and FIG. 14B shows a second graph as an example of a graph network represented by second graph data generated by an information processing device according to embodiment 1. FIG. 15A shows a first graph as an example of a graph network represented by first graph data acquired by an information processing device according to embodiment 1, and FIG. 15B shows a second graph as an example of a graph network represented by second graph data generated by an information processing device according to embodiment 1. 11 is a flowchart showing an example of processing performed by an information processing device according to the second embodiment. FIG. 17A shows a first graph as an example of a graph network represented by first graph data acquired by an information processing device according to embodiment 2, and FIG. 17B shows a second graph as an example of a graph network represented by second graph data generated by an information processing device according to embodiment 2. FIG. 18A shows a first graph as an example of a graph network represented by first graph data acquired by an information processing device according to embodiment 2, and FIG. 18B shows a second graph as an example of a graph network represented by second graph data generated by an information processing device according to embodiment 2. FIG. 19A shows a first graph as an example of a graph network represented by first graph data acquired by an information processing device according to embodiment 2, and FIG. 19B shows a second graph as an example of a graph network represented by second graph data generated by an information processing device according to embodiment 2. 10 is a flowchart showing an example of processing performed by an information processing device according to a modification of the first embodiment. FIG. 21A is a first graph as an example of a graph network represented by first graph data acquired by an information processing device, and FIG. 21B is a second graph as an example of a graph network represented by second graph data generated by an information processing device. FIG. 22A is a first graph as an example of a graph network represented by first graph data acquired by an information processing device, and FIG. 22B is a second graph as an example of a graph network represented by second graph data generated by an information processing device. 13 is a flowchart showing a process performed by an information processing device according to a third embodiment. 24A is a circuit diagram shown by a netlist acquired by an information processing device according to embodiment 3, and FIG. 24B is a netlist acquired by the information processing device according to embodiment 3. FIG. A table showing the number of circuits, the average number of nodes, the average number of edges, and the average number of node types contained in the netlist used as the dataset. 26A is a circuit diagram showing an electrical circuit having a multi-element component, and FIG. 26B is a graph network showing the electrical circuit of FIG. 26A. Graph showing the inference accuracy when learning was performed under conditions where a multi-element component was not decomposed into virtual components and terminal components, and inference was performed using test data. A graph network in which all terminal components are connected using only terminal components without using virtual components in the electric circuit of FIG. 26A. 29 is a graph showing the inference accuracy of learning using the graph network in FIG. 28 and performing inference using test data. A graph network in which terminal components are connected via virtual components in the electric circuit of FIG. 26A. 31 is a graph showing the inference accuracy of learning using the graph network in FIG. 30 and performing inference using test data. FIG. 1 is a circuit diagram showing an example of a block diagram inside a semiconductor device. A graph network of multi-element components with edges added between terminal components. Graph networks that represent electrical circuits with multi-element components. 35A is a circuit diagram showing an electrical circuit having a multi-element component, and FIG. 35B is a graph network showing the electrical circuit of FIG. 35A. 31 is a graph showing the inference results for test data in a graph neural network in which the conditions and all other than the input data are the same as in FIG. 30 . Graph networks that represent electrical circuits with multi-element components. FIG. 13 is a schematic diagram in which node attribute information is assigned to each of a virtual node and a decomposition node. FIG. 13 is a schematic diagram in which node attribute information is assigned to each of a virtual node and a decomposition node, and shows an example in which the node attribute information is an average value of attribute information of connected decomposition nodes. FIG. 41A is a graph network showing a multi-element component with three terminals, and FIG. 41B is a schematic diagram in which unique numerical values are assigned to one or more pieces of node attribute information of virtual nodes and decomposition nodes based on domain information or terminal information. FIG. 13 is a schematic diagram showing that the number of elements of attribute information at a two-terminal decomposition point is equal. 11 is a schematic diagram showing how different values are assigned to the input side and the output side of at least one element of node attribute information at a two-terminal decomposition point. A schematic diagram showing how to equalize the number of elements in matrices that form the attribute information of nodes in a graph network.

Hereinafter, embodiments of the present disclosure will be described in detail with reference to the drawings.
Embodiment 1.
First, the configuration of an information processing device 100 according to the first embodiment will be described with reference to Fig. 1. Fig. 1 is a block diagram showing the configuration of the information processing device 100 according to the first embodiment. The information processing device 100 according to the first embodiment is a device that acquires graph data indicating a graph, and generates graph data indicating another graph based on the graph data. In other words, the information processing device 100 according to the first embodiment is a device that converts graph data indicating a graph into graph data indicating another graph. As shown in Fig. 1, the information processing device 100 includes a graph data acquisition unit 10, a node extraction unit 20, and a graph generation unit 30.

The graph data acquisition unit 10 acquires graph data indicating a graph network as a graph. For example, the graph data acquisition unit 10 acquires graph data from an input device (not shown) that accepts an input operation by an operator and inputs information to the information processing device 100, from an external device connected to the information processing device 100 so as to be able to communicate by wire or wirelessly, or by reading information stored in a storage unit (not shown) provided in the information processing device 100. In addition, for example, the graph data acquisition unit 10 acquires, as graph data, data sets such as geometric data, text data, and tabular data indicating graph networks consisting of nodes (points) and edges (lines), such as neural networks, molecular structures, electric circuits, social networks, and computer networks. Specifically, a graph network indicating an electric circuit may be a graph network in which components are indicated by nodes and wiring connecting the components is indicated by edges. As a graph network showing a social network, a graph network in which individuals are represented by nodes and relationships between individuals are represented by edges, or a graph network in which companies and users are represented by nodes and the products of specific companies are represented by edges, thereby associating companies and users with the products they use.

The node extraction unit 20 extracts specific nodes as original nodes that match a specific condition set in advance from among the nodes in the graph network represented by the graph data based on the graph data acquired by the graph data acquisition unit 10. For example, the node extraction unit 20 extracts specific nodes based on information held by the nodes in the graph network represented by the graph data. Also, for example, the node extraction unit 20 extracts specific nodes having a number of edges connected thereto that is within a specific range from among the nodes in the graph network represented by the graph data. Note that in the first embodiment, the graph data acquired by the graph data acquisition unit 10 is also referred to as first graph data, and the graph network represented by the first graph data is also referred to as the first graph. Details of specific nodes will be described later.

The graph generation unit 30 generates graph data indicating a new graph network based on the first graph data and information related to the nodes extracted by the node extraction unit 20. The graph generation unit 30 has a node decomposition unit 31 and an edge modification unit 32. Note that the information processing device 100 may have a display control unit (not shown) that displays the graph data generated by the graph generation unit 30 on a display device such as a liquid crystal panel, and may have an output unit (not shown) that outputs the graph data generated by the graph generation unit 30 to an external device.

The node decomposition unit 31 decomposes the node extracted by the node extraction unit 20 into multiple nodes. In other words, the node decomposition unit 31 generates multiple new nodes based on the node extracted by the node extraction unit 20, and deletes the specific node extracted by the node extraction unit 20.

The edge modification unit 32 modifies the edges of the graph network represented by the first graph data according to the result of the node decomposition by the node decomposition unit 31. For example, the edge modification unit 32 generates an edge that connects to the new node generated by the node decomposition unit 31, and deletes the node that is connected to the specific node extracted by the node extraction unit 20. For example, the edge modification unit 32 changes the connection destination of the edge so that the existing edge is connected to the new node generated by the node decomposition unit 31. In this way, the graph generation unit 30 generates graph data indicating a new graph network in which a subgraph having a plurality of new nodes and new edges connecting the plurality of new nodes to each other is replaced with the specific node extracted by the node extraction unit 20 in the first graph. Note that in the first embodiment, the new graph data generated by the graph generation unit 30 based on the first graph data is also referred to as second graph data, and the graph network represented by the second graph data is also referred to as the second graph. Details of the graph generation unit 30 will be described later.

Next, the hardware configuration of the information processing device 100 will be described with reference to Figs. 2 and 3. Fig. 2 is a block diagram showing an example of the hardware configuration of the information processing device 100 according to the first embodiment, and Fig. 3 is a block diagram showing an example of a hardware configuration of the information processing device 100 according to the first embodiment, which is different from that shown in Fig. 2. For example, as shown in Fig. 2, the information processing device 100 has a processor 100a, a memory 100b, and an I/O port 100c, and is configured so that the processor 100a reads and executes a program stored in the memory 100b. The memory 100b is composed of, for example, a non-volatile or volatile semiconductor memory such as a RAM, a ROM, a flash memory, an EPROM, an EEPROM, or a combination of these. The memory 100b may also be a magnetic disk, a flexible disk, an optical disk, a compact disk, a mini disk, a DVD, or the like. The memory 100b may also be an HDD or an SSD.

Also, for example, as shown in FIG. 3, the information processing device 100 has a processing circuit 100d, which is dedicated hardware, and an I/O port 100c. The processing circuit 100d is configured, for example, by a single circuit, a composite circuit, a programmed processor, a parallel programmed processor, a system LSI (Large-Scale Integration), an ASIC (Application Specific Integrated Circuit), an FPGA (Field Programmable Gate Array), or a combination of these. Each function of the information processing device 100 is realized by the processor 100a or the processing circuit 100d, which is dedicated hardware, executing a program that is software, firmware, or a combination of software and firmware.

Next, with reference to Figs. 4 to 15, the details of the process in which the information processing device 100 according to embodiment 1 generates second graph data based on the first graph data will be described. Fig. 4 is a flowchart showing the process performed by the information processing device 100 according to embodiment 1. As shown in Fig. 4, when the information processing device 100 starts the process, it acquires graph data (step ST11). For example, in this process, the information processing device 100 acquires graph data indicating a graph network having a plurality of nodes and a plurality of edges connecting these plurality of nodes to each other, by using the graph data acquisition unit 10.

After performing the process of step ST11, the information processing device 100 extracts specific nodes that meet a specific condition set in advance from among the nodes in the first graph shown by the first graph data acquired in the process of step ST11 (step ST12). For example, based on the first graph data acquired by the graph data acquisition unit 10, the information processing device 100 extracts, as specific nodes, nodes from the nodes in the first graph that have multiple pieces of information and are connected to edges associated with each of the multiple pieces of information, using the node extraction unit 20. In other words, in the process of step ST12, the information processing device 100 extracts, as specific nodes, from the first graph, nodes that have multiple pieces of information including the first information and the second information and are connected to multiple edges including a first edge associated with the first information and a second edge associated with the second information.

After performing the processing of step ST12, the information processing device 100 determines whether or not a specific node has been extracted from the first graph in the processing of step ST12 (step ST13). In other words, after performing the processing of step ST12, the information processing device 100 determines whether or not the first graph represented by the first graph data acquired in the processing of step ST11 has a specific node that meets a specific condition that has been set in advance.

If the first graph has a specific node (YES in step ST13), the information processing device 100 generates multiple new nodes based on the information held by any of the extracted specific nodes (step ST14). For example, if any of the extracted specific nodes has multiple pieces of information and is a node to which edges associated with each of the multiple pieces of information are connected, in this process, the information processing device 100 generates multiple new nodes including nodes corresponding to each piece of information held by the specific node by the node decomposition unit 31. In other words, if any of the extracted specific nodes has multiple pieces of information including first information and second information and is a node to which multiple edges including a first edge associated with the first information and a second edge associated with the second information are connected, in this process, the information processing device 100 generates multiple new nodes including a second node corresponding to the first information and a third node corresponding to the second information by the node decomposition unit 31.

After performing the processing of step ST14, the information processing device 100 connects edges to the new multiple nodes generated in the processing of step ST14 (step ST15). For example, in this processing, the information processing device 100 generates a new edge by the edge modification unit 32 and connects between the new multiple nodes generated in the processing of step ST14. Also, for example, in this processing, the information processing device 100 generates a new edge by the edge modification unit 32 and connects a node that was connected via an edge to the specific node extracted in the processing of step ST12 to one of the new multiple nodes generated. Specifically, if any of the extracted specific nodes has multiple pieces of information including the first information and the second information, and is a node to which multiple edges including a first edge associated with the first information and a second edge associated with the second information are connected, in this process, the information processing device 100 generates multiple edges including a new edge having one end connected to the same as the first edge and the other end connected to the first node corresponding to the first information, and a new edge having one end connected to the same as the second edge and the other end connected to the second node corresponding to the second information.

After performing the processing of step ST15, the information processing device 100 deletes unnecessary edges (step ST16). For example, in this processing, the information processing device 100 deletes edges that have become unnecessary as a result of generating multiple nodes in the processing of step ST15. Specifically, in this processing, the information processing device 100 deletes edges that are connected to the specific node extracted in the processing of step ST12.

After performing the processing of step ST16, the information processing device 100 deletes the specific node extracted in the processing of step ST12 (step ST17). As a result, second graph data is generated that indicates a new second graph in which a subgraph having a plurality of new nodes and new edges connecting the plurality of new nodes to each other in the first graph is replaced with the specific node extracted by the node extraction unit 20.

If the processing of step ST17 has been performed, or if the first graph represented by the first graph data does not have a specific node (NO in step ST13), the information processing device 100 ends the processing. Note that if the first graph has multiple specific nodes, the information processing device 100 may be configured to perform the processing of steps ST14 to ST17 for each specific node, or may be configured to perform the processing of steps ST14 to ST17 for multiple specific nodes in parallel.

Next, a specific example of the processing performed by the information processing device 100 according to the first embodiment will be described. FIG. 5 is a flowchart showing an example of the processing performed by the information processing device according to the first embodiment. For example, the information processing device 100 extracts, as specific nodes, nodes to which three or more edges are connected from the first graph represented by the first graph data acquired in the processing of step ST11 (step ST22).

FIG. 6A shows a first graph G1 as an example of a graph network represented by the first graph data acquired by the information processing device 100 according to the first embodiment. For example, if node n13 represents a company, and nodes n11, n12, and n14 represent users, in a graph network showing that a connection is formed between a company and a plurality of users, nodes representing a plurality of users are connected to node n13 representing the company via edges. Note that the first graph G1 shown in FIG. 6A may be the entire graph network represented by the graph data acquired by the graph data acquisition unit 10, or may be a part of the graph network represented by the graph data acquired by the graph data acquisition unit 10.

For example, if the first graph data indicating the first graph G1 shown in FIG. 6A is acquired in the processing of step ST11, then in the processing of step ST22, the information processing device 100 extracts node n13, to which three edges, edge e11, edge e12, and edge e13, are connected, as a specific node.

After performing the processing of step ST22, the information processing device 100 determines whether or not a specific node has been extracted from the first graph G1 in the processing of step ST22 (step ST23). In other words, after performing the processing of step ST22, the information processing device 100 determines whether or not the first graph represented by the first graph data acquired in the processing of step ST12 has a specific node to which three or more edges are connected.

If the first graph G1 has a specific node (YES in step ST23), the information processing device 100 generates a virtual node and a plurality of decomposition nodes as a plurality of new nodes based on the information of any of the extracted specific nodes (step ST24). For example, in the process of step ST22, if node n13 is extracted as a specific node, the information processing device 100 generates new nodes including a plurality of decomposition nodes corresponding to each of the plurality of pieces of information held by node n13 and a virtual node as a connection node for connecting these plurality of decomposition nodes to each other by the node decomposition unit 31. In other words, in the process of step ST22, if node n13 having first information and second information is extracted as a specific node, the information processing device 100 generates new nodes including a plurality of decomposition nodes including a decomposition node corresponding to the first information and a decomposition node corresponding to the second information and a virtual node for connecting these plurality of decomposition nodes to each other by the node decomposition unit 31.

6B is a second graph as an example of a graph network shown by the second graph data generated by the information processing device according to the first embodiment. As shown in FIG. 6B, for example, in the process of step ST22, when node n13 having first information corresponding to edge e11, second information corresponding to edge e12, and third information corresponding to edge e13 is extracted as a specific node, the information processing device 100 generates new nodes including node n15, which is a decomposition node corresponding to the first information held by node n13, node n16, which is a decomposition node corresponding to the second information, and node n17, which is a decomposition node corresponding to the third information, and node n18, which is a virtual node for connecting these multiple decomposition nodes to each other, by the node decomposition unit 31. For example, the multiple pieces of information held by the specific node may be information indicating which edge the specific node is connected to, or information indicating which node the specific node is connected to via a specific edge, or, if the first graph is a graph network indicating an electric circuit and the specific node is a node indicating a component of the electric circuit having multiple terminals, may be information for identifying the terminals, or may be information indicating the weight of the connection between the specific node and another node connected via an edge.

After performing the processing of step ST24, the information processing device 100 connects edges to the new multiple nodes generated in the processing of step ST24 (step ST25). For example, in this processing, the information processing device 100 generates new edges by the edge changing unit 32, and connects between the multiple decomposition nodes generated in the processing of step ST24 and the virtual node. Also, for example, in this processing, the information processing device 100 connects nodes n11, n12, and n14, which were connected via edges to node n13 extracted in the processing of step ST22, to any of the multiple decomposition nodes generated.

As shown in FIG. 6B, specifically, in this process, the information processing device 100 uses the edge change unit 32 to generate a new edge e15 to connect node n18 and node n15, generate an edge e16 to connect node n18 and node n16, and generate an edge e17 to connect node n18 and node n17. Also, in this process, the information processing device 100 connects node n15 and node n11 with edge e11, connects node n16 and node n12 with edge e12, and connects node n17 and node n14 with edge e13.

For example, in the relationship between a company and a user, generally, individual users who are stakeholders focus on aspects (domains) such as products and sales as multiple pieces of information that a company possesses. For example, if the first graph G1 is a graph network representing a social network with companies and users as nodes, and three users are connected to the node representing the company via three edges, in the processing of step ST24, the information processing device 100 generates node n18, which is a virtual node that abstractly represents the company, and generates nodes n15, n16, and n17, which are decomposition nodes that decompose the company into each domain, which is multiple pieces of information that the company possesses, and in the processing of step ST25, connects node n18 to node n15, node n16, and node n17, and connects each user that was connected to node n13 in the first graph G1 to node n18, node n15, and node n16 via edges.

In addition, the information processing device 100 may be configured to generate the edge connecting node n15 and node n11, the edge connecting node n16 and node n12, and the edge connecting node n17 and node n14 separately from edges e11, e12, and e13. When configured in this way, when the information processing device 100 performs the processing of step ST25, it deletes the edge connecting node n11 and node n13, the edge connecting node n12 and node n13, and the edge connecting node n14 and node n13 in the first graph G1 as unnecessary edges (step ST26).

After performing the process of step ST26, the information processing device 100 deletes node n13, which is a specific node (step ST17). As a result, second graph data is generated that indicates a second graph G1' in which node n13 is replaced with a subgraph g1' having a plurality of nodes including nodes n15, n16, n17, and n18 in the first graph G1, and edges e15, e16, and e17 that connect these plurality of nodes to each other. For example, in a first graph G1 that indicates a social network in which nodes are companies and users, a graph network is generated in which node n13 indicating a company is replaced with a subgraph g1' that is decomposed for each domain (field) that the company has. For example, nodes n15, n16, and n17 indicate product 1, product 2, and product 3 of the company indicated by node n13, respectively.

Note that the second graph shown by the second graph data generated based on the first graph data showing the first graph in FIG. 6A is not limited to that in FIG. 6B. For example, the number of new nodes generated based on the information held by a specific node may be one, or any number equal to or greater than two, and may be the same as or different from the number of edges connected to the specific node. In addition, the edges connected to the new nodes may be edges connecting multiple decomposition nodes, or edges connecting one decomposition node to multiple nodes.

Next, another example of the second graph shown in FIG. 6B will be described with reference to FIG. 7 and FIG. 8. FIG. 7 shows a second graph G1'' as an example different from FIG. 6B of a graph network represented by second graph data generated by the information processing device 100 according to embodiment 1.

7, in the subgraph g1'' of the second graph G1'', node n15, which is a decomposition node generated based on node n13, which is a specific node (see FIG. 6A), and node n18, which is a virtual node, are connected by edge e15, node n16, which is a decomposition node, and node n18 are connected by edge e16, node n17, which is a decomposition node, and node n18 are connected by edge e17, and node n15 and node n16 are connected by edge e19. Furthermore, node n15 is connected to node n11 by edge e11 and is connected to node n12 by edge e18. Furthermore, node n12 is connected to node n15 by edge e18 and is connected to node n16 by edge e12. In this way, in the second graph G1'', one decomposition node may be connected to multiple existing nodes, or a specific existing node may be connected to multiple decomposition nodes. For example, if the second graph G1'' is a graph network representing a social network, one decomposition node may be connected to multiple users, or a node representing a specific user may be connected to multiple decomposition nodes.

The first and second graphs are not limited to the relationship between one company and multiple users, but may be graph networks showing the relationship between multiple companies and multiple users. In such cases, the multiple companies may be connected to each other by edges. In such relationships between companies, decomposition nodes and multiple edges can be set between them. For example, even if one user and one domain of a specific company are connected multiple times in the first and second graphs, these multiple connections may be aggregated as one connection if they can be considered as similar information. For example, if one user and one domain of a specific company are connected multiple times in the first and second graphs, these multiple connections may not be considered as similar information, by subdividing the domains as different domains, the occurrence of multiple edges can be suppressed even in various graph networks.

In addition, in the first embodiment, the first graph and the second graph may be static graph networks, or may be dynamic graph networks in which the nodes of the graph network and the connections between the nodes change over time, such as SNS (Social Networking Service) or traffic information. When the first graph and the second graph are dynamic graph networks, even if one user and one domain of a specific company are connected multiple times, there is only one connection in the time direction, and these connections do not become multiple edges. Furthermore, the second graph may be a graph network in which multiple similar decomposition nodes are combined into one decomposition node so as to prevent self-loops and multiple edges from occurring, and multiple users are connected to one decomposition node. By forming the second graph in this way, it is possible to suppress the occurrence of multiple edges and self-loops that cause information degradation, and reduce the processing time in a graph neural network, etc.

FIG. 8 shows a second graph G1''' as an example of a graph network shown by second graph data generated by the information processing device 100 according to embodiment 1, different from those shown in FIGS. 6B and 7. As shown in FIG. 8, in the subgraph g1''' of the second graph G1''', node n15, which is a decomposition node generated based on node n13, which is a specific node (see FIG. 6A), and node n18, which is a virtual node, are connected by edge e15, and node n17, which is a decomposition node, and node n18 are connected by edge e17. In addition, node n15 is connected to node n11 by edge e11, and is connected to node n12 by edge e12. In this way, one decomposition node may be connected to multiple users in the second graph G1'''.

Below, we will explain the case where the first graph is a graph network showing the citation relationships between papers and books. Generally, papers are written to specialize in a particular technology, whereas a book may systematically compile multiple papers and cite multiple papers. In the first graph, by showing papers or books as nodes and showing that a paper or book is cited as an edge, it becomes possible to show the citation relationships between papers and books.

For example, in the second graph G1''' shown in FIG. 8, by connecting node n18, which is a virtual node indicating a book, with nodes n15 and n17, which are decomposition nodes generated according to the chapters of the book, which are the multiple pieces of information (domains) that a book has, with edges, the citation relationships between papers and books divided by domain can be represented in a graph network. Therefore, the second graph G1''' shown in FIG. 8 indicates that both the paper indicated by node n11 and the paper indicated by node n12 cite a specific chapter (e.g., chapter 4) indicated by node n15 of the book indicated by node n18, and that the paper indicated by node n14 cites another chapter indicated by node n17.

In addition, in a graph network showing the citation relationships between papers and books, the domain of a book is not limited to a chapter, but may be, for example, a section or an article. In this way, even if a self-loop and multiple edges occur in the first graph, a graph network without self-loops and multiple edges can be generated by subdividing the node representing the book in the second graph according to the book's domain and providing one or more book decomposition nodes for each paper.

The extent to which the nodes are decomposed is set appropriately based on the content of the process (graph network processing, graph neural network processing, etc.), the type of graph network, the content of the graph data (dataset) to be acquired, etc. For example, in a dataset for generating a learning model that predicts the citation relationship between a paper and a corresponding part of a book using a graph neural network, it is desirable to decompose the nodes finely, but in a process for simply finding the relationship between citations and cited, it may not be necessary to decompose the nodes finely. Also, if the amount of information contained in the dataset is limited, and if it is difficult to obtain additional information in such a case, it is desirable to decompose the node into decomposition nodes with the same number of edges connected to the node, without decomposing it beyond the information contained in the dataset.

In conventional graph networks, information from multiple domains is consolidated into a single node, so the relationship between the domain of the node and surrounding nodes cannot be maintained as a graph network, or becomes unclear, which causes information degradation. In contrast, the information processing device 100 according to embodiment 1 generates one decomposition node for each edge connected to a specific node, so relationships with surrounding nodes can be maintained separately for each domain. The information processing device 100 according to embodiment 1 maintains multiple pieces of information held by a specific node as information for multiple decomposition nodes, so domain information is not lost even when graph processing is performed, and information degradation can be suppressed.

In the graph network according to the first embodiment, a self-loop can be considered to represent a relationship between domains. In contrast to this, in conventional graph networks, a self-loop means a connection from all domains to all domains that a node has, and cannot have information on a connection from a specific domain to a specific domain as in the first embodiment. On the other hand, in the first embodiment, a self-loop can be represented by information that connects one end and the other end of an edge between different decomposition nodes generated based on one specific node, so that it is possible to hold the relationship between domains as a graph network. Also, in the first embodiment, the graph network can be structured to have no self-loop, so that it is possible to hold the connection information from a specific domain to another domain that a node has as a graph network.

Multiple edges in a graph network mean that two nodes are connected by two or more edges, but in the first embodiment, a specific node is decomposed into decomposition nodes with the same number as the edges connected to it, so that the graph network can have a graph structure that does not have multiple edges. For example, in the past, when a graph network has a first specific node and a second specific node, the first specific node has domain A and domain C, and the second specific node has domain B and domain D, and there are connections between domain A and domain B and domain C and domain D as multiple edges, it was necessary to aggregate the information connecting the first specific node and the second specific node. On the other hand, in the first embodiment, domain A and domain B, and domain C and domain D are represented as decomposition nodes, so that each connection can be represented by a graph structure. This makes it possible to suppress the information degradation that occurred in the past.

As another method for suppressing such information degradation, the occurrence of self-loops and multiple edges can also be suppressed by forming a complete graph in which all decomposition nodes are connected to each other by edges without using virtual nodes. However, a self-loop in a single node is converted to multiple edges after converting a single node into a complete graph, resulting in information degradation. Furthermore, since the relationship between decomposition nodes is a black box, a complete graph is required to maintain the relationship between the decomposition nodes. However, since the number of edges when forming a complete graph is proportional to the square of the number of decomposition nodes, the number of edges increases as the number of decomposition nodes increases, and the amount of calculation increases exponentially. For example, even for a node with a relatively small number of connected edges of 1,000, 49,950 edges between decomposition nodes are required. In contrast, in the first embodiment, a virtual node is provided and a structure is created in which multiple decomposition nodes are connected via the virtual node, so that the edges between decomposition nodes can be expressed with 1,000 edges, the same as the number of decomposition nodes. This allows for a significant reduction in calculation cost, calculation time, and memory, making it possible to process a large-scale graph network having multiple nodes that was previously difficult to calculate. By using virtual nodes and decomposition nodes, a self-loop at a single node is equivalent to connecting the decomposition nodes with an edge, so there are no multiple edges as in a complete graph, and no information degradation occurs.

The graph generation unit 30 is not limited to generating the above-mentioned second graph based on the first graph data acquired by the graph data acquisition unit 10. The graph generation unit 30 may generate second graph data indicating a second graph in which a specific node as an original node is replaced with a subgraph having a plurality of nodes including a first node corresponding to the first information and a second node corresponding to the second information based on the first graph acquired by the graph data acquisition unit 10, and may generate the second graph data so that the first edge is connected to the first node and the second edge is connected to the second node in the second graph. Other examples of second graphs generated by the graph generation unit 30 based on the first graph data acquired by the graph data acquisition unit 10 are shown below.

FIG. 9A shows a first graph G0 as an example of a graph network represented by the first graph data acquired by the information processing device 100 according to embodiment 1. Note that the first graph G0 shown in FIG. 9A may be the entire graph network represented by the graph data acquired by the graph data acquisition unit 10, or may be a part of the graph network represented by the graph data acquired by the graph data acquisition unit 10.

9A, when the graph data acquisition unit 10 acquires first graph data indicating a first graph G0 having a node n10 as a specific node having the first information and the second information, an edge e11 as a first edge associated with the first information and connected to the node n10, and an edge e12 as a second edge associated with the second information and connected to the node n10, the graph generation unit 30 generates second graph data indicating a second graph G0' in which the node n10 has been replaced with a subgraph g0' including a node n15 as a first node corresponding to the first information and a node n16 as a second node corresponding to the second information. At this time, the graph generation unit 30 generates the second graph data so that the edge e11 is connected to the node n15 and the edge e12 is connected to the node n16 in the second graph G0'.

10A and 10B show a second graph as another example of a graph network represented by the second graph data generated by the information processing device 100 according to the first embodiment. The graph generating unit 30 may generate the second graph data such that in the second graph, the first edge is divided into a first-1 edge and a first-2 edge, one end of the first-1 edge is connected to the first node, and one end of the first-2 edge is connected to the second node.

For example, when the graph data acquisition unit 10 acquires the first graph data showing the first graph G0 in FIG. 9A, the graph generation unit 30 may generate second graph data showing the second graph G0' shown in FIG. 10A, or may generate second graph data showing the second graph G0'' shown in FIG. 10B. The second graph G0'' is a graph in which the edge e11 in the first graph G0 is divided into edge e11-1 as the 1-1 edge and edge e11-2 as the 1-2 edge, one end of edge e11-1 is connected to node n15 as the first node, and one end of edge e11-2 is connected to node n16 as the second node.

FIG. 11 shows a second graph as a modified example of the graph network of FIG. 10B, which is shown by the second graph data generated by the information processing device 100 according to the first embodiment. For example, one or both of the edges e11-1 and e11-2 in the second graph G0'' may be edges having directionality. Specifically, when the graph data acquisition unit 10 acquires the first graph data showing the first graph G0 of FIG. 9A, the graph generation unit 30 may generate second graph data showing the second graph G0'' in which the edge e11-2 is an edge having directionality, as shown in FIG. 11.

FIG. 12 is a diagram showing another example in which the first node and the second node are connected by a new edge in the second graph, and is a second graph as a modified example of the graph network in FIG. 9B shown by the second graph data generated by the information processing device 100 according to the first embodiment. For example, when the graph data acquisition unit 10 acquires the first graph data showing the first graph G0 in FIG. 9A, the graph generation unit 30 generates the second graph data so that the second graph G0''' is a graph having a new edge e10 with one end connected to node n15 as the first node and the other end connected to n16 as the second node, as shown in FIG. 12.

FIG. 13 is a diagram showing another example in which the first node and the second node are connected by a new edge and a new node in the second graph, and is a second graph as a modified example of the graph network in FIG. 9B shown by the second graph data generated by the information processing device 100 according to the first embodiment. For example, when the first graph data showing the first graph G0 in FIG. 9A is acquired by the graph data acquisition unit 10, the graph generation unit 30 generates the second graph data so that the second graph G0'''' has node n18 as a connecting node for connecting node n15 and node n16, as shown in FIG. 13.

14A and 14B are diagrams showing another example in which a specific node as an original node has first information, second information, and third information, in which FIG. 14A is a first graph as an example of a graph network shown by first graph data acquired by information processing device 100 according to embodiment 1, and FIG. 14B is a second graph as an example of a graph network shown by second graph data generated by information processing device 100 according to embodiment 1. When first graph data showing a first graph having an original node having N pieces of information, where N is a natural number equal to or greater than 2, is acquired by graph data acquisition unit 10, graph generation unit 30 generates second graph data showing a second graph in which the original node in the first graph is replaced with a subgraph having N nodes different from each other and associated with each of the N pieces of information.

Specifically, as shown in FIG. 14A, when the graph data acquisition unit 10 acquires first graph data indicating a first graph G9 having a node n13 as a specific node having the first information, the second information, and the third information, an edge e11 as a first edge associated with the first information and connected to the node n13, and an edge e12 as a second edge associated with the second information and connected to the node n13, the graph generation unit 30 generates second graph data indicating a second graph G9' in which the node n13 has been replaced with a subgraph g9' including a node n15 as a first node corresponding to the first information, a node n16 as a second node corresponding to the second information, and a node n17 as a third node corresponding to the third information. At this time, the graph generation unit 30 generates the second graph data so that the edge e11 is connected to the node n15 and the edge e12 is connected to the node n16 in the second graph G9'.

15A and 15B are diagrams showing another example in which a specific node as an original node has first information, second information, and third information, in which Fig. 15A is a first graph as an example of a graph network shown by first graph data acquired by information processing device 100 according to embodiment 1, and Fig. 15B is a second graph as an example of a graph network shown by second graph data generated by information processing device 100 according to embodiment 1. For example, when first graph data showing a first graph having an original node connected to N edges, where N is a natural number equal to or greater than 2, is acquired by graph data acquisition unit 10, graph generation unit 30 generates second graph data showing a second graph in which the original node in the first graph has been replaced with a subgraph having N nodes different from each other corresponding to each of the N edges. In addition, when the graph data acquisition unit 10 acquires first graph data indicating a first graph having an original node connected to N edges, where N is a natural number equal to or greater than two, the graph generation unit 30 may be configured to generate second graph data indicating a second graph in which the original node in the first graph has been replaced with a subgraph having N nodes that are different from each other and correspond to each of the N or fewer edges.

Specifically, as shown in FIG. 15A, when first graph data indicating a first graph G1 having node n13 as a specific node having first information, second information, and third information by the graph data acquisition unit 10, edge e11 as a first edge associated with the first information and connected to node n13, edge e12 as a second edge associated with the second information and connected to node n13, and edge e13 as a third edge associated with the third information and connected to node n13, the graph generation unit 30 generates second graph data indicating a second graph G1'''' in which node n13 has been replaced with a subgraph g1'''' including node n15 as a first node corresponding to the first information, node n16 as a second node corresponding to the second information, and node n17 as a third node corresponding to the third information. At this time, the graph generation unit 30 generates the second graph data so that in the second graph G9', edge e11 is connected to node n15, edge e12 is connected to node n16, and edge e13 is connected to node n17.

Below, a specific example of the process performed by the information processing device 100 according to the embodiment 1 will be given. In the embodiment 1, for example, the information constituting the graph network can be written as text data as follows.

Node 1; Edge 1, Edge 2, Edge 3
Node 2; Edge 3, Edge 4

From this information, it is known that three edges are connected to node 1, and two edges are connected to node 2. It is also known that node 1 and node 2 are connected by edge 3.

Furthermore, the information processing device 100 according to the first embodiment defines, for example, one or more new virtual nodes for node 1 to which three edges are connected, and defines new decomposition nodes in the same number as the number of edges connected to node 1. Therefore, the above text data becomes as follows.

Node 1; Edge 1, Edge 2, Edge 3
Node 2; Edge 3, Edge 4
Virtual node 1-1;
Decomposition node 1-1;
Decomposition node 1-2;
Decomposition nodes 1-3;

In this case, the naming of the virtual nodes and decomposition nodes can be freely determined as long as they are different from the names of other nodes in the graph network. In the above, they are named virtual node 1-1, decomposition node 1-1, decomposition node 1-2, and decomposition node 1-3.

Next, the information processing device 100 connects the edges connected to the specific node to each of the decomposition nodes. As a result, the above text data becomes as follows.

Node 1; Edge 1, Edge 2, Edge 3
Node 2; Edge 3, Edge 4
Virtual node 1-1;
Decomposition node 1-1; edge 1
Decomposition node 1-2; edge 2
Decomposition node 1-3; edge 3

Furthermore, the information processing apparatus 100 defines new edges (edge 1-1, edge 1-2, edge 1-3) that connect the decomposition nodes and the virtual nodes. As a result, the above text data becomes as follows.

Node 1; Edge 1, Edge 2, Edge 3
Node 2; Edge 3, Edge 4
Virtual node 1-1; Edge 1-1, Edge 1-2, Edge 1-3
Decomposition node 1-1; edge 1, edge 1-1
Decomposition node 1-2; edge 2, edge 1-2
Decomposition node 1-3; edge 3, edge 1-3

From this connection information, the information processing device 100 removes connections between edges and specific nodes to which three or more edges are connected. As a result, the above text data becomes as follows.

Node 1;
Node 2; Edge 3, Edge 4
Virtual node 1-1; Edge 1-1, Edge 1-2, Edge 1-3
Decomposition node 1-1; edge 1, edge 1-1
Decomposition node 1-2; edge 2, edge 1-2
Decomposition node 1-3; edge 3, edge 1-3

Furthermore, the information processing device 100 removes a specific node to which three or more unnecessary edges are connected. As a result, the above text data becomes as follows.

Node 2; Edge 3, Edge 4
Virtual node 1-1; Edge 1-1, Edge 1-2, Edge 1-3
Decomposition node 1-1; edge 1, edge 1-1
Decomposition node 1-2; edge 2, edge 1-2
Decomposition node 1-3; edge 3, edge 1-3

By the above processing, the information of the specific node to which the three edges were connected is transferred to the virtual node, decomposition node 1-1, decomposition node 1-2, and decomposition node 1-3, and the processing related to the first embodiment is completed. This processing makes it possible to convert the specific node into a node that does not have multiple edges, which are the main cause of information degradation, between two nodes, and a self-loop that starts at one node and ends at the same node without passing through other nodes. In particular, multiple edges and self-loops cause information degradation when learning and inferring with a graph neural network, which is a method of deep learning.

This is because in graph neural network processing, each node forms a self-loop even for nodes that do not have a self-loop in order to propagate the node attributes that indicate the characteristics of its own node to the next hidden layer. As a result, the information of the self-loop that existed in the graph network does not remain, or the amount of information contained in the self-loop in the graph network decreases (the amount of information decreases relatively because the presence or absence of a self-loop is greater than the difference between one or two self-loops). Also, for multiple edges, the graph neural network sets up an activation function that is sensitive to real numbers between 0 and 1 or -1 and 1 after setting up a weight matrix, so while the difference between 0 with no edge and 1 with an edge is 1, the difference in the output of the activation function for one edge and two edges that are multiple edges will be small, for example, 0 and 0.1.

To be more specific about processing in a graph neural network, an adjacency matrix is used for the input as a method of representing a graph network. An adjacency matrix is expressed as a square matrix with the same number of rows and columns as the number of nodes, and a node ID is assigned to each column and row. In an adjacency matrix, elements where connected nodes and node IDs intersect are expressed as 1, and elements between nodes with no connection are expressed as 0. For this reason, an adjacency matrix with no self-loops has diagonal elements of 0. Also, in the case of multiple edges, the elements between nodes can be 2 or 3 depending on the number of multiple edges.

However, in many graph neural network algorithms, the attribute information between adjacent nodes is combined (embedding or contraction) based only on the presence or absence of connections, making it difficult to take the number of connections into account. For this reason, for example, when the number of connections is 2, the node attribute information of the multiple edges is not weighted twice and embedded in the adjacent node, but the weighting of the node attribute information between adjacent nodes is determined by the weight matrix obtained by learning. Technically, it is possible to arbitrarily strengthen the bonds of multiple edges with a connection number of 2, for example by making them twice as strong, but this is not desirable as it introduces human preconceptions. For example, when considering a molecular structure as a graph network, with carbon and hydrogen as nodes and bonds between each atom as edges, when comparing ethane with a single bond, ethylene with a double bond, and acetylene with a triple bond, molecules with double and triple bonds can be considered as molecules with multiple edges.

In this case, it is also clear that the bond energies of ethane, ethylene, and acetylene are 331 kJ/mol, 591 kJ/mol, and 827 kJ/mol, respectively, and do not double or triple depending on the number of bonds. For this reason, even in the case of multiple edges, the bond strength must be acquired by learning using a data set. With conventional methods, it was difficult to have multiple edges, but with the first embodiment, multiple edges can be expressed as a simple graph without using multiple edges.

In addition, regarding self-loops, graph neural networks update node attribute information between adjacent nodes using a weighted average, but in doing so, it is necessary to propagate the attribute value of the node itself to the next hidden layer. For this type of processing, self-loops must be created for all nodes, and self-loops are also formed during processing for nodes that do not have self-loops. In other words, two or more self-loops are formed for nodes that already have self-loops, but just as with multiple edges, there is no technical basis for arbitrarily doubling or more the element of a node's attributes even if the number of self-loops becomes two or more, so it is difficult for a graph neural network to process information from a graph network with self-loops without information degradation.

In particular, when there is one hidden layer, it is relatively easy to apply special processing to self-loops and multiple edges to make information degradation less likely to occur, but when there are two or more hidden layers, the number of combinations with adjacent nodes increases and the results of special processing are averaged out, making special processing difficult and making it hard to prevent information degradation. In this way, self-loops and multiple edges cause information degradation in graph neural networks. For the above reasons, the method shown in embodiment 1, in which self-loops and multiple edges are decomposed into virtual nodes and decomposed nodes before being made into an adjacency matrix, has a remarkable effect of making information degradation less likely to occur in graph networks and graph processing including graph neural networks.

In addition to the above molecular structure examples, the following data can be considered as data that can be expressed as a graph network.
・Social Networks
・Citation of papers (Citation Networks)
- Hyperlink relationships between Web pages (Web Networks)
・Relationship between products and buyers (Online Review Networks)
・Road Networks, Traffic Networks
・Knowledge Graph

In addition, examples of electrical engineering data that can be expressed as graph networks include: Electrical circuits Model-based development Physical simulations using mesh structures such as finite element methods and finite difference methods

For example, in a social network, if users are nodes and connections between users are edges, node attribute information can be considered as user information such as name, gender, and nationality. In the case of citing papers, if papers are nodes and citing and cited papers are edges, node attribute information can be considered as the contents and keywords of each paper. In the case of web pages, if homepages are nodes and hyperlinks between homepages are edges, node attribute information is the contents and update information of the web pages. In the case of the relationship between products and purchasers, if products and purchasers are nodes and the relationship between products and purchasers is edges, nodes are product information and user purchase history. In a transportation network, if intersections are nodes and roads between intersections are edges, node attribute information is the waiting time and traffic volume at the intersection. In a knowledge graph, if proper nouns are nodes and connections between proper nouns are edges, node attribute information is keywords. In a circuit, if circuit components are nodes and wiring between circuit components is edges, node attribute information is the model number and circuit constants of the circuit components. In model-based development, if each development block is considered a node and the flows connecting each development block are considered edges, then the node attribute information represents the progress and physical properties of each development block. In physical simulations using mesh structures, if the vertices of the mesh are considered nodes and the connections between the vertices are considered edges, then the node attribute information represents the coordinates of the vertices and material constants.

In addition, because graph networks enable processing in non-Euclidean space, it is possible to represent all processing of Euclidean space information, such as images, voice, and natural language, which are subsets of non-Euclidean space, as graph networks. For this reason, processing to convert this data into a graph network may be added, and the method shown in embodiment 1 may be applied. For example, in voice and natural language, it is possible to calculate that one word is closely related to other words by using techniques such as Attention and Transformer. With these techniques, when one word is related to three or more words, the method shown in embodiment 1 can be used.

In the first embodiment, various elements can be represented by nodes, not limited to the above examples, as long as they can be defined as nouns. Furthermore, in a graph network having two or more nodes, if there is a relationship between these nodes, the relationship can be represented by an edge. In particular, if there is a unidirectional relationship between two nodes, such as the relationship between citing and being cited of a paper, the edge may be defined as a directed graph, giving direction to the edge.

In addition, the graph network in the first embodiment is assumed to be an adjacency matrix or text information, specifically, a relational database or JSON (JavaScript Object Notation), XML, a table format, etc., but any format may be used as long as it can be expressed as a graph network regardless of human readability, such as a unique storage format (binary data) specific to a language such as Matlab or Python. In addition, they are stored as a database in a storage medium such as a USB memory, a hard disk, or an SSD, and are read into a memory on a DRAM or a GPU (graphics memory (VRAM)) during processing, and are converted into a graph network and processed by a processing device such as a CPU, a GPU, an ASIC, or an FPGA. In addition, the processing results are stored in a memory and output by saving as a database, visually displaying a graph network or output results so that a person can understand, or sending them to another information processing device. Since these data saving methods are in a reversible conversion relationship with each other, in the first embodiment, it is assumed that the data is saved as text, with emphasis on readability. For example, a graph network can be expressed as follows using text data with nodes as the basis:

Node 1; Edge 1, Edge 2
Node 2; Edge 1, Edge 3

Graph networks can also be written in terms of edges as follows:

Edge 1; Node 1, Node 2
Edge 2; Node 1
Edge 3; Node 2

Since these are mutually reversible, in the first embodiment, they are represented based on nodes, which are easy to understand. Note that nodes and edges are represented by separating them with a ";", but any other specified notation method, such as spaces or other characters, can be used.

In addition, the information processing device 100 according to the first embodiment extracts nodes to which three or more edges are connected and performs processing to decompose the nodes, but may be configured not to perform processing to decompose nodes to which two or fewer edges are connected, or may be configured to perform processing to decompose nodes in the same way as nodes to which three or more edges are connected.

Furthermore, it is desirable to provide one or more virtual nodes. For example, in a graph neural network, by increasing the number of virtual nodes, the weight matrix is generated by random numbers, and it is possible to show the characteristics of each virtual node, so that the expressive power of the graph network can be improved. On the other hand, since the number of edges increases as the number of virtual nodes increases, and the amount of calculation of the information processing device 100 increases, in many cases, it is desirable that the information processing device 100 is configured to generate three or less virtual nodes. For example, if 10 edges are connected to one specific node and the specific node is decomposed into 10 decomposition nodes, 10 edges are required when there is one virtual node, 20 edges are required when there are two virtual nodes, and 30 edges are required when there are three virtual nodes. Furthermore, when there are four virtual nodes, 40 edges are required, which is about the same as 45 edges (the number of combinations in which 2 are selected from 10) when no virtual nodes are used. Furthermore, considering the amount of calculation due to an increase in four virtual nodes, in the above example, the amount of calculation is about the same when four virtual nodes are used and when no virtual nodes are used, and the effect of using virtual nodes is reduced. Therefore, to take advantage of the feature that virtual nodes can achieve by reducing the amount of calculations and memory usage, there is an upper limit to the number of virtual nodes that can be used for one node.

In general, if the number of edges connected to a specific node is N and the number of virtual nodes is K, then it is desirable to set K so that N x (N-1)/2 >> K x N + K x (K-1)/2. It is also desirable that ">>" is 10 times or more. However, if the number of nodes is four or less, it is acceptable to have one virtual node, although it cannot be 10 times or more. This formula means that the number of N x (N-1)/2 edges decomposed without using virtual nodes is sufficiently smaller than the K x N connections between virtual nodes and decomposition nodes and the K x (K-1)/2 connections between virtual nodes. For example, if there are 100 decomposition nodes, then 4550 >> 100 x K + K x (K-1)/2. If ">>" is 10 times, then 100 x K + K x (K-1)/2 is 406 when K is 4, and 510 when K is 5, so K can be selected up to 4. However, in a connected graph, the amount of calculation increases exponentially as K increases, so it is desirable to make K as small as possible. In addition, by connecting virtual nodes, the number of paths between decomposition nodes increases, which has the advantage of accelerating the convergence of the graph neural network and speeding up learning. On the other hand, there is a disadvantage that the characteristics of each virtual node are lost, especially when a specific node has multiple domain information, and the expressiveness is likely to decrease. For this reason, when each specific node has multiple domain information, or when the number of decomposition nodes is, for example, 100 or more, it is not necessary to connect virtual nodes, and it is sufficient to set the above K to satisfy N x (N-1)/2 >> K x N, in which case a connected graph is not generated and the amount of calculation can be significantly reduced.

In the above, when the virtual nodes are connected and when the virtual nodes are not connected, multiple edges and self-loops are suppressed, and a special effect not seen in the past is achieved. In particular, when the number of virtual nodes is one, the amount of calculation can be reduced the most, so that a remarkable effect can be obtained in which the amount of calculation and information degradation can be reduced simultaneously in many data sets. In addition, when there are two virtual nodes, there is a feature that a closed path is created that propagates from one decomposition node to the first virtual node and the second virtual node, and it is also possible to analyze the characteristics closed with the virtual node and the decomposition node generated based on one node without relying on the connection of external nodes or edges. This can have a remarkable effect, for example, in a graph neural network, when the information possessed by one node becomes dominant in expressing the feature amount of the graph network.
The feature refers to a set of values that serve as a clue for predicting the correct label of the learning data or test data among the input learning data or test data. This feature can be acquired within the framework of a graph neural network, and a classification problem can be realized by inputting these feature values to a fully connected layer, outputting the same number of values as the number of classes, and applying an activation function used in classification, such as a log softmax function or a softmax function, immediately before the output layer. A regression problem can be realized by inputting these feature values to a fully connected layer and outputting them as a single numerical value. In addition to cases where a correct label is present, such as in a classification or regression problem, a graph neural network that extracts features, such as an autoencoder, can be combined with deep learning that restores input data from features, or self-supervised learning, which is unsupervised learning that hides (masks) node attributes or edge attributes and predicts the hidden value, can also be performed. In this way, features are a group of numbers that abstractly represent the characteristics of the input data obtained by applying a nonlinear function to the input data within the framework of deep learning. Although the features themselves cannot be understood by humans, by learning them in combination with a loss function that outputs the difference from the correct answer, it is possible to capture the characteristics of the input data from the data.

Furthermore, it is desirable that the number of decomposition nodes is the same as the number of edges connected to a specific node. As shown in the above examples of papers and books, since the purpose is to use different decomposition nodes for each domain, decomposition nodes that can be considered as a common domain to the domains of specific nodes may be aggregated into one decomposition node if self-loops and multiple edges do not occur. For example, chapters 2 and 3 of a book may be expressed as one decomposition node. Also, decomposition nodes that are not connected to nodes other than virtual nodes via edges may be defined, for example, corresponding to chapters with no citations. For example, in the above social network, the names of the decomposition nodes are Product 1, Product 2, Product 3, and in the case of citing a paper, Chapters 3 and 4. However, by defining a table in which names correspond to real numbers or integers and assigning them to part of the elements of the node attribute information of the decomposition nodes, and replacing them with real numbers or integers, and by assigning information that can determine the domain information, such as Product 1, to part of the name of the decomposition node, the information degradation when converting to a graph network can be further reduced. Taking a book as an example, this indicates that chapter 5, which does not cite any papers, can be used as a decomposition node, which has the effect of eliminating the need to redefine the book's virtual nodes and decomposition nodes when other papers or books that cite chapter 5 are published. Furthermore, the fact that a book has 5 chapters can be extracted from the graph structure alone. This means that when the graph is treated as a circuit and semiconductors are the subject of discussion, the terminal numbers of semiconductors represent their functions, so even decomposition nodes that have no wiring connections contain information. Therefore, by leaving such terminals without wiring connections as nodes, a remarkable and unprecedented effect can be achieved, in that semiconductors can be reproduced from the graph structure alone.

The virtual nodes and decomposition nodes are connected, for example, by newly defined edges. When there are two or more virtual nodes, the decomposition nodes are connected to each other by edges. However, when a graph network is represented as an adjacency matrix or connectivity matrix, it can be represented by real numbers or integers other than 0, so it does not necessarily have to be data that can be illustrated. Also, two or more virtual nodes do not have to be connected by edges, but if they are connected by edges, the number of edges between virtual nodes increases exponentially, so the number of virtual nodes should be four or less, preferably three or less.

For example, the connection between a specific node and an edge is removed after the edge connected to the specific node is connected to the decomposition node, or at the same time as the connection. In this case, all edges connected to the specific node are connected to the decomposition node, so the information between the specific node and the edge is transferred to the information between the decomposition node and the edge without any information degradation. Therefore, the information between the specific node and the edge is no longer necessary, and even if that information is deleted, no information degradation occurs.

For example, a specific node is deleted after the connection between the specific node and an edge has been removed. Once the connection between the specific node and an edge has been removed, the specific node will no longer have any edges connected to it, so no information degradation will occur even if a specific node that has no connections to edges is removed.

For example, a domain refers to each class in data that can be classified into classes. In the example of a company in the graph network of the first embodiment, each product can be classified into a class, i.e., product 1, product 2, and product 3, so it becomes a domain. Furthermore, if there are two systems, product and sales, it is possible to separate the domain into a domain related to products and a domain related to sales, and to separate the decomposition nodes for each domain with different systems. Also, for example, in an orthogonal coordinate system for indicating data that belongs to a different type or dimension from the systems in the first embodiment, it is not possible to mix the magnitudes of the x-axis, y-axis, and z-axis into one system, so it is possible to have three domains, with one system for the x-axis, one system for the y-axis, and one system for the z-axis. Also, with regard to products, it is not possible to mix the domain related to price and the domain related to inventory into one system, so it is possible to have one domain for price and one system for inventory.

In the first embodiment, the virtual node and the decomposition node are in a star graph relationship, and the information processing device 100 according to the first embodiment is configured to convert a specific node to which multiple edges are connected into a star graph representation. For example, such a star graph is composed of multiple virtual nodes corresponding to information for identifying each terminal of a multi-terminal component having N (e.g., a natural number equal to or greater than 3) terminals, a decomposition node as a connection node, and multiple edges connecting them. In this way, the graph structure of the star graph generated based on the specific node is a structure in which the virtual node and the decomposition node are connected by one edge, and multiple decomposition nodes are not connected to each other. For this reason, in order for node attribute information to move from one decomposition node to a different decomposition node, it is necessary to go through a virtual node, and further, the structure is characterized in that only decomposition nodes are connected to the virtual node.

As described above, the information processing device 100 according to the first embodiment includes a graph data acquisition unit 10 that acquires first graph data representing a first graph having a specific node having first information and second information, a first edge associated with the first information and connected to the first node, and a second edge associated with the second information and connected to the first node, and a graph generation unit 30 that generates second graph data representing a second graph in which the specific node has been replaced with a subgraph having a plurality of nodes in the first graph, including a first node that is a decomposition node corresponding to the first information and a second node that is a decomposition node corresponding to the second information, and edges that connect the plurality of nodes to each other. The graph generation unit 30 generates the second graph data such that in the second graph, the first edge is connected to the first node and the second edge is connected to the second node, resulting in a graph network.

When configured in this manner, the information processing device 100 generates data indicating a graph network in which, when a node of a graph network has multiple pieces of information, the node is replaced with a subgraph having multiple nodes including a decomposition node corresponding to the multiple pieces of information, thereby making it possible to suppress degradation of information when processing the graph network. Note that the subgraph is not limited to one formed of a single graph in which all nodes are connected to each other, but may be formed of multiple graphs that are independent of each other.

Embodiment 2.
Next, an information processing device 100 according to embodiment 2 will be described with reference to Fig. 16 to Fig. 22. The information processing device 100 according to embodiment 2 differs from the information processing device 100 according to embodiment 1 in some of the processes performed on graph data, but the configuration is the same, and the same reference numerals and names are used for the same configuration as in embodiment 1, and description thereof will be omitted.

FIG. 16 is a flowchart showing an example of processing performed by the information processing device 100 according to embodiment 2. After acquiring the first graph data in the processing of step ST11, the information processing device 100 according to embodiment 1 extracts a node to which three or more edges are connected from the first graph as a specific node, whereas after acquiring the first graph data in the processing of step ST11, the information processing device 100 according to embodiment 2 extracts a node to which two edges are connected (two-terminal connection point) from the first graph as a specific node (step ST32).

FIG. 17A shows a first graph G2 as an example shown by the first graph data acquired by the information processing device 100 according to embodiment 2. After performing the processing of step ST32, the information processing device 100 determines whether or not a specific node has been extracted from the first graph in the processing of step ST32 (step ST33). If the first graph has a specific node (YES in step ST33), the information processing device 100 generates multiple new nodes based on information held by any of the extracted specific nodes (step ST34).

17B is a second graph as an example of a graph network represented by the second graph data generated by the information processing device 100 according to the second embodiment. For example, as shown in FIG. 17A, if the first graph G2 has a node n21 to which two edges are connected, in the process of step ST34, the information processing device 100 generates nodes n22 and n23, which are decomposition nodes, based on information corresponding to edges e21 and e22 connected to the node n21, which the node n21 has, as shown in FIG. 17B. After performing the process of step ST34, the information processing device 100 connects edges to the nodes n22 and n23, which are decomposition nodes (step ST35). For example, in this process, the information processing device 100 connects nodes n22 and n23 with a new edge e23, connects edge e21 to node n22, and connects edge e22 to node n23. The processes of steps ST36 and ST17 below are the same as those of the first embodiment, and therefore will not be described.

In the second embodiment, similarly to the first embodiment, when a graph network is obtained as connection information by a text or an adjacency matrix, two-terminal connection points to which two or more edges are connected can be extracted from the connection information. For example, when the following connection information is in text format, node 1 and node 2 each become two-terminal connection points to which two or more edges are connected, so that, for example, node 1 can be two-terminal connection point 1 and node 2 can be two-terminal connection point 2.

Node 1; Edge 1, Edge 2, Edge 3
Node 2; Edge 3, Edge 4

Next, for each two-terminal connection point, we define two two-terminal decomposition points, which results in:

2-terminal connection point 1; edge 1, edge 2, edge 3
2-terminal connection point 2; edge 3, edge 4
2-terminal decomposition point 1-1;
2-terminal decomposition point 1-2;
2-terminal decomposition point 2-1;
2-terminal decomposition point 2-2;

Then, by connecting the edges connected to the two-terminal connection points to the two-terminal decomposition points, we get the following:

2-terminal connection point 1; edge 1, edge 2, edge 3
2-terminal connection point 2; edge 3, edge 4
2-terminal decomposition point 1-1; Edge 1, Edge 2
2-terminal decomposition point 1-2; edge 3
2-terminal decomposition point 2-1; edge 3
2-terminal decomposition point 2-2; edge 4

In this case, edges 1 and 2 are assumed to connect to the domain of two-terminal decomposition point 1-1. This is true when two-terminal connection point 1 has two inputs and one output, or two outputs and one input, and the input and output can be read from the text data. However, in the case of a data set where it is not possible to determine whether something is an input or an output, it is desirable to process it as a specific node connected by three edges, as explained in the first embodiment. For example, in cases where the association between input and output is not determined, such as the relationship between citations and cited entities, it is sufficient to define citations as inputs and cited entities as outputs, and generate a graph network for the data set based on the definition.

Next, new edges (edge 1-1, edge 2-1) are defined between the two divided two-terminal decomposition points, and the nodes are connected as follows.

2-terminal connection point 1; edge 1, edge 2, edge 3
2-terminal connection point 2; edge 3, edge 4
2-terminal decomposition point 1-1; Edge 1, Edge 2, Edge 1-1
2-terminal decomposition point 1-2; edge 3, edge 1-1
2-terminal decomposition point 2-1; edge 3, edge 2-1
2-terminal decomposition point 2-2; edge 4, edge 2-1

As a result, since the information on the two-terminal connection points and edges is transferred to the information on the two-terminal decomposition points and edges without information degradation, removing the information on the two-terminal connection points and edges does not result in information degradation, as follows.

2-terminal connection point 1;
2-terminal connection point 2;
2-terminal decomposition point 1-1; Edge 1, Edge 2, Edge 1-1
2-terminal decomposition point 1-2; edge 3, edge 1-1
2-terminal decomposition point 2-1; edge 3, edge 2-1
2-terminal decomposition point 2-2; edge 4, edge 2-1

As a result of the above process, the two-terminal connection point is no longer connected to an edge, so the two-terminal connection point is removed, and the following final output is obtained.

2-terminal decomposition point 1-1; Edge 1, Edge 2, Edge 1-1
2-terminal decomposition point 1-2; edge 3, edge 1-1
2-terminal decomposition point 2-1; edge 3, edge 2-1
2-terminal decomposition point 2-2; edge 4, edge 2-1

In addition, the information processing device 100 may be configured to perform both the processing for a specific node to which three or more edges are connected as shown in embodiment 1, and the processing for a specific node to which two edges are connected as shown in embodiment 2. For example, when three or more edges are connected and the relationship between input and output cannot be extracted from the graph data, it is desirable for the information processing device 100 to be configured to perform a combination of the processing shown in embodiment 1 and the processing shown in embodiment 2.

Furthermore, the new edge generated in the processing of step ST35 described above is not limited to an edge connecting the two decomposition nodes generated in the processing of step ST34 to each other. In other words, the subgraph generated by the graph generation unit 30 is not limited to one in which the multiple nodes in the subgraph are directly connected to each other via edges. For example, the new edge generated in the processing of step ST35 may be an edge that connects the two decomposition nodes generated in the processing of step ST34 in parallel, without directly connecting these two decomposition nodes to each other.

18A shows a first graph G21 as an example different from FIG. 17A of a graph network shown by first graph data acquired by information processing device 100 according to embodiment 2, and FIG. 18B shows a second graph G21' as an example different from FIG. 17B of a graph network shown by second graph data generated by information processing device 100 according to embodiment 2. For example, as shown in FIG. 18A, in the processing of step ST11, when a first graph G21 having node n210, specific node n211 as an original node, node n212, a first edge e210 connecting node n210 and specific node n211, and a second edge e211 connecting specific node n211 and node n212 is acquired, as shown in FIG. 18B, in the processing of step ST34, information processing device 100 generates a first node n210 as a first decomposition node based on information held by specific node n211, and a second edge e211 connecting specific node n211 and node n212. In the processing of step ST35, a new third edge e213 connecting node n212 and the first node n213, and a new fourth edge e212 connecting node n210 and the second node n214 may be generated, and the first node n213 and the second node n214 may be connected in parallel such that node n210 and the first node n213 are connected by the first edge e210 and node n212 and the second node n214 are connected by the second edge e211. In other words, in the second graph G21' in which the specific node n211 is replaced with the subgraph g21', the graph generating unit 30 divides the first edge e210 into the first edge e210 as the 1-1 edge and the fourth edge e212 as the 1-2 edge, divides the second edge e211 into the second edge e211 as the 2-2 edge and the third edge e213 as the 2-1 edge, connects one end of the first edge e210 to the first node n213, and divides the fourth edge e212 into the second edge e211 as the 2-2 edge and the third edge e213 as the 2-1 edge. The second graph data may be generated so that one end of the edge e210 and the fourth edge e212 are connected to the second node n214, the other end of the first edge e210 and the other end of the fourth edge e212 are connected to the common node n210, one end of the second edge e211 is connected to the second node n214, one end of the third edge e213 is connected to the first node n213, and the other end of the second edge e211 and the other end of the third edge e213 are connected to the common node n212. For example, the third edge e213 and the fourth edge e212, which are new edges, are generated as edges having directionality. Specifically, the third edge e213 may have a directionality input to the second node, and the fourth edge e212 may have a directionality input to the first node. The first graph may be a graph showing an electric circuit, the node n211 as the original node may be a diode or a battery (DC power source) included in the electric circuit, or a directional coupler, or a transmitting/receiving antenna, the third edge e213 may have a direction of input to the first node, and the fourth edge e212 may have a direction of input to the second node. In other words, the third edge e213 may have a direction from the node n212 to the first node n213, and the fourth edge e212 may have a direction from the node n210 to the second node n214.

For example, when the second graph generated by the information processing device 100 is an undirected graph that does not have edge directionality, there is a problem that a diode that includes a directional reverse bias in an electric circuit cannot be explicitly expressed, and it is necessary to rely on the learning of the graph neural network. When dealing with such a diode, it is expected that a signal with the first edge as input and the second edge as output and a signal with the second edge as input and the first edge as output will have different characteristics. However, when the second graph is an undirected graph, the order in which the first node and the second node pass is different between the signal flowing from the first node to the second node and the signal flowing from the second node to the first node in the graph neural network that processes the graph. Therefore, due to the effect of the nonlinear function due to the activation function in the graph neural network, it is possible to take into account the directionality by learning rather than expressing it only with the original node. However, this is knowledge that needs to be acquired by learning the graph neural network, and since it is not given explicitly, more learning data and learning time are required.

In contrast, in the second graph shown in FIG. 18B, only signals flow from left to right through the first edge e210 due to the influence of the third edge e213. Also, signals do not flow from right to left through the second edge e211 due to the influence of the fourth edge e212. Therefore, by explicitly providing data, there is no need to acquire knowledge through learning of the graph neural network, and information degradation during conversion to a graph network can be suppressed. Therefore, more accurate inference can be performed with less data. Note that at this time, one or both of the first edge e210 and the second edge e211 may have a directionality, and further, if one or both of the first edge e210 and the second edge e211 have a directionality, one or both of the third edge e213 and the fourth edge e212 may not have a directionality. Note that when the original node n211 represents a diode, the first node n213 and the second node n214 correspond to an anode and a cathode. For example, if the original node represents a battery, the first node n213 and the second node n214 correspond to the positive and negative poles of the battery. For example, if the original node represents an antenna, the first node n213 and the second node n214 correspond to the transmitting and receiving poles of the antenna.

Also, for example, when considering the citation relationship between a book and a paper, if a paper cites a book, the paper cites and the book is cited, and this can be expressed as a directed graph in a graph network. For example, if a cited paper is cited when revising a book, the book cites and the paper is cited, and the paper and the book are mutually related. However, if a book is represented as a single node, the relationship between citation and citation becomes ambiguous. Also, in the case of a directed graph, only one relationship between citation and citation can be represented, and if it is represented by edges with two directions, it will be the same as a single edge with no direction when represented in an adjacency matrix, resulting in information degradation. Therefore, this problem can be solved by decomposing citation and citation into separate nodes as shown in Figure 18B and giving direction to at least one edge connecting to each node. As a result, citation information propagates via the first edge e210, the first node n213, and the third edge e213, and cited information propagates via the second edge e211, the second node n214, and the fourth edge e212, so by assigning different attribute information to the first node n213 and the second node n214, an asymmetric relationship can be represented in the graph network.

FIG. 19A shows a first graph G22 as an example different from FIGS. 17A and 18A of a graph network shown by first graph data acquired by information processing device 100 according to embodiment 2, and FIG. 19B shows a second graph G22' as an example different from FIGS. 17B and 18B of a graph network shown by second graph data generated by information processing device 100 according to embodiment 2.

For example, as shown in FIG. 19A, in the processing of step ST11, a first graph G22 is acquired that has node n210, a specific node n220 as an original node, a specific node n230 as an original node, node n212, an edge e220 connecting node n210 and specific node n220, an edge e221 connecting specific node n220 and specific node n230, and an edge e222 connecting specific node n230 and node n212. In this case, as shown in FIG. 19B, in the processing of step ST34, the information processing device 100 divides two decomposition nodes, a first node n221 and a second node n222, into two decomposition nodes, based on the information held by the specific node n220. n222, and generates two decomposition nodes, a first node n231 and a second node n232, based on information held by the specific node n230. In the processing of step ST35, an edge e224 connecting the node n212 and the first node n231, an edge e223 connecting the node n210 and the second node n222, an edge e225 connecting the first node n221 and the first node n231, and an edge e226 connecting the second node n222 and the second node n232 are generated, and the edge e220 connects the node n210 and the first node n221, and the edge e222 connects the node n212 and the second node n232. Furthermore, the first node n221 and the second node n222, and the first node n231 and the second node n232 may be configured to be connected in parallel, respectively. For example, the new edges e225 and e226 are generated as directional edges.

For example, in citing a book, when node n220 is a book and node n230 is a paper, the following can be written as text data: In the following expression, edge e211 has a bidirectional relationship of citing and being cited.

Node n220; edge e211, edge e220
Node n230; edge e211, edge e222

In the above, a decomposition node is defined for each node, and the directionality of the edge e211 is also defined. In the following example, a signal entering a node is represented by (IN), and a signal leaving the node is represented by (OUT). In a graph network, IN and OUT can be represented as directed graphs, and edges without direction can be considered as bidirectional directed graphs, so that an adjacency matrix that mathematically describes a graph network can be considered to be the same as an undirected graph.

Node n220; edge e211, edge e220
Node n230; edge e211, edge e222
Node n221; edge e225 (IN)
Node n 222; edge e 226 (OUT)
Node n231; edge e225 (OUT)
Node n 232; edge e 226 (IN)

Furthermore, if the edges e220 and e222 connected to the nodes n220 and n230 are respectively defined as edges e220 and e223, and edges e224 and e222, then the following is obtained.

Node n220; edge e211, edge e220
Node n230; edge e211, edge e222
Node n221; edge e225 (IN), edge e220
Node n222; edge e226 (OUT), edge e223
Node n231; edge e225 (OUT), edge e224
Node n232; edge e226 (IN), edge e222

At this time, the nodes n220 and n230, and the edges e211, e220, and e222 are unnecessary because they have been replaced by the decomposition nodes and the edges e225, e226, e220, e223, e224, and e222 without information degradation. Therefore, the final result is as follows.

Node n221; edge e225 (IN), edge e220
Node n222; edge e226 (OUT), edge e223
Node n231; edge e225 (OUT), edge e224
Node n232; edge e226 (IN), edge e222

Since there is a relationship between node n221 and node n222, and there is a relationship between node n231 and node n232, the nodes may be connected by edges.

20 is a flowchart showing an example of processing performed by the information processing device 100 according to a modified example of the first embodiment. Specifically, FIG. 20 shows processing performed by the information processing device 100 when extracting node n31 to which four edges are connected from the first graph. By combining the processing according to the first embodiment as shown in FIG. 20 with the processing shown in the second embodiment, the graph network shown in FIG. 21A can be converted into the graph network shown in FIG. 21B. FIG. 21A is a first graph as an example of a graph network shown by the first graph data acquired by the information processing device 100. Specifically, FIG. 21A is a graph network in which a specific node to which three or more edges are connected and a two-terminal connection point are connected by two edges, i.e., multiple edges. FIG. 21B is a second graph as an example of a graph network shown by the second graph data generated by the information processing device 100.

For example, as shown in Figures 20, 21A, and 21B, the information processing device 100 generates four decomposition nodes, node n33, node n33, node n33, and node n33, based on node n31 to which four edges are connected, and node n37, which is a virtual node, and generates two decomposition nodes, node n38 and node n39, based on node n32 to which two edges are connected.

Below is a specific example of graph data in a case where a process is performed by combining the process shown in the first embodiment and the process shown in the second embodiment. Node 1 is a specific node to which four edges are connected, and node 2 is a two-terminal connection point connected to the specific node by two edges.

Node 1; Edge 1, Edge 2, Edge 3, Edge 4
Node 2; Edge 3, Edge 4

For ease of understanding, we will call node 1 a specific node and node 2 a two-terminal connection point. Note that changing the definition of the names does not change the information in the graph network, so there is no degradation of information.

Specific node: Edge 1, Edge 2, Edge 3, Edge 4
Two-terminal connection point: edge 3, edge 4

If a two-terminal decomposition point is added, which is a decomposition of a two-terminal connection point into two, the result will be as follows.

Specific node: Edge 1, Edge 2, Edge 3, Edge 4
Two-terminal connection point: edge 3, edge 4
2-terminal decomposition point 1;
2-terminal decomposition point 2;

If the connection between a specific node and a two-terminal connection point is transferred to the connection between a specific node and a two-terminal decomposition point, the result is as follows.

Specific node: Edge 1, Edge 2, Edge 3, Edge 4
Two-terminal connection point: edge 3, edge 4
2-terminal decomposition point 1; edge 3
2-terminal decomposition point 2; edge 4

If the two-terminal decomposition points are connected with a new edge (edge 1-1), the result is as follows.

Specific node: Edge 1, Edge 2, Edge 3, Edge 4
Two-terminal connection point: edge 3, edge 4
2-terminal decomposition point 1; edge 3, edge 1-1
2-terminal decomposition point 2; edge 4, edge 1-1

Here, since the information between the specific node and the two-terminal connection point has been transferred to the information of the two two-terminal decomposition points without degradation, the edge between the specific node and the two-terminal connection point is removed, and the two-terminal connection point is also removed. As a result, the following is the final output.

Specific node: Edge 1, Edge 2, Edge 3, Edge 4
2-terminal decomposition point 1; edge 3, edge 1-1
2-terminal decomposition point 2; edge 4, edge 1-1

In the second embodiment, the two-terminal connection point is a specific node connected by two edges. The two-terminal connection point may have an input or an output, or both an input and an output. For example, in the case of citing a paper shown in the first embodiment, since a paper has a relationship of either citing or being cited, if the time when the paper is cited is considered as an input and the time when the paper is cited is considered as an output, the two-terminal connection point can be considered as a node with an input and an output. Similarly, in the case of an SNS, the time when one user cites another user can be considered as an input, and the time when the paper is cited by another user can be considered as an output. In addition, in the case of citing a paper, a specific node connected by three or more edges and a two-terminal connection point connected by two or more edges may occur due to the time difference between when a paper is published on the web and when it becomes a journal, the time difference due to the difference in the edition of the book, etc., and the paper may be cited and cited by each other. In a social network, a two-terminal connection point also occurs when a citation and a citation occur between a company and a user. These examples are special cases, but they occur many times in the electric circuit described in the third embodiment described later, so the frequency of occurrence depends on the data set. In this way, the information processing device 100 according to embodiment 2 can avoid multiple edges for any data set, thereby suppressing information degradation.

A two-terminal decomposition point is generated by defining two two-terminal decomposition points for one two-terminal connection point. If one of the two-terminal decomposition points is considered as an input and the other as an output, the two-terminal connection point could not distinguish the input/output relationship, whereas the two-terminal decomposition point can clarify the input/output relationship with an undirected graph without using a directed graph. In particular, it has a special effect when there is a difference between the forward and reverse directions, that is, the signal propagating from the input to the output and the signal propagating from the output to the input. When there is a relationship between the input and the output, it is possible to express it with a directed graph in which signals flow forcibly in only one direction, but since signals do not propagate in the reverse direction in a directed graph, this cannot be realized by the conventional method in which there is a characteristic in the reverse direction as well. In contrast, in the second embodiment, different node attribute information is given to the input and output, and by processing with an undirected graph, even if the characteristics in the forward and reverse directions are significantly different, it is possible to learn them as data with different characteristics. This shows that it has a remarkable characteristic that has not been seen before.

In addition, in order to hold the relationship between the input and output of the two-terminal decomposition point, it is also desirable to hold the relationship between the input and output as data in the name of the two-terminal decomposition point or in at least one element of the matrix that is the node attribute information of the two-terminal decomposition point. Specifically, when giving it as a name, assuming that xx is the edge number, this can be realized by setting the input to xx-0 and the output to xx-1. When giving it as node attribute information, the information can be held by setting the node attribute information in the first column of the input side of the two-terminal decomposition point in an N-column matrix to 0 and the first column on the output side to 1. For example, the input and output can be defined by giving attribute information to the attribute information of the two-terminal decomposition point with a one-hot vector. For example, assuming that the attribute information of the node is represented by a three-column matrix, this can be realized by defining the input attribute information as 0, 0, 1 and the output attribute information as 0, 1, 0 as follows.

2-terminal decomposition point 1; 0, 0, 1 (input)
2-terminal decomposition point 2; 0, 1, 0 (output)

In addition, when a two-terminal decomposition point with input and output is included in the target data set, it can be divided into input and output by defining it as 1, 0, 0, for example. However, in the case of input and output, instead of one-hot vectors, 0, 1, 1, which is the sum of each element of input 0, 0, 1 and output 0, 1, 0, can be assigned as node attribute information. This reduces the number of columns, thereby reducing the amount of calculation, calculation time, and memory required for graph processing. Although it is expressed as 0 or 1, it can be defined in any way, such as real numbers, integers, strings, and complex numbers, as long as the two can be distinguished by information processing. For example, in the case of a diode, when the forward bias characteristic and reverse bias characteristic are known, a value representing each characteristic can be assigned to the element. In addition, since it is decomposed from a single two-terminal component, when the forward and reverse characteristics are unknown, it is desirable to set the node attribute information of the two-terminal decomposition point to the same value except for the information related to the input and output, and it is also acceptable to hold node attribute information other than the node attribute information related to the input and output (in the case of a book or paper, keywords, publication year, publisher, etc.) as a one-hot vector.

Since the two two-terminal decomposition points have an input-output relationship, meaning input and output, or bidirectional, an edge connects the two two-terminal decomposition points. It does not have to be a specific edge, but in a graph network, any representation that can be converted reversibly can be used, such as an adjacency matrix, a connection matrix, a Laplacian matrix, or describing the two connections as text data.

In order to transfer the information between a specific node and a two-terminal connection point to the connection between the specific node and the two-terminal decomposition point, the specific node and the two-terminal decomposition point are connected. As a result, the connection information between the specific node and the two-terminal connection point is maintained as the connection information between the specific node and the two-terminal decomposition point without information degradation. For example, in the graph data represented by the following, if the first edge is defined as the input and the second edge is defined as the output, the input and output information cannot be maintained as graph network information with the conventional two-terminal connection point.

Two-terminal connection point: edge 3, edge 4

On the other hand, in the second embodiment, it can be determined that edge 3 is connected as an input to two-terminal decomposition point 1, and edge 4 is connected as an output to two-terminal decomposition point 2, and information that would be discarded during processing in conventional methods can be retained in the second embodiment, thereby suppressing information degradation. Also, while conventional two-terminal connection points cannot retain the input/output relationship in processing such as graph neural networks, such information can be retained as two-terminal decomposition points, such as matrix elements that become node attribute information and names of two-terminal decomposition points, thereby preventing information degradation.

22A shows a first graph G4 as an example of a graph network shown by the first graph data acquired by the information processing device 100, and FIG. 22B shows a second graph G4' as an example of a graph network shown by the second graph data generated by the information processing device 100. For example, when the graph network shown by the graph data is a graph network showing an electric circuit, as shown in FIG. 22A, the information processing device 100 extracts node n41, which is a multi-element component connected to six edges, as a specific node to which three or more edges are connected, from among the nodes showing the components of the electric circuit. In this case, for example, the information processing device 100 generates nodes n42, n43, n44, n45, n46, and n47, which are terminal components serving as decomposition nodes corresponding to each of the six edges, and generates node n48, which is a virtual component serving as a virtual node for connecting these nodes n42 to n47 to each other.

Embodiment 3.
Next, an information processing device 100 according to embodiment 3 will be described with reference to Fig. 23 to Fig. 31. The information processing device 100 according to embodiment 3 differs from the information processing device 100 according to embodiment 1 in some of the processes performed on graph data, but has the same configuration, and the same reference numerals and names are used for the same configuration as in embodiment 1, and description thereof will be omitted.

FIG. 23 is a flowchart showing an example of processing performed by the information processing device 100 according to embodiment 3. The processing performed by the information processing device 100 according to embodiment 3 will be described below, taking as an example a case where the information processing device 100 acquires a parts list and inter-parts connection list of an electric circuit as the first graph data. The information processing device 100 acquires a parts list and inter-parts connection list of an electric circuit as the first graph data in the processing of step ST11 (step ST51). For example, the information processing device 100 acquires the parts list and inter-parts connection list of the electric circuit as a netlist, which is text information.

24A is a circuit diagram shown by a netlist acquired by the information processing device 100 according to the third embodiment, and FIG. 24B is a netlist acquired by the information processing device 100 according to the third embodiment. Generally, several dozen different formats of netlists are known, but in any format, the circuit components, the auxiliary information (node attribute information) such as the model numbers and circuit constants of the circuit components, and the connection information between the circuit components, which are essential for forming a circuit, are included, and are in a reversible conversion relationship. Therefore, it is possible to extract from the netlist a component list describing the component names and an inter-component connection list describing the connection information between the components. In the third embodiment, the circuit and netlist for embedding in a printed circuit board are described, but the same applies to the circuit design between the logic design and layout design for designing a semiconductor. In this case, instead of the model numbers and circuit constants of the circuit components, the netlist includes auxiliary information such as physical dimensions at the time of layout, physical properties of materials, parasitic capacitance, residual inductance, residual resistance, and leakage current, and connection information between the components having the auxiliary information.

In particular, when considering circuits that include active elements such as semiconductors, active elements are multi-element components because they have three or more terminals. Specifically, even the simplest active element, such as the simplest power supply IC, has three terminals: an input terminal, an output terminal, and a GND terminal that serves as the reference potential. In addition to this, all active elements, such as ASICs, CPUs, FPGAs, memories, switching power supply elements, and communication elements, have three or more terminals, and some active elements have more than 2,000 terminals. Passive circuit components such as common mode choke coils have four terminals, two input terminals and two output terminals, so they can be treated the same as the active elements listed above.

In addition to three-terminal capacitors, single-phase transformers, three-phase transformers, motors (electric motors), and compressors, diode arrays, and resistor arrays can also be considered as multi-element components with three or more terminals. However, in the case of transformers, diode arrays, resistor arrays, etc., if the wiring connection information is clear and the parasitic components between adjacent components are clear, they may be broken down into multiple two-terminal components. On the other hand, passive elements such as normal mode choke coils, capacitors, resistors, and diodes are two-terminal components and are therefore not subject to processing in embodiment 3.

When focusing on such multi-element components, as shown in Figures 22A and 22B, one or more virtual nodes are newly defined for each multi-element component as virtual components and added to the components list. In addition, the terminals of the multi-element component are extracted from the netlist, and the same number of terminal components as the number of terminals are added to the components list as decomposition nodes (step ST54). At this time, non-connected (NC) terminals may or may not be added as terminal components. However, it is desirable to add them except for special reasons such as terminals that are not wired inside the semiconductor in order to standardize the semiconductor package. This allows circuits with different circuit configurations on the same semiconductor to be expressed by the same combination of circuit components and terminal components. At this time, as in the first embodiment, wiring is not connected to the NC terminals, so only virtual components are connected to the terminal components representing the NC terminals.

Focusing on multi-element components that can be extracted from the above netlist, virtual components and terminal components are defined from one multi-element component, connections are made between the defined virtual components and terminal components (step ST56), and the connection information is added to the inter-component connection list. In addition, for the wiring connected to each terminal of the multi-element component, the wiring is connected to each terminal component, and the connection information is added to the inter-component connection list (step ST55). However, it is not necessary for only one wiring to be connected to one terminal, and multiple wirings may be added to the inter-component connection list so that they are connected to one terminal. For example, a terminal through which a large current flows has a mechanism for inputting or outputting the same signal to multiple terminals to ensure the rated current value, but these terminals may be combined into one.

Furthermore, the above process replaces the multi-element components with virtual components and terminal components, and all the wires connected to the multi-element components are connected to the terminal components. As a result, the information of the multi-element components is transferred to the virtual components, terminal components, and wires connected to the terminal components without information degradation. Therefore, the wires connected to the multi-element components are removed from the inter-component connection list (step ST57), and the multi-element components are removed from the component list (step ST58), and information on the virtual components, terminal components, wires connected to the terminal components, and components other than the multi-element components that are not the processing targets is output (step ST59). The third embodiment provides two unprecedented advantages. The first is that the multiple edges and self-loops described in the first embodiment can be eliminated, preventing information degradation. The second is that the terminal numbers can be held as a graph network. To explain the second advantage in detail, the multi-element components will be written as follows, for example.

XU1; N002 N003 IN 0 N001 IN N002 N004

At this time, depending on the definition of each netlist, the wiring names from N002 to N004 mean the terminal numbers of the semiconductor in order. Even if the definition and the expression method change, all netlists have the above information because it is information for connecting terminals and wiring and is essential information for the circuit. In the above example, it means that N002 is connected to terminal number 1 of semiconductor XU1, N003 is connected to terminal number 2, IN is terminal number 3, GND at 0 is terminal number 4, N001 is terminal number 5, IN is terminal number 6, N002 is terminal number 7, and N004 is terminal number 8. Conventionally, since it is not possible to hold information about terminal numbers because it is not broken down into terminal parts, it is information that is lost by processing such as graph neural networks, which causes information degradation. On the other hand, in the third embodiment, it is broken down into terminal parts, and the terminal number can be held as part of the name of the terminal parts or as one element in the matrix of the node attribute information representing the terminal parts, so the above information degradation does not occur. For this reason, the above special effect can be obtained in the third embodiment.

In the first and second embodiments, specific nodes, virtual nodes, edges, decomposition nodes, two-terminal connection points, and two-terminal decomposition points were described, but in the third embodiment, specific nodes correspond to multi-element components, virtual nodes correspond to virtual components, edges correspond to wiring, decomposition nodes correspond to terminal components, two-terminal connection points correspond to two-terminal components, and two-terminal decomposition points correspond to two-terminal decomposition components. Below, a specific example of the third embodiment will be described using the circuit diagram shown in FIG. 24A as an example.

For example, a netlist is created by directly writing circuit information into a circuit CAD or text data. There are more than 10 known formats for netlists, such as the Allegro format and the ExpressPCB format, and all formats include wiring between circuit components, model numbers of circuit components, and circuit constants. An example of the notation of the netlist in Fig. 24B is shown below. In Fig. 24B, D1 indicates the name of the component, D2 indicates the wiring to be connected, D3 indicates the model number of the component, and D4 indicates the circuit constants.

V1;IN 0 3.3
XU1;N002 N003 IN 0 N001 IN N002 N004 LT3489
L1;IN N001 2.2u
D1;N001 OUT 1N5818
C1; OUT 0 20u
R1; OUT N003 28.7K
R2; N003 0 5.23K
C2;N004 0. 001u
Rload;OUT 0 13

In this netlist, the part before the ";" is defined as the circuit component, and the part after the ";" is defined as the wiring and model number or circuit constant. In the netlist, V1 is the power supply, XU1 is the semiconductor, L1 is the coil, D1 is the diode, C1 and C2 are capacitors, R1, R2 and Rload are resistors, and Rload represents the load resistor which is the output.

From the netlist, the following parts list and inter-parts connection list can be obtained. The parts list is the circuit parts before the ";", and the inter-parts connection list can be created by focusing on the wiring name after the ";". For example, if you select N001 as the wiring name for the inter-parts connection list, the circuit parts that use N001 are XU1, L1, and D1, so it can be written as N001; XU1, L1, D1. If you write down the other wiring in the same way, you get the following.

IN; V1, XU1, L1
OUT; D1, C1, R1, Rload
0; V1, XU1, C1, R2, C2, Rload
N001;XU1,L1,D1
N002;XU1
N003;XU1,R1,R2
N004;XU1,C2

If the components connected to the wiring N001 are combined in pairs, three combinations can be written: (XU1, L1), (XU1, D1), and (L1, D1), which correspond to the wiring between the components. The inter-component connection list only indicates the presence or absence of a connection, so the order does not matter in the undirected graph shown in the third embodiment. In other words, (XU1, L1) and (L1, XU1) mean the same information, so either can be used. However, in the case of a directed graph as shown in FIG. 18B or FIG. 19B, for example, XU1 is defined as OUT and L1 as IN, and XU1, L1) is defined as an edge from XU1 to L1. Then, an edge without direction information can be represented as a bidirectional edge by two, (XU1, L1) and (L1, XU1), to have the same effect as an edge in an undirected graph. By performing this process for all the wiring, an inter-component connection list can be created. As described above, if there is a netlist, an inter-component connection list can be created uniquely. The inter-component connection list is as shown below, but since it has a large number of elements and is easy for an information processing device to process, it is difficult for a human to understand. Therefore, the third embodiment will be described using a method for updating a netlist written as text data.

Parts list: [V1, XU1, L1, D1, C1, R1, R2, C2, Rload]
Inter-part connection list: [(V1,XU1), (V1,L1), (XU1,L1), (D1,C1), (D1,R1), (D1,Rload), (C1,R1), (C1,Rload), (R1,Rload), (V1,XU1), (V1,C1), (V1,R2), (V1,C2), (V1,Rload), (XU1,C1), (XU1,R2), (XU1, C2), (XU1, Rload), (C1, R2), (C1, C2), (C1, Rload), (R2, C2), (R2, Rload), (C2, Rload), (XU1, L1 ), (XU1, D1), (L1, D1), (XU1, R1), (XU1, R2), (R1, R2), (XU1, C2), (XU1, L1), (XU1, D1), (L1, D1)]

The only multi-element component in the above netlist is semiconductor XU1, which is represented as follows:

XU1;N002 N003 IN 0 N001 IN N002 N004 LT3489

N002 to N004 represent wiring, and LT3489 is the model number of a switching semiconductor from Analog Devices (registered trademark). Depending on the format of the netlist, the model number of the semiconductor and the circuit constants of the passive components may not be included in the netlist and may be written on a different line, but because of the reversible conversion relationship, the third embodiment will explain the method of writing them all together on one line.

In the third embodiment, the number of virtual components is described as one, but two or more virtual components may be used, as in the first embodiment. However, since the number of terminals in a semiconductor is limited and this would lead to an increase in the amount of calculations, it is desirable to limit the number of virtual components to three, as in the first embodiment. When defining a virtual component, the name of the virtual component can be freely determined, but in the third embodiment, the name is set to XU1_virtual, and the netlist is updated as follows:

XU1;N002 N003 IN 0 N001 IN N002 N004 LT3489
XU1_virtual;

The terminal parts are the wiring "N002 N003 IN 0 N001 IN N002 N004 LT3489" of XU1 in the above semiconductor netlist, since LT3489 is the part model number, N002 N003 IN 0 N001 IN N002 N004 are the wirings. This method of defining the netlist indicates that wirings with wiring names N002 are connected to terminal 1 of the semiconductor, N003 to terminal 2, IN to terminal 3, 0 to terminal 4, N001 to terminal 5, IN to terminal 6, N002 to terminal 7, and N004 to terminal 8. Therefore, eight terminal parts are defined for eight wirings. However, since there are two INs in this example, terminal 3 and terminal 6 to which IN is connected may be treated as one terminal part, as shown in embodiment 1.

On the other hand, there are also two N002s, but since this is a wiring that forms a closed self-loop connecting the terminals of a multi-element component, it cannot be combined into one terminal. The fact that it is a self-loop can be determined from the fact that N002 is not used in connections to other components in the netlist of the entire circuit. In addition, although it is not included in the example of FIG. 24A, in cases where NC is included, it is preferable to define the NC terminal as a terminal component. In particular, in cases where the same semiconductor is used in different electric circuits and the NC terminal is also connected to wiring and used in the other electric circuits, by defining the NC terminal as a terminal component, the number of terminal components for one semiconductor can be constant regardless of the circuit configuration around the semiconductor. As a result, it is possible to fix the virtual components and terminal components for each model number of the component, and the effect is obtained that it is possible to uniformly handle electric circuits with different circuit topologies for one model number. However, it is preferable not to define NC terminals that are not used regardless of how the semiconductor is used, such as when there is no wiring inside the semiconductor, as terminal components in order to reduce the amount of calculations in the graph network processing.

The netlist based on the above method is as follows, but the names of the terminal components in the netlist may be any names as long as they are different from the names of the other terminal components and circuit components.

XU1;N002 N003 IN 0 N001 IN N002 N004 LT3489
XU1_virtual;
XU1-1;
XU1-2;
XU1-3;
XU1-4;
XU1-5;
XU1-6;
XU1-7;
XU1-8;

Regarding the connection between the terminal parts and the wiring, since the number of wirings of the terminal parts and the multi-element parts defined above is equal, each wiring of the multi-element parts is assigned to the terminal parts. Through this process, the netlist is updated as follows:

XU1;N002 N003 IN 0 N001 IN N002 N004 LT3489
XU1_virtual;
XU1-1;N002
XU1-2;N003
XU1-3;IN
XU1-4;0
XU1-5;N001
XU1-6;IN
XU1-7;N002
XU1-8;N004

The connection between the virtual component and the terminal component defines the wiring between the virtual component and the terminal component. The name of the wiring can be any name as long as it is not the same as the name of other wiring used in the circuit. For example, in the third embodiment, if the names of the wiring are Line1 to Line8, the netlist will be as follows.

XU1;N002 N003 IN 0 N001 IN N002 N004 LT3489
XU1_virtual; Line1, Line2, Line3, Line4, Line5, Line6, Line7, Line8
XU1-1; N002, Line 1
XU1-2; N003, Line 2
XU1-3; IN, Line 3
XU1-4;0, Line4
XU1-5; N001, Line 5
XU1-6; IN, Line 6
XU1-7; N002, Line7
XU1-8; N004, Line 8

Removing multi-element components from the components list and from the inter-component connection list is no longer necessary because all information contained in the multi-element component semiconductor XU1 has been moved to XU1_virtual and XU1-1 to XU1-8. For this reason, the multi-element components and wiring are deleted from the inter-component connection list, and the multi-element components are deleted from the components list. However, because the component model numbers remain as information, they are retained as node attribute information for the virtual components, or node attribute information for the virtual components and terminal components. Through the above processing, the netlist that includes the two-terminal components that were not processed because they were not subject to processing will look like the one below, and this is the final output.

V1;IN 0 3.3
XU1_virtual; Line1, Line2, Line3, Line4, Line5, Line6, Line7, Line8 LT3489
XU1-1; N002, Line 1
XU1-2; N003, Line 2
XU1-3; IN, Line 3
XU1-4;0, Line4
XU1-5; N001, Line 5
XU1-6; IN, Line 6
XU1-7; N002, Line7
XU1-8; N004, Line 8
L1;IN N001 2.2u
D1;N001 OUT 1N5818
C1; OUT 0 20u
R1; OUT N003 28.7K
R2; N003 0 5.23K
C2;N004 0. 001u
Rload; OUT 0 13

In the third embodiment, for convenience of explanation, the netlist is updated, but it is preferable to perform the processing using the parts list and inter-parts connection list. Updating the netlist is easy for people to understand, but for information processing devices, it involves rewriting text data, which makes it more likely for human or mechanical errors to occur, such as encoding errors or errors due to escape sequences. On the other hand, replacing characters with numbers, IDs, etc. and processing as matrix or list data makes it harder for people to understand, but makes it less likely for exceptions to occur and processing errors to occur for information processing devices. In this case, rather than defining parts and wiring by name as in the third embodiment, replacing each part with a unique number makes it easier to process mechanically, and if these replaced definitions are stored as a database, the names can be replaced with more easily understandable names from the results of processing.

In this way, the information processing device 100 according to the third embodiment first extracts a parts list and an inter-parts connection list from the netlist in the process shown in FIG. 23. Then, one virtual part is added to the parts list, and the same number of terminal parts as the number of wires connected to the multi-element part or the same number as the number of terminals of the multi-element part are added to the parts list. At this time, since the number of wires will not be more than the number of terminals of the multi-element part, the number of wires will be less, and terminals to which no wires are connected will be NC terminals. FIG. 23 shows the case where the number of wires is the same as the number of wires connected to the multi-element part. Since the number of terminal parts is equal to the number of wires, one wire can be connected to one terminal part. In addition, new wires are defined between the terminal parts and the virtual parts and added to the inter-parts connection list, the connections between the multi-element part and the wires are removed from the inter-parts connection list, and the multi-element part after the information transfer is completed is removed from the parts list, and the parts list and the inter-parts connection list are output.

In the third embodiment, a method for converting text data including a netlist into a graph network with reversibility is shown. When a netlist of an electric circuit is converted into a graph network and then the converted graph network is converted back into a netlist, if the characteristics of the original electric circuit can be expressed using the inverse converted netlist, then it can be determined that there is no information degradation when converted into a graph network. However, conversion from a netlist to a graph network and conversion from a graph network to a netlist are not reversible processes, and therefore different algorithms must be constructed. For this reason, it is difficult to evaluate only the conversion or the inverse conversion. It is also possible to compare and evaluate the characteristics of the electric circuit before conversion and that generated by inverse conversion using the output results of a circuit simulation.

However, even with small degradations in information in the netlist, there is no guarantee that the netlist after reverse conversion can be calculated in a circuit simulator, i.e. that the calculations will be completed without errors. As an example, if even one incorrect wiring is added to a semiconductor terminal, the circuit simulation will not be able to output correct results even if all other information can be correctly reverse converted. It is also possible to compare the netlists before and after the above conversion, but because the order of components in the netlist and the names of the wiring are arbitrary, it is difficult to compare the netlist before conversion with the netlist generated by reverse conversion, and therefore an appropriate evaluation cannot be made.

For this reason, in the third embodiment, in order to evaluate the accuracy of conversion to a graph network, a method is proposed in which a graph network is input into a graph neural network and the accuracy of the conversion is confirmed based on the inference accuracy of the graph neural network. This is because it is believed that if there is little information degradation when converting to a graph network, the inference accuracy of the graph neural network will be high, and conversely, if information degradation occurs during conversion, the inference accuracy of the graph neural network will be low. In order to compare under fair conditions, except for the number of nodes, which changes due to the addition of virtual parts and terminal parts, the structure of the graph neural network (the number of hidden layers and the number of channels in each hidden layer), the number of epochs which is the number of repetitions, the number of mini-batches which is the number of data divisions, the optimization algorithm, etc. are not changed, and the combination of training data and test data is fixed so as not to change for each calculation.

In addition, the training data and test data were divided randomly to ensure equal numbers to avoid bias. Furthermore, because graph neural networks experience variability in learning due to the initial random number values, the initial values were changed 10 times to change the average of the inference values for testing, reducing the variability in learning.

The data set consisted of 3,308 electric circuits included in the Analog Devices circuit simulator LTspice. Of the 3,308, 2,315 (70%) were used as training data, and the remaining 993 were used as test data. The training data and test data were fixed. As shown in Figure 25, seven types of circuit components were used in the data set, and a netlist was extracted from the electric circuit, creating a seven-class graph classification problem. Figure 25 is a table showing the number of electric circuits (Circuits), the average number of nodes (Nodes), the average number of edges (Edges), and the average number of node types (Node Features) included in the netlist used as the data set. The number of power circuits (Power Products) was the largest, accounting for 70% of the total. The type of node refers to semiconductors, resistors, capacitors, coils, etc., and even if multiple capacitors are used in one circuit, it is counted as one. In addition, when a semiconductor is divided into terminal components, it is possible to assign the type of terminal component from the semiconductor's spec sheet. In this embodiment, the semiconductor is treated as a complete black box, so no terminal information is given and all terminals are defined as the same type of node.

The graph neural network was constructed with a network having three hidden layers. GraphSage was used as the reduction algorithm, as it provided the highest inference accuracy under all conditions. A three-layer network using GraphSage and the ReLU activation function was used, and a seven-value classification was performed using the Softmax activation function before the output layer. Note that a three-layer network was used for this dataset because it provided the highest inference accuracy compared to two-layer and four to six-layer networks under all conditions. However, it is acceptable to change the layer structure and neural network algorithm according to the dataset, as with general neural networks, by using a network with three or more layers when the scale of the electrical circuit is larger than that of the dataset in Figure 25, or a two-layer network when the scale of the electrical circuit is smaller.

Next, the effect of the third embodiment will be described with reference to Figs. 26 to 31. Fig. 26A is a circuit diagram showing an electric circuit including a multi-element component, and Fig. 26B is a graph network showing the electric circuit of Fig. 26A. As shown in Fig. 26B, a plurality of edges including edge e51 and edge e52 are connected to the multi-element component X, edge e51 is a self-loop, and edge e52 is a multiple edge. Fig. 27 is a graph network showing the inference accuracy when learning is performed under the condition that the multi-element component is not decomposed into virtual components and terminal components, and inference is performed using test data. Fig. 28 is a graph network showing the inference accuracy when all terminal components are connected using only terminal components without using virtual components in the electric circuit of Fig. 26A, and a complete graph is formed. Fig. 29 is a graph network showing the inference accuracy when learning is performed using the graph network of Fig. 28 and inference is performed using test data. Also, Fig. 30 shows a graph network in which terminal components are connected via virtual components in the electric circuit of Fig. 26A to form a star graph, and Fig. 31 shows a graph network showing the inference accuracy obtained by learning with the graph network of Fig. 30 and performing inference with test data. Note that a specific node (original node) in the first graph may be a single node showing a component in the electric circuit and a wiring connected to the component.

In all of the above examples, the learning was performed over 4,000 epochs, and the average of the maximum values of 10 trials was used as the inference accuracy. In the results shown in Figures 26A, 26B, and 27, the maximum inference accuracy was 97.20%. In addition, in the electric circuit of Figure 26A shown in Figures 28 and 29, when all terminal components are connected using only terminal components without using virtual components, the inference accuracy for the test data was calculated as 96.89% when the average of the maximum values of 10 trials was calculated, and the inference accuracy was lower than before the division into terminal components. In the case of learning and inference using the graph network according to the third embodiment shown in Figures 30 and 31, the inference accuracy for the test data was calculated as 97.72% when the average of the maximum values of 10 trials was calculated. From this, it can be seen that the inference accuracy drops by 0.5% when learning and inferring using only terminal components without using virtual components, whereas the inference accuracy improves by using virtual components and terminal components, and it is considered that the improvement was achieved by reducing information degradation.

In addition, when using a CPU (Intel (registered trademark) i9-11950H) and a GPU (Nvidia (registered trademark) RTX A5000), the calculation time required for learning is 7 minutes for Figure 27, 30 minutes for Figure 29, and 10 minutes for Figure 31, and it can be seen that Figure 31 is at a higher level than Figure 29.

Furthermore, comparing the conventional method in which there is no decomposition into terminals as shown in FIG. 26B with embodiment 3 in which there is decomposition into virtual components and terminal components as shown in FIG. 30, link prediction, which predicts the presence or absence of wiring, is difficult in the conventional method due to the existence of multiple edges, whereas embodiment 3 makes it possible to predict two or more edges between two nodes, which signify multiple edges, as a simple graph. Also, in node prediction, which predicts component constants and component model numbers, better results can be obtained than in the past, since it is possible to control the component directionality and the number of component terminals. Note that in embodiment 3, the reference potential (GND) is defined as a node, which makes it possible to reduce the occurrence of multiple edges.

The adjacency matrix generated based on the third embodiment can be used for graph classification (classifying the type of graph network), graph regression (predicting a real number sequence from a graph network), link prediction (predicting the presence or absence of an edge), node prediction (predicting the presence or absence of a node), and node characteristic prediction (predicting the type of node or the numerical value of a node) by a graph neural network. Graph features can be extracted using a graph VAE (Variational Autoencoder), and a graph network that satisfies desired conditions can be generated using a graph GAN (Generative Adversarial Network). These can be performed in the same way as general graph neural network processing, so details will not be explained.

If input and output voltages are also defined as nodes in the same way as GND, the input and output nodes can be multi-element components, which has the characteristic that calculations including input and output can be performed; however, since the direction of the input and output is clear, it is not necessarily necessary to divide these components into virtual components and terminal components. Also, depending on the purpose of use of the information processing device, such as when there is no need to reverse convert the results after graph processing as in the graph classification example above, it is not necessary to divide all of the multi-element components in the graph network. It is possible to divide only those that meet certain conditions, such as dividing only multi-element components with 10 or more terminals, or multi-element components that have self-loops or multiple edges.

Embodiment 4.
Next, an information processing device 100 according to embodiment 4 will be described with reference to Fig. 32 and Fig. 33. The information processing device 100 according to embodiment 4 differs from the information processing device 100 according to embodiment 1 in some of the processes performed on graph data, but has the same configuration, and the same reference numerals and names are used for the same configuration as in embodiment 1, and description thereof will be omitted.

In the third embodiment, the processing of circuit diagrams, which are essential for creating electric circuits on a printed circuit board, was explained. However, this method can be applied not only to circuits for designing printed circuit boards, but also to circuits for designing the inside of semiconductors. This is because inside semiconductors, in addition to transistors, the same circuit components as on a printed circuit board, such as resistors, coils, capacitors, and diodes, can be created. However, unlike circuit diagrams on a printed circuit board, there are no model numbers, so by adding parameters such as component dimensions, coating thickness, and material constants as node attribute information, processing equivalent to that of the third embodiment can also be used for semiconductor design.

Similarly, by adding parameters such as dimensions, coating thickness, and material constants as attribute information for circuit constants, processing similar to that of embodiment 3 can be used in semiconductor design. Furthermore, in the case of printed circuit board design, if a block diagram showing the internal circuit configuration of the semiconductor and the performance of the components in a schematic diagram is published on a spec sheet, the block diagram may be converted into a graph network and incorporated into the circuit diagram of the printed circuit board as a circuit component. Note that for blocks in the block diagram with three or more wire connections, virtual components can be defined, and terminal components according to the number of wires can be defined to perform the same processing as for multi-terminal components.

Figure 32 shows an example of a block diagram inside a semiconductor. In cases like this where some of the internal information of the semiconductor is known, it is acceptable to connect terminal components with strong relationships with new edges. This is also common to all multi-element components, not just semiconductors. In the example block diagram in Figure 32, it can be seen that X:1 and X:4, X:2 and X:3, and X:5 and X:6 are connected via a single component, so these terminal components are connected. Figure 33 shows a graph network of a multi-element component in which edges have been added between terminal components. It is also acceptable to define new virtual components between the terminal components and connect the above X:1 and X:4, X:2 and X:3, and X:5 and X:6 via each virtual component.

Specifically, in addition to the virtual parts shown in the third embodiment, virtual parts 1, 2, and 3 are defined, and connections are made as follows: X:1 -> virtual part 1 -> X:4, X:2 -> virtual part 2 -> X:3, and X:5 -> virtual part 3 -> X:6, and connections are made between virtual parts 1 and 2, between virtual parts 2 and 3, and between virtual parts 3 and 1. This results in a graph network that includes the characteristics of semiconductors, and compared to a conventional single node, it is possible to make a graph network that contains more information about the electric circuit, so that it is possible to reduce information degradation when converting from an electric circuit to a graph network. Furthermore, in addition to giving each terminal part the terminal information of the multi-element part as node attribute information, it is desirable to use adjacent terminal information as node attribute information for the attribute information of each virtual part. This is because it is possible to learn from values close to the solution by giving an additive average close to the weighted average of adjacent terminal information obtained by contracting the graph neural network as an initial condition, which can shorten the calculation time and reduce the possibility of falling into a minimum value.

Embodiment 5.
Next, an information processing device 100 according to embodiment 5 will be described with reference to Fig. 34 to Fig. 37. The information processing device 100 according to embodiment 5 differs from the information processing device 100 according to embodiment 1 in some of the processes performed on graph data, but has the same configuration, and the same reference numerals and names are used for the same configuration as in embodiment 1, and description thereof will be omitted.

The information processing device 100 is applied to a two-terminal component to which two or more wires are connected in a netlist of an electric circuit or a graph network that can be created from the netlist. In the fifth embodiment, as in the second embodiment, the effect can be obtained even when used alone, but by combining the method according to the third embodiment, it is possible to particularly reduce information degradation. The terminology will be explained using the netlist according to FIG. 24B shown in the third embodiment as an example. The netlist in FIG. 24B is republished as follows.

V1;IN 0 3.3
XU1;N002 N003 IN 0 N001 IN N002 N004 LT3489
L1;IN N001 2.2u
D1;N001 OUT 1N5818
C1; OUT 0 20u
R1; OUT N003 28.7K
R2; N003 0 5.23K
C2;N004 0. 001u
Rload;OUT 0 13

A two-terminal circuit component is a component that consists of an input terminal and an output terminal. In the above netlist, all components except XU1 are two-terminal circuit components, so the two-terminal circuit components are V1, L1, D1, C1, R1, R2, C2, and Rload. Wires also have physical entities and can be considered as nodes, but while circuit components have complex physical properties, wiring only has connection information between circuit components, so in embodiment 5, circuit components are considered as nodes and wiring is considered as edges that connect nodes. However, it is preferable to define GND, which is the reference potential of an electric circuit, as a node, as this reduces multiple edges.

A two-terminal disassembled component can be thought of as the two-terminal circuit component described above disassembled into two circuit components. The names of the disassembled components can be any as long as they are unique and not the same as other circuit component names. In the fifth embodiment, V1 is V1-1 and V1-2, L1 is L1-1 and L1-2, D1 is D1-1 and D1-2, C1 is C1-1 and C1-2, R1 is R1-1 and R1-2, R2 is R2-1 and R2-2, C2 is C2-1 and C2-2, and Rload is Rload-1 and Rload-2. However, the power supply does not necessarily have to be divided into two-terminal disassembled components.

The connection between a 2-terminal disassembled component and wiring means that the wiring connected to the 2-terminal circuit component is connected to each of the 2-terminal disassembled components that have been disassembled into two, and each wiring is assigned to the 2-terminal disassembled component. In the above example of the netlist, it is as follows.

V1;IN 0 3.3
XU1;N002 N003 IN 0 N001 IN N002 N004 LT3489
L1;IN N001 2.2u
D1;N001 OUT 1N5818
C1; OUT 0 20u
R1; OUT N003 28.7K
R2; N003 0 5.23K
C2;N004 0. 001u
Rload;OUT 0 13
V1-1;IN
V1-2;0
L1-1;IN
L1-2; N001
D1-1; N001
D1-2;OUT
C1-1;OUT
C1-2;0
R1-1;OUT
R1-2; N003
R2-1; N003
R2-2;0
C2-1; N004
C2-2;0
Rload-1; OUT
Rload-2;0

"Connection between 2-terminal decomposition components" connects 2-terminal decomposition components with newly defined wires, and any wire name can be used as long as it is different from other wire names used in the graph network. In the following example, Wire1 to Wire8 are used.

V1;IN 0 3.3
XU1;N002 N003 IN 0 N001 IN N002 N004 LT3489
L1;IN N001 2.2u
D1;N001 OUT 1N5818
C1; OUT 0 20u
R1; OUT N003 28.7K
R2; N003 0 5.23K
C2;N004 0. 001u
Rload;OUT 0 13
V1-1;IN Wire1
V1-2;0 Wire
L1-1;IN Wire2
L1-2;N001 Wire2
D1-1;N001 Wire3
D1-2; OUT Wire3
C1-1; OUT Wire4
C1-2;0 Wire4
R1-1; OUT Wire5
R1-2; N003 Wire5
R2-1; N003 Wire6
R2-2;0 Wire6
C2-1;N004 Wire7
C2-2;0 Wire7
Rload-1; OUT Wire8
Rload-2;0 Wire8

Regarding circuit constants, for resistors, coils, and capacitors, it is desirable to assign half the value of the two-terminal component for resistors and coils, and twice the value of the two-terminal component for capacitors, as node attribute information according to circuit theory. In addition, the power supply is defined as the same value as the voltage or current of the two-terminal component, regardless of whether it is divided or not. This is because if the voltage or current is halved or doubled, it may not work below the minimum voltage, or it may be destroyed by exceeding the rated voltage, so it is undesirable to change it regardless of whether it is divided or not. In the case where the direction of the current is directional, such as a DC voltage source or a DC current source, a graph network with directionality can be created by decomposing the nodes in parallel and giving a direction to at least one edge for each decomposed node, as shown in FIG. 34. In addition to DC voltage sources and DC current sources, it can also be applied to circuit components with directionality such as diodes and directional couplers. At this time, by assigning different characteristic values to the node attributes of each decomposed node, information on different characteristics can be propagated in the forward and reverse directions. In this case, by dividing the circuit components with directionality in the graph in Figure 30 in parallel and assigning different types of node attributes to each circuit component using a one-hot vector, the inference accuracy for the test data is calculated as the average of the maximum values of 10 trials, which is 97.82%, an average improvement of 0.1% from the 97.72% in Figure 30.
FIG. 35A is a circuit diagram showing an electric circuit including a multi-element component, and FIG. 35B is a graph network showing the electric circuit of FIG. 35A. The characteristics in the forward and reverse directions can be obtained by decomposing for each terminal as in FIG. 35B, but when it is known that the characteristics in the forward and reverse directions are different, it is preferable to decompose in parallel. In addition, when the nodes are decomposed in series as in FIG. 35B, when focusing on V:1 and V:2, the weight matrix of the graph neural network and the activation function, which is a nonlinear function, are applied in the order of X:1, V:1, V:2, and G, and the characteristics in the reverse direction are different from those of G, V:2, V:1, and X:1 due to the effect of the activation function. Therefore, different characteristics in the forward and reverse directions can be obtained by learning. However, by dividing circuit components having directionality in parallel and combining them with edges having direction, the characteristics in the forward and reverse directions can be explicitly changed without relying on learning, which is desirable because it not only reduces the amount of calculations but also improves the inference accuracy.

Details will be given later, but the features of nodes, such as circuit constants, can be stored as a graph network by assigning them as real numbers to one element of a one-hot vector that holds node attribute information. In addition, if the dynamic range of the feature is large and it will be rounded by computer, it is desirable to assign a value obtained by applying a logarithmic function to the feature to one element of the one-hot vector.

Diodes can have different characteristics as graph network information by defining the anode as 0 and the cathode as 1 in the node attribute information of the two-terminal decomposition component. Note that 0 and 1 can be reversed, and any integer or real number other than 0 or 1 can be used as long as they can be distinguished. Although directional couplers have three or more terminals, the direction of signal flow can be defined by setting different values in the attribute information of the two-terminal decomposition component that serves as the input and output, just like diodes. When defining diodes and directional couplers as model numbers, this can be achieved by storing the model number as one element of the node attribute information and defining 0 and 1 as one-hot vectors for the other node attribute information. The netlist is as follows:

V1;IN 0 3.3
XU1;N002 N003 IN 0 N001 IN N002 N004 LT3489
L1;IN N001 2.2u
D1;N001 OUT 1N5818
C1; OUT 0 20u
R1; OUT N003 28.7K
R2; N003 0 5.23K
C2;N004 0. 001u
Rload;OUT 0 13
V1-1;IN Wire1 3.3
V1-2;0 Wire1 3.3
L1-1; IN Wire2 1.1u
L1-2;N001 Wire2 1.1u
D1-1;N001 Wire3 1N5818
D1-2; OUT Wire3 1N5818
C1-1; OUT Wire4 40u
C1-2;0 Wire4 40u
R1-1; OUT Wire5 14.35K
R1-2; N003 Wire5 14.35K
R2-1; N003 Wire6 2.615K
R2-2;0 Wire6 2.615K
C2-1;N004 Wire7 0.002u
C2-2;0 Wire7 0.002u
Rload-1; OUT Wire8 6.5
Rload-2;0 Wire8 6.5

When removing two-terminal circuit components from the component list and inter-component connection list, all information about the two-terminal circuit components has been transferred to two-terminal disassembled components by the above process, so removing the two-terminal circuit components does not cause information degradation. Therefore, the wiring connected to the two-terminal circuit components is disconnected, and the following netlist from which the two-terminal circuit components have been removed is the final output. Note that, as explained in the third embodiment, the above process has been explained using a netlist for ease of understanding, but the same results can be obtained using a component list and inter-component connection list that are uniquely created from the netlist.

XU1;N002 N003 IN 0 N001 IN N002 N004 LT3489
V1-1; IN L1 3.3
V1-2;0 L1 3.3
L1-1;IN L2 1.1u
L1-2; N001 L2 1.1u
D1-1;N001 L3 1N5818
D1-2; OUT L3 1N5818
C1-1; OUT L4 40u
C1-2;0 L4 40u
R1-1; OUT L5 14.35K
R1-2; N003 L5 14.35K
R2-1; N003 L6 2.615K
R2-2;0 L6 2.615K
C2-1; N004 L7 0.002u
C2-2;0 L7 0.002u
Rload-1; OUT L8 6.5
Rload-2;0 L8 6.5

In the second embodiment, the decomposition of a two-terminal connection point into a two-terminal decomposition point was described, but the same processing can be performed by treating the two-terminal connection point as a two-terminal circuit component and the two-terminal decomposition point as a two-terminal decomposition component. However, while in the second embodiment, it is sufficient to input the same elements into the node attribute information of the two-terminal decomposition point, in the fifth embodiment, the circuit constants are based on circuit theory, and resistors and coils must be halved and capacitors must be doubled. In particular, when processing diodes and directional couplers with a graph network, they generally need to be processed as directed graphs, but as in the fifth embodiment, by making at least one element of the node attribute information a different element for the anode and cathode, they can be processed as undirected graphs. In addition, anodes and cathodes can be explicitly created by using directed graphs and decomposing components in parallel. Furthermore, in avalanche diodes and Zener diodes that also use reverse bias, if a directed graph is used with a single node, the reverse bias cannot be taken into account. Therefore, by converting the graph using the method according to embodiment 5 and adding information as node attribute information and processing the undirected graph or the nodes decomposed in parallel as a directed graph, processing can be performed with fewer exceptions and reduced information degradation.

As explained in the third embodiment, for both multi-terminal and two-terminal components, the terminal number can be used as one element of a matrix that is the node attribute information of the terminal component or two-terminal decomposition component to retain information. This information would disappear in the conventional method of defining a multi-element component as a single node, and the ability to retain this information is a special effect of the fifth embodiment. In addition, for two-terminal components, the input-output relationship usually disappears when converted to a graph network, but as a two-terminal decomposition component, the information can be retained by leaving the input or output as a numerical value in at least one element of each node attribute information. In addition, negative circuit constants such as negative resistance and negative inductance can occur, but when decomposing into two-terminal decomposition components, just as with resistance and inductance (coils) that have positive circuit constants, the node attribute information can be set to half the circuit constant.

FIG. 35B is a graph network obtained by applying the method of embodiment 5 to the graph network of the circuit shown in FIG. 30 of embodiment 3. In FIG. 35B, the two-terminal components of the power supply V, coil L, capacitor C, and resistor R are divided into two terminals. FIG. 36 is a graph showing the inference results for test data in a graph neural network with the same conditions as FIG. 30 except for the input data. Under these conditions, the average of the maximum inference results obtained by 10 learnings was 97.50%. This is 0.2% lower than the 97.72% shown in FIG. 30 and 0.3% lower than the 97.82% shown in FIG. 34, but it means that the inference accuracy is 0.3% higher than the 97.20% of the conventional method that does not include virtual components or two-terminal decomposition components shown in FIG. 26B. The calculation time was 12 minutes, which was longer than in Figures 26B and 30 due to the increased number of nodes, but was less than twice that of the conventional example in Figure 26B, a small increase compared to the improvement in accuracy. This improvement in accuracy can be attributed to the reduction in information degradation during conversion from a netlist to a graph network by using two-terminal decomposition components.

When simulating an actual electric circuit, components such as coils, capacitors, resistors, and diodes have the characteristic that, when subjected to AC signals, the coil, resistor, and diode have floating capacitance (also called parasitic capacitance) in parallel, and the capacitor has residual inductance in series. In such cases, the same processing can be achieved by breaking down the circuit components into multiple two-terminal components, for example by giving the capacitor a structure with residual inductance in series, and attaching a capacitor that acts as floating capacitance in parallel to the coil as a node.

In the above, the circuit components and ground are nodes and the wiring is edges, but as shown in Figure 37, it is also desirable to treat the wiring including the circuit components and ground as nodes and connect related nodes with edges. By doing so, the number of decomposition nodes X:1 to X:6 is equal to the number of edges connected to the decomposition nodes. As a result, the decomposition nodes are connected only to virtual nodes and wiring nodes, and even if this conversion is performed, the circuit information can be converted to a graph network without loss. Furthermore, when changed in this way, the inference accuracy for the test data is 97.22%, and although the inference accuracy drops by about 0.5% due to the inclusion of wiring nodes that are unrelated to the inference, a high inference accuracy is obtained. The reason for the drop in inference accuracy is that in this experiment, a three-layer graph neural network was used, so it was possible to consider up to the node attributes of the circuit components three steps away, whereas the presence of wiring nodes meant that only the characteristics of the node of the circuit component one step away could be considered, which is thought to have reduced the inference accuracy. To solve this problem, learning and inference can be performed using a graph neural network with five or more layers, but the time required for learning and memory usage increase exponentially, so it may not be possible to use it depending on the size of the circuit.

Next, the node attribute information shown in the first to fifth embodiments will be described with reference to Figs. 38 to 43. Fig. 38 is a schematic diagram in which the node attribute information n15d, n16d, n17d, and n18d are assigned to the virtual node and decomposition node shown in the first embodiment, respectively, taking the first embodiment as an example. For example, the node attribute information is a matrix with 1 row and N columns, or a tensor that can be reversibly transformed into a matrix with 1 row and N columns, and the characteristics of the node are defined by assigning values such as numerical values or character strings to the N matrix elements. In particular, the fifth embodiment is characterized in that the number of elements of the virtual node and the decomposition node is equal. This is equivalent to the fact that the virtual node and the decomposition node each have N elements, where N is a natural number. In Fig. 38, if N is 5 and the elements of the node attribute information are a1 to a5, b1 to b5, c1 to c5, and d1 to d5, the text data of the first embodiment is as follows:

Virtual node; virtual node-decomposition node 1, virtual node-decomposition node 2, virtual node-decomposition node 3
Decomposition node 1; edge 1, virtual node - decomposition node 1
Decomposition node 2; edge 2, virtual node - decomposition node 2
Decomposition node 3; edge 3, virtual node - decomposition node 3

In addition, it can be expressed by the following information:

Virtual nodes: a1, a2, a3, a4, a5
Decomposition node 1: b1, b2, b3, b4, b5
Decomposition node 2: c1, c2, c3, c4, c5
Decomposition node 3: d1, d2, d3, d4, d5

In addition, this is an important element in graph neural networks, as the processing method involves learning by contracting, combining, and embedding node attribute information between connected nodes using a weight matrix obtained through learning. In particular, in graph neural networks, the weight matrix is multiplied for each column and combined for each element, so it is desirable to provide node attribute information as a one-hot vector. This is because unrelated elements in a one-hot vector are 0, so multiplication will be 0 regardless of what elements the weight matrix contains, and even after combining, the multiplication between unrelated elements, i.e. the Hadamard product, will be 0. Conversely, if there is a component with a value of 1 in a one-hot vector, even if that information is multiplied by a weight matrix with non-zero elements in multiple hidden layers, it will propagate as a non-zero element, so the information is less likely to degrade. This means that there is orthogonality.

Next, the attribute information of the virtual node will be explained. The decomposition node has specific elements such as domain information in the first embodiment, and terminal numbers, circuit constants, and part model numbers in the third embodiment, but the virtual node can be freely defined. It is desirable to enter user and company information in the social network dataset in the first embodiment, and book information in the paper citation dataset in the virtual node. However, the node attribute information of the virtual node can be any type, such as an integer, real number, or character string. However, when processing with a graph neural network, only numeric values are accepted, so non-numeric character strings must be replaced with unique numeric values.

Also, in order to reduce the range of elements that the weight matrix can take, it is desirable to normalize each element of the node attribute information to a real number between 0 and 1. This is because activation functions such as the ReLU (Rectified Linear Unit) function and the tanh function, which are used for nonlinear processing after the weight matrix, are often designed to be sensitive to 0 to 1 or -1 to +1. Also, when the node attribute information of the decomposition node is clear, it is desirable to set the node attribute information of the virtual node to the average value (additive average) of the attribute information of the connected decomposition node, as shown in Figure 39. However, when it is a virtual node or there is information specific to the virtual node, these elements will be lost if all elements are averaged, so in that case it is desirable to set only the average value except for some columns that have information specific to the virtual node. This is because in the calculation of the graph neural network, a weight matrix is applied to take the sum, but by entering elements close to the sum in advance, the calculation can be speeded up and it is less likely to fall into a minimum value.

Also, for faster calculations and data sets that are not prone to falling into a minimum value, it is possible to set all the node attribute information of the virtual nodes to 0, which is desirable because the node attribute information and graph features of the virtual nodes can be obtained without prior knowledge provided by a human. In addition, 1 or a random number other than 0 may be used as the initial value, but if one-hot vectors are used for even a portion of the attribute information columns, using 1 or a random number will result in loss of orthogonality and even non-existent elements will be generated, so using 0 or the average value of the node attribute information of adjacent decomposition nodes is a desirable method for reducing information degradation. Furthermore, Figure 40A is a graph network showing a multi-element component with three terminals, and Figure 40B is a schematic diagram in which unique numerical values are assigned to one or more node attribute information of virtual nodes and decomposition nodes based on domain information and terminal information. In this figure, 0 is assigned to the virtual nodes, and 1 to 3 corresponding to the terminal numbers of the specific nodes are assigned to the decomposition nodes, which reduces information degradation of the terminal numbers. In the example of Figure 40B, the terminal numbers are 1 to 3, but they can be defined in any way as long as they correspond to the terminal numbers of the specific nodes.

FIG. 41 is a schematic diagram showing that the number of elements of the node attribute information n22d and n23d at the two-terminal decomposition point described in the second embodiment is equal. As with the relationship between the virtual node and the decomposition node in FIG. 38, by making the number of pieces of attribute information equal, the processing as a graph network can be averaged and processing can be performed by a graph neural network.

FIG. 42 is a schematic diagram showing how different values are assigned to the input and output sides of at least one element of node attribute information at a two-terminal decomposition point. For example, as shown in FIG. 42, by setting the input side of the attribute information to 0 and the output side to 1, the characteristics of the two-terminal decomposition point can be retained as graph information.

FIG. 43 is a schematic diagram showing how to equalize the number of elements in the matrices forming the attribute information of the nodes in a graph network. In FIGS. 38 to 42, the attribute information of the virtual nodes, decomposition nodes, and two-terminal decomposition points was explained individually, but as shown in FIG. 43, by making the number of node attribute information n01d, n02d, and n03d in the graph network equal, it is possible to eliminate the need for exception handling when processing information on the graph network. In addition, when performing graph classification in a graph neural network, it is necessary to use multiple graph networks, but by standardizing the number of elements of the node attribute information held by all graph networks used and defining the information held by each column, it becomes possible to process multiple graph networks in parallel at once, which is excellent in terms of reducing calculation time and simplifying processing, and has a special effect not seen in the past.

Note that this disclosure allows for free combinations of each embodiment, modifications to any of the components of each embodiment, or the omission of any of the components of each embodiment.

The information processing device according to the present disclosure can be used, for example, to convert graph data showing an electrical circuit into another graph structure and suppress degradation of information when performing graph processing.

10 graph data acquisition unit, 20 node extraction unit, 30 graph generation unit, 31 node decomposition unit, 32 edge modification unit, 100 information processing device, G1 first graph, G1' second graph, G1'' second graph, G1'' second graph, g1' subgraph, g1'' subgraph, g1''' subgraph, e11 first edge, e12 second edge, e15 edge, e16 edge, n13 original node (specific node), n15 first node, n16 second node, n18 connecting node (virtual node).

Claims (15)

a graph data acquisition unit that acquires first graph data indicating a first graph having an original node having first information and second information, a first edge associated with the first information and connected to the original node, and a second edge associated with the second information and connected to the original node;
a graph generating unit configured to generate second graph data representing a second graph in which the original node is replaced with a subgraph having a plurality of nodes including a first node corresponding to the first information and a second node corresponding to the second information in the first graph,
the graph generation unit generates the second graph data such that, in the second graph, the first edge is connected to the first node and the second edge is connected to the second node. 2. The information processing device according to claim 1, wherein the graph generation unit divides the first edge into a 1-1 edge and a 1-2 edge in the second graph, and generates the second graph data so as to form a graph in which one end of the 1-1 edge is connected to the first node and one end of the 1-2 edge is connected to the second node. 3. The information processing apparatus according to claim 2, wherein the first-second edge is an edge having directionality. 4. The information processing device according to claim 1, wherein the graph generation unit generates the second graph data so that the second graph has a new edge having one end connected to the first node and the other end connected to the second node. the graph generation unit generates the second graph data such that the plurality of nodes of the subgraph have a connection node for connecting the first node and the second node to each other;
The information processing apparatus according to claim 1 , wherein the connection node is a part of the subgraph. 6. The information processing device according to claim 5, wherein the graph generation unit generates the second graph data so that the number of nodes, excluding the connection node, among the plurality of nodes in the subgraph is equal to the number of edges, including the first edge and the second edge, connected to the original node in the first graph. 7. The information processing device according to claim 5, wherein the graph generation unit generates the second graph data such that, among the plurality of nodes in the subgraph, each node other than the connecting node and the connecting node are connected to each other by one edge. 2. The information processing device according to claim 1, wherein, when first graph data indicating a first graph having an original node having N pieces of information, where N is a natural number equal to or greater than two, is acquired by the graph data acquisition unit, the graph generation unit generates second graph data indicating a second graph in which the original node in the first graph is replaced with a subgraph having N nodes different from each other and associated with each of the N pieces of information. 2. The information processing device according to claim 1, wherein, when first graph data indicating a first graph having an original node to which N edges, where N is a natural number equal to or greater than two, are connected, is acquired by the graph data acquisition unit, the graph generation unit generates second graph data indicating a second graph in which the original node in the first graph is replaced with a subgraph having N nodes different from each other corresponding to each of the N or less edges. the first graph is a graph showing an electric circuit,
the original node is a node indicating a component included in the electric circuit,
the first information and the second information are information for identifying a terminal of the component,
The information processing device according to claim 1 , wherein the first edge and the second edge are wirings connected to the component. the first graph is a graph showing an electric circuit,
the original nodes are nodes that indicate components and wiring included in the electric circuit,
the first information and the second information are information for identifying a terminal of the component,
10. The information processing apparatus according to claim 1, wherein the first edge and the second edge are lines connecting nodes indicating the components and wiring. the first graph is a graph showing an electric circuit,
The original node is a multi-terminal component having three or more terminals (N terminals) including a semiconductor included in an electric circuit,
the N terminals are information for identifying terminals of the multi-terminal component,
10. The information processing apparatus according to claim 6, wherein the subgraph constituting the multi-terminal component is a star graph with a connection node at its center. the first graph is a graph showing an electric circuit,
The original node is a diode or a battery included in the electric circuit,
the first information and the second information are information for identifying a positive electrode and a negative electrode of the diode or the battery,
7. The information processing device according to claim 1, wherein the first edge and the second edge are wirings connected to the diode or the battery. the first graph is a graph showing an electric circuit,
The original node is a diode or a battery in an electric circuit;
Dividing the first edge into a 1-1 edge and a 1-2 edge;
Dividing the second edge into a second-1 edge and a second-2 edge;
one end of the 1-1 edge is connected to the first node, one end of the 1-2 edge is connected to the second node, and the other end of the 1-1 edge and the other end of the 1-2 edge are connected to a common node 1;
one end of the 2-1 edge is connected to the first node, one end of the 2-2 edge is connected to the second node, and the other end of the 2-1 edge and the other end of the 2-2 edge are connected to a common node 2;
the first-second edge has a direction from the common node 1 to the second node,
4. The information processing apparatus according to claim 3, wherein the 2-1 edge has a direction from the common node 2 to the first node. An information processing method performed by an apparatus including a graph data acquisition unit and a graph generation unit,
a step of the graph data acquisition unit acquiring first graph data indicating a first graph having an original node having first information and second information, a first edge associated with the first information and connected to the original node, and a second edge associated with the second information and connected to the original node;
a step of generating second graph data indicating a second graph in which the original node in the first graph is replaced with a subgraph having a plurality of nodes including a first node corresponding to the first information and a second node corresponding to the second information,
the graph generation unit generates the second graph data such that, in the second graph, the first edge is connected to the first node and the second edge is connected to the second node.

Images