Lei Zou

Given a query graph, top-k subgraph matching finds up to $k$ matches in a data graph with the highest scores according to a user-defined scoring function. It has wide applications across many fields, including knowledge graphs and social networks. Due to the enormous search space, existing methods are not efficient enough on large graphs. In this paper, we propose PTAB, an efficient serial algorithm for top-k subgraph matching. It traverses an efficiently pruned search space by topology-aware subspace score upper bounds computed from a novel hop index, which stores the range of node properties in a constrained multi-hop neighborhood of each node. Additionally, PTAB integrates a cost-aware root selection strategy, which chooses query nodes leading to a search process that utilizes the pruning power of the hop index as much as possible. Furthermore, we use a novel edge-cut strategy to handle general query graphs with cycles. We also extend PTAB to a parallel version, PTABP, which further improves performance via multi-threading and enhanced pruning techniques. Experimental results on real and synthetic datasets demonstrate that our methods outperform existing methods.

In distributed property graph systems, complex pattern queries are typically decomposed into subqueries that can be independently executed within individual partitions. However, the integration of their results requires inter-partition joins, which incur significant communication overhead. Moreover, the order of inter-partition joins plays a pivotal role in determining the size of intermediate results, which subsequently affects the overall efficiency of distributed query processing. To address these challenges, we propose R2O (Rewriting to Ordering), a dual-layer framework that jointly optimizes both inter-partition joins and join order for distributed pattern queries. We first introduce a partition-aware query rewriting strategy, which restructures and merges subqueries at partition boundaries to reduce intermediate results during inter-partition joins. Building on this strategy, R2O employs graph neural networks and reinforcement learning to construct a local rewriting model and a global ordering model. This unified end-to-end model effectively reduces intermediate results during inter-partition joins and identifies effective join orders, enabling efficient distributed query plan optimization. Experimental results on billion-scale property graphs indicate that R2O is compatible with different partitioning methods and yields 1–2 orders of magnitude speedup (up to 3 orders in some queries) over state-of-the-art query optimization techniques.

Continuous subgraph matching (CSM), which finds incremental matches of a query graph for each update in a dynamic graph, has gained significant research attention. Most CSM algorithms follow a common indexing-enumeration paradigm: they first use indexes to identify candidate vertices and edges for the query graph, and then enumerate matches based on these candidates. Although there have been several comprehensive experimental analyses of CSM algorithms, they tend to evaluate CSM algorithms holistically, obscuring the distinct contributions of the indexing and enumeration methods to overall performance. In this paper, we decouple the indexing method and enumeration method of existing CSM algorithms, and focus on the comparison of indexing methods. Our experimental results offer guidance on index selection across different scenarios, serving as a reference for future research and industrial applications. They further reveal the relative importance of different index components, informing strategies to discard less essential parts when memory is limited. Additionally, we show that the commonly used candidate count metric may underestimate the filtering effectiveness of certain indexes, suggesting that future research should adopt more reliable evaluation metrics.

The advent of in-context learning (ICL) allows pretrained large language models (LLMs) to handle unseen inputs by leveraging context, without requiring parameter updates. However, the success of ICL is strongly influenced by factors such as the quality, size, and ordering of demonstrations, often resulting in unstable or less-than-ideal outcomes. This work is the first to address these limitations through the lens of demonstration augmentation. We first propose a simple yet effective ICL method, termed implicit demonstration augmentation-based ICL (IDAICL), that enriches demonstrations by leveraging their deep feature distributions, integrating knowledge from the entire demonstration set to enhance LLM predictions. From a theoretical standpoint, we demonstrate that when the number of augmented samples tends to infinity, our method asymptotically converges to a new form of logit calibration. Building upon this foundation, we further propose a domain-aware IDAICL (D-IDAICL) method, which improves the precision of knowledge integration by identifying and leveraging the most pertinent domain for each test sample during augmentation. Specifically, a hypernetwork is employed to adaptively select the most effective domain based on the deep representation of the test sample. The corresponding domain-specific knowledge is then utilized to augment the demonstrations, resulting in a domain-aware logit calibration function that enhances predictive performance. Comprehensive evaluations across multiple tasks using eight LLMs reveal that both approaches markedly boost overall and worst-case accuracy, leading to improved robustness and predictive capability. In addition, our approaches mitigate performance fluctuations across different demonstrations, orderings, and templates, while also showing effectiveness in handling class imbalance.

Graph streams are rapidly evolving sequences of edges that convey continuously changing relationships among entities, playing a crucial role in domains such as networking, finance, and cybersecurity. Their massive scale and high dynamism make obtaining accurate statistics challenging with limited memory constraints. Traditional methods summarize graph streams through hand-crafted sketches, while recent studies have begun to replace these sketches with neural counterparts to improve adaptability and accuracy. However, this shift faces a major challenge: under limited memory, dominant frequent items tend to overshadow rare ones, hindering the neural network's ability to recover accurate statistics. To address this, we propose Crane, a hierarchical neural sketch architecture for graph stream summarization. Crane uses a hierarchical carry mechanism that automatically elevates frequent items to higher memory layers, reducing interference between frequent and infrequent items within the same layer. To better accommodate real-world deployment, Crane further adopts an adaptive memory expansion strategy that dynamically adds new layers once the occupancy of the top layer exceeds a threshold, enabling scalability across diverse data magnitudes. Extensive experiments on various datasets ranging from 20K to 60M edges demonstrate that Crane reduces estimation error by roughly 10x compared to state-of-the-art methods.

With the increasing use of RDF graphs, storing and querying such data using SPARQL remains a critical problem. Current mainstream solutions rely on cloud-based data management architectures, but often suffer from performance bottlenecks in environments with limited bandwidth or high system load. To address this issue, this paper explores for the first time the integration of edge computing to move graph data storage and processing to edge environments, thereby improving query performance. This approach requires offloading query processing to edge servers, which involves addressing two challenges: data localization and network scheduling. First, the data localization challenge lies in computing the subgraphs maintained on edge servers to quickly identify the servers that can handle specific queries. To address this challenge, we introduce a new concept of pattern-induced subgraphs. Second, the network scheduling challenge involves efficiently assigning queries to edge and cloud servers to optimize overall system performance. We tackle this by constructing a overall system model that jointly captures data distribution, query characteristics, network communication, and computational resources. Accordingly, we further propose a joint formulation of query assignment and computational resource allocation, modeling it as a Mixed Integer Nonlinear Programming (MINLP) problem and solve this problem using a modified branch-and-bound algorithm. Experimental results on real datasets under a real cloud platform demonstrate that our proposed method outperforms the state-of-the-art baseline methods in terms of efficiency. The codes are available on GitHub

With a global shortage of primary healthcare physicians—particularly in resource-limited settings—large language models (LLMs) have the potential to support and enhance patients’ health awareness. Here we developed P&P Care (Population Medicine and Public Health), an LLM-powered primary care chatbot using a dual-track role-play codesign framework where community stakeholders and researchers simulated each another’s perspectives across four phases: contextual understanding; cocreation; testing and refinement; and implementation and evolution. The codesigned chatbot was integrated with e-learning modules and tested in a randomized controlled trial. The trial included 2,113 participants (1,052 women and 1,061 men) from urban and rural areas across 11 Chinese provinces who were randomly assigned to receive a consultation either with preparatory e-learning via the P&P Care or without. The study met its primary endpoint with the e-learning group showing significantly higher objective health awareness (mean score 2.95 ± 1.22) compared with the consultation-only group (mean score 2.34 ± 1.02; P < 0.001). Codesign offers a scalable solution for deploying LLMs in resource-limited settings. Chinese Clinical Trial Registry identifier: ChiCTR2500098101 .