US-20260127446-A1 - ACCELERATION METHOD AND SYSTEM FOR HETEROGENEOUS GRAPH NEURAL NETWORKS BASED ON META-PATH GRAPHS

US20260127446A1US 20260127446 A1US20260127446 A1US 20260127446A1US-20260127446-A1

Abstract

An acceleration method for heterogeneous graph neural networks based on meta-path graphs is provided, including: constructing a meta-path graph by arranging all meta-path instances in graph form, based on a given heterogeneous graph and specified types of meta-paths; partitioning the meta-path graph to obtain multiple meta-path subgraphs, which are further divided by workload; performing layer-based encoding on the meta-path instances according to the workload distribution; merging all meta-path instance slice encodings based on inter-layer relationships in the meta-path graph to obtain meta-path instance encodings; and performing intra-meta-path aggregation and inter-meta-path aggregation to compute the final features of the target vertices. The present method significantly reduces redundant computations in heterogeneous graph neural network, thereby improving model inference efficiency.

Inventors

Long Zheng
Haiheng HE
Xiaofei Liao
Hai Jin
Haifeng Liu
Yu Huang

Assignees

HUAZHONG UNIVERSITY OF SCIENCE AND TECHNOLOGY

Dates

Publication Date: 20260507
Application Date: 20250328
Priority Date: 20241105

Claims (20)

1 . An acceleration method for heterogeneous graph neural networks based on meta-path graphs, the method comprising: constructing a meta-path graph by arranging all meta-path instances in graph form, based on a given heterogeneous graph and specified types of meta-paths; partitioning the meta-path graph to obtain multiple meta-path subgraphs; dividing the meta-path subgraphs by workload; performing layer-based encoding on the meta-path instances according to the workload distribution, and merging all meta-path instance slice encodings based on inter-layer relationships in the meta-path graph, so as to obtain meta-path instance encodings; and performing intra-meta-path aggregation and inter-meta-path aggregation to compute final features of target vertices.
2 . The acceleration method of claim 1 , wherein the step of constructing the meta-path graph comprises: extracting vertices and edges from the heterogeneous graph according to the types appearing in the meta-paths; and copying repeated vertices and edges into the previously constructed portion of the meta-path graph, and expanding further according to the meta-path schema, so as to form a complete meta-path graph.
3 . The acceleration method of claim 1 , wherein the step of partitioning the meta-path graph comprises: collecting the vertices in central layers of the meta-path graph, so as to obtain all central-layer vertices of the meta-path graph; dividing the central-layer vertices into multiple batches, each batch containing an equal number of the central-layer vertices; and traversing the meta-path graph from all the vertices in each batch, respectively, in both outgoing and incoming edge directions, so as to obtain the meta-path subgraphs corresponding to each batch.
4 . The acceleration method of claim 1 , wherein the step of dividing the meta-path subgraphs by workload comprises: dividing the meta-path subgraph into at least two sections by layer, with each section containing contiguous layers, thus forming a meta-path slice graph that contains part of the meta-path instances; and traversing the meta-path slice graphs in sequence of layers, so as to obtain slices for all the meta-path instances.
5 . The acceleration method of claim 1 , wherein the meta-path instance encodings are obtained through: encoding the meta-path instance slices to obtain partial encodings for the meta-path instances; using edge relationships among different layers to re-encode the meta-path instance slice encodings in different subgraphs, so as to obtain all the meta-path instance encodings; performing intra-meta-path aggregation for the same meta-path subgraph, so as to obtain feature information of the target vertices; and performing inter-meta-path aggregation for the feature information of the target vertices shared across different meta-path graphs, so as to compute the final features of all the target vertices.
6 . The acceleration method of claim 5 , wherein the step of encoding the meta-path instance slices comprises: determining whether there is any sequential part that is identical among meta-path definitions corresponding to the meta-path graphs; and if yes, implementing priority-based layer division; otherwise, implementing layer-based division.
7 . The acceleration method of claim 2 , wherein the step of constructing the meta-path graph further includes: analyzing the type of each vertex and edge in the meta-path and recording the definition of each type in the heterogeneous graph.
8 . The acceleration method of claim 7 , wherein the step of constructing the meta-path graph further includes: using database queries or graph traversal algorithms to extract vertices and edges corresponding to each type in the meta-path from the heterogeneous graph, ensuring that the extracted edges connect vertices in accordance with the order and type requirements of the meta-path.
9 . The acceleration method of claim 4 , wherein the method further includes: during the traversal, extracting the vertices and edges related to the meta-path to form complete meta-path instance slices, and recording the structural features and connectivity of each meta-path instance slice.
10 . The acceleration method of claim 5 , wherein the method further includes: after encoding for all meta-path instances of the meta-path graphs, for every meta-path subgraph, aggregating the meta-path instances of the same target vertex, wherein an aggregation method is used to integrate the feature information of the same target vertex and generate the feature representation for each target vertex, so as to ensure consistency and integrity of the information throughout the aggregation process.
11 . An acceleration system for heterogeneous graph neural networks based on meta-path graphs, the system comprising: a construction module, for constructing a meta-path graph by arranging all meta-path instances in graph form, based on a given heterogeneous graph and specified types of meta-paths; a partitioning module, for partitioning the meta-path graph to obtain multiple meta-path subgraphs; a computation module, for dividing the meta-path subgraphs by workload; and a merging module, for performing layer-based encoding on the meta-path instances according to the workload distribution, and merging all meta-path instance slice encodings based on inter-layer relationships in the meta-path graph, so as to obtain meta-path instance encodings; and for performing intra-meta-path aggregation and inter-meta-path aggregation to compute final features of target vertices.
12 . The acceleration system of claim 11 , wherein the construction module comprises multiple construction sub-modules for constructing the meta-path graphs, wherein the construction sub-modules each comprise an extraction module and an expansion module, wherein the extraction module extracts vertices and edges from the heterogeneous graph according to the types appearing in the meta-paths; and the expansion module copies repeated vertices and edges into the previously constructed portion of the meta-path graph, and expands further according to the meta-path schema, so as to form a complete meta-path graph.
13 . The acceleration system of claim 12 , wherein the partitioning module comprises multiple partitioning sub-modules, which are used to partition the meta-path graphs into multiple subgraphs, and after the partitioning is completed, the resulting meta-path subgraphs are sent to the computation module.
14 . The acceleration system of claim 13 , wherein the computation module comprises multiple computation sub-modules, wherein the computation sub-modules divide the meta-path subgraphs by workload according to layers, so as to obtain multiple meta-path slice graphs and perform encoding computations; and the computation sub-modules each include a loading module and an encoding module, wherein the loading module divides the meta-path subgraph into at least two sections by layer, with each section containing contiguous layers, thus forming a meta-path slice graph that contains part of the meta-path instances; and the encoding module traverses the meta-path slice graphs in sequence of layers, so as to obtain slices for all the meta-path instances.
15 . The acceleration system of claim 14 , wherein the merging module comprises multiple merging sub-modules, wherein the merging sub-modules each include an encoding-merging module, an intra-meta-path aggregation module, and an inter-meta-path aggregation module, wherein the code-merging module encodes the meta-path instance slices to obtain partial encodings for the meta-path instances, and uses edge relationships among different layers to re-encode the meta-path instance slice encodings in different subgraphs, so as to obtain all the meta-path instance encodings; the intra-meta-path aggregation module performs intra-meta-path aggregation for the same meta-path subgraph, so as to obtain feature information of the target vertices; and the inter-meta-path aggregation module performs inter-meta-path aggregation for the feature information of the target vertices shared across different meta-path graphs, so as to compute the final features of all the target vertices.
16 . The acceleration system of claim 15 , wherein the extraction module includes a first port for receiving heterogeneous graph data and a second port for sending extracted data; and the expansion module includes a third port for receiving extracted data and a fourth port for sending the completed meta-path graph, wherein the second port and the third port are in connection with each other.
17 . The acceleration system of claim 16 , wherein the expansion module sends the completed meta-path graph through the fourth port to a fifth port of the partitioning module, achieving a seamless connection from extraction to expansion.
18 . The acceleration system of claim 17 , wherein the partitioning submodules receive the meta-path graph from the construction module via the fifth port and send the partitioned meta-path subgraphs to the load module via a sixth port, with the sixth port connected to a seventh port of the load module.
19 . The acceleration system of claim 18 , wherein the load module receives the meta-path subgraph through the seventh port and sends the generated meta-path slice graph to the encoding module via an eighth port, with the eighth port in structured data exchange connection with a ninth port of the encoding module.
20 . The acceleration system of claim 19 , wherein the encoding module receives the meta-path slice graph through the ninth port and sends the encoded meta-path instance slice graph to the merging module through a tenth port, with the tenth port in Unicode-supported connection with an eleventh port of the merging module.

Description

This application claims the benefit of Chinese Patent Application No. CN 202411569136.4, filed on Nov. 5, 2024, which is hereby incorporated by reference as if fully set forth herein. BACKGROUND OF THE APPLICATION 1. Technical Field The present disclosure relates to acceleration of heterogeneous graph neural networks (HGNNs), and more particularly to an acceleration method and system for heterogeneous graph neural networks based on meta-path graphs. 2. Description of Related Art Heterogeneous graphs represent a graph structure in which vertices and edges have different types. In a heterogeneous graph, connections between vertices and/or with edges can be diverse and complex, reflecting various types of relationships in the real world. Key concepts in heterogeneous graphs include: 1. Vertex Type. In a heterogeneous graph, vertices can be classified into different types, each with specific attributes and semantics. For example, in a social network, vertex types may include users, groups, and pages. 2. Edge Type. Similarly, edges in a heterogeneous graph can represent various types of relationships between vertices. For example, in a social network, edge types may represent “friend” relationships, “like” relationships, or “comment” relationships. 3. Meta-Path. A meta-path defines a specific type of connection between vertices. It describes how a path, composed of a sequence of vertices and edge types, connects one vertex to another. Meta-paths are crucial tools for capturing the complex relationships between vertices in a heterogeneous graph. A heterogeneous graph neural network (HGNN) is a neural network model designed for processing heterogeneous graph data. As compared to common graph neural networks (GNNs), HGNNs can effectively handle different types of vertices and edges in heterogeneous graphs. The development of HGNNs can be traced back to common graph representation learning methods, such as vertex embedding and graph embedding. With the advancement of deep learning, GNNs were introduced to learn representations of graph data. Due to the complexity of heterogeneous graphs, researchers have proposed various GNN-based heterogeneous graph models to address challenges posed by heterogeneous graph data. These models aim to learn representations for the different types of vertices in a heterogeneous graph, enabling the transmission and learning of information through the connections between vertices. Multivariate mapping relationships between meta-paths and heterogeneous graphs often lead to a huge number of meta-path instances, and maintenance of such massive meta-path instances presents a significant challenge. Early research used breadth-first search (BFS) to match meta-path instances. A BFS-based HGNN approach first enumerates all meta-path instances, and stores them in large memory spaces that may be thousands of times larger than the original graph. These instances can then be directly accessed by the encoder. However, because each meta-path instance is stored separately, the encoding process becomes unavoidably affected by redundant computations. Furthermore, encoding meta-path instances by vertex index order can lead to load imbalances. A recent solution employs depth-first search (DFS) for traversing (to generate) meta-path instances from the original graph. The DFS-based approach matches meta-path instances during construction of a semantic graph. Once a meta-path instance is matched, its semantic information will be encoded into the embedding and used to incrementally update the semantic graph before finally being discarded. Therefore, a DFS-based HGNN can save storage overheads significantly because the meta-path instances no longer need to be stored. However, discarding the meta-path instances after use introduces additional overheads, as the system must re-match meta-path instances from the original graph during model inference, which increases inference latency. Although the DFS-based approach may be effective in minimizing redundant computation for meta-path instances of the same target vertex by changing the encoding sequence and direction of meta-path instances, redundant computation across different target vertices remains. Both approaches fail to resolve some critical issues in HGNNs, such as high costs for constructing semantic graphs, memory overheads, and redundant computation. Hence, the present disclosure aims to design an efficient HGNN system. CN114298279A discloses a method for constructing design space of heterogeneous graph neural network (HGNN) with multiple design dimensions. It provides a unified HGNN framework and defines the design space for HGNNs based on this framework. This approach overcomes the limitations of previous works, which evaluated HGNNs only at the model level. It introduces a module-level evaluation perspective, enabling researchers to analyze design dimensions that significantly impact model performance. A platform, Space4HGNN, is established therein for c