WO2024101537A1 - Method and computer device for node importance-based graph augmentation preserving graph core structure - Google Patents

Abstract

Disclosed are a method and computer device for node importance-based graph augmentation preserving a graph core structure. The graph data augmentation method augments graph data for training a graph neural network (GNN) and comprises the steps of: extracting subgraphs from two different graphs, respectively; and mixing the subgraphs to generate virtual graph data.

Description

Method and computer apparatus for node importance-based graph augmentation that preserves the core structure of the graph

The explanation below is about technology for augmenting graph data for GNN (graph neural network) learning.

Graph classification plays an important role in a variety of fields, from chemistry to social data analysis. In recent years, attempts to solve graph classification tasks using GNNs have attracted attention.

Deep models are successfully learned from unstructured data in various areas such as computer vision. However, the problem is that, like most deep models, GNNs often require too much data to generalize graph data, making them impractical.

Data augmentation technology is being used to train these data-intensive neural networks more cost-effectively ([1] Zhao, Tong, et al. "Data augmentation for graph neural networks." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 12. 2021). Existing graph augmentation methods rely heavily on injecting structural noise, such as edge manipulation, without considering the semantics of each graph data, which can mislead the network due to its context-agnostic nature. Additionally, most graph augmentation strategies focus on node classification tasks and have limitations that make them difficult to apply directly to graph classification.

As another option, you can consider mixup technology, which has become one of the standard data augmentation techniques due to its excellent performance in image classification, sentence classification, and model robustness. However, existing mixups are generally not suitable for graph data without node correlation because they are somewhat specific to image data or require data instances to be in the same dimensional space, and the number of nodes may also vary for each graph instance.

It is possible to provide graph transplant technology, a graph data augmentation methodology that mixes subgraphs of two different graph data.

In a graph data augmentation method performed on a computer device, the computer device includes at least one processor configured to execute computer-readable instructions included in a memory, and the graph data augmentation method includes learning a graph neural network (GNN). Augmenting graph data for: extracting, by the at least one processor, subgraphs from two different graphs; and generating virtual graph data by mixing the partial graph, by the at least one processor.

According to one aspect, the extracting step may extract the partial graph using node saliency on each graph.

According to another aspect, the extracting step includes calculating node importance based on node features and gradient in each graph; and extracting a k-hop graph from each graph using the node importance.

According to another aspect, the generating step includes removing a first partial graph extracted from a destination graph from the destination graph; and transplanting a second partial graph extracted from a source graph to the target graph from which the first partial graph has been removed.

According to another aspect, the transplanting step includes adding a new edge between a node remaining after the first subgraph is removed from the target graph and a specific node sampled from the second subgraph. can do.

According to another aspect, the specific node may be randomly sampled from the second subgraph through degree preservation (DP), which preserves the expected degree of the node in the original graph.

According to another aspect, the specific node may be sampled from the second partial graph through edge prediction, which predicts edge existence probability using features of node pairs.

According to another aspect, the edge prediction uses a differentiable edge predictor that is trained through supervised learning using the original graph and an end-to-end manner using a virtual graph. You can use it.

According to another aspect, the graph data augmentation method determines, by the at least one processor, a label of the virtual graph data based on node importance of the first partial graph and the second partial graph. Additional steps may be included.

According to another aspect, the determining step includes determining a label weight for the virtual graph data according to the relative importance between the nodes remaining after the first partial graph is removed from the target graph and the nodes included in the second partial graph. It may include deriving steps.

A graph data augmentation system implemented by a computer device, comprising at least one processor configured to execute computer-readable instructions included in a memory, wherein the at least one processor is configured to store graph data for learning a graph neural network (GNN). augmenting, the process of extracting subgraphs from two different graphs; and a graph data augmentation system that processes the process of generating virtual graph data by mixing the partial graph.

According to an embodiment of the present invention, graph data can be effectively augmented by generating virtual graph data through graph data augmentation technology that synthesizes partial graphs of two different graph data, and through this, graph-based artificial intelligence technology. You can expect groundbreaking performance improvements.

1 is a block diagram for explaining an example of the internal configuration of a computer device according to an embodiment of the present invention.

Figure 2 is a flowchart showing a graph data augmentation method in one embodiment of the present invention.

Figure 3 shows an example of a graph transplant process in one embodiment of the present invention.

Hereinafter, embodiments of the present invention will be described in detail with reference to the attached drawings.

Embodiments of the present invention relate to technology for augmenting graph data for GNN learning.

Embodiments including those specifically disclosed in this specification may provide technology for augmenting virtual graph data using different graph data.

GNN shows excellent performance in graph-related problems, but the GNN learning process also requires sufficient labeled data as in other domains. The process of collecting labels for graph data is expensive and realistically difficult, and graph data augmentation techniques have recently been attracting attention. Most data augmentation methodologies for graph classification problems rely on approaches that artificially modify a single graph by relying on domain knowledge. Recently, mixup-based data augmentation techniques have shown remarkable performance in several domains, but it is difficult to apply mixup augmentation techniques to graph-structured data due to their different sizes and connectivity. To solve these difficulties, the present invention proposes a data augmentation technology that mixes partial graphs of two different graph data.

The graph data enhancement system according to embodiments of the present invention may be implemented by at least one computer device, and the graph data enhancement method according to embodiments of the present invention may be implemented by at least one computer device included in the graph data enhancement system. It can be performed through . At this time, the computer program according to an embodiment of the present invention may be installed and driven in the computer device, and the computer device may perform the graph data augmentation method according to the embodiments of the present invention under the control of the driven computer program. there is. The above-described computer program can be combined with a computer device and stored in a computer-readable recording medium to execute the graph data augmentation method on the computer.

1 is a block diagram showing an example of a computer device according to an embodiment of the present invention. For example, a graph data enhancement system according to embodiments of the present invention may be implemented by the computer device 100 shown in FIG. 1.

As shown in FIG. 1, the computer device 100 is a component for executing the graph data augmentation method according to embodiments of the present invention, including a memory 110, a processor 120, a communication interface 130, and input/output. It may include an interface 140.

The memory 110 is a computer-readable recording medium and may include a non-permanent mass storage device such as random access memory (RAM), read only memory (ROM), and a disk drive. Here, non-perishable large-capacity recording devices such as ROM and disk drives may be included in the computer device 100 as a separate permanent storage device that is distinct from the memory 110. Additionally, an operating system and at least one program code may be stored in the memory 110. These software components may be loaded into the memory 110 from a computer-readable recording medium separate from the memory 110. Such separate computer-readable recording media may include computer-readable recording media such as floppy drives, disks, tapes, DVD/CD-ROM drives, and memory cards. In another embodiment, software components may be loaded into the memory 110 through the communication interface 130 rather than a computer-readable recording medium. For example, software components may be loaded into memory 110 of computer device 100 based on computer programs installed by files received over network 160.

The processor 120 may be configured to process instructions of a computer program by performing basic arithmetic, logic, and input/output operations. Commands may be provided to the processor 120 by the memory 110 or the communication interface 130. For example, the processor 120 may be configured to execute received instructions according to program codes stored in a recording device such as memory 110.

The communication interface 130 may provide a function for the computer device 100 to communicate with other devices through the network 160. For example, a request, command, data, file, etc. generated by the processor 120 of the computer device 100 according to a program code stored in a recording device such as memory 110 is transmitted to the network ( 160) and can be transmitted to other devices. Conversely, signals, commands, data, files, etc. from other devices may be received by the computer device 100 through the communication interface 130 of the computer device 100 via the network 160. Signals, commands, data, etc. received through the communication interface 130 may be transmitted to the processor 120 or memory 110, and files, etc. may be stored in a storage medium (as described above) that the computer device 100 may further include. It can be stored as a permanent storage device).

The communication method is not limited, and may include not only a communication method utilizing communication networks that the network 160 may include (e.g., mobile communication network, wired Internet, wireless Internet, and broadcasting network), but also short-distance wired/wireless communication between devices. there is. For example, the network 160 may include a personal area network (PAN), a local area network (LAN), a campus area network (CAN), a metropolitan area network (MAN), a wide area network (WAN), and a broadband network (BBN). , may include one or more arbitrary networks such as the Internet. Additionally, the network 160 may include any one or more of network topologies including a bus network, star network, ring network, mesh network, star-bus network, tree or hierarchical network, etc. Not limited.

The input/output interface 140 may be a means for interfacing with the input/output device 150. For example, input devices may include devices such as a microphone, keyboard, camera, or mouse, and output devices may include devices such as displays and speakers. As another example, the input/output interface 140 may be a means for interfacing with a device that integrates input and output functions, such as a touch screen. The input/output device 150 may be configured as a single device with the computer device 100.

Additionally, in other embodiments, computer device 100 may include fewer or more components than those of FIG. 1 . However, there is no need to clearly show most prior art components. For example, the computer device 100 may be implemented to include at least a portion of the input/output device 150 described above, or may further include other components such as a transceiver, a camera, various sensors, and a database.

Below, we will describe a specific example of a node importance-based graph augmentation technology that preserves the core structure of the graph.

The computer device 100 according to this embodiment may be configured with a graph data augmentation system implemented on a computer. The processor 120 of the computer device 100 may be implemented as a component for performing the following graph data augmentation method. Depending on the embodiment, components of the processor 120 may be selectively included in or excluded from the processor 120. Additionally, depending on the embodiment, components of the processor 120 may be separated or merged to express the functions of the processor 120.

The processor 120 and the components of the processor 120 can control the computer device 100 to perform the steps included in the graph data augmentation method below. For example, the processor 120 and its components may be implemented to execute instructions according to the code of an operating system included in the memory 110 and the code of at least one program.

Here, the components of the processor 120 may be expressions of different functions performed by the processor 120 according to instructions provided by program codes stored in the computer device 100.

The processor 120 may read necessary instructions from the memory 110 where instructions related to controlling the computer device 100 are loaded. In this case, the read command may include an command for controlling the processor 120 to execute a graph data augmentation method that will be described later.

These embodiments relate to a new mixup-based data augmentation technology (hereinafter referred to as 'graph transplant technology') for graph classification tasks that can be used on multi-domain datasets regardless of graph geometry. To understand the mixing of graph instances with unrelated nodes and different numbers of nodes, the graph transplant technique selects a subgraph from each target and source instance and transplants the subgraph from the source to the target from which the subgraph has been removed. When porting a subgraph from one instance to another, the final product may not align correctly with the corresponding interpolated labels if the original charge of the subgraph is not reflected in the labels. To solve this problem, this embodiment can utilize node saliency to select subgraphs and assign labels. In particular, node importance is defined as the 'l2-norm' of the gradient of the classification loss for the output of the graph convolution layer. This can be seen as a measure of the contribution of a node when the model classifies the graph. Additionally, the label of a mixed graph can be determined by the importance ratio between the source subgraph and the target subgraph. Instead of purely using the ratio of the number of nodes in a subgraph, importance-based label mixing appropriately describes mixed graphs by weighting nodes according to their importance. Another important challenge in blending graphs is determining the connections between subgraphs obtained from two different instances. For this purpose, two transformations can be applied: 1) random connection with constraints on the original node degree, and 2) edge prediction based on node features.

In other words, the main content of the present invention is as follows.

(1) We use a mixup-based graph augmentation method that can mix graphs with two different structures by replacing the target subgraph with the source subgraph while maintaining the local structure.

(2) In contrast to random augmentation, which runs the risk of generating noisy samples, in this embodiment a novel method that leverages node importance to generate a properly mixed graph using adaptively assigned labels that adhere to those labels. Use strategy.

Figure 2 is a flowchart for explaining an example of a graph data augmentation method in an embodiment of the present invention.

Referring to FIG. 2, in step S210, the processor 120 may extract a partial graph from each graph using node importance for two different graphs. In this embodiment, in order to extract partial graphs containing meaningful information (class-specific information) of the graph, 'node saliency', which indicates the importance of a node, can be defined as the slope of each node with respect to loss. The processor 120 can use node importance to find and extract a subgraph of important k-hops from each graph.

In step S220, the processor 120 may generate virtual graph data by connecting partial graphs extracted from two different graphs. Partial graphs extracted from two different graphs can be connected by a differentiable edge predictor as a learnable predictor and synthesized into a new mix graph.

In step S230, the processor 120 may determine a label for the virtual graph data generated in step S220 based on the importance of the corresponding partial graph and generate label data for GNN learning. The label of virtual graph data can be determined by the relative importance contained in each subgraph, which can effectively prevent semantic inconsistency between the label and virtual graph data.

First, the preliminary is explained.

Graph classification

는 노드 i에 대한 d차원 노드 피처 벡터가 i번째 항목인 피처 행렬이다. N(v)는 엣지로 v에 연결된 노드 집합

이다. 그래프 C-클래스 분류 작업의 경우 각 데이터 포인트(G,y)는 그래프 G와 해당 레이블 y∈{1,…,C}로 구성된다. 목표는 그래프 G를 가져와서 각 클래스에 대한 확률을 예측하는 GNN 모델을 훈련시키는 것이다.Let G=(V,E) be defined as an undirected graph. Here, V means a node set and E means an edge set.

is a feature matrix where the d-dimensional node feature vector for node i is the i-th item. N(v) is the set of nodes connected to v by edges

am. For a graph C-class classification task, each data point (G,y) is a graph G and its label y∈{1,… It consists of ,C}. The goal is to take a graph G and train a GNN model that predicts probabilities for each class.

GNN (graph neural networks for graph classification)

.In this embodiment, the graph neural network for graph classification must consider the following components: 1) message function m _l , 2) permutation invariant message aggregation function Φ _l , such as mean, sum or maximum for each element, 3) node update function h _l , 4) read function that combines permutation-invariant and node embedding together to obtain graph representation at the end

.

이 계층 l에서 노드 v의 잠재 벡터라고 하자. GNN의 재귀적 정의를 사용하여 표기법을 단순화하기 위해

을 사용하여 입력 노드 피처를 나타낸다. 각 GNN 계층에서 노드 피처는

로 업데이트되고, 마지막 L번째 계층 이후에는 모든 노드 피처 벡터가 읽기 함수

로 결합된다. x_G를 분류기 f에 전달함으로써 그래프 G에 대한 예측

를 얻는다. 여기서,

이다. 대표적인 예로, GCN(graph convolutional network) 계층은

로 정의된다. 여기서, 엣지 가중치가 e_v,u이고

이다.

Let be the latent vector of node v in this layer l. To simplify the notation we use the recursive definition of GNN.

Use to represent input node features. In each GNN layer, the node features are

, and after the last Lth layer, all node feature vectors are updated with the read function

are combined with Prediction on graph G by passing x _G to classifier f

get here,

am. As a representative example, the GCN (graph convolutional network) layer is

It is defined as Here, the edge weight is e _v,u and

am.

Mixup and its variants

Mixup is an interpolation-based normalization technique that generates virtual data by combining example pairs and labels for classification problems. Let x∈X be the input vector and y∈Y be the one-hot encoded C-class label in the data distribution D. The mixture-based augmentation method optimizes the loss L as follows, given the mixture ratio distribution q:

[Equation 1]

와

로 정의된다. 또 다른 예로, 혼합 함수를

로 정의하며, 여기서

는 이진 마스크

에 대한 요소별 아다마르(Hadamard) 곱을 나타내며(

),

이고, 여기서 W와 H는 이미지의 폭과 높이이다.Here, g and l are the data and label mixup functions, respectively. These functions have mixing parameters sampled from the beta distribution Beta(α,α)

and

It is defined as As another example, a mixed function

It is defined as, where

is the binary mask

Represents the element-wise Hadamard product for (

),

, where W and H are the width and height of the image.

Hereinafter, the graph transplant technology will be described in detail.

Graph transplantation technology is an effective augmentation technique for graph classification that creates meaningful mixed graphs by considering the context of graph instances. Figure 3 shows an example of a graph transplant process according to the present invention.

Referring to FIG. 3, first, the processor 120 calculates the node importance S _π and S of the source graph G _π and the target graph G.

와 임의 노드

에 의해 고정된(anchored) 각 그래프에서 k-홉의 부분 그래프를 추출할 수 있다.Next, the processor 120 is the main node

and random nodes

A partial graph of k-hops can be extracted from each graph anchored by .

Next, the processor 120 may determine the mixed label y' based on the node importance S _π and S.

를 대상 부분 그래프로 이식할 수 있다.Finally, the processor 120 generates the source-side partial graph

can be transplanted to the target subgraph.

The detailed process for each step is as follows.

Node Saliency for GNNs

Graph porting does not depend on any specific method of calculating the importance of a subgraph and can be combined with a variety of approaches. Unlike the general goal of explainability, which is finding important regions given a trained model, in this embodiment the goal is to dynamically find and blend subgraphs while the GNN is being trained. Therefore, we prioritize an approach that can simply and quickly find the importance of nodes using node features and gradients.

에 대한 분류 손실

의 기울기를 계산한다. 기울기는 원본 그래프에 대한 훈련 단계의 부산물이기 때문에 거의 비용 없이 얻을 수 있다. 그렇다면, 노드 v의 중요도 s_v는 노드

에 해당하는 기울기의 l2-놈으로 도출된다. l번째 계층에서 컴퓨팅 기울기를 선택하는 것은 각 노드에 대한 l-홉 이웃의 높은 수준의 공간 정보를 캡처하는 것이다. 따라서, 최종 노드 중요도 벡터

를 네트워크 아키텍처 수정 없이 얻을 수 있다.Considering the latent node feature matrix X ^{(l) obtained} from the GNN lth layer, first

Classification loss for

Calculate the slope of . Since the gradient is a by-product of the training step on the original graph, it can be obtained at almost no cost. Then, the importance s _v of node v is node

It is derived as the l2-norm of the slope corresponding to . Choosing a computing gradient at the lth layer is to capture high-level spatial information of the l-hop neighbors for each node. Therefore, the final node importance vector

can be obtained without modifying the network architecture.

Graph Mixing

Salient subgraph selection: Consider N graph arrangements (G ₁ ,…,G _N ) for every iteration. Two different graphs G _πi and G _i are formed as a pair, where π is range(N) = [1,… ,N] is the shuffle index. Excluding the index i for brevity of explanation, G _π and G refer to the source graph and target graph, respectively.

를 구성하려면, 먼저 노드

의 중요도 R%를 선택하여 클래스 의미론을 포함하는 중요한 부분을 찾는다. 노드 중요도는 정의에 의해 l-홉 부분 그래프의 중요성을 나타낸다. 전체 훈련 단계에서 동일한 노드를 반복적으로 선택하는 것을 피하기 위해 상위-2R% 주요 노드에서 무작위로 균일하게

를 확률적으로 샘플링한다. 선택된 앵커

의 집합이 주어지면, 각 이동 단계에 대해 인접 이웃의 p%를 무작위로 취함으로써 부분 K-홉 부분 그래프

를 추출한다. p는 각 훈련 반복에 대해 Beta(α,α)*100에서 샘플링된다(알고리즘 1 참조).Subgraph from source G _π

To configure, first node

Select the importance R% of to find the important parts containing the class semantics. Node importance, by definition, represents the importance of an l-hop subgraph. Randomly and uniformly from the top-2R% major nodes to avoid repeatedly selecting the same nodes throughout the entire training phase.

Probabilistically sample. selected anchor

Given a set of , a partial K-hop subgraph is obtained by randomly taking p% of its immediate neighbors for each move step.

Extract . p is sampled from Beta(α,α)*100 for each training iteration (see Algorithm 1).

[Table 1]

The main reason for choosing some subgraphs is that when the graph is dense, a K-hop subgraph can match the entire graph G. For each iteration, K is stochastically sampled from a discrete space K.

를 이식한다. 알고리즘 1에 의해 얻어진 노드 V는 대상 그래프 G에서 제거된다. 소스 측과 달리 앵커 노드

는 증강 그래프의 다양성을 위해 대상 그래프 G에서 R%로 무작위로 선택된다. 이 노드들이 떨어지는 곳은 소스

의 부분 그래프가 이식될 곳이다. v＼

에 의해 유도된 나머지 대상 부분 그래프는

=(v＼

)로 정의된다.On the target side, a subgraph is removed from the original graph to create a subgraph on the source side.

transplant. The node V obtained by Algorithm 1 is removed from the target graph G. Unlike the source side, the anchor node

is randomly selected as R% from the target graph G for the diversity of the augmented graph. Where these nodes fall is the source

This is where the subgraph of will be transplanted. v＼

The remaining target subgraph derived by is

=(v\

) is defined as.

Transplant: The graph transplant algorithm is as follows.

[Table 2]

와

를 추출한 후,

와 v＼

사이에 새로운 엣지를 추가하여

를

에 이식한다. 공식적으로,

v＼

로 결합된 그래프 G'=(V',E')을 구성하고

와 v＼

사이의 연결을 결정한다. 본 실시예에서는 로컬 정보와 내부 구조를 온전하게 보존하기 위해 부분 그래프 추출에 의해 노드가 엣지를 잃는다고 할 수 있다. 이를 위해 그래프 G에서 deg_G(v)를 노드 v의 정도(degree)로 정의하자. 그렇다면, 인위적 엣지가 부착될 수 있는 소스 및 대상 그래프의 후보 노드 집합은 각각

,

이며, 노드 정도의 총 변화량은

,

이다.subgraph

and

After extracting,

Wow v＼

By adding a new edge between

cast

transplanted to officially,

v＼

Construct a graph G'=(V',E') joined by

Wow v＼

determine the connections between In this embodiment, it can be said that nodes lose edges by partial graph extraction in order to preserve local information and internal structure intact. For this purpose, let us define deg _G (v) as the degree of node v in graph G. Then, the sets of candidate nodes in the source and target graphs to which artificial edges can be attached are respectively

,

, and the total amount of change in node degree is

,

am.

와,

사이의 연결을 결정하기 위해 다음의 두 가지 접근 방식을 사용한다. 첫 번째는

노드 쌍

를 무작위로 균일하게 샘플링하는 것이다. DP(degree preservation)라고 부르는 이 간단하고 효율적인 방법은 원본 그래프에서 노드의 예상되는 정도를 보존한다. 이를 통해 생성된 그래프의 분포를 원본 그래프에서 너무 벗어나지 않게 다양한 샘플을 생성할 수 있다. 다른 하나는, 연결을 위한 노드 쌍의 피처를 고려하여 훈련 단계에서 미분 가능한 엣지 예측 모듈을 도입하는 것이다. 이를 엣지 예측(edge prediction)이라고 명명한다. 엣지 예측 모듈

은 연결된 노드 피처 쌍

을 취하여 엣지 존재 확률

을 예측한다. 표기법으로

를 사용하여 노드 쌍 (u,v)의 표현을 소비하는 엣지 예측 변수를 나타낸다. 무방향 그래프의 경우 대칭 형태를 고려하고 평균

를 취한다.

의 입력에 대해 l번째 GNN 계층 이후 잠재 노드 피처

및

를 활용하여 로컬 정보를 함께 활용한다. 베르누이(Bernoulli)(

)에서 새로운 엣지 가중치

를 샘플링한다. 샘플링된 엣지 가중치

를 미분 가능하도록 훈련 단계에서 직통 검벨-소프트맥스(Gumbel-Softmax) 추정기에 의존한다. 마지막으로, 새 엣지 집합 E'은

로 설정된다.

and,

The following two approaches are used to determine the connection between: at first

node pair

is randomly and uniformly sampled. This simple and efficient method, called degree preservation (DP), preserves the expected degree of a node in the original graph. Through this, various samples can be generated so that the distribution of the generated graph does not deviate too much from the original graph. The other is to introduce a differentiable edge prediction module in the training stage by considering the features of node pairs for connection. This is called edge prediction. Edge prediction module

is a pair of connected node features

By taking the edge existence probability

predict. by notation

Use to denote an edge predictor that consumes the representation of the node pair (u,v). For undirected graphs, consider symmetric shapes and average

Take .

Latent node features after the lth GNN layer for the input of

and

Use local information together. Bernoulli (

) new edge weights in

Sample . Sampled edge weights

It relies on a direct Gumbel-Softmax estimator in the training stage to make it differentiable. Finally, the new edge set E' is

is set to .

The learning algorithm for graph transplantation is as follows.

[Table 3]

The edge prediction module is trained using supervised learning using the original graph and an end-to-end method using the virtual graph (see lines 4-5 and 13 of Algorithm 3).

Adaptive Label Mixing

In the present invention, we generate virtual graph data that captures graph semantics while maintaining original local information. Assigning appropriate labels to the generated graphs is necessary to prevent the network from being misled by inadequate supervision from noisy data. For example, assume that the core nodes that mainly determine the properties of the target graph G are condensed into a small area. When nodes in this small area are removed through the subgraph selection method described above, most of the original properties of G are lost, so simply assigning labels proportional to the number of nodes cannot properly describe the generated graph. To solve this problem, we propose a simple but effective label mixing strategy for graph porting.

(및 대상 그래프

의 나머지 부분)의 중요성을 원본 전체 그래프에서 부분 그래프를 구성하는 노드의 전체 중요도로 정의한다. 이 적응적 중요도 함수 I(S,V)는

로 공식화될 수 있다. 생성된 그래프 G'에 대한 레이블 가중치

은 소스

와 대상

에서 결합되는 부분의 상대적 중요도에 따라 도출되며 혼합 인스턴스

에 대한 레이블은

로 정의된다. 여기서

이다.Source Subgraph

(and target graph

The importance of the remaining part) is defined as the overall importance of the nodes that make up the partial graph in the original entire graph. This adaptive importance function I(S,V) is

It can be formalized as Label weights for the generated graph G'

silver sauce

and target

It is derived according to the relative importance of the parts being combined in mixed instances.

The label for is

It is defined as here

am.

The final goal in the present invention is as shown in Equation 2.

[Equation 2]

은

로 정의된다. 그래프 이식에 대한 전체 학습 프로세스는 알고리즘 3과 같다.here,

silver

It is defined as The overall learning process for graph transplantation is the same as Algorithm 3.

The graph data augmentation method according to the present invention can be applied to graph data of different sizes and irregular connectivity, and can generate a meaningful virtual graph by considering the semantic importance of the partial graph.

The graph data augmentation method according to the present invention can be applied to graph classification problems, property prediction problems of molecular structures, graph representation learning for new drug development, and graph feature prediction problems using only limited label information.

As such, according to embodiments of the present invention, graph data can be effectively augmented by generating virtual graph data through graph data augmentation technology that synthesizes partial graphs of two different graph data, and through this, graph-based artificial intelligence. The technology can be expected to dramatically improve performance.

The device described above may be implemented with hardware components, software components, and/or a combination of hardware components and software components. For example, the devices and components described in the embodiments include a processor, a controller, an arithmetic logic unit (ALU), a digital signal processor, a microcomputer, a field programmable gate array (FPGA), and a programmable logic unit (PLU). It may be implemented using one or more general-purpose or special-purpose computers, such as a logic unit, microprocessor, or any other device capable of executing and responding to instructions. The processing device may execute an operating system (OS) and one or more software applications running on the operating system. Additionally, a processing device may access, store, manipulate, process, and generate data in response to the execution of software. For ease of understanding, a single processing device may be described as being used; however, those skilled in the art will understand that a processing device includes multiple processing elements and/or multiple types of processing elements. It can be seen that it may include. For example, a processing device may include a plurality of processors or one processor and one controller. Additionally, other processing configurations, such as parallel processors, are possible.

Software may include a computer program, code, instructions, or a combination of one or more of these, which may configure a processing unit to operate as desired, or may be processed independently or collectively. You can command the device. The software and/or data may be embodied in any type of machine, component, physical device, computer storage medium or device for the purpose of being interpreted by or providing instructions or data to the processing device. there is. Software may be distributed over networked computer systems and stored or executed in a distributed manner. Software and data may be stored on one or more computer-readable recording media.

The method according to the embodiment may be implemented in the form of program instructions that can be executed through various computer means and recorded on a computer-readable medium. At this time, the medium may continuously store a computer-executable program, or temporarily store it for execution or download. In addition, the medium may be a variety of recording or storage means in the form of a single or several pieces of hardware combined. It is not limited to a medium directly connected to a computer system and may be distributed over a network. Examples of media include magnetic media such as hard disks, floppy disks, and magnetic tapes, optical recording media such as CD-ROMs and DVDs, magneto-optical media such as floptical disks, And there may be something configured to store program instructions, including ROM, RAM, flash memory, etc. Additionally, examples of other media include recording or storage media managed by app stores that distribute applications, sites or servers that supply or distribute various other software, etc.

As described above, although the embodiments have been described with limited examples and drawings, various modifications and variations can be made by those skilled in the art from the above description. For example, the described techniques are performed in a different order than the described method, and/or components of the described system, structure, device, circuit, etc. are combined or combined in a different form than the described method, or other components are used. Alternatively, appropriate results may be achieved even if substituted or substituted by an equivalent.

Therefore, other implementations, other embodiments, and equivalents of the claims also fall within the scope of the claims described below.

Claims (15)

In a graph data augmentation method performed on a computer device, The computer device includes at least one processor configured to execute computer-readable instructions contained in a memory, The graph data augmentation method is, By augmenting graph data for GNN (graph neural network) learning, extracting subgraphs from two different graphs, respectively, by the at least one processor; and generating virtual graph data by mixing the partial graph, by the at least one processor Graph data augmentation method including. According to paragraph 1, The extracting step is, Extracting the subgraph using node saliency on each graph A graph data augmentation method characterized by According to paragraph 1, The extraction step is, Calculating node importance based on node features and gradient in each graph; and Extracting a k-hop graph from each graph using the node importance Graph data augmentation method including. According to paragraph 1, The generating step is, removing a first partial graph extracted from a destination graph from the destination graph; and Transplanting a second partial graph extracted from a source graph to the target graph from which the first partial graph has been removed. Graph data augmentation method including. According to clause 4, The transplanting step is, Adding a new edge between a node remaining after the first subgraph is removed from the target graph and a specific node sampled from the second subgraph Graph data augmentation method including. According to clause 5, The specific node is randomly sampled from the second partial graph through degree preservation (DP), which preserves the expected degree of the node in the original graph. A graph data augmentation method characterized by According to clause 5, The specific node is sampled from the second partial graph through edge prediction, which predicts edge existence probability using features of node pairs. A graph data augmentation method characterized by In clause 7, The edge prediction uses a differentiable edge predictor that is trained through supervised learning using the original graph and an end-to-end manner using a virtual graph. A graph data augmentation method characterized by According to clause 4, The graph data augmentation method is, Determining, by the at least one processor, a label of the virtual graph data based on node importance of the first partial graph and the second partial graph. A graph data augmentation method further comprising: According to clause 9, The determining step is, Deriving a label weight for the virtual graph data according to the relative importance between the nodes remaining after the first partial graph is removed from the target graph and the nodes included in the second partial graph. Graph data augmentation method including. In a graph data augmentation system implemented with a computer device, At least one processor configured to execute computer readable instructions contained in memory Including, The at least one processor, By augmenting graph data for GNN (graph neural network) learning, The process of extracting subgraphs from two different graphs; and Process of generating virtual graph data by mixing the partial graph A graph data augmentation system that processes . According to clause 11, The at least one processor, In each graph, node saliency is calculated based on node features and gradient, Extracting a k-hop graph from each graph using the node importance A graph data augmentation system featuring. According to clause 11, The at least one processor, Remove the first subgraph extracted from the destination graph from the destination graph, Transplanting a second partial graph extracted from a source graph to the target graph from which the first partial graph has been removed. A graph data augmentation system featuring. According to clause 13, The at least one processor, Adding a new edge between a node remaining after the first subgraph is removed from the target graph and a specific node sampled from the second subgraph, The specific node is sampled from the second partial graph through edge prediction, which predicts edge existence probability using features of node pairs. A graph data augmentation system featuring. According to clause 13, The at least one processor, Determining the label of the virtual graph data based on node importance of the first subgraph and the second subgraph, Deriving a label weight for the virtual graph data according to the relative importance between the nodes remaining after the first subgraph is removed from the target graph and the nodes included in the second subgraph. A graph data augmentation system featuring.

Images