Privacy-preserving graph analytics on hybrid cloud environments

Patent metadata

Field	Value
Publication number	US-2025190602-A1
Application number	US-202318533389-A
Country	US
Kind code	A1
Filing date	Dec 8, 2023
Priority date	Dec 8, 2023
Publication date	Jun 12, 2025
Grant date	—

Abstract

A method for preserving privacy by counting triangles on a graph G for hybrid cloud environments includes partitioning data elements of the graph G into a plurality of non-overlapping subgraphs, modifying each of the plurality of non-overlapping subgraphs to generate a plurality of p-induced subgraphs, distributing each of the plurality of p-induced subgraphs to a separate server located on a public cloud environment, computing a resultant number of triangles (p-integer) associated with each of the p-induced subgraphs for each of the separate servers located on the public cloud environment and computing a final number of triangles associated with the resultant number of triangles (p-integer) via an on-premise server.

First claim

What is claimed is:

1 . A method for preserving privacy by counting triangles on a graph G for hybrid cloud environments, the method comprising:
partitioning data elements of the graph G into a plurality of non-overlapping subgraphs; modifying each of the plurality of non-overlapping subgraphs to generate a plurality of p-induced subgraphs; distributing each of the plurality of p-induced subgraphs to a separate server located on a public cloud environment; computing a resultant number of triangles (p-integer) associated with each of the p-induced subgraphs for the separate server located on the public cloud environment; and computing a final number of triangles associated with the resultant number of triangles (p-integer) via an on-premise server.

2 . The method of claim 1 , wherein partitioning includes partitioning the data elements responsive to a set of graph parameters.

3 . The method of claim 2 , wherein the graph parameters include at least one of a clustering coefficient and a transitivity ratio.

4 . The method of claim 1 , wherein distributing includes augmenting each of the plurality of non-overlapping subgraphs with at least one of a set of new vertices and random edge connections.

5 . The method of claim 1 , further comprising transmitting the resultant number of triangles (p-integer) to the on-premise server.

6 . The method of claim 1 , wherein computing a final number of triangles includes,
adding the p-integer to the number of triangles associated with the p-induced subgraphs to create a semi-final number of triangles, and subtracting a number of triangles that have at least one added edge connection to previously added random edge connections from the semi-final number of triangles.

7 . A method for preserving privacy by counting triangles on a graph for hybrid cloud environments, the method comprising:
partitioning data elements of a graph G into a plurality of non-overlapping subgraphs; distributing each of the plurality of non-overlapping subgraphs to a separate server located on a public cloud environment; augmenting each of the plurality of non-overlapping subgraphs with new vertices and random edge connections to create p-induced subgraphs; computing a resultant number of triangles (p-integer) associated with each of the plurality of non-overlapping subgraphs for each of the servers located on the public cloud environment; transmitting the p-integer to an on-premise server; and computing a final number of triangles associated with subgraphs formed by coupling the p-induced subgraphs via the on-premise server by adding the p-integer to a number of triangles associated with the subgraphs formed by coupling the p-induced subgraphs and subtracting a number of triangles that have at least one added edge connection to previously added random edge connections.

8 . The method of claim 7 , wherein partitioning includes partitioning the data elements responsive to a set of graph parameters.

9 . The method of claim 8 , wherein the graph parameters include at least one of a clustering coefficient and a transitivity ratio.

10 . The method of claim 7 , wherein distributing includes augmenting each of the plurality of non-overlapping subgraphs with at least one of a set of new vertices and random edge connections.

11 . A computing system, comprising:
a machine learning system for implementing a method for preserving privacy by counting triangles on a graph G for hybrid cloud environments, the system configured to:
partition data elements of the graph G into a plurality of non-overlapping subgraphs;
modify each of the plurality of non-overlapping subgraphs to generate a plurality of p-induced subgraphs;
distribute each of the plurality of p-induced subgraphs to a separate server located on a public cloud environment;
compute a resultant number of triangles (p-integer) associated with each of the p-induced subgraphs for the separate server located on the public cloud environment; and
compute a final number of triangles associated with the resultant number of triangles (p-integer) via an on-premise server.

12 . The computing system of claim 11 , wherein partitioning includes partitioning the data elements responsive to a set of graph parameters.

13 . The computing system of claim 12 , wherein the graph parameters include at least one of a clustering coefficient and a transitivity ratio.

14 . The computing system of claim 11 , wherein distributing includes augmenting each of the plurality of non-overlapping subgraphs with at least one of a set of new vertices and random edge connections.

15 . The computing system of claim 11 , further comprising transmitting the resultant number of triangles (p-integer) to the on-premise server.

16 . The computing system of claim 11 , wherein computing a final number of triangles includes,
adding the p-integer to the number of triangles associated with the p-induced subgraphs to create a semi-final number of triangles, and subtracting a number of triangles that have at least one added edge connection to previously added random edge connections from the semi-final number of triangles.

17 . A computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform operations for implementing a method for preserving privacy by counting triangles on a graph G for hybrid cloud environments, the method comprising:
partitioning data elements of the graph G into a plurality of non-overlapping subgraphs; modifying each of the plurality of non-overlapping subgraphs to generate a plurality of p-induced subgraphs; distributing each of the plurality of p-induced subgraphs to a separate server located on a public cloud environment; computing a resultant number of triangles (p-integer) associated with each of the p-induced subgraphs for each of the separate servers located on the public cloud environment; and computing a final number of triangles associated with the resultant number of triangles (p-integer) via an on-premise server, wherein computing a final number of triangles includes,
adding the p-integer to a number of triangles associated with the p-induced subgraphs to create a semi-final number of triangles, and
subtracting a number of triangles that have at least one added edge connection to previously added random edge connections from the semi-final number of triangles.

18 . The method of claim 17 , wherein partitioning includes partitioning the data elements responsive to a set of graph parameters.

19 . The method of claim 18 , wherein the graph parameters includes at least one of a clustering coefficient and a transitivity ratio.

20 . The method of claim 17 , wherein distributing includes augmenting each of the plurality of non-overlapping subgraphs with at least one of a set of new vertices and random edge connections.

21 . The method of claim 17 , further comprising transmitting the resultant number of triangles (p-integer) to the on-premise server.

22 . A system comprising:
a memory having computer readable instructions for implementing a method for preserving privacy by counting triangles on a graph G for hybrid cloud environments; and one or more processors for executing the computer readable instructions, the computer readable instructions controlling the one or more processors to perform operations comprising: partitioning dat

Assignees

• IBM

Inventors

• Kalantzis Vasileios
• Horesh Lior
• Ubaru Shashanka
• Kollias Georgios

Classifications

• G06F21/6245

  Protecting personal data, e.g. for financial or medical purposes · CPC title

• G06F21/6218 Primary

  to a system of files or objects, e.g. local or distributed file system or database · CPC title