IP Library › Granted Patent US 12,688,410
Granted Patent B2
US 12,688,410 · App. 17/338,974 · Granted Jul 21, 2026

Generating prediction outputs using dynamic graphs

Inventors: Petar Velickovic (Cambridge, GB); Charles Blundell (London, GB); Oriol Vinyals (London, GB); Razvan Pascanu (Letchworth Garden City, GB); Lars Buesing (Letchworth Garden City, GB); Matthew Overlan (London, GB)
Assignee: GDM Holding LLC
G06N3/08G06F16/2379G06F16/9024G06N3/04
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,688,410
App. No.
17/338,974
Filed
Jun 4, 2021
Granted
Jul 21, 2026
Kind
B2
Art Unit
2121
USPC
706/21
Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for generating prediction outputs characterizing a set of entities. In one aspect, a method comprises: obtaining data defining a graph, comprising: (i) a set of nodes, wherein each node represents a respective entity from the set of entities, (ii) a current set of edges, wherein each edge connects a pair of nodes, and (iii) a respective current embedding of each node; at each of a plurality of time steps: updating the respective current embedding of each node, comprising processing data defining the graph using a graph neural network; and updating the current set of edges based at least in part on the updated embeddings of the nodes; and at one or more of the plurality of time steps: generating a prediction output characterizing the set of entities based on the current embeddings of the nodes.

Claims (73)

1 . A method performed by one or more data processing apparatus for generating prediction outputs characterizing a set of entities, the method comprising:

obtaining data defining a graph, comprising: (i) a set of nodes, wherein each node in the set of nodes represents a respective entity from the set of entities, (ii) a current set of edges, wherein each edge in the current set of edges connects a pair of nodes, and (iii) a respective current embedding of each node;

at each of a plurality of time steps:

updating the respective current embedding of each node of the graph, comprising processing data defining the graph using a graph neural network to update the respective current embedding of each node of the graph using feature representations of neighboring nodes identified based on the current set of edges at the time step;

updating the current set of edges of the graph based at least in part on the updated embeddings of the nodes of the graph, comprising:

processing the updated embeddings of the nodes in the graph, using a set of neural network parameters that have been trained by a machine learning training technique, to generate (i) a respective relevance score between each of a plurality of pairs of nodes in the graph, and (ii) a respective masking output for each node that characterizes whether to update edges connected to the node in the current set of edges; and

updating the current set of edges of the graph based on the relevance scores and the masking outputs, wherein updating the current set of edges comprises:

determining nodes with edges designated for replacement based on the masking outputs;

updating edges belonging to each node designated for replacement by adding one or more edges to the graph, or removing one or more edges from the graph, or both based on the set of relevance scores; and

after updating the current set of edges of the graph, providing the updated graph for processing at a next time step; and

at one or more of the plurality of time steps:

generating a prediction output characterizing the set of entities based on the current embeddings of the nodes of the graph.

2 . The method of claim 1 , wherein processing the updated embeddings of the nodes in the graph, using the set of neural network parameters that have been trained by a machine learning training technique, to generate the respective relevance score between each pair of nodes in the plurality of pairs of nodes in the graph comprises:

for first node and a second node in the pair of nodes, determining the relevance score between the first node and the second node based on the updated embeddings of the first node and the second node.

3 . The method of claim 2 , wherein the set of neural network parameters that have been trained by a machine learning training technique comprises a set of query parameters and a set of key parameters, and wherein determining the relevance score between the first node and the second node in the pair of nodes based on the updated embeddings of the first node and the second node comprises:

processing the updated embedding of the first node in accordance with the set of query parameters to generate a query embedding of the first node;

processing the updated embedding of the second node in accordance with the set of key parameters to generate a key embedding of the second node; and

determining the relevance score between the first node and the second node based on a similarity measure between: (i) the query embedding of the first node, and (ii) the key embedding of the second node.

4 . The method of claim 3 , wherein the similarity measure between: (i) the query embedding of the first node, and (ii) the key embedding of the second node, comprises an inner product of: (i) the query embedding of the first node, and (ii) the key embedding of the second node.

5 . The method of claim 1 , wherein the current set of edges includes a predefined set of static edges and a current set of dynamic edges, and wherein updating the current set of edges of the graph based on the relevance scores and the masking output comprises comprises updating only the current set of dynamic edges for nodes with edges designated for replacement based on the relevance scores between pairs of nodes in the graph.

6 . The method of claim 5 , wherein updating the current set of dynamic edges for nodes with edges designated for replacement based on the relevance scores between pairs of nodes in the graph comprises, for each given first node of the graph:

determining that a relevance score between the given first node and a given second node is higher than a relevance score between the given first node and any other node other than the given second node; and

adding an edge connecting the given first node to the given second node to the current set of dynamic edges.

7 . The method of claim 6 , further comprising removing one or more edges from the current set of dynamic edges prior to adding any edges to the current set of dynamic edges.

8 . The method of claim 5 , wherein at each of the plurality of time steps, the updated set of dynamic edges includes a predefined number of dynamic edges.

9 . The method of claim 1 , wherein updating the respective current embedding of each node of the graph comprises:

for each node in the graph, processing an input comprising the current embedding of the node using an encoder neural network to generate a feature representation of the node; and

providing the respective feature representation of each node as an input to the graph neural network.

10 . The method of claim 9 , further comprising, for each node in the graph:

receiving, at each time step, respective input features corresponding to the node;

wherein the encoder neural network processes an input comprising both: (i) the current embedding corresponding to the node, and (ii) the input features corresponding to the node, to generate the feature representation corresponding to the node.

11 . The method of claim 9 , wherein processing data defining the graph using the graph neural network to update the respective current embedding of each node of the graph using feature representations of neighboring nodes identified based on the current set of edges at the time step comprises, for one or more nodes of the graph:

processing respective feature representations of: (i) the node, and (ii) one or more other nodes that are connected to the node, in accordance with a plurality of graph neural network parameters to update the current embedding of the node.

12 . The method of claim 1 , wherein generating a prediction output characterizing the set of entities based on the current embeddings of the nodes of the graph comprises:

generating a pooled embedding by pooling current embeddings of the nodes of the graph; and

processing the pooled embedding to generate the prediction output.

13 . The method of claim 1 , wherein the current embeddings of the nodes of the graph and the current set of edges of the graph are updated in accordance with values of a set of parameters, and further comprising:

updating the values of the set of parameters using gradients of an objective function that measures respective errors between:

(i) the current set of edges of the graph, and (ii) a target set of edges of the graph, at each of the plurality of time steps; and

(i) the masking outputs for each node in the graph, and (ii) target masking outputs for each node in the graph, at each of the plurality of time steps.

14 . The method of claim 13 , wherein the objective function further measures an error between: (i) the prediction outputs characterizing the set of entities, and (ii) target outputs characterizing the set of entities.

15 . The method of claim 13 , wherein the target set of edges and the target masking outputs at each of the plurality of time steps are generated using a disjoint-set union data structure.

16 . The method of claim 1 , wherein at a first time step of the plurality of time steps:

the current set of edges includes a respective edge connecting each node in the graph to itself; and

the respective current embedding of each node is a default embedding.

17 . The method of claim 1 , wherein each entity in the set of entities is a respective atom in a molecule, and wherein the prediction output characterizes the energy required to break up the molecule.

18 . The method of claim 1 , wherein each entity in the set of entities is an object in a physical system, and wherein the prediction output characterizes a respective predicted future position of each of the objects in the physical system.

19 . A system comprising:

one or more computers; and

one or more storage devices communicatively coupled to the one or more computers, wherein the one or more storage devices store instructions that, when executed by the one or more computers, cause the one or more computers to perform operations for generating prediction outputs characterizing a set of entities, the operations comprising:

obtaining data defining a graph, comprising: (i) a set of nodes, wherein each node in the set of nodes represents a respective entity from the set of entities, (ii) a current set of edges, wherein each edge in the current set of edges connects a pair of nodes, and (iii) a respective current embedding of each node;

at each of a plurality of time steps:

updating the respective current embedding of each node of the graph, comprising processing data defining the graph using a graph neural network to update the respective current embedding of each node of the graph using feature representations of neighboring nodes identified based on the current set of edges at the time step;

updating the current set of edges of the graph based at least in part on the updated embeddings of the nodes of the graph, comprising:

processing the updated embeddings of the nodes in the graph, using a set of neural network parameters that have been trained by a machine learning training technique, to generate (i) a respective relevance score between each of a plurality of pairs of nodes in the graph, and (ii) a respective masking output for each node that characterizes whether to update edges connected to the node in the current set of edges; and

updating the current set of edges of the graph based on the relevance scores and the masking outputs, wherein updating the current set of edges comprises:

 determining nodes with edges designated for replacement based on the masking outputs;

 updating edges belonging to each node designated for replacement by adding one or more edges to the graph, or removing one or more edges from the graph, or both based on the set of relevance scores; and

after updating the current set of edges of the graph, providing the updated graph for processing at a next time step; and

at one or more of the plurality of time steps:

generating a prediction output characterizing the set of entities based on the current embeddings of the nodes of the graph.

20 . One or more non-transitory computer storage media storing instructions that when executed by one or more computers cause the one or more computers to perform operations for generating prediction outputs characterizing a set of entities, the operations comprising:

obtaining data defining a graph, comprising: (i) a set of nodes, wherein each node in the set of nodes represents a respective entity from the set of entities, (ii) a current set of edges, wherein each edge in the current set of edges connects a pair of nodes, and (iii) a respective current embedding of each node;

at each of a plurality of time steps:

updating the respective current embedding of each node of the graph, comprising processing data defining the graph using a graph neural network to update the respective current embedding of each node of the graph using feature representations of neighboring nodes identified based on the current set of edges at the time step;

updating the current set of edges of the graph based at least in part on the updated embeddings of the nodes of the graph, comprising:

processing the updated embeddings of the nodes in the graph, using a set of neural network parameters that have been trained by a machine learning training technique, to generate (i) a respective relevance score between each of a plurality of pairs of nodes in the graph, and (ii) a respective masking output for each node that characterizes whether to update edges connected to the node in the current set of edges; and

updating the current set of edges of the graph based on the relevance scores and the masking outputs, wherein updating the current set of edges comprises:

determining nodes with edges designated for replacement based on the masking outputs;

updating edges belonging to each node designated for replacement by adding one or more edges to the graph, or removing one or more edges from the graph, or both based on the set of relevance scores; and

after updating the current set of edges of the graph, providing the updated graph for processing at a next time step; and

at one or more of the plurality of time steps:

generating a prediction output characterizing the set of entities based on the current embeddings of the nodes of the graph.

Assignments (2)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 6, 2025
From: DEEPMIND TECHNOLOGIES LIMITED
To: GDM HOLDING LLC
Reel/Frame 071498/0210 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 29, 2021
From: VELICKOVIC, PETAR; BLUNDELL, CHARLES; VINYALS, ORIOL; PASCANU, RAZVAN; BUESING, LARS; OVERLAN, MATTHEW
To: DEEPMIND TECHNOLOGIES LIMITED
Reel/Frame 056704/0898 →
Continuity (2)
Provisional Application 63035449 · Jun 5, 2020
Related Publication 20210383228A1 · Dec 9, 2021
References Cited (62)
US 20160267397A1 · Carlsson · 2016 [cited by examiner]
US 20200074246A1 · Goyal · 2020 [cited by examiner]
US 20210081717A1 · Creed · 2021 [cited by examiner]
WO WO2019081781A1 · 2019 [cited by examiner]
J Wu et al., Dynamic Graph Convolutional Networks for Entity Linking, Proceedings of The Web Conference 2020, Apr. 20-24, 2020 (Year: 2020). [cited by examiner]
S M Kazemi et al., Representation Learning for Dynamic Graphs: A Survey, J of Machine Learning Research, vol. 21 (2020), pp. 1-73 (Year: 2020). [cited by examiner]
W Kool, et al., Attention, Learn to Solve Routing Problems, published as a conference paper at ICLR 2019. https://arxiv.org/pdf/1803.08475 (Year: 2019). [cited by examiner]
F Zhu, Improved collective influence of finding most influential nodes based on disjoint-set reinsertion, Scientific Reports (2018) 8:14503 (https://www.nature.com/articles/s41598-018-32874-5.pdf) (Year: 2018). [cited by examiner]
Battaglia et al., “Interaction networks for learning about objects, relations and physics,” CoRR, arxiv.org/abs/1612.00222, Dec. 2016, 12 pages. [cited by applicant]
Chen et al., “Can graph neural networks count substructures?,” CoRR, Feb. 2020, arXiv:2002.04025, 42 pages. [cited by applicant]
Chen et al., “Measuring and relieving the over-smoothing problem for graph neural networks from the topological view,” CoRR, Sep. 2019, arXiv:1909.03211, 12 pages. [cited by applicant]
Deac et al., “Graph neural induction of value iteration,” CoRR, Sep. 2020, arxiv.org/abs/2009.12604, 5 pages. [cited by applicant]
Dinitz, “Algorithm for solution of a problem of maximum flow in networks with power estimation,” Soviet Math. Dokl., Jan. 1970, 11(5):1277-1280. [cited by applicant]
Dwivedi et al., “Benchmarking graph neural networks,” CoRR, Mar. 2020, arXiv:2003.00982, 30 pages. [cited by applicant]
Franceschi et al., “Learning discrete structures for graph neural networks,” CoRR, Mar. 2019, arXiv:1903.11960, 14 pages. [cited by applicant]
Fredman et al., “The cell probe complexity of dynamic data structures,” Proceedings of the twenty-first annual ACM symposium on Theory of computing, Feb. 1989, pp. 345-354. [cited by applicant]
Galler et al., “An improved equivalence algorithm,” Communications of the ACM, May 1964, 7(5):301-303. [cited by applicant]
Garg et al., “Generalization and representational limits of graph neural networks,” Proceedings of the 37th International Conference on Machine Learning, 2020, 119:3419-3430. [cited by applicant]
Georgiev et al., “Neural bipartite matching,” CoRR, May 2020, arxiv.org/abs/2005.11304, 6 pages. [cited by applicant]
Gilmer et al., “Neural message passing for quantum chemistry,” Proceedings of the 34th International Conference on Machine Learning, 2017, 70:1263-1272. [cited by applicant]
Github.com [online], “Composable transformations of Python+NumPy programs: differentiate, vectorize, JIT to GPU/TPU, and more,” Sep. 2020, retrieved on May 19, 2021, retrieved from URL<https://github.com/google/jax>, 12… [cited by applicant]
Goel et al., “Disjoint set union with randomized linking,” Proceedings of the 2014 Anual ACM-SIAM Symposium on Discrete Algorithms, 2014, pp. 1005-1017. [cited by applicant]
Grover et al., “Graphite: Iterative generative modeling of graphs,” CoRR, Mar. 2018, arXiv:1803.10459, 13 pages. [cited by applicant]
Hamrick et al., “Relational inductive bias for physical construction in humans and machines,” CoRR, Jun. 2018, arXiv:1806.01203, 7 pages. [cited by applicant]
Jiang et al., “Semi-supervised learning with graph learning-convolutional networks,” Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019, pp. 11313-11320. [cited by applicant]
Kaiser et al., “Neural GPUs learn algorithms,” CoRR, Nov. 2015, arXiv:1511.08228, 9 pages. [cited by applicant]
Kazi et al., “Differentiable graph module (DGM) graph convolutional networks,” CoRR, Feb. 2020, arXiv:2002.04999, 10 pages. [cited by applicant]
Kingma et al., “Adam: A method for stochastic optimization,” CoRR, Dec. 2014, arXiv:1412.6980, 15 pages. [cited by applicant]
Kipf et al., “Neural relational inference for interacting systems,” CoRR, Feb. 2018, arXiv:1802.04687, 17 pages. [cited by applicant]
Kitaev et al., “Reformer: The efficient transformer,” CoRR, Jan. 2020, arXiv:2001.04451, 12 pages. [cited by applicant]
Kool et al., “Attention, learn to solve routing problems!,” CoRR, Mar. 2018, arXiv:1803.08475, 25 pages. [cited by applicant]
Kruskal, “On the shortest spanning subtree of a graph and the traveling salesman problem,” Proceedings of the American Mathematical Society, Feb. 1956, 7(1):48-50. [cited by applicant]
Li et al., “Learning deep generative models of graphs,” CoRR, Mar. 2018, arXiv:1803.03324, 21 pages. [cited by applicant]
Liu et al., “Non-local graph neural networks,” CoRR, May 2020, arXiv:2005.14612, 13 pages. [cited by applicant]
Pritzel et al., “Neural episodic control,” Proceedings of the 34th International Conference on Machine Learning, 2017, 70:2827-2836. [cited by applicant]
Richter et al., “Normalized attention without probability cage,” CoRR, May 2020, arXiv:2005.09561, 22 pages. [cited by applicant]
Sanchez-Gonzalez et al., “Learning to simulate complex physics with graph networks,” CoRR, Feb. 2020, arXiv:2002.09405, 20 pages. [cited by applicant]
Santoro et al., “A simple neural network module for relational reasoning,” CoRR, Jun. 2017, arxiv.org/abs/1706.01427, 16 pages. [cited by applicant]
Serviansky et al., “Set2graph: Learning graphs from sets,” CoRR, Feb. 2020, arXiv:2002.08772, 19 pages. [cited by applicant]
Shiloach et al., “An on-line edge-deletion problem,” Journal of the ACM, Jan. 1981, 28(1):1-4. [cited by applicant]
Sleator et al., “A data structure for dynamic trees,” Journal of computer and system sciences, Jun. 1983, 26(3):362-391. [cited by applicant]
Stanley, “Acyclic orientations of graphs,” Discrete Mathematics, May 2006, 306(10-11):905-909. [cited by applicant]
Tang et al., “Towards Scale-Invariant Graph-related Problem Solving by Iterative Homogeneous GNNs,” CoRR, Oct. 2020, arxiv.org/abs/2010.13547, 37 pages. [cited by applicant]
Tarjan et al., “Dynamic trees in practice,” Journal of Experimental Algorithmics, Sep. 2009, 14(4.5):21 pages. [cited by applicant]
Tarjan et al., “Efficiency of a good but not linear set union algorithm,” Journal of the ACM, Apr. 1975,22(2):215-225. [cited by applicant]
Tarjan et al., “Finding biconnected components and computing tree functions in logarithmic parallel time,” 25th Annual Symposium on Foundations of Computer Science, Oct. 1984, pp. 12-20. [cited by applicant]
Tarjan et al., “Worst-case analysis of set union algorithms,” Journal of the ACM, Apr. 1984, 31(2):245-281. [cited by applicant]
Trask et al., “Neural arithmetic logic units,” CoRR, Aug. 2018, arxiv.org/abs/1808.00508, 15 pages. [cited by applicant]
Vaswani et al., “Attention is all you need,” CoRR, Jun. 2017, arxiv.org/abs/1706.03762, 15 pages. [cited by applicant]
Velickovic et al., “Graph attention networks,” CoRR, Oct. 2017, arXiv:1710.10903, 12 pages. [cited by applicant]
Velickovic et al., “Neural execution of graph algorithms,” CoRR, Oct. 2019, arXiv:1910.10593, 14 pages. [cited by applicant]
Velickovic et al., “Pointer Graph Networks,” CoRR, Oct. 2020, arXiv:2006.06380v2, 21 pages. [cited by applicant]
Vinyals et al., “Order matters: Sequence to sequence for sets,” CoRR, Nov. 2015, arXiv:1511.06391, 11 pages. [cited by applicant]
Vinyals et al., “Pointer networks,” CoRR, Jun. 2015, arxiv.org/abs/1506.03134, 9 pages. [cited by applicant]
Wang et al., “Dynamic graph cnn for learning on point clouds,” ACM Transactions on Graphics, Oct. 2019, 38(5):1-12. [cited by applicant]
Wang et al., “Improving graph attention networks with large margin-based constraints,” CoRR, Oct. 2019, arXiv:1910.11945, 10 pages. [cited by applicant]
Xu et al., “How powerful are graph neural networks?,” CoRR, Oct. 2018, arXiv:1810.00826, 17 pages. [cited by applicant]
Xu et al., “What can neural networks reason about?,” CoRR, May 2019, arXiv:1905.13211, 18 pages. [cited by applicant]
Yan et al., “Neural execution engines: Learning to execute subroutines,” CoRR, Jun. 2020, arXiv:2006.08084, 21 pages. [cited by applicant]
Zaheer et al., “Deep sets. In Advances in neural information processing systems,” CoRR, Mar. 2017, arxiv.org/abs/1703.06114, 29 pages. [cited by applicant]
Zaremba et al., “Learning to execute,” CoRR, Oct. 2014, arXiv:1410.4615, 25 pages. [cited by applicant]
Zhao et al., “PairNorm: Tackling oversmoothing in gans.” CoRR, Sep. 2019, arXiv:1909.12223, 17 pages. [cited by applicant]