Given a stream of graph edges from a dynamic graph, how can we assign anomaly scores to edges and subgraphs in an online manner, for the purpose of detecting unusual behavior, using constant time and memory? For example, in intrusion detection, existing work seeks to detect either anomalous edges or anomalous subgraphs, but not both. In this paper, we first extend the count-min sketch data structure to a higher-order sketch. This higher-order sketch has the useful property of preserving the dense subgraph structure (dense subgraphs in the input turn into dense submatrices in the data structure). We then propose 4 online algorithms that utilize this enhanced data structure, which (a) detect both edge and graph anomalies; (b) process each edge and graph in constant memory and constant update time per newly arriving edge, and; (c) outperform state-of-the-art baselines on 4 real-world datasets. Our method is the first streaming approach that incorporates dense subgraph search to detect graph anomalies in constant memory and time.

The search and discovery process of a job-seeker towards realizing the dream opportunity can be very complex. Given the dynamic nature of job postings, churn-rate of skills, and gaps in intent matches, professionals often find it hard to discover the right opportunity. Most often, they need guidance on the right search queries to issue or next-steps in the job-seeking funnel to reach a target job-apply. In this work, we experiment with job-sessions dataset from LinkedIn, to understand and represent user's job-seeking behavior. In particular using action sequences unified from various search and discovery channels, we pre-train language models, e.g. BERT (Bidirectional Encoder Representations from Transformers) to model user's activities. We further fine-tune the BERT based contextual session embeddings towards predicting entities from target sessions, in an eXtreme Multi-Label (XML) classification setting. We hypothesize that XML fine-tuning task enables dense-representation, and predicted entities to be used in multiple downstream tasks of job-search query recommendation, job-search ranking, job recommendation retrieval, and job-notification expansion, as shown in experiments. We demonstrate significant improvements in accuracy across tasks leading to reduced time to reach a given job-apply, as well as increase in total job-applies in the system. We also share the learning from deploying these models in production. To the best of our knowledge, this is the first work to efficiently model cross-channel activities at scale using self-attention mechanisms, leading to statistically significant improvement in job-seeker experience.

Given taxi-ride counts information between departure and destination locations, how can we forecast their future demands? In general, given a data stream of events with seasonal patterns that innovate over time, how can we effectively and efficiently forecast future events? In this paper, we propose Shifting Seasonal Matrix Factorization approach, namely SSMF, that can adaptively learn multiple seasonal patterns (called regimes), as well as switching between them. Our proposed method has the following properties: (a) it accurately forecasts future events by detecting regime shifts in seasonal patterns as the data stream evolves; (b) it works in an online setting, i.e., processes each observation in constant time and memory; (c) it effectively realizes regime shifts without human intervention by using a lossless data compression scheme. We demonstrate that our algorithm outperforms state-of-the-art baseline methods by accurately forecasting upcoming events on three real-world data streams.

Machine learning models are extensively being used to make decisions that have a significant impact on human life. These models are trained over historical data that may contain information about sensitive attributes such as race, sex, religion, etc. The presence of such sensitive attributes can impact certain population subgroups unfairly. It is straightforward to remove sensitive features from the data; however, a model could pick up prejudice from latent sensitive attributes that may exist in the training data. This has led to the growing apprehension about the fairness of the employed models. In this paper, we propose a novel algorithm that can effectively identify and treat latent discriminating features. The approach is agnostic of the learning algorithm and generalizes well for classification as well as regression tasks. It can also be used as a key aid in proving that the model is free of discrimination towards regulatory compliance if the need arises. The approach helps to collect discrimination-free features that would improve the model performance while ensuring the fairness of the model. The experimental results from our evaluations on publicly available real-world datasets show a near-ideal fairness measurement in comparison to other methods.

Networking infrastructure, such as routers and firewalls, consist of a policy (i.e., where to forward which packets) and a mechanism that implements it. As the correctness of the policy is critical, it is a natural candidate for formal verification. Indeed, several verification algorithms have been developed, that detect anomalies, conflicts, and redundancies in practical firewalls and flow tables. However, theory suggests that the problem is intractable in general: the decision tree for a policy is of size O((2n)d), where n is the number of rules and d is the number of observed features used in making the decision. (In a typical firewall, n = 1000 and d = 10.) In this paper, we show why the verification of practical firewalls is not as hard as previously thought. Using a new concept, “rules in play,” we find a new, tight bound on the size of the decision tree, and suggest three other factors - narrow fields, singletons, and all-matches - that make the problem tractable in practice. We also present an algorithm to solve an open problem: pruning a policy to the minimum possible number of rules, without changing its meaning.