Search

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Protection systems are one of the most critical components in the transmission system and are becoming more digital with ongoing automation. These digital systems are prone to vulnerabilities/attacks, and exploitation of these vulnerabilities may cause major impacts on the electric grid performance. Multiple alarms reported in the control center could be a result of the faults (expected operations) or failures in the protection system (anomalies/ unexpected operation). Situational awareness gained through sensors such as a phasor measurement unit (PMU) and data acquired through the cyber system provide an opportunity to develop continuous cyber-physical monitoring of the system. Note that relay data are not reported in the control center continuously. This paper presents a cyber-physical data analytics based technique to monitor transmission protection system and detect malicious activity. Initially, continuous monitoring of PMU data is utilized for data anomaly detection, which includes bad or missing data using long short-term memory (LSTM). Then, PMU data of interest are utilized for failure diagnosis, using a semisupervised deep autoencoder model. In this research, cyber anomalies are modeled by manipulating the setting/logic design of protective devices, and a ridge regression based classifier with a feature engineering pipeline is used to detect cyber anomalies. The results from the deep autoencoder model and ridge regression based classifier are then utilized for detailed investigation to find the root causes of the observed events assisted by the cyber log data from the protection devices. The algorithm is validated using a real-time simulation of the IEEE test system with industrial hardware relays and PMUs in the loop. Data analytics algorithm running on server utilizes these real-time data continuously for anomaly detection and classification for the developed use cases. [ABSTRACT FROM AUTHOR]

With the advent of phasor measurement units (PMUs), high resolution synchronized phasor measurements enables real time system monitoring and control. PMUs transmit data to local controllers in substations and phasor data concentrators for system wide monitoring and control application in the control center. They provide real-time phasor data for critical power system applications such as remedial action schemes, oscillation detection, and state estimation. The quality of phasor data from PMUs is critical for smart grid applications. Several methods are developed to detect anomalies in time series data, tailored for PMU data analysis. Nevertheless, applying stand alone methods (with fixed parameters) takes great tuning effort, and does not always achieve high accuracy. In this paper, we adopt an unsupervised ensemble learning approach to develop fast, scalable bad data/event detection for PMU data. The ensemble method invokes a set of base detectors to generate anomaly scores of the PMU data, and makes decisions by aggregating the scores from each detector. We develop two algorithms: 1) a learning algorithm that trains the ensemble model and 2) an online algorithm that infers the anomaly scores with the ensemble model over PMU data streams. The proposed method provides flag for data anomalies and triggers further analysis to differentiate between events and bad data. Using both simulated and real-world PMU data, we show that our ensemble model can be efficiently trained, can achieve high accuracy in detecting diversified errors/events, and outperforms its counterparts that use single standalone detection method. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 of pattern containment to characterize graph pattern matching using graph pattern views. We show that a pattern query can be answered using a set of views if and only if it 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. [ABSTRACT FROM AUTHOR]