Crossbar-based resistive RAM has been widely used in deep learning accelerator designs because it largely eliminates weight movement between memory and processing units. The high-density storage and low leakage power make it a good fit for edge/IoT devices. However, existing ReRAM designs for traditional neural networks cannot support Attention-based Neural Networks, which are stacked with encoders and decoders instead of convolutional layers or fully connected layers. In addition to matrix-matrix multiplications in traditional neural networks, an encoder or a decoder also includes the attention mechanism, the layer normalization and the gaussian error linear unit. These new characteristics make the data flow far more complicated than that of a convolutional layer. Faulty ReRAM devices are additional obstacles when mapping weights that severely degrade computation accuracy. Existing hardware redundancy strategies that are unaware of application characteristics usually result in inefficient designs. In this work, we analyze the data flow of these attention-based neural networks and propose a ReRAM-based accelerator with a dedicated pipeline design for Attention-based Neural Networks. When considering cells with hard faults in crossbars, we further propose NuXG, a non-uniform redundancy strategy, to meet accuracy requirements and save energy consumption by decreasing the redundancy ratio. Finally, we evaluate results and demonstrate that the proposed can achieve more than two times improved performance over existing redundancy schemes in both power efficiency and throughput for Attention-based Neural Networks. Moreover, it also significantly outperforms an NVIDIA GPU.

Recent studies identify that Deep learning Neural Networks (DNNs) are vulnerable to subtle perturbations, which are not perceptible to the human visual system but can fool the DNN models and lead to wrong outputs. These algorithms are the first efforts to move forward to secure deep learning by providing an avenue to train future defense networks. We propose the first hardware accelerator for adversarial attacks based on memristor crossbar arrays. Our design significantly improves the throughput of a visual adversarial perturbation system, which can further improve the robustness and security of future deep learning systems. Based on the algorithm uniqueness, we propose four implementations for the adversarial attack accelerator (A^3) to improve the throughput, energy efficiency, and computational efficiency.

Malware targeting mobile devices is a pervasive problem in modern life. The detection of malware is essentially a software classification problem based on information gathered from program analysis. We focus on classification of Android applications using system API-call sequences and investigate the effectiveness of Deep Neural Networks (DNNs) for such purpose. The ability of DNNs to learn complex and flexible features may lead to timely and effective detection of malware. We design a Convolutional Neural Network (CNN) for sequence classification and conduct a set of experiments on malware detection and categorization of software into functionality groups to test and compare our CNN with classifications by recurrent neural network (LSTM) and other n-gram based methods. Both CNN and LSTM significantly outperformed n-gram based methods. Surprisingly, the performance of our CNN is also much better than that of the LSTM, which is considered a natural choice for sequential data.

In materials science, micro-level (atomic-scale) activities are considered to be the key to understanding various macro-level (bulk) properties of a material. Molecular dynamics simulations are widely used to obtain atom dynamics. However, researchers are often too overwhelmed by the amount of simu lation data to discover relevant atomic activities. Furthermore, mining the structure graph of a material (the graph where the constituent atoms form nodes and the bonds between the atoms form edges) offers little help in this scenario. It is the patterns among the atomic dynamics that may reveal the mechanisms underlying a particular material property. Discovery of such patterns can lead to a better model and better predictions of the properties and behaviors of the materials. We propose an event graph to model the atomic dynamics and propose a graph mining algorithm to discover popular subgraphs in the event graph. Because the event graph is a directed acyclic graph, our mining algorithm uses a new graph encoding scheme that is based on topological-sorting. This encoding scheme ensures that our algorithm enumerates candidate subgraphs without any duplication. Experiments with simulation data of silica liquid demonstrate the effectiveness of our mining system which we call ``ToPoMine''.

We introduce a new method for classification called the influence machine. The influence machine assigns influence powers to the instances in the training sample so that they can apply their influence to other instances through the connections between the instances specified by a connection matrix. A new instance is classified to be positive if the overall influence it receives is positive and vice versa. Similar to support vector machine (SVM), the influence machine selects a small subset of the training instances to give influence power. However, this selection is very different from how the support vectors are selected by SVM. Experiment results show that the classification performance of the influence machine is comparable to that of the SVM. In a few cases, the influence machine shows much better classification accuracy. The influence machine has other advantages: any similarity matrix can be applied with the influence machine, not like SVM which requires that the kernel be positive definite. Furthermore, the influence machine uses linear optimization, instead of the quadratic optimization used by SVM. It may be more suitable for large scale learning problems.

Transfer learning is a new learning paradigm, in which, besides the training data for the targeted learning task, data that are related to the task (often under a different distribution) are also employed to help train a better learner. For example, out-dated data can be used as such related data. In this paper, we propose a new transfer learning framework for training neural network (NN) ensembles. The framework has two key features: 1) it uses the well-known negative correlation learning to train an ensemble of diverse neural networks from the related data, fully discovering the knowledge in the data; and 2) a penalized incremental learning scheme is used to adapt the neural networks obtained from negative correlation learning to the training data for the targeted learning task. The adaptation is guided by reference neural networks that measure the relatedness between the training and the related data. Experiments on benchmark data sets show that our framework can achieve classification accuracy competitive to existing ensemble transfer learning methods such as TrAdaBoost and TrBagg. We discuss some characteristics of our framework observed in the experiment and the scenarios under which the framework may have superior performance.

One important problem in machine learning is how to extract knowledge from prior experience, then transfer and apply this knowledge in new learning tasks. To address this problem, transfer learning leverages information from (supervised) learning on related tasks to facilitate the current learning task. Self-taught learning uses information extracted from (unsupervised) learning on related data. In this paper, we propose a new method for knowledge extraction, transfer and application in classification. We consider document classification where we mine correlation relationships among the words from a set of documents and compile a collection of correlation relationships as prior knowledge. This knowledge is then applied to generate new features for classifying documents in classes/types different from the ones from which we obtain the correlation relationships. Our experiment results show that the correlation-based knowledge transfer helps to reduce classification errors.

Network security has been a serious concern for many years. For example, firewalls often record thousands of exploit attempts on a daily basis. Network administrators could benefit from information on potential aggressive attack sources, as such information can help to proactively defend their networks. For this purpose, several large-scale information sharing systems have been established, in which information on cyberattacks targeting each participant network is shared such that a network can be forewarned of attacks observed by others. However, the total number of reported attackers is huge in these systems. Thus, a challenging problem is to identify the attackers that are most relevant to each individual network (i.e., most likely to come to that network in the near future). We present a framework to estimate the relevance of each attacker with respect to each network. In particular, we model each attacker's relevance as a function over the networks. Different attackers have different functions. The distribution of the functions is modeled using a Gaussian process (GP). The relevance function of each attacker is then inferred from the Gaussian process, that itself is learned from the collection of attack information. We test our framework on the attack reports in the DShield information sharing system. Experiments show that attackers found relevant to a network by our framework are indeed more likely to come to that network in the future.

We explore problems related to computing graph distances in the data-stream model. The goal is to design algorithms that can process the edges of a graph in an arbitrary order given only a limited amount of working memory. We are motivated by both the practical challenge of processing massive graphs such as the web graph and the desire for a better theoretical understanding of the data-stream model. In particular, we are interested in the trade-offs between model parameters such as per-data-item processing time, total space, and the number of passes that may be taken over the stream. These trade-offs are more apparent when considering graph problems than they were in previous streaming work that solved problems of a statistical nature. Our results include the following: (1) Spanner construction: There exists a single-pass, $\tilde{O}(tn^{1+1/t})$-space, $\tilde{O}(t^2n^{1/t})$-time-per-edge algorithm that constructs a $(2t+1)$-spanner. For $t=\Omega(\log n/{\log\log n})$, the algorithm satisfies the semistreaming space restriction of $O(n\operatorname{polylog}n)$ and has per-edge processing time $O(\operatorname{polylog}n)$. This resolves an open question from [J. Feigenbaum et al., Theoret. Comput. Sci., 348 (2005), pp. 207–216]. (2) Breadth-first-search (BFS) trees: For any even constant k, we show that any algorithm that computes the first k layers of a BFS tree from a prescribed node with probability at least $2/3$ requires either greater than $k/2$ passes or $\tilde{\Omega}(n^{1+1/k})$ space. Since constructing BFS trees is an important subroutine in many traditional graph algorithms, this demonstrates the need for new algorithmic techniques when processing graphs in the data-stream model. (3) Graph-distance lower bounds: Any t-approximation of the distance between two nodes requires $\Omega(n^{1+1/t})$ space. We also prove lower bounds for determining the length of the shortest cycle and other graph properties. (4) Techniques for decreasing per-edge processing: We discuss two general techniques for speeding up the per-edge computation time of streaming algorithms while increasing the space by only a small factor.

When a data set contains objects of multiple types, to cluster the objects of one type, it is often necessary to consider the cluster structure on the objects of the other types. Co-clustering the related objects often generates better clusters. One basic connection here is that the similarity among the objects of one type is often affected by the cluster structures on the objects of the other types. Although many co-clustering schemes have been proposed, none has explicitly explored such a connection. We propose a framework that utilizes this connection directly. In this framework, employing a spectral-embedding- based approach, we first obtain certain approximate cluster information about the objects of individual types. Such information is then used to refine the similarity measures for the objects of the related types. The final clustering is performed with the refined similarity. We tested our framework on both bipartite-graph and document clustering. Our experiments showed that the refined similarity leads to much better clustering, indicating that our refinement makes the similarity measures closer to their true values.

We consider the problem of finding highly correlated pairs in a large data set. That is, given a threshold not too small, we wish to report all the pairs of items (or binary attributes) whose (Pearson) correlation coefficients are greater than the threshold. Correlation analysis is an important step in many statistical and knowledge-discovery tasks. Normally, the number of highly correlated pairs is quite small compared to the total number of pairs. Identifying highly correlated pairs in a naive way by computing the correlation coefficients for all the pairs is wasteful. With massive data sets, where the total number of pairs may exceed the main-memory capacity, the computational cost of the naive method is prohibitive. In their KDD'04 paper [15], Hui Xiong et al. address this problem by proposing the TAPER algorithm. The algorithm goes through the data set in two passes. It uses the first pass to generate a set of candidate pairs whose correlation coefficients are then computed directly in the second pass. The efficiency of the algorithm depends greatly on the selectivity (pruning power) of its candidate-generating stage.In this work, we adopt the general framework of the TAPER algorithm but propose a different candidate-generation method. For a pair of items, TAPER's candidate-generation method considers only the frequencies (supports) of individual items. Our method also considers the frequency (support) of the pair but does not explicitly count this frequency (support). We give a simple randomized algorithm whose false-negative probability is negligible. The space and time complexities of generating the candidate set in our algorithm are asymptotically the same as TAPER's. We conduct experiments on synthesized and real data. The results show that our algorithm produces a greatly reduced candidate set - one that can be several orders of magnitude smaller than that generated by TAPER. Because of this, our algorithm uses much less memory and can be faster. The former is critical for dealing with massive data.

For an unweighted undirected graph G= (V,E), and a pair of positive integers α ≥ 1, β ≥ 0, a subgraph G'= (V,H), H ⊆ E, is called an (α,β)-spanner of G if for every pair of vertices u, v ∈ V, distG'(u,v) ≤ α • distG'(u,v) + β.It was shown in [20] that for any e > 0, κ = 1,2, ..., there exists an integer β = β(e,κ) such that for every n-vertex graph G there exists a (1+e,β)-spanner G' with O(n1+1/κ) edges. An efficient distributed protocol for constructing (1+e,β)-spanners was devised in [18]. The running time and the communication complexity of that protocol are O(n1+ρ) and O(|E|nρ), respectively, where ρ is an additional control parameter of the protocol that affects only the additive term β.In this paper we devise a protocol with a drastically improved running time (O(nρ) as opposed to (O(n1+ρ) for constructing (1+e,β)-spanners. Our protocol has the same communication complexity as the protocol of [18], and it constructs spanners with essentially the same properties as the spanners that are constructed by the protocol of [18].We also show that our protocol for constructing (1+e, β)-spanners can be adapted to the streaming model, and devise a streaming algorithm that uses a constant number of passes and O(n1+1/κ • log n) bits of space for computing all-pairs-almost-shortest-paths of length at most by a multiplicative factor (1 + e) and an additive term of β greater than the shortest paths. Our algorithm processes each edge in time O(nρ), for an arbitrarily small ρ > 0. The only previously known algorithm for the problem [21] constructs paths of length κ times greater than the shortest paths, has the same space requirements as our algorithm, but requires O(n1+1/κ) time for processing each edge of the input graph. However, the algorithm of [21] uses just one pass over the input, as opposed to the constant number of passes in our algorithm. We also show that any streaming algorithm for o(n)-approximate distance computation requires Ω(n) bits of space.