There is increasing attention toward search indexes based on dense vector representations as they can encode latent semantic features and can be generated efficiently, thanks to the advances in representation learning. Building an index on vectors was addressed by methods like locality-sensitive hashing (LSH), Inverted File Index (IVF), and near-neighbor graphs and perfected for high performance. However, the current near-neighbor (NN) indexes cannot be directly used in a real recommendation engine where both learned dense features and the constraints-attributes are used. The existing methods are cascaded index with vector search followed by a naive matching or inverted index for filtering on attribute tokens. This filtering on post-vector search matched sets often limits the control on output size and adds latency due to repeated calls to the NN engine. We aim to make a single-stage retrieval model that can retrieve in a single pass and control the output size without compromising on latency. An NN index amenable to this should have a very similar structure to the attribute token-based inverted index. Hence, we develop an efficient constraint search engine based on the high dimensional sparse embeddings of semantic features added with attribute tokens. With this, we get an Inverted index-based Constraint Near Neighbor search-ICONN, where we retrieve search results with 100% match on query attributes and close to its semantic features. We achieve a better latency vs recall10@10 tradeoff compared to the standard NN search followed by attribute filtering.

Vanilla federated learning does not support learning in an online environment, learning a personalized model on each client, and learning in a decentralized setting. There are existing methods extending federated learning in each of the three aspects. However, some important applications on enterprise edge servers (e.g. online item recommendation at global scale) involve the three aspects at the same time. Therefore, we propose a new learning setting Decentralized Personalized Online Federated Learning that considers all the three aspects at the same time.In this new setting for learning, the first technical challenge is how to aggregate the shared model parameters from neighboring clients to obtain a personalized local model with good performance on each client. We propose to directly learn an aggregation by optimizing the performance of the local model with respect to the aggregation weights. This not only improves personalization of each local model but also helps the local model adapting to potential data shift by intelligently incorporating the right amount of information from its neighbors. The second challenge is how to select the neighbors for each client. We propose a peer selection method based on the learned aggregation weights enabling each client to select the most helpful neighbors and reduce communication cost at the same time. We verify the effectiveness and robustness of our proposed method on three real-world item recommendation datasets and one air quality prediction dataset.

There are various scenarios where very quick insights from a massive amount of data need to be extracted in a time-critical manner. These might be fresh insights or re-looking at why previous insights did not work and how to fix those. A marketing campaign is one real-world scenario where a non-programmer needs to dig such huge data in a very short period of time (a few hours) in order to hit a target revenue. In this demo paper, we will describe Electra - a system that integrates an automated data-insight discovery mechanism with a novel machine-learning (ML) driven approximate query processing (AQP) engine that can answer complex queries with a large number of predicates or conditions with high accuracy. This AQP engine uses a conditional generative model to generate a very small sample (~1000 rows) corresponding to the actual query to be answered and computes the highly accurate approximate answer from those instead of running the query against the original data. The insight discovery workflow bootstraps insights using ML algorithms based on the statistical characteristics of the data and further offers a no-code based interface to drill down for deeper insights. The queries from this interface are answered by the AQP engine that runs locally at the client-side itself to offer low latency interactions.

This paper introduces higher-order link prediction methods based on the notion of closing higher-order network motifs. The methods are fast and efficient for real-time ranking and link prediction-based applications such as online visitor stitching, web search, and online recommendation. In such applications, real-time performance is critical. The proposed methods do not require any explicit training data, nor do they derive an embedding from the graph data, or perform any explicit learning. Most existing unsupervised methods with the above desired properties are all based on closing triangles (common neighbors, Jaccard similarity, and the ilk). In this work, we develop unsupervised techniques based on the notion of closing higher-order motifs that generalize beyond closing simple triangles. Through extensive experiments, we find that these higher-order motif closures often outperform triangle-based methods, which are commonly used in practice. This result implies that one should consider other motif closures beyond simple triangles. We also find that the best motif closure depends highly on the underlying network and its structural properties. Furthermore, all methods described in this work are fast for link prediction-based applications requiring real-time performance. The experimental results indicate the importance of closing higher-order motifs for unsupervised link prediction. Finally, these new higher-order motif closures can serve as a basis for studying and developing better unsupervised real-time link prediction and ranking methods.

Online marketing platforms often store millions of website visitors' behavior as a large sparse matrix with rows as visitors and columns as behavior. These platforms allow marketers to conduct Audience Expansion, a technique to identify new audiences with similar behavior to the original target audiences. In this paper, we propose a method to achieve interactive Audience Expansion from millions of visitor data efficiently. Unlike other methods that undergo significant computations upon inputs, our approach provides interactive responses when a marketer inputs the target audiences and similarity measures. The idea is to apply data summarization technique on the large visitor matrix to obtain a small set of summaries representing the similarities in the matrix. We propose efficient algorithms to compute the data summaries on a distributed computing environment (i.e., Spark) and conduct the expansion using the summaries. Our experiment shows that our approach (1) provides 10 times more accurate and 27 times faster Audience Expansion results on real datasets and (2) achieves a 98% speed-up compared to straightforward data summarization implementations. We also present an interface to apply the algorithm for real-world scenarios.

In this article, we introduce a generalization of graphlets to heterogeneous networks called typed graphlets . Informally, typed graphlets are small typed induced subgraphs. Typed graphlets generalize graphlets to rich heterogeneous networks as they explicitly capture the higher-order typed connectivity patterns in such networks. To address this problem, we describe a general framework for counting the occurrences of such typed graphlets. The proposed algorithms leverage a number of combinatorial relationships for different typed graphlets. For each edge, we count a few typed graphlets, and with these counts along with the combinatorial relationships, we obtain the exact counts of the other typed graphlets in o (1) constant time. Notably, the worst-case time complexity of the proposed approach matches the time complexity of the best known untyped algorithm. In addition, the approach lends itself to an efficient lock-free and asynchronous parallel implementation. While there are no existing methods for typed graphlets, there has been some work that focused on computing a different and much simpler notion called colored graphlet. The experiments confirm that our proposed approach is orders of magnitude faster and more space-efficient than methods for computing the simpler notion of colored graphlet. Unlike these methods that take hours on small networks, the proposed approach takes only seconds on large networks with millions of edges. Notably, since typed graphlet is more general than colored graphlet (and untyped graphlets), the counts of various typed graphlets can be combined to obtain the counts of the much simpler notion of colored graphlets. The proposed methods give rise to new opportunities and applications for typed graphlets.

Heterogeneous networks are seemingly ubiquitous in the real world. Yet, most graph mining methods such as clustering have mostly focused on homogeneous graphs by ignoring semantic information in real-world systems. Moreover, most methods are based on first-order connectivity patterns (edges) despite that higher-order connectivity patterns are known to be important in understanding the structure and organization of such networks. In this work, we propose a framework for higher-order spectral clustering in heterogeneous networks through the notions of typed graphlets and typed-graphlet conductance. The proposed method builds clusters that preserve the connectivity of higher-order structures built up from typed graphlets. The approach generalizes previous work on higher-order spectral clustering. We theoretically prove a number of important results including a Cheeger-like inequality for typed-graphlet conductance that shows near-optimal bounds for the method. The theoretical results greatly simplify previous work while providing a unifying theoretical framework for analyzing higher-order spectral methods. Empirically, we demonstrate the effectiveness of the framework quantitatively for three important applications including clustering, compression, and link prediction.

Discrete time event sequences from web users are commonly encountered in a variety of real-world domains, from digital marketing to recommender systems. Most of the literature in the area focuses on supervised prediction tasks of the user's next action or return time. However, little attention has been paid to the challenging task of modeling user evolution and behavior in a quantitative fashion. For example, progress of the users' knowledge in an online tutorial, user exploration, or engagement. We propose methods to perform a time-varying clustering along with event predictions in a unified domain agnostic framework. Our framework can help track the evolution of the users as they interact with the platform. We evaluate our methods on three real-world datasets and show that our method performs at par with the supervised baseline on the prediction tasks while providing meaningful clusters.

The success of many graph-based machine learning tasks highly depends on an appropriate representation learned from the graph data. Most work has focused on learning node embeddings that preserve proximity as opposed to structural role-based embeddings that preserve the structural similarity among nodes. These methods fail to capture higher-order structural dependencies and connectivity patterns that are crucial for structural role-based applications such as visitor stitching from web logs. In this work, we formulate higher-order network representation learning and describe a general framework called HONE for learning such structural node embeddings from networks via the subgraph patterns (network motifs, graphlet orbits/positions) in a nodes neighborhood. A general diffusion mechanism is introduced in HONE along with a space-efficient approach that avoids explicit construction of the k-step motif-based matrices using a k-step linear operator. Furthermore, HONE is shown to be fast and efficient with a worst-case time complexity that is nearly-linear in the number of edges. The experiments demonstrate the effectiveness of HONE for a number of important tasks including link prediction and visitor stitching from large web log data.

Online visitor behaviors are often modeled as a large sparse matrix, where rows represent visitors and columns represent behavior. To discover customer segments with different hierarchies, marketers often need to cluster the data in different splits. Such analyses require the clustering algorithm to provide real-time responses on user parameter changes, which the current techniques cannot support. In this paper, we propose a real-time clustering algorithm, sparse density peaks, for large-scale sparse data. It pre-processes the input points to compute annotations and a hierarchy for cluster assignment. While the assignment is only a single scan of the points, a naive pre-processing requires measuring all pairwise distances, which incur a quadratic computation overhead and is infeasible for any moderately sized data. Thus, we propose a new approach based on MinHash and LSH that provides fast and accurate estimations. We also describe an efficient implementation on Spark that addresses data skew and memory usage. Our experiments show that our approach (1) provides a better approximation compared to a straightforward MinHash and LSH implementation in terms of accuracy on real datasets, (2) achieves a 20 × speedup in the end-to-end clustering pipeline, and (3) can maintain computations with a small memory. Finally, we present an interface to explore customer segments from millions of online visitor records in real-time.

The success of deep convolutional neural networks in the domains of computer vision and speech recognition has led researchers to investigate generalizations of the said architecture to graph-structured data. A recently-proposed method called Graph Convolutional Networks has been able to achieve state-of-the-art results in the task of node classification. However, since the proposed method relies on localized first-order approximations of spectral graph convolutions, it is unable to capture higher-order interactions between nodes in the graph. In this work, we propose a motif-based graph attention model, called Motif Convolutional Networks, which generalizes past approaches by using weighted multi-hop motif adjacency matrices to capture higher-order neighborhoods. A novel attention mechanism is used to allow each individual node to select the most relevant neighborhood to apply its filter. We evaluate our approach on graphs from different domains (social networks and bioinformatics) with results showing that it is able to outperform a set of competitive baselines on the semi-supervised node classification task. Additional results demonstrate the usefulness of attention, showing that different higher-order neighborhoods are prioritized by different kinds of nodes.

Motivated by the computational and storage challenges that dense embeddings pose, we introduce the problem of latent network summarization that aims to learn a compact, latent representation of the graph structure with dimensionality that is independent of the input graph size (\i.e., #nodes and #edges), while retaining the ability to derive node representations on the fly. We propose Multi-LENS, an inductive multi-level latent network summarization approach that leverages a set of relational operators and relational functions (compositions of operators) to capture the structure of egonets and higher-order subgraphs, respectively. The structure is stored in low-rank, size-independent structural feature matrices, which along with the relational functions comprise our latent network summary. Multi-LENS is general and naturally supports both homogeneous and heterogeneous graphs with or without directionality, weights, attributes or labels. Extensive experiments on real graphs show 3.5-34.3% improvement in AUC for link prediction, while requiring 80-2152x less output storage space than baseline embedding methods on large datasets. As application areas, we show the effectiveness of Multi-LENS in detecting anomalies and events in the Enron email communication graph and Twitter co-mention graph.