Graph neural networks for datasets with heterophily

Patent metadata

Field	Value
Publication number	US-12175366-B2
Application number	US-202117210157-A
Country	US
Kind code	B2
Filing date	Mar 23, 2021
Priority date	Mar 23, 2021
Publication date	Dec 24, 2024
Grant date	Dec 24, 2024

Abstract

Techniques are provided for training graph neural networks with heterophily datasets and generating predictions for such datasets with heterophily. A computing device receives a dataset including a graph data structure and processes the dataset using a graph neural network. The graph neural network defines prior belief vectors respectively corresponding to nodes of the graph data structure, executes a compatibility-guided propagation from the set of prior belief vectors and using a compatibility matrix. The graph neural network predicts predicting a class label for a node of the graph data structure based on the compatibility-guided propagations and a characteristic of at least one node within a neighborhood of the node. The computing device outputs the graph data structure where it is usable by a software tool for modifying an operation of a computing environment.

First claim

The invention claimed is:

1. A method that includes performing, with one or more processing devices, operations comprising:
receiving a dataset including a graph data structure;
processing, with a graph neural network, the dataset to generate a new graph data structure, wherein processing the graph neural network includes, at least:
defining a set of prior belief vectors respectively corresponding to nodes of the graph data structure,
applying a parameterized compatibility matrix to a node of the graph neural network to propagate a characteristic of a belief vector corresponding to the node to nodes within a neighborhood of the node,
performing echo cancelation to prevent the characteristic from being subsequently propagated back to the node while executing, using the parameterized compatibility matrix to model a probability of nodes of different classes being connected, a compatibility-guided propagation from the set of prior belief vectors,
predicting, by the graph neural network, a class label for the node of the graph data structure based on the compatibility-guided propagations and a characteristic of at least one node within the neighborhood of the node, and
assigning the class label to the node; and

outputting, using the class label, the new graph data structure, wherein the new graph data structure is usable by a software tool for modifying an operation of a computing environment.

2. The method of claim 1 , wherein modifying the operation of a computing environment comprises one or more of:
servicing a query to the dataset by retrieving, from the new graph data structure, entity data corresponding to the node having the class label;
modifying a subset of data elements of the dataset based on class labels in the new graph data structure that are generated with the compatibility-guided propagation; and
modifying, based on entity relationship represented by edges in the new graph data structure, interactive content in a manner specific to a target entity represented by the node having the class label.

3. The method of claim 1 , wherein the operations further comprise training the graph neural network by, at least:
minimizing, via modifications to one or more parameters of the graph neural network, a loss function that is based on a cross entropy loss, a co-training loss of the graph neural network, and a regulation term that centers the parameterized compatibility matrix around zero.

4. The method of claim 1 , wherein the operations further include:
pre-training the graph neural network for a predetermined quantity of iteration using a training dataset to generate a training set of belief vectors respectively corresponding to nodes of the graph neural network;
generating the parameterized compatibility matrix; and
computing values for matrix elements of the parameterized compatibility matrix using the training set of belief vectors.

5. The method of claim 1 , wherein the operations further comprise generating the parameterized compatibility matrix.

6. The method of claim 5 , wherein applying the parameterized compatibility matrix includes:
iteratively applying the parameterized compatibility matrix in a sliding window to the nodes of the graph neural network.

7. A method that includes performing, with one or more processing devices, operations comprising:
accessing a dataset, wherein a portion of data of the dataset is labeled with ground truth segments;
receiving a graph neural network including a graph data structure, wherein nodes of the graph data structure model the dataset;
generating, using a neural network, a belief vector for a node of the graph data structure, the belief vector including a probability of a class label of the node;
applying a compatibility matrix to the node of the graph data structure, the compatibility matrix modifying the belief vector of the node based on belief vectors of nodes in a neighborhood of the node;
computing, based on the belief vectors, a loss value, wherein the loss value is computed based (a) a co-training loss from the neural network, and (b) a regulation value that keeps rows of the compatibility matrix centered around zero;
updating parameters of the compatibility matrix based on the loss value; and
outputting the graph data structure with the compatibility matrix as updated.

8. The method of claim 7 , wherein the operations further comprise:
determining a class label for the node of the graph data structure based on the belief vector of the node and a ground truth segment corresponding to another node of the graph data structure.

9. The method of claim 7 , wherein the operations further include:
applying the compatibility matrix to each node of the graph neural network in a sliding window over a quantity of iterations that is based on a quantity of nodes in the graph data structure.

10. The method of claim 9 , wherein applying the compatibility matrix to the node of the graph data structure includes:
performing echo cancelation that prevents the belief vector of the node from being propagated back to the node from the nodes in the neighborhood of the node.

11. The method of claim 7 , wherein the co-training loss from the graph neural network measures a distance between an initial set of belief vectors to a ground-truth distribution for nodes in a training dataset.

12. A non-transitory computer-readable medium having program code stored thereon that, when executed by processing hardware, performs operations comprising:
receiving a dataset;
applying a parameterized compatibility matrix to a node of a graph neural network to propagate a characteristic of a belief vector corresponding to the node to nodes within a neighborhood of the node,
performing echo cancelation to prevent the characteristic from being subsequently propagated back to the node;
a step for generating a graph data structure that models the dataset using a graph neural network including the parameterized compatibility matrix, the graph neural network modeling, using compatibility guided propagations, a probability of nodes of different classes being connected; and
outputting the graph data structure.

13. The non-transitory computer-readable medium of claim 12 , wherein modifying the operation of a computing environment comprises one or more of:
servicing a query to the dataset by retrieving, from the graph data structure, entity data corresponding to a node having a class label;
modifying a subset of data elements the dataset based on class labels in the graph data structure that are generated with a compatibility-guided propagation; and
modifying, based on entity relationship represented by edges in the graph data structure, interactive content in a manner specific to a target entity represented by the node having the class label.

14. The transitory computer-readable medium of claim 12 , wherein the operations further comprise:
a step for predicting a class label for a node based on a belief vector of the node.

15. The non-transitory computer-readable medium of claim 12 , wherein the operations further include:
pre-training a neural network for a predetermined quantity of iteration using a training dataset to generate a set of belief vectors respectively corresponding to nodes of the graph neural network;
generating the parameterized compatibility matrix; and
estimating values of the parameterized compatibility matrix using the set of belief vectors.

16. The non-transitory computer-readable medium of claim 12 , wherein the operations further include generating the parameterized compatibility matrix.

17.

Assignees

• Adobe Inc

Inventors

• Rossi Ryan
• Mai Tung
• Lipka Nedim
• Zhu Jiong
• Rao Anup
• Swaminathan Viswanathan

Classifications

• G06N3/0895

  Weakly supervised learning, e.g. semi-supervised or self-supervised learning · CPC title

• G06N3/09

  Supervised learning · CPC title

• G06F18/24147

  Distances to closest patterns, e.g. nearest neighbour classification · CPC title

• G06F18/21322

  Rendering the within-class scatter matrix non-singular · CPC title

• G06N5/02

  Knowledge representation; Symbolic representation · CPC title