KR-20260066500-A - Network Alignment Method and Apparatus

KR20260066500AKR 20260066500 AKR20260066500 AKR 20260066500AKR-20260066500-A

Abstract

The present invention relates to a method and apparatus for aligning a network using only a graph structure in a situation where node attribute information is unavailable. A network alignment method related to an embodiment of the present invention may include the steps of: obtaining structural relationship information for each of the nodes constituting a source network and a target network—wherein the source network and the target network include an anchor node—; measuring the structural similarity between each node constituting each network and the anchor node for each of the source network and the target network; generating an attribute value for each node using the measured structural similarity, assigning the generated attribute value to each node, and vectorizing each node to which the attribute value is assigned; and aligning the source network and the target network according to the similarity between the vectorized nodes of each of the source network and the target network.

Inventors

김상욱
임재환
서동혁

Assignees

한양대학교 산학협력단

Dates

Publication Date: 20260512
Application Date: 20241104

Claims (14)

A step of obtaining structural relationship information for each of the nodes constituting the source network and the target network—the source network and the target network include anchor nodes—; A step of measuring the structural similarity between each node constituting each network and the anchor node for each of the source network and the target network; A step of generating attribute values for each node using the structural similarity measured above, assigning the generated attribute values to each node, and vectorizing each node to which the attribute values are assigned; and A network alignment method characterized by including the step of aligning the source network and the target network according to the similarity between the vectorized nodes of each of the source network and the target network.
In paragraph 1, The step of measuring the structural similarity above includes the step of constructing a similarity matrix, and In the above similarity matrix, the number of rows and columns is equal to the number of anchor nodes, and The number of the other of the above rows and columns is equal to the number of nodes constituting each of the above networks, and A network alignment method characterized in that the matrix value is the structural similarity measured between the anchor node corresponding to each row and each column and the node constituting each network.
In paragraph 2, The step of measuring the structural similarity above A network alignment method characterized by including the step of expanding multiple similarity matrices based on structural similarity measured by multiple methods, such that rows or columns match, to form a single similarity matrix.
In paragraph 3, the step of vectorizing each of the above nodes A step of extracting a row or column corresponding to each node constituting each network for each of the source network and the target network; and A network alignment method characterized by including the step of using the matrix values of the extracted rows or columns as input to a learned selection neural network to select specific matrix values by the selection neural network, and treating matrix values not selected by the selection neural network as 0.
In paragraph 4, the step of vectorizing each of the above nodes A network alignment method characterized by including the step of outputting a vector of each node based on the selected specific matrix value and the matrix value processed as zero.
In paragraph 5, the above-mentioned selection neural network is A network alignment method characterized by being used independently for each of the source network and the target network.
In paragraph 5, the step of outputting the vector of each of the above nodes The method further includes the step of outputting an embedding vector by using the connection information of each node, to which the vector of each node output above is assigned as an attribute value, as the input to a graph neural network, wherein The above graph neural network outputs the embedding vector of each node through the reconstruction loss value, and A network alignment method characterized in that the above reconstruction loss value is a correction factor that creates the embedding vector similar to the actual structure of the source network and the target network.
A device having one or more processors and a memory for storing one or more programs executed by said one or more processors, The above processor Obtain structural relationship information for each of the nodes constituting the source network and the target network, and For each of the above source network and the above target network, the structural similarity between each node constituting each network and the anchor node is measured, and Using the structural similarity measured above, attribute values for each of the above nodes are generated, the generated attribute values are assigned to each of the above nodes, and each of the above nodes to which the attribute values are assigned is vectorized. A network alignment device characterized by aligning the source network and the target network according to the similarity between the vectorized nodes of each of the source network and the target network.
In paragraph 8, the above processor The step of measuring the structural similarity above involves constructing a similarity matrix, and In the above similarity matrix, the number of rows and columns is equal to the number of anchor nodes, and The number of the other of the above rows and columns is equal to the number of nodes constituting each of the above networks, and A network alignment device characterized in that the matrix value is the structural similarity measured between the anchor node corresponding to each row and each column and the node constituting each network.
In paragraph 9, the above processor A network alignment device characterized by expanding multiple similarity matrices based on structural similarity measured by multiple methods, such that rows or columns match, to form a single similarity matrix.
In Clause 10, the above processor For each of the above source network and the above target network, a row or column corresponding to each node constituting each network is extracted, and A network alignment device characterized by using the matrix values of the extracted rows or columns as input to a learned selection neural network to select specific matrix values by the selection neural network, and treating matrix values not selected by the selection neural network as 0.
In Clause 11, the above processor A network alignment device characterized by outputting a vector of each node based on the selected specific matrix value and the matrix value processed as zero.
In Clause 12, the above-mentioned selection neural network is A network alignment device characterized by being used independently for each of the source network and the target network.
In Clause 12, the above processor The vector of each node output above is used as an input to a graph neural network to output an embedding vector, using the connection information of each node assigned as an attribute value. The above graph neural network outputs the embedding vector of each node through the reconstruction loss value, and A network alignment device characterized in that the above reconstruction loss value is a correction factor that creates the embedding vector similar to the actual structure of the source network and the target network.

Description

Network Alignment Method and Apparatus The present invention relates to a network alignment method and apparatus, and more specifically, to a method and apparatus for aligning a network using only a graph structure in a situation where node attribute information is unavailable. Network data (or graph data) is highly useful for describing various objects and the relationships between them, such as social networks, relational networks, molecular structures, and recommendation systems. Network data (hereinafter referred to as 'network') consists of nodes corresponding to each object and edges connecting nodes according to the relationships between the nodes, enabling the analysis of associations between multiple objects. For example, in a social network, nodes can represent users and edges can represent relationships between users (e.g., friends), while in a relational network, nodes can represent individual papers and edges can represent citation relationships. Furthermore, in a recommendation system, nodes can be users or products, and edges can represent recommendation relationships. Meanwhile, a multiple network refers to a network in which distinct networks include nodes for at least one identical object. Multiple networks are utilized in a wide range of application fields, from computer vision, bioinformatics, and web mining to chemistry and social network analysis. In multi-networks, it is crucial to identify nodes related to the same object across multiple nodes within each network. The process of identifying corresponding nodes across different networks is called Network Alignment (NA) (also known as graph matching). In other words, network alignment refers to the task of detecting corresponding nodes between two different networks based on the structure and node attributes of each network. Network alignment can be utilized as an initial step for downstream machine learning tasks across multiple networks. For example, identifying different accounts of the same user on various social networks (e.g., Facebook, Twitter, etc.) through network alignment facilitates friend recommendations, user behavior prediction, and personalized advertising. Furthermore, in bioinformatics, aligning specific protein-protein interaction (PPI) networks allows for the effective prioritization of candidate genes. However, when node attribute information was unavailable, network alignment, which is the task of detecting corresponding nodes between two different networks, had limitations. Therefore, there is a need for research on techniques to perform network alignment even when node attribute information is unavailable. FIG. 1 is a diagram illustrating the concept of a network alignment device aligning a network in relation to an embodiment of the present invention. FIG. 2 is a block diagram showing a configuration classified according to operation in a network alignment device related to an embodiment of the present invention. FIG. 3 is a diagram illustrating a method for configuring a similarity matrix in a network alignment device related to an embodiment of the present invention. FIG. 4 is a diagram illustrating a method for assigning attributes to nodes in a network alignment device related to an embodiment of the present invention. FIG. 5 is a diagram illustrating the process of outputting an embedding by reflecting a correction factor in a network alignment device related to an embodiment of the present invention. Figure 6 is a detailed block diagram of the similarity calculation unit illustrated in Figure 2. FIG. 7 is a diagram showing a pair of nodes finally aligned in a network alignment device related to an embodiment of the present invention. FIG. 8 is a diagram illustrating a computing environment including a computing device related to an embodiment of the present invention. In order to fully understand the present invention, the operational advantages of the present invention, and the objectives achieved by the implementation of the present invention, reference must be made to the accompanying drawings illustrating preferred embodiments of the present invention and the contents described in the accompanying drawings. The present invention will be described in detail below by explaining preferred embodiments with reference to the attached drawings. However, the present invention may be implemented in various different forms and is not limited to the embodiments described. Furthermore, to clearly explain the present invention, parts unrelated to the description are omitted, and the same reference numerals in the drawings indicate the same components. The embodiments and the terms used therein are not intended to limit the technology described in this document to specific embodiments and should be understood to include various modifications, equivalents, and/or substitutions of said embodiments. In describing various embodiments below, if it is determined that a detailed description of related known functions or c