Given a social network$G=(V, E)$, the unconstrained profit maximization problem aims to identify a subset$S \subseteq V$that maximizes the net profit, defined as the expected influence spread$\Gamma (S)$of set$S$minus the associated cost$c(S)$, i.e.,$\Gamma (S) - c(S)$. However, this problem presupposes an unlimited budget, which is often impractical in real scenarios. Motivated by this, we investigate the budgeted profit maximization (BPM) problem by adding a budget constraint. Unfortunately, addressing the BPM problem with a theoretical approximation guarantee remains relatively under-explored in the literature. In response, assuming$\Gamma (S)$is known for any$S \subseteq V$, we propose an algorithm that guarantees returning a set$S^{o}$such that$\Gamma (S^{o}) - c(S^{o}) \geq (1 - \frac{1}{e}) \frac{\Gamma (S^*)}{2} - \frac{c(S^*)}{2}$, where$S^*$denotes an optimal solution for BPM. Then, we develop a practical solution, which uses the reverse reachable set (RR-set) technique for influence estimation, without assuming knowledge of$\Gamma (S)$, while still maintaining a strong approximation guarantee. Additionally, similar to existing RR-set-based solutions for influence cascade-related problems, our RR-set-based solution relies on generating a large number of random RR-sets to accurately estimate$\Gamma (S)$. However, the existing RR-set generation method suffers from high memory stall rates due to its irregular memory access patterns, leaving room for further efficiency improvement. Therefore, we propose a new RR-set generation method that utilizes batch execution and cache prefetching. When a memory access is required, instead of stalling while waiting for data, the CPU first issues an asynchronous prefetch request to load the target data into the cache, and then switches to processing the generation of other RR-sets within the same batch, effectively hiding memory access latency. This method can be seamlessly integrated into existing RR-set-based solutions to improve their efficiency. Finally, we conduct extensive experiments on real, large-scale datasets to demonstrate the effectiveness and efficiency of our proposed solutions.

A multi-view attributed graph (MVAG)$\mathcal{G}$captures the diverse relationships and properties of real-world entities through multiple graph views and attribute views. Effectively utilizing all views in$\mathcal{G}$is essential for MVAG clustering and embedding, which are important for applications like recommendation systems, anomaly detection, social network analysis, etc. Existing methods either achieve inferior result quality or incur significant computational costs to handle large-scale MVAGs. In this paper, we present a spectrum-guided Laplacian aggregation scheme with an effective objective formulation and two efficient algorithms SGLA and SGLA+, to cohesively integrate all views of$\mathcal{G}$into an MVAG Laplacian matrix, which readily enables classic graph algorithms to handle$\mathcal{G}$with superior performance in clustering and embedding tasks. We begin by conducting a theoretical analysis to design an integrated objective that consists of two components, the eigengap and connectivity objectives, aiming to link the spectral properties of the aggregated MVAG Laplacian with the underlying community and connectivity properties of$\mathcal{G}$. A constrained optimization problem is then formulated for the integration, which is computationally expensive to solve. Thus, we first develop the SGLA algorithm, which already achieves excellent performance compared with existing methods. To further enhance efficiency, we design SGLA+ to reduce the number of costly objective evaluations via sampling and approximation to quickly find an approximate optimum. Extensive experiments compare our methods against 12 baselines for clustering and 8 baselines for embedding on 8 multi-view attributed graphs, validating the superior performance of SGLA and SGLA+ in terms of result quality and efficiency. Compared with the most effective baselines, our methods are significantly faster, often by up to orders of magnitude. Our implementation is available at https://github.com/CyanideCentral/SGLA/.

Real-world trajectories are often sparse with low-sampling rates (i.e., long intervals between consecutive GPS points) and misaligned with road networks, yet many applications demand high-quality data for optimal performance. To improve data quality with sparse trajectories as input, we systematically study two related research problems: trajectory recovery on road network, which aims to infer missing points to recover high-sampling trajectories, and map matching, which aims to map GPS points to road segments to determine underlying routes. Capturing latent patterns in complex sparse trajectory data on road networks is challenging, especially with large-scale datasets. In this paper, we present efficient methods TRMMA and MMA for accurate trajectory recovery and map matching, respectively, where MMA serves as the first step of TRMMA. In MMA, we carefully formulate a classification task to map a GPS point from sparse trajectories to a road segment over a small candidate segment set, rather than the entire road network. We develop techniques in MMA to generate effective embeddings that capture the patterns of GPS data, directional information, and road segments, to accurately align sparse trajectories to routes. For trajectory recovery, TRMMA focuses on the segments in the route returned by MMA to infer missing points with position ratios on road segments, producing high-sampling trajectories efficiently by avoiding evaluation of all road segments. Specifically, in TRMMA, we design a dual-transformer encoding process to cohesively capture latent patterns in trajectories and routes, and an effective decoding technique to sequentially predict the position ratios and road segments of missing points. We conduct extensive experiments to compare TRMMA and MMA with numerous existing methods for trajectory recovery and map matching, respectively, on 4 large real-world datasets. TRMMA and MMA consistently achieve the best result quality, often by a significant margin. Moreover, TRMMA and MMA are highly efficient during training and inference, being up orders of magnitude faster than the next best competitors. The implementation is at https://github.com/derekwtian/TRMMA.

Tables are a prevalent format for structured data, yet their metadata, such as semantic types and column relationships, is often incomplete or ambiguous. Column annotation tasks, including Column Type Annotation (CTA) and Column Property Annotation (CPA), address this by leveraging table context, which are critical for data management. Existing methods typically serialize all columns in a table into pretrained language models to incorporate context, but this coarse-grained approach often degrades performance in wide tables with many irrelevant or misleading columns. To address this, we propose a novel retrieve-and-verify context selection framework for accurate column annotation, introducing two methods: REVEAL and REVEAL+. In REVEAL, we design an efficient unsupervised retrieval technique to select compact, informative column contexts by balancing semantic relevance and diversity, and develop context-aware encoding techniques with role embeddings and target-context pair training to effectively differentiate target and context columns. To further improve performance, in REVEAL+, we design a verification model that refines the selected context by directly estimating its quality for specific annotation tasks. To achieve this, we formulate a novel column context verification problem as a classification task and then develop the verification model. Moreover, in REVEAL+, we develop a top-down verification inference technique to ensure efficiency by reducing the search space for high-quality context subsets from exponential to quadratic. Extensive experiments on six benchmark datasets demonstrate that our methods consistently outperform state-of-the-art baselines.

Recent advancements in AI have enabled models to map real-world entities, such as product images, into high-dimensional vectors, making approximate nearest neighbor search (ANNS) crucial for various applications. Often, these vectors are associated with additional attributes like price, prompting the need for range-filtered ANNS where users seek similar items within specific attribute ranges. Naive solutions like pre-filtering and post-filtering are straightforward but inefficient. Specialized indexes, such as SeRF, SuperPostFiltering, and iRangeGraph, have been developed to address these queries effectively. However, these solutions do not support dynamic updates, limiting their practicality in real-world scenarios where datasets frequently change. To address these challenges, we propose DIGRA, a novel dynamic graph index for range-filtered ANNS. DIGRA supports efficient dynamic updates while maintaining a balance among query efficiency, update efficiency, indexing cost, and result quality. Our approach introduces a dynamic multi-way tree structure combined with carefully integrated ANNS indices to handle range filtered ANNS efficiently. We employ a lazy weight-based update mechanism to significantly reduce update costs and adopt optimized choice of ANNS index to lower construction and update overhead. Experimental results demonstrate that DIGRA achieves superior trade-offs, making it suitable for large-scale dynamic datasets in real-world applications.

Given a set O of objects consisting of n high-dimensional vectors, the problem of approximate nearest neighbor (ANN) search for a query vector q is crucial in many applications where objects are represented as feature vectors in high-dimensional spaces. Each object in O often has attributes like popularity or price, which influence the search. Practically, searching for the nearest neighbor to q might include a range filter specifying the desired attribute values, e.g., within a specific price range. Existing solutions for range filtered ANN search often face trade-offs among excessive storage, poor query performance, and limited support for updates. To address this challenge, we propose RangePQ, a novel indexing scheme that supports efficient range filtered ANN searches and updates, requiring only linear space. Our scheme integrates seamlessly with existing PQ-based index---a widely recognized, scalable index type for ANN searches---to enhance range-filtered ANN queries and update capabilities. Our indexing method, supporting arbitrary range filters, has a space complexity of (O(n log K)), where K is a parameter of the PQ-based index and log K scales with O(log n). To reduce the space cost, we further present a hybrid two-layer structure to reduce space usage to O(n), preserving query efficiency without additional update costs. Experimental results demonstrate that our indexing scheme significantly improves query performance while maintaining competitive update performance and space efficiency.

An attributed hypergraph comprises nodes with attributes and hyperedges that connect varying numbers of nodes. Attributed hypergraph node and hyperedge embedding (AHNEE) maps nodes and hyperedges to compact vectors for use in important tasks such as node classification, hyperedge link prediction, and hyperedge classification. Generating high-quality embeddings is challenging due to the complexity of attributed hypergraphs and the need to embed both nodes and hyperedges, especially in large-scale data. Existing solutions often fall short by focusing only on nodes or lacking native support for attributed hypergraphs, leading to inferior quality, and struggle with scalability on large attributed hypergraphs. We propose SAHE, an efficient and effective approach that unifies node and hyperedge embeddings for AHNEE computation, advancing the state of the art via comprehensive embedding formulations and algorithmic designs. First, we introduce two higher-order similarity measures, HMS-N and HMS-E, to capture similarities between node pairs and hyperedge pairs, respectively. These measures consider multi-hop connections and global topology within an extended hypergraph that incorporates attribute-based hyperedges. SAHE formulates the AHNEE objective to jointly preserve all-pair HMS-N and HMS-E similarities. Direct optimization is computationally expensive, so we analyze and unify core approximations of all-pair HMS-N and HMS-E to solve them simultaneously. To enhance efficiency, we design several non-trivial optimizations that avoid iteratively materializing large dense matrices while maintaining high-quality results. Extensive experiments on diverse attributed hypergraphs and 3 downstream tasks, compared against 11 baselines, show that SAHE consistently outperforms existing methods in embedding quality and is up to orders of magnitude faster.

Cryptocurrencies are rapidly expanding and becoming vital in digital financial markets. However, the rise in cryptocurrency-related illicit activities has led to significant losses for users. To protect the security of these platforms, it is critical to identify illicit accounts effectively. Current detection methods mainly depend on feature engineering or are inadequate to leverage the complex information within cryptocurrency transaction networks, resulting in suboptimal performance. In this paper, we present DIAM, an effective method for detecting illicit accounts in cryptocurrency transaction networks modeled by directed multi-graphs with attributed edges. DIAM first features an Edge2Seq module that captures intrinsic transaction patterns from parallel edges by considering edge attributes and their directed sequences, to generate effective node representations. Then in DIAM, we design a multigraph Discrepancy (MGD) module with a tailored message passing mechanism to capture the discrepant features between normal and illicit nodes over the multigraph topology, assisted by an attention mechanism. DIAM integrates these techniques for end-to-end training to detect illicit accounts from legitimate ones. Extensive experiments, comparing against 15 existing solutions on 4 large cryptocurrency datasets of Bitcoin and Ethereum, demonstrate that DIAM consistently outperforms others in accurately identifying illicit accounts. For example, on a Bitcoin dataset with 20 million nodes and 203 million edges, DIAM attains an F1 score of 96.55%, markedly surpassing the runner-up's score of 83.92%. The code is available at https://github.com/TommyDzh/DIAM.

Graph-level representation learning is important in a wide range of applications. Existing graph-level models are generally built on i.i.d. assumption for both training and testing graphs. However, in an open world, models can encounter out-of-distribution (OOD) testing graphs that are from different distributions unknown during training. A trustworthy model should be able to detect OOD graphs to avoid unreliable predictions, while producing accurate in-distribution (ID) predictions. To achieve this, we present SGOOD, a novel graph-level OOD detection framework. We find that substructure differences commonly exist between ID and OOD graphs, and design SGOOD with a series of techniques to encode task-agnostic substructures for effective OOD detection. Specifically, we build a super graph of substructures for every graph, and develop a two-level graph encoding pipeline that works on both original graphs and super graphs to obtain substructure-enhanced graph representations. We then devise substructure-preserving graph augmentation techniques to further capture more substructure semantics of ID graphs. Extensive experiments against 11 competitors on numerous graph datasets demonstrate the superiority of SGOOD, often surpassing existing methods by a significant margin. The code is available at https://github.com/TommyDzh/SGOOD.

Graph anomaly detection (GAD) has gained increasing attention in recent years due to its critical application in a wide range of domains, such as social networks, financial risk management, and traffic analysis. Existing GAD methods can be categorized into node and edge anomaly detection models based on the type of graph objects being detected. However, these methods typically treat node and edge anomalies as separate tasks, overlooking their associations and frequent co-occurrences in real-world graphs. As a result, they fail to leverage the complementary information provided by node and edge anomalies for mutual detection. Additionally, state-of-the-art GAD methods, such as CoLA and SL-GAD, heavily rely on negative pair sampling in contrastive learning, which incurs high computational costs, hindering their scalability to large graphs. To address these limitations, we propose a novel unified graph anomaly detection framework based on bootstrapped self-supervised learning (named BOURNE). We extract a subgraph (graph view) centered on each target node as node context and transform it into a dual hypergraph (hypergraph view) as edge context. These views are encoded using graph and hypergraph neural networks to capture the representations of nodes, edges, and their associated contexts. By swapping the context embeddings between nodes and edges and measuring the agreement in the embedding space, we enable the mutual detection of node and edge anomalies. Furthermore, BOURNE can eliminate the need for negative sampling, thereby enhancing its efficiency in handling large graphs. Extensive experiments conducted on six benchmark datasets demonstrate the superior effectiveness and efficiency of BOURNE in detecting both node and edge anomalies.

Attributed bipartite graphs (ABGs) are an expressive data model for describing the interactions between two sets of heterogeneous nodes that are associated with rich attributes, such as customer-product purchase networks and author-paper authorship graphs. Partitioning the target node set in such graphs into k disjoint clusters (referred to as k-ABGC) finds widespread use in various domains, including social network analysis, recommendation systems, information retrieval, and bioinformatics. However, the majority of existing solutions towards k-ABGC either overlook attribute information or fail to capture bipartite graph structures accurately, engendering severely compromised result quality. The severity of these issues is accentuated in real ABGs, which often encompass millions of nodes and a sheer volume of attribute data, rendering effective k-ABGC over such graphs highly challenging.

A bipartite graph contains inter-set edges between two disjoint vertex sets, and is widely used to model real-world data, such as user-item purchase records, author-article publications, and biological interactions between drugs and proteins. k-Bipartite Graph Clustering (k-BGC) is to partition the target vertex set in a bipartite graph into k disjoint clusters. The clustering quality is important to the utility of k-BGC in various applications like social network analysis, recommendation systems, text mining, and bioinformatics, to name a few. Existing approaches to k-BGC either output clustering results with compromised quality due to inadequate exploitation of high-order information between vertices, or fail to handle sizable bipartite graphs with billions of edges. Motivated by this, this paper presents two efficient k-BGC solutions, HOPE and HOPE+, which achieve state-of-the-art performance on large-scale bipartite graphs. HOPE obtains high scalability and effectiveness through a new k-BGC problem formulation based on the novel notion of high-order perspective (HOP) vectors and an efficient technique for low-rank approximation of HOP vectors. HOPE+ further elevates the k-BGC performance to another level with a judicious problem transformation and a highly efficient two-stage optimization framework. Two variants, HOPE+ (FNEM) and HOPE+ (SNEM) are designed when either the Frobenius norm or spectral norm is applied in the transformation. Extensive experiments, comparing HOPE and HOPE+ against 13 competitors on 10 real-world datasets, exhibit that our solutions, especially HOPE+, are superior to existing methods in terms of result quality, while being up to orders of magnitude faster. On the largest dataset MAG with 1.1 billion edges, HOPE+ is able to produce clusters with the highest clustering accuracy within 31 minutes, which is unmatched by any existing solution for k-BGC.

Real-world directed graphs are dynamically changing, and it is important to identify and maintain the strong connectivity information between nodes, which is useful in numerous applications. Given an input graphG, we study a new problem,minimum strongly connected subgraph collection(MSCSC), which asks for a complete collection of subgraphs, each of which contains amaximalset of nodes that are strongly connected to each other viaminimumnumber of edges inG. MSCSC is NP-hard, and its computation and maintenance are challenging, especially on large-scale dynamic graphs. Thus, we resort to approximate MSCSC with theoretical guarantees. We develop a series of approximate MSCSC methods for both static and dynamic graphs. Specifically, we first develop a static MSCSC method MSC that only needs one scan of the graphG, runs in linear timew.r.t., the number of edges, and provides rigorous approximation guarantees. Then, based on MSC, we leverage a reduced directed acyclic graph ofGto design incremental MSCSC method MSCiwith two variants to handle edge insertions efficiently. We further develop MSCdthat updates MSCSC under edge deletions by efficiently scanning only locally affected subgraphs. Moreover, to demonstrate the high utility, we conduct two use case studies to apply our MSCSC methods to boost the efficiency of dynamic strongly connected component (SCC) maintenance and dynamic SCC-based reachability index maintenance. Extensive experiments on 8 large graphs, including 3 billion-edge graphs, validate the superior efficiency of our methods.

Abstract Attributed networks containing entity-specific information in node attributes are ubiquitous in modeling social networks, e-commerce, bioinformatics, etc. Their inherent network topology ranges from simple graphs to hypergraphs with high-order interactions and multiplex graphs with separate layers. An important graph mining task is node clustering, aiming to partition the nodes of an attributed network into k disjoint clusters such that intra-cluster nodes are closely connected and share similar attributes, while inter-cluster nodes are far apart and dissimilar. It is highly challenging to capture multi-hop connections via nodes or attributes for effective clustering on multiple types of attributed networks. In this paper, we first present as an efficient approach to attributed hypergraph clustering (AHC). includes a carefully-crafted K -nearest neighbor augmentation strategy for the optimized exploitation of attribute information on hypergraphs, a joint hypergraph random walk model to devise an effective AHC objective, and an efficient solver with speedup techniques for the objective optimization. The proposed techniques are extensible to various types of attributed networks, and thus, we develop as a versatile attributed network clustering framework, capable of attributed graph clustering , attributed multiplex graph clustering , and AHC. Moreover, we devise with algorithmic designs tailored for GPU acceleration to boost efficiency. We have conducted extensive experiments to compare our methods with 19 competitors on 8 attributed hypergraphs, 16 competitors on 6 attributed graphs, and 16 competitors on 3 attributed multiplex graphs, all demonstrating the superb clustering quality and efficiency of our methods.

Heterogeneous Information Network based Recommender Systems (HIN-based RS) can model the complex interactions between different objects in RS. However, existing models assume HIN is invariable and merely use HIN as a data source for assisting recommendation. In this paper, we summarize our multi-task learning framework MTRec for recommendation over HIN. MTRec relies on the self-attention mechanism to learn the semantics of meta-paths in HIN and jointly optimizes the tasks of both recommendation and link prediction. Using a Bayesian task weight learner, MTRec is able to achieve the balance of two tasks during optimization automatically. Moreover, MTRec provides good interpretability of recommendation through a “translation” mechanism which is used to model the three-way interactions among users, items and the meta-paths connecting them. Experimental results demonstrate the effectiveness and the robustness of MTRec over state-of-the-art models.

Detecting anomalous trajectories has become an important task in many location-based applications. While many approaches have been proposed for this task, they suffer from various issues including (1) incapability of detecting anomalous subtrajectories, which are finer-grained anomalies in trajectory data, and/or (2) non-data driven, and/or (3) requirement of sufficient supervision labels which are costly to collect. In this paper, we propose a novel reinforcement learning based solution called RL4OASD, which avoids all aforementioned issues of existing approaches. RL4OASD involves two networks, one responsible for learning features of road networks and trajectories and the other responsible for detecting anomalous subtrajectories based on the learned features, and the two networks can be trained iteratively without labeled data. Extensive experiments are conducted on two real datasets, and the results show that our solution can significantly outperform the state-of-the-art methods (with 20-30% improvement) and is efficient for online detection (it takes less than 0.1ms to process each newly generated data point).

Hypergraphs are an omnipresent data structure used to represent high-order interactions among entities. Given a hypergraph H wherein nodes are associated with attributes, attributed hypergraph clustering (AHC) aims to partition the nodes in H into k disjoint clusters, such that intra-cluster nodes are closely connected and share similar attributes, while inter-cluster nodes are far apart and dissimilar. It is highly challenging to capture multi-hop connections via nodes or attributes on large attributed hypergraphs for accurate clustering. Existing AHC solutions suffer from issues of prohibitive computational costs, sub-par clustering quality, or both. In this paper, we present AHCKA, an efficient approach to AHC, which achieves state-of-the-art result quality via several algorithmic designs. Under the hood, AHCKA includes three key components: (i) a carefully-crafted K-nearest neighbor augmentation strategy for the optimized exploitation of attribute information on hypergraphs, (ii) a joint hypergraph random walk model to devise an effective optimization objective towards AHC, and (iii) a highly efficient solver with speedup techniques for the problem optimization. Extensive experiments, comparing AHCKA against 15 baselines over 8 real attributed hypergraphs, reveal that AHCKA is superior to existing competitors in terms of clustering quality, while often being up to orders of magnitude faster.

We study route planning that utilizes historical trajectories to predict a realistic route from a source to a destination on a road network at given departure time. Route planning is a fundamental task in many location-based services. It is challenging to capture latent patterns implied by complex trajectory data for accurate route planning. Recent studies mainly resort to deep learning techniques that incur immense computational costs, especially on massive data, while their effectiveness are complicated to interpret. This paper proposes DRPK, an effective and efficient route planning method that achieves state-of-the-art performance via a series of novel algorithmic designs. In brief, observing that a route planning query (RPQ) with closer source and destination is easier to be accurately predicted, we fulfill a promising idea in DRPK to first detect the key segment of an RPQ by a classification model KSD, in order to split the RPQ into shorter RPQs, and then handle the shorter RPQs by a destination-driven route planning procedure DRP. Both KSD and DRP modules rely on a directed association (DA) indicator, which captures the dependencies between road segments from historical trajectories in a surprisingly intuitive but effective way. Leveraging the DA indicator, we develop a set of well-thought-out key segment concepts that holistically consider historical trajectories and RPQs. KSD is powered by effective encoders to detect high-quality key segments, without inspecting all segments in a road network for efficiency. We conduct extensive experiments on 5 large-scale datasets. DRPK consistently achieves the highest effectiveness, often with a significant margin over existing methods, while being much faster to train. Moreover, DRPK is efficient to handle thousands of online RPQs in a second,e.g., 2768 RPQs per second on a PT dataset,i.e., 0.36 milliseconds per RPQ.

In modern online services, it is of growing importance to process web-scale graph data and high-dimensional sparse data together into embeddings for downstream tasks, such as recommendation, advertisement, prediction, and classification. There exist learning methods and systems for either high-dimensional sparse data or graphs, but not both. There is an urgent need in industry to have a system to efficiently process both types of data for higher business value, which however, is challenging. The data in Tencent contains billions of samples with sparse features in very high dimensions, and graphs are also with billions of nodes and edges. Moreover, learning models often perform expensive operations with high computational costs. It is difficult to store, manage, and retrieve massive sparse data and graph data together, since they exhibit different characteristics. We present EmbedX, an industrial distributed learning framework from Tencent, which is versatile and efficient to support embedding on both graphs and high-dimensional sparse data. EmbedX consists of distributed server layers for graph and sparse data management, and optimized parameter and graph operators, to efficiently support 4 categories of methods, including deep learning models on high-dimensional sparse data, network embedding methods, graph neural networks, and in-house developed joint learning models on both types of data. Extensive experiments on massive Tencent data and public data demonstrate the superiority of EmbedX. For instance, on a Tencent dataset with 1.3 billion nodes, 35 billion edges, and 2.8 billion samples with sparse features in 1.6 billion dimension, EmbedX performs an order of magnitude faster for training and our joint models achieve superior effectiveness. EmbedX is deployed in Tencent. A/B test on real use cases further validates the power of EmbedX. EmbedX is implemented in C++ and open-sourced at https://github.com/Tencent/embedx.

Searching spatial objects is a fundamental task in spatial services such as online maps. Traditional search methods are based on filtering conditions, burdening users to specify their requirements. This paper focuses on spatial search via examples. Particularly, the user can specify an example, which is a set of objects of interest, and the purpose is to find a list of results, each containing a set of objects with similar properties to the given example. We conducted a user study, showing that a search interface based on examples can effectively complement existing approaches. However, the existing example-based search is not scalable, hindering its applications to larger datasets. To address this challenge, we propose two new algorithms, namely HSP and LORA, to efficiently answer example-based spatial queries. HSP is an algorithm based on a hierarchical partitioning of the search space, and it achieves up to 20 times faster than the state-of-the-art algorithm. LORA further improves the efficiency, running up to 5000 times faster than the state-of-the-art algorithm. We present a systematic evaluation to demonstrate the efficacy of our algorithms.

Instant messaging client (IMC) is now an essential tool for mobile users. In the representative IMC We Chat, cybercriminals deceive frauds, causing financial loss to normal users. Through statistical analysis, we find that certain fraud interactions commonly occur among WeChat users who are not k-hop neighbors. Therefore, efficiently answering whether the distance between two vertices is not longer than k at a certain time point (i.e., k-hop reachability queries) over the dynamic social graph of WeChat becomes a crucial task for fraud feature extraction in the detection system: it can help human experts quickly identify suspicious user interactions and the query results can be further used as the input feature to the downstream machine learning based detection methods. In this paper, we illustrate Bidirectional k-hop Reachability Query Processing over a Dynamic Graph (BREAD) that is used in WeChat for extracting the k-hop reachability feature for fraud detection. BREAD adopts the idea of estimating Personalized PageRank value. It first conducts the backward search from the destination vertex to construct an intermediate vertex set. Then, it performs a certain amount of random walks from the start vertex to see whether they can hit the intermediate vertex set, and the results are returned to answer k-hop reachability queries. We further propose$\text{BREAD}++$that leverages the massive parallel processing power of GPU to achieve a considerable performance gain. Experiments on several large-scale dynamic graph benchmarks and the social graph of WeChat have demonstrated that$\text{BREAD}/\text{BREAD}++$is superior than existing index-free competitors: our methods provide not only fast but also accurate responses and they are of practical value to k-hop reachability feature extraction in the fraud detection system of WeChat. Our implementation is available at https://github.com/XMUDM/BREAD.

Given a bipartite graph G consisting of inter-set weighted edges connecting the nodes in two disjoint sets U and V, bipartite network embedding (BNE) maps each node ui in U and vj in V to compact embedding vectors that capture the hidden topological features surrounding the nodes, to facilitate downstream tasks. Effective BNE should preserve not only the direct connections between nodes but also the multi-hop relationships formed alternately by the two types of nodes in G, which can incur prohibitive overheads, especially on massive bipartite graphs with millions of nodes and billions of edges. Existing solutions are hardly scalable to massive bipartite graphs, and often produce low-quality results. This paper proposes GEBE, a generic BNE framework achieving state-of-the-art performance on massive bipartite graphs, via four main algorithmic designs. First, we present two generic measures to capture the multi-hop similarity/proximity between homogeneous/heterogeneous nodes respectively, and the measures can be instantiated with three popular probability distributions, including Poisson, Geometric, and Uniform distributions. Second, GEBE formulates a novel and unified BNE objective to preserve the two measures of all possible node pairs. Third, GEBE includes several efficiency designs to get high-quality embeddings on massive graphs. Finally, we observe that GEBE achieves the best performance when instantiating MHS and MHP using a Poisson distribution, and thus, we further develop GEBEp based on Poisson-instantiated MHS and MHP, with non-trivial efficiency optimizations. Extensive experiments, comparing 15 competitors on 10 real datasets, demonstrate that our solutions, especially GEBEp, obtain superior result utility than all competitors for top-N recommendation and link prediction, while being up to orders of magnitude faster.

Traditional recommender systems (RS) only consider homogeneous data and cannot fully model heterogeneous information of complex objects and relations. Recent advances in the study of Heterogeneous Information Network (HIN) have shed some light on how to leverage heterogeneous information in RS. However, existing HIN-based recommendation models assume HIN is invariable and merely use HIN as a data source for assisting recommendation, which limits their performance. In this paper, we propose a multi-task learning framework, called MTRec, for recommendation over HIN. MTRec relies on self-attention mechanism to learn the semantics of meta-paths in HIN and jointly optimizes the tasks of both recommendation and link prediction. Using a Bayesian task weight learner, MTRec is able to achieve the balance of two tasks during optimization automatically. Moreover, MTRec provides good interpretabilities of recommendation through a “translation” mechanism which is used to model the three-way interactions among users, items and the meta-paths connecting them. Experimental results demonstrate the superiority of MTRec over state-of-the-art HIN-based recommendation models, and the case studies we provide illustrate that MTRec enhances the explainability of RS.

Given a graph G where each node is associated with a set of attributes, and a parameter k specifying the number of output clusters, k-attributed graph clustering (k-AGC) groups nodes in G into k disjoint clusters, such that nodes within the same cluster share similar topological and attribute characteristics, while those in different clusters are dissimilar. This problem is challenging on massive graphs, e.g., with millions of nodes and billions of attribute values. For such graphs, existing solutions either incur prohibitively high costs, or produce clustering results with compromised quality.

Given a set V , the problem of unconstrained submodular maximization with modular costs (USM-MC) asks for a subset S ⊆ V that maximizes f ( S ) - c ( S ), where f is a non-negative, monotone, and submodular function that gauges the utility of S , and c is a non-negative and modular function that measures the cost of S. This problem finds applications in numerous practical scenarios, such as profit maximization in viral marketing on social media. This paper presents ROI-Greedy, a polynomial time algorithm for USM-MC that returns a solution S satisfying [EQUATION], where S * is the optimal solution to USM-MC. To our knowledge, ROI-Greedy is the first algorithm that provides such a strong approximation guarantee. In addition, we show that this worst-case guarantee is tight , in the sense that no polynomial time algorithm can ensure [EQUATION], for any ϵ > 0. Further, we devise a non-trivial extension of ROI-Greedy to solve the profit maximization problem, where the precise value of f ( S ) for any set S is unknown and can only be approximated via sampling. Extensive experiments on benchmark datasets demonstrate that ROI-Greedy significantly outperforms competing methods in terms of the tradeoff between efficiency and solution quality.

Given a graph G and a node u ∈ G, a single source SimRank query evaluates the similarity between u and every node v ∈ G. Existing approaches to single source SimRank computation incur either long query response time, or expensive pre-computation, which needs to be performed again whenever the graph G changes. Consequently, to our knowledge none of them is ideal for scenarios in which (i) query processing must be done in realtime, and (ii) the underlying graph G is massive, with frequent updates. Motivated by this, we propose SimPush, a novel algorithm that answers single source SimRank queries without any pre-computation, and achieves significantly higher query speed than even the fastest known index-based solutions. Further, SimPush provides rigorous result quality guarantees, and its high performance does not rely on any strong assumption of the graph. Specifically, compared to existing methods, SimPush employs a radically different algorithmic design that focuses on (i) identifying a small number of nodes relevant to the query, and subsequently (ii) computing statistics and performing residue push from these nodes only. We prove the correctness of SimPush, analyze its time complexity, and compare its asymptotic performance with that of existing methods. Meanwhile, we evaluate the practical performance of SimPush through extensive experiments on 9 real datasets. The results demonstrate that SimPush consistently outperforms all existing solutions, often by over an order of magnitude. In particular, on a commodity machine, SimPush answers a single source SimRank query on a web graph containing over 133 million nodes and 5.4 billion edges in under 62 milliseconds, with 0.00035 empirical error, while the fastest index-based competitor needs 1.18 seconds.

Given a graph G where each node is associated with a set of attributes, attributed network embedding (ANE) maps each node v ∈ G to a compact vector X v , which can be used in downstream machine learning tasks. Ideally, X v should capture node v 's affinity to each attribute, which considers not only v 's own attribute associations, but also those of its connected nodes along edges in G . It is challenging to obtain high-utility embeddings that enable accurate predictions; scaling effective ANE computation to massive graphs with millions of nodes pushes the difficulty of the problem to a whole new level. Existing solutions largely fail on such graphs, leading to prohibitive costs, low-quality embeddings, or both. This paper proposes PANE, an effective and scalable approach to ANE computation for massive graphs that achieves state-of-the-art result quality on multiple benchmark datasets, measured by the accuracy of three common prediction tasks: attribute inference, link prediction, and node classification. In particular, for the large MAG data with over 59 million nodes, 0.98 billion edges, and 2000 attributes, PANE is the only known viable solution that obtains effective embeddings on a single server, within 12 hours. PANE obtains high scalability and effectiveness through three main algorithmic designs. First, it formulates the learning objective based on a novel random walk model for attributed networks. The resulting optimization task is still challenging on large graphs. Second, PANE includes a highly efficient solver for the above optimization problem, whose key module is a carefully designed initialization of the embeddings, which drastically reduces the number of iterations required to converge. Finally, PANE utilizes multi-core CPUs through non-trivial parallelization of the above solver, which achieves scalability while retaining the high quality of the resulting embeddings. Extensive experiments, comparing 10 existing approaches on 8 real datasets, demonstrate that PANE consistently outperforms all existing methods in terms of result quality, while being orders of magnitude faster.

Given an input graph G and a node v ∈ G , homogeneous network embedding (HNE) maps the graph structure in the vicinity of v to a compact, fixed-dimensional feature vector. This paper focuses on HNE for massive graphs, e.g. , with billions of edges. On this scale, most existing approaches fail, as they incur either prohibitively high costs, or severely compromised result utility. Our proposed solution, called Node-Reweighted PageRank (NRP), is based on a classic idea of deriving embedding vectors from pairwise personalized PageRank (PPR) values. Our contributions are twofold: first, we design a simple and efficient baseline HNE method based on PPR that is capable of handling billion-edge graphs on commodity hardware; second and more importantly, we identify an inherent drawback of vanilla PPR, and address it in our main proposal NRP. Specifically, PPR was designed for a very different purpose, i.e. , ranking nodes in G based on their relative importance from a source node's perspective. In contrast, HNE aims to build node embeddings considering the whole graph. Consequently, node embeddings derived directly from PPR are of suboptimal utility. The proposed NRP approach overcomes the above deficiency through an effective and efficient node reweighting algorithm, which augments PPR values with node degree information, and iteratively adjusts embedding vectors accordingly. Overall, NRP takes O ( m log n ) time and O ( m ) space to compute all node embeddings for a graph with m edges and n nodes. Our extensive experiments that compare NRP against 18 existing solutions over 7 real graphs demonstrate that NRP achieves higher result utility than all the solutions for link prediction, graph reconstruction and node classification, while being up to orders of magnitude faster. In particular, on a billion-edge Twitter graph, NRP terminates within 4 hours, using a single CPU core.

Given a graph G , a source node s ∈ G and a positive integer k , a top- k Personalized PageRank (PPR) query returns the k nodes with the highest PPR values with respect to s , where the PPR of a node v measures its relevance from the perspective of source s. Top- k PPR processing is a fundamental task in many important applications such as web search, social networks, and graph analytics. This paper aims to answer such a query in realtime , i.e., within less than 100ms, on an Internet-scale graph with billions of edges. This is far beyond the current state of the art, due to the immense computational cost of processing a PPR query. We achieve this goal with a novel algorithm kPAR, which utilizes the massive parallel processing power of GPUs. The main challenge in designing a GPU-based PPR algorithm lies in that a GPU is mainly a parallel computation device, whereas PPR processing involves graph traversals and value propagation operations, which are inherently sequential and memory-bound. Existing scalable PPR algorithms are mostly described as single-thread CPU solutions that are resistant to parallelization. Further, they usually involve complex data structures which do not have efficient adaptations on GPUs. kPAR overcomes these problems via both novel algorithmic designs (namely, adaptive forward push and inverted random walks ) and system engineering (e.g., load balancing) to realize the potential of GPUs. Meanwhile, kPAR provides rigorous guarantees on both result quality and worst-case efficiency. Extensive experiments show that kPAR is usually 10x faster than parallel adaptations of existing methods. Notably, on a billion-edge Twitter graph, kPAR answers a top-1000 PPR query in 42.4 milliseconds.

Spatial clustering deals with the unsupervised grouping of places into clusters and finds important applications in urban planning and marketing. Current spatial clustering models disregard information about the people and the time who and when are related to the clustered places. In this paper, we show how the density-based clustering paradigm can be extended to apply on places which are visited by users of a geo-social network. Our model considers spatio-temporal information and the social relationships between users who visit the clustered places. After formally defining the model and the distance measure it relies on, we provide alternatives to our model and the distance measure. We evaluate the effectiveness of our model via a case study on real data; in addition, we design two quantitative measures, called social entropy and community score, to evaluate the quality of the discovered clusters. The results show that temporal-geo-social clusters have special properties and cannot be found by applying simple spatial clustering approaches and other alternatives.

RDF data are traditionally accessed using structured query languages, such as SPARQL. However, this requires users to understand the language as well as the RDF schema. Keyword search on RDF data aims at relieving the user from these requirements; the user only inputs a set of keywords and the goal is to find small RDF subgraphs which contain all keywords. At the same time, popular RDF knowledge bases also include spatial semantics, which opens the road to location-based search operations. In this work, we propose and study a novel location-based keyword search query on RDF data. The objective of top-k relevant semantic places (kSP) retrieval is to find RDF subgraphs which contain the query keywords and are rooted at spatial entities close to the query location. The novelty of kSP queries is that they are location-aware and that they do not rely on the use of structured query languages. We design a basic method for the processing of kSP queries. To further accelerate kSP retrieval, two pruning approaches and a data preprocessing technique are proposed. Extensive empirical studies on two real datasets demonstrate the superior and robust performance of our proposals compared to the basic method.

We study the modeling and evaluation of aspatio-textual skyline(STS) query, in which the skyline points are selected not only based on their distances to a set of query locations, but also based on their relevance to a set of query keywords. STS is especially relevant to modern applications, where points of interest are typically augmented with textual descriptions. We investigate three models for integrating textual relevance into the spatial skyline. Among them, model STD, which combines spatial distance with textual relevance in a derived dimensional space, is found to be the most effective one. STD computes a skyline which not only satisfies the intent of STS, but also has a small and easy-to-interpret size. We propose an efficient algorithm for computing STD-based skylines, which operates on an IR-tree that indexes the data. The effectiveness of our STD model and the efficiency of the proposed algorithm are evaluated on real data sets.

Spatial clustering deals with the unsupervised grouping of places into clusters and finds important applications in urban planning and marketing. Current spatial clustering models disregard information about the people who are related to the clustered places. In this paper, we show how the density-based clustering paradigm can be extended to apply on places which are visited by users of a geo-social network. Our model considers both spatial information and the social relationships between users who visit the clustered places. After formally defining the model and the distance measure it relies on, we present efficient algorithms for its implementation, based on spatial indexing. We evaluate the effectiveness of our model via a case study on real data; in addition, we design two quantitative measures, called social entropy and community score to evaluate the quality of the discovered clusters. The results show that geo-social clusters have special properties and cannot be found by applying simple spatial clustering approaches. The efficiency of our index-based implementation is also evaluated experimentally.