Research

Current Projects

• Activity modeling and influence detection in large social networks
• Towards scalable homomorphic encryption for scientific computation on public clouds
• Machine-learning for engineering design in high-dimensional parameter space
• Addressing scaling and reliability of physics-based numerical simulation techniques for the cloud

Activity modeling and influence detection in large social networks

Students: Chuanjia Xing and Albert Yu

With the world moving towards a high-degree of connectedness there is an intense effort towards understanding the formation and operation of large, connected social networks. While, individual users do make up the atomic structure of the networks, the emphasis is on modeling the network at a more understandable macro-scale. Efforts thus far have concentrated on computationally expensive, node-by-node bottom-up approaches on static graphs often resulting in less than satisfactory macro-models of the social networks.

Our recent work presented at the Design Automation Conference (DAC-2011) shows that the PageRank equation can be cast into an equivalent Helmholtz equation on a graph, the solution of which can be computed in a fast manner through the acceleration techniques, which are the heart of modern, physics-based field solvers.

We propose to extend the same to perform activity modeling, influence detection and hierarchical clustering in large social networks through a combination of the following methods:

• Low-rank user models. Such a model will leverage the methods applied in Latent Semantic Indexing (LSI) and machine learning techniques.
• Development of compact link models between users through machine learning. The link models will be a combination of the topology based connectivity and a weight based on the link between the two subjects. The topology part is obtained from the graph Helmholtz based formulation and the subjective part will come from machine learning.
• Born’s approximation for computing incremental Green’s functions on graphs in a computationally efficient manner.
• Study of the propagation of influence and the nature flows.
• Visualization of hierarchical clusters and activity on a network.

Fig 1: Relationship between page-rank on log-scale (y-axis) and the square of the equivalent wave number (x-axis) on a graph. Notice that large page-ranks correlate with large imaginary wave numbers.

Key papers and presentations:

V. Jandhyala, "Physics-based field-theoretic design automation tools for social networks and web search," 48th ACM/EDAC/IEEE Design Automation Conference (DAC), San Diego, CA, 2011, pp. 280 – 281

C. Xing, V. Jandhyala, "Wave Operators and Green’s Functions on Random Graphs," To be presented at IEEE Antennas and Propagation Symposium, Chicago, IL, July 2012

back to top

Towards scalable homomorphic encryption for scientific computation on public clouds

Student: Albert Yu

Large-scale scientific computation, encompassing a variety of applications such as electronic design automation, financial portfolio optimization, internet search, computational drug design etc. will benefit immensely from the power of public clouds such as the Amazon EC2. Such computations are typically performed on critical IP (such as the device geometry in a micro-electronic circuit or a sub-system, protein structure in drug-design scenario). Consumers of a computational-service that takes the burden of the scientific computation on a design or geometry to a public cloud have a serious and a legitimate concern about their IP being exposed in transit or while the computational instance is running on the cloud. Thus security is a big deterrent to the deployment of the power of the public cloud on data involving critical IP.

Key-based methods have been the workhorse of encryption methods over the last few decades. They do suffer from the following disadvantages:

1. The methods are only as secure as the key; key compromise renders encryption ineffective.
2. The decryption step implies decrypted information on the cloud, requiring an additional encryption step or opening up critical intellectual property to hacking.
3. These methods do not provably guarantee that the critical IP does not reside on the cloud, either in encrypted or decrypted form.

Our research focuses on one-way encryption methods and scaling them for enabling large-scale secure, scientific computation on the cloud. Our current work work in this direction includes:

1. Provably one-way, key-free encryption using Green’s function matrices and securing the matrix-vector product for use in cloud-based electromagnetic solvers.
2. Utilizing the concepts of homomorphic encryption and function composition to extend the above method to a more general class of problems in scientific computation.

Fig 1: The function composition technique to encrypt scientific computations on a cloud-computing platform.

Fig. 2: Illustrating the multiplication of a Green’s function matrix coming from the rectangular grid shown on the left and a sparse vector. The top figure shows the standard MDS based reconstruction on the Green’s function matrix. Note that the geometry is reasonably well recovered. The bottom figure shows the reconstruction from MDS when operating on the matrix and the vector jointly transformed through the function composition technique. The ratio of the norms of the error vector and the actual vector was 0.015% when using the function composition method to secure the Mat-Vec product.

Key papers and presentations:

A. R. Yu, V. Jandhyala, "On Securing Green’s Function-Based Field Simulation on Public Computing Clouds," To be presented at IEEE Antennas and Propagation Symposium, Chicago, IL, July 2012

back to top

Machine-learning for engineering design in high-dimensional parameter space

Student: Wei Cui

The design of complex engineering systems (such a sub-system of a smart-phone or the channel for the memory path in an advanced node) involves tuning of hundreds of parameters. Although field simulators are able to simulate devices with complex shapes (and hence a larger number of design parameters describing the features), the next challenge is to use such simulators in order to provide automated, parametric simulation and optimization in a high-dimensional design space, while minimizing the times of calling to solvers. This is necessary because each simulation of a complex design can take many hours on a single machine even with a fast electromagnetic solver.

Several ingredients need to work well together to enable such an automated optimization process. The primary ones being:

• Utilizing an intelligent sampling strategy for the initial design space sampling.
• Supervised learning to build a model.
• Usage of good test-vectors to test the model.
• A good error-feedback mechanism and additional sampling.
• Fast refinement of the model by adding more sampling points based on an error-feedback mechanism. This enables trading off accuracy vs additional simulations.
• An effective and flexible optimization strategy involving global and local optimizers
• Building the entire system on a cloud-computing platform to take advantage of the massive compute-power and the elasticity.

Currently our work is focused on optimizing all of these steps.

Fig. 1:  The surface response of the 1st and 2nd factors of a 8-factor 7-level system, setting the rest of factors to the 1st level:  (left) actual response surface and (right) estimated response surface given 49 training sets.

Key papers and presentations:

W. Cui, S. Chakraborty, V. Jandhyala, "Large Orthogonal Array-Based Optimization for High-Dimensional Parametric Systems,"To be presented at IEEE Antennas and Propagation Symposium, Chicago, IL, July 2012

W. Cui, S. Chakraborty, V. Jandhyala, "High-Dimensional Electromagnetic Design Sensitivity," To be presented at IEEE Antennas and Propagation Symposium, Chicago, IL, July 2012

back to top

Addressing scaling and reliability of physics-based numerical simulation techniques for the cloud

Researcher: Dr. Miao Sui

Design of physical systems using large-scale scientific computing entails a significant investment in specialized computing infrastructure. As cloud computing emerges as a new paradigm in large-scale computing, these costs can be alleviated by commercial cloud computing environments, such as the widely used Amazon EC2.

This has led to research in the direction of harnessing the power of the cloud to create a scalable and reliable vehicle for ultra-fast engineering analysis and design. A key element would therefore be the enabling of forward solver to scale well on the cloud. Thus, one of the research projects at the ACE lab is focused on fine-tuning the algorithms for fast-field simulations to enable very good scalability and reliability on the cloud platforms.

The research issues that our on-going work is addressing include:

• Parallelization of the algorithms (such as QR-based or FFT-based), which form the core of fast physics-based simulation schemes, for very good scalability on the cloud.
• Addressing the issues of point-to-point latency (standard clouds have extremely variable latency) and reliability (such as recovery from failed nodes) for the fast field simulation methods.

back to top