Continual Knowledge Graph Embedding (CKGE) aims to continually learn embeddings for new knowledge, i.e., entities and relations, while retaining previously acquired knowledge. Most existing CKGE methods mitigate catastrophic forgetting via regularization or replaying old knowledge. They conflate new and old knowledge of an entity within the same embedding space to seek a balance between them. However, entities inherently exhibit multi-faceted semantics that evolve dynamically as their relational contexts change over time. A shared embedding fails to capture and distinguish these temporal semantic variations, degrading lifelong link prediction accuracy across snapshots. To address this, we propose a Multi-Faceted CKGE framework (MF-CKGE) for semantic-aware link prediction. During offline learning, MF-CKGE separates temporal old and new knowledge into distinct embedding spaces to prevent knowledge entanglement and employs semantic decoupling to reduce semantic redundancy, thereby improving space efficiency. During online inference, MF-CKGE adaptively identifies semantically query-relevant entity embeddings by quantifying their semantic importance, reducing interference from query-irrelevant noise. Experiments on eight datasets show that MF-CKGE achieves an average (maximum) improvement of 1.7% (2.7%) and 1.4% (3.8%) in MRR and Hits@10, respectively, over the best baseline. Our source code and datasets are available at: https://anonymous.4open.science/r/MF-CKGE-04E5.

Community search on attributed graphs (CSAG) is a fundamental topic in graph data mining. Given an attributed graph G and a query node q , CSAG seeks a structural- and attribute-cohesive subgraph from G that contains q . Exact methods based on graph traversal are time-consuming, especially for large graphs. Approximate methods improve efficiency by pruning the search space with heuristics but still take hundreds of milliseconds to tens of seconds to respond, hindering their use in time-sensitive applications. Moreover, pruning strategies are typically tailored to specific algorithms and their cohesiveness metrics, making them difficult to generalize. To address this, we study a general approach to accelerate various CSAG methods. We first present a proximity graph-based, cohesiveness-aware hierarchical index that accommodates different cohesiveness metrics. Then, we present two optimizations to enhance the index's navigability and reliability. Finally, we design a compressed storage structure for space-efficient indexing. Experiments on real-world datasets show that integrating our index with existing mainstream CSAG methods results in an average 30.7× speedup while maintaining a comparable or even better attribute cohesiveness.

Attributed graphs are extensively utilized in marketing, friend recommendations, disease prediction, etc. In attributed graphs, nodes are associated with attributes to enrich the graph representation, while edges indicate relationships between nodes. However, ensuring data privacy when publishing attributed graphs is a significant challenge due to the sensitive nature of both attributes and relationships. Existing methods fail to preserve graph structures effectively and neglect correlations among node attributes, leading to diminished utility for published synthetic graphs. To address these issues, we propose PrivAGS, a framework for publishing attributed graphs with Rényi Differential Privacy (RDP) guarantees. PrivAGS reconstructs graph structures and attributes based on community structures to capture tightly connected features. We propose a bounded Gaussian threshold mechanism to preserve attribute correlations and utilize probabilistic graph models with optimized inference structures to infer distributions and release node attributes. Additionally, PrivAGS introduces a new structural model, MCEG, to capture clustering structures and enable efficient graph reconstruction. Extensive experiments on five real-world datasets show that PrivAGS generates privacy-preserving, high-utility synthetic data.

Given a graph G and a query node q , the goal of community search (CS) is to find a structurally cohesive subgraph from G that contains q. Significant progress has been made in community search using deep learning in recent years. To the best of our knowledge, no existing work has provided a comprehensive review of learning-based community search methods. Additionally, we find that: (1) Existing methods offer diverse definitions or descriptions of communities, which require systematic summarization. (2) The methods rely on distinct metrics for limited community assessment. (3) Overhead evaluations of the methods vary and exhibit certain biases. Therefore, a comprehensive survey and experimental study are essential to achieve four key objectives: designing a unified pipeline, clarifying community definitions, enriching community evaluation, and establishing overhead assessment. In this paper, we first propose a unified pipeline for these methods, highlighting techniques. We categorize community definitions and analyze the relationships between identified communities. Beyond that, we proposed several community metrics to evaluate the communities comprehensively. Moreover, we introduce a more detailed overhead evaluation approach that considers resource consumption during both the training and search phases. Finally, we employ the proposed community evaluation metrics and overhead assessment framework to evaluate and analyze the methods, examine correlations among metrics, and explore the effects of several commonly used techniques.

Given an attributed graph$G$and a query node$q$, Community Search over Attributed Graphs (CS-AG) aims to find a structure- and attribute-cohesive subgraph from$G$that contains$q$. Although CS-AG has been widely studied, they still face three challenges. (1) Exact methods based on graph traversal are time-consuming, especially for large graphs. Some tailored indices can improve efficiency, but introduce nonnegligible storage and maintenance overhead. (2) Approximate methods with a loose approximation ratio only provide a coarse-grained evaluation of a community's quality, rather than a reliable evaluation with an accuracy guarantee in runtime. (3) Attribute cohesiveness metrics often ignores the important correlation with the query node$q$. We formally define our CS-AG problem atop a$q- \mathbf{centric}$attribute cohesiveness metric considering both textual and numerical attributes, for$k-\mathbf{core}$model on homogeneous graphs. We show the problem is NP-hard. To solve it, we first propose an exact baseline with three pruning strategies. Then, we propose an index-free sampling-estimation-based method to quickly return an approximate community with an accuracy guarantee, in the form of a confidence interval. Once a good result satisfying a user-desired error bound is reached, we terminate it early. We extend it to heterogeneous graphs,$k-\mathbf{truss}$model, and size-bounded CS. Comprehensive experimental studies on ten real-world datasets show its superiority, e.g., at least$1.54\times (41.1\times$on average) faster in response time and a reliable relative error (within a user-specific error bound) of attribute cohesiveness is achieved.

Given a vector dataset$\mathcal{X}$, a query vector$\vec{x}_{q}$, graph-based Approximate Nearest Neighbor Search (ANNS) aims to build a proximity graph (PG) as an index of$\mathcal{X}$and approximately return vectors with minimum distances to$\vec{x}_{q}$by searching over the PG index. It has been widely recognized that graph-based ANNS is effective and efficient, however, it suffers from the large-scale$\mathcal{X}$because of the entire PG is too large to fit into the memory. To solve this, Product Quantization (PQ) integrated graph-based ANNS is proposed to reduce the memory usage, by replacing a large PG with original vectors by the one with smaller compact codes of quantized vectors. Existing PQ methods do not consider the important routing features of PG, thus resulting in low-quality quantized vectors that significantly affect the ANNS's effectiveness. In this paper, we present an end-to-end Routing-guided learned Product Quantization (RPQ) for graph-based ANNS, which easily can be adaptive to existing popular PGs. Specifically, RPQ consists of (1) a differentiable quantizer used to make the standard discrete PQ differentiable to suit for back-propagation of end-to-end learning, (2) a sampling-based feature extractor used to extract neighborhood and routing features of a PG by using the quantized vectors, and (3) a multi-feature joint training module with two types of feature-aware losses to continuously optimize the differentiable quantizer. As a result, the inherent features of a specific PG would be embedded into the learned PQ, thus generating high-quality quantized vectors that facilitate the graph-based ANNS's effectiveness and efficiency. Moreover, we integrate our RPQ with the state-of-the-art DiskANN and existing PGs to improve their performance. Comprehensive experimental studies on real-world large-scale datasets (scale from 1M to 1B) demonstrate RPQ's superiority.

Given a graph G and a query node q, community search (CS) aims to find a structurally cohesive subgraph from G that contains q. CS is widely used in many real-world applications, such as online recommendation and expert finding. Recently, the rise of learning-based CS methods has garnered extensive research interests, showcasing the promising potential of neural solutions. However, there remains room for optimization: (1) They initialize node features via classical methods, e.g., one-hot, random, and position encoding, which may fall short in capturing valuable community cohesiveness-related features. (2) The reliance on GCN or GCN-like models poses challenges in scaling to large graphs. (3) Existing methods do not adapt well to dynamic graphs, often requiring retraining from scratch. To handle this, we present CSFormer, a scalable CS based on Graph Transformer. First, we present a novel l-hop neighborhood community vector based on n-order h-index to represent each node's community features, generating a sequence of feature vectors by varying the neighborhood scope l. Then, we build a Transformer backbone to learn a good graph embedding that carries rich community features, based on which we perform a prediction-filtering-based online CS to efficiently return a community of q. We extend CSFormer to dynamic graphs and various community models. Extensive experiments on seven real-world graphs show our solution's superiority on effectiveness, e.g., we attain an average improvement of 20.6% in F1-score compared to the latest competitors.

Given a graph G and a query node q, community search (CS) seeks a cohesive subgraph from G that contains q. CS has gained much research interests recently. In the database research community, researchers aim to find the most cohesive subgraph satisfying a specific community model (e.g., k-core or k-truss) via graph traversal. These works obtain good precision, however suffering from the low efficiency issue. In the AI research community, a new thought of using the deep learning model to support CS without relying on graph traversal emerges. Supervised end-to-end models using GCN are presented, which perform efficiently, but leave a large room for precision improvement. None of them can achieve a good balance between the efficiency and effectiveness. This motivates our solution: First, we present an offline community-injected graph embedding method to preserve the community’s cohesiveness features into the learned node representations. Second, we resort to a proximity graph (PG) built from node representations, to quickly return the community online. Moreover, we develop a self-augmented method based on KL divergence to further optimize node representations. Extensive experiments on seven real-world graphs show our solution’s superiority on effectiveness (at least 39.3% improvement) and efficiency (one to two orders of magnitude faster).

This paper introduces an efficient and robust framework for hybrid query (HQ) processing, which combines approximate nearest neighbor search (ANNS) with attribute constraint. HQ aims to find objects that are similar to a feature vector and match some structured attributes. Existing methods handle ANNS and attribute filtering separately, leading to inefficiency and inaccuracy. Our framework, called native hybrid query (NHQ), builds a composite index based on proximity graph (PG) and applies joint pruning for HQ. We can easily adapt existing PGs to this framework for efficient HQ processing. We also propose two new navigable PGs (NPGs) with optimized edge selection and routing, which improve the overall ANNS performance. We implement five HQ methods based on the proposed NPGs and existing PGs in NHQ, and show that they outperform the state-of-the-art methods on 10 real-world datasets (up to 315$\times$ faster with the same accuracy).

Expert finding is crucial for a wealth of applications in both academia and industry. Given a user query and trove of academic papers, expert finding aims at retrieving the most relevant experts for the query, from the academic papers. Existing studies focus on embedding-based solutions that consider academic papers’ textual semantic similarities to a query via document representation and extract the top- n experts from the most similar papers. Beyond implicit textual semantics, however, papers’ explicit relationships (e.g., co-authorship) in a heterogeneous graph (e.g., DBLP) are critical for expert finding, because they help improve the representation quality. Despite their importance, the explicit relationships of papers generally have been ignored in the literature. In this article, we study expert finding on heterogeneous graphs by considering both the explicit relationships and implicit textual semantics of papers in one model. Specifically, we define the cohesive ( k , 𝒫)-core community of papers w.r.t. a meta-path 𝒫 (i.e., relationship) and propose a ( k , 𝒫)-core based document embedding model to enhance the representation quality. Based on this, we design a proximity graph-based index (PG-Index) of papers and present a threshold algorithm (TA)-based method to efficiently extract top- n experts from papers returned by PG-Index. We further optimize our approach in two ways: (1) we boost effectiveness by considering the ( k , 𝒫)-core community of experts and the diversity of experts’ research interests, to achieve high-quality expert representation from paper representation; and (2) we streamline expert finding, going from “extract top- n experts from top- m ( m> n ) semantically similar papers” to “directly return top- n experts”. The process of returning a large number of top- m papers as intermediate data is avoided, thereby improving the efficiency. Extensive experiments using real-world datasets demonstrate our approach’s superiority.

This paper demonstrates AGQ [26] - our system for approximate and interactive processing of aggregate queries on knowledge graphs (KGs), e.g., "what is the average price of cars produced in Germany?" One can support aggregate queries based on factoid queries, e.g., "find all cars produced in Germany", by applying an aggregate operation on factoid queries' answers. However, this straightforward method is problematic since both the accuracy and efficiency of factoid query processing would impact the performance of aggregate queries. Moreover, returning a one-time, exact result might add computation overhead and hinder users' engagement and interactivity.

A knowledge graph (KG) manages large-scale and real-world facts as a big graph in a schema-flexible manner. Aggregate query is a fundamental query over KGs, e.g., “what is the average price of cars produced in Germany?”. Despite its importance, answering aggregate queries on KGs has received little attention in the literature. Aggregate queries can be supported based on factoid queries, e.g., “find all cars produced in Germany”, by applying an additional aggregate operation on factoid queries' answers. However, this straightforward method is challenging because both the accuracy and efficiency of factoid query processing will seriously impact the performance of aggregate queries. In this paper, we propose a “sampling-estimation” model to answer aggregate queries over KGs, which is the first work to provide an approximate aggregate result with an effective accuracy guarantee, and without relying on factoid queries. Specifically, we first present a semantic-aware sampling to collect a high-quality random sample through a random walk based on knowledge graph embedding. Then, we propose unbiased estimators for COUNT, SUM, and a consistent estimator for AVG to compute the approximate aggregate results based on the random sample, with an accuracy guarantee in the form of confidence interval. We extend our approach to support iterative improvement of accuracy, and more complex queries with filter, GROUP-BY, and different graph shapes, e.g., chain, cycle, star, flower. Extensive experiments over real-world KGs demonstrate the effectiveness and efficiency of our approach.

Finding relevant experts in specified areas is often crucial for a wide range of applications in both academia and industry. Given a user input query and a large amount of academic knowledge (e.g., academic papers), expert finding aims to find and rank the experts who are most relevant to the given query, from the academic knowledge. Existing studies mainly focus on the embedding-based solutions that (1) consider academic papers' textual semantic similarities to a given query through document representation models and (2) extract the$\mathbf{top-}n$experts with the greatest similarities. Beyond the implicit textual semantics of papers, however, the papers' explicit relationships (e.g., co-authorship, citation, and same-topic relationship) in a heterogeneous academic graph (e.g., DBLP) are critical for document representation, insofar as they help improve the expert finding quality. Despite their importance, the explicit relationships of papers generally have been ignored in the literature. In this paper, we study the academic expert finding on heterogeneous graphs by considering the explicit relationships besides the implicit textual semantics of papers in one representation model. Specifically, we first define the$(k,\mathcal{P})$-core to denote a cohesive community of papers that are closely connected via a meta-path$\mathcal{P}(\mathcal{P}$indicates the different relationships of papers). We then propose an offline$(k,\mathcal{P})$-core based document embedding model to capture papers' various explicit relationships for representation. Moreover, by using papers' embeddings, we present an online threshold algorithm (TA)-based method to efficiently return top-n experts via a carefully designed proximity graph-based index (PG-Index). We extend our approach to support multiple relationships simultaneously for representation. Extensive experiments over real-world datasets demonstrate the effectiveness and efficiency of our approach.

Approximate nearest neighbor search (ANNS) constitutes an important operation in a multitude of applications, including recommendation systems, information retrieval, and pattern recognition. In the past decade, graph-based ANNS algorithms have been the leading paradigm in this domain, with dozens of graph-based ANNS algorithms proposed. Such algorithms aim to provide effective, efficient solutions for retrieving the nearest neighbors for a given query. Nevertheless, these efforts focus on developing and optimizing algorithms with different approaches, so there is a real need for a comprehensive survey about the approaches' relative performance, strengths, and pitfalls. Thus here we provide a thorough comparative analysis and experimental evaluation of 13 representative graph-based ANNS algorithms via a new taxonomy and fine-grained pipeline. We compared each algorithm in a uniform test environment on eight real-world datasets and 12 synthetic datasets with varying sizes and characteristics. Our study yields novel discoveries, offerings several useful principles to improve algorithms, thus designing an optimized method that outperforms the state-of-the-art algorithms. This effort also helped us pinpoint algorithms' working portions, along with rule-of-thumb recommendations about promising research directions and suitable algorithms for practitioners in different fields.

Recently, graph query is widely adopted for querying knowledge graphs. Given a query graph GQ, the graph query finds subgraphs in a knowledge graph G that exactly or approximately match GQ. We face two challenges on graph query: (1) the structural gap between GQand the predefined schema in G causes mismatch with query graph, (2) users cannot view the answers until the graph query terminates, leading to a longer system response time (SRT). In this paper, we propose a semantic-guided and response-time-bounded graph query to return the top-k answers effectively and efficiently. We leverage a knowledge graph embedding model to build the semantic graph SGQ, and we define the path semantic similarity (pss) over SGQas the metric to evaluate the answer's quality. Then, we propose an A* semantic search on SGQto find the top-k answers with the greatest pss via a heuristic pss estimation. Furthermore, we make an approximate optimization on A* semantic search to allow users to trade off the effectiveness for SRT within a user- specific time bound. Extensive experiments over real datasets confirm the effectiveness and efficiency of our solution.

Summary Approximate nearest neighbor search (ANNS) is widely employed to find the most similar data efficiently from a large‐scale dataset. The key of ANNS is to construct an effective index to prune the search space and retrieve the approximate data rather than the exact one in a very short time. Most of the existing ANNS methods only adopt the distance metric to build an index, which cannot support multiattribute ANNS. In this article, we present a novel approach for multiattribute ANNS based on navigable small world (NSW) graph, called MA‐NSW. Given a dataset, MA‐NSW (i) builds a proximity subgraph overlay for each multiattribute combination, and integrates all overlays to a hierarchical index, (ii) adopts a navigation tree to access related subgraph overlay and prune unrelated overlays, and (iii) gets nearest neighbor results from the related overlays by greedy search. MA‐NSW guarantees efficiency and it is defined in terms of arbitrary metric spaces (eg, Euclidean distance and cosine similarity). Performance evaluation has demonstrated that the proposed approach shows superior performance in multiattribute ANNS.

Summary RDF knowledge graphs (KG) usually contain billions of labeled entities, and how to obtain the desired results efficiently on RDF KG for given SPARQL queries have attracted increasing attentions recently. However, it is difficult for users to write a complex SPARQL query without full knowledge of the underlying KG schema due to the “schema‐free” feature of RDF KG. In this paper, we study the problem of acquiring semantic approximate results for a simple SPARQL query instead of the complex expression. The basic idea behind is to use the real knowledge semantics to extend the query intention of given simplified SPARQL query, and then a semantic based greedy search over is designed to return top‐k similar results. To obtain the knowledge semantics efficiently, we define type similarity to reorganize the original KG as a corpus with semantic locality and then a context aware text embedding model is adopted to achieve the semantic vectors of existing knowledge. Afterwards, an approximate query method over RDF KG is designed to obtain top‐k similar results based on the knowledge semantics above. Extensive experiments over DBpedia dataset and QALD‐4 benchmark confirm our solution's superiority on both effectiveness and efficiency.

Summary Online aggregation is a query processing technique that returns approximate answers with error guarantees (in the form of confidence intervals) continuously during the query execution process. This approach offers users a suitable tradeoff between query efficiency and accuracy. The key issue of online aggregation is how to ensure a random sample collection's efficiency and effectiveness. However, the often‐used “blind” sampling method does not adequately consider dataset statistics and other useful information, leading to inefficient sampling and poor sample quality. This becomes a glaring performance issue for skewed data distribution over joins. To alleviate this problem, we utilize dataset statistics to propose a new “guided” sampling approach, which consists of a logic‐partition‐based weighted Gaussian sampling method tailored for the skewed join key, as well as a two‐level sample allocation method that applies to the skewed measured value. Extensive experiments using the TPC‐H benchmark for skewed data distribution demonstrate our solution's superior performance.

Sampling-based approximate query processing method provides the way, in which the users can save their time and resources for 'Big Data' analytical applications, if the estimated results can satisfy the accuracy expectation earlier before a long wait for the final accurate results. Online aggregation (OLA) is such an attractive technology to respond aggregation queries by calculating approximate results with the confidence interval getting tighter over time. It has been built into the MapReuduce-based cloud system for big data analytics, which allows users to monitor the query progress and save money by killing the computation earlier once sufficient accuracy has been obtained. Unfortunately, there exists a major obstacle that is the estimation failure of OLA affects the OLA performance, which is resulted from the biased sample set that violates the unbiased assumption of OLA sampling. To handle this problem, we first propose a hybrid approximate query processing model to improve the overall OLA performance, where a dynamic scheme switching mechanism is deliberately designed to switch unpromising OLA queries into the bootstrap scheme for further processing, avoiding the whole dataset scanning resulted from the OLA estimation failure. In addition, we also present a progressive estimation method to reduce the false positive ratio of our dynamic scheme switching mechanism. Moreover, we have implemented our hybrid approximate query processing system in Hadoop, and conducted extensive experiments on the TPC-H benchmark for skewed data distribution. Our results demonstrate that our hybrid system can produce acceptable approximate results within a time period one order of magnitude shorter compared to the original OLA over Hadoop.

Personalized recommendation technology in E-commerce is widespread to solve the problem of product information overload. However, with the further growth of the number of E-commerce users and products, the original recommendation algorithms and systems will face several new challenges: (1) to model user's interests more accurately, (2) to provide more diverse recommendation modes, and (3) to support large-scale expansion. To address these challenges, from the actual demands of E-commerce applications (as Made-in-China website), a personalized hybrid recommendation system, which can support massive data set, is designed and implemented in this paper by using Cloud technology. Hereinto, the recommendation algorithms are designed based on a novel user interesting model for different scenarios, and the massive data parallel processing techniques in Cloud computing is utilized to realize the effective execution of recommendation algorithms. Finally, several experiments are presented to highlight the system performance.