Query rewriting is essential for database performance optimization, but existing automated rule enumeration methods suffer from exponential search spaces, severe redundancy, and poor scalability, especially when handling complex query plans with five or more nodes, where a node represents an operator in the plan tree. We present SLER, a scalable system that enables efficient and effective rewrite rule discovery by combining standardized template enumeration with a learning to rank approach. SLER uses standardized templates, abstractions of query plans with operator structures preserved but data specific details removed, to eliminate structural redundancies and drastically reduce the search space. A learn to rank model guides enumeration by pre filtering the most promising template pairs, enabling scalable rule generation for large node templates. Evaluated on over 11000 real world SQL queries from both open source and commercial workloads, SLER has automatically constructed a rewrite rule repository exceeding 1 million rules - the largest empirically validated rewrite rule library to date. Notably, at the scale of one million rules, SLER supports query plan templates with complexity up to channel level depth. This unprecedented scale opens the door to discovering highly intricate transformations across diverse query patterns. Critically, SLER's template driven design and learned ranking mechanism are inherently extensible, allowing seamless integration of new and complex operators, paving the way for next generation optimizers powered by comprehensive, adaptive rule spaces.

Abstract Knowledge distillation is a widely used technique whereby knowledge from large pre‐trained models is transferred into smaller student models. However, this process is non‐trivial and traditionally requires technical and theoretical expertise in AI/ML. We investigate a visualization‐driven strategy for making this process more accessible and intuitive via developing I n F i C on D, a novel tool that leverages visual concepts to scaffold the knowledge distillation process and support subsequent no‐code fine‐tuning of student models. I n F i C on D's backend pipeline extracts text‐aligned visual concepts and constructs highly interpretable student models; its frontend supports interactively fine‐tuning these student models by directly manipulating concept influences. Empirical evaluations help validate that I n F i C on D effectively supports knowledge distillation and subsequent fine‐tuning workflows. We additionally discuss insights and lessons learned about how human‐in‐the‐loop and visualization‐driven approaches like I n F i C on D can support accessible and adaptable AI explainability and model distillation.

Communities, formed by a subset of vertices that are densely connected to each other and loosely connected to outside community members, widely exist to represent functional modules in real-world complex systems. Most existing community detection and search methods aim at finding communities at one single level, neglecting the natural properties of overlapping and hierarchy in communities. Therefore, the discovery of hierarchical graph clustering (HGC) to find communities at different levels, which is particularly useful in many applications. However, existing HGC studies suffer from two significant limitations: 1) inefficiency over large-scale networks, and 2) generating too many levels of community hierarchy without distinguishing the hierarchy differences. To address the above limitations, we revisit the problem of hierarchical graph clustering and formulate the problem based on our proposed three important properties. To tackle it, we propose theoretical-guaranteed fast solutions, in terms of algorithm complexity and hierarchy levels. We first formulate our HGC problem to admit three key properties of hierarchical communities. Based on the natural hierarchical structure of$k$-core, we develop a simple and importantly useful technique of core propagation. The key idea of core propagation is to take each$k$-core as one seed of hierarchical communities and find disjoint communities within$k$-core using a linear-time algorithm of label propagation. We propose two core propagation approaches of top-down and bottom-up algorithms, in terms of different search directions of$k$-cores by increment and decrement on$k$, respectively. The top-down method can find a given level of hierarchical communities in$O(t m)$time, where$t$is an input of hierarchy levels and$m$is the graph size. To dismiss the hardness of users' input hierarchy parameter$t$, the bottom-up algorithm is equipped with a well-designed strategy of auto-adjusting hierarchical levels based on the graph structure itself. We also develop the coreness weight-based label propagation to ensure the accurate label voting of compressed communities at low levels. The bottom-up method runs fast in$O(m \log \delta(G))$, where$\log \delta(G)$is a small value of the maximum coreness in graph$G$. Extensive experiments conducted on real-world graphs with ground-truth HGCs validate the effectiveness and efficiency of our proposed core propagation methods against state-of-the-art methods. Two case studies on the world-wide flight network and the Hong Kong road network demonstrate the particular usage of our HGC methods.

The problem of structural diversity search has been widely studied recently, which aims to find out the users with the highest structural diversity in social networks. The structural diversity of a user is depicted by the number of social contexts inside his/her contact neighborhood. Three structural diversity models based on cohesive subgraph models (e.g., k-sized component, k-core, and k-truss), have been proposed. Previous solutions only focus on CPU-based sequential solutions, suffering from several key steps of that cannot be highly parallelized. GPUs enjoy high-efficiency performance in parallel computing for solving many complex graph problems such as triangle counting, subgraph pattern matching, and graph decomposition. In this paper, we provide a unified framework to utilize multiple GPUs to accelerate the computation of structural diversity search under the mentioned three structural diversity models. We first propose a GPU-based lock-free method to efficiently extract ego-networks in CSR format in parallel. Second, we design detailed GPU-based solutions for computingk-sized component-based,k-core-based, and alsok-truss-based structural diversity scores by dynamically grouping GPU resources. To effectively optimize the workload balance among multiple GPUs, we propose a greedy work-packing scheme and a dynamic work-stealing strategy to fulfill usage. Extensive experiments on real-world datasets validate the superiority of our GPU-based structural diversity search solutions in terms of efficiency and effectiveness.

Large language models (LLMs) have gained widespread popularity due to their ability to perform ad-hoc natural language processing (NLP) tasks with simple natural language prompts. Part of the appeal for LLMs is their approachability to the general public, including individuals with little technical expertise in NLP. However, prompts can vary significantly in terms of their linguistic structure, context, and other semantics, and modifying one or more of these aspects can result in significant differences in task performance. Non-expert users may find it challenging to identify the changes needed to improve a prompt, especially when they lack domain-specific knowledge and appropriate feedback. To address this challenge, we present PromptAid, a visual analytics system designed to interactively create, refine, and test prompts through exploration, perturbation, testing, and iteration. PromptAid uses coordinated visualizations which allow users to improve prompts via three strategies: keyword perturbations, paraphrasing perturbations, and obtaining the best set of in-context few-shot examples. PromptAid was designed through a pre-study involving NLP experts, and evaluated via a robust mixed-methods user study. Our findings indicate that PromptAid helps users to iterate over prompts with less cognitive overhead, generate diverse prompts with the help of recommendations, and analyze the performance of the generated prompts while surpassing existing state-of-the-art prompting interfaces in performance.

Augmented reality (AR) provides a significant opportunity to improve collaboration between co-located team members jointly analyzing data visualizations, but existing rigorous studies are lacking. We present a novel method for qualitatively encoding the positions of co-located users collaborating with head-mounted displays (HMDs) to assist in reliably analyzing collaboration styles and behaviors. We then perform a user study on the collaborative behaviors of multiple, co-located synchronously collaborating users in AR to demonstrate this method in practice and contribute to the shortfall of such studies in the existing literature. Pairs of users performed analysis tasks on several data visualizations using both AR and traditional desktop displays. To provide a robust evaluation, we collected several types of data, including software logging of participant positioning, qualitative analysis of video recordings of participant sessions, and pre- and post-study questionnaires including the NASA TLX survey. Our results suggest that the independent viewports of AR headsets reduce the need to verbally communicate about navigating around the visualization and encourage face-to-face and non-verbal communication. Our novel positional encoding method also revealed the overlap of task and communication spaces vary based on the needs of the collaborators.

Traditional deep learning interpretability methods which are suitable for model users cannot explain network behaviors at the global level and are inflexible at providing fine-grained explanations. As a solution, concept-based explanations are gaining attention due to their human intuitiveness and their flexibility to describe both global and local model behaviors. Concepts are groups of similarly meaningful pixels that express a notion, embedded within the network's latent space and have commonly been hand-generated, but have recently been discovered by automated approaches. Unfortunately, the magnitude and diversity of discovered concepts makes it difficult to navigate and make sense of the concept space. Visual analytics can serve a valuable role in bridging these gaps by enabling structured navigation and exploration of the concept space to provide concept-based insights of model behavior to users. To this end, we design, develop, and validate ConceptExplainer, a visual analytics system that enables people to interactively probe and explore the concept space to explain model behavior at the instance/class/global level. The system was developed via iterative prototyping to address a number of design challenges that model users face in interpreting the behavior of deep learning models. Via a rigorous user study, we validate how ConceptExplainer supports these challenges. Likewise, we conduct a series of usage scenarios to demonstrate how the system supports the interactive analysis of model behavior across a variety of tasks and explanation granularities, such as identifying concepts that are important to classification, identifying bias in training data, and understanding how concepts can be shared across diverse and seemingly dissimilar classes.

Reinforcement learning (RL) is used in many domains, including autonomous driving, robotics, stock trading, and video games. Unfortunately, the black box nature of RL agents, combined with legal and ethical considerations, makes it increasingly important that humans (including those are who not experts in RL) understand the reasoning behind the actions taken by an RL agent, particularly in safety-critical domains. To help address this challenge, we introduce PolicyExplainer, a visual analytics interface which lets the user directly query an autonomous agent. PolicyExplainer visualizes the states, policy, and expected future rewards for an agent, and supports asking and answering questions such as: “Why take this action? Why not take this other action? When is this action taken?” PolicyExplainer is designed based upon a domain analysis with RL researchers, and is evaluated via qualitative and quantitative assessments on a trio of domains: taxi navigation, a stack bot domain, and drug recommendation for HIV patients. We find that PolicyExplainer's visual approach promotes trust and understanding of agent decisions better than a state-of-the-art text-based explanation approach. Interviews with domain practitioners provide further validation for PolicyExplainer as applied to safety-critical domains. Our results help demonstrate how visualization-based approaches can be leveraged to decode the behavior of autonomous RL agents, particularly for RL non-experts.

Social decisions made by individuals are easily influenced by information from their social neighborhoods. A key predictor of social contagion is the multiplicity of social contexts inside the individual’s contact neighborhood, which is termed structural diversity. However, the existing models have limited decomposability for analyzing large-scale networks, and suffer from the inaccurate reflection of social context diversity. In this paper, we propose a truss-based structural diversity model to overcome the weak decomposability. Based on this model, we study a novel problem of truss-based structural diversity search in a graph$G$, that is, to find the$r$vertices with the highest truss-based structural diversity and return their social contexts. To tackle this problem, we propose an online structural diversity search algorithm in$O(\rho (m+\mathcal {T}))$time, where$\rho$,$m$, and$\mathcal {T}$are respectively the arboricity, the number of edges, and the number of triangles in$G$. To improve the efficiency, we design an elegant and compact index, called TSD-index, which keeps the structural diversity information for all individual vertices. We further optimize the structure of TSD-index into a highly compressed GCT-index. Our GCT-index-based structural diversity search utilizes the global triangle information for fast index construction and finds answers in$O(m)$time. Extensive experiments demonstrate the effectiveness and efficiency of our proposed model and algorithms, against state-of-the-art methods.

Structural diversity, the multiplicity of social contexts inside an individual's contact neighborhood, is shown to play an important role in the social contagion process. Existing models have limited decomposability for analyzing large-scale networks, which may suffer from the inaccurate reflection of social context diversity. In this paper, we propose a truss-based structural diversity model to address the limitations. We study the problem of top-r structural diversity search to find r vertices with the largest truss-based structural diversity scores in a graph. We propose two novel index structures of TSD-index and GCT-index, and efficient index-based query processing algorithms to solve the problem. Extensive experiments demonstrate the effectiveness and efficiency of our proposed model and algorithms, against state-of-the-art methods.

The eruption of a pandemic, such as COVID-19, can cause an unprecedented global crisis. Contact tracing, as a pillar of communicable disease control in public health for decades, has shown its effectiveness on pandemic control. Despite intensive research on contact tracing, existing schemes are vulnerable to attacks and can hardly simultaneously meet the requirements of data integrity and user privacy. The design of a privacy-preserving contact tracing framework to ensure the integrity of the tracing procedure has not been sufficiently studied and remains a challenge. In this paper, we propose P2B-Trace, a privacy-preserving contact tracing initiative based on blockchain. First, we design a decentralized architecture with blockchain to record an authenticated data structure of the user's contact records, which prevents the user from intentionally modifying his local records afterward. Second, we develop a zero-knowledge proximity verification scheme to further verify the user's proximity claim while protecting user privacy. We implement P2B-Trace and conduct experiments to evaluate the cost of privacy-preserving tracing integrity verification. The evaluation results demonstrate the effectiveness of our proposed system.

Hierarchical directed acyclic graph (HDAG) is an essential graph model to represent terminology relationships in a hierarchy, such as Disease Ontology, Gene Ontology, and Wikipedia. However, due to massive terminologies and complex structures in a HDAG, an end user might feel difficult to explore and summarize the whole graph, which is practically useful but less studied in the literature. In this demo, we develop an interactive system of HDAG-Explorer to help users summarize HDAG with highly important and diverse vertices. Our HDAG-Explorer system exhibits several useful features including summarized visualization, interactive exploration, and structural statistics report. All these features facilitate in-depth understanding of the HDAG data. We showcase the usability of the HDAG-Explorer through two real-world applications of summarized topic recommendation and visual data exploration.