Within a large database 𝒢 containing graphs with labeled nodes and directed, multi-edges; how can we detect the anomalous graphs? Most existing work are designed for plain (unlabeled) and/or simple (unweighted) graphs. We introduce CODEtect , the first approach that addresses the anomaly detection task for graph databases with such complex nature. To this end, it identifies a small representative set 𝒮 of structural patterns (i.e., node-labeled network motifs) that losslessly compress database 𝒢 as concisely as possible. Graphs that do not compress well are flagged as anomalous. CODEtect exhibits two novel building blocks: (i) a motif-based lossless graph encoding scheme, and (ii) fast memory-efficient search algorithms for 𝒮. We show the effectiveness of CODEtect on transaction graph databases from three different corporations and statistically similar synthetic datasets, where existing baselines adjusted for the task fall behind significantly, across different types of anomalies and performance metrics.

Given a set of node-labeled directed weighted graphs, how to find the most anomalous ones? How can we summarize the normal behavior in the database without losing information? We propose GAWD, for detecting anomalous graphs in directed weighted graph databases. The idea is to (1) iteratively identify the "best" substructure (i.e., subgraph or motif) that yields the largest compression when each of its occurrences is replaced by a super-node, and (2) score each graph by how much it compresses over iterations --- the more the compression, the lower the anomaly score. Different from existing work [1] on which we build, GAWD exhibits (i) a lossless graph encoding scheme, (ii) ability to handle numeric edge weights, (iii) interpretability by common patterns, and (iv) scalability with running time linear in input size. Experiments on four datasets injected with anomalies show that GAWD achieves significantly better results than state-of-the-art baselines.

Error correcting codes are a fundamental component in modern day communication systems, demanding extremely high throughput, ultra-reliability and low latency. Recent approaches using machine learning (ML) models as decoders offer both improved performance and great adaptability to unknown environments, where traditional decoders struggle. We introduce a general framework to further boost the performance and applicability of ML models. We propose to combine ML decoders with a competing discriminator network that tries to distinguish between codewords and noisy words, and, hence, guides the decoding models to recover transmitted codewords. Our framework is game-theoretic, motivated by generative adversarial networks (GANs), with the decoder and discriminator competing in a zero-sum game. The decoder learns to simultaneously decode and generate codewords while the discriminator learns to tell the difference between decoded outputs and codewords. Thus, the decoder is able to decode noisy received signals into codewords, increasing the probability of successful decoding. We show a strong connection of our framework with the optimal maximum likelihood decoder by proving that this decoder defines a Nash equilibrium point of our game. Hence, training to equilibrium has a good possibility of achieving the optimal maximum likelihood performance. Moreover, our framework does not require training labels, which are typically unavailable during communications, and, thus, seemingly can be trained online and adapt to channel dynamics. To demonstrate the performance of our framework, we combine it with recent neural decoders and show improved performance compared to the original models and traditional decoding algorithms on various codes.

Edge computing has revolutionized the world of mobile and wireless networks world thanks to its flexible, secure, and performing characteristics. Lately, we have witnessed the increasing use of it to make more performing the deployment of machine learning (ML) techniques such as federated learning (FL). FL was debuted to improve communication efficiency compared to conventional distributed machine learning (ML). The original FL assumes a central aggregation server to aggregate locally optimized parameters and might bring reliability and latency issues. In this paper, we conduct an in-depth study of strategies to replace this central server by a flying master that is dynamically selected based on the current participants and/or available resources at every FL round of optimization. Specifically, we compare different metrics to select this flying master and assess consensus algorithms to perform the selection. Our results demonstrate a significant reduction of runtime using our flying master FL framework compared to the original FL from measurements results conducted in our EdgeAI testbed and over real 5G networks using an operational edge testbed.

Federated learning has emerged recently as a promising solution for distributing machine learning tasks through modern networks of mobile devices. Recent studies have obtained lower bounds on the expected decrease in model loss that is achieved through each round of federated learning. However, convergence generally requires a large number of communication rounds, which induces delay in model training and is costly in terms of network resources. In this paper, we propose a fast-convergent federated learning algorithm, called$\mathsf {FOLB}$, which performs intelligent sampling of devices in each round of model training to optimize the expected convergence speed. We first theoretically characterize a lower bound on improvement that can be obtained in each round if devices are selected according to the expected improvement their local models will provide to the current global model. Then, we show that$\mathsf {FOLB}$obtains this bound through uniform sampling by weighting device updates according to their gradient information.$\mathsf {FOLB}$is able to handle both communication and computation heterogeneity of devices by adapting the aggregations according to estimates of device’s capabilities of contributing to the updates. We evaluate$\mathsf {FOLB}$in comparison with existing federated learning algorithms and experimentally show its improvement in trained model accuracy, convergence speed, and/or model stability across various machine learning tasks and datasets.

Given a labeled dataset that contains a rare (or minority) class containing of-interest instances, as well as a large class of instances that are not of interest, how can we learn to recognize future of-interest instances over a continuous stream? The setting is different from traditional classification in that instances from novel minority subclasses might continually emerge over time—and hence is often referred as continual, life-long, or open-world classification. We introduce RaRecognize, which ( i ) estimates a general decision boundary between the rare class and the majority class, ( ii ) learns to recognize the individual rare subclasses that exist within the training data, as well as ( iii ) flags instances from previously unseen rare subclasses as newly emerging (i.e., novel). The learner in (i) is general in the sense that by construction it is dissimilar to the specialized learners in (ii) , thus distinguishes minority from the majority without overly tuning to what is only seen in the training data. Thanks to this generality, RaRecognize ignores all future instances that it labels as majority and recognizes the recurring as well as emerging rare subclasses only. This saves effort at test time as well as ensures that the model size grows moderately over time as it only maintains specialized minority learners. Overall, we build an end-to-end system which consists of (1) a representation learning component that transforms data instances into suitable vector inputs; (2) a continual classifier that labels incoming instances as majority (not of interest), rare recurrent, or rare emerging; and (3) a clustering component that groups the rare emerging instances into novel subclasses for expert vetting and model re-training. Through extensive experiments, we show that RaRecognize outperforms state-of-the art baselines on three real-world datasets that contain documents related to corporate-risk and (natural and man-made) disasters as rare classes.

Cyber-epidemics, the widespread of fake news or propaganda through social media, can cause devastating economic and political consequences. A common countermeasure against cyber-epidemics is to disable a small subset of suspected social connections or accounts to effectively contain the epidemics. An example is the recent shutdown of 125,000 ISIS-related Twitter accounts. Despite many proposed methods to identify such a subset, none are scalable enough to provide high-quality solutions in nowadays' billion-size networks. To this end, we investigate the Spread Interdiction problems that seek the most effective links (or nodes) for removal under the well-known Linear Threshold model. We propose novel CPU-GPU methods that scale to networks with billions of edges, yet possess rigorous theoretical guarantee on the solution quality. At the core of our methods is an O(1)-space out-of-core algorithm to generate a new type of random walks, called Hitting Self-avoiding Walks (HSAWs). Such a low memory requirement enables handling of big networks and, more importantly, hiding latency via scheduling of millions of threads on GPUs. Comprehensive experiments on real-world networks show that our algorithms provide much higher quality solutions and are several orders of magnitude faster than the state-of-the art. Comparing to the (single-core) CPU counterpart, our GPU implementations achieve significant speedup factors up to 177× on a single GPU and 338× on a GPU pair.

The blooming availability of traces for social, biological, and communication networks opens up unprecedented opportunities in analyzing diffusion processes in networks. However, the sheer sizes of the nowadays networks raise serious challenges in computational efficiency and scalability. In this paper, we propose a new hyper-graph sketching framework for influence dynamics in networks. The core of our sketching framework, called SKIS, is an efficient importance sampling algorithm that returns only non-singular reverse cascades in the network. Comparing to previously developed sketches like RIS and SKIM, our sketch significantly enhances estimation quality while substantially reducing processing time and memory-footprint. Further, we present general strategies of using SKIS to enhance existing algorithms for influence estimation and influence maximization which are motivated by practical applications like viral marketing. Using SKIS, wedesign high-quality influence oracles for seed sets with average estimation error up to 10x times smaller than those using RIS and 6x times smaller than SKIMs. In addition, our influence maximization using SKIS substantially improves the quality of solutions for greedy algorithms. It achieves up to 10x times speed-up and 4x memory reduction for the fastest RIS-based DSSA algorithm, while maintaining the same theoretical guarantees.

Given a social network, the Influence Maximization (InfMax) problem seeks a seed set of k people that maximizes the expected influence for a viral marketing campaign. However, a solution for a particular seed size k is often not enough to make an informed choice regarding budget and cost-effectiveness. In this article, we propose the computation of Influence Spectrum (InfSpec), the maximum influence at each possible seed set size k within a given range [ k lower , k upper ], thus providing optimal decision making for any availability of budget or influence requirements. As none of the existing methods for InfMax are efficient enough for the task in large networks, we propose LISA (sub-Linear Influence Spectrum Approximation), an efficient approximation algorithm for InfSpec (and also InfMax) with the best-known worst-case guarantees for billion-scale networks. LISA returns an (1-1/e -ϵ)-approximate influence spectrum with high probability (1-δ), where ϵ, δ are precision parameters provided by users. Using statistical decision theory, LISA has an asymptotic optimal running time (in addition to optimal approximation guarantee). In practice, LISA surpasses the state-of-the-art InfMax methods, taking less than 15 minutes to process a network of 41.7 million nodes and 1.5 billions edges.

Online social networks have been one of the most effective platforms for marketing and advertising. Through the “world-of-mouth” exchanges, so-called viral marketing, the influence and product adoption can spread from few key influencers to billions of users in the network. To identify those key influencers, a great amount of work has been devoted for the influence maximization (IM) problem that seeks a set of k seed users that maximize the expected influence. Unfortunately, IM encloses two impractical assumptions: 1) any seed user can be acquired with the same cost and 2) all users are equally interested in the advertisement. In this paper, we propose a new problem, called cost-aware targeted viral marketing (CTVM), to find the most costeffective seed users, who can influence the most relevant users to the advertisement. Since CTVM is NP-hard, we design an efficient (1 - 1/√e - ∈)-approximation algorithm, named Billion-scale Cost-award Targeted algorithm (BCT), to solve the problem in billion-scale networks. Comparing with IM algorithms, we show that BCT is both theoretically and experimentally faster than the state-of-the-arts while providing better solution quality. Moreover, we prove that under the linear threshold model, BCT is the first sub-linear time algorithm for CTVM (and IM) in dense networks. We carry a comprehensive set of experiments on various real-networks with sizes up to several billion edges in diverse disciplines to show the absolute superiority of BCT on both CTVM and IM domains. Experiments on Twitter data set, containing 1.46 billions of social relations and 106 millions tweets, show that BCT can identify key influencers in trending topics in only few minutes.

Given an aftermath of a cascade in the network, i.e. a set VI of "infected" nodes after an epidemic outbreak or a propagation of rumors/worms/viruses, how can we infer the sources of the cascade? Answering this challenging question is critical for computer forensic, vulnerability analysis, and risk management. Despite recent interest towards this problem, most of existing works focus only on single source detection or simple network topologies, e.g. trees or grids. In this paper, we propose a new approach to identify infection sources by searching for a seed set S that minimizes the symmetric difference between the cascade from S and VI, the given set of infected nodes. Our major result is an approximation algorithm, called SISI, to identify infection sources without the prior knowledge on the number of source nodes. SISI, to our best knowledge, is the first algorithm with provable guarantee for the problem in general graphs. It returns a 2/((1-ε)2 Δ-approximate solution with high probability, where Δ denotes the maximum number of nodes in VI that may infect a single node in the network. Our experiments on real-world networks show the superiority of our approach and SISI in detecting true source(s), boosting the F1-measure from few percents, for the state-of-the-art NETSLEUTH, to approximately 50%.

Online social networks have been one of the most effective platforms for marketing and advertising. Through the “world-of-mouth” exchanges, so-called viral marketing, the influence and product adoption can spread from few key influencers to billions of users in the network. To identify those key influencers, a great amount of work has been devoted for the Influence Maximization (IM) problem that seeks a set of k seed users that maximize the expected influence. Unfortunately, IM encloses two impractical assumptions: 1) any seed user can be acquired with the same cost and 2) all users are equally interested in the advertisement. In this paper, we propose a new problem, called Cost-aware Targeted Viral Marketing (CTVM), to find the most cost-effective seed users who can influence the most relevant users to the advertisement. Since CTVM is NP-hard, we design an efficient (1 − 1/√e-∊ − e)-approximation algorithm, named BCT, to solve the problem in billion-scale networks. Comparing with IM algorithms, we show that BCT is both theoretically and experimentally faster than the state-of-the-arts while providing better solution quality. Moreover, we prove that under the Linear Threshold model, BCT is the first sub-linear time algorithm for CTVM (and IM) in dense networks. In our experiments with a Twitter dataset, containing 1.46 billions of social relations and 106 millions tweets, BCT can identify key influencers in each trending topic in only few minutes.

Influence Maximization (IM), that seeks a small set of key users who spread the influence widely into the network, is a core problem in multiple domains. It finds applications in viral marketing, epidemic control, and assessing cascading failures within complex systems. Despite the huge amount of effort, IM in billion-scale networks such as Facebook, Twitter, and World Wide Web has not been satisfactorily solved. Even the state-of-the-art methods such as TIM+ and IMM may take days on those networks. In this paper, we propose SSA and D-SSA, two novel sampling frameworks for IM-based viral marketing problems. SSA and D-SSA are up to 1200 times faster than the SIGMOD'15 best method, IMM, while providing the same (1-1/e-ε) approximation guarantee. Underlying our frameworks is an innovative Stop-and-Stare strategy in which they stop at exponential check points to verify (stare) if there is adequate statistical evidence on the solution quality. Theoretically, we prove that SSA and D-SSA are the first approximation algorithms that use (asymptotically) minimum numbers of samples, meeting strict theoretical thresholds characterized for IM. The absolute superiority of SSA and D-SSA are confirmed through extensive experiments on real network data for IM and another topic-aware viral marketing problem, named TVM.