Methods for community search, method for training community search model, and electronic device

Patent metadata

Field	Value
Publication number	US-12038989-B2
Application number	US-202218148775-A
Country	US
Kind code	B2
Filing date	Dec 30, 2022
Priority date	Jan 19, 2022
Publication date	Jul 16, 2024
Grant date	Jul 16, 2024

Abstract

A method for community search is performed by an electronic device. The method includes: obtaining graph data to be processed, in which the graph data includes a plurality of nodes and a plurality of connection edges between the nodes; determining a query node from the plurality of nodes based on the graph data, and determining a target community to which the query node belongs by performing a community search for the query node, in which the target community includes the query node, and at least one node other than the query node in the plurality of nodes; and determining the query node and performing the community search for the query node repeatedly until the community to which each node included in the graph data belongs is determined.

First claim

What is claimed is:

1. A method for community search in a network based on deep learning, performed by an electronic device, the method comprising:
obtaining graph data to be processed, wherein the graph data comprises a plurality of nodes and a plurality of connection edges between the nodes;
determining a query node from the plurality of nodes based on the graph data, and determining a target community to which the query node belongs by performing a community search for the query node, wherein the target community comprises the query node and at least one node other than the query node in the plurality of nodes; and
repeatedly performing the steps of determining the query node and performing the community search for the query node, until a community to which each node included in the graph data belongs is determined;
wherein determining the target community to which the query node belongs by performing the community search for the query node, comprises:
adding the query node to a first community, wherein the first community is an empty community;
determining, based on expression vectors corresponding to nodes contained in the first community and expression vectors corresponding to the first nodes, a prediction quality of the first community by the reinforcement learning network after the first nodes are added to the first community, wherein the first nodes are nodes other than the nodes contained in the first community in the plurality of nodes;
updating the first community by adding a target node in the first nodes to the first community,
wherein the target node is one of the first nodes that enables the highest prediction quality of the first community after being added into the first community; and
updating the first community repeatedly until the updated first community satisfies a preset end condition, and determining the updated first community as the target community.

2. The method of claim 1 , wherein determining the query node from the plurality of nodes, comprises:
determining an importance corresponding to each of the nodes;
obtaining, from the plurality of nodes, first nodes whose communities are not determined; and
determining a node with the highest importance from the first nodes as the query node.

3. The method of claim 2 , wherein determining the query node from the plurality of nodes based on the graph data, and determining the target community to which the query node belongs by performing the community search for the query node, comprises:
determining the query node from the plurality of nodes by inputting the graph data into a community search model; and
determining the target community to which the query node belongs by performing the community search for the query node.

4. The method of claim 3 , wherein the community search model comprises a graph neural network and a reinforcement learning network, and determining the query node from the plurality of nodes by inputting the graph data into the community search model, and determining the target community to which the query node belongs by performing the community search for the query node, comprises:
obtaining expression vectors corresponding to the plurality of nodes by inputting the graph data into the graph neural network;
determining the query node from the plurality of nodes by inputting the expression vectors corresponding to the plurality of nodes into the reinforcement learning network; and
determining the target community to which the query node belongs by performing the community search for the query node through the reinforcement learning network.

5. The method of claim 1 , wherein the preset end condition comprises at least one of: a degree of each node in the updated first community being at least a preset value, or a number of nodes contained in the updated first community reaching a preset number.

6. A method for training a community search model, performed by an electronic device, the method comprising:
obtaining training graph data, wherein the training graph data comprises a plurality of sample nodes and a plurality of connection edges between the sample nodes;
obtaining expression vectors corresponding to the plurality of sample nodes by inputting the training graph data into a graph neural network comprised in an initial community search model;
determining a query sample node from the plurality of sample nodes by inputting the expression vectors corresponding to the plurality of sample nodes into a reinforcement learning network comprised in the initial community search model, determining a sample community to which the query sample node belongs by performing a community search for the query sample node through the reinforcement learning network, and adjusting model parameters of the graph neural network and the reinforcement learning network during the community search through the reinforcement learning network, wherein the sample community comprises the query sample node and at least one sample node other than the query sample node in the plurality of sample nodes; and
obtaining a target community search model by determining the query sample node and adjusting the model parameters repeatedly until a sample community to which each sample node belongs included in the sample graph data is determined;
wherein adjusting the model parameters of the graph neural network and the reinforcement learning network during the community search, comprises:
obtaining a first true quality of a first sample community, wherein the first sample community comprises a sample query node;
determining, based on expression vectors corresponding to sample nodes contained in the first sample community and an expression vector corresponding to a first target sample node, a first prediction quality of the first sample community by the reinforcement learning network after the first target sample node is added to the first sample community, wherein the first target sample node is one of first sample nodes that enables the highest prediction quality of the first sample community after being added into the first sample community, and the first sample nodes are sample nodes other than the sample nodes contained in the first sample community in the plurality of sample nodes;
obtaining a second true quality of a second sample community, wherein the second sample community comprises at least the sample query node and the first target sample node;
determining, based on expression vectors corresponding to sample nodes contained in the second sample community and an expression vector corresponding to a second target sample node, a second prediction quality of the second sample community by the reinforcement learning network after the second target sample node is added to the second sample community, wherein the second target sample node is one of second sample nodes that enables the highest prediction quality of the second sample community after being added into the second sample community, and the second sample nodes are sample nodes other than the sample nodes contained in the second sample community in the plurality of sample nodes;
determining a loss value based on the first true quality, the second true quality, the first prediction quality, and the second prediction quality; and
adjusting the model parameters of the graph neural network and the reinforcement learning network based on the loss value.

7. An electronic device, comprising:
at least one processor; and
a memory configured to store instructions executable by the at least one processor,
when the instructions are executed by the at least one processor, the at least one processor is caused to:
obtain graph data to be processed, wherein the graph data comprises a plurality of nodes and a plurality of connection edges between the n

Assignees

• Beijing Baidu Netcom Sci & Tech Co Ltd

Inventors

• Dong Zheng
• Wang Peng
• Song Xin
• Zhu Hengshu
• Yao Kaichun

Classifications

• G06N3/092

  Reinforcement learning · CPC title

• G06N3/042

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

• G06N3/048

  Activation functions · CPC title

• G06N3/0464

  Convolutional networks [CNN, ConvNet] · CPC title

• G06F16/90335

  Query processing · CPC title