Latent network summarization

Patent metadata

Field	Value
Publication number	US-11113293-B2
Application number	US-201916252169-A
Country	US
Kind code	B2
Filing date	Jan 18, 2019
Priority date	Jan 18, 2019
Publication date	Sep 7, 2021
Grant date	Sep 7, 2021

Abstract

Embodiments of the present invention provide systems, methods, and computer storage media for latent summarization of a graph. Structural features can be captured from feature vectors associated with each node of the graph by applying base functions on the feature vectors and iteratively applying relational operators to successive feature matrices to derive deeper inductive relational functions that capture higher-order structural information in different subgraphs of increasing size (node separations). Heterogeneity can be summarized by performing capturing features in appropriate subgraphs (e.g., node-centric neighborhoods associated with each node type, edge direction, and/or edge type). Binning and/or dimensionality reduction can be applied to the resulting feature matrices. The resulting set of relational functions and multi-level feature matrices can form a latent summary that can be used to perform a variety of graph-based tasks, including node classification, node clustering, link prediction, entity resolution, anomaly and event detection, and inductive learning tasks.

First claim

What is claimed is:

1. One or more computer storage media storing computer-useable instructions that, when used by one or more computing devices, cause the one or more computing devices to perform operations comprising:
accessing an input graph comprising nodes and edges connecting the nodes;
accessing one or more initial node-specific feature vectors corresponding to each node;
generating a latent summary of the input graph by:
constructing a base feature matrix by applying, in a corresponding neighborhood for each node, a base function to the one or more initial node-specific feature vectors for the node; and
constructing a multi-level representation comprising a feature matrix at each of a plurality of levels by iteratively applying a relational function based on the base feature matrix, wherein the latent summary includes the relational function and the multi-level representation; and

providing the latent summary to facilitate performing a graph-based task based on the latent summary.

2. The one or more computer storage media of claim 1 , wherein the input graph is a heterogeneous graph, and wherein generating the latent summary of the input graph further comprises including, in the multi-level representation, localized structural information associated with one or more subsets of the corresponding neighborhood for each node corresponding to at least one of node type, edge directionality, or edge type.

3. The one or more computer storage media of claim 2 , wherein including the localized structural information in the multi-level representation comprises at least one of forming a tensor or concatenating the localized structural information in the multi-level representation.

4. The one or more computer storage media of claim 1 , wherein the base function comprises one or more of a mean, variance, sum, max, min, 11-distance, or 12-distance.

5. The one or more computer storage media of claim 1 , the operations further comprising applying a binning function to represent each feature vector in the multi-level representation based on distribution of feature values.

6. The one or more computer storage media of claim 1 , the operations further comprising applying dimensionality reduction to the multi-level representation.

7. The one or more computer storage media of claim 1 , wherein the corresponding neighborhood for each node comprises an egonet of the node.

8. The one or more computer storage media of claim 1 , the operations further comprising composing the relational function by iteratively applying one or more relational operators.

9. The one or more computer storage media of claim 1 , wherein the graph-based task comprises performing, based on the latent summary, at least one of inductive summarization, node embedding, link prediction, or inductive anomaly detection.

10. A computerized method comprising:
accessing an input graph comprising nodes and edges connecting the nodes;
accessing one or more initial node-specific feature vectors corresponding to each node;
generating a multi-level representation of the input graph by:
constructing a feature matrix at each of a plurality of levels by applying one or more relational operators to the one or more initial node-specific feature vectors and iteratively capturing structural information in neighborhoods associated with different node separations; and
including, in the multi-level representation, localized structural information associated with subsets of the neighborhoods corresponding to at least one of node type, edge directionality, or edge type; and

providing the multi-level representation to facilitate performing a graph-based task.

11. The computerized method of claim 10 , wherein including the localized structural information in the multi-level representation comprises at least one of forming a tensor or concatenating the localized structural information in the multi-level representation.

12. The computerized method of claim 10 , wherein the multi-level representation further comprises a base feature matrix constructed by applying a base function to the one or more initial node-specific feature vectors for each node.

13. The computerized method of claim 12 , wherein the base function comprises one or more of a mean, variance, sum, max, min, 11-distance, or 12-distance.

14. The computerized method of claim 10 , the method further comprising applying a binning function to represent each feature vector in the multi-level representation based on distribution of feature values.

15. The computerized method of claim 10 , the method further comprising applying dimensionality reduction to the multi-level representation.

16. The computerized method of claim 10 , wherein iteratively capturing the structural information in the neighborhoods associated with the different node separations comprises applying the one or more relational operators only over egonets.

17. The computerized method of claim 10 , wherein iteratively applying one or more relational operators composes a plurality of relational functions, the method further comprising providing the relational functions to facilitate performing the graph-based task.

18. The computerized method of claim 10 , wherein the graph-based task comprises performing, based on the multi-level representation, at least one of inductive summarization, node embedding, link prediction, or inductive anomaly detection.

19. A computer system comprising:
one or more hardware processors and memory configured to provide computer program instructions to the one or more hardware processors;
a latent summarization component configured to use the one or more hardware processors to:
access an input graph comprising nodes and edges connecting the nodes;
access one or more initial node-specific feature vectors corresponding to each node;
generate a multi-level representation of the input graph by:
constructing a feature matrix at each of a plurality of levels by applying one or more relational operators to the one or more initial node-specific feature vectors and iteratively capturing structural information in neighborhoods associated with different node separations; and
including, in the multi-level representation, localized structural information associated with subsets of the neighborhoods corresponding to at least one of node type, edge directionality, or edge type; and

provide the multi-level representation to facilitate performing a graph-based task.

20. The computer system of claim 19 , wherein the graph-based task comprises at least one of inductive summarization, node embedding, link prediction, or inductive anomaly detection.

Assignees

• Adobe Inc

Inventors

• Jin Di
• Rossi Ryan A
• Koh Eunyee
• Kim Sungchul
• Rao Anup

Classifications

• G06F16/288

  Entity relationship models · CPC title

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/215

  Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors · CPC title

• G06F16/2465 Primary

  Query processing support for facilitating data mining operations in structured databases · CPC title

• G06F2216/03

  Data mining · CPC title