Subgraph counting, which involves determining the frequency of a query graph within a data graph, has numerous applications such as query optimization, fraud detection, and evaluating the expressiveness of graph neural networks. Despite its importance, there has been no systematic study on the impact of adversarial graph perturbations on subgraph counts. In this work, we examine the kSub problem, which aims to identify k edge additions that maximize the count of a query graph. We prove that kSub is intractable due to its NP-hardness, even for constant approximation. To address this, we relax the problem into a top-k selection, termed topkSub. Depending on the structure of the relaxed query graph, we distinguish two possible processing scenarios (namely, the connected and the disconnected case), and design dedicated search space pruning strategies for each scenario. Additionally, we develop sampling techniques on the pruned search space to scale topkSub for handling large graphs. In the form of a case study, we demonstrate that topkSub effectively uncovers vulnerabilities in state-of-the-art GNN models for subgraph counting, providing a significant advantage over alternative graph perturbation methods. The efficiency analysis shows that our pruning techniques achieve substantial speedups for exact processing in both connected and disconnected cases, while our sampling methods reduce estimation errors by 1-2 orders of magnitude compared to state-of-the-art samplers.

Graph pattern mining (GPM) is essential for uncovering complex patterns and relationships in graph data, with applications spanning social network analysis, bioinformatics, and recommendation systems. However, existing GPM systems face significant challenges, including high computational costs, limited scalability, and inefficiencies in handling large datasets. These systems can be categorized into two paradigms: embedding centric systems, which struggle with the exponential growth of the search space, and pattern-centric systems, which often fail to leverage the full potential of input patterns. Despite their individual strengths, a critical research gap exists in understanding the comparative limitations of these approaches and the specific bottlenecks that hinder their performance. To address these limitations, we propose the gDAG model, a novel framework that unifies the computational processes of both paradigms, enabling comprehensive performance analysis. The gDAG model serves as the foundation for our BLITZ system, which incorporates innovative optimization techniques, such as path merging and quick counting. Our experimental results demonstrate that BLITZ achieves an average speedup of 10x in mining time compared to existing methods, significantly reducing execution time. Our experimental results demonstrate that BLITZ not only improves execution time but also provides a robust framework for future research

Concurrent graph query (CGQ) processing has been used to solve a wide range of graph applications. By analyzing real-world workloads of CGQs, we observe significant repeated computations among the queries. In this work, we present KGraph, a novel graph processing memoization engine to efficiently handle CGQs on large graphs by performing memoization on graphs. However, the efficacy of memoization in optimizing CGQs on large graphs is constrained by substantial computational and memory overheads, coupled with the potential amount of sharing opportunities. Thus, we develop two novel approaches in KGraph to address the memoization overhead. First, we develop a fine-grained memoization method, which only maintains query results within their associated graph partitions. This approach not only reduces the overhead but also enhances the potential for sharing. Secondly, we selectively perform memoization on pivotal queries, those with a high likelihood of promoting substantial computation sharing among CGQs, while avoiding the excessive overhead associated with managing unnecessary memoization across a large number of queries. We comprehensively analyze KGraph's performance using five popular CGQ applications. Experimental results show that our system achieves an average speedup of 4.2× over the state-of-the-art CGQ systems.

Relational graphs encapsulate nontrivial inherent interactions among entities in heterogeneous data sources. Iden-tifying hubs in relational graphs is vital in various applications such as fraud detection, influence analysis, and protein complex discovery. However, building relational graphs induced by meta-paths on heterogeneous data entails substantial costs, thus hin-dering efficient hub discovery. In this paper, we propose a novel sketch propagation framework for approximate hub queries in induced relational graphs that avoids explicitly materializing those graphs. Our framework specifically supports hub queries that ask for all nodes whose centrality scores, based on degree or h-index, are in the top quantile with provable guarantees under the notion of ∊-separable sets. In addition, we devise pruning techniques that efficiently process personalized hub queries asking whether a given node is a hub. Extensive experiments on real-world and synthetic data confirm the efficacy and efficiency of our proposals, which achieve orders of magnitude speed-ups over exact methods while consistently attaining accuracy beyond 90%.

The influence maximization (IM) problem identifies a set$S$of$k$seed nodes from a social network$G$to maximize the expected number of nodes activated through an information diffusion process initiated by$S$. With the broad adoption of IM in sensitive societal domains, including healthcare, education, and recruitment, fairness-aware IM (FIM), which not only maximizes the influence spread but also ensures its proportional distribution between different groups in the population of$G$, has attracted much attention recently. However, existing FIM methods only work under the non-adaptive setting, where all seed nodes must be selected before any influence result is observed. In this paper, we investigate the problem of fairness-aware adaptive IM (FAIM), where the$k$seed nodes are selected in$B=\lceil k / r\rceil$batches of equal size$r$, so that the choice of the$b$-th batch can be made after the influence results of the previous$b-1$batches of seeds have been observed for each$b \in[B]$. We propose FAIM-RL, a new reinforcement learning framework for FAIM. Specifically, by formulating FAIM as a Markov decision process (MDP), the FAIM-RL framework leverages graph neural networks (GNNs) for influence- and topology-based node representations and a deep Q-network (DQN) for expected return estimation, so as to select seed nodes that can strike a balance between maximizing influence spread and ensuring group fairness in each batch. Extensive experiments on four real-world and synthetic network datasets demonstrate that FAIM-RL achieves significantly better trade-offs between influence and fairness metrics than state-of-the-art IM methods. Our code and data are publicly available at https://github.com/fzzf09/FAIM-RL.

In China, the number of riders in the on-demand delivery industry has surpassed ten million. Ensuring that these riders earn a decent income can enhance their financial security, reduce poverty, and promote social equity and stability. Due to ease of use, lower-cost maintenance and environmental friendliness, electric bicycles (e-bikes) are the primary mode of transportation for delivery riders. However, these riders frequently encounter depleted batteries due to limited capacity and prolonged charging times, necessitating inconvenient swaps or recharges during deliveries. To address this issue, we propose the e-bike Battery Swap-as-a-Service (eBaaS), an innovative battery-swapping system that leverages an intelligent AIoT network for seamless battery swapping at distributed locations across urban areas. eBaaS integrates edge-cloud collaboration, battery resource allocation, battery anomaly detection, and battery range prediction to minimize downtime and reduce unnecessary mileage. While eBaaS's potential benefits are evident, there has been a lack of robust methods to quantify its impact. Thus, we further developed the eBaaS Impact Evaluation Method (EIEM), the first comprehensive model to address this gap. EIEM analyzes data from approximately 260,000 delivery riders and 5 million riding trajectories. Findings indicate that eBaaS reduces average invalid mileage by 6 km and increases the order volume by an average of over 20% daily per e-bike rider. Meanwhile, the annual electricity savings result in a reduction of 2.74 million kilograms of carbon emissions for 260,000 riders. The eBaaS system is therefore significantly beneficial for environmental conservation and sustainable urban development.

How can we efficiently identify the densest subgraph over relational graphs? Existing dense subgraph discovery (DSD) approaches assume that a relational graph H is already derived from a heterogeneous data source and they focus on efficient discovery of the densest subgraph on the materialized H. Unfortunately, materializing relational graphs can be resource-intensive, which thus limits the practical usefulness of existing algorithms over large datasets. To mitigate this, we propose a novel Summary-bAsed deNsest Subgraph discovery (SANS) system. Our unique summary-based peeling algorithm forms the core of SANS. Following the peeling paradigm, it utilizes summaries of each node's neighborhood to efficiently estimate peeling coefficients and subgraph densities at each peeling iteration and thus avoids materializing the relational graph completely. Through extensive experiments, we demonstrate the efficacy and efficiency of SANS, reaching orders of magnitude speedups compared to the conventional baselines with materialization, while consistently achieving at least 95% accuracy compared to peeling algorithms based on materialization.

Community detection in heterogeneous information networks (HINs) poses significant challenges due to the diversity of entity types and the complexity of their interrelations. While traditional algorithms may perform adequately in some scenarios, many struggle with the high memory usage and computational demands of large-scale HINs. To address these challenges, we introduce a novel framework, SCAR, which efficiently uncovers community structures in HINs without requiring network materialization. SCAR leverages insights from meta-paths to interpret multi-relational data through compact vertex-based sketches, significantly reducing computational overhead and materialization overhead. We propose a sketch-based technique for estimating changes in modularity, improving both the precision and speed in community detection. Our extensive evaluations on diverse real-world datasets provide detailed comparative metrics, demonstrating that SCAR outperforms several state-of-the-art methods, including Gdy, Louvain, Leiden, Infomap, Walktrap, and Networkit, in execution time and memory consumption while maintaining competitive accuracy. Overall, SCAR offers a robust and scalable solution for revealing community structures in large HINs, with applications across various domains, including social networks, academic collaboration networks, and e-commerce platforms.

Detecting fraudulent activities in financial and e-commerce transaction networks is crucial. One effective method for this is Densest Subgraph Discovery (DSD). However, deploying DSD methods in production systems faces substantial scalability challenges due to the predominantly sequential nature of existing methods, which impedes their ability to handle large-scale transaction networks and results in significant detection delays. To address these challenges, we introduce Dupin, a novel parallel processing framework designed for efficient DSD processing in billion-scale graphs. Dupin is powered by a processing engine that exploits the unique properties of the peeling process, with theoretical guarantees on detection quality and efficiency. Dupin provides user-friendly APIs for flexible customization of DSD objectives and ensures robust adaptability to diverse fraud detection scenarios. Empirical evaluations indicate that Dupin consistently outperforms several existing DSD methods, achieving performance improvements of up to two orders of magnitude compared to traditional approaches. On billion-scale graphs, Dupin demonstrates the potential to enhance the prevention of fraudulent transactions by approximately 49.5 basis points and reduces density error from 30.3% to below 5.0%, as supported by our experimental results.

What is the widest community in which a person exercises a strong impact? Although extensive attention has been devoted to searching communities containing given individuals, the problem of finding their unique communities of influence has barely been examined. In this paper, we study the novel problem of Characteristic cOmmunity Discovery (COD) in attributed graphs. Our goal is to identify the largest community, taking into account the query attribute, in which the query node has a significant impact. The key challenge of the COD problem is that it requires evaluating the influence of the query node over a large number of hierarchically structured communities. We first propose a novel compressed COD evaluation approach to accelerate the influence estimation by eliminating redundant computations for overlapping communities. Then, we further devise a local hierarchical reclustering method to alleviate the skewness of hierarchical communities generated by global clustering for a specific query attribute. Extensive experiments confirm the effectiveness and efficiency of our solutions to COD: they find characteristic communities better than existing community search methods by several quality measures and achieve up to 25 x speedups against well-crafted baselines.

Efficient news exploration is crucial in real-world applications, particularly within the financial sector, where numerous control and risk assessment tasks rely on the analysis of public news reports. The current processes in this domain predominantly rely on manual efforts, often involving keyword-based searches and the compilation of extensive keyword lists. In this paper, we introduce NCEXPLORER, a framework designed with OLAP-like operations to enhance the news exploration experience. NCEXPLORER empowers users to use roll-up operations for a broader content overview and drill-down operations for detailed insights. These operations are achieved through integration with external knowledge graphs (KGs), encompassing both fact-based and ontology-based structures. This integration significantly augments exploration capabilities, offering a more comprehensive and efficient approach to unveiling the underlying structures and nuances embedded in news content. Extensive empirical studies through master-qualified evaluators on Amazon Mechanical Turk demonstrate NCEXPLORER'S superiority over existing state-of-the-art news search methodologies across an array of topic domains, using real-world news datasets.

An outstanding fact (OF) is a striking claim by which some entities stand out from their peers on some attribute. OFs serve data journalism, fact checking, and recommendation. However, one could jump to conclusions by selecting truthful OFs while intentionally or inadvertently ignoring lateral contexts and data that render them less striking. This jumping conclusion bias from unstable OFs may disorient the public, including voters and consumers, raising concerns about fairness and transparency in political and business competition. It is thus ethically imperative for several stakeholders to measure the robustness of OFs with respect to lateral contexts and data. Unfortunately, a capacity for such inspection of OFs mined from knowledge graphs (KGs) is missing. In this paper, we propose a methodology that inspects the robustness of OFs in KGs by perturbation analysis. We define (1) entity perturbation, which detects outlying contexts by perturbing context entities in the OF; and (2) data perturbation, which considers plausible data that render an OF less striking. We compute the expected strikingness scores of OFs over perturbation relevance distributions and assess an OF as robust if its measured strikingness does not deviate significantly from the expected. We devise a suite of exact and sampling algorithms for perturbation analysis on large KGs. Extensive experiments reveal that our methodology accurately and efficiently detects frail OFs generated by existing mining approaches on KGs. We also show the effectiveness of our approaches through case and user studies.

The study of uncertain graphs is crucial in diverse fields, including but not limited to protein interaction analysis, viral marketing, and network reliability. Processing queries on uncertain graphs presents formidable challenges due to the vast probabilistic space they encapsulate. While existing systems employ batch processing to address these challenges, their performance is often compromised by the suboptimal selection of parallel graph traversal methods, the excessive costs in random number generation, and additional workloads intrinsic to batch processing. In this paper, we introduce uBlade, an efficient batch-processing framework for uncertain graph queries on multi-core CPUs. uBlade utilizes the work-efficient graph traversal, achieving superior parallelism in the batch processing model. Additionally, our Quasi-Sampling technique reduces the random number generation cost by a factor of B, with O(B) denoting the batch size. We further examine the extra workload resulting from batch processing and introduce an efficient strategy to reorder possible worlds, minimizing this associated overhead. Through comprehensive evaluations, we showcase that uBlade achieves up to two orders of magnitude speedups against the state-of-the-art CPU and GPU-based solutions.

Subgraph counting is a fundamental component for many downstream applications such as graph representation learning and query optimization.Since obtaining the exact count is often intractable,there have been a plethora of approximation methods on graph sampling techniques. Nonetheless, the state-of-the-art sampling methods still require massive samples to produce accurate approximations on large data graphs.We propose gSWORD, a GPU framework that leverages the massive parallelism of GPUs to accelerate iterative sampling algorithms for subgraph counting. Despite the embarrassingly parallel nature of the samples, there are unique challenges in accelerating subgraph counting due to its irregular computation logic. To address these challenges, we introduce two GPU-centric optimizations: (1) sample inheritance, enabling threads to inherit samples from neighboring threads to avoid idling, and (2) warp streaming, effectively distributing workloads among threads through a streaming process. Moreover, we propose a CPU-GPU co-processing pipeline that overlaps the sampling and enumeration processes to mitigate the underestimation issue. Experimental results demonstrate that deploying state-of-the-art sampling algorithms on gSWORD can perform millions of samples per second. The co-processing pipeline substantially improves the estimation accuracy in the cases where existing methods encounter severe underestimations with negligible overhead.

Graph analytical queries (GAQs) are becoming increasingly important in various domains, including social networks, recommendation systems, and bioinformatics, among others.GAQs typically require iterative processing of the graph data to compute various metrics and identify patterns or anomalies. Parallel to the burgeoning demand for graph analytics, the need for Concurrent Graph Analytical Queries (CGAQs), allowing simultaneous execution of multiple graph queries, is increasing. Within social networks,CGAQs bolster real-time analytics, concurrently investigate various network properties, such as community detection, path analysis, and influence propagation. In transportation,CGAQs concurrently optimize multiple routes and manage real-time traffic data, contributing significantly to efficient supply chain strategies and traffic management. The key property ofCGAQs lies in their capacity for shared processing, exploiting the synergies between concurrent queries, which in return opens opportunities for improved system scalability and throughput. In this survey, we present a comprehensive review ofsystem-levelandalgorithm-levelefforts to supportCGAQprocessing. We introduce a novel survey framework based on three aspects: 1) What are the sharing opportunities exploited? 2) What are the scheduling techniques proposed to maximize sharing? 3) What are the optimizations employed? We also identify important gaps and promising research directions forCGAQprocessing.

Graph label propagation (LP) is a core component in many downstream applications such as fraud detection, recommendation and image segmentation. In this paper, we proposeGLP, a GPU-based framework to enable efficientLPprocessing on large-scale graphs. By investigating the data processing pipeline in a large e-commerce platform, we have identified two key challenges on integrating GPU-acceleratedLPprocessing to the pipeline: (1) programmability for evolving application logics; (2) demand for real-time performance. Motivated by these challenges, we offer a set of expressive APIs that data engineers can customize and deploy efficientLPalgorithms on GPUs with ease. To achieve better performance, we propose novel GPU-centric optimizations by leveraging the community as well as power-law properties of large graphs. Further, we significantly reduce the expensive data transfer cost between CPUs and GPUs by enablingLPprocessing on compressed graphs. Extensive experiments have confirmed the effectiveness of our proposed approaches over the state-of-the-art GPU methods. Furthermore, our proposed solution supports a real billion-scale graph workload for fraud detection and achieves 13.2× speedup to the current in-house solution running on a high-end multicore machine with compressed graphs.

This paper proposes a novel graph structure to address the problems of information spreading in a real-world, frequently updating graph, with two main contributions at hand: accurately tracing infection diffusion according to fine-grained user movements and finding vulnerable vertices under the virus immunization scenario to mitigate infection diffusion. Unlike previous work that primarily predicts the long-term epidemic trend at the census level, this study aims to intervene in the short-term at the individual level. Therefore, two downstream tasks are formulated to illustrate practicalities:EpidemicMitigating in PublicArea problem ($EMA$) andEpidemic MaximizedSpread in PublicArea problem ($ESA$), where$EMA$aims to find intervention strategies, and$ESA$is an adversarial solution against the intervention strategy to test the robustness. Comprehensive experiments are conducted using two real-world datasets with millions of public transport trips, which demonstrate the effectiveness of our approach and highlight the importance of considering the dynamic nature of close contacts in epidemic modelling.

Subgraph enumeration is important for many applications such as network motif discovery, community detection, and frequent subgraph mining. To accelerate the execution, recent works utilize graphics processing units (GPUs) to parallelize subgraph enumeration. The performances of these parallel schemes are dominated by the set intersection operations which account for up to 95% of the total processing time. (Un)surprisingly, a significant portion (as high as 99%) of these operations is actually redundant, i.e., the same set of vertices is repeatedly encountered and evaluated. Therefore, in this paper, we seek to salvage and recycle the results of such operations to avoid repeated computation. Our solution consists of two phases. In the first phase, we generate a reusable plan that determines the opportunity for reuse. The plan is based on a novel reuse discovery mechanism that can identify available results to prevent redundant computation. In the second phase, the plan is executed to produce the subgraph enumeration results. This processing is based on a newly designed reusable parallel search strategy that can efficiently maintain and retrieve the results of set intersection operations. Our implementation on GPUs shows that our approach can achieve up to 5 times speedups compared with the state-of-the-art GPU solutions.

Temporal graphs are ubiquitous data structures in many scenarios, including social networks, user-item interaction networks, etc. In this paper, we focus on predicting the exact time of future interactions between node pairs on a temporal graph. This problem can support interesting applications including time-sensitive items recommendation, congestion prediction on road networks, etc. We present the Graph Neural Point Process (GNPP) to tackle this problem. GNPP relies on the graph neural message passing and the temporal point process framework. Most previous graph neural models devised for temporal graphs either utilize the chronological order information or rely on specific point process models, ignoring the exact timestamps and complicated temporal patterns. In GNPP, we adapt a time encoding scheme to map real-valued timestamps to a high-dimensional vector space so that the temporal information can be modeled precisely. Further, GNPP considers the structural information of graphs by conducting message passing aggregation on the constructed line graph. The obtained representation defines a neural conditional intensity function that models events’ generation mechanisms for predicting interactions’ time between node pairs. We evaluate this model on several synthetic and real-world temporal graphs where it outperforms recently proposed neural point process models and graph neural models devised for temporal graphs. We further conduct ablation comparisons and visual analyses to shed some light on the learned model and understand the functionality of important components comprehensively.

With the empirical success of Graph Neural Networks (GNNs) on graph-related tasks, it is intriguing to investigate their theoretical power on these tasks. In this paper, we focus on GNNs’ theoretical power on substructure counting, a fundamental yet challenging task in many applications. Previous works have proven that the 2-dimensional Weisfeiler-Leman algorithm (2-WL) equivalent GNNs can only count limited substructures. However, the substructure counting ability of theoretically more powerful and computationally tractable GNNs remains unclear. In this paper, we study conditions for substructures to be theoretically countable by k-WL equivalent GNNs, and then focus on 3-WL equivalent ones, which are currently the most theoretically powerful instances with practical computational cost. Further, we propose an algorithm to determine the countability of substructures for 3-WL equivalent GNNs. Our results reveal that 3-WL equivalent GNNs can count considerably more substructures than 2-WL equivalent ones. However, the proportion of countable patterns and prediction performance decrease as the pattern size increases. Therefore, we propose a Layer Permutation Pooling (LPP) model for better substructure counting performance. LPP first decomposes the data graph into subgraphs. Then we propose a layer permutation scheme to represent each decomposed subgraph as a set of matrices. Finally, LPP utilizes a neural network to conduct predictions on matrices. We compare LPP with several state-of-the-art GNNs on various datasets. Experimental results show that LPP outperforms baselines by 84% on average with the RMSE metric.

In this paper, we study local clustering over labeled graphs, which extracts a subgraph with nodes having high label density matched to the query labels as well as high structure density around a seed node. Despite the progress made in the last few years, we observe two major limitations of existing methods: (I) The candidate subgraphs have to comply with strict topology-driven models and better candidates can be pruned by these topological constraints; (II) The topological constraints give rise to substantial computational overheads and existing works have to construct prohibitively large indexes for online processing. To mitigate these limitations, we explore the idea of using conductance in local clustering that ensures structure density through minimizing conductance. Conductance is a well-understood metric primarily for detecting unlabeled clusters but for labeled graphs, applying conductance directly is insufficient because the label information is not taken into consideration. To this end, we propose a novel Label-Aware Motif weighted framework (LAM) to transform the labeled graph to a weighted graph so that both the label and the structure proximity of nodes are captured. We define label-aware motifs as small high-order structures of nodes with query labels. Nodes within a label-aware motif are both closely connected and relevant to query labels, which ease the process of identifying labeled clusters. Our theoretical study shows that LAM is able to better distinguish the desired candidates under the personalized pagerank distribution from the seed node on random graphs generated by the stochastic block model. Based on such nice properties of LAM, we propose an index-free peeling algorithm to efficiently search local clusters on labeled graphs. Extensive experiments on both real-world and synthetic networks show that our proposed algorithm can achieve up to 90% relative effectiveness improvements (F1 scores), while using 10 times less memory than the SOTA algorithm.

In many route planning applications, finding constrained shortest paths (CSP) is an important and fundamental problem. CSP aims to find the shortest path between two nodes on a graph while satisfying a path constraint. Solving CSPs requires a large search space and is prohibitively slow on large graphs, even with the state-of-the-art parallel solution on GPUs. The reason lies in the lack of effective navigational information and pruning strategies in the search procedure. In this paper, we propose SPEC, a Shortest Path Enhanced approach for solving the exact CSP problem. Our design rationales of SPEC rely on the observation that the shortest path (SP) provides valuable information in the search procedure of CSP. Hence, we propose a label priority that distinguishes promising candidate paths based on SP. We further devise efficient pruning and teleporting strategies utilizing SP lengths and costs, which eliminates unfeasible paths at an early stage. Furthermore, we observe that the expansion number at each search iteration affects the overall performance significantly. Thus, we devise an adaptive controller based on reinforcement learning. We also show that SPEC works seamlessly with the parallel implementation. Extensive experimental results on 8 read-world graphs reveal that single thread SPEC achieves an order of magnitude speedup over the state-of-the-art GPU-based method. The parallel implementation boosts SPEC 3 to 5 times further.

Subgraph enumeration is important for many applications such as network motif discovery, community detection, and frequent subgraph mining. To accelerate the execution, recent works utilize graphics processing units (GPUs) to parallelize subgraph enumeration. The performances of these parallel schemes are dominated by the set intersection operations which account for up to 95 percent of the total processing time. (Un)surprisingly, a significant portion (as high as 99 percent) of these operations is actually redundant, i.e., the same set of vertices is repeatedly encountered and evaluated. Therefore, in this article, we seek to salvage and recycle the results of such operations to avoid repeated computation. Our solution consists of two phases. In the first phase, we generate a reusable plan that determines the opportunity for reuse. The plan is based on a novel reuse discovery mechanism that can identify available results to prevent redundant computation. In the second phase, the plan is executed to produce the subgraph enumeration results. This processing is based on a newly designed reusable parallel search strategy that can efficiently maintain and retrieve the results of set intersection operations. Our implementation on GPUs shows that our approach can achieve up to 5 times speedups compared with the state-of-the-art GPU solutions.

How can we assess a network's ability to maintain its functionality under attacks?Network robustnesshas been studied extensively in the case of deterministic networks. However, applications such as online information diffusion and the behavior of networked public raise a question of robustness inprobabilisticnetworks. We propose three novel robustness measures for networks hosting a diffusion under the Independent Cascade or Linear Threshold model, susceptible to attacks by an adversarial attacker who disables nodes. The outcome of such a process depends on the selection of its initiators, or seeds, by theseeder, as well as on two factors outside the seeder's discretion: the attacker's strategy and the probabilistic diffusion outcome. We consider three levels of seeder awareness regarding these twouncontrolledfactors, and evaluate the network's viability aggregated over all possible extents of an attack. We introduce novel algorithms from building blocks found in previous works to evaluate the proposed measures. A thorough experimental study with synthetic and real, scale-free and homogeneous networks establishes that these algorithms are effective and efficient, while the proposed measures highlight differences among networks in terms of robustness and the surprise they furnish when attacked. Last, we devise a new measure of diffusion entropy, and devise ways to enhance the robustness of probabilistic networks.

In this demo, we present an online multi-modal community query engine (MQE) on Alibaba's billion-scale heterogeneous network. MQE has two distinct features in comparison with existing community query engines. Firstly, MQE supports multimodal community search on heterogeneous graphs with keyword and image queries. Secondly, to facilitate community understanding in real business scenarios, MQE generates natural language descriptions for the retrieved community in combination with other useful demographic information. The distinct features of MQE benefit many downstream applications in Alibaba's e-commerce platform like recommendation. Our experiments confirm the effectiveness and efficiency of MQE on graphs with billions of edges.

Selecting a small set of representatives from a large database is important in many applications such as multi-criteria decision making, web search, and recommendation. The k-regret minimizing set (k-RMS) problem was recently proposed for representative tuple discovery. Specifically, for a large database P of tuples with multiple numerical attributes, the k-RMS problem returns a size-r subset Q of P such that, for any possible ranking function, the score of the top-ranked tuple in Q is not much worse than the score of the kth-ranked tuple in P. Although the k-RMS problem has been extensively studied in the literature, existing methods are designed for the static setting and cannot maintain the result efficiently when the database is updated. To address this issue, we propose the first fully-dynamic algorithm for the k-RMS problem that can efficiently provide the up-to-date result w.r.t. any tuple insertion and deletion in the database with a provable guarantee. Experimental results on several real-world and synthetic datasets demonstrate that our algorithm runs up to four orders of magnitude faster than existing k-RMS algorithms while providing results of nearly equal quality.

In this paper, we study the problem of efficient motif-based graph partitioning (MGP). We observe that existing methods require to enumerate all motif instances to compute the exact edge weights for partitioning. However, the enumeration is prohibitively expensive against large graphs. We thus propose a sampling-based MGP (SMGP) framework that employs an unbiased sampling mechanism to efficiently estimate the edge weights while trying to preserve the partitioning quality. To further improve the effectiveness, we propose a novel adaptive sampling framework called SMGP+. SMGP+ iteratively partitions the input graph based on up-to-date estimated edge weights, and adaptively adjusts the sampling distribution so that edges that are more likely to affect the partitioning outcome will be prioritized for weight estimation. To our best knowledge, this is the first attempt to solve the MGP problem without employing exact edge weight computations, which gives hope for existing MGP methods to perform on complicated motifs in a scalable yet effective manner. Extensive experiments on seven real-world datasets have validated that our framework delivers competitive partitioning quality compared to existing workflows based on exact edge weights, while achieving orders of magnitude speedup.

The hash table is a fundamental structure that has been implemented on graphics processing units (GPUs) to accelerate a wide range of analytics workloads. Most existing works have focused on static scenarios and occupy large GPU memory to maximize the insertion efficiency. In many cases, data stored in hash tables get updated dynamically, and existing approaches use unnecessarily large memory resources. One naïve solution is to rebuild a hash table (known as rehashing) whenever it is either filled or mostly empty. However, this approach renders significant overheads for rehashing. In this paper, we propose a novel dynamic cuckoo hash table technique on GPUs, known as DyCuckoo. We devise a resizing strategy for dynamic scenarios without rehashing the entire table that ensures a guaranteed filled factor. The strategy trades search performance with resizing efficiency, and this tradeoff can be configured by users. To further improve efficiency, we propose a 2-in-d cuckoo hashing scheme that ensures a maximum of two lookups for find and delete operations, while retaining similar performance for insertions as a general cuckoo hash. Extensive experiments have validated the proposed design's effectiveness over several state-of-the-art hash table implementations on GPUs. DyCuckoo achieves superior efficiency while enables fine-grained memory control, which is not available in existing GPU hash table approaches.

News search tools help end users to identify relevant news stories. However, existing search approaches often carry out in a "black-box" process. There is little intuition that helps users understand how the results are related to the query. In this paper, we propose a novel news search framework, called NEWSLINK, to empower intuitive news search by using relationship paths discovered from open Knowledge Graphs (KGs). Specifically, NEWSLINK embeds both a query and news documents to subgraphs, called subgraph embeddings, in the KG. Their embeddings' overlap induces relationship paths between the involving entities. Two major advantages are obtained by incorporating subgraph embeddings into search. First, they enrich the search context, leading to robust results. Second, the relationship paths linking entities inter and intra news documents can help users better understand and digest the results for the given query. Through both human and automatic evaluations, we verify that NEWSLINK can help users understand the result-to-query relatedness, while its search quality is robust and outperforms many established search approaches, including Apache Lucene and a KG-powered query expansion approach, as well as popular deep learning models, Sentence-BERT (SBERT) and DOC2VEC.

Link prediction is a fundamental task for graph analysis and the topic has been studied extensively for static or dynamic graphs. Essentially, the link prediction is formulated as a binary classification problem about two nodes. However, for temporal graphs, links (or interactions) among node sets appear in sequential orders. And the orders may lead to interesting applications. While a binary link prediction formulation fails to handle such an order-sensitive case. In this paper, we focus on such an interaction order prediction problem among a given node set on temporal graphs. For the technical aspect, we develop a graph neural network model named Temporal ATtention network (TAT), which utilizes the fine-grained time information on temporal graphs by encoding continuous real-valued timestamps as vectors. For each transformation layer of the model, we devise an attention mechanism to aggregate neighborhoods' information based on their representations and time encodings attached to their specific edges. We also propose a novel training scheme to address the permutation-sensitive property of the problem. Experiments on several real-world temporal graphs reveal that TAT outperforms some state-of-the-art graph neural networks by 55% on average under the AUC metric.

An Outstanding Fact (OF) is an attribute that makes a target entity stand out from its peers. The mining of OFs has important applications, especially in Computational Journalism, such as news promotion, fact-checking, and news story finding. However, existing approaches to OF mining: (i) disregard the context in which the target entity appears, hence may report facts irrelevant to that context; and (ii) require relational data, which are often unavailable or incomplete in many application domains. In this paper, we introduce the novel problem of mining Context-aware Outstanding Facts (COFs) for a target entity under a given context specified by a context entity. We propose FMiner, a context-aware mining framework that leverages knowledge graphs (KGs) for COF mining. FMiner generates COFs in two steps. First, it discovers top-k relevant relationships between the target and the context entity from a KG. We propose novel optimizations and pruning techniques to expedite this operation, as this process is very expensive on large KGs due to its exponential complexity. Second, for each derived relationship, we find the attributes of the target entity that distinguish it from peer entities that have the same relationship with the context entity, yielding the top-l COFs. As such, the mining process is modeled as a top-(k,l) search problem. Context-awareness is ensured by relying on the relevant relationships with the context entity to derive peer entities for COF extraction. Consequently, FMiner can effectively navigate the search to obtain context-aware OFs by incorporating a context entity. We conduct extensive experiments, including a user study, to validate the efficiency and the effectiveness of FMiner.

Coresets are succinct summaries of large datasets such that, for a given problem, the solution obtained from a coreset is provably competitive with the solution obtained from the full dataset. As such, coreset-based data summarization techniques have been successfully applied to various problems, e.g., geometric optimization, clustering, and approximate query processing, for scaling them up to massive data. In this paper, we study coresets for the maxima representation of multidimensional data: Given a set P of points in $ \mathbbR ^d $, where d is a small constant, and an error parameter $ \varepsilon \in (0,1) $, a subset $ Q \subseteq P $ is an $ \varepsilon $-coreset for the maxima representation of P iff the maximum of Q is an $ \varepsilon $-approximation of the maximum of P for any vector $ u \in \mathbbR ^d $, where the maximum is taken over the inner products between the set of points (P or Q) and u. We define a novel minimum $\varepsilon$-coreset problem that asks for an $\varepsilon$-coreset of the smallest size for the maxima representation of a point set. For the two-dimensional case, we develop an optimal polynomial-time algorithm for the minimum $ \varepsilon $-coreset problem by transforming it into the shortest-cycle problem in a directed graph. Then, we prove that this problem is NP-hard in three or higher dimensions and present polynomial-time approximation algorithms in an arbitrary fixed dimension. Finally, we provide extensive experimental results on both real and synthetic datasets to demonstrate the superior performance of our proposed algorithms.

GPU's massive computing power offers unprecedented opportunities to enable large graph analysis. Existing studies proposed various preprocessing approaches that convert the input graphs into dedicated structures for GPU-based optimizations. However, these dedicated approaches incur significant preprocessing costs as well as weak programmability to build general graph applications. In this paper, we introduce SAGE, a self-adaptive graph traversal on GPUs, which is free from preprocessing and operates on ubiquitous graph representations directly. We propose Tiled Partitioning and Resident Tile Stealing to fully exploit the computing power of GPUs in a runtime and self-adaptive manner. We also propose Sampling-based Reordering to further optimize the memory efficiency of SAGE through a lightweight and effective node reordering technique on the fly. Extensive experiments demonstrate that SAGE can achieve superior graph traversal performance over existing approaches under different architectural scenarios, i.e., single-GPU, out-of-core, and multi-GPU.

As large graph processing emerges, we observe a costly fork-processing pattern (FPP) that is common in many graph algorithms. The unique feature of the FPP is that it launches many independent queries from different source vertices on the same graph. For example, an algorithm in analyzing the network community profile can execute Personalized PageRanks that start from tens of thousands of source vertices at the same time. We study the efficiency of handling FPPs in state-of-the-art graph processing systems on multi-core architectures, including Ligra, Gemini, and GraphIt. We find that those systems suffer from severe cache miss penalty because of the irregular and uncoordinated memory accesses in processing FPPs. In this paper, we propose ForkGraph, a cache-efficient FPP processing system on multi-core architectures. In order to improve the cache reuse, we divide the graph into partitions each sized of LLC (last-level cache) capacity, and the queries in an FPP are buffered and executed on the partition basis. We further develop efficient intra- and inter-partition execution strategies for efficiency. For intra-partition processing, since the graph partition fits into LLC, we propose to execute each graph query with efficient sequential algorithms (in contrast with parallel algorithms in existing parallel graph processing systems) and present an atomic-free query processing method by consolidating contending operations to cache-resident graph partition. For inter-partition processing, we propose two designs, yielding and priority-based scheduling, to reduce redundant work in processing. Besides, we theoretically prove that ForkGraph performs the same amount of work, to within a constant factor, as the fastest known sequential algorithms in FPP queries processing, which is work efficient. Our evaluations on real-world graphs show that ForkGraph significantly outperforms state-of-the-art graph processing systems (including Ligra, Gemini, and GraphIt) with two orders of magnitude speedups.

Fraud detection is a pressing challenge for most financial and commercial platforms. In this paper, we study the processing pipeline of fraud detection in a large e-commerce platform of TaoBao. Graph label propagation (LP) is a core component in this pipeline to detect suspicious clusters from the user-interaction graph.Furthermore, the run-time of the LP component occupies 75% overhead of TaoBao's automated detection pipeline. To enable real-time fraud detection, we propose a GPU-based framework, called GLP, to support large-scale LP workloads in enterprises.We have identified two key challenges when integrating GPU acceleration into TaoBao's data processing pipeline: (1)programmability for evolving fraud detection logics; (2)demand for real-time performance. Motivated by these challenges, we offer a set of expressive APIs that data engineers can customize and deploy efficient LP algorithms on GPUs with ease. We propose novel GPU-centric optimizations by leveraging the community as well as power-law properties of large graphs. Extensive experiments have confirmed the effectiveness of our proposed optimizations. With a single GPU, GLP supports a real billion-scale graph workload from the fraud detection pipeline of TaoBao and achieves 8.2x speedup to the current in-house distributed solution running on high-end multicore machines.

Influence maximization has been studied extensively from the perspective of the influencer. However, the influencer typically purchases influence from a provider, for example in the form of purchased advertising. In this paper, we study the problem from the perspective of the influence provider. Specifically, we focus on influence providers who sell Out-of-Home (OOH) advertising on billboards. Given a set of requests from influencers, how should an influence provider allocate resources to minimize regret, whether due to forgone revenue from influencers whose needs were not met or due to over-provisioning of resources to meet the needs of influencers? We formalize this as the \underlineM inimizing \underlineR egret for the \underlineO OH \underlineA dvertising \underlineM arket problem (\problem). We show that \problem is both NP-hard and NP-hard to approximate within any constant factor. The regret function is neither monotone nor submodular, which renders any straightforward greedy approach ineffective. Therefore, we propose a randomized local search framework with two neighborhood search strategies, and prove that one of them ensures an approximation factor to a dual problem of \problem. Experiments on real-world user movement and billboard datasets in New York City and Singapore show that on average our methods outperform the baselines in effectiveness by five times.

Influence diffusion estimation is a crucial problem in social network analysis. Most prior works mainly focus on predicting the total influence spread, i.e., the expected number of influenced nodes given an initial set of active nodes (aka. seeds). However, accurate estimation of susceptibility, i.e., the probability of being influenced for each individual, is more appealing and valuable in real-world applications. Previous methods generally adopt Monte Carlo simulation or heuristic rules to estimate the influence, resulting in high computational cost or unsatisfactory estimation error when these methods are used to estimate susceptibility. In this work, we propose to leverage graph neural networks (GNNs) for predicting susceptibility. As GNNs aggregate multi-hop neighbor information and could generate over-smoothed representations, the prediction quality for susceptibility is undesirable. To address the shortcomings of GNNs for susceptibility estimation, we propose a novel DeepIS model with a two-step approach: (1) a coarse-grained step where we estimate each node's susceptibility coarsely; (2) a fine-grained step where we aggregate neighbors' coarse-grained susceptibility estimations to compute the fine-grained estimate for each node. The two modules are trained in an end-to-end manner. We conduct extensive experiments and show that on average DeepIS achieves five times smaller estimation error than state-of-the-art GNN approaches and two magnitudes faster than Monte Carlo simulation.

As random walk is a powerful tool in many graph processing, mining and learning applications, this paper proposes an efficient in-memory random walk engine named ThunderRW. Compared with existing parallel systems on improving the performance of a single graph operation, ThunderRW supports massive parallel random walks. The core design of ThunderRW is motivated by our profiling results: common RW algorithms have as high as 73.1% CPU pipeline slots stalled due to irregular memory access, which suffers significantly more memory stalls than the conventional graph workloads such as BFS and SSSP. To improve the memory efficiency, we first design a generic step-centric programming model named Gather-Move-Update to abstract different RW algorithms. Based on the programming model, we develop the step interleaving technique to hide memory access latency by switching the executions of different random walk queries. In our experiments, we use four representative RW algorithms including PPR, DeepWalk, Node2Vec and MetaPath to demonstrate the efficiency and programming flexibility of ThunderRW. Experimental results show that ThunderRW outperforms state-of-the-art approaches by an order of magnitude, and the step interleaving technique significantly reduces the CPU pipeline stall from 73.1% to 15.0%.

A great variety of complex systems ranging from user interactions in communication networks to transactions in financial markets can be modeled as temporal graphs, which consist of a set of vertices and a series of timestamped and directed edges. Temporal motifs in temporal graphs are generalized from subgraph patterns in static graphs which take into account edge orderings and durations in addition to structures. Counting the number of occurrences of temporal motifs is a fundamental problem for temporal network analysis. However, existing methods either cannot support temporal motifs or suffer from performance issues. In this paper, we focus on approximate temporal motif counting via random sampling. We first propose a generic edge sampling (ES) algorithm for estimating the number of instances of any temporal motif. Furthermore, we devise an improved EWS algorithm that hybridizes edge sampling with wedge sampling for counting temporal motifs with 3 vertices and 3 edges. We provide comprehensive analyses of the theoretical bounds and complexities of our proposed algorithms. Finally, we conduct extensive experiments on several real-world datasets, and the results show that our ES and EWS algorithms have higher efficiency, better accuracy, and greater scalability than the state-of-the-art sampling method for temporal motif counting.

Network embedding effectively transforms complex network data into a low-dimensional vector space and has shown great performance in many real-world scenarios, such as link prediction, node classification, and similarity search. A plethora of methods have been proposed to learn node representations and achieve encouraging results. Nevertheless, little attention has been paid on the embedding technique for bipartite attributed networks, which is a typical data structure for modeling nodes from two distinct partitions.

Subgraph enumeration is important for many applications such as network motif discovery and community detection. Recent works utilize graphics processing units (GPUs) to parallelize subgraph enumeration, but they can only handle graphs that fit into the GPU memory. In this paper, we propose a new approach for GPU-accelerated subgraph enumeration that can efficiently scale to large graphs beyond the GPU memory. Our approach divides the graph into partitions, each of which fits into the GPU memory. The GPU processes one partition at a time and searches the matched subgraphs of a given pattern (i.e., instances) within the partition as in the small graph. The key challenge is on enumerating the instances across different partitions, because this search would enumerate considerably redundant subgraphs and cause the expensive data transfer cost via the PCI-e bus. Therefore, we propose a novel shared execution approach to eliminate the redundant subgraph searches and correctly generate all the instances across different partitions. The experimental evaluation shows that our approach can scale to large graphs and achieve significantly better performance than the existing single-machine solutions.

How can we assess a network’s ability to maintain its functionality under attacks? Network robustness has been studied extensively in the case of deterministic networks. However, applications such as online information diffusion and the behavior of networked public raise a question of robustness in probabilistic networks. We propose three novel robustness measures for networks hosting a diffusion under the Independent Cascade (IC) model, susceptible to node attacks. The outcome of such a process depends on the selection of its initiators, or seeds, by the seeder, as well as on two factors outside the seeder’s discretion: the attack strategy and the probabilistic diffusion outcome. We consider three levels of seeder awareness regarding these two uncontrolled factors, and evaluate the network’s viability aggregated over all possible extents of node attacks. We introduce novel algorithms from building blocks found in previous works to evaluate the proposed measures. A thorough experimental study with synthetic and real, scale-free and homogeneous networks establishes that these algorithms are effective and efficient, while the proposed measures highlight differences among networks in terms of robustness and the surprise they furnish when attacked. Last, we devise a new measure of diffusion entropy that can inform the design of probabilistically robust networks.

The recently emerging applications such as software-defined networks and autonomous vehicles require efficient and exact solutions for constrained shortest paths (CSP), which finds the shortest path in a graph while satisfying some user-defined constraints. Compared with the common shortest path problems without constraints, CSP queries have a significantly larger number of subproblems. The most widely used labeling algorithm becomes prohibitively slow and impractical. Other existing approaches tend to find approximate solutions and build costly indices on graphs for fast query processing, which are not suitable for emerging applications with the requirement of exact solutions. A natural question is whether and how we can efficiently find the exact solution for CSP. In this paper, we propose Vine , a framework that parallelizes the labeling algorithm to efficiently find the exact CSP solution using GPUs. The major challenge addressed in Vine is how to deal with a large number of subproblems that are mostly unpromising but require a significant amount of memory and computational resources. Our solution is twofold. First, we develop a two-level pruning approach to eliminate the subproblems by making good use of the GPU's hierarchical memory. Second, we propose an adaptive parallelism control model based on the observations that the degree of parallelism (DOP) is the key to performance optimization with the given amount of computational resources. Extensive experiments show that Vine achieves 18× speedup on average over the widely adopted CPU-based solution running on 40 CPU threads. Vine also has over 5× speedup compared with a GPU approach that statically controls the DOP. Compared to the state-of-the-art approximate solution with preprocessed indices, Vine provides exact results with competitive or even better performance.

In this article, we propose and study the problem of trajectory-driven influential billboard placement: given a set of billboards U (each with a location and a cost), a database of trajectories T , and a budget L , we find a set of billboards within the budget to influence the largest number of trajectories. One core challenge is to identify and reduce the overlap of the influence from different billboards to the same trajectories, while keeping the budget constraint into consideration. We show that this problem is NP-hard and present an enumeration based algorithm with (1-1/e) approximation ratio. However, the enumeration would be very costly when | U | is large. By exploiting the locality property of billboards’ influence, we propose a partition-based framework PartSel. PartSel partitions U into a set of small clusters, computes the locally influential billboards for each cluster, and merges them to generate the global solution. Since the local solutions can be obtained much more efficiently than the global one, PartSel would reduce the computation cost greatly; meanwhile it achieves a non-trivial approximation ratio guarantee. Then we propose a LazyProbe method to further prune billboards with low marginal influence, while achieving the same approximation ratio as PartSel. Next, we propose a branch-and-bound method to eliminate unnecessary enumerations in both PartSel and LazyProbe, as well as an aggregated index to speed up the computation of marginal influence. Experiments on real datasets verify the efficiency and effectiveness of our methods.

Massive volumes of data continuously generated on social platforms have become an important information source for users. A primary method to obtain fresh and valuable information from social streams is \emph{social search}. Although there have been extensive studies on social search, existing methods only focus on the \emph{relevance} of query results but ignore the \emph{representativeness}. In this paper, we propose a novel Semantic and Influence aware $k$-Representative ($k$-SIR) query for social streams based on topic modeling. Specifically, we consider that both user queries and elements are represented as vectors in the topic space. A $k$-SIR query retrieves a set of $k$ elements with the maximum \emph{representativeness} over the sliding window at query time w.r.t. the query vector. The representativeness of an element set comprises both semantic and influence scores computed by the topic model. Subsequently, we design two approximation algorithms, namely \textsc{Multi-Topic ThresholdStream} (MTTS) and \textsc{Multi-Topic ThresholdDescend} (MTTD), to process $k$-SIR queries in real-time. Both algorithms leverage the ranked lists maintained on each topic for $k$-SIR processing with theoretical guarantees. Extensive experiments on real-world datasets demonstrate the effectiveness of $k$-SIR query compared with existing methods as well as the efficiency and scalability of our proposed algorithms for $k$-SIR processing.

An information dissemination campaign is often multifaceted, involving several facets or pieces of information disseminating from different sources. The question then arises, how should we assign such pieces to eligible sources so as to achieve the best viral dissemination results? Past research has studied the problem of Influence Maximization (IM), which is to select a set of k promoters that maximizes the expected reach of a message over a network. However, in this classical IM problem, each promoter spreads out the same unitary piece of information. In this paper, we propose the Optimal Influential Pieces Assignment (OIPA) problem, which is to assign k distinct pieces of an information campaign OIPA to k promoters, so as to achieve the highest viral adoption in a network. We express adoption by users with a logistic model, and show that approximating OIPA within any constant factor is NP-hard. Even so, we propose a branch-and-bound framework for problem with an (1-1/e) approximation ratio. We further optimize this framework with a pruning-intensive progressive upper-bound estimation approach, yielding a (1-1/e-ε) approximation ratio and significantly lower time complexity, as it relies on the power-law properties of real-world social networks to run efficiently. Our extensive experiments on several real-world datasets show that the proposed approaches consistently outperform intuitive baselines, adopted from state-of-the-art IM algorithms. Furthermore, the progressive approach demonstrates superior efficiency with an up to 24-fold speedup over the plain branch-and-bound approach.

Coresets are important tools to generate concise summaries of massive datasets for approximate analysis. A coreset is a small subset of points extracted from the original point set such that certain geometric properties are preserved with provable guarantees. This paper investigates the problem of maintaining a coreset to preserve the minimum enclosing ball (MEB) for a sliding window of points that are continuously updated in a data stream. Although the problem has been extensively studied in batch and append-only streaming settings, no efficient sliding-window solution is available yet. In this work, we first introduce an algorithm, called AOMEB, to build a coreset for MEB in an append-only stream. AOMEB improves the practical performance of the state-of-the-art algorithm while having the same approximation ratio. Furthermore, using AOMEB as a building block, we propose two novel algorithms, namely SWMEB and SWMEB+, to maintain coresets for MEB over the sliding window with constant approximation ratios. The proposed algorithms also support coresets for MEB in a reproducing kernel Hilbert space (RKHS). Finally, extensive experiments on real-world and synthetic datasets demonstrate that SWMEB and SWMEB+ achieve speedups of up to four orders of magnitude over the state-of-the-art batch algorithm while providing coresets for MEB with rather small errors compared to the optimal ones.

In this paper we propose and study the problem of optimizing the influence of outdoor advertising (ad) when impression counts are taken into consideration. Given a database U of billboards, each of which has a location and a non-uniform cost, a trajectory database T and a budget B, it aims to find a set of billboards that has the maximum influence under the budget. In line with the advertising consumer behavior studies, we adopt the logistic function to take into account the impression counts of an ad (placed at different billboards) to a user trajectory when defining the influence measurement. However, this poses two challenges: (1) our problem is NP-hard to approximate within a factor of O(|T|1-ε) for any ε>0 in polynomial time; (2) the influence measurement is non-submodular, which means a straightforward greedy approach is not applicable. Therefore, we propose a tangent line based algorithm to compute a submodular function to estimate the upper bound of influence. Henceforth, we introduce a branch-and-bound framework with a θ-termination condition, achieving θ2/(1 - 1/e) approximation ratio. However, this framework is time-consuming when |U| is huge. Thus, we further optimize it with a progressive pruning upper bound estimation approach which achieves θ2/(1 - 1/e - ε) approximation ratio and significantly decreases the running-time. We conduct the experiments on real-world billboard and trajectory datasets, and show that the proposed approaches outperform the baselines by 95% in effectiveness. Moreover, the optimized approach is around two orders of magnitude faster than the original framework.

Graph processing on GPUs received much attention in the industry and the academia recently, as the hardware accelerator offers attractive potential for performance boost. However, the high-bandwidth device memory on GPUs has limited capacity that constrains the size of the graph to be loaded on chip. In this paper, we introduce GPU-based graph traversal on compressed graphs, so as to enable the processing of graphs having a larger size than the device memory. Designed towards GPU's SIMT architecture, we propose two novel parallel scheduling strategies Two-Phase Traversal and Task-Stealing to handle thread divergence and workload imbalance issues when decoding the compressed graph. We further optimize our solution against power-law graphs by proposing Warp-centric Decoding and Residual Segmentation to facilitate parallelism on processing skewed out-degree distribution. Extensive experiments show that with 2x-18x compression rate, our proposed GPU-based graph traversal on compressed graphs (GCGT) achieves competitive efficiency compared with the state-of-the-art graph traversal approaches on non-compressed graphs.

E-commerce taxonomy plays an essential role in online retail business. Existing taxonomy of e-commerce platforms organizes items into an ontology structure. However, the ontology-driven approach is subject to costly manual maintenance and often does not capture user's search intention, particularly when user searches by her personalized needs rather than a universal definition of the items. Observing that search queries can effectively express user's intention, we present a novel large-Scale Hierarchical taxOnomy via grAph based query coaLition ( SHOAL ) to bridge the gap between item taxonomy and user search intention. SHOAL organizes hundreds of millions of items into a hierarchical topic structure . Each topic that consists of a cluster of items denotes a conceptual shopping scenario, and is tagged with easy-to-interpret descriptions extracted from search queries. Furthermore, SHOAL establishes correlation between categories of ontology-driven taxonomy, and offers opportunities for explainable recommendation. The feedback from domain experts shows that SHOAL achieves a precision of 98% in terms of placing items into the right topics, and the result of an online A/B test demonstrates that SHOAL boosts the Click Through Rate (CTR) by 5%. SHOAL has been deployed in Alibaba and supports millions of searches for online shopping per day.

In this paper, we demonstrate an Intelligent Trajectory-driven outdoor Advertising deployment Assistant (ITAA), which assists users to find an optimal strategy for outdoor advertising (ad) deployment. The challenge is how to measure the influence to the moving trajectories of ads, and how to optimize the placement of ads among billboards that maximize the influence has been proven NP-hard. Therefore, we develop a framework based on two trajectory-driven influence models. ITAA is built upon this framework with a user-friendly UI. It serves both ad companies and their customers. We enhance the interpretability to improve the user's understanding of the influence of ads. The interactive function of ITAA is made interpretable and easy to engage.

Representative subset selection (RSS) is an important tool for users to draw insights from massive datasets. Existing literature models RSS as the submodular maximization problem to capture the “diminishing returns” property of the representativeness of selected subsets, but often only has a single constraint (e.g., cardinality), which limits its applications in many real-world problems. To capture the data recency issue and support different types of constraints, we formulate dynamic RSS in data streams as maximizing submodular functions subject to general d-knapsack constraints (SMDK) over sliding windows. We propose a KnapWindow framework (KW) for SMDK. KW utilizes the KnapStream algorithm (KS) for SMDK in append-only streams as a subroutine. It maintains a sequence of checkpoints and KS instances over the sliding window. Theoretically, KW is 1-ε/1+d-approximate for SMDK. Furthermore, we propose a KnapWindowPlus framework (KW) to improve upon KW. KW+builds an index SubKnapChk to manage the checkpoints and KS instances. SubKnapChk deletes a checkpoint whenever it can be approximated by its successors. By keeping much fewer checkpoints, KW+achieves higher efficiency than KW while still guaranteeing a 1-ε'/2+2d-approximate solution for SMDK. Finally, we evaluate the efficiency and solution quality of KW and KW+in real-world datasets. The experimental results demonstrate that KW achieves more than two orders of magnitude speedups over the batch baseline and preserves high-quality solutions for SMDK over sliding windows. KW+further runs 5-10 times faster than KW while providing solutions with equivalent or even better utilities.

The wide adoption of social networks has brought a new demand on influence analysis. This paper presents OCTOPUS that offers social network users and analysts valuable insights through topic-aware social influence analysis services. OCTOPUS has the following novel features. First, OCTOPUS provides a user-friendly interface that allows users to employ simple and easy-to-use keywords to perform influence analysis. Second, OCTOPUS provides three powerful keyword-based topic-aware influence analysis tools: keyword-based influential user discovery, personalized influential keywords suggestion, and interactive influential paths exploration. These tools can not only discover influential users, but also provide insights on how the users influence the network. Third, OCTOPUS enables online influence analysis, which provides end-users with instant results. We have implemented and deployed OCTOPUS, and demonstrate its usability and efficiency on two social networks.

Representative subset selection (RSS) is an important tool for users to draw insights from massive datasets. A common approach is to model RSS as the submodular maximization problem because the utility of extracted representatives often satisfies the "diminishing returns" property. To capture the data recency issue and support different types of constraints in real-world problems, we formulate RSS as maximizing a submodular function subject to a d-knapsack constraint (SMDK) over sliding windows. Then, we propose a novel KnapWindow framework for SMDK. Theoretically, KnapWindow is 1-ε/1+d - approximate for SMDK and achieves sublinear complexity. Finally, we evaluate the efficiency and effectiveness of KnapWindow on real-world datasets. The results show that it achieves up to 120x speedups over the batch baseline with at least 94% utility assurance.

We study the important problem of user alignment in e-commerce: to predict whether two online user identities that access an e-commerce site from different devices belong to one real-world person. As input, we have a set of user activity logs from Taobao and some labeled user identity linkages. User activity logs can be modeled using a heterogeneous interaction graph (HIG), and subsequently the user alignment task can be formulated as a semi-supervised HIG embedding problem. HIG embedding is challenging for two reasons: its heterogeneous nature and the presence of edge features. To address the challenges, we propose a novel Heterogeneous Embedding Propagation (HEP) model. The core idea is to iteratively reconstruct a node's embedding from its heterogeneous neighbors in a weighted manner, and meanwhile propagate its embedding updates from reconstruction loss and/or classification loss to its neighbors. We conduct extensive experiments on large-scale datasets from Taobao, demonstrating that HEP significantly outperforms state-of-the-art baselines often by more than 10% in F-scores.

In this paper we propose and study the problem of trajectory-driven influential billboard placement: given a set of billboards $\ur$ (each with a location and a cost), a database of trajectories $\td$ and a budget $\budget$, find a set of billboards within the budget to influence the largest number of trajectories. One core challenge is to identify and reduce the overlap of the influence from different billboards to the same trajectories, while keeping the budget constraint into consideration. We show that this problem is NP-hard and present an enumeration based algorithm with $(1-1/e)$ approximation ratio. However, the enumeration should be very costly when $|\ur|$ is large. By exploiting the locality property of billboards' influence, we propose a partition-based framework \psel. \psel partitions $\ur$ into a set of small clusters, computes the locally influential billboards for each cluster, and merges them to generate the global solution. Since the local solutions can be obtained much more efficient than the global one, \psel should reduce the computation cost greatly; meanwhile it achieves a non-trivial approximation ratio guarantee. Then we propose a \bbsel method to further prune billboards with low marginal influence, while achieving the same approximation ratio as \psel. Experiments on real datasets verify the efficiency and effectiveness of our methods.

Influence Maximization (IM), which selects a set of k users (called seed set) from a social network to maximize the expected number of influenced users (called influence spread), is a key algorithmic problem in social influence analysis. Due to its immense application potential and enormous technical challenges, IM has been extensively studied in the past decade. In this paper, we survey and synthesize a wide spectrum of existing studies on IM from an algorithmic perspective, with a special focus on the following key aspects: (1) a review of well-accepted diffusion models that capture the information diffusion process and build the foundation of the IM problem, (2) a fine-grained taxonomy to classify existing IM algorithms based on their design objectives, (3) a rigorous theoretical comparison of existing IM algorithms, and (4) a comprehensive study on the applications of IM techniques in combining with novel context features of social networks such as topic, location, and time. Based on this analysis, we then outline the key challenges and research directions to expand the boundary of IM research.

Influence maximization (IM), which selects a set of k seed users (a.k.a., a seed set ) to maximize the influence spread over a social network, is a fundamental problem in a wide range of applications. However, most existing IM algorithms are static and location-unaware. They fail to provide high-quality seed sets efficiently when the social network evolves rapidly and IM queries are location-aware. In this article, we first define two IM queries, namely Stream Influence Maximization (SIM) and Location-aware SIM (LSIM), to track influential users over social streams. Technically, SIM adopts the sliding window model and maintains a seed set with the maximum influence value collectively over the most recent social actions. LSIM further considers social actions are associated with geo-tags and identifies a seed set that maximizes the influence value in a query region over a location-aware social stream. Then, we propose the Sparse Influential Checkpoints (SIC) framework for efficient SIM query processing. SIC maintains a sequence of influential checkpoints over the sliding window and each checkpoint maintains a partial solution for SIM in an append-only substream of social actions. Theoretically, SIC keeps a logarithmic number of checkpoints w.r.t. the size of the sliding window and always returns an approximate solution from one of the checkpoint for the SIM query at any time. Furthermore, we propose the Location-based SIC (LSIC) framework and its improved version LSIC + , both of which process LSIM queries by integrating the SIC framework with a Quadtree spatial index. LSIC can provide approximate solutions for both ad hoc and continuous LSIM queries in real time, while LSIC + further improves the solution quality of LSIC. Experimental results on real-world datasets demonstrate the effectiveness and efficiency of the proposed frameworks against the state-of-the-art IM algorithms.

Social influence has attracted significant attention owing to the prevalence of social networks (SNs). In this paper, we study a new social influence problem, called personalized social tags exploration (PITEX), to help any user in the SN explore how she influences the network. Given a target user, it finds a size-k tag set that maximizes this user's social influence. We prove the problem is NP-hard to be approximated within any constant ratio. To solve it, we introduce a sampling-based framework, which has an approximation ratio of 1-ε over 1+ε with high probabilistic guarantee. To speedup the computation, we devise more efficient sampling techniques and propose best-effort exploration to quickly prune tag sets with small influence. To further enable instant exploration, we devise a novel index structure and develop effective pruning and materialization techniques. Experimental results on real large-scale datasets validate our theoretical findings and show high performances of our proposed methods.

Personalized PageRank (PPR) is a well-known proximity measure in graphs. To meet the need for dynamic PPR maintenance, recent works have proposed a local update scheme to support incremental computation. Nevertheless, sequential execution of the scheme is still too slow for highspeed stream processing. Therefore, we are motivated to design a parallel approach for dynamic PPR computation. First, as updates always come in batches, we devise a batch processing method to reduce synchronization cost among every single update and enable more parallelism for iterative parallel execution. Our theoretical analysis shows that the parallel approach has the same asymptotic complexity as the sequential approach. Second, we devise novel optimization techniques to effectively reduce runtime overheads for parallel processes. Experimental evaluation shows that our parallel algorithm can achieve orders of magnitude speedups on GPUs and multi-core CPUs compared with the state-of-the-art sequential algorithm.

As graph analytics often involves compute-intensive operations, GPUs have been extensively used to accelerate the processing. However, in many applications such as social networks, cyber security, and fraud detection, their representative graphs evolve frequently and one has to perform a rebuild of the graph structure on GPUs to incorporate the updates. Hence, rebuilding the graphs becomes the bottleneck of processing high-speed graph streams. In this paper, we propose a GPU-based dynamic graph storage scheme to support existing graph algorithms easily. Furthermore, we propose parallel update algorithms to support efficient stream updates so that the maintained graph is immediately available for high-speed analytic processing on GPUs. Our extensive experiments with three streaming applications on large-scale real and synthetic datasets demonstrate the superior performance of our proposed approach.

Influence maximization (IM), which selects a set of k users (called seeds) to maximize the influence spread over a social network, is a fundamental problem in a wide range of applications such as viral marketing and network monitoring. Existing IM solutions fail to consider the highly dynamic nature of social influence, which results in either poor seed qualities or long processing time when the network evolves. To address this problem, we define a novel IM query named Stream Influence Maximization (SIM) on social streams. Technically, SIM adopts the sliding window model and maintains a set of k seeds with the largest influence value over the most recent social actions. Next, we propose the Influential Checkpoints (IC) framework to facilitate continuous SIM query processing. The IC framework creates a checkpoint for each window shift and ensures an ε -approximate solution. To improve its efficiency, we further devise a Sparse Influential Checkpoints (SIC) framework which selectively keeps O (log N /β checkpoints for a sliding window of size N and maintains an ε(1−β)/2-approximate solution. Experimental results on both real-world and synthetic datasets confirm the effectiveness and efficiency of our proposed frameworks against the state-of-the-art IM approaches.

Automatic discovery of newsworthy themes from sequenced data can relieve journalists from manually poring over a large amount of data in order to find interesting news. In this paper, we propose a novel$k$-Sketch query that aims to find$k$striking streaks to best summarize a subject. Our scoring function takes into account streak strikingness and streak coverage at the same time. We study the$k$-Sketch query processing in both offline and online scenarios, and propose various streak-level pruning techniques to find striking candidates. Among those candidates, we then develop approximate methods to discover the$k$most representative streaks with theoretical bounds. We conduct experiments on four real datasets, and the results demonstrate the efficiency and effectiveness of our proposed algorithms: the running time achieves up to 500 times speedup and the quality of the generated summaries is endorsed by the anonymous users from Amazon Mechanical Turk.

Many real applications in real-time news stream advertising call for efficient processing of long queries against short text. In such applications, dynamic news feeds are regarded as queries to match against an advertisement (ad) database for retrieving the k most relevant ads. The existing approaches to keyword retrieval cannot work well in this search scenario when queries are triggered at a very high frequency. To address the problem, we introduce new techniques to significantly improve search performance. First, we devise a two-level partitioning for tight upper bound estimation and a lazy evaluation scheme to delay full evaluation of unpromising candidates, which can bring three to four times performance boosting in a database with 7 million ads. Second, we propose a novel rank-aware block-oriented inverted index to further improve performance. In this index scheme, each entry in an inverted list is assigned a rank according to its importance in the ad. Then, we introduce a block-at-a-time search strategy based on the index scheme to support a much tighter upper bound estimation and a very early termination. We have conducted experiments with real datasets, and the results show that the rank-aware method can further improve performance by an order of magnitude.

Social media advertising is a multi-billion dollar market and has become the major revenue source for Facebook and Twitter. To deliver ads to potentially interested users, these social network platforms learn a prediction model for each user based on their personal interests. However, as user interests often evolve slowly, the user may end up receiving repetitive ads. In this paper, we propose a context-aware advertising framework that takes into account the relatively static personal interests as well as the dynamic news feed from friends to drive growth in the ad click-through rate. To meet the real-time requirement, we first propose an online retrieval strategy that finds k most relevant ads matching the dynamic context when a read operation is triggered. To avoid frequent retrieval when the context varies little, we propose a safe region method to quickly determine whether the top-k ads of a user are changed. Finally, we propose a hybrid model to combine the merits of both methods by analyzing the dynamism of news feed to determine an appropriate retrieval strategy. Extensive experiments conducted on multiple real social networks and ad datasets verified the efficiency and robustness of our hybrid model.

Internet users are shifting from searching on traditional media to social network platforms (SNPs) to retrieve up-to-date and valuable information. SNPs have two unique characteristics: frequent content update and small world phenomenon. However, existing works are not able to support these two features simultaneously. To address this problem, we develop a general framework to enable real time personalized top-k query. Our framework is based on a general ranking function that incorporates time freshness, social relevance and textual similarity. To ensure efficient update and query processing, there are two key challenges. The first is to design an index structure that is update-friendly while supporting instant query processing. The second is to efficiently compute the social relevance in a complex graph. To address these challenges, we first design a novel 3D cube inverted index to support efficient pruning on the three dimensions simultaneously. Then we devise a cube based threshold algorithm to retrieve the top-k results, and propose several pruning techniques to optimize the social distance computation, whose cost dominates the query processing. Furthermore, we optimize the 3D index via a hierarchical partition method to enhance our pruning on the social dimension. Extensive experimental results on two real world large datasets demonstrate the efficiency and the robustness of our proposed solution.

Advertising in social network has become a multi-billion-dollar industry. A main challenge is to identify key influencers who can effectively contribute to the dissemination of information. Although the influence maximization problem, which finds a seed set of k most influential users based on certain propagation models, has been well studied, it is not target-aware and cannot be directly applied to online advertising. In this paper, we propose a new problem, named Keyword-Based Targeted Influence Maximization (KB-TIM), to find a seed set that maximizes the expected influence over users who are relevant to a given advertisement. To solve the problem, we propose a sampling technique based on weighted reverse influence set and achieve an approximation ratio of (1 − 1/ e − ε ). To meet the instant-speed requirement, we propose two disk-based solutions that improve the query processing time by two orders of magnitude over the state-of-the-art solutions, while keeping the theoretical bound. Experiments conducted on two real social networks confirm our theoretical findings as well as the efficiency. Given an advertisement with 5 keywords, it takes only 2 seconds to find the most influential users in a social network with billions of edges.