Conventional image restoration methods often implicitly assume that the degradation type in the input image is "seen" and "known" to the model, meaning it is trained and tested on the same type of degradation. More recent "all-in-one" models are designed to handle only one single degradation type in an image at a time, though the type can vary within a small, predefined set. This paper proposes OmniRestore, a novel approach to tackle a new and challenging task: "Omni Restoration", meaning restoring images with random, combined degradations of unspecified numbers and types. In this task, the restoration model must be able to restore images corrupted by multiple degradation types simultaneously, without prior knowledge of the exact types and the number of degradations in the input image. To address this, we devise a Mixture-of-Experts (MoE) architecture with a shared encoder and a group of type-sensitive decoder experts, alongside a two-stage training pipeline to expand the generalizability to various degradation types and their combinations. Extensive experiments demonstrate that our OmniRestore model consistently and significantly outperforms all state-of-the-art (SOTA) single-degradation models, vertical ensembles of those models, and "all-in-one" models on the Omni Restoration task. Our model also surpasses most of the competing models under a single-degradation setting with seen or unseen degradations. Our dataset and code are publicly available at https://github.com/anjusreekarnavar/OmniRestore.

Stereo image dehazing aims to restore haze-free images by leveraging the complementary information contained in binocular images. Current methods primarily focus on designing image-level modules and pipelines to utilize complementary information between the left and right-view images. However, these image-level cross-view interactions overlook regional differences in haze concentration and stereo image disparity maps. Consequently, we propose a Progressive Stereo Image Dehazing Network via Cross-view Region Interaction, termed PSIDNet, which fully considers the internal characteristics and external manifestation of haze and disparity, and explicitly addresses the stereo image dehazing task by a regional-aware interactive mechanism. Specifically, we divide hazy images into regions and independently interact with left and right-view information at region levels, meaning weights are not shared across regional patches. This approach allows us to treat different regions with different priorities, i.e., concentrate on regional patches with heavier haze concentration and larger disparities, hence enabling more accurate restoration of hazy images. Furthermore, we introduce an effective cross-view region interactive block that extracts information based on the channel dimension of dual views and later adopts matrix multiplication to generate mutual attention maps based on the fused features. Extensive experiments on synthetic and real-scenario datasets demonstrate the efficacy of our method, compared to other related monocular and stereo image dehazing and restoration methods. Our code will be released publicly at https://github.com/Alvin2112/PSIDNet.

Shortest distance calculation between two locations in road networks is an important problem and has many applications. This problem has been widely researched for over two decades. Several advanced algorithms have been developed since the last formal evaluation. This paper provides a comprehensive experimental evaluation of these state-of-the-art algorithms. Our evaluation provides several important insights on the advantage/disadvantages of these algorithms, and it enables us to recommend the most suitable algorithm for some application scenarios. We are able to confirm some previous experimental results and raise questions on some others. We also evaluate the effect of a simple path compression technique on these algorithms.

Reachability query is a fundamental problem and has been well studied on static graphs. However, in the real world, the graphs are not static but always evolving over time. In this paper, we study the problem of historical reachability query on evolving graphs. We propose a novel index, named HR-Index, which integrates complete and correct historical reachability information of the evolving graph. A historical reachability query on an evolving graph can be converted into a static reachability query on its HR-Index and thus query efficiency can be improved significantly. We also propose two optimization techniques to reduce the size of HR-Index effectively. We confirm the effectiveness and efficiency of our method through conducting extensive experiments on real-life datasets. Experimental results show both vertex and edge size of HR-Index are far smaller than that of the evolving graphs and our method has at least an order of magnitude improvement in time and space efficiency compared to the state-of-the-art method.

In this paper, we study the following problem: given a knowledge graph (KG) and a set of input vertices (representing concepts or entities) and edge labels, we aim to find the smallest connected subgraphs containing all of the inputs. This problem plays a key role in KG-based search engines and natural language question answering systems, and it is a natural extension of the Steiner tree problem, which is known to be NP-hard. We present RECON, a system for finding approximate answers. RECON aims at achieving high accuracy with instantaneous response (i.e., sub-second/millisecond delay) over KGs with hundreds of millions edges without resorting to expensive computational resources. Furthermore, when no answer exists due to disconnection between concepts and entities, RECON refines the input to a semantically similar one based on the ontology, and attempts to find answers with respect to the refined input. We conduct a comprehensive experimental evaluation of RECON. In particular we compare it with five existing approaches for finding approximate Steiner trees. Our experiments on four large real and synthetic KGs show that RECON significantly outperforms its competitors and incurs a much smaller memory footprint.

Abstract Nowadays, public gatherings and social events are an integral part of a modern city life. To run such events seamlessly, it requires real time mining and monitoring of causally related events so that the management can make informed decisions and take appropriate actions. The automatic detection of event causality from short text such as tweets could be useful for event management in this context. However, detecting event causality from tweets is a challenging task. Tweets are short, unstructured, and often written in highly informal language which lacks enough contextual information to detect causality. The existing approaches apply different techniques including hand‐crafted linguistic rules and machine learning models. However, none of the approaches tackle the issue related to the lack of contextual information. In this paper, we detect event causality in tweets by applying a context word extension technique and a deep causal event detection model. The context word extension technique is driven by background knowledge extracted from one million news articles. Our model achieves 79.35% recall and 67.28% f1‐score, which are 17.39% and 2.33% improvements to the state‐of‐the‐art approach.

In this paper, we study an information exchange process in which a network of individuals exchanges a binary opinion.In the process, the individuals change their opinions only if a majority of their neighbours have the opposite opinion and they do it synchronously.Motivated by applications in multiagent systems, distributed computing, and social science, our goal is to derive graphtheoretic features of the network that guarantee whenever a majority of individuals initially have the same opinion, they will eventually spread the opinion to all individuals.We tackle the problem by first introducing a graph-theoretic notion called controlling set which is capable of characterising the information exchange process and, by exploiting the notion, we obtain a series of lower and upper bounds on the in-degree of vertices as well as lower bound on the size of certain neighbourhoods for guaranteeing the majority to unanimity behaviour.

Causal question answering is a task of answering causality related questions. The questions are referred to as binary causal questions when the questions e.g., "Could X cause Y?" can be answered by yes/no answers. Answer to the previous question is yes if X is a cause of Y, and otherwise no. The binary causal question answering systems can be used to validate causal relationships, which can be particularly useful for decision making. For example, it could be useful for the tourism authorities to know the answer to the question "Could growing social tension cause reduction in tourism?". We aim to automatically answer such binary causal questions by developing a machine learning model. However, training a machine learning model to detect causal relationships is challenging due to the lack of large and high quality labeled datasets. In this paper, we propose a transfer learning-based approach which fine-tunes pretrained transformer based language models on a small dataset of cause-effect pairs to detect causality and answer binary causal questions. The proposed approach achieves performance comparable to a number of benchmark approaches on five benchmark test datasets extracted by human experts conditioned on the same small training dataset.

This paper introduces the use of pictogram design concept in ancient China for the development of a set of today's "graphic icons" or "infographics" in modern social network visualization systems. These graphic icons should be close to sensory symbols that derive their expressive power from their ability to use the perceptual processing power of the brain without learning. Therefore, with the use of such a set of "sensory symbols" we aim to achieve the identification of corresponding physical objects (or their attributes) to be performed close to the pre-attentive time.

Twitter has become a great source of user-generated information about events. Very often people report causal relationships between events in their tweets. Automatic detection of causality information in these events might play an important role in prescriptive event analytics. Existing approaches include both rule-based and data-driven supervised methods. However, it is challenging to identify event causality accurately using linguistic rules due to the unstructured nature and grammatical incorrectness of social media short text such as tweets. Also, it is difficult to develop a data-driven supervised method for event causality detection in tweets due to insufficient contextual information. This paper proposes a novel event context word extension technique based on background knowledge. To demonstrate the effectiveness of our event context word extension technique, we develop a feed-forward neural network based approach to detect event causality from tweets. Extensive experiments demonstrate the superiority of our approach.

Fast reachability detection is one of the key problems in graph applications. Most of the existing works focus on creating an index and answering reachability based on that index. For these approaches, the index construction time and index size can become a concern for large graphs. More recently query-preserving graph compression has been proposed, and searching reachability over the compressed graph has been shown to be able to significantly improve query performance as well as reducing the index size. In this paper, we introduce a multilevel compression scheme for DAGs, which builds on existing compression schemes, but can further reduce the graph size for many real-world graphs. We propose an algorithm to answer reachability queries using the compressed graph. Extensive experiments with four existing state-of-the-art reachability algorithms and 12 real-world datasets demonstrate that our approach outperforms the existing methods. Experiments with synthetic datasets ensure the scalability of this approach. We also provide a discussion on possible compression for k-reachability.

With the popularity of knowledge graphs growing rapidly, large amounts of RDF graphs have been released, which raises the need for addressing the challenge of distributed subgraph matching queries. In this paper, we propose an efficient distributed method to answer subgraph matching queries on big RDF graphs using MapReduce. In our method, query graphs are decomposed into a set of stars that utilize the semantic and structural information embedded RDF graphs as heuristics. Two optimization techniques are proposed to further improve the efficiency of our algorithms. One algorithm, called RDF property filtering , filters out invalid input data to reduce intermediate results; the other is to improve the query performance by postponing the Cartesian product operations. The extensive experiments on both synthetic and real-world datasets show that our method outperforms the close competitors S2X and SHARD by an order of magnitude on average.

We study the subgraph enumeration problem under distributed settings. Existing solutions either suffer from severe memory crisis or rely on large indexes, which makes them impractical for very large graphs. Most of them follow a synchronous model where the performance is often bottlenecked by the machine with the worst performance. Motivated by this, in this paper, we propose RADS, a Robust Asynchronous Distributed Subgraph enumeration system. RADS first identifies results that can be found using single-machine algorithms. This strategy not only improves the overall performance but also reduces network communication and memory cost. Moreover, RADS employs a novel region-grouped multi-round expand verify & filter framework which does not need to shuffle and exchange the intermediate results, nor does it need to replicate a large part of the data graph in each machine. This feature not only reduces network communication cost and memory usage, but also allows us to adopt simple strategies for memory control and load balancing, making it more robust. Several optimization strategies are also used in RADS to further improve the performance. Our experiments verified the superiority of RADS to state-of-the-art subgraph enumeration approaches.

The problem of influence maximization has attracted a lot of attention as it provides a way to improve marketing, branding, and product adoption. However, existing studies rarely consider the physical locations of the social users, although location is an important factor in targeted marketing. In this paper, we investigate the problem of influence spanning maximization in location-aware social networks. Our target is to identify the maximum spanning geographical regions in a query region, which is very different from the existing methods that focus on the quantity of the activated users in the query region. Since the problem is NP-hard, we develop one greedy algorithm with a 1-1/e approximation ratio and further improve its efficiency by developing an upper bound based approach. Then, we propose the OIR index by combining ordered influential node lists and an R*-tree and design the index based solution. The efficiency and effectiveness of our proposed solutions and index have been verified using three real datasets.

This paper proposes a novel approach of weakly supervised video object segmentation, which only needs one pixel to guide the segmentation. We use two deep neural networks to get the instance-level semantic segmentation masks and optical flow maps of each frame. An object probability map to the first frame in video is generated by combining the semantic masks, the optical flow maps and the guiding pixel. The object probability map propagates forward and backward and becomes more accurate to each frame. Finally, an energy minimization problem on a function that consists of unary term of object probability and pairwise terms of label smoothness potentials is solved to get the pixel-wise object segmentation mask of each frame. We evaluate our method on a benchmark dataset, and the experimental results show that the proposed approach achieves impressive performance in comparison with state-of-the-art methods.

In this paper, a suite of lightweight security protocols for the Internet of Things (IoT) is presented. It comprises protocols for lightweight encryption, authentication as well as key management. The key management protocol is the application of our early work on information theoretically secure key management to IoT; it is computationally efficient and information-theoretically secure, and enables that every data item (file) is encrypted with its own random key. The security and computational efficiency of the proposed protocols are compared with those of IPsec, which is the most commonly used suite of network-layer security protocols in Internet based applications but not desirable, due to its computationally-intensive procedures, to IoT applications and cyber-physical systems (CPS) with resource and computation-capability constraints. The proposed security protocols can be employed in IoT and CPS applications, replacing the IPsec core algorithms or the whole IPsec suite, to achieve a higher level of security with a very low resource consumption that helps to maintain the system sustainability.

Influence maximization is a recent but well-studied problem which helps identify a small set of users that are most likely to “influence” the maximum number of users in a social network. The problem has attracted a lot of attention as it provides a way to improve marketing, branding, and product adoption. However, existing studies rarely consider the physical locations of the users, but location is an important factor in targeted marketing. In this paper, we propose and investigate the problem of influence maximization in location-aware social networks, or, more generally,Geo-social Influence Spanning Maximization. Given a query$q$composed of a region$R$, a regional acceptance rate$\rho$, and an integer$k$as a seed selection budget, our aim is to find the maximum geographic spanning regions (MGSR). We refer to this as the MGSR problem. Our approach differs from previous work as we focus more on identifying the maximum spanning geographical regions within a region$R$, rather than just the number of activated users in the given network like the traditional influence maximization problem[14]. Our research approach can be effectively used for online marketing campaigns that depend on the physical location of social users. To address the MGSR problem, we first prove NP-Hardness. Next, we present a greedy algorithm with a$1-1/e$approximation ratio to solve the problem, and further improve the efficiency by developing an upper bounded pruning approach. Then, we propose the OIR*-Tree index, which is a hybrid index combining ordered influential node lists with an R*-tree. We show that our index based approach is significantly more efficient than the greedy algorithm and the upper bounded pruning algorithm, especially when$k$is large. Finally, we evaluate the performance for all of the proposed approaches using three real datasets.

We propose an efficient distributed method for answering regular path queries (RPQs) on large-scale RDF graphs using partial evaluation. In local computation, we devise a dynamic programming approach to evaluate local and partial answers of an RPQ on each computing site in parallel. In the assembly phase, an automata-based algorithm is proposed to assemble the partial answers of the RPQ into the final results. The experiments on benchmark RDF graphs show that our method outperforms the state-of-the-art message passing methods by up to an order of magnitude.

Existing work on subgraph isomorphism search mainly focuses on a-query-at-a-time approaches: optimizing and answering each query separately. When multiple queries arrive at the same time, sequential processing is not always the most efficient. In this paper, we study multi-query optimization for subgraph isomorphism search. We first propose a novel method for efficiently detecting useful common sub-graphs and a data structure to organize them. Then we propose a heuristic algorithm based on the data structure to compute a query execution order so that cached intermediate results can be effectively utilized. To balance memory usage and the time for cached results retrieval, we present a novel structure for caching the intermediate results. We provide strategies to revise existing single-query subgraph isomorphism algorithms to seamlessly utilize the cached results, which leads to significant performance improvement. Extensive experiments verified the effectiveness of our solution.

Subgraph Isomorphism is a fundamental problem in graph data processing. Most existing subgraph isomorphism algorithms are based on a backtracking framework which computes the solutions by incrementally matching all query vertices to candidate data vertices. However, we observe that extensive duplicate computation exists in these algorithms, and such duplicate computation can be avoided by exploiting relationships between data vertices. Motivated by this, we propose a novel approach, BoostIso , to reduce duplicate computation. Our extensive experiments with real datasets show that, after integrating our approach, most existing subgraph isomorphism algorithms can be speeded up significantly, especially for some graphs with intensive vertex relationships, where the improvement can be up to several orders of magnitude.

We review the problem of finding contained rewritings (CRs) for XPath queries using XPath views. CR is proposed to cater for data integration scenarios, where views are unlikely to be complete due to the limited coverage of data sources, and hence equivalent rewritings are impossible to be found. As a result, we are usually required to find a maximal contained rewriting (MCR) for a query to provide the best possible answers. An MCR is a set of CRs, and may contain redundant CRs. Obviously, evaluating redundant CRs on materialized views is unnecessary. In this paper, we first address how to find the irredundant maximal contained rewriting (IMCR), i.e. all the irredundant CRs. We show that the existing approach ignores a type of situation, and turns out to be not sufficient. As a result, the only safe solution is a brute-force pairwise containment check for all the CRs. We then propose some heuristics to speed up the brute-force comparisons. When a materialized view is given, we propose how to evaluate the IMCR on the materialized view, which, to our knowledge, is the first work on optimizing the evaluation of a set of produced CRs on the materialized view by considering the inherent structural characteristics of the CRs. Our experiments show the effectiveness and efficiency of our algorithms.

We study the spelling suggestion problem for XML keyword search, which provides users with alternative queries that may better express users' search intention. In order to return the suggested queries more efficiently, we evaluate the quality of the query by estimating the selectivity and quality of each query pattern. The selectivity estimation is based on the XSketch synopsis, which summarizes the structure and value distribution of the original XML data source. We propose an approach to generating the top-K query candidates. Experiments with real datasets verifies the effectiveness and efficiency of our approach.

Modern visual analytics tools provide mechanism for users to gain unknown knowledge through effective visual interactions for user to quickly understand the progress of algorithms and adjust the input parameters on intermediate visualizations that towards the production of most satisfied outcome. This requires the quick production of a sequence of graph visualizations. However, the traditional force-directed graph drawing algorithms are very slow to reach an equilibrium configuration of forces. They usually spend tens of seconds producing the layout of a graph converge. Thus, they do not satisfy the requirement of rapid drawing of graphs. This paper proposes a fast convergence method for drawing force-directed graphs. We essentially pre-calculate the geometrical position of all vertices before applying a force-directed layout algorithm to reach the energy minimization of the graph layout. The experimental results have shown that this approach could not only reduce the convergence time but also the number of edge crossings that approves the quality of layout significantly.

We revisit the problem of answering tree pattern queries using views. We first show that, for queries and views that do not have nodes labeled with the wildcard *, there is an approach which does not require us to find any rewritings explicitly, yet which produces the same answers as the maximal contained rewriting. Then, using the new approach, we give simple conditions and a corresponding algorithm for identifying redundant view answers, which are view answers that can be ignored when evaluating the maximal contained rewriting. We also consider redundant view answers in the case where there are multiple views, the relationship between redundant views and redundant view answers, and discuss how to combine the removal of redundant view answers and redundant rewritings. We show that the aforesaid results can be extended to a number of other special cases. Finally, for arbitrary queries and views in P {/,//,.,[]} , we provide a method to find the maximal contained rewriting and show how to answer the query using views without explicitly finding the rewritings.

We revisit the problem of answering tree pattern queries using views. We first show that, for queries and views that do not have nodes labeled with the wildcard *, there is an alternative to the approach of query rewriting which does not require us to find any rewritings explicitly yet which produces the same answers as the maximal contained rewriting. Then, using the new approach, we give a simple criterion and a corresponding algorithm for identifying redundant view answers, which are view answers that can be ignored when evaluating the maximal contained rewriting. Finally, for queries and views that do have nodes labeled *, we provide a method to find the maximal contained rewriting and show how to answer the query using views without explicitly finding the rewritings.

Networking attacks embedded in spam emails are increasingly becoming numerous and sophisticated in nature. Hence this has given a growing need for spam email analysis to identify these attacks. The use of these intrusion detection systems has given rise to other two issues, 1) the presentation and understanding of large amounts of spam emails, 2) the user-assisted input and quantified adjustment during the analysis process. In this paper we introduce a new analytical model that uses two coefficient vectors: 'density' and 'weight'for the analysis of spam email viruses and attacks. We then use a visual clustering method to classify and display the spam emails. The visualization allows users to interactively select and scale down the scope of views for better understanding of different types of the spam email attacks. The experiment shows that this new model with the clustering visualization can be effectively used for network security analysis.

Tree patterns represent important fragments of XPath. In this paper, we show that some classes of tree patterns exhibit such a property that, given a finite number of tree patterns P1, ..., Pn, there exists another pattern P (tree pattern or DAG-pattern) such that P1, ..., Pn, are all contained in P, and for any tree pattern Q belonging to a given class C, P1, ..., Pn, are contained in Q implies P is contained in Q.

We present XKMis, a system for keyword search in XML documents. Unlike previous work, our method is not based on the lowest common ancestor (LCA) or its variant, rather we divide the nodes into meaningful and self-containing information segments, called minimal information segments (MISs), and return MIS-subtrees which consist of MISs that are logically connected by the keywords. The MIS-subtrees are closer to what the user wants. The MIS-subtrees enable us to use the region code of XML trees to develop an algorithm for the search which is more efficient especially for large XML trees. We report our experiment results, which verify the better effectiveness and efficiency of our system.

Web services have been emerging as a promising technology for business integration. Transactional support to integrated businesses via composing individual Web services is a critical issue. Current Web services protocols (e.g. BPEL4WS) have been proposed to deal with this issue on a strong assumption that each Web service is compensatable for a recovery purpose. It is arguable that Web services composition requires more transactional support beyond the compensation-based solution. This paper looks into the problem of transactional support for composing and scheduling those Web services that may have different transactional properties. The transactional properties of workflow constructs, which are fundamental to the composition of Web services, are thoroughly investigated. The concept of a connection point is introduced to derive the transactional properties of composite Web services. The scheduling issue of composite Web services is also discussed.