IP Library › Granted Patent US 12,572,592
Granted Patent B2
US 12,572,592 · App. 16/809,679 · Granted Mar 10, 2026

Automated graph embedding recommendations based on extracted graph features

Inventors: Ana Paula Appel (São Paulo, BR); Renato Luiz de Freitas Cunha (São Paulo, BR); Bruno Silva (São Paulo, BR); Rogerio Abreu de Paula (São Paulo, BR)
Assignee: International Business Machines Corporation
G06F16/9024G06F18/213G06F18/22G06N20/00
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,572,592
App. No.
16/809,679
Granted
Mar 10, 2026
Kind
B2
Abstract

Embodiments of the invention are directed to a computer-implemented method for matching a graph-under-analysis to a technique for embedding the graph-under-analysis. In a non-limiting example, the computer-implemented method includes receiving, using a processor, graph data representing the graph-under-analysis, wherein the graph-under-analysis represents a network. The graph data is analyzed, using the processor, to extract graph property data representing properties of the graph-under-analysis. Based at least in part on a result of analyzing the graph property data, one or more embedding techniques are selected, wherein at least one of the one or more embedding techniques is configured to transform the graph data to a graph embedding that is used by a task algorithm to perform a task.

Claims (75)

1 . A computer-implemented method for matching a graph-under-analysis to a technique for embedding the graph-under-analysis, the computer-implemented method comprising:

receiving, using a processor, graph data representing the graph-under-analysis, wherein the graph-under-analysis represents a network;

analyzing, using the processor, the graph data to extract graph property data representing properties of the graph-under-analysis;

wherein analyzing the graph data comprises computing spectrum data of the graph-under-analysis and using the computed spectrum data to derive, directly from the computed spectrum data, the graph property data representing multiple types of the graph properties of the graph-under-analysis;

wherein the graph property data comprises the spectrum data of the graph-under-analysis;

annotating the graph data with the graph property data to generate annotated graph data, wherein the annotated graph data comprises the graph data in combination with the extracted graph property data captured as annotations associated with nodes, edges or the graph as a whole; and

selecting, using the processor, from an embedding technique repository one or more embedding techniques from a group of multiple embedding techniques stored in the embedding technique repository, wherein the multiple embedding techniques are distinct from each other, wherein the selecting is based on an analysis of the annotated graph data, wherein the analysis is performed by using the annotations within the annotated graph data to inform the selection of the one or more embedding techniques;

wherein at least one of the one or more embedding techniques is configured to transform the graph data to a graph embedding that is used by a task algorithm to perform a task.

2 . The computer-implemented method of claim 1 , wherein the spectrum data of the graph-under-analysis comprises eigenvalues of the graph-under-analysis's adjacency matrix.

3 . The computer-implemented method of claim 1 , wherein selecting the one or more embedding techniques further comprises applying a set of embedding technique selection rules to the annotated graph data.

4 . The computer-implemented method of claim 3 , wherein:

the embedding technique repository is further configured to store graph property data comprising known graphs having known graph characteristics;

applying the set of embedding technique selection rules includes comparing the graph property data to the stored graph property data comprising known graphs having known graph characteristics;

the stored graph property data is associated with stored known graph embedding techniques that have been used to translate at least one of the known graphs to a vector space on which a known task has been performed; and

selecting the one or more embedding techniques is further based at least in part on a result of using the set of embedding technique selection rules to compare the graph property data to the stored graph property data.

5 . The computer-implemented method of claim 1 , wherein selecting the one or more embedding techniques further comprises applying the graph property data to a machine learning model that determines a level of similarity between the graph property data and stored graph property data.

6 . The computer-implemented method of claim 1 further comprising performing, using the processor, a selection process for each of the multiple types of graph properties, the selection process comprising:

selecting one of the multiple types of graph properties;

analyzing the graph property data to determine a set of task options for the selected one of the multiple types of graph properties;

receiving a selected task, wherein the selected task is one of the task options;

receiving parameters of the selected task; and

receiving an instruction to apply a first one of the one or more embedding techniques to the graph data.

7 . The computer-implemented method of claim 1 , further comprising:

transforming the graph data according to at one of the one or more embedding techniques to produce a graph embedding; and

using the task algorithm on the produced graph embedding to produce a task output.

8 . A computer system for matching a graph-under-analysis to a technique for embedding the graph-under-analysis, the computer system comprising:

a memory; and

a processor communicatively coupled to the memory and configured to perform processor operations comprising:

receiving graph data representing the graph-under-analysis, wherein the graph-under-analysis represents a network;

analyzing the graph data to extract graph property data representing properties of the graph-under-analysis;

wherein analyzing the graph data comprises computing spectrum data of the graph-under-analysis and using the computed spectrum data to derive, directly from the computed spectrum data, the graph property data representing multiple types of the graph properties of the graph-under-analysis;

wherein the graph property data comprises the spectrum data of the graph-under-analysis;

annotating the graph data with the graph property data to generate annotated graph data, wherein the annotated graph data comprises the graph data in combination with the extracted graph property data captured as annotations associated with nodes, edges or the graph as a whole; and

selecting, from an embedding technique repository one or more embedding techniques from a group of multiple embedding techniques, wherein the multiple embedding techniques are distinct from each other, wherein the selecting is based on an analysis of the annotated graph data, wherein the analysis is performed by using the annotations within the annotated graph data to inform the selection of the one or more embedding techniques;

wherein at least one of the one or more embedding techniques is configured to transform the graph data to a graph embedding that is used by a task algorithm to perform a task.

9 . The computer system of claim 8 , wherein the spectrum data of the graph-under-analysis comprises eigenvalues of the graph-under-analysis's adjacency matrix.

10 . The computer system of claim 8 , wherein selecting the one or more embedding techniques further comprises applying a set of embedding technique selection rules to the annotated graph data.

11 . The computer system of claim 10 , wherein:

the embedding technique repository is further configured to store graph property data comprising known graphs having known graph characteristics;

applying the set of embedding technique selection rules includes comparing the graph property data to the stored graph property data comprising known graphs having known graph characteristics;

the stored graph property data is associated with stored known graph embedding techniques that have been used to translate at least one of the known graphs to a vector space on which a known task has been performed; and

selecting the one or more embedding techniques is further based at least in part on a result of using the set of embedding technique selection rules to compare the graph property data to the stored graph property data.

12 . The computer system of claim 8 , wherein selecting the one or more embedding techniques further comprises applying the graph property data to a machine learning model that determines a level of similarity between the graph property data and stored graph property data.

13 . The computer system of claim 8 , wherein the processor operations further comprise performing a selection process for a first type of the multiple types of graph properties, the selection process comprising:

selecting the first type;

analyzing the graph property data to determine a set of task options for the selected first type;

receiving a selected task, wherein the selected task is one of the task options;

receiving parameters of the selected task; and

receiving an instruction to apply a first one of the one or more embedding techniques to the graph data.

14 . The computer system of claim 13 , wherein performing the selection process for the first type of the multiple types of graph properties comprises performing the selection process on each the multiple types of graph properties.

15 . The computer system of claim 8 , wherein the group of multiple embedding techniques are selected from group consisting of a node2vec embedding technique, a multi-hop embedding technique, and a random walk embedding technique.

16 . The computer system of claim 8 , wherein the processor operations further comprise:

transforming the graph data according to at least one of the one or more embedding techniques to produce a graph embedding; and

using the task algorithm on the produced graph embedding to produce a task output.

17 . A computer program product for matching a graph-under-analysis to a technique for embedding the graph-under-analysis, the computer program product comprising a computer readable program stored on a computer readable storage medium, wherein the computer readable program, when executed on a processor system, causes the processor system to perform processor system operations comprising:

receiving graph data representing the graph-under-analysis, wherein the graph-under-analysis represents a network;

analyzing the graph data to extract graph property data representing properties of the graph-under-analysis;

wherein analyzing the graph data comprises computing spectrum data of the graph-under-analysis and using the computed spectrum data to derive, directly from the computed spectrum data, the graph property data representing multiple types of the graph properties of the graph-under-analysis;

wherein the graph property data comprises the spectrum data of the graph-under-analysis;

annotating the graph data with the graph property data to generate annotated graph data;

wherein the spectrum data of the graph-under-analysis comprises eigenvalues of the graph-under-analysis's adjacency matrix;

based at least in part on the annotated graph data, selecting one or more embedding techniques;

wherein at least one of the one or more embedding techniques is configured to transform the graph data to a graph embedding that is used by a task algorithm to perform a task; and

performing a selection process for each of the multiple types of graph properties, the selection process comprising:

selecting one of the multiple types of graph properties;

analyzing the graph property data to determine a set of task options for the selected one of the multiple types of graph properties;

receiving a selected task, wherein the selected task is one of the task options;

receiving parameters of the selected task; and

receiving an instruction to apply a first one of the one or more embedding techniques to the graph data.

18 . The computer program product of claim 17 , wherein selecting the one or more embedding techniques comprises applying a set of embedding technique selection rules to the annotated graph data.

19 . The computer program product of claim 18 , wherein:

applying the set of embedding technique selection rules includes comparing the graph property data to a repository of stored graph property data comprising known graphs having known graph characteristics;

the stored graph property data is associated with stored known graph embedding techniques that have been used to translate at least one of the known graphs to a vector space on which a known task has been performed; and

selecting the one or more embedding techniques is further based at least in part on a result of using the set of embedding technique selection rules to compare the graph property data to the stored graph property data.

20 . The computer program product of claim 17 , wherein selecting the one or more embedding techniques comprises applying the graph property data to a machine learning model that determines a level of similarity between the graph property data and stored graph property data.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Mar 5, 2020
From: APPEL, ANA PAULA; DE FREITAS CUNHA, RENATO LUIZ; SILVA, BRUNO; DE PAULA, ROGERIO ABREU
To: INTERNATIONAL BUSINESS MACHINES CORPORATION
Reel/Frame 052023/0242 →
Continuity (1)
Related Publication 20210279279A1 · Sep 9, 2021
References Cited (45)
US 7263462B2 · Funge et al. · 2007 [cited by applicant]
US 7705847B2 · Helfman et al. · 2010 [cited by applicant]
US 8046324B2 · Patil et al. · 2011 [cited by applicant]
US 8082220B2 · Hadad et al. · 2011 [cited by applicant]
US 9652286B2 · Fan · 2017 [cited by applicant]
US 10062039B1 · Lockett · 2018 [cited by applicant]
US 10095992B1 · Brestoff et al. · 2018 [cited by applicant]
US 10331495B2 · Bequet et al. · 2019 [cited by applicant]
US 10349134B2 · Hamiti et al. · 2019 [cited by applicant]
US 10402403B2 · Viken et al. · 2019 [cited by applicant]
US 10409828B2 · Abdelhamid et al. · 2019 [cited by applicant]
US 20030041041A1 · Cristianini · 2003 [cited by examiner]
US 20100121792A1 · Yang et al. · 2010 [cited by applicant]
US 20130138587A1 · Patil et al. · 2013 [cited by applicant]
US 20150339835A1 · Mohr · 2015 [cited by examiner]
US 20170178021A1 · Lipkin et al. · 2017 [cited by applicant]
US 20180107507A1 · Lin et al. · 2018 [cited by applicant]
US 20180129710A1 · Tagami · 2018 [cited by examiner]
US 20180341720A1 · Bhatia et al. · 2018 [cited by applicant]
US 20190122111A1 · Min et al. · 2019 [cited by applicant]
US 20190251480A1 · Garcial. et al. · 2019 [cited by applicant]
US 20190279086A1 · Nicol et al. · 2019 [cited by applicant]
US 20200210858A1 · De Bie · 2020 [cited by examiner]
US 20200258004A1 · Heimann · 2020 [cited by examiner]
US 20200387135A1 · Khorasgani · 2020 [cited by examiner]
US 20210397790A1 · Arvela · 2021 [cited by examiner]
William Fleshman, “Spectral Clustering,” Feb. 20, 2019, Towards Data Science, https://towardsdatascience.com/spectral-clustering-aba2640c0d5b (Year: 2019). [cited by examiner]
Appel et al., “Temporally Evolving Community Detection and Prediction in Content-Centric Networks,” arXiv preprint arXiv:1807.06560 (2018), 10 pages. [cited by applicant]
Dai et al., “Learning combinatorial optimization algorithms over graphs,” Advances in Neural Information Processing Systems, 2017, 24 pages. [cited by applicant]
Ganapathiraju et al., “Schizophrenia interactome with 504 novel protein-protein interactions,” NPJ Schizophrenia 2.1 (2016): 1-10. [cited by applicant]
Goyal et al., “Graph Embedding Techniques, Applications, and Performance: A Survey,” Knowledge-Based Systems 151 (2018): 78-94. [cited by applicant]
Hamilton et al., “Representation learning on graphs: Methods and applications,” arXiv preprint arXiv:1709.05584 (2017), 24 pages. [cited by applicant]
Huang et al., “Knowledge graph embedding based question answering,” Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, ACM, 2019, 9 pages. [cited by applicant]
Ivanoska et al., “Web tool for graph embeddings representation techniques evaluation,” 2019 42nd International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), IEEE, 2019… [cited by applicant]
Kumar et al., “Learning Dynamic Embeddings from Temporal Interactions.” arXiv preprint arXiv:1812.02289 (2018), 11 pages. [cited by applicant]
Leskovec, “WWW-18 Tutorial: Representation Learning on Networks,” The Web Conference 2018 (WWW), France, 2018, http://snap.stanford.edu/proj/embeddings-www/ (retrieved Feb. 10, 2020), 1 page. [cited by applicant]
Simonovsky, “Deep Learning on Attributed Graphs: A Journey from Graphs to Their Embeddings and Back,” arXiv preprint arXiv:1901.08296 (2019), 121 pages. [cited by applicant]
Singer et al., “Node Embedding over Temporal Graphs,” arXiv preprint arXiv:1903.08889 (2019), 8 pages. [cited by applicant]
Wang et al., “Knowledge graph embedding: A survey of approaches and applications,” IEEE Transactions on Knowledge and Data Engineering 29.12 (2017): 2724-2743. [cited by applicant]
Wang et al., “Premise selection for theorem proving by deep graph embedding,” Advances in Neural Information Processing Systems, 2017, 11 pages. [cited by applicant]
Wu et al., “A comprehensive survey on graph neural networks,” arXiv preprint arXiv:1901.00596 (2019), 22 pages. [cited by applicant]
Xu et al., “How powerful are graph neural networks?” arXiv preprint arXiv:1810.00826 (2018), 17 pages. [cited by applicant]
Xu et al., “Knowledge graph representation with jointly structural and textual encoding,” arXiv preprint arXiv:1611.08661 (2016), 7 pages. [cited by applicant]
You et al., “Graph convolutional policy network for goal-directed molecular graph generation,” Advances in Neural Information Processing Systems 31, 2018, 12 pages. [cited by applicant]
Zhou et al., “Graph neural networks: A review of methods and applications,” arXiv preprint arXiv:1812.08434 (2018), 22 pages. [cited by applicant]