Research

Parallel Iteratively Reweighted least squares Min-Cut solver (PIRMCut)

- - The PIRMCut algorithm is a step towards the goal of a scalable, parallel s-t min-cut solver for graphs with hundreds of millions or billions of edges. It is built on the reduction of the undirected s-t min-cut problem to solving a sequence of reweighted electrical flow problems. Such a reduction makes it feasible to exploit high parallelism in solving the undirected s-t min-cut problem, which is notorious for its hardness of parallelization.
  - PIRMCut is implemented on a distributed memory platform and the empirical experiments reveal its desirable parallel scalability on large graphs. Based on the observation that the node voltages induced by the electrical flow polarize toward 0 and 1, we devised a two-level rounding procedure that greatly improves the convergence of PIRMCut. As an efficient parallel numerical algorithm that can naturally handle floating-point valued s-t min-cut problems, PIRMCut could readily be applied to killer applications like Magnetic Resonance Imaging analysis and energy minimization in Markov random fields.

Erasure coding for fault oblivious linear system solvers

- Dealing with hardware and software faults is an important problem as parallel and distributed systems scale to millions of processing cores and wide area networks. Traditional methods for dealing with faults include checkpoint-restart, active replicas, and deterministic replay. Each of these techniques has associated resource overheads and constraints. We propose an alternate approach to dealing with faults, based on input augmentation. This approach, which is an algorithmic analog of erasure coded storage, applies a minimally modified algorithm on the augmented input to produce an augmented output. The execution of such an algorithm proceeds completely oblivious to faults in the system. In the event of one or more faults, the real solution is recovered using a rapid reconstruction method from the augmented output. In theory, we proves that the fault tolerance capacity of an encoding matrix can be characterized by its Kruskal rank. We demonstrate this approach on the problem of solving sparse linear systems using a conjugate gradient solver. The experiments show that our approach can be made oblivious to a large number of faults with low computational overhead, representing a significant improvement over the state of the art.

EigenGP: sparse Gaussian process models with data-dependent eigenfunctions

Inference in Gaussian process (GP) model suffers from high computational cost and it is known that designing nonstationary GP prior is difficult in practice. We propose a sparse Gaussian process model called EigenGP based on the Karhunen-Loeve (KL) expansion of a given GP prior. We use the Nystrom approximation to obtain data dependent eigenfunctions and then select these eigenfunctions by evidence maximization. This selection reduces the effective number of eigenfunctions used in EigenGP and simultaneously provides a nonstationary GP prior. The evidence maximization is achieved through an approximate EM using expectation propagation (EP). Given that the eigenfunctions of a Gaussian kernel are associated with clusters of data points, either labeled or unlabled, selecting relevant eigenfunctions enables EigenGP to conduct semi-supervised learning as well.

Group feature selection in high dimensional linear kernel Gaussian process classification

For high dimensional linear kernel Gaussian process classification, identifying the significant features that are informative for prediction not only boosts classification accuracy but also provides useful output for post-analysis from the application domain perspective. Usually the significant features come in groups. Depending on applications, a group could be a region of a human face image, or a time point in time course data. We developed a group automatic relevance determination (GARD) algorithm that is capable of group feature selection in high dimensional linear kernel Gaussian process classification. Compared with alternative methods (e.g., group lasso for logistic regression), GARD does not require any manual tuning of model hyperparameters. Instead it automatically learns the feature relevance coefficients from high dimensional data by maximizing the marginal likelihood using the EP-EM algorithm. When the number of data points is much smaller than the dimension of the feature vector, GARD is very computationally efficient.

Module Propagation: a probabilistic framework for graph mining

- A central task in graph data analysis is to discover subgraphs recurring in a single or multiple graphs. The recurring graphs, once discovered, can help us understand complex graph data and serve to generate informative features for graph search and prediction. Although many multiple graph mining algorithms have been proposed to identify isomorphic subgraphs recurring in multiple unweighted graphs, the problem of discovering representative modules that are similar but not necessarily isomorphic from a single or multiple weighted graphs has not been well studied yet. Solving this problem is critical because most real world graphs are weighted and noisy. We propose a probabilistic framework called Module Propagation (MP) that formulates the problem as an energy minimization task in a specially constructed Markov random field. Using this approach we can efficiently decompose a single or multiple weighted graphs into a set of similar representative modules. To test the usefulness of modules discovered by MP, we apply them to two graph classification applications: chemical compounds activity classification and crystal structures prototype classification. On both applications, MP achieves significantly higher prediction accuracy than other graph feature extraction algorithms.