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

12217,157

18/271301

January 30, 2023

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.

Visa International Service Association (San Francisco, CA, US)

Visa International Service Association (San Francisco, CA, US)

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.

11461581 October 2022 Luo
11822533 November 2023 Flöther
2002/0126648 September 2002 Kuchi
2018/0062937 March 2018 Narasimhan et al.
2020/0265291 August 2020 Cheng
2020/0366690 November 2020 Cheng et al.
2020/0387135 December 2020 Khorasgani
2021/0067558 March 2021 Ni
2021/0326389 October 2021 Sankar et al.
2022/0101103 March 2022 Fatemi
2022/0150123 May 2022 Kim

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

edspgr.12217157