IP Library › Granted Patent US 12,217,157
Granted Patent B2
US 12,217,157 · App. 18/271,301 · Granted Feb 4, 2025

System, method, and computer program product for dynamic node classification in temporal-based machine learning classification models

Inventors: Jiarui Sun (Urbana, IL); Mengting Gu (Stanford, CA); Michael Yeh (Newark, CA); Liang Wang (San Jose, CA); Wei Zhang (Fremont, CA)
Assignee: Visa International Service Association
G06N3/049G06F17/16
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,217,157
App. No.
18/271,301
Granted
Feb 4, 2025
Kind
B2
Abstract

Described are a system, method, and computer program product for dynamic node classification in temporal-based machine learning classification models. The method includes receiving graph data of a discrete time dynamic graph including graph snapshots, and node classifications associated with all nodes in the discrete time dynamic graph. The method includes converting the discrete time dynamic graph to a time-augmented spatio-temporal graph and generating an adjacency matrix based on a temporal walk of the time-augmented spatio-temporal graph. The method includes generating an adaptive information transition matrix based on the adjacency matrix and determining feature vectors based on the nodes and the node attribute matrix of each graph snapshot. The method includes generating and propagating initial node representations across information propagation layers using the adaptive information transition matrix and classifying a node of the discrete time dynamic graph subsequent to the first time period based on final node representations.

Claims (62)

1. A computer-implemented method comprising:

receiving, with at least one processor, graph data of a discrete time dynamic graph comprising a plurality of graph snapshots, wherein each graph snapshot of the plurality of graph snapshots is associated with an instance of the discrete time dynamic graph at a time step in a first time period, and wherein each graph snapshot of the plurality of graph snapshots comprises a plurality of nodes, a plurality of edges, and a node attribute matrix;

receiving, with the at least one processor, a plurality of node classifications associated with all nodes in the discrete time dynamic graph, wherein each node classification of the plurality of node classifications is associated with a node of the plurality of nodes in each graph snapshot of the plurality of graph snapshots;

converting, with the at least one processor, the discrete time dynamic graph to a time-augmented spatio-temporal graph based on the plurality of edges of each graph snapshot of the plurality of graph snapshots;

generating, with the at least one processor, an adjacency matrix of at least one adjacency matrix based on a temporal walk of the time-augmented spatio-temporal graph, the adjacency matrix comprising a plurality of adjacency matrices positioned along a diagonal of the adjacency matrix, wherein each adjacency matrix of the plurality of adjacency matrices is associated with a graph snapshot of the plurality of graph snapshots at a separate time step in the first time period, and wherein the adjacency matrix of the at least one adjacency matrix comprises at least one copied matrix of one or more adjacency matrices of the plurality of adjacency matrices;

generating, with the at least one processor, at least one adaptive information transition matrix based on the at least one adjacency matrix;

determining, with the at least one processor, a plurality of feature vectors based on the plurality of nodes and the node attribute matrix of each graph snapshot of the plurality of graph snapshots, wherein each feature vector of the plurality of feature vectors is associated with a node of the discrete time dynamic graph;

generating, with the at least one processor, a plurality of initial node representations, wherein each initial node representation of the plurality of initial node representations is based on a feature vector of the plurality of feature vectors and a node associated with the feature vector;

propagating, with the at least one processor, the plurality of initial node representations across a plurality of information propagation layers using the at least one adaptive information transition matrix to produce a plurality of final node representations based on an output of a final layer of the plurality of information propagation layers; and

classifying, with the at least one processor, at least one node of the discrete time dynamic graph in a time step of a second time period subsequent to the first time period based on the plurality of final node representations.

2. The method of claim 1 , wherein generating the adjacency matrix of the at least one adjacency matrix based on the temporal walk of the time-augmented spatio-temporal graph comprises:

generating, with the at least one processor, the adjacency matrix of the at least one adjacency matrix based on a bijection between all possible temporal walks of the time-augmented spatio-temporal graph and all possible temporal walks of the discrete time dynamic graph.

3. The method of claim 1 , wherein generating the adjacency matrix of the at least one adjacency matrix based on the temporal walk of the time-augmented spatio-temporal graph comprises:

restricting, with the at least one processor, the temporal walk such that when traversing from a first node in a first time step to a second node in a second time step, the temporal walk must first visit a same node in the second time step that corresponds to the first node in the first time step.

4. The method of claim 1 , wherein the at least one adjacency matrix comprises a structural adjacency matrix and a temporal adjacency matrix.

5. The method of claim 1 , wherein the at least one adaptive information transition matrix comprises an adaptive structural transition matrix and an adaptive temporal transition matrix.

6. The method of claim 1 , wherein classifying the at least one node of the discrete time dynamic graph comprises:

converting, with the at least one processor, the plurality of final node representations to a plurality of class logits using a multilayer perceptron decoder; and

classifying, with the at least one processor, the at least one node based on the plurality of class logits.

7. The method of claim 1 , wherein generating the at least one adaptive information transition matrix based on the at least one adjacency matrix comprises:

generating, with the at least one processor, the at least one adaptive information transition matrix based on the at least one adjacency matrix using a dynamic attention mechanism; and

determining, with the at least one processor, an attention weight for the dynamic attention mechanism using a nonlinear activation function.

8. The method of claim 1 , wherein propagating the plurality of initial node representations across the plurality of information propagation layers using the at least one adaptive information transition matrix comprises:

feeding, with the at least one processor, a plurality of intermediate node representations produced from a first information propagation layer of the plurality of information propagation layers as an input into a second information propagation layer of the plurality of information propagation layers.

9. A system comprising at least one processor, the at least one processor being programmed or configured to:

receive graph data of a discrete time dynamic graph comprising a plurality of graph snapshots, wherein each graph snapshot of the plurality of graph snapshots is associated with an instance of the discrete time dynamic graph at a time step in a first time period, and wherein each graph snapshot of the plurality of graph snapshots comprises a plurality of nodes, a plurality of edges, and a node attribute matrix;

receive a plurality of node classifications associated with all nodes in the discrete time dynamic graph, wherein each node classification of the plurality of node classifications is associated with a node of the plurality of nodes in each graph snapshot of the plurality of graph snapshots;

convert the discrete time dynamic graph to a time-augmented spatio-temporal graph based on the plurality of edges of each graph snapshot of the plurality of graph snapshots;

generate an adjacency matrix of at least one adjacency matrix based on a temporal walk of the time-augmented spatio-temporal graph, the adjacency matrix comprising a plurality of adjacency matrices positioned along a diagonal of the adjacency matrix, wherein each adjacency matrix of the plurality of adjacency matrices is associated with a graph snapshot of the plurality of graph snapshots at a separate time step in the first time period, and wherein the adjacency matrix of the at least one adjacency matrix comprises at least one copied matrix of one or more adjacency matrices of the plurality of adjacency matrices;

generate at least one adaptive information transition matrix based on the at least one adjacency matrix;

determine a plurality of feature vectors based on the plurality of nodes and the node attribute matrix of each graph snapshot of the plurality of graph snapshots, wherein each feature vector of the plurality of feature vectors is associated with a node of the discrete time dynamic graph;

generate a plurality of initial node representations, wherein each initial node representation of the plurality of initial node representations is based on a feature vector of the plurality of feature vectors and a node associated with the feature vector;

propagate the plurality of initial node representations across a plurality of information propagation layers using the at least one adaptive information transition matrix, to produce a plurality of final node representations based on an output of a final layer of the plurality of information propagation layers; and

classify at least one node of the discrete time dynamic graph in a time step of a second time period subsequent to the first time period based on the plurality of final node representations.

10. The system of claim 9 , wherein, while generating the adjacency matrix of the at least one adjacency matrix based on the temporal walk of the time-augmented spatio-temporal graph, the at least one processor is programmed or configured to:

generate the adjacency matrix of the at least one adjacency matrix based on a bijection between all possible temporal walks of the time-augmented spatio-temporal graph and all possible temporal walks of the discrete time dynamic graph.

11. The system of claim 9 , wherein, while generating the adjacency matrix of the at least one adjacency matrix based on the temporal walk of the time-augmented spatio-temporal graph, the at least one processor is programmed or configured to:

restrict the temporal walk such that when traversing from a first node in a first time step to a second node in a second time step, the temporal walk must first visit a same node in the second time step that corresponds to the first node in the first time step.

12. The system of claim 9 , wherein the at least one adjacency matrix comprises a structural adjacency matrix and a temporal adjacency matrix.

13. The system of claim 12 , wherein the at least one adaptive information transition matrix comprises an adaptive structural transition matrix and an adaptive temporal transition matrix.

14. The system of claim 9 , wherein, while classifying the at least one node of the discrete time dynamic graph, the at least one processor is programmed or configured to:

convert the plurality of final node representations to a plurality of class logits using a multilayer perceptron decoder; and

classify the at least one node based on the plurality of class logits.

15. A computer program product comprising at least one non-transitory computer-readable medium comprising one or more instructions that, when executed by at least one processor, cause the at least one processor to:

receive graph data of a discrete time dynamic graph comprising a plurality of graph snapshots, wherein each graph snapshot of the plurality of graph snapshots is associated with an instance of the discrete time dynamic graph at a time step in a first time period, and wherein each graph snapshot of the plurality of graph snapshots comprises a plurality of nodes, a plurality of edges, and a node attribute matrix;

receive a plurality of node classifications associated with all nodes in the discrete time dynamic graph, wherein each node classification of the plurality of node classifications is associated with a node of the plurality of nodes in each graph snapshot of the plurality of graph snapshots;

convert the discrete time dynamic graph to a time-augmented spatio-temporal graph based on the plurality of edges of each graph snapshot of the plurality of graph snapshots;

generate an adjacency matrix of at least one adjacency matrix based on a temporal walk of the time-augmented spatio-temporal graph, the adjacency matrix comprising a plurality of adjacency matrices positioned along a diagonal of the adjacency matrix, wherein each adjacency matrix of the plurality of adjacency matrices is associated with a graph snapshot of the plurality of graph snapshots at a separate time step in the first time period, and wherein the adjacency matrix of the at least one adjacency matrix comprises at least one copied matrix of one or more adjacency matrices of the plurality of adjacency matrices;

generate at least one adaptive information transition matrix based on the at least one adjacency matrix;

determine a plurality of feature vectors based on the plurality of nodes and the node attribute matrix of each graph snapshot of the plurality of graph snapshots, wherein each feature vector of the plurality of feature vectors is associated with a node of the discrete time dynamic graph;

generate a plurality of initial node representations, wherein each initial node representation of the plurality of initial node representations is based on a feature vector of the plurality of feature vectors and a node associated with the feature vector;

propagate the plurality of initial node representations across a plurality of information propagation layers using the at least one adaptive information transition matrix, to produce a plurality of final node representations based on an output of a final layer of the plurality of information propagation layers; and

classify at least one node of the discrete time dynamic graph in a time step of a second time period subsequent to the first time period based on the plurality of final node representations.

16. The computer program product of claim 15 , wherein the one or more instructions that cause the at least one processor to generate the adjacency matrix of the at least one adjacency matrix based on the temporal walk of the time-augmented spatio-temporal graph cause the at least one processor to:

generate the adjacency matrix of the at least one adjacency matrix based on a bijection between all possible temporal walks of the time-augmented spatio-temporal graph and all possible temporal walks of the discrete time dynamic graph.

17. The computer program product of claim 15 , wherein the one or more instructions that cause the at least one processor to generate the adjacency matrix of the at least one adjacency matrix based on the temporal walk of the time-augmented spatio-temporal graph cause the at least one processor to:

restrict the temporal walk such that when traversing from a first node in a first time step to a second node in a second time step, the temporal walk must first visit a same node in the second time step that corresponds to the first node in the first time step.

18. The computer program product of claim 15 , wherein the at least one adjacency matrix comprises a structural adjacency matrix and a temporal adjacency matrix.

19. The computer program product of claim 18 , wherein the at least one adaptive information transition matrix comprises an adaptive structural transition matrix and an adaptive temporal transition matrix.

20. The computer program product of claim 15 , wherein the one or more instructions that cause the at least one processor to classify the at least one node of the discrete time dynamic graph cause the at least one processor to:

convert the plurality of final node representations to a plurality of class logits using a multilayer perceptron decoder; and

classify the at least one node based on the plurality of class logits.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jul 7, 2023
From: SUN, JIARUI; GU, MENGTING; YEH, MICHAEL; WANG, LIANG; ZHANG, WEI
To: VISA INTERNATIONAL SERVICE ASSOCIATION
Reel/Frame 064183/0775 →
Continuity (2)
Provisional Application 63304771 · Jan 31, 2022
Related Publication 20240078416A1 · Mar 7, 2024
References Cited (40)
US 11461581B2 · Luo · 2022 [cited by examiner]
US 11822533B2 · Flöther · 2023 [cited by examiner]
US 20020126648A1 · Kuchi · 2002 [cited by examiner]
US 20180062937A1 · Narasimhan et al. · 2018 [cited by applicant]
US 20200265291A1 · Cheng · 2020 [cited by examiner]
US 20200366690A1 · Cheng et al. · 2020 [cited by applicant]
US 20200387135A1 · Khorasgani · 2020 [cited by examiner]
US 20210067558A1 · Ni · 2021 [cited by examiner]
US 20210326389A1 · Sankar et al. · 2021 [cited by applicant]
US 20220101103A1 · Fatemi · 2022 [cited by examiner]
US 20220150123A1 · Kim · 2022 [cited by examiner]
Bianchi et al., “Graph Neural Networks with Convolutional ARMA Filters”, Jan. 24, 2021, 14 pages. [cited by applicant]
Brody et al., “How Attentive Are Graph Attention Networks?”, Oct. 11, 2021, 24 pages. [cited by applicant]
Chen et al., “Simple and Deep Graph Convolutional Networks”, Proceedings of the 37th International Conference on Machine Learning, 2020, 11 pages. [cited by applicant]
Chien et al., “Adaptive Universal Generalized PageRank Graph Neural Network”, International Conference on Learning Representations, 2021, 24 pages. [cited by applicant]
Gasteiger et al., “Predict Then Propagate: Graph Neural Networks Meet Personalized PageRank”, International Conference on Learning Representations, 2019, 15 pages. [cited by applicant]
Gehring et al., “Convolutional Sequence to Sequence Learning”, Proceedings of the 34th International Conference on Machine Learning, 2017, 10 pages, Sydney, Australia. [cited by applicant]
Goyal et al., “DynGEM: Deep Embedding Method for Dynamic Graphs”, May 29, 2018, 8 pages. [cited by applicant]
Grover et al., “node2vec: Scalable Feature Learning for Networks”, International Conference on Knowledge Discovery and Data Mining, Aug. 13, 2016, 10 pages, San Francisco, CA. [cited by applicant]
Hamilton et al., “Inductive Representation Learning on Large Graphs”, 31st Conference on Neural Information Processing Systems, 2017, 11 pages, Long Beach, CA. [cited by applicant]
Kingma et al., “Adam: A Method for Stochastic Optimization”, International Conference on Learning Representations, 2015, 15 pages. [cited by applicant]
Kipf et al., “Semi-Supervised Classification With Graph Convolutional Networks”, International Conference on Learning Representations, 2017, 14 pages. [cited by applicant]
Kumar et al., “Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks”, International Conference on Knowledge Discovery and Data Mining, Aug. 4, 2019, 11 pages, Anchorage, AK. [cited by applicant]
Levie et al., “CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filters”, Oct. 31, 2018, 20 pages. [cited by applicant]
Li et al., “Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning”, The Thirty-Second AAAI Conference on Artificial Intelligence, 2018, pp. 3538-3545. [cited by applicant]
Manessi et al., “Dynamic graph convolutional networks”, Pattern Recognition, 2020, 18 pages, vol. 97. [cited by applicant]
Nguyen et al., “Continuous-Time Dynamic Network Embeddings”, Track; Third International Workshop on Learning Representation for Big Networks, Apr. 23, 2018, pp. 969-976, Lyon, France. [cited by applicant]
Pareja et al., “EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs”, The Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020, pp. 5363-5370. [cited by applicant]
Paszke et al., “PyTorch: An Imperative Style, High-Performance Deep Learning Library”, 33rd Conference on Neural Information Processing Systems, 2019, 12 pages, Vancouver, Canada. [cited by applicant]
Perozzi et al., “DeepWalk: Online Learning of Social Representations”, International Conference on Knowledge Discovery and Data Mining, Aug. 24, 2014, pp. 701-710, New York, NY. [cited by applicant]
Rossi et al., “Temporal Graph Networks for Deep Learning on Dynamic Graphs”, Proceedings of the 37th International Conference on Machine Learning, 2020, 9 pages, Vienna, Austria. [cited by applicant]
Rozenshtein et al., “Temporal PageRank”, European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2016, pp. 674-689. [cited by applicant]
Sankar et al., “DySAT: Deep Neural Representation Learning on Dynamic Graphs via Self-Attention Networks”, International Conference on Web Search and Data Mining, Feb. 3, 2020, 9 pages, Houston, TX. [cited by applicant]
Page et al., “The PageRank Citation Ranking: Bringing Order to the Web”, Jan. 29, 1998, 17 pages. [cited by applicant]
Trivedi et al., “DyREP: Learning Representations Over Dynamic Graphs”, International Conference on Learning Representations, 2019, 25 pages. [cited by applicant]
Vaswani et al., “Attention Is All You Need”, 31st Conference on Neural Information Processing Systems, 2017, 11 pages, Long Beach, CA. [cited by applicant]
Velickovic et al., “Graph Attention Networks”, International Conference on Learning Representations, 2018, 12 pages. [cited by applicant]
Xu et al., “How Powerful Are Graph Neural Networks?”, International Conference on Learning Representations, 2019, 17 pages. [cited by applicant]
Xu et al., “Spatio-Temporal Attentive RNN for Node Classification in Temporal Attributed Graphs”, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, 2019, pp. 3947-3953. [cited by applicant]
Xu et al., “Inductive Representation Learning On Temporal Graphs”, International Conference on Learning Representations, 2020, 19 pages. [cited by applicant]