Mining relevant approximate subgraphs from multigraphs

Patent metadata

Field	Value
Publication number	US-9934327-B2
Application number	US-201514726789-A
Country	US
Kind code	B2
Filing date	Jun 1, 2015
Priority date	Jun 1, 2015
Publication date	Apr 3, 2018
Grant date	Apr 3, 2018

Abstract

A mechanism is provided in a data processing system for extracting subgraphs from a multigraph with approximation. The mechanism receives a multigraph and a relevance function and a pattern generation component executing within the data processing system searches the multigraph for occurrences of at least one pattern based on an approximation function. A relevance computation component executing within the data processing system determines a relevance measure for the multigraph based on the relevance function and the occurrences of the at least one pattern. The mechanism provides output of relevant patterns based on the occurrences of the at least one pattern.

First claim

What is claimed is:

1. An apparatus comprising:
a processor; and
a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to implement a subgraph extraction system, wherein the instructions cause the processor to:
receive, by the subgraph extraction system, a multigraph and a relevance function;
search, by a search space exploration section of the subgraph extraction system, the multigraph for occurrences of at least one pattern based on an approximation function, wherein searching the multigraph comprises dividing, by a pattern generation component executing within the search space exploration section of the subgraph extraction system, the multigraph into a plurality of components based on application of an approximation function and searching the plurality of component for occurrences of the at least one pattern simultaneously using parallel processing;
determine, by a relevance computation component executing within a relevance computation section of the subgraph extraction system, a relevance measure for each component based on the relevance function and the occurrences of the at least one pattern;
determine, by the relevance computation component, an overall relevance measure for the multigraph based on the relevance measures of the plurality of components; and
provide, by the subgraph extraction system, output of relevant patterns based on the occurrences of the at least one pattern.

2. The apparatus of claim 1 , wherein dividing the multigraph into the plurality of components is based on a cut strategy, wherein the cut strategy comprises multidimensional modularity optimization, weighted minimum cuts in graphs, edge-betweenness based clustering, Markov clustering, or label propagation based community detection.

3. The apparatus of claim 1 , wherein the approximation function is computed at data pre-processing stage or during searching the multigraph.

4. The apparatus of claim 1 , wherein the approximation function is controlled by a parameter bounding a loss in accuracy or resource consumption.

5. The apparatus of claim 1 , wherein the relevance function is defined as a function of frequency, node labels, edge labels, or subgraph structure.

6. The apparatus of claim 1 , wherein the instructions further cause the processor to:
perform an action on entities or relationships represented by the relevant patterns.

7. The apparatus of claim 1 , wherein the at least one pattern comprises at least one labeled multigraph.

8. A computer program product comprising a computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a computing device, causes the computing device to implement a subgraph extraction system, wherein the instructions cause the processor to:
receive, by the subgraph extraction system, a multigraph and a relevance function;
search, by a search space exploration section of the subgraph extraction system, the multigraph for occurrences of at least one pattern based on an approximation function, wherein searching the multigraph comprises dividing, by a pattern generation component executing within the search space exploration section of the subgraph extraction system, the multigraph into a plurality of components based on application of an approximation function and searching the plurality of component for occurrences of the at least one pattern simultaneously using parallel processing;
determine, by a relevance computation component executing within a relevance computation section of the subgraph extraction system, a relevance measure for each component based on the relevance function and the occurrences of the at least one pattern;
determine, by the relevance computation component, an overall relevance measure for the multigraph based on the relevance measures of the plurality of components; and
provide, by the subgraph extraction system, output of relevant patterns based on the occurrences of the at least one pattern.

9. The computer program product of claim 8 , wherein the computer readable program further causes the computing device to:
perform an action on entities or relationships represented by the relevant patterns.

10. The computer program product of claim 9 , wherein searching the plurality of component for occurrences of the at least one pattern simultaneously using parallel processing comprises sending the plurality of components to a plurality of threads, processors, virtual processors, processing cores, or processing nodes.

11. The apparatus of claim 1 , wherein searching the plurality of component for occurrences of the at least one pattern simultaneously using parallel processing comprises sending the plurality of components to a plurality of threads, processors, virtual processors, processing cores, or processing nodes.

12. The apparatus of claim 6 , wherein performing the action on the entities or relationships represented by the relevant patterns comprises suggesting friends in social networks, predicting bandwidth needs for peer-to-peer networks, or preventing potential failures in power networks.

13. The computer program product of claim 8 , wherein searching the multigraph comprises dividing the multigraph into a plurality of components based on application of an approximation function and searching each component for occurrences of the at least one pattern.

14. The computer program product of claim 8 , wherein dividing the multigraph into the plurality of components is based on a cut strategy, wherein the cut strategy comprises multidimensional modularity optimization, weighted minimum cuts in graphs, edge-betweenness based clustering, Markov clustering, or label propagation based community detection.

15. The computer program product of claim 8 , wherein the approximation function is computed at data pre-processing stage or during searching the multigraph.

16. The computer program product of claim 8 , wherein the approximation function is controlled by a parameter bounding a loss in accuracy or resource consumption.

17. The computer program product of claim 8 , wherein the relevance function is defined as a function of frequency, node labels, edge labels, or subgraph structure.

18. The computer program product of claim 8 , wherein the at least one pattern comprises at least one labeled multigraph.

Assignees

• IBM

Inventors

• Anchuri Pranay
• Berlingerio Michele
• Braghin Stefano

Classifications

• G06F16/532

  Query formulation, e.g. graphical querying · CPC title

• G06F16/213

  with details for schema evolution support · CPC title

• G06F16/9024 Primary

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

• G06F16/73

  Querying · CPC title

• G06F16/2465

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