Privacy-preserving Linear Algebra Framework for Graph Query Algorithms for Massive Networks

The research on graph data has been rejuvenated with a large range of recent real-world applications, ranging from social networks (Twitter), information networks (DBpedia), and co- purchase networks (Amazon.com) to biological and chemical databases (in 2012, there were at least 1500 online data sources). Due to the volume of data graphs and a lack of IT expertise, hosting efficient graph query services has been a technically challenging task for the owners of graph data. Hence, they may prefer to outsource these services to third-party service providers (SPs) for scalability, elasticity and performance. Some companies (especially, in the pharmaceutical domain) have been supporting structural search services.

SPs may not always be trusted. Security, including the confidentiality of data (and of queries), has been recognized as one of the critical attributes of quality of service (QoS); this QoS attribute directly influences the willingness of both data owners and query clients to use an SP’s services. The main challenge of privacy-preserving techniques is striking the balance between the security guarantee and the utility (in our case, performance) of the services. While our initial efforts on privacy-preserving graph queries [ICDE15a,TKDE15a] provide efficient techniques with various security guarantees, these techniques do not appear unifiable.

It is important to recognize that there is a stream of fundamental graph algorithms derived from linear algebra. In this project, we investigate a novel unified framework for privacy-preserving linear algebra that is generic enough to implement a wide range of graph query algorithms. Specifically, we investigate practical unified privacy-preserving algorithms, including those used to find private set intersections/unions, scalar products, and matrix multiplications/additions. To our knowledge, the linear algebra approach for privacy-preserving graph algorithms has not been studied before.

The research methodologies are listed as follows. Two specific examples of these will be given in the proposal.
1. Determine the encodings of graph topology (such as matrices), and graph attributes (such as vectors);
2. Express query algorithms in terms of additions/multiplications of matrices/vectors;
3. Determine efficient encryption schemes; and
4. Conduct privacy analysis with various attack models.

Further, it is known that using linear algebra for graph algorithms can be inefficient. Hence, we will exploit our expertise on database research to optimize their computations for massive graphs.

The outcomes of the project will not be limited to scholarly works. The privacy-preserving framework (e.g., API) is expected to be generic enough to form the building blocks of real-world applications for graph queries.