Deep learning models rely on highly optimized tensor libraries for efficient inference on heterogeneous hardware. Current deep compilers typically predetermine layouts of tensors and then optimize loops of operators. However, such unidirectional and one-off workflow strictly separates graph-level optimization and operator-level optimization into different system layers, missing opportunities for unified tuning.

Traditional deep learning compilers rely on heuristics for subgraph generation, which impose extra constraints on graph optimization, e.g., each subgraph can only contain at most one complex operator. In this paper, we propose AGO, a framework for graph optimization with arbitrary structures to boost the inference performance of deep models by removing such constraints. To create new optimization opportunities for complicated subgraphs, we propose intensive operator fusion, which effectively stitches multiple complex operators together for better performance. Further, we design a graph partitioning scheme that allows an arbitrary structure for each subgraph while guaranteeing the acyclic property among all generated subgraphs. Additionally, to enable efficient performance tuning for complicated subgraphs, we devise a divide-and-conquer tuning mechanism to orchestrate different system components. Through extensive experiments on various neural networks and mobile devices, we show that our system can improve the inference performance by up to 3.3× when compared with state-of-the-art vendor libraries and deep compilers.

The rapid expansion of global cloud wide-area networks (WANs) has posed a challenge for commercial optimization engines to efficiently solve network traffic engineering (TE) problems at scale. Existing acceleration strategies decompose TE optimization into concurrent subproblems but realize limited parallelism due to an inherent tradeoff between run time and allocation performance.

Traditional DDoS attack detection monitors volumetric traffic features to detect attack onset. To reduce false positives, such detection is often conservative---raising an alert only after a sustained period of observed anomalous behavior. However, contemporary attacks tend to be short, which combined with a long detection delay means that most of the attack still reaches and impacts the victim. We propose Xatu, a system that utilizes auxiliary signals to improve the accuracy and timeliness of existing DDoS detection systems. We explore two types of auxiliary signals, attack preparation signals and the history of prior attacks. These signals can be easily mined from existing traffic monitoring systems in many ISP networks. To leverage these auxiliary signals for attack detection, we propose a multi-timescale LSTM model, which derives both long-term and short-term patterns from diverse auxiliary signals. We then leverage survival analysis to quickly detect attacks when they occur while minimizing false positives and thus scrubbing costs. We evaluate Xatu on traffic from a large ISP, using commercial defense alert data to label prevalent attack events. Xatu would help the commercial defense scrub up to 44.1% additional anomalous traffic and would reduce its median detection delay by 9.5 minutes.1

In networks where massive sources make observations of same entities, we intend to seek thetruth– the most trustworthy value of each entity from conflicting information claimed by multiple sources. Various methods are proposed for accurately inferring both source reliability and truths, yet relying heavily on centralized settings that incur tremendous overhead to source side. In this paper, we offer adecentralizeddesign of truth discovery task that can fit favorably to the environments with limited resources. Considering that sources forming the connected network and making individual observations, we undertake the joint maximum likelihood estimation (MLE) of truth and source reliability. Our decentralization framework simply allows each source to maintain local information exchange at a time, and computes very basic functions of data observations. To this end, we facilitate the decentralization by simplifying the MLE problem into optimizing an objective function. Upon the proof of NP-hardness, two proposed decentralized algorithms (exact and approximation) are decentralized and randomized via a combination of algorithms from their centralized counterparts that ensure performance guarantee. The derived time complexity features explicit data/network dependent terms, which leads to further acceleration in truth finding. Remarkably, in two well connected networks like random geometric and preferential attachment graphs, the accelerated approximation method enjoys logarithmic time complexity while preserving comparable accuracy to the centralized counterparts. The effectiveness of the proposed decentralizations are further empirically confirmed.

With the advent of the era of big data, deep learning has become a prevalent building block in a variety of machine learning or data mining tasks, such as signal processing, network modeling and traffic analysis, to name a few. The massive user data crowdsourced plays a crucial role in the success of deep learning models. However, it has been shown that user data may be inferred from trained neural models and thereby exposed to potential adversaries, which raises information security and privacy concerns. To address this issue, recent studies leverage the technique of differential privacy to design private-preserving deep learning algorithms. Albeit successful at privacy protection, differential privacy degrades the performance of neural models. In this paper, we develop ADADP, an adaptive and fast convergent learning algorithm with a provable privacy guarantee. ADADP significantly reduces the privacy cost by improving the convergence speed with an adaptive learning rate and mitigates the negative effect of differential privacy upon the model accuracy by introducing adaptive noise. The performance of ADADP is evaluated on real-world datasets. Experiment results show that it outperforms state-of-the-art differentially private approaches in terms of both privacy cost and model accuracy.

This paper studies the problem of optimizing multicast energy consumption in delay-constrained mobile wireless networks, where information from the source needs to be delivered to all the k destinations within an imposed delay constraint. Most existing works simply focus on deriving transmission schemes with the minimum transmitting energy, overlooking the energy consumption at the receiver side. Therefore, in this paper, we propose ConMap, a novel and general framework for efficient transmission scheme design that jointly optimizes both the transmitting and receiving energy. In doing so, we formulate our problem of designing minimum energy transmission scheme, called DeMEM, as a combinatorial optimization one, and prove that the approximation ratio of any polynomial time algorithm for DeMEM cannot be better than (1/4) lnk. Aiming to provide more efficient approximation schemes, the proposed ConMap first converts DeMEM into an equivalent directed Steiner tree problem through creating auxiliary graph gadgets to capture energy consumption, then maps the computed tree back into a transmission scheme. The advantages of ConMap are threefolded: 1) Generality- ConMap exhibits strong applicability to a wide range of energy models; 2) Flexibility- Any algorithm designed for the problem of directed Steiner tree can be embedded into our ConMap framework to achieve different performance guarantees and complexities; 3) Efficiency- ConMap preserves the approximation ratio of the embedded Steiner tree algorithm, to which only slight overhead will be incurred. The three features are then empirically validated, with ConMap also yielding near-optimal transmission schemes compared to a brute-force exact algorithm. To our best knowledge, this is the first work that jointly considers both the transmitting and receiving energy in the design of multicast transmission schemes in mobile wireless networks.

A crucial privacy-driven issue nowadays is re- identifying ano-nymized social networks by mapping them to correlated cross-domain auxiliary networks. Prior works are typically based on modeling social networks as random graphs representing users and their relations, and subsequently quantify the quality of mappings through cost functions that are proposed without sufficient rationale. Also, it remains unknown how to algorithmically meet the demand of such quantifications, i.e., to find the minimizer of the cost functions. We address those concerns in a more realistic social network modeling parameterized by community structures that can be leveraged as side information for de- anonymization. By Maximum A Posteriori (MAP) estimation, our first contribution is new and well justified cost functions, which, when minimized, enjoy superiority to previous ones in finding the correct mapping with the highest probability. The feasibility of the cost functions is then for the first time algorithmically characterized. While proving the general multiplicative inapproximability, we are able to propose two heuristics, which, respectively, enjoy an ε-additive approximation and a conditional optimality in carrying out successful user re- identification. Our theoretical findings are empirically validated,with a notable dataset extracted from rare true cross-domain networks that reproduce genuine social network de-anonymization.

Determination of source-destination connectivity in networks has long been a fundamental problem, where most existing works are based on deterministic graphs that overlook the inherent uncertainty in network links. To overcome such limitation, this paper models the network as an uncertain graph where each edge e exists independently with some probability p(e). The problem examined is that of determining whether a given pair of nodes, a source s and a destination t, are connected by a path or separated by a cut. Assuming that during each determining process we are associated with an underlying graph, the existence of each edge can be unraveled through edge testing at a cost of c(e). Our goal is to find an optimal strategy incurring the minimum expected testing cost with the expectation taken over all possible underlying graphs that form a product distribution. Formulating it into a combinatorial optimization problem, we first characterize the computational complexity of optimally determining source-destination connectivity in uncertain graphs. Specifically, through proving the NP-hardness of two closely related problems, we show that, contrary to its counterpart in deterministic graphs, this problem cannot be solved in polynomial time unless P=NP. Driven by the necessity of designing an exact algorithm, we then apply the Markov Decision Process framework to give a dynamic programming algorithm that derives the optimal strategies. As the exact algorithm may have prohibitive time complexity in practical situations, we further propose two more efficient approximation schemes compromising the optimality. The first one is a simple greedy approach with linear approximation ratio. Interestingly, we show that naive as it is, it has comparable performance than some other seemingly more sophisticated algorithms. Second, by harnessing the sub-modularity of the problem, we further design a more elaborate algorithm with better approximation ratio. The effectiveness of the proposed algorithms are justified through extensive simulations on three real network datasets, from which we demonstrate that the proposed algorithms yield strategies with smaller expected cost than conventional heuristics.

This paper studies the problem of optimizing multicast energy consumption in delay-constrained mobile wireless networks, where information from the source needs to be delivered to all the k destinations within an imposed delay constraint. Most existing works simply focus on deriving transmission schemes with the minimum transmitting energy, overlooking the energy consumption at the receiver side. Therefore, in this paper, we propose ConMap, a novel and general framework for efficient transmission scheme design that jointly optimizes both the transmitting and receiving energy. In doing so, we formulate our problem of designing minimum energy transmission scheme, called DeMEM, as a combinatorial optimization one, and prove that the approximation ratio of any polynomial time algorithm for DeMEM cannot be better than ¼ ln k. Aiming to provide more efficient approximation schemes, the proposed ConMap first converts DeMEM into an equivalent directed Steiner tree problem through creating auxiliary graph gadgets to capture energy consumption, then maps the computed tree back into a transmission scheme. The advantages of ConMap are threefolded: i) Generality-- ConMap exhibits strong applicability to a wide range of energy models; ii) Flexibility-- Any algorithm designed for the problem of directed Steiner tree can be embedded into our ConMap framework to achieve different performance guarantees and complexities; iii) Efficiency-- ConMap preserves the approximation ratio of the embedded Steiner tree algorithm, to which only slight overhead will be incurred. The three features are then empirically validated, with ConMap also yielding near-optimal transmission schemes compared to a brute-force exact algorithm. To our best knowledge, this is the first work that jointly considers both the transmitting and receiving energy in the design of multicast transmission schemes in mobile wireless networks.

Determination of source-destination connectivity in networks has long been a fundamental problem, where most existing works are based on deterministic graphs that overlook the inherent uncertainty in network links. To overcome such limitation, this paper models the network as an uncertain graph, where each edge e exists independently with some probability p(e). The problem examined is that of determining whether a given pair of nodes, a source s and a destination t, are connected by a path or separated by a cut. Assuming that during each determining process we are associated with an underlying graph, the existence of each edge can be unraveled through edge testing at a cost of c(e). Our goal is to find an optimal strategy incurring the minimum expected testing cost with the expectation taken over all possible underlying graphs that form a product distribution. Formulating it into a combinatorial optimization problem, we first characterize the computational complexity of optimally determining source-destination connectivity in uncertain graphs. Specifically, through proving the NP-hardness of two closely related problems, we show that, contrary to its counterpart in deterministic graphs, this problem cannot be solved in polynomial time unless P = NP. Driven by the necessity of designing an exact algorithm, we then apply the Markov decision process framework to give a dynamic programming algorithm that derives the optimal strategies. As the exact algorithm may have prohibitive time complexity in practical situations, we further propose two more efficient approximation schemes compromising the optimality. The first one is a simple greedy approach with linear approximation ratio. Interestingly, we show that naive as it is, and it enjoys significantly better performance guarantee than some other seemingly more sophisticated algorithms. Second, by harnessing the submodularity of the problem, we further design a more elaborate algorithm with better approximation ratio. The effectiveness of the proposed algorithms is justified through extensive simulations on three real network data sets, from which we demonstrate that the proposed algorithms yield strategies with smaller expected cost than conventional heuristics.