During the COVID-19 pandemic, a major driver of new surges has been the emergence of new variants. When a new variant emerges in one or more countries, other nations monitor its spread in preparation for its potential arrival. The impact of the new variant and the timings of epidemic peaks in a country highly depend on when the variant arrives. The current methods for predicting the spread of new variants rely on statistical modeling, however, these methods work only when the new variant has already arrived in the region of interest and has a significant prevalence. Can we predict when a variant existing elsewhere will arrive in a given region? To address this question, we propose a variant-dynamics-informed Graph Neural Network (GNN) approach. First, we derive the dynamics of variant prevalence across pairs of regions (countries) that apply to a large class of epidemic models. The dynamics motivate the introduction of certain features in the GNN. We demonstrate that our proposed dynamics-informed GNN outperforms all the baselines, including the currently pervasive framework of Physics-Informed Neural Networks (PINNs). To advance research in this area, we introduce a benchmarking tool to assess a user-defined model's prediction performance across 87 countries and 36 variants.

Individual models of infectious diseases or trajectories coming from different simulations may vary considerably, making it challenging for public communication and supporting policy-making. Therefore, it is common in public health to first create a consensus across multiple models and simulations through ensembling. However, current methods are limited to mean and median ensembles that perform aggregation of scale (cases, hospitalizations, deaths) along the time axis, which often misrepresents the underlying trajectories -- e.g., they underrepresent the peak. Instead, we wish to create an ensemble that represents aggregation simultaneously over both time and scale and thus better preserves the properties of the trajectories. This is particularly useful for public health where time-series have a sequence of meaningful local trends that are ordered, e.g., a surge to an increase to a peak to a decrease. We propose a novel alignment method DTW+SBA, which combines a representation of local trends along with dynamic time warping barycenter averaging. We prove key properties of this method that ensure appropriate alignment based on local trends. We demonstrate on real multi-model outputs that our approach preserves the properties of underlying trajectories. We also show that our alignment leads to a more sensible clustering of epidemic trajectories.

Indirect surveys, in which respondents provide information about other people they know, have been proposed for estimating (nowcasting) the size of a hidden population where privacy is important or the hidden population is hard to reach. Examples include estimating casualties in an earthquake, conditions among female sex workers, and the prevalence of drug use and infectious diseases. The Network Scale-up Method (NSUM) is the classical approach to developing estimates from indirect surveys, but it was designed for one-shot surveys. Further, it requires certain assumptions and asking for or estimating the number of individuals in each respondent's network. In recent years, surveys have been increasingly deployed online and can collect data continuously (e.g., COVID-19 surveys on Facebook during much of the pandemic). Conventional NSUM can be applied to these scenarios by analyzing the data independently at each point in time, but this misses the opportunity of leveraging the temporal dimension. We propose to use the responses from indirect surveys collected over time and develop analytical tools (i) to prove that indirect surveys can provide better estimates for the trends of the hidden population over time, as compared to direct surveys and (ii) to identify appropriate temporal aggregations to improve the estimates. We demonstrate through extensive simulations that our approach outperforms traditional NSUM and direct surveying methods. We also empirically demonstrate the superiority of our approach on a real indirect survey dataset of COVID-19 cases.

While the worst of COVID-19 pandemic has most likely passed us, an occurrence of equally devastating global pandemic or regional epidemic cannot be ruled out in future. H1N1, Zika, SARS, MERS, and Ebola outbreaks over the past few decades have sharply illustrated our enormous vulnerability to emerging infectious diseases. While the data mining research community has demonstrated increased interest in epidemiological applications, much is still left to be desired. For example, there is an urgent need to develop sound theoretical principles and transformative computational approaches that will allow us to address the escalating threat of current and future pandemics. Data mining and knowledge discovery have an important role to play in this regard. Different aspects of infectious disease modeling, analysis, and control have traditionally been studied within the confines of individual disciplines, such as mathematical epidemiology and public health, and data mining and machine learning. Coupled with increasing data generation across multiple domains/sources (e.g., wastewater surveillance, electronic medical records, and social media), there is a clear need for analyzing them to inform public health policies and outcomes timely. Recent advances in disease surveillance and forecasting, and initiatives such as the CDC Flu Challenge, CDC COVID-19 Forecasting Hub etc., have brought these disciplines closer together. On the one hand, public health practitioners seek to use novel datasets, such as Safegraph, Unacast, and Google mobility data, and techniques like Graph Neural Networks. On the other hand, researchers from data mining and machine learning develop novel tools for solving many fundamental problems in the public health policy planning and decision-making process, leveraging novel datasets (e.g., COVID-19 behavioral health surveys, contact tracing trees, and satellite images of urban streets) and combining them with more traditional time series information (e.g., surveillance, hospitalization, and death records). We believe the next stage of advances will result from closer collaborations between these two groups, which is the main objective of epiDAMIK.

During the COVID-19 pandemic, forecasting COVID-19 trends to support planning and response was a priority for scientists and decision makers alike. In the United States, COVID-19 forecasting was coordinated by a large group of universities, companies, and government entities led by the Centers for Disease Control and Prevention and the US COVID-19 Forecast Hub (https://covid19forecasthub.org). We evaluated approximately 9.7 million forecasts of weekly state-level COVID-19 cases for predictions 1-4 weeks into the future submitted by 24 teams from August 2020 to December 2021. We assessed coverage of central prediction intervals and weighted interval scores (WIS), adjusting for missing forecasts relative to a baseline forecast, and used a Gaussian generalized estimating equation (GEE) model to evaluate differences in skill across epidemic phases that were defined by the effective reproduction number. Overall, we found high variation in skill across individual models, with ensemble-based forecasts outperforming other approaches. Forecast skill relative to the baseline was generally higher for larger jurisdictions (e.g., states compared to counties). Over time, forecasts generally performed worst in periods of rapid changes in reported cases (either in increasing or decreasing epidemic phases) with 95% prediction interval coverage dropping below 50% during the growth phases of the winter 2020, Delta, and Omicron waves. Ideally, case forecasts could serve as a leading indicator of changes in transmission dynamics. However, while most COVID-19 case forecasts outperformed a naïve baseline model, even the most accurate case forecasts were unreliable in key phases. Further research could improve forecasts of leading indicators, like COVID-19 cases, by leveraging additional real-time data, addressing performance across phases, improving the characterization of forecast confidence, and ensuring that forecasts were coherent across spatial scales. In the meantime, it is critical for forecast users to appreciate current limitations and use a broad set of indicators to inform pandemic-related decision making.

The traditional methods for detecting autism spectrum disorder (ASD) are expensive, subjective, and time-consuming, often taking years for a diagnosis, with many children growing well into adolescence and even adulthood before finally confirming the disorder. Recently, graph-based learning techniques have demonstrated impressive results on resting-state functional magnetic resonance imaging (rs-fMRI) data from the Autism Brain Imaging Data Exchange (ABIDE). We introduce IMAGIN, a multI-granular, Multi-Atlas spatio-temporal attention Graph Isomorphism Network, which, which we use to learn graph representations of dynamic functional brain connectivity (chronnectome), as opposed to static connectivity (connectome). The experimental results demonstrate that IMAGIN achieves a 5-fold cross validation accuracy of 79.25%, which surpasses the current state-of-the-art by 1.5%. In addition, analysis of the spatial and temporal attention scores provide further validation for the neural basis of autism.

The epiDAMIK workshop serves as a platform for advancing the utilization of data-driven methods in the fields of epidemiology and public health research. These fields have seen relatively limited exploration of data-driven approaches compared to other disciplines. Therefore, our primary objective is to foster the growth and recognition of the emerging discipline of data-driven and computational epidemiology, providing a valuable avenue for sharing state-of-the-art research and ongoing projects. The workshop also seeks to showcase results that are not typically presented at major computing conferences, including valuable insights gained from practical experiences. Our target audience encompasses researchers in AI, machine learning, and data science from both academia and industry, who have a keen interest in applying their work to epidemiological and public health contexts. Additionally, we welcome practitioners from mathematical epidemiology and public health, as their expertise and contributions greatly enrich the discussions. Homepage: https://epidamik.github.io/

The increasing penetration of solar PhotoVoltaic (PV) panels in residential markets is leading to increasing solar generation hidden behind metering instruments of utility companies. Current metering infrastructure only measures the net load (sum of consumption and solar generation signals) from customers. However, it is desirable to observe solar generation separate from load consumption for grid optimizations. To enable that, we propose an unsupervised Behind-the-Meter (BTM) disaggregation model that utilizes a novel Consumer Mixture Model (CMM) for the modelling of consumption load in the disaggregation model. CMM uses consumption patterns of neighboring customers without PVs installed as features for modelling. We evaluate our model on an Australia dataset and use a load regression model and a state-of-the-art disaggregation model as baselines. We show that our model outperforms the baselines – the Mean Average Error of disaggregation results of our model was 28.37% lower than the state-of-the-art model. Additionally, we show that our model is agnostic to aggregation levels. This enables the utilities to focus on specific grid portions as needed.

Infectious disease forecasting for ongoing epidemics has been traditionally performed, communicated, and evaluated as numerical targets – 1, 2, 3, and 4 week ahead cases, deaths, and hospitalizations. While there is great value in predicting these numerical targets to assess the burden of the disease, we argue that there is also value in communicating the future trend (description of the shape) of the epidemic – for instance, if the cases will remain flat o r a s urge i s expected. To ensure what is being communicated is useful we need to be able to evaluate how well the predicted shape matches with the ground truth shape. Instead of treating this as a classification problem ( one out of n shapes), we define a transformation of the numerical forecasts into a "shapelet"-space representation. In this representation, each dimension corresponds to the similarity of the shape with one of the shapes of interest (a shapelet). We prove that this representation satisfies the property that two shapes that one would consider similar are mapped close to each other, and vice versa. We demonstrate that our representation is able to reasonably capture the trends in COVID-19 cases and deaths time-series. With this representation, we define an evaluation measure and a measure of agreement among multiple models. We also define the shapelet-space ensemble of multiple models as the mean of their shapelet-space representations. We show that this ensemble is able to accurately predict the shape of the future trend for COVID-19 cases and trends. We also show that the agreement between models can provide a good indicator of the reliability of the forecast.

Machine learning algorithms have shown potential to improve prefetching performance by accurately predicting future memory accesses. Existing approaches are based on the modeling of text prediction, considering prefetching as a classification problem for sequence prediction. However, the vast and sparse memory address space leads to large vocabulary, which makes this modeling impractical. The number and order of outputs for multiple cache line prefetching are also fundamentally different from text prediction.

Similar to previous iterations, the epiDAMIK @ KDD workshop is a forum to promote data driven approaches in epidemiology and public health research. Even after the devastating impact of COVID-19 pandemic, data driven approaches are not as widely studied in epidemiology, as they are in other spaces. We aim to promote and raise the profile of the emerging research area of data-driven and computational epidemiology, and create a venue for presenting state-of-the-art and in-progress results-in particular, results that would otherwise be difficult to present at a major data mining conference, including lessons learnt in the 'trenches'. The current COVID-19 pandemic has only showcased the urgency and importance of this area. Our target audience consists of data mining and machine learning researchers from both academia and industry who are interested in epidemiological and public-health applications of their work, and practitioners from the areas of mathematical epidemiology and public health. Homepage: https://epidamik.github.io/.

Robotic comedians (and social robots generally) need to recognize and adapt to human responses during playful dialog. To support this ability, we determined design guidelines via a survey of 20 human comedians and developed a machine learning pipeline to support comedian-like behaviors by our robotic system. Based on comedian input, we identified that discerning laughter vs. no laughter during a joke setup and big laugh vs. so-so response vs. no laugh after a punchline were important skills for a comedian. To enable these abilities in a robotic system, we used an existing dataset of robot comedy performance audio to train classifiers for audience responses during the setup and after the punchline of jokes. Top-performing models for the above types of discernment performed similarly to human raters who completed the same classification task. Comparison of the current results to our past efforts of a similar nature reveal repeatability of top-performing approaches and generalizability of the approaches to new parts of robot comedy routines. The social intelligence supported by this work can promote the likability and acceptance of robots.

Data prefetching hides memory latency by predicting and loading necessary data into cache beforehand. Most prefetchers in the literature are efficient for specific memory address patterns thereby restricting their utility to specialized applications-they do not perform well on hybrid applications with multifarious access patterns. Therefore we propose ReSem-ble: a Reinforcement Learning (RL) based adaptive enSemble framework that enables multiple prefetchers to complement each other on hybrid applications. Our RL trained ensemble controller takes prefetch suggestions from all prefetchers as input, selects the best suggestion dynamically, and learns online toward getting higher cumulative rewards, which are collected from prefetch hits/misses. Our ensemble framework using a simple multilayer perceptron as the controller achieves on the average 85.27 % (accuracy) and 44.22 % (coverage), leading to 31.02 % IPC improvement, which outperforms state-of-the-art individual prefetchers by 8.35%-26.11 %, while also outperforming SBP, a state-of-the-art (non-RL) ensemble prefetcher by 5.69%.

Task mapping is critical for the effective utilization of high performance computing systems. Recently, heterogeneous platforms consisting of CPUs, GPUs, FPGAs, and hardware accelerators have become popular. While there have been extensive studies to optimize task mapping, existing approaches have primarily focused on homogeneous platforms and rely on heuristics like greedy algorithms and do not effectively explore the search space. In this paper, we focus on a class of task mapping problems that captures heterogeneity in the application as well as in the target platform. We consider task mapping under a generalized computational setting where heterogeneous applications consisting of interdependent tasks with platform-dependent execution and communication parameters are to be mapped onto heterogeneous resource-limited execution platforms including CPUs, GPUs, FPGAs, and accelerators. This abstracts modern scientific workflows where computations proceed in an iterative fashion. We propose Pick-Best-Pair with Running Best (PRB) - a Monte Carlo Tree Search (MCTS) based approach to identify a task-hardware mapping for an input application. We formulate the task mapping problem as an integer linear programming problem and solve it using our PRB approach that conducts a series of LP relaxations with randomized rounding by leveraging exploration of long-term cumulative reward in terms of the total completion time, instead of a local optimal solution. We evaluate our approach by varying the number of stages, number of tasks per stage, and types of tasks, as well as resources with mixed types. Experimental results show that our proposed algorithm is effective in finding efficient mapping compared with classic approaches, such as the greedy heuristic and the randomized LP rounding. PRB achieves up to 20% improvement over greedy algorithm and 15% over LP relaxation with randomized rounding.

Effective social robots should leverage humor’s unique ability to improve relationship connections and dispel stress, but current robots possess limited (if any) humorous abilities. In this paper, we aim to supplement one aspect of autonomous robots by giving robotic systems the ability to "read the room" to assess how their humorous statements are received by nearby people in real time. Using a dataset of the audio of crowd responses to a robotic comedian over multiple performances (first presented in past work), we establish human-labeled joke success ground truths and compare individual human rater accuracy against the outputs of lightweight Machine Learning (ML) approaches that are easy to deploy in real-time joke assessment. Our results indicate that all three ML approaches (naïve Bayes, support vector machines, and single-hidden-layer feedforward neural networks) performed significantly better than the baseline approach used in our past work. In particular, support vector machines and neural network approaches are comparable to a human rater in the task of assessing if a joke failed or not in certain cases. The products of this work will inform self-assessment techniques for robots and help social robotics researchers test their own assessment methods on realistic data from human crowds.

The 4th [email protected] workshop is a forum to discuss new insights into how data mining can play a bigger role in epidemiology and public health research. While the integration of data science methods into epidemiology has significant potential, it remains under studied. We aim to raise the profile of this emerging research area of data-driven and computational epidemiology, and create a venue for presenting state-of-the-art and in-progress results-in particular, results that would otherwise be difficult to present at a major data mining conference, including lessons learnt in the 'trenches'. The current COVID-19 pandemic has only showcased the urgency and importance of this area. Our target audience consists of data mining and machine learning researchers from both academia and industry who are interested in epidemiological and public-health applications of their work, and practitioners from the areas of mathematical epidemiology and public health.

State-of-the-art Graph Neural Networks (GNNs) have limited scalability with respect to the graph and model sizes. On large graphs, increasing the model depth often means exponential expansion of the scope (i.e., receptive field). Beyond just a few layers, two fundamental challenges emerge: 1. degraded expressivity due to oversmoothing, and 2. expensive computation due to neighborhood explosion. We propose a design principle to decouple the depth and scope of GNNs – to generate representation of a target entity (i.e., a node or an edge), we first extract a localized subgraph as the bounded-size scope, and then apply a GNN of arbitrary depth on top of the subgraph. A properly extracted subgraph consists of a small number of critical neighbors, while excluding irrelevant ones. The GNN, no matter how deep it is, smooths the local neighborhood into informative representation rather than oversmoothing the global graph into “white noise”. Theoretically, decoupling improves the GNN expressive power from the perspectives of graph signal processing (GCN), function approximation (GraphSAGE) and topological learning (GIN). Empirically, on seven graphs (with up to 110M nodes) and six backbone GNN architectures, our design achieves significant accuracy improvement with orders of magnitude reduction in computation and hardware cost.

Graph Neural Networks (GNNs) are proven to be powerful models to generate node embedding for downstream applications. However, due to the high computation complexity of GNN inference, it is hard to deploy GNNs for large-scale or real-time applications. In this paper, we propose to accelerate GNN inference by pruning the dimensions in each layer with negligible accuracy loss. Our pruning framework uses a novel LASSO regression formulation for GNNs to identify feature dimensions (channels) that have high influence on the output activation. We identify two inference scenarios and design pruning schemes based on their computation and memory usage for each. To further reduce the inference complexity, we effectively store and reuse hidden features of visited nodes, which significantly reduces the number of supporting nodes needed to compute the target embedding. We evaluate the proposed method with the node classification problem on five popular datasets and a real-time spam detection application. We demonstrate that the pruned GNN models greatly reduce computation and memory usage with little accuracy loss. For full inference, the proposed method achieves an average of 3.27X speedup with only 0.002 drop in F1-Micro on GPU. For batched inference, the proposed method achieves an average of 6.67X speedup with only 0.003 drop in F1-Micro on CPU. To the best of our knowledge, we are the first to accelerate large scale real-time GNN inference through channel pruning.

Spectral-domain CNNs have been shown to be more efficient than traditional spatial CNNs in terms of reducing computation complexity. However they come with a 'kernel explosion' problem that, even after compression (pruning), imposes a high memory burden and off-chip bandwidth requirement for kernel access. This creates a performance gap between the potential acceleration offered by compression and actual FPGA implementation performance, especially for low-latency CNN inference. In this paper, we develop a principled approach to overcoming this performance gap and designing a low-latency, low-bandwidth, spectral sparse CNN accelerator on FPGAs. First, we analyze the bandwidth-storage tradeoff of sparse convolutional layers and locate communication bottlenecks. We then develop a dataflow for flexibly optimizing data reuse in different layers to minimize off-chip communication. Finally, we propose a novel scheduling algorithm to optimally schedule the on-chip memory access of multiple sparse kernels and minimize read conflicts. On a state-of-the-art FPGA platform, our design reduces data transfers by 42% with DSP utilization up to 90% and achieves inference latency of 9 ms for VGG16, compared to the baseline state-of-the-art latency of 68 ms.

Q-Table based Reinforcement Learning (QRL) is a class of widely used algorithms in AI that work by successively improving the estimates of Q values -- quality of state-action pairs, stored in a table. They significantly outperform Neural Network based techniques when the state space is tractable. Fast learning for AI applications in several domains (e.g. robotics), with tractable 'mid-sized' Q-tables, still necessitates performing substantial rapid updates. State-of-the-art FPGA implementations of QRL do not scale with the increasing Q-Table state space, thus are not efficient for such applications. In this work, we develop a novel FPGA implementation of QRL, scalable to large state spaces and facilitating a large class of AI applications. Our pipelined architecture provides higher throughput while using significantly fewer on-chip resources and thereby supports a variety of action selection policies that covers Q-Learning and variations of bandit algorithms. Possible dependencies caused by consecutive Q value updates are handled, allowing the design to process one Q-sample every clock cycle. Additionally, we provide the first known FPGA implementation of the SARSA (State-Action-Reward-State-Action) algorithm. We evaluate our architecture for Q-Learning and SARSA algorithms and show that our designs achieve a high throughput of up to 180 million Q samples per second.

Writing high-performance code requires significant expertise in the programming language, compiler optimizations, and hardware knowledge. This often leads to poor productivity and portability and is inconvenient for a non-programmer domain-specialist such as a Physicist. More desirable is a high-level language where the domain-specialist simply specifies the workload in terms of high-level operations (e.g., matrix-multiply(A, B)), and the compiler identifies the best implementation fully utilizing the heterogeneous platform. For creating a compiler that supports productivity, portability, and performance simultaneously, it is crucial to predict the performance of various available implementations (variants) of the dominant operations (kernels) contained in the workload on various hardware to decide (a) which variant should be chosen for each kernel in the workload, and (b) on which hardware resource the variant should run. To enable the performance prediction, we propose lightweight augmented neural networks for arbitrary combinations of kernel-variant-hardware. A key innovation is utilizing the mathematical complexity of the kernels as a feature to achieve higher accuracy. These models are compact to reduce training time and allow fast inference during compile-time and run-time. Using models with less than 75 parameters, and only 250 training data instances, we are able to obtain accurate performance predictions, significantly outperforming traditional feed-forward neural networks on 48 kernel-variant-hardware combinations. We further demonstrate that our variant-selection approach can be used in Halide implementations to obtain up to 1.7x speedup over Halide auto-scheduler.

To improve the reliability of content shared on social media, effective strategies for mitigating the diffusion of fake news are increasingly necessary. Traditionally, to counter false belief a competing cascade approach is used. This approach assumes that the opposite belief is already known, and thus, not applicable to newly spreading fake news. Another approach is to block nodes and links of the network to impede the flow of fake news (rumor/influence blocking). However, a more active way to battle the dissemination of fake news is to propagate the corresponding real news, since people who receive the real news in tandem with the fake news are less likely to believe in fake news. Such a setting is especially useful on a messaging platform such as WhatsApp, where the news item flows as a private message and the correction of fake news and its propagation must be performed by the users within the network as they receive it. To achieve this goal, we propose network-based recruitment for active fake news correction (RecANt) to find a set of individuals of a pre-defined size to be incentivized for actively fact-checking and passing on the real news so as to reach the maximum number of nodes in the network. These individuals should be such that they are likely to receive the fake news so that they can test its credibility, and when they propagate the corresponding real news, it reaches a large number of individuals. We prove that RecANt is NP-Hard with a monotone and submodular objective, leading to a polynomial time greedy algorithm (AFC) which provides a (1 - 1/e - ε)-approximation. We further optimize the runtime of AFC by developing a fast graph-pruning heuristic (RAFC) that performs as well as AFC in checking the spread of fake news while reducing the runtime significantly. Simulations on several networks demonstrate that our approach outperforms popular social network centrality measures and state-of-the-art information diffusion algorithm.

Graph sampling is an important tool to obtain small and manageable subgraphs from large real-world graphs. Prior research has shown that Induced Edge Sampling (IES) outperforms other sampling methods in terms of the quality of subgraph obtained. Even though fast sampling is crucial for several workflows, there has been little work on parallel sampling algorithms in the past.

Accurate prediction of crime incidents can assist the police in better planning of prevention strategies and scheduling deployment. The problem is often studied as a spatio-temporal regression problem approached by dividing the area of interest into a grid of uniform cells, and performing regression on timeseries of each cell. We propose that changing the method of division of the area can significantly improve crime prediction. We demonstrate this using a heterogeneous division of the area obtained by our partitioning algorithm that takes into account the density of crime. We further show that existing measures do not provide a fair comparison of two methods that partition the area in two different ways. To address this severe drawback in crime prediction evaluation, we propose a novel measure which is based on optimal allocation of resources relying on the prediction and then checking the actual number of crimes that would have been avoided by the allocation. Essentially, our measure answers the question of which model would have assisted in preventing most number of actual crimes if allocation were to be done using the predicted crimes. We also prove that a greedy algorithm results in the optimal allocation resources, thus making our evaluation computationally lightweight. Experiments on real-world datasets demonstrate that heterogeneous division of the area results in improved crime prediction while drastically decreasing the number of models to be trained compared to uniform grid division.

To accelerate inference of Convolutional Neural Networks (CNNs), various techniques have been proposed to reduce computation redundancy. Converting convolutional layers into frequency domain significantly reduces the computation complexity of the sliding window operations in space domain. On the other hand, weight pruning techniques address the redundancy in model parameters by converting dense convolutional kernels into sparse ones. To obtain high-throughput FPGA implementation, we propose spec - the first work to prune and accelerate spectral CNNs. First, we propose a systematic pruning algorithm based on Alternative Direction Method of Multipliers (ADMM). The offline pruning iteratively sets the majority of spectral weights to zero, without using any handcrafted heuristics. Then, we design an optimized pipeline architecture on FPGA that has efficient random access into the sparse kernels and exploits various dimensions of parallelism in convolutional layers. Overall, achieves high inference throughput with extremely low computation complexity and negligible accuracy degradation. We demonstrate by pruning and implementing LeNet and VGG16 on the Xilinx Virtex platform. After pruning 75% of the spectral weights, achieves 0% accuracy loss for LeNet, and <; 1% accuracy loss for VGG16. The resulting accelerators achieve up to 24× higher throughput, compared with the state-of-the-art FPGA implementations for VGG16.

The Graph Convolutional Network (GCN) model and its variants are powerful graph embedding tools for facilitating classification and clustering on graphs. However, a major challenge is to reduce the complexity of layered GCNs and make them parallelizable and scalable on very large graphs - state-of the art techniques are unable to achieve scalability without losing accuracy and efficiency. In this paper, we propose novel parallelization techniques for graph sampling-based GCNs that achieve superior scalable performance on very large graphs without compromising accuracy. Specifically, our GCN guarantees work-efficient training and produces order of magnitude savings in computation and communication. To scale GCN training on tightly-coupled shared memory systems, we develop parallelization strategies for the key steps in training: For the graph sampling step, we exploit parallelism within and across multiple sampling instances, and devise an efficient data structure for concurrent accesses that provides theoretical guarantee of near-linear speedup with number of processing units. For the feature propagation step within the sampled graph, we improve cache utilization and reduce DRAM communication by data partitioning. We prove that our partitioning strategy is a 2-approximation for minimizing the communication time compared to the optimal strategy. We demonstrate that our parallel graph embedding outperforms state-of-the-art methods in scalability (with respect to number of processors, graph size and GCN model size), efficiency and accuracy on several large datasets. On a 40-core Xeon platform, our parallel training achieves 64× speedup (with AVX) in the sampling step and 25× speedup in the feature propagation step, compared to the serial implementation, resulting in a net speedup of 21×. Our scalable algorithm enables deeper GCN, as demonstrated by 1306× speedup on a 3-layer GCN compared to Tensorflow implementation of state-of-the-art.

Interventions to reduce violence among homeless youth are difficult to implement due to the complex nature of violence. However, a peer-based intervention approach would likely be a worthy approach as it has been shown that individuals who interact with more violent individuals are more likely to be violent, suggesting a contagious nature of violence. We propose Uncertain Voter Model to represent the complex process of diffusion of violence over a social network, that captures uncertainties in links and time over which the diffusion of violence takes place. Assuming this model, we define Violence Minimization problem where the task is to select a predefined number of individuals for intervention so that the expected number of violent individuals in the network is minimized over a given time-frame. We extend the problem to a probabilistic setting, where the success probability of converting an individual into non-violent is a function of the number of “units” of intervention performed on them. We provide algorithms for finding the optimal intervention strategies for both scenarios. We demonstrate that our algorithms perform significantly better than interventions based on popular centrality measures in terms of reducing violence.

Often in marketing, political campaigns and social media, two competing products or opinions propagate over a social network. Studying social influence in such competing cascades scenarios enables building effective strategies for maximizing the propagation of one process by targeting the most "influential" nodes in the network. The majority of prior work however, focuses on unsigned networks where individuals adopt the opinion of their neighbors with certain probability. In real life, relationships between individuals can be positive (e.g., friend of relationship) or negative (e.g. connection between "foes"). According to social theory, people tend to have similar opinions to their friends but opposite of their foes. In this work, we study the problem of competing cascades on signed networks, which has been relatively unexplored. Particularly, we study the progressive propagation of two competing cascades in a signed network under the Independent Cascade Model, and provide an approximate analytical solution to compute the probability of infection of a node at any given time. We leverage our analytical solution to the problem of competing cascades in signed networks to develop a heuristic for the influence maximization problem. Unlike prior work, we allow the seed-set to be initialized with populations of both cascades with the end goal of maximizing the spread of one cascade. We validate our approach on several large-scale real-world and synthetic networks. Our experiments demonstrate that our influence maximization heuristic significantly outperforms state-of-the-art methods, particularly when the network is dominated by distrust relationships.

Understanding how information flows in online social networks is of great importance. It is generally difficult to obtain accurate prediction results of cascades over such networks, therefore a variety of diffusion models have been proposed in the literature to simulate diffusion processes instead. We argue that such models require extensive simulation results to produce good estimates of future spreads. In this work, we take a complimentary approach. We present a generalized, analytical model of influence in social networks that captures social influence at various levels of granularity, ranging from pairwise influence, to local neighborhood, to the general population, and external events, therefore capturing the complex dynamics of human behavior. We demonstrate that our model can integrate a variety of diffusion models. Particularly, we show that commonly used diffusion models in social networks can be reduced to special cases of our model, by carefully defining their parameters. Our goal is to provide a closed-form expression to approximate the probability of infection for every node in an arbitrary, directed network at any time t. We quantitatively evaluate the approximation quality of our analytical solution as compared to numerous popular diffusion models on a real-world dataset and a series of synthetic graphs.

It is often desirable to identify the concepts that are present in a corpus. A popular way to deal with this objective is to discover clusters of words or topics, for which many algorithms exist in the literature. Yet most of these methods lack the interpretability that would enable interaction with a user not familiar with their inner workings. The paper proposes a graph-based topic extraction algorithm, which can also be viewed as a soft-clustering of words present in a given corpus. Each topic, in the form of a set of words, represents an underlying concept in the corpus. The method allows easy interpretation of the clustering process, and hence enables the scope of user involvement at various steps. For a quantitative evaluation of the topics extracted, we use them as features to get a compact representation of documents for classification tasks. We compare the classification accuracy achieved by a reduced feature set obtained with our method versus other topic extraction techniques, namely Latent Dirichlet Allocation and Non-negative Matrix Factorization. While the results from all the three algorithms are comparable, the speed and easy interpretability of our algorithm makes it more appropriate to be used interactively by lay users.

In online social systems, users with common affiliations or interests form social groups for discussing various topical issues. We study the relationships among these social groups, which manifest through users who are common members of multiple groups, and the evolution of these relationships as new users join the groups. Focusing on a certain number of the most popular groups, we model the group memberships of users as a subclass of bipartite networks, known as Alphabetic Bipartite Networks (α-BiNs), where one of the partitions contains a fixed number of nodes (the popular groups) while the other grows unboundedly with time (new users joining the groups). Specifically, we consider the evolution of the thresholded projection of the user-group bipartite network onto the set of groups, which accurately represents the inter-group relationships. We propose and solve a preferential attachment based growth model for evolution of α-BiNs, and analytically compute the degree distribution of the thresholded projection. We further investigate whether the predictions of this model can explain the projection degree distributions of user-group networks derived from several real social systems (Livejournal, Youtube and Flickr). The study also shows that the inter-group network is tightly knit, and there is an implicit semantic hierarchy within its structure, that is clearly identified by the method of thresholding. To the best of our knowledge, this is the first attempt to analytically model the dynamical relationships among groups in online social systems.