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.

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.