Knowledge Graph Question Answering (KGQA) has advanced through structured query generation, yet most efforts target RDF/SPARQL, leaving Cypher and property graphs underexplored, despite increasing demand for unified KGQA in industry settings. We propose UniQGen, a novel constraint-based framework that employs LLM agents to dynamically extract and refine representative graph query clauses into executable, intent-aligned graph queries across query languages. The foundation of our method is a variant of Chase & Backchase, a family of algorithms for query optimization and reformulation. We extend Chase & Backchase with a dynamic reasoning process over query constraints that also interact with LLMs for query quality estimation. With a Cypher-supported Freebase graph deployed on Amazon Neptune, we extensively evaluate our approach on popular KGQA benchmarks (GraphQ, GrailQA, and WebQSP). We demonstrate that UniQGen outperforms state-of-the-art graph query generation techniques in both accuracy and efficiency, with F1 gains of 31.6% on GraphQ and 4.9% on GrailQA. Unlike prior methods, our framework does not require fine-tuning for schema matching, making it more extensible to schema-less graphs and semantics in query workloads, and is more suitable for enterprise-grade KGQA. We release Cypher outputs and a Neptune-ready Freebase snapshot to support reproducible, cross-language KGQA research.

Graph neural networks (GNNs) are deep learning models designed for graph-structured data that have achieved strong results across domains--social networks, knowledge graphs, bioinformatics, transportation, World Wide Web, and finance--on tasks such as node and graph classification, link prediction, entity resolution, question answering, recommendation, and fraud detection. Explaining the decisions of high-performing, yet ''black-box'' GNNs remains both challenging and essential. The initial five years have produced tremendous progress with many GNN explainers (e.g., GNNExplainer, PGExplainer, SubgraphX, PGMExplainer, GraphLime, GCFExplainer, CF2, GNN-LRP) that identify the influential nodes, edges, subgraphs, and features aiming to explain the output of GNNs.

Detecting, analyzing, and predicting power outages is crucial for grid risk assessment and disaster mitigation. Numerous outages occur each year, exacerbated by extreme weather events such as hurricanes. Existing outage data are typically reported at the county level, limiting their spatial resolution and making it difficult to capture localized patterns. However, it offers excellent temporal granularity. In contrast, nighttime light satellite image data provides significantly higher spatial resolution and enables a more comprehensive spatial depiction of outages, enhancing the accuracy of assessing the geographic extent and severity of power loss after disaster events. However, these satellite data are only available on a daily basis. Integrating spatiotemporal visual and time-series data sources into a unified knowledge representation can substantially improve power outage detection, analysis, and predictive reasoning. In this paper, we propose GeoOutageKG, a multimodal knowledge graph that integrates diverse data sources, including nighttime light satellite image data, high-resolution spatiotemporal power outage maps, and county-level timeseries outage reports in the U.S. We describe our method for constructing GeoOutageKG by aligning source data with a developed ontology, GeoOutageOnto. Currently, GeoOutageKG includes over 10.6 million individual outage records spanning from 2014 to 2024, 300,000 NTL images spanning from 2012 to 2024, and 15,000 outage maps. GeoOutageKG is a novel, modular and reusable semantic resource that enables robust multimodal data integration. We demonstrate its use through multiresolution analysis of geospatiotemporal power outages. OSF Repository: https://doi.org/10.17605/OSF.IO/QVD8B GitHub Repository: https://purl.org/geooutagekg Ontology Documentation: https://purl.org/geooutageonto

We demonstrate ExGIS , a parallel inference query engine to support explainable Graph Neural Network (GNNs) inference analysis in large graphs. (1) For a class of GNNs ℳ L with at most L layers, and a graph G , ExGIS performs an offline, once-for-all compression of G to a small graph G c , such that for any inference query Q that requests the output of any GNN M ∈ ℳ L on any node v in G, G c can be directly queried to yield correct output without decompression. (2) Given a workload W of inference queries that requests the output of GNNs from ℳ over G , ExGIS perform fast online GNN inference and interpretation in parallel. It dynamically partitions W to balance workloads, and (a) executes inference that only consults compressed graph G c without decompression, and (b) directly yields concise, explanatory subgraphs from G c that can clarify the query output with high fidelity, all in parallel. Moreover, ExGIS integrates visual, interactive interfaces for query performance analysis, and a Large Language Models (LLMs)- enabled interpreter to support user-friendly, natural language explanation of query outputs. We demonstrate the compression rate and scalability of ExGIS, and its application in interpretable anomaly detection over bitcoin transaction networks and academic networks.

Graph Neural Networks (GNNs) have demonstrated promising performance in graph analysis. Nevertheless, the inference process of GNNs remains costly, hindering their applications for large graphs. This paper proposes inference-friendly graph compression (IFGC), a graph compression scheme to accelerate GNNs inference. Given a graph G and a GNN M , an IFGC computes a small compressed graph G c , to best preserve the inference results of M over G , such that the result can be directly inferred by accessing G c with no or little decompression cost. (1) We characterize IFGC with a class of inference equivalence relation. The relation captures the node pairs in G that are not distinguishable for GNN inference. (2) We introduce three practical specifications of IFGC for representative GNNs: structural preserving compression (SPGC), which computes G c that can be directly processed by GNN inference without decompression; ( α,r )-compression, that allows for a configurable trade-off between compression ratio and inference quality, and anchored compression that preserves inference results for specific nodes of interest. For each scheme, we introduce compression and inference algorithms with guarantees of efficiency and quality of the inferred results. We conduct extensive experiments on diverse sets of large-scale graphs, which verifies the effectiveness and efficiency of our graph compression approaches.

Machine learning (ML) assets, such as models, datasets, and metadata—are central to modern ML workflows. Despite their explosive growth in practice, these assets are often underutilized due to fragmented documentation, siloed storage, inconsistent licensing, and lack of unified discovery mechanisms, making ML-asset management an urgent challenge. This tutorial offers a comprehensive overview of ML-asset management activities across its lifecycle, including curation, discovery, and utilization. We provide a categorization of ML assets, and major management issues, survey state-of-the-art techniques, and identify emerging opportunities at each stage. We further highlight system-level challenges related to scalability, lineage, and unified indexing. Through live demonstrations of systems, this tutorial equips both researchers and practitioners with actionable insights and practical tools for advancing ML-asset management in real-world and domain-specific settings.

We are developing geospatiotemporal predictive models

Spatiotemporal graph neural networks (STGNNs) have been adopted for predictive analysis in various scientific domains. Despite their promising performance, the dominance of big (geo)spatiotemporal data with large and heterogeneous dimensions raise computational challenges to effective adoption, generalization and fine-tuning of graph models. Moreover, continuous and high quality historical data may not always exist for such generalization. This paper proposes a framework that can co-evolve historical geospatial temporal datasets and an STGNN model by (1) incorporating elevation features optimized for water systems, and (2) integrating and interacting geospatial data discovery and graph learning with a "rehearsal" mechanism, that automatically generalize STGNNs to broader areas. The process divides spatiotemporal data into regional fragments with inferrable features, and iteratively (1) augment sparse training data in terms of feature similarity, (2) explore the augmented data by a trial "rehearsing" of the current model to decide a fraction of data to be adopted, over which a consistently good accuracy is observed, and (3) generalize STGNNs with promising regional data, ensured by rehearsal performance. This exploratory process hence learns to decide when and where to generalize STGNNs, for cost-effective generalization. Using real-world datasets, we experimentally verify the effectiveness and efficiency of our rehearsal framework.

Photovoltaic (PV) power stations have become an integral component to the global sustainable energy landscape. Accurately monitoring and estimating the performance of PV systems is critical to their feasibility for power generation and as a financial asset. One of the most challenging problems is to understand and estimate the long-term Performance Loss Rate (PLR) for large fleets of PV inverters. This paper introduces a novel Spatio-Temporal Graph Neural Network empowered, long-term Trend analysis system (ST-GTrend), to estimate PLR of PV systems at fleet-level. ST-GTrend nontrivially integrates spatio-temporal coherence and graph attention to separate PLR as a long-term 'aging' trend from multiple fluctuation terms in the PV input data, with a design that can easily scale to large PV sets with effective, multi-level parallel computation. (1) To cope with diverse degradation patterns in timeseries, ST-GTrend adopts a paralleled graph autoencoder array to extract aging and fluctuation terms simultaneously, and imposes flatness and smoothness regularizations to disentangle between aging and fluctuation. (2) For large PV systems, ST-GTrend enables a multi-level parallelization paradigm to scale the training and inference computation with a provable performance guarantee. ST-GTrend has been deployed in CRADLE, a scientific high performance computing infrastructure. We evaluated ST-GTrend with three real-world large-scale PV datasets, spanning a time period of 10 years. Our results show that ST-GTrend reduces MAPE and Euclidean distance-based errors on average by 34.74% and 33.66% of SOTA methods, and scales well to large PV sets. We also showcase that the advantages of ST-GTrend generalize for the need of long-term trend analysis in financial and economic data.

Knowledge graphs (KGs) are routinely curated to provide factual data for various domain-specific analyses. Nevertheless, it remains nontrivial to explore domain knowledge with standard query languages. We demonstrate GraphLingo, a natural language (NL)-based knowledge exploration system designed for exploring domain-specific knowledge graphs. It differs from conventional knowledge graph search tools in that it enables an interactive exploratory NL query over domain-specific knowledge graphs. GraphLingo seamlessly integrates graph query processing and large language models with a graph pattern-based prompt generation approach to guide users in exploring relevant factual knowledge. It streamlines NL-based question & answer, graph query optimization & refining, and automatic prompt generation. A unique feature of GraphLingo is its capability to enable users to explore by seamlessly switching between a more ‘open’ approach and a more relevant yet ‘conservative’ one, facilitated by diversified query suggestions. We show cases of GraphLingo in curriculum suggestion, and materials scientific data search.

This paper introduces a new class of explanation structures, called robust counterfactual witnesses (RCWs), to provide robust, both counterfactual and factual explanations for graph neural networks. Given a graph neural network$\mathcal{M}$, a robust counterfactual witness refers to the fraction of a graph$G$that are counterfactual and factual explanation of the results of$\mathcal{M}$over$G$, but also remains so for any “disturbed”$G$by flipping up to$k$of its node pairs. We establish the hardness results, from tractable results to co-NP-hardness, for verifying and generating robust counterfactual witnesses. We study such structures for GNN-based node classification, and present efficient algorithms to verify and generate RCWs. We also provide a parallel algorithm to verify and generate RCWs for large graphs with scalability guarantees. We experimentally verify our explanation generation process for benchmark datasets, and showcase their applications.

Generating explanations for graph neural networks (GNNs) has been studied to understand their behaviors in analytical tasks such as graph classification. Existing approaches aim to understand the overall results of GNNs rather than providing explanations for specific class labels of interest, and may return explanation structures that are hard to access, nor directly queryable. We propose GVEX, a novel paradigm that generates Graph Views for GNN EXplanation. (1) We design a two-tier explanation structure called explanation views. An explanation view consists of a set of graph patterns and a set of induced explanation subgraphs. Given a database G of multiple graphs and a specific class label l assigned by a GNN-based classifier M, it concisely describes the fraction of G that best explains why l is assigned by M. (2) We propose quality measures and formulate an optimization problem to compute optimal explanation views for GNN explanation. We show that the problem is Σ2P-hard. (3) We present two algorithms. The first one follows an explain-and-summarize strategy that first generates high-quality explanation subgraphs which best explain GNNs in terms of feature influence maximization, and then performs a summarization step to generate patterns. We show that this strategy provides an approximation ratio of 1/2. Our second algorithm performs a single-pass to an input node stream in batches to incrementally maintain explanation views, having an anytime quality guarantee of 1/4-approximation. Using real-world benchmark data, we experimentally demonstrate the effectiveness, efficiency, and scalability of GVEX. Through case studies, we showcase the practical applications of GVEX.

We demonstrate ModsNet , a search tool for pre-trained data science MOD el s recommendatio N using E xamplar da T aset. Given a set of pre-trained data science models, an "example" input dataset, and a user-specified performance metric, ModsNet answers the following query: "what are top-k models that have the best expected performance for the input data?" The need for searching high-quality pre-trained models is evident in data-driven analysis. Inspired by "query by example" paradigm, ModsNet does not require users to write complex queries, but only provide an "examplar" dataset, a task description, and a performance measure as input, and can automatically suggest top- k matching models that are expected to have desirable performance to perform the task over the provided sample dataset. ModsNet utilizes a knowledge graph to integrate model performances over datasets and synchronizes it with a bipartite graph neural network to estimate model performance, reduce inference cost, and promptly respond to top- k model search queries. To cope with strict cold-start (upon receiving a new dataset when no historical performance of registered models are observed), it performs a dynamic, cost-bounded "probe-and-select" strategy to incrementally identify promising models. We demonstrate the application of ModsNet in enabling efficient scientific data analysis.

In this study, we conduct a detailed evaluation of machine learning and multimodal learning approaches in two distinct areas: a standard medical imaging benchmark and a novel material sciences benchmark. We utilize the CheXpert chest x-ray dataset for medical imaging and introduce a newly created Fluoropolymer Atomic Force Microscopy (AFM) dataset for material sciences. Both datasets are enhanced with additional images and binary metadata, encoded as one-hot vectors. We tested both pretrained and non-pretrained Convolutional Neural Network (CNN) models, such as ResNet50, ResNet101, DenseNet121, InceptionV3, and Xception, across different combinations of image and metadata inputs. Our results reveal that integrating multimodal data, including simple binary metadata, significantly enhances classification accuracy compared to conventional unimodal approaches or advanced MADDi models. This indicates the efficacy of multimodal learning in enriching data representation and boosting image classification performance. Notably, Xception models showed exceptional performance in CheXpert tests, and most models improved crystal structure predictions in AFM datasets. These insights set a new benchmark for performance and underscore the potential of multimodal learning in data-intensive applied science research.

Data analytical pipelines routinely involve various domain-specific data science models. Such models require expensive manual or training effort and often incur expensive validation costs (e.g., via scientific simulation analysis). Meanwhile, high-value models remain to be ad-hocly created, isolated, and underutilized for a broad community. Searching and accessing proper models for data analysis pipelines is desirable yet challenging for users without domain knowledge. This paper introduces ModsNet, a novel MODel SelectioN framework that only requires an Example daTaset. (1) We investigate the following problem: Given a library of pre-trained models, a limited amount of historical observations of their performance, and an "example" dataset as a query, return k models that are expected to perform the best over the query dataset. (2) We formulate a regression problem and introduce a knowledge-enhanced framework using a model-data interaction graph. Unlike traditional methods, (1) ModsNet uses a dynamic, cost-bounded "probe-and-select" strategy to incrementally identify promising pre-trained models in a strict cold-start scenario (when a new dataset without any interaction with existing models is given). (2) To reduce the learning cost, we develop a clustering-based sparsification strategy to prune unpromising models and their interactions. (3) We showcase of ModsNet built on top of a crowdsourced materials knowledge base platform. Our experiments verified its effectiveness, efficiency, and applications over real-world analytical pipelines.

We introduce GALE, an active adversarial learning framework to detect nodes with erroneous information in attributed graphs. GALE is empowered by a new adversarial active error detection framework, which interacts active learning with a graph generative adversarial model to best exploit limited labeled examples of erroneous nodes. It dynamically determines diversified query nodes in batches with bounded size in terms of node typicality to enrich a pool of examples, which in turn provides representative examples to best train an adversarial classifier to capture different types of errors. Moreover, GALE provides an annotation algorithm to suggest a context of possible correct attribute values and error types, to facilitate the labeling of query nodes. We show that using limited queries and examples, GALE significantly improves competing methods such as constraint-based detection, outlier detection, and Graph Neural Networks (e.g. GCNs), with 32%, 31%, and 17% gain in F-1 score on average, and is feasible in learning cost for large graphs.

Data dependencies have been extended to graphs to characterize topological and value constraints. Existing data dependencies are defined to capture inconsistencies in static graphs. Nevertheless, inconsistencies may occur over evolving graphs and only for certain time periods. The need for capturing such inconsistencies in temporal graphs is evident in anomaly detection and predictive dynamic network analysis. This paper introduces a class of data dependencies called Temporal Graph Functional Dependencies (TGFDs). TGFDs generalize functional dependencies to temporal graphs as a sequence of graph snapshots that are induced by time intervals, and enforce both topological constraints and attribute value dependencies that must be satisfied by these snapshots. (1) We establish the complexity results for the satisfiability and implication problems of TGFDs. (2) We propose a sound and complete axiomatization system for TGFDs. (3) We also present efficient parallel algorithms to detect inconsistencies in temporal graphs as violations of TGFDs. The algorithm exploits data and temporal locality induced by time intervals, and uses incremental pattern matching and load balancing strategies to enable feasible error detection in large temporal graphs. Using real datasets, we experimentally verify that our algorithms achieve lower runtimes compared to existing baselines, while improving the accuracy over error detection using existing graph data constraints, e.g., GFDs and GTARs with 55% and 74% gain in F1-score, respectively.

Given a set of node groups in a graph (e.g., gender or race groups), how to succinctly summarize their neighbors, and meanwhile ensure a "fair" representation to mitigate under- or over-representation of a certain group? We propose a novel framework to compute concise summaries of node groups with fairness guarantees. (1) We introduce a pattern-correction structure called r-summaries. An r-summary uses a graph pattern set to specify representative nodes and an auxiliary edge correction set to losslessly describe their r-hop neighbors. (2) We formulate the fair group summarization problem, which is to compute an r-summary that can select and accurately describe high quality nodes and their neighbors with small edge corrections, and meanwhile guarantee a desirable coverage for each group. The need for generating such summaries is evident in social recommendation, healthcare and graph search. We show that the problem is $\Sigma _2^p$-complete with the verification problem already NP-complete. (3) We present approximation algorithms that can generate r-summaries with (a) guaranteed quality and coverage properties, and (b) relative approximations on optimal edge correction costs. For large groups, we introduce an efficient algorithm that interleaves node selection and localized pattern discovery to reduce unnecessary computation. In addition, we introduce an algorithm to incrementally maintain the r-summaries over dynamic graphs with evolving edges. Using real-world data, we experimentally verify the efficiency and effectiveness of our algorithms and verify their applications.

The integration of the global Photovoltaic (PV) market with real time data-loggers has enabled large scale PV data analytical pipelines for power forecasting and reliability assessment of PV fleets. Nevertheless, the performance of PV data analysis depends on the quality of PV timeseries data. We propose a novel Spatio-Temporal Denoising Graph Autoencoder STD-GAE framework to impute missing PV Power Data. STD-GAE exploits temporal correlation, spatial coherence, and value dependencies from domain knowledge to recover missing data. It is empowered by two modules. (1) To cope with sparse yet various scenarios of missing data, STD-GAE incorporates a domain-knowledge aware data augmentation module to create plausible variations of missing data patterns. This generalizes STD-GAE to robust imputation over different seasons and environment. (2) STD-GAE nontrivially integrates spatiotemporal graph convolution layers and denoising autoencoder to improve the accuracy of imputation accuracy at PV fleet level. Experimental results on two PV datasets show that STD-GAE can achieve a gain of 43.14% in imputation accuracy and remains less sensitive to missing rate, different seasons, and missing scenarios, compared with state-of-the-art data imputation methods.

Using big data, distributed computing systems such as Apache Hadoop requires processing massive amount of data to support business and research applications. Thus, it is critical to ensure the cyber security of such systems. To better defend from advanced cyber attacks that pose threats to even well-protected enterprises, system-auditing based techniques have been adopted for monitoring system activities and assisting attack investigation. In this demo, we are building a system that collects system auditing logs from a big data system and performs data analysis to understand how system auditing can be used more effectively to assist attack investigation on big systems. We also built a demo application that detects unexpected file deletion and presents root causes for the deletion.

Modern multidisciplinary materials science routinely processes scientific workflows that integrate different data resources (e.g., X-ray data, scripts, analytical results). Most of such data resources are isolated in research labs, created ad-hocly, and remain underutilized. We demonstrate CRUX, a Crowdsourced platform for materials data ResoUrces and workflow eXploration. CRUX is empowered by coherent data-workflow modeling, knowledge-based resource assembly for workflow search, and data provenance to support workflow exploration. CRUX allows users to declare parameterized workflows as graph patterns, and automatically recommends crowdsourced resources with quality guarantees. We demonstrate the ease-of-use and the performance of CRUX with three categories of queries: data search, workflow recommendation, and resource exploration. We make case of CRUX for peak finding in X-ray Diffraction (XRD) data, a cornerstone task in materials research. We show that CRUX enables new interactive paradigms to explore and design workflows for data analysts in general.

This paper studies the problem of subgraph query generation with guarantees on both diversity and group fairness. Given a query template (with parameterized search predicates) and a set of node groups in a graph, it is to compute a set of sub-graph queries that instantiate the query template, and each query ensures diversified answers that meanwhile covers each group with a desired number of nodes. Such need is evident in web and social search with fairness constraints, query optimization, and query benchmarking. We formalize a bi-criteria optimization problem that aims to find a Pareto optimal set of query instances in terms of diversity and fairness measures. We show the problem is in Δ$P$2 and verify its hardness (NP-hard and fixed-parameter tractable). We provide (1) two efficient algorithms that can approximate Pareto optimal sets with E-dominance relations that yield representative query instances with a bounded size, and (2) an online algorithm that progressively generates and maintains fixed-size ∊-Pareto set with small delay time. We experimentally verify that our algorithms can efficiently generate queries with desired diversity and coverage properties for targeted groups.

This paper investigates the problem of subgraph query generation with output that satisfies both diversity and fairness constraints. Given a set of groups with associated cardinality requirements, it is to compute subgraph queries with diversified output that meanwhile covers the groups with the desired cardinality. Such need is evident in web and social search with fairness constraints. We formalize subgraph query generation as a bi-criteria optimization problem on the diversity and fairness properties of queries, and verify its hardness and approximability. We show that the problem is in Σp2 , and remains NP-complete even for single-node queries. Despite the hardness, (1) we show that approximations exist whenever a corresponding subset selection process provides good solutions, and provide feasible algorithms with performance guarantees for two practical query generation scenarios. We also present a fast heuristic algorithm for the general problem, which early terminates without enumerating queries. We experimentally verify that our algorithms can efficiently generate queries with desired diversity and coverage properties for targeted groups.

One important problem that is insufficiently studied is finding densest lasting subgraphs in large dynamic graphs, which considers the time duration of the subgraph pattern. We propose a framework called Expectation-Maximization with Utility functions (EMU), a novel stochastic approach that nontrivially extends the conventional EM approach. EMU has the flexibility of optimizing any user-defined utility functions. We validate our EMU approach by showing that it converges to the optimum---by proving that it is a specification of the general Minorization-Maximization (MM) framework with convergence guarantees. We devise EMU algorithms for the densest lasting subgraph problem, as well as several variants by varying the utility function. Using real-world data, we evaluate the effectiveness and efficiency of our techniques, and compare them with two prior approaches on dense subgraph detection.

Subgraph queries are routinely used to search for entities in richly attributed graphs e.g., social networks and knowledge graphs. With little knowledge of underlying data, users often need to rewrite queries multiple times to reach desirable answers. Why-questions are studied to clarify missing or unexpected query results. This paper makes a first step to answer Why-questions for entity search in attributed graphs. We consider three common types of Why-questions: Why-not, Why, and Why-rank, which suggest query manipulations that are responsible for user-specified missing, unexpected, and undesirably ranked entities, respectively. (1) We approach a general query rewriting paradigm that suggests to identify desired entities that are specified by Why-questions. We introduce measures that characterize good query rewrites by incorporating both query editing cost and answer closeness. (2) While computing optimal query rewrites is intractable, we develop feasible algorithms, from approximation to fast heuristics, and provide query rewrites with (near) optimality guarantees whenever possible, for Why, Why-not and Why-rank questions. We further show that our results remain intact for Why questions that (1) request a single query rewrite to clarify multiple types of entities, and (2) variants such as Why-empty and Why-so-many, by providing the matching algorithms. Using real-world graphs, we experimentally verify that our algorithms are effective and feasible for large graphs. Our case study also verifies their application in e.g., knowledge exploration.

This paper introduces a constraint-based approach to clarify missing values in graphs. Our method capitalizes on a set Σ of graph data constraints. An explanation is a sequence of operational enforcement of Σ towards the recovery of interested yet missing data (e.g., attribute values, edges). We show that constraint-based approach helps us to understand not only why a value is missing, but also how to recover the missing value. We study Σ-explanation problem, which is to compute the optimal explanations with guarantees on the informativeness and conciseness. We show the problem is in Δ2Pfor established graph data constraints such as graph keys and graph association rules. We develop an efficient bidirectional algorithm to compute optimal explanations, without enforcing Σ on the entire graph. We also show our algorithm can be easily extended to support graph refinement within limited time, and to explain missing answers. Using real-world graphs, we experimentally verify the effectiveness and efficiency of our algorithms.

Detecting nodes with erroneous values in real-world graphs remains challenging due to the lack of examples and various error scenarios. We demonstrate GEDet, an error detection engine that can detect erroneous nodes in graphs with a few examples. The GEDet framework tackles error detection as a few-shot node classification problem. We invite the attendees to experience the following unique features. (1) Few-shot detection . Users only need to provide a few examples of erroneous nodes to perform error detection with GEDet. GEDet achieves desirable accuracy with (a) a graph augmentation module, which automatically generates synthetic examples to learn the classifier, and (b) an adversarial detection module, which improves classifiers to better distinguish erroneous nodes from both cleaned nodes and synthetic examples. We show that GEDet significantly improves the state-of-the-art error detection methods. (2) Diverse error scenarios . GEDet profiles data errors with a built-in library of transformation functions from correct values to errors. Users can also easily "plug in" new error types or examples. (3) User-centric detection . GEDet supports (a) an active learning mode to engage users to verify detected results, and adapts the error detection process accordingly; and (b) visual interfaces to interpret and track detected errors.

Detecting nodes with erroneous information in graphs is important yet challenging, due to the lack of examples and the diversified s cenarios o f e rrors. W e i ntroduce GEDet, a few-shot learning based framework to detect erroneous nodes in graphs. GEDet consists of two novel components, each addresses a unique challenge. (1) To cope with the lack of examples, we introduce a graph augmentation module to enrich training labels. The module not only generates additional synthetic training labels by simulating different erroneous scenarios, but also exploits non-local relations to enrich neighborhood information. (2) To further improve the accuracy, we introduce an adversarially learned module that can better detect erroneous nodes by distinguishing nodes with synthetic and real labels encoded by graph autoencoders. Unlike conventional error detection models, GEDet yields effective classifiers that are optimized for a few yet diversified examples in the presence of multiple error scenarios. We show that using only a small number of examples, GEDet significantly improves the competing methods such as constraint-based detection and anomaly detection, with a gain of 35% on recall, and 30% on precision.

This paper studies a class of neighborhood con-straints to characterize and repair erroneous entity information in multi-relational graph data. (1) We propose a class of constraints called star functional dependencies (StarFDs). Unlike conventional integrity constraints, a StarFDenforces value dependencies conditioned by entities and their relevant neighbors, which are identified by a star pattern that incorporates conjunctive regular path queries. StarFDsachieve a balance between expressiveness and complexity: the validation of StarFDsis tractable, and the satisfiability and implication of StarFDsare NP-complete and coNP-complete, respectively. (2) Given a set of StarFDsΣ and a graph G, the entity repair problem is to compute a minimum repair of G by enforcing Σ with the smallest amount of changes. Although this problem is NP-complete and hard to approximate, we show it is feasible to compute repairs in large graphs. Our approach (a) discriminately detects and resolves errors with optimal, approximable and cost-bounded solutions whenever possible, and (b) incurs a time cost determined by Σ and the size of inconsistencies, for all cases. Using real world data, we show that StarFD-based techniques effectively identify and repair errors. We also show that our repairing algorithms benefit other tasks such as fact checking.

We demonstrate Kronos, a framework and system that automatically extracts highly dynamic knowledge for complex event analysis in Cyber-Physical systems. Kronos captures events with anomaly-based event model, and integrates various events by correlating with their temporal associations in realtime, from heterogeneous, continuous cyber-physical measurement data streams. It maintains a lightweight highly dynamic knowledge base, enabled by online, window-based ensemble learning and incremental association analysis for event detection and linkage, respectively. These algorithms incur time costs determined by available memory, independent of the size of streams. Exploiting the highly dynamic knowledge, Kronos supports a rich set of stream event analytical queries including event search (keywords and query-by-example), provenance queries ("which measurements or features are responsible for detected events?"), and root cause analysis. We demonstrate how the GUI of Kronos interacts with users to support both continuous and ad-hoc queries online and enables situational awareness in Cyber-power systems, communication, and traffic networks.

There has recently been a lot of ongoing research in the areas of fairness, bias and explainability of machine learning (ML) models due to the self-evident or regulatory requirements of various ML applications. We make the following observation: All of these approaches require a robust understanding of the relationship between ML models and the data used to train them. In this work, we introduce the ML provenance tracking problem: the fundamental idea is to automatically track which columns in a dataset have been used to derive the features/labels of an ML model. We discuss the challenges in capturing such information in the context of Python, the most common language used by data scientists.

One important problem that is insufficiently studied is finding densest lasting-subgraphs in large dynamic graphs, which considers the time duration of the subgraph pattern. We propose a framework called Expectation-Maximization with Utility functions (EMU), a novel stochastic approach that nontrivially extends the conventional EM approach. EMU has the flexibility of optimizing any user-defined utility functions. We validate our EMU approach by showing that it converges to the optimum-by proving that it is a specification of the general Minorization-Maximization (MM) framework with convergence guarantees. We then devise EMU algorithms for the densest lasting subgraph problem. Using real-world graph data, we experimentally verify the effectiveness and efficiency of our techniques, and compare with two prior approaches on dense subgraph detection.

Subgraph queries have been routinely used to search graphs e.g., social networks and knowledge bases. With little knowledge of underlying data, users often need to rewrite queries multiple times to reach desirable answers. Why-questions are studied to explain missing (as “Why-not” questions) or unexpected answers (as “Why” questions). This paper makes a first step to answer why-questions for subgraph queries in attributed graphs. (1) We approach query rewriting and construct query rewrites, which modify original subgraph queries to identify desired entities that are specified by Why questions. We introduce measures that characterize good query rewrites by incorporating both query editing cost and answer closeness. (2) While computing optimal query rewrite is intractable for Why-questions, we develop feasible algorithms, from exact algorithms to heuristics, and provide query rewrites with (near) optimality guarantees whenever possible, for both Why and Why-not questions. These algorithms dynamically select “picky” operators that ensure to change (estimated) answers closer to desired ones, and incur cost determined by the size of query results and questions only. We also show that these algorithms readily extend to other Why-questions such as Why-empty and Why-so-many. Using real-world graphs, we experimentally verify that our algorithms are effective and feasible for large graphs. Our case study also verifies their application in e.g., knowledge exploration.

Backbones refer to critical tree structures that span a set of nodes of interests in networks. This paper introduces a novel class of attributed backbones and detection algorithms in richly attributed networks. Unlike conventional models, attributed backbones capture dynamics in edge cost model: it specifies affinitive attributes for each edge, and the cost of each edge is dynamically determined by the selection of its associated affinitive attributes and the closeness of their values at its end nodes. The backbone discovery is to compute an attributed backbone that covers interested nodes with smallest connection cost dynamically determined by selected affinitive attributes. While this problem is hard to approximate, we develop feasible algorithms within practical reach for large attributed networks. (1) We show that this problem is fixed-parameter approximable parameterized by the number of affinitive attributes, by providing a Lagrangean-preserving 2-approximation. (2) When the attribute number is large and specifying closeness function is difficult, we provide a fast heuristic, which learns an edge-generative model, and applies the model to infer best backbones, without the need of specifying closeness functions. Using real-world networks, we verify the effectiveness and efficiency of our algorithms and show their applications in collaboration recommendation.

We demonstrate NAVIGATE, an explai\underlineNA ble query engine for \underlineVI sual \underlineG r\underlineA ph explora\underlineT ion by \underlineE xamples. NAVIGATE interleavesquery rewriting and query answering to help users (1) search graphs \textslwithout writing complex queries, and (2) understand answers by providing intuitive explanations. Users can visually construct queries and specify missing or unwanted example entities to guide the exploration towards desired answers. NAVIGATE can rewrite queries with answers close to examples, by minimally altering their topological and semantic constraints. Another unique feature is its ability to explain query results by tracing the query manipulation operators that are responsible for transforming the original answers to desirable ones. In addition, NAVIGATE optimizes system response time by referring to dynamically cachedstar views to reduce both query evaluation and rewriting cost at run time. We also demonstrate its ease-of-use, efficiency, and explainable exploration in applications such as recommendation and knowledge base search.

This paper studies the problem of \em answering Why-questions for graph pattern queries. Given a query Q, its answers $Q(G)$ in a graph G, and an exemplar $\E$ that describes desired answers, it aims to compute a query rewrite $Q'$, such that $Q'(G)$ incorporates relevant entities and excludes irrelevant ones wrt $\E$ under a closeness measure. (1) We characterize the problem by \em Q-Chase. It rewrites Q by applying a sequence of applicable operators guided by $\E$, and backtracks to derive optimal query rewrite. (2) We develop feasible Q-Chase-based algorithms, from anytime solutions to fixed-parameter approximations to compute query rewrites. These algorithms implement Q-Chase by detecting picky operators at run time, which discriminately enforce $\E$ to retain answers that are closer to exemplars, and effectively prune both operators and irrelevant matches, by consulting a cache of star patterns (called \em star views ). Using real-world graphs, we experimentally verify the efficiency and effectiveness of \qchase techniques and their applications.

Keys for graphs incorporate the topology and value constraints needed to uniquely identify entities in a graph. They have been studied to support object identification, knowledge fusion, and social network reconciliation. Existing key constraints identify entities as the matches of a graph pattern by subgraph isomorphism, which enforce label equality on node types. These constraints can be too restrictive to characterize structures and node labels that are syntactically different but semantically equivalent. We propose a new class of key constraints, Ontological Graph Keys (OGKs) that extend conventional graph keys by ontological subgraph matching between entity labels and an external ontology. We show that the implication and validation problems for OGKs are each NP-complete. To reduce the entity matching cost, we also provide an algorithm to compute a minimal cover for OGKs. We then study the entity matching problem with OGKs, and a practical variant with a budget on the matching cost. We develop efficient algorithms to perform entity matching based on a (budgeted) Chase procedure. Using real-world graphs, we experimentally verify the efficiency and accuracy of OGK-based entity matching.

Node ranking in temporal networks are often impacted by heterogeneous context from node content, temporal, and structural dimensions. This paper introduces TGNet , a deep learning framework for node ranking in heterogeneous temporal graphs. TGNet utilizes a variant of Recurrent Neural Network to adapt context evolution and extract context features for nodes. It incorporates a novel influence network to dynamically estimate temporal and structural influence among nodes over time. To cope with label sparsity, it integrates graph smoothness constraints as a weak form of supervision. We show that the application of TGNet is feasible for large-scale networks by developing efficient learning and inference algorithms with optimization techniques. Using real-life data, we experimentally verify the effectiveness and efficiency of TGNet techniques. We also show that TGNet yields intuitive explanations for applications such as alert detection and academic impact ranking, as verified by our case study.

We demonstrate GExp, an interactive graph exploration tool that uses keywords to support effective access and exploration of large graphs. GExp interleaves keyword query suggestion, which generates keyword queries that expand the original query, and query evaluation, that returns the answers to suggested queries for feedback. It advocates (1) cost-aware exploration, which suggests keyword queries that have low answer cost (thus high answer quality), and (2) incremental query evaluation to update the query answers with a bounded time cost. It differs from prior systems in its ability to identify and leverage substructures that augment original answers for query expansion and evaluation with provable cost bounds. A unique feature of GExp is that users can trade the quality of query answers with their evaluation cost by tuning the bound of answer cost in an ad-hoc manner. We demonstrate how GExp supports graph exploratory with three established keyword query classes with bounded time cost, and guarantees on result quality, using real-world knowledge bases and information networks.

We demonstrate \perco, a distributed system for graph pattern discovery in dynamic graphs. In contrast to conventional mining systems, Percolator advocates efficient pattern mining schemes that (1) support pattern detection with keywords; (2) integrate incremental and parallel pattern mining; and (3) support analytical queries such as trend analysis. The core idea of \perco is to dynamically decide and verify a small fraction of patterns and their instances that must be inspected in response to buffered updates in dynamic graphs, with a total mining cost independent of graph size. We demonstrate a( the feasibility of incremental pattern mining by walking through each component of \perco, b) the efficiency and scalability of \perco over the sheer size of real-world dynamic graphs, and c) how the user-friendly \gui of \perco interacts with users to support keyword-based queries that detect, browse and inspect trending patterns. We demonstrate how \perco effectively supports event and trend analysis in social media streams and research publication, respectively.

Given a knowledge graph and a fact (a triple statement), fact checking is to decide whether the fact belongs to the missing part of the graph. Facts in real-world knowledge bases are typically interpreted by both topological and semantic context that is not fully exploited by existing methods. This paper introduces a novel fact checking method that explicitly exploits discriminant subgraph structures. Our method discovers discriminant subgraphs associated with a set of training facts, characterized by a class of graph fact checking rules. These rules incorporate expressive subgraph patterns to jointly describe both topological and ontological constraints. (1) We extend graph fact checking rules ( $${\mathsf{GFCs}}$$ ) to a class of ontological graph fact checking rules ( $${\mathsf{OGFCs}}$$ ). $${\mathsf{OGFCs}}$$ generalize $${\mathsf{GFCs}}$$ by incorporating both topological constraints and ontological closeness to best distinguish between true and false fact statements. We provide quality measures to characterize useful patterns that are both discriminant and diversified. (2) Despite the increased expressiveness, we show that it is feasible to discover $${\mathsf{OGFCs}}$$ in large graphs with ontologies, by developing a supervised pattern discovery algorithm. To find useful $${\mathsf{OGFCs}}$$ as early as possible, it generates subgraph patterns relevant to training facts and dynamically selects patterns from a pattern stream with a small update cost per pattern. We verify that $${\mathsf{OGFCs}}$$ can be used as rules and provide useful features for other statistical learning-based fact checking models. Using real-world knowledge bases, we experimentally verify the efficiency and the effectiveness of $${\mathsf{OGFC}}$$ -based techniques for fact checking.

Querying heterogeneous and large-scale knowledge graphs is expensive. This paper studies a graph summarization framework to facilitate knowledge graph search. (1) We introduce a class of reduced summaries. Characterized by approximate graph pattern matching, these summaries are capable of summarizing entities in terms of their neighborhood similarity up to a certain hop, using small and informative graph patterns. (2) We study a diversified graph summarization problem. Given a knowledge graph, it is to discover top-k summaries that maximize a bi-criteria function, characterized by both informativeness and diversity. We show that diversified summarization is feasible for large graphs, by developing both sequential and parallel summarization algorithms. (a) We show that there exists a 2-approximation algorithm to discover diversified summaries. We further develop an anytime sequential algorithm which discovers summaries under resource constraints. (b) We present a new parallel algorithm with quality guarantees. The algorithm is parallel scalable, which ensures its feasibility in distributed graphs. (3) We also develop a summary-based query evaluation scheme, which only refers to a small number of summaries. Using real-world knowledge graphs, we experimentally verify the effectiveness and efficiency of our summarization algorithms, and query processing using summaries.

Given an evolving network and a set of user-specified keywords, how to discover and maintain the active events specified by the keywords? In this paper, we study the problem of event pattern discovery by keywords in graph streams. (1) We propose a class of event patterns to capture events relevant to user-specified keywords, by integrating (approximate) topological and value bindings from keywords. We also introduce an activeness measure, to balance the pattern expressiveness and the cost of pattern discovery. (2) We develop both from-scratch and incremental algorithms to discover and maintain active events in graph streams. Using real-world graph streams, we experimentally verify the effectiveness of the event pattern model and the efficiency of our from-scratch and incremental algorithms.

Detecting regularities between complex events in temporal graphs is critical for emerging applications. This paper proposes graph temporal association rules (GTAR). A GTAR extends traditional association rules to discover temporal associations for complex events captured by a class of temporal pattern queries. We introduce notions of support and confidence for GTARS and formalize the discovery problem for GTARS. We show that despite the enhanced expressive power, GTARS discovery is feasible over large temporal graphs. We develop an effective rule discovery algorithm, which integrates event mining and rule discovery as a single process, and reduces the redundant computation by leveraging their interaction. Using real-life and synthetic data, we experimentally verify the effectiveness and scalability of the algorithms. Our case study also verifies that GTARS demonstrate highly interpretable associations in real-world networks.

This demo presents BEAMS, a system that automatically discovers and monitors top-k complex events over graph streams. Unlike conventional event detection over streams of items, BEAMS is able to (1) characterize and detect complex events in dynamic networks as graph patterns, and (2) perform online event discovery with a class of bounded algorithms that compute changes to top-k events in response to the transactions in graph streams, and incurs a minimized time cost determined by the changes, independent of the size of graph streams. We demonstrate: a) how BEAMS identifies top-k complex events as graph patterns in graph streams, and supports ad-hoc event queries online, b) how it copes with the sheer size of real-world graph streams with bounded event detection algorithm, and c) how the GUI of BEAMS interacts with users to support adhoc event queries that detect, browse and inspect trending events. Video: https://youtu.be/lVUGM0Fa17Q.

This paper presents GRAPE, a parallel system for graph computations. GRAPE differs from prior systems in its ability to parallelize existing sequential graph algorithms as a whole. Underlying GRAPE are a simple programming model and a principled approach, based on partial evaluation and incremental computation. We show that sequential graph algorithms can be "plugged into" GRAPE with minor changes, and get parallelized. As long as the sequential algorithms are correct, their GRAPE parallelization guarantees to terminate with correct answers under a monotonic condition. Moreover, we show that algorithms in MapReduce, BSP and PRAM can be optimally simulated on GRAPE. In addition to the ease of programming, we experimentally verify that GRAPE achieves comparable performance to the state-of-the-art graph systems, using real-life and synthetic graphs.

We demonstrate GRAPE, a parallel GRAPh query Engine. GRAPE advocates a parallel model based on a simultaneous fixed point computation in terms of partial and incremental evaluation. It differs from prior systems in its ability to parallelize existing sequential graph algorithms as a whole, without the need for recasting the entire algorithms into a new model. One of its unique features is that under a monotonic condition, GRAPE parallelization guarantees to terminate with correct answers as long as the sequential algorithms "plugged in" are correct. We demonstrate its parallel computations, ease-of-use and performance compared with the start-of-the-art graph systems. We also demonstrate a use case of GRAPE in social media marketing.

Given a graph query Q posed on a knowledge graph G, top-k graph querying is to find k matches in G with the highest ranking score according to a ranking function. Fast top-k search in knowledge graphs is challenging as both graph traversal and similarity search are expensive. Conventional top-k graph search is typically based on threshold algorithm (TA), which can no long fit the demand in the new setting. This work proposes STAR, a top-k knowledge graph search framework. It has two components: (a) a fast top-k algorithm for star queries, and (b) an assembling algorithm for general graph queries. The assembling algorithm uses star query as a building block and iteratively sweeps the star match lists with a dynamically adjusted bound. For top-k star graph query where an edge can be matched to a path with bounded length d, we develop a message passing algorithm, achieving time complexity O(d2|E| + md) and space complexity linear to d|V| (assuming the size of Q and k is bounded by a constant), where m is the maximum node degree in G. STAR can further be leveraged to answer general graph queries by decomposing a query to multiple star queries and joining their results later. Learning-based techniques to optimize query decomposition are also developed. We experimentally verify that STAR is 5-10 times faster than the state-of-the-art TA-style graph search algorithm, and 10-100 times faster than a belief propagation approach.

Mining and searching heterogeneous and large knowledge graphs is challenging under real-world resource constraints such as response time. This paper studies a framework that discover to facilitate knowledge graph search. 1) We introduce a class of summaries characterized by graph patterns. In contrast to conventional summaries defined by frequent subgraphs, the summaries are capable of adaptively summarize entities with similar neighbors up to a bounded hop. 2) We formulate the computation of graph summarization as a bi-criteria pattern mining problem. Given a knowledge graph G, the problem is to discover k diversified summaries that maximizes the informativeness measure. Although this problem is NP-hard, we show that it is 2-approximable. We also introduce an online mining algorithm that trade-off speed and accuracy, under given resource constraints. 3) We develop query evaluation algorithms that make use of the summaries as views. These algorithms efficiently compute (approximate) answers with high accuracy, and only refer to a small number of summaries. Our experimental study verifies that online mining over large knowledge graphs is feasible, and can suggest bounded search in knowledge graphs.

This paper proposes quantified graph patterns (QGPs), an extension of graph patterns by supporting simple counting quantifiers on edges. We show that QGPs naturally express universal and existential quantification, numeric and ratio aggregates, as well as negation. Better still, the increased expressivity does not come with a much higher price. We show that quantified matching, i.e., graph pattern matching with QGPs, remains NP-complete in the absence of negation, and is DP-complete for general QGPs. We show how quantified matching can be conducted by incorporating quantifier checking into conventional subgraph isomorphism methods. We also develop parallel scalable algorithms for quantified matching. As an application of QGPs, we introduce quantified graph association rules defined with QGPs, to identify potential customers in social media marketing. Using real-life and synthetic graphs, we experimentally verify the effectiveness of QGPs and the scalability of our algorithms.

We propose a class of functional dependencies for graphs, referred to as GFDs. GFDs capture both attribute-value dependencies and topological structures of entities, and subsume conditional functional dependencies (CFDs) as a special case. We show that the satisfiability and implication problems for GFDs are coNP-complete and NP-complete, respectively, no worse than their CFD counterparts. We also show that the validation problem for GFDs is coNP-complete. Despite the intractability, we develop parallel scalable algorithms for catching violations of GFDs in large-scale graphs. Using real-life and synthetic data, we experimentally verify that GFDs provide an effective approach to detecting inconsistencies in knowledge and social graphs.

Answering queries using views has proven effective for querying relational and semistructured data. This paper investigates this issue for graph pattern queries based on graph simulation. We propose a notion ofpattern containmentto characterize graph pattern matching using graph pattern views. We show that a pattern query can be answered using a set of viewsif and only ifit is contained in the views. Based on this characterization, we develop efficient algorithms to answer graph pattern queries. We also study problems for determining (minimal, minimum) containment of pattern queries. We establish their complexity (from cubic-time to NP-complete) and provide efficient checking algorithms (approximation when the problem is intractable). In addition, when a pattern query is not contained in the views, we study maximally contained rewriting to find approximate answers; we show that it is in cubic-time to compute such rewriting, and present a rewriting algorithm. We experimentally verify that these methods are able to efficiently answer pattern queries on large real-world graphs.

We propose graph-pattern association rules (GPARs) for social media marketing. Extending association rules for item-sets, GPARs help us discover regularities between entities in social graphs, and identify potential customers by exploring social influence. We study the problem of discovering top- k diversified GPARs. While this problem is NP-hard, we develop a parallel algorithm with accuracy bound. We also study the problem of identifying potential customers with GPARs. While it is also NP-hard, we provide a parallel scalable algorithm that guarantees a polynomial speedup over sequential algorithms with the increase of processors. Using real-life and synthetic graphs, we experimentally verify the scalability and effectiveness of the algorithms.

Answering queries using views has proven an effective technique for querying relational and semistructured data. This paper investigates this issue for graph pattern queries based on (bounded) simulation, which have been increasingly used in, e.g., social network analysis. We propose a notion of pattern containment to characterize graph pattern matching using graph pattern views. We show that a graph pattern query can be answered using a set of views if and only if the query is contained in the views. Based on this characterization we develop efficient algorithms to answer graph pattern queries. In addition, we identify three problems associated with graph pattern containment. We show that these problems range from quadratic-time to NP-complete, and provide efficient algorithms for containment checking (approximation when the problem is intractable). Using real-life data and synthetic data, we experimentally verify that these methods are able to efficiently answer graph pattern queries on large social graphs, by using views.

Performance monitor software for data centers typically generates a great number of alert sequences. These alert sequences indicate abnormal network events. Given a set of observed alert sequences, it is important to identify the most critical alerts that are potentially the causes of others. While the need for mining critical alerts over large scale alert sequences is evident, most alert analysis techniques stop at modeling and mining the causal relations among the alerts.

This paper studies the problem of querying graphs within bounded resources. Given a query Q, a graph G and a small ratio α, it aims to answer Q in G by accessing only a fraction GQ of G of size |GQ| ≤ α |G|. The need for this is evident when G is big while our available resources are limited, as indicated by α. We propose resource-bounded query answering via a dynamic scheme that reduces big G to GQ. We investigate when we can find the exact answers Q(G) from GQ, and if GQ cannot accommodate enough information, how accurate the approximate answers Q(GQ) are. To verify the effectiveness of the approach, we study two types of queries. One consists of pattern queries that have data locality, such as subgraph isomorphism and strong simulation. The other is the class of reachability queries, without data locality. We show that it is hard to get resource-bounded algorithms with 100% accuracy: NP-hard for pattern queries, and non-existing for reachability when α ≠ 1. Despite these, we develop resource-bounded algorithms for answering these queries. Using real-life and synthetic data, we experimentally evaluate the performance of the algorithms. We find that they scale well for both types of queries, and our approximate answers are accurate, even 100% for small α.

Querying complex graph databases such as knowledge graphs is a challenging task for non-professional users. In this demo, we present SLQ, a user-friendly graph querying system enabling schemales and structures graph querying, where a user need not describe queries precisely as required by most databases. SLQ system combines searching and ranking: it leverages a set of transformation functions, including abbreviation, ontology, synonym, etc., that map keywords and linkages from a query to their matches in a data graph, based on an automatically learned ranking model. To help users better understand search results at different levels of granularity, it supports effective result summarization with "drill-down" and "roll-up" operations. Better still, the architecture of SLQ is elastic for new transformation functions, query logs and user feedback, to iteratively refine the ranking model. SLQ significantly improves the usability of graph querying. This demonstration highlights (1) SLQ can automatically learn an effective ranking model, without assuming manually labeled training examples, (2) it can efficiently return top ranked matches over noisy, large data graphs, (3) it can summarize the query matches to help users easily access, explore and understand query results, and (4) its GUI can interact with users to help them construct queries, explore data graphs and inspect matches in a user-friendly manner.

This paper studies fundamental problems for distributed graph simulation. Given a pattern query Q and a graph G that is fragmented and distributed, a graph simulation algorithm A is to compute the matches Q ( G ) of Q in G . We say that A is parallel scalable in (a) response time if its parallel computational cost is determined by the largest fragment F m of G and the size | Q | of query Q , and (b) data shipment if its total amount of data shipped is determined by | Q | and the number of fragments of G, independent of the size of graph G . (1) We prove an impossibility theorem : there exists no distributed graph simulation algorithm that is parallel scalable in either response time or data shipment. (2) However, we show that distributed graph simulation is partition bounded, i.e. , its response time depends only on | Q |, | F m | and the number | V f | of nodes in G with edges across different fragments; and its data shipment depends on | Q | and the number | E f | of crossing edges only. We provide the first algorithms with these performance guarantees. (3) We also identify special cases of patterns and graphs when parallel scalability is possible. (4) We experimentally verify the scalability and efficiency of our algorithms.

Querying complex graph databases such as knowledge graphs is a challenging task for non-professional users. Due to their complex schemas and variational information descriptions, it becomes very hard for users to formulate a query that can be properly processed by the existing systems. We argue that for a user-friendly graph query engine, it must support various kinds of transformations such as synonym, abbreviation, and ontology. Furthermore, the derived query results must be ranked in a principled manner. In this paper, we introduce a novel framework enabling schemaless and structureless graph querying (SLQ), where a user need not describe queries precisely as required by most databases. The query engine is built on a set of transformation functions that automatically map keywords and linkages from a query to their matches in a graph. It automatically learns an effective ranking model, without assuming manually labeled training examples, and can efficiently return top ranked matches using graph sketch and belief propagation. The architecture of SLQ is elastic for "plug-in" new transformation functions and query logs. Our experimental results show that this new graph querying paradigm is promising: It identifies high-quality matches for both keyword and graph queries over real-life knowledge graphs, and outperforms existing methods significantly in terms of effectiveness and efficiency.

We present ExpFinder, a system for finding experts in social networks based on graph pattern matching. We demonstrate (1) how ExpFinder identifies top-K experts in a social network by supporting bounded simulation of graph patterns, and by ranking the matches based on a metric for social impact; (2) how it copes with the sheer size of real-life social graphs by supporting incremental query evaluation and query preserving graph compression, and (3) how the GUI of ExpFinder interacts with users to help them construct queries and inspect matches.

Subgraph querying has been applied in a variety of emerging applications. Traditional subgraph querying based on subgraph isomorphism requires identical label matching, which is often too restrictive to capture the matches that are semantically close to the query graphs. This paper extends subgraph querying to identify semantically related matches by leveraging ontology information. (1) We introduce the ontology-based subgraph querying, which revises subgraph isomorphism by mapping a query to semantically related subgraphs in terms of a given ontology graph. We introduce a metric to measure the similarity of the matches. Based on the metric, we introduce an optimization problem to find top K best matches. (2) We provide a filtering-and-verification framework to identify (top-K) matches for ontology-based subgraph queries. The framework efficiently extracts a small subgraph of the data graph from an ontology index, and further computes the matches by only accessing the extracted subgraph. (3) In addition, we show that the ontology index can be efficiently updated upon the changes to the data graphs, enabling the framework to cope with dynamic data graphs. (4) We experimentally verify the effectiveness and efficiency of our framework using both synthetic and real life graphs, comparing with traditional subgraph querying methods.

Graph pattern matching has been widely used in e.g., social data analysis. A number of matching algorithms have been developed that, given a graph patternQand a graphG, compute the setM(Q,G)of matches ofQinG. However, these algorithms often return an excessive number of matches, and are expensive on large real-life social graphs. Moreover, in practice many social queries are to find matches of a specific pattern node, rather than the entireM(Q,G). This paper studies top-kgraph pattern matching. (1) We revise graph pattern matching defined in terms of simulation, by supporting a designated output nodeuo. GivenGandQ, it is to find those nodes inM(Q,G)that matchuo, instead of the large setM(Q,G). (2) We study two classes of functions for ranking the matches: relevance functions δr() based on, e.g., social impact, and distance functions δd() to cover diverse elements. (3) We develop two algorithms for computing top-kmatches ofuobased on δr(), with the early termination property, i.e., they find top-kmatches without computing the entireM(Q,G). (4) We also study diversified top-kmatching, a bi-criteria optimization problem based on both δr() and δd(). We show that its decision problem is NP-complete. Nonetheless, we provide an approximation algorithm with performance guarantees and a heuristic one with the early termination property. (5) Using real-life and synthetic data, we experimentally verify that our (diversified) top-kmatching algorithms are effective, and outperform traditional matching algorithms in efficiency.

It is increasingly common to find real-life data represented as networks of labeled, heterogeneous entities. To query these networks, one often needs to identify the matches of a given query graph in a (typically large) network modeled as a target graph. Due to noise and the lack of fixed schema in the target graph, the query graph can substantially differ from its matches in the target graph in both structure and node labels, thus bringing challenges to the graph querying tasks. In this paper, we propose NeMa (Network Match), a neighborhood-based subgraph matching technique for querying real-life networks. (1) To measure the quality of the match, we propose a novel subgraph matching cost metric that aggregates the costs of matching individual nodes, and unifies both structure and node label similarities. (2) Based on the metric, we formulate the minimum cost subgraph matching problem. Given a query graph and a target graph, the problem is to identify the (top- k ) matches of the query graph with minimum costs in the target graph. We show that the problem is NP-hard, and also hard to approximate. (3) We propose a heuristic algorithm for solving the problem based on an inference model. In addition, we propose optimization techniques to improve the efficiency of our method. (4) We empirically verify that NeMa is both effective and efficient compared to the keyword search and various state-of-the-art graph querying techniques.

Keyword search has been popularly used to query graph data. Due to the lack of structure support, a keyword query might generate an excessive number of matches, referred to as "answer graphs", that could include different relationships among keywords. An ignored yet important task is to group and summarize answer graphs that share similar structures and contents for better query interpretation and result understanding. This paper studies the summarization problem for the answer graphs induced by a keyword query Q . (1) A notion of summary graph is proposed to characterize the summarization of answer graphs. Given Q and a set of answer graphs G, a summary graph preserves the relation of the keywords in Q by summarizing the paths connecting the keywords nodes in G. (2) A quality metric of summary graphs, called coverage ratio, is developed to measure information loss of summarization. (3) Based on the metric, a set of summarization problems are formulated, which aim to find minimized summary graphs with certain coverage ratio. (a) We show that the complexity of these summarization problems ranges from ptime to NP-complete. (b) We provide exact and heuristic summarization algorithms. (4) Using real-life and synthetic graphs, we experimentally verify the effectiveness and the efficiency of our techniques.

In a wide array of disciplines, data can be modeled as an interconnected network of entities, where various attributes could be associated with both the entities and the relations among them. Knowledge is often hidden in the complex structure and attributes inside these networks. While querying and mining these linked datasets are essential for various applications, traditional graph queries may not be able to capture the rich semantics in these networks. With the advent of complex information networks, new graph queries are emerging, including graph pattern matching and mining, similarity search, ranking and expert finding, graph aggregation and OLAP. These queries require both the topology and content information of the network data, and hence, different from classical graph algorithms such as shortest path, reach ability and minimum cut, which depend only on the structure of the network. In this tutorial, we shall give an introduction of the emerging graph queries, their indexing and resolution techniques, the current challenges and the future research directions.

In social networks, information and influence diffuse among users as cascades. While the importance of studying cascades has been recognized in various applications, it is difficult to observe the complete structure of cascades in practice. In this paper we study the cascade inference problem following the independent cascade model, and provide a full treatment from complexity to algorithms: (a) we propose the idea of consistent trees as the inferred structures for cascades, these trees connect source nodes and observed nodes with paths satisfying the constraints from the observed temporal information. (b) We introduce metrics to measure the likelihood of consistent trees as inferred cascades, as well as several optimization problems for finding them. (c) We show that the decision problems for consistent trees are in general NP-complete, and that the optimization problems are hard to approximate. (d) We provide approximation algorithms with performance guarantees on the quality of the inferred cascades, as well as heuristics. We experimentally verify the efficiency and effectiveness of our inference algorithms, using real and synthetic data.

It is common to find graphs with millions of nodes and billions of edges in, e.g., social networks. Queries on such graphs are often prohibitively expensive. These motivate us to propose query preserving graph compression, to compress graphs relative to a class Λ of queries of users' choice. We compute a small Gr from a graph G such that (a) for any query Q Ε Λ Q, Q(G) = Q'(Gr), where Q' Ε Λ can be efficiently computed from Q; and (b) any algorithm for computing Q(G) can be directly applied to evaluating Q' on Gr as is. That is, while we cannot lower the complexity of evaluating graph queries, we reduce data graphs while preserving the answers to all the queries in Λ. To verify the effectiveness of this approach, (1) we develop compression strategies for two classes of queries: reachability and graph pattern queries via (bounded) simulation. We show that graphs can be efficiently compressed via a reachability equivalence relation and graph bisimulation, respectively, while reserving query answers. (2) We provide techniques for aintaining compressed graph Gr in response to changes ΔG to the original graph G. We show that the incremental maintenance problems are unbounded for the two lasses of queries, i.e., their costs are not a function of the size of ΔG and changes in Gr. Nevertheless, we develop incremental algorithms that depend only on ΔG and Gr, independent of G, i.e., we do not have to decompress Gr to propagate the changes. (3) Using real-life data, we experimentally verify that our compression techniques could reduce graphs in average by 95% for reachability and 57% for graph pattern matching, and that our incremental maintenance algorithms are efficient.

In the real world a graph is often fragmented and distributed across different sites. This highlights the need for evaluating queries on distributed graphs. This paper proposes distributed evaluation algorithms for three classes of queries: reachability for determining whether one node can reach another, bounded reachability for deciding whether there exists a path of a bounded length between a pair of nodes, and regular reachability for checking whether there exists a path connecting two nodes such that the node labels on the path form a string in a given regular expression. We develop these algorithms based on partial evaluation , to explore parallel computation. When evaluating a query Q on a distributed graph G , we show that these algorithms possess the following performance guarantees, no matter how G is fragmented and distributed: (1) each site is visited only once ; (2) the total network traffic is determined by the size of Q and the fragmentation of G, independent of the size of G ; and (3) the response time is decided by the largest fragment of G rather than the entire G . In addition, we show that these algorithms can be readily implemented in the MapReduce framework. Using synthetic and real-life data, we experimentally verify that these algorithms are scalable on large graphs, regardless of how the graphs are distributed.

It is increasingly common to find graphs in which edges bear different types, indicating a variety of relationships. For such graphs we propose a class of reachability queries and a class of graph patterns, in which an edge is specified with a regular expression of a certain form, expressing the connectivity in a data graph via edges of various types. In addition, we define graph pattern matching based on a revised notion of graph simulation. On graphs in emerging applications such as social networks, we show that these queries are capable of finding more sensible information than their traditional counterparts. Better still, their increased expressive power does not come with extra complexity. Indeed, (1) we investigate their containment and minimization problems, and show that these fundamental problems are in quadratic time for reachability queries and are in cubic time for pattern queries. (2) We develop an algorithm for answering reachability queries, in quadratic time as for their traditional counterpart. (3) We provide two cubic-time algorithms for evaluating graph pattern queries based on extended graph simulation, as opposed to the NP-completeness of graph pattern matching via subgraph isomorphism. (4) The effectiveness, efficiency and scalability of these algorithms are experimentally verified using real-life data and synthetic data.

Graph pattern matching has become a routine process in emerging applications such as social networks. In practice a data graph is typically large, and is frequently updated with small changes. It is often prohibitively expensive to recompute matches from scratch via batch algorithms when the graph is updated. With this comes the need for incremental algorithms that compute changes to the matches in response to updates, to minimize unnecessary recomputation. This paper investigates incremental algorithms for graph pattern matching defined in terms of graph simulation, bounded simulation and subgraph isomorphism. (1) For simulation, we provide incremental algorithms for unit updates and certain graph patterns. These algorithms are optimal: in linear time in the size of the changes in the input and output, which characterizes the cost that is inherent to the problem itself. For general patterns we show that the incremental matching problem is unbounded, i.e., its cost is not determined by the size of the changes alone. (2) For bounded simulation, we show that the problem is unbounded even for unit updates and path patterns. (3) For subgraph isomorphism, we show that the problem is intractable and unbounded for unit updates and path patterns. (4) For multiple updates, we develop an incremental algorithm for each of simulation, bounded simulation and subgraph isomorphism. We experimentally verify that these incremental algorithms significantly outperform their batch counterparts in response to small changes, using real-life data and synthetic data.

The paper formulates and investigates the aggregation problem for synthesized mediators of Web services (SWMs). An SWM is a finite-state transducer defined in terms of templates for component services. Upon receiving an artifact, an SWM selects a set of available services from a library to realize its templates, and invokes those services to operate on the artifact, in parallel; it produces a numeric value as output (e.g., the total price of a package) by applying synthesis rules. Given an SWM, a library and an input artifact, the aggregation problem is to find a mapping from the component templates of the SWM to available services in the library that maximizes (or minimizes) the output. As opposed to the composition syntheses of Web services, the aggregation problem aims to optimize the realization of a given mediator, to best serve the users' need. We analyze this problem, and show that its complexity depends on the underlying graph structure of the mediator: while it is undecidable when such graphs contain even very simple cycles, it is solvable in single-exponential time (in the size of the specification) for SWMs whose underlying graphs are acyclic. We prove several results of this kind, with matching lower bounds (NP and PSPACE), and analyze restrictions that lead to polynomial-time solutions.

Graph pattern matching is typically defined in terms of subgraph isomorphism, which makes it an np-complete problem. Moreover, it requires bijective functions, which are often too restrictive to characterize patterns in emerging applications. We propose a class of graph patterns, in which an edge denotes the connectivity in a data graph within a predefined number of hops. In addition, we define matching based on a notion of bounded simulation, an extension of graph simulation. We show that with this revision, graph pattern matching can be performed in cubic-time, by providing such an algorithm. We also develop algorithms for incrementally finding matches when data graphs are updated, with performance guarantees for dag patterns. We experimentally verify that these algorithms scale well, and that the revised notion of graph pattern matching allows us to identify communities commonly found in real-world networks.

In a variety of emerging applications one needs to decide whether a graph G matches another G p , i.e. , whether G has a topological structure similar to that of G p . The traditional notions of graph homomorphism and isomorphism often fall short of capturing the structural similarity in these applications. This paper studies revisions of these notions, providing a full treatment from complexity to algorithms. (1) We propose p-homomorphism (p -hom) and 1-1 p -hom, which extend graph homomorphism and subgraph isomorphism, respectively, by mapping edges from one graph to paths in another, and by measuring the similarity of nodes . (2) We introduce metrics to measure graph similarity, and several optimization problems for p -hom and 1-1 p -hom. (3) We show that the decision problems for p -hom and 1-1 p -hom are NP-complete even for DAGs, and that the optimization problems are approximation-hard. (4) Nevertheless, we provide approximation algorithms with provable guarantees on match quality. We experimentally verify the effectiveness of the revised notions and the efficiency of our algorithms in Web site matching, using real-life and synthetic data.

The dependency propagation problem is to determine, given a view defined on data sources and a set of dependencies on the sources, whether another dependency is guaranteed to hold on the view. This paper investigates dependency propagation for recently proposed conditional functional dependencies (CFDs). The need for this study is evident in data integration, exchange and cleaning since dependencies on data sources often only hold conditionally on the view. We investigate dependency propagation for views defined in various fragments of relational algebra, CFDs as view dependencies, and for source dependencies given as either CFDs or traditional functional dependencies (FDs). (a) We establish lower and upper bounds, all matching , ranging from PTIME to undecidable. These not only provide the first results for CFD propagation, but also extend the classical work of FD propagation by giving new complexity bounds in the presence of finite domains. (b) We provide the first algorithm for computing a minimal cover of all CFDs propagated via SPC views; the algorithm has the same complexity as one of the most efficient algorithms for computing a cover of FDs propagated via a projection view, despite the increased expressive power of CFDs and SPC views. (c) We experimentally verify that the algorithm is efficient.