Subgraph counting, which involves determining the frequency of a query graph within a data graph, has numerous applications such as query optimization, fraud detection, and evaluating the expressiveness of graph neural networks. Despite its importance, there has been no systematic study on the impact of adversarial graph perturbations on subgraph counts. In this work, we examine the kSub problem, which aims to identify k edge additions that maximize the count of a query graph. We prove that kSub is intractable due to its NP-hardness, even for constant approximation. To address this, we relax the problem into a top-k selection, termed topkSub. Depending on the structure of the relaxed query graph, we distinguish two possible processing scenarios (namely, the connected and the disconnected case), and design dedicated search space pruning strategies for each scenario. Additionally, we develop sampling techniques on the pruned search space to scale topkSub for handling large graphs. In the form of a case study, we demonstrate that topkSub effectively uncovers vulnerabilities in state-of-the-art GNN models for subgraph counting, providing a significant advantage over alternative graph perturbation methods. The efficiency analysis shows that our pruning techniques achieve substantial speedups for exact processing in both connected and disconnected cases, while our sampling methods reduce estimation errors by 1-2 orders of magnitude compared to state-of-the-art samplers.

Efficient news exploration is crucial in real-world applications, particularly within the financial sector, where numerous control and risk assessment tasks rely on the analysis of public news reports. The current processes in this domain predominantly rely on manual efforts, often involving keyword-based searches and the compilation of extensive keyword lists. In this paper, we introduce NCEXPLORER, a framework designed with OLAP-like operations to enhance the news exploration experience. NCEXPLORER empowers users to use roll-up operations for a broader content overview and drill-down operations for detailed insights. These operations are achieved through integration with external knowledge graphs (KGs), encompassing both fact-based and ontology-based structures. This integration significantly augments exploration capabilities, offering a more comprehensive and efficient approach to unveiling the underlying structures and nuances embedded in news content. Extensive empirical studies through master-qualified evaluators on Amazon Mechanical Turk demonstrate NCEXPLORER'S superiority over existing state-of-the-art news search methodologies across an array of topic domains, using real-world news datasets.

An outstanding fact (OF) is a striking claim by which some entities stand out from their peers on some attribute. OFs serve data journalism, fact checking, and recommendation. However, one could jump to conclusions by selecting truthful OFs while intentionally or inadvertently ignoring lateral contexts and data that render them less striking. This jumping conclusion bias from unstable OFs may disorient the public, including voters and consumers, raising concerns about fairness and transparency in political and business competition. It is thus ethically imperative for several stakeholders to measure the robustness of OFs with respect to lateral contexts and data. Unfortunately, a capacity for such inspection of OFs mined from knowledge graphs (KGs) is missing. In this paper, we propose a methodology that inspects the robustness of OFs in KGs by perturbation analysis. We define (1) entity perturbation, which detects outlying contexts by perturbing context entities in the OF; and (2) data perturbation, which considers plausible data that render an OF less striking. We compute the expected strikingness scores of OFs over perturbation relevance distributions and assess an OF as robust if its measured strikingness does not deviate significantly from the expected. We devise a suite of exact and sampling algorithms for perturbation analysis on large KGs. Extensive experiments reveal that our methodology accurately and efficiently detects frail OFs generated by existing mining approaches on KGs. We also show the effectiveness of our approaches through case and user studies.

Graph analytical queries (GAQs) are becoming increasingly important in various domains, including social networks, recommendation systems, and bioinformatics, among others.GAQs typically require iterative processing of the graph data to compute various metrics and identify patterns or anomalies. Parallel to the burgeoning demand for graph analytics, the need for Concurrent Graph Analytical Queries (CGAQs), allowing simultaneous execution of multiple graph queries, is increasing. Within social networks,CGAQs bolster real-time analytics, concurrently investigate various network properties, such as community detection, path analysis, and influence propagation. In transportation,CGAQs concurrently optimize multiple routes and manage real-time traffic data, contributing significantly to efficient supply chain strategies and traffic management. The key property ofCGAQs lies in their capacity for shared processing, exploiting the synergies between concurrent queries, which in return opens opportunities for improved system scalability and throughput. In this survey, we present a comprehensive review ofsystem-levelandalgorithm-levelefforts to supportCGAQprocessing. We introduce a novel survey framework based on three aspects: 1) What are the sharing opportunities exploited? 2) What are the scheduling techniques proposed to maximize sharing? 3) What are the optimizations employed? We also identify important gaps and promising research directions forCGAQprocessing.