Method and system for incremental metapath storage and dynamic maintenance

Patent metadata

Field	Value
Publication number	US-12572594-B2
Application number	US-202418610495-A
Country	US
Kind code	B2
Filing date	Mar 20, 2024
Priority date	Mar 30, 2023
Publication date	Mar 10, 2026
Grant date	Mar 10, 2026

Abstract

A method for incremental metapath storage and dynamic maintenance is provided, which includes, reformatting metapath instances, from a designated heterogeneous graph and of a designated metapath type, into path graphs; executing graph updating tasks and performing dynamic maintenance on the updated path graphs, traversing the path graph to obtain the location of metapath updates and update the path graph; for metapaths with length greater than 2 and with symmetrical central portion, central merge operation is performed to simplify path graph and perform subsequent restoration operation; and directly perform restoration operation on path graphs that do not meet the merging conditions. The present disclosure utilizes characteristics of graph update to obtain locality of metapath updates, and combines internal relationship characteristics of metapath instances to greatly speed up metapath generation and achieve real-time inference of dynamic heterogeneous graph models.

First claim

What is claimed is:

1 . A method performed by a computing system comprising a processor and memory for reducing data access during real-time inference of a heterogeneous graph neural network by utilizing incremental metapath storage and dynamic maintenance, the method comprising the steps of:
reformatting metapath instances, from a designated heterogeneous graph and of a designated metapath type, into path graphs; executing graph updating tasks and performing the dynamic maintenance on the path graphs; and making triggering-condition queries on the path graphs having undergone the dynamic maintenance, wherein the step of making triggering-condition queries comprises the substeps of:
performing a merge operation on path graphs that meet triggering conditions; and
performing a restoration operation on path graphs that do not meet the triggering conditions;
storing the path graphs on one or more readable storage media selected from the group comprising electric connection having one or more leads, portable disks, hard drives, random-access memory (RAM), read-only memory (ROM), erasable programmable read-only memory (EPROM or flash memory), optical fibers, portable compact disc read-only memory (CD-ROM), optical disks, magnetic disks, or any combination thereof, wherein the computing system receives changes to the designated heterogenous graph, wherein the changes comprise insertions of new vertices or new edges and/or deletions of vertices or edges, wherein the computer system incrementally maintains stored path graphs based on the received changes and reduces data access during real-time inference of a heterogenous graph neural network by utilizing the stored path graphs.

2 . The method of claim 1 , wherein the step of reformatting metapath instances, from a designated heterogeneous graph and of a designated metapath type, into path graphs comprises the substeps of:
in respect to the designated heterogeneous graph and the designated metapath type, matching the metapath instances satisfying metapath definitions; and traversing the metapath instances so as to reformat the metapath instances into the path graphs.

3 . The method of claim 2 , wherein the step of executing graph updating tasks and performing the dynamic maintenance on the path graphs comprises the substeps of:
determining whether types of vertices and/or edges added into or deleted from the path graphs affect the existing metapath instances, and if yes, executing a subsequent substep, or if not, skipping the subsequent substeps; if the graph updating tasks involve deletion of the edges, traversing a set of vertices in the path graphs that are of types corresponding to the types of the edges deleted, and performing a deletion operation on the set of vertices; if the graph updating tasks involve addition of the edges, traversing a set of neighbors of a set of vertices in the path graphs that are of types corresponding to the types of the edges, so as to determine locations of vertices or edges to be added into the path graphs; or if the graph updating tasks involve addition or deletion the vertices, performing an addition operation or a deletion operation for multiple said edges instead, and repeating the step for graph updating tasks involving deletion of the edges or graph updating tasks involving addition of the edges.

4 . The method of claim 2 , wherein the substep of, in respect to the designated heterogenous graph and the designated metapath type, matching the metapath instances satisfying the metapath definitions comprises the substeps of:
in respect to the designated heterogenous graph and the designated metapath type, matching the metapath instances satisfying the metapath definitions in sequence beginning from a certain vertex in the designated heterogenous graph; repeating the previous substep until the designated heterogenous graph has been traversed and all said metapath instances have been acquired; and as for metapath instances of multiple metapath types, repeating the previous substeps until all of the metapath instances of each the designated metapath types have been acquired.

5 . The method of claim 2 , wherein the substep of traversing the metapath instances so as to reformat the metapath instances into the path graphs comprises:
traversing all of the metapath instances of the designated metapath type, and reformatting the edges of each of the metapath instances into vertices for storage; and as for all the metapath types existing in the initial graph, repeating the previous step so as to acquire the path graphs of the metapath instances of all said metapath types.

6 . The method of claim 5 , wherein the vertices include information of a starting vertex and a target vertex related to the edge in the corresponding instance.

7 . The method of claim 5 , wherein if two edges in a metapath instance have connected vertices, the two reformatted vertices are connected by edges.

8 . The method of claim 1 , wherein the substep of performing a merge operation on the path graphs that meet the triggering conditions comprises the substeps of:
acquiring metapaths in all of the designated metapath types that satisfy the metapath definitions; acquiring path graphs that correspond to the metapaths that satisfy the metapath definitions; and performing the merge operation on a central portion of each of the path graphs.

9 . The method of claim 8 , wherein the metapaths that satisfy the metapath definitions are those metapaths that have a length greater than a predetermined length and have a symmetrical central portion.

10 . The method of claim 1 , wherein the substep of performing a restoration operation on the path graphs that do not meet the triggering conditions comprises the substeps of:
sequentially traversing path graphs that have not undergone the merge operation, so as to obtain all of the metapath instances; and traversing path graphs that have undergone the merge operation from the central portion thereof toward two sides thereof, so as to obtain all of the metapath instances.

11 . A system for reducing data access during real-time inference of a heterogeneous graph neural network by utilizing incremental metapath storage and dynamic maintenance, wherein the system comprises:
a processor coupled to a memory; a maintenance module, for dynamically maintaining path graphs and sending the path graphs to a restoration module in a workload-balancing manner; the restoration module, for performing a restoration operation on the path graphs that have been updated by the maintenance module, so as to obtain all metapath instances, and performing an aggregation operation on the metapath instances; one or more readable storage media, for storing the path graphs, selected from the group comprising electric connection having one or more leads, portable disks, hard drives, random-access memory (RAM), read-only memory (ROM), erasable programmable read-only memory (EPROM or flash memory), optical fibers, portable compact disc read-only memory (CD-ROM), optical disks, magnetic disks, or any combination thereof; and wherein the system receives changes to the designated heterogenous graph, wherein the changes comprise insertions of new vertices or new edges and/or deletions of vertices or edges; wherein the computer system incrementally maintains the stored path graphs based on the received changes and reduces data access during real-time inference of a heterogenous graph neural network by utilizing the stored path graphs.

12 . The system of claim 11 , wherein the maintenance module comprises one or more maintenance sub-modules, wherein each of the maintenance sub-modules comp

Assignees

• Univ Huazhong Science Tech
• Zhejiang Lab

Inventors

• Zheng Long
• He Haiheng
• Liao Xiaofei
• Jin Hai
• Chen Dan
• Huang Yu

Classifications

• G06F40/30 Primary

  Semantic analysis · CPC title

• G06F16/00

  Information retrieval; Database structures therefor; File system structures therefor · CPC title

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06N3/042

  Knowledge-based neural networks; Logical representations of neural networks · CPC title