Using partial evaluation in holistic subgraph search

Because of its wide application, the subgraph matching problem has been studied extensively during the past decade. However, most existing solutions assume that a data graph is a vertex/edge-labeled graph (i.e., each vertex/edge has a simple label). These solutions build structural indices by considering the vertex labels. However, some real graphs contain rich-content vertices such as user profiles in social networks and HTML pages on the World Wide Web. In this study, we consider the problem of subgraph matching using a more general scenario. We build a structural index that does not depend on any vertex content. Based on the index, we design a holistic subgraph matching algorithm that considers the query graph as a whole and finds one match at a time. In order to further improve efficiency, we propose a “partial evaluation and assembly” framework to find subgraph matches over large graphs. Last but not least, our index has light maintenance overhead. Therefore, our method can work well on dynamic graphs. Extensive experiments on real graphs show that our method outperforms the state-of-the-art algorithms.     

Answering pattern match queries in large graph databases via graph embedding

The growing popularity of graph databases has generated interesting data management problems, such as subgraph search, shortest path query, reachability verification, and pattern matching. Among these, a pattern match query is more flexible compared with a subgraph search and more informative compared with a shortest path or a reachability query. In this paper, we address distance-based pattern match queries over a large data graph G. Due to the huge search space, we adopt a filter-and-refine framework to answer a pattern match query over a large graph. We first find a set of candidate matches by a graph embedding technique and then evaluate these to find the exact matches. Extensive experiments confirm the superiority of our method.     

Uniquely Restricted Matchings

A matching in a graph is a set of edges no two of which share a common vertex. In this paper we introduce a new, specialized type of matching which we call uniquely restricted matchings, originally motivated by the problem of determining a lower bound on the rank of a matrix having a specified zero/ non-zero pattern. A uniquely restricted matching is defined to be a matching M whose saturated vertices induce a subgraph which has only one perfect matching, namely M itself. We introduce the two problems of recognizing a uniquely restricted matching and of finding a maximum uniquely restricted matching in a given graph, and present algorithms and complexity results for certain special classes of graphs. We demonstrate that testing whether a given matching M is uniquely restricted can be done in O(|M||E|) time for an arbitrary graph G=(V,E) and in linear time for cacti, interval graphs, bipartite graphs, split graphs and threshold graphs. The maximum uniquely restricted matching problem is shown to be NP-complete for bipartite graphs, split graphs, and hence for chordal graphs and comparability graphs, but can be solved in linear time for threshold graphs, proper interval graphs, cacti and block graphs. Received April 12, 1998; revised June 21, 1999.     

On the induced matching problem

We study extremal questions on induced matchings in certain natural graph classes. We argue that these questions should be asked for twinless graphs, that is graphs not containing two vertices with the same neighborhood. We show that planar twinless graphs always contain an induced matching of size at least n/40 while there are planar twinless graphs that do not contain an induced matching of size (n+10)/27. We derive similar results for outerplanar graphs and graphs of bounded genus. These extremal results can be applied to the area of parameterized computation. For example, we show that the induced matching problem on planar graphs has a kernel of size at most 40k that is computable in linear time; this significantly improves the results of Moser and Sikdar (2007). We also show that we can decide in time O(k⁹¹+n) whether a planar graph contains an induced matching of size at least k.     

不确定图间α-β子图同构匹配算法

子图查询返回图数据集合中所有包含查询图的数据图。在查询图和数据图同时为不确定性图的前提下,提出了不确定图间的期望子图同构定义和α-β子图同构匹配定义。不确定图间的期望子图同构是确定图上子图同构在概率图模型上的直接推广,不确定图间α-β子图同构利用两个限制阈值来衡量查询图和数据图间的匹配质量。文章详细阐述了α-β子图同构匹配的语义特点,分析了其和期望子图同构的联系和差别,设计实现α-β子图同构匹配判定算法。     

Parameterized complexity of connected even/odd subgraph problems

In 2011, Cai an Yang initiated the systematic parameterized complexity study of the following set of problems around Eulerian graphs: for a given graph G and integer k, the task is to decide if G contains a (connected) subgraph with k vertices (edges) with all vertices of even (odd) degrees. They succeed to establish the parameterized complexity of all cases except two, when we ask about:

•

a connected k-edge subgraph with all vertices of odd degrees, the problem known as k-Edge Connected Odd Subgraph; and     

<Emphasis Type="Italic">k</Emphasis>-Outerplanar Graphs,Planar Duality,and Low Stretch Spanning Trees

Low distortion probabilistic embedding of graphs into approximating trees is an extensively studied topic. Of particular interest is the case where the approximating trees are required to be (subgraph) spanning trees of the given graph (or multigraph), in which case, the focus is usually on the equivalent problem of finding a (single) tree with low average stretch. Among the classes of graphs that received special attention in this context are k-outerplanar graphs (for a fixed k): Chekuri, Gupta, Newman, Rabinovich, and Sinclair show that every k-outerplanar graph can be probabilistically embedded into approximating trees with constant distortion regardless of the size of the graph. The approximating trees in the technique of Chekuri et al. are not necessarily spanning trees, though.     

Stable sets in k-colorable -free graphs

We show that, for fixed k, there is a polynomial-time algorithm that finds a maximum (or maximum-weight) stable set in any graph that belongs to the class of k-colorable P₅-free graphs, or, more generally, to the class of P₅-free graphs that contain no clique of size k+1. This is based on the following structural result: every connected k-colorable P₅-free graph has a vertex whose non-neighbors induce a (k−1)-colorable subgraph.     

WSM: a novel algorithm for subgraph matching in large weighted graphs

Given an undirected/directed large weighted data graph and a similar smaller weighted pattern graph, the problem of weighted subgraph matching is to find a mapping of the nodes in the pattern graph to a subset of nodes in the data graph such that the sum of edge weight differences is minimum. Biological interaction networks such as protein-protein interaction networks and molecular pathways are often modeled as weighted graphs in order to account for the high false positive rate occurring intrinsically during the detection process of the interactions. Nonetheless, complex biological problems such as disease gene prioritization and conserved phylogenetic tree construction largely depend on the similarity calculation among the networks. Although several existing methods provide efficient methods for graph and subgraph similarity measurement, they produce nonintuitive results due to the underlying unweighted graph model assumption. Moreover, very few algorithms exist for weighted graph matching that are applicable with the restriction that the data and pattern graph sizes are equal. In this paper, we introduce a novel algorithm for weighted subgraph matching which can effectively be applied to directed/undirected weighted subgraph matching. Experimental results demonstrate the superiority and relative scalability of the algorithm over available state of the art methods.     

Incremental <Emphasis Type="Italic">k</Emphasis>-core decomposition: algorithms and evaluation

A k-core of a graph is a maximal connected subgraph in which every vertex is connected to at least k vertices in the subgraph. k-core decomposition is often used in large-scale network analysis, such as community detection, protein function prediction, visualization, and solving NP-hard problems on real networks efficiently, like maximal clique finding. In many real-world applications, networks change over time. As a result, it is essential to develop efficient incremental algorithms for dynamic graph data. In this paper, we propose a suite of incremental k-core decomposition algorithms for dynamic graph data. These algorithms locate a small subgraph that is guaranteed to contain the list of vertices whose maximum k-core values have changed and efficiently process this subgraph to update the k-core decomposition. We present incremental algorithms for both insertion and deletion operations, and propose auxiliary vertex state maintenance techniques that can further accelerate these operations. Our results show a significant reduction in runtime compared to non-incremental alternatives. We illustrate the efficiency of our algorithms on different types of real and synthetic graphs, at varying scales. For a graph of 16 million vertices, we observe relative throughputs reaching a million times, relative to the non-incremental algorithms.     

Inexact subgraph isomorphism in MapReduce

Inexact subgraph matching based on type-isomorphism was introduced by Berry et al. [J. Berry, B. Hendrickson, S. Kahan, P. Konecny, Software and algorithms for graph queries on multithreaded architectures, in: Proc. IEEE International Parallel and Distributed Computing Symposium, IEEE, 2007, pp. 1–14] as a generalization of the exact subgraph matching problem. Enumerating small subgraph patterns in very large graphs is a core problem in the analysis of social networks, bioinformatics data sets, and other applications. This paper describes a MapReduce algorithm for subgraph type-isomorphism matching. The MapReduce computing framework is designed for distributed computing on massive data sets, and the new algorithm leverages MapReduce techniques to enable processing of graphs with billions of vertices. The paper also introduces a new class of walk-level constraints for narrowing the set of matches. Constraints meeting criteria defined in the paper are useful for specifying more precise patterns and for improving algorithm performance. Results are provided on a variety of graphs, with size ranging up to billions of vertices and edges, including graphs that follow a power law degree distribution.     

Maximum planar subgraphs and nice embeddings: Practical layout tools

In automatic graph drawing a given graph has to be laid out in the plane, usually according to a number of topological and aesthetic constraints. Nice drawings for sparse nonplanar graphs can be achieved by determining a maximum planar subgraph and augmenting an embedding of this graph. This approach appears to be of limited value in practice, because the maximum planar subgraph problem is NP-hard.We attack the maximum planar subgraph problem with a branch-and-cut technique which gives us quite good, and in many cases provably optimum, solutions for sparse graphs and very dense graphs. In the theoretical part of the paper, the polytope of all planar subgraphs of a graphG is defined and studied. All subgraphs of a graphG, which are subdivisions ofK ₅ orK _3,3, turn out to define facets of this polytope. For cliques contained inG, the Euler inequalities turn out to be facet-defining for the planar subgraph polytope. Moreover, we introduce the subdivision inequalities,V _2k inequalities, and the flower inequalities, all of which are facet-defining for the polytope. Furthermore, the composition of inequalities by 2-sums is investigated.We also present computational experience with a branch-and-cut algorithm for the above problem. Our approach is based on an algorithm which searches for forbidden substructures in a graph that contains a subdivision ofK ₅ orK _3,3. These structures give us inequalities which are used as cutting planes.Finally, we try to convince the reader that the computation of maximum planar subgraphs is indeed a practical tool for finding nice embeddings by applying this method to graphs taken from the literature.     

GSO:基于图神经网络的深度学习计算图子图替换优化框架

深度学习在各种实际应用中取得了巨大成功,如何有效提高各种复杂的深度学习模型在硬件设备上的执行效率是该领域重要的研究内容之一.深度学习框架通常将深度学习模型表达为由基础算子构成的计算图,为了提高计算图的执行效率,传统的深度学习系统通常基于一些专家设计的子图替换规则,采用启发式搜索算法来优化计算图.它们的不足主要有:1)搜...     

Fast processing of graph queries on a large database of small and medium-sized data graphs

We propose a new way of indexing a large database of small and medium-sized graphs and processing exact subgraph matching (or subgraph isomorphism) and approximate (full) graph matching queries. Rather than decomposing a graph into smaller units (e.g., paths, trees, graphs) for indexing purposes, we represent each graph in the database by its graph signature, which is essentially a multiset. We construct a disk-based index on all the signatures via bulk loading. During query processing, a query graph is also mapped into its signature, and this signature is searched using the index by performing multiset operations. To improve the precision of exact subgraph matching, we develop a new scheme using the concept of line graphs. Through extensive evaluation on real and synthetic graph datasets, we demonstrate that our approach provides a scalable and efficient disk-based solution for a large database of small and medium-sized graphs.     

Structure and Recognition of Graphs with No 6-wheel Subdivision

The subgraph homeomorphism problem has been shown by Robertson and Seymour to be polynomial-time solvable for any fixed pattern graph H. The result, however, is not practical, involving constants that are worse than exponential in |H|. Practical algorithms have only been developed for a few specific pattern graphs, the most recent of these being the wheels with four and five spokes. This paper looks at the subgraph homeomorphism problem where the pattern graph is a wheel with six spokes. The main result is a theorem characterizing graphs that do not contain subdivisions of W ₆. We give an efficient algorithm for solving the subgraph homeomorphism problem for W ₆. We also give a strengthening of the previous W ₅ result.     

A constant approximation algorithm for the densest k-subgraph problem on chordal graphs

The densest k-subgraph (DkS) problem asks for a k-vertex subgraph of a given graph with the maximum number of edges. The DkS problem is NP-hard even for special graph classes including bipartite, planar, comparability and chordal graphs, while no constant approximation algorithm is known for any of these classes. In this paper we present a 3-approximation algorithm for the class of chordal graphs. The analysis of our algorithm is based on a graph theoretic lemma of independent interest.     

Indexing through laplacian spectra

With ever growing databases containing multimedia data, indexing has become a necessity to avoid a linear search. We propose a novel technique for indexing multimedia databases in which entries can be represented as graph structures. In our method, the topological structure of a graph as well as that of its subgraphs are represented as vectors whose components correspond to the sorted laplacian eigenvalues of the graph or subgraphs. Given the laplacian spectrum of graph G, we draw from recently developed techniques in the field of spectral integral variation to generate the laplacian spectrum of graph G+e without computing its eigendecomposition, where G+e is a graph obtained by adding edge e to graph G. This process improves the performance of the system for generating the subgraph signatures for 1.8% and 6.5% in datasets of size 420 and 1400, respectively. By doing a nearest neighbor search around the query spectra, similar but not necessarily isomorphic graphs are retrieved. Given a query graph, a voting schema ranks database graphs into an indexing hypothesis to which a final matching process can be applied. The novelties of the proposed method come from the powerful representation of the graph topology and successfully adopting the concept of spectral integral variation in an indexing algorithm. To examine the fitness of the new indexing framework, we have performed a number of experiments using an extensive set of recognition trials in the domain of 2D and 3D object recognition. The experiments, including a comparison with a competing indexing method using two different graph-based object representations, demonstrate both the robustness and efficacy of the overall approach.     

Sum Coloring Interval and k -Claw Free Graphs with Application to Scheduling Dependent Jobs

We consider the sum coloring and sum multicoloring problems on several fundamental classes of graphs, including the classes of interval and k-claw free graphs. We give an algorithm that approximates sum coloring within a factor of 1.796, for any graph in which the maximum k-colorable subgraph problem is polynomially solvable. In particular, this improves on the previous best known ratio of 2 for interval graphs. We introduce a new measure of coloring, robust throughput}, that indicates how quickly the graph is colored, and show that our algorithm approximates this measure within a factor of 1.4575. In addition, we study the contiguous (or non-preemptive) sum multicoloring problem on k-claw free graphs. This models, for example, the scheduling of dependent jobs on multiple dedicated machines, where each job requires the exclusive use of at most k machines. Assuming that k is a fixed constant, we obtain the first constant factor approximation for the problem.     

A user parameter-free approach for mining robust sequential classification rules

Recent years have witnessed extensive studies of graph classification due to the rapid increase in applications involving structural data and complex relationships. To support graph classification, all existing methods require that training graphs should be relevant (or belong) to the target class, but cannot integrate graphs irrelevant to the class of interest into the learning process. In this paper, we study a new universum graph classification framework which leverages additional “non-example” graphs to help improve the graph classification accuracy. We argue that although universum graphs do not belong to the target class, they may contain meaningful structure patterns to help enrich the feature space for graph representation and classification. To support universum graph classification, we propose a mathematical programming algorithm, ugBoost, which integrates discriminative subgraph selection and margin maximization into a unified framework to fully exploit the universum. Because informative subgraph exploration in a universum setting requires the search of a large space, we derive an upper bound discriminative score for each subgraph and employ a branch-and-bound scheme to prune the search space. By using the explored subgraphs, our graph classification model intends to maximize the margin between positive and negative graphs and minimize the loss on the universum graph examples simultaneously. The subgraph exploration and the learning are integrated and performed iteratively so that each can be beneficial to the other. Experimental results and comparisons on real-world dataset demonstrate the performance of our algorithm.     

Hardness and approximation of minimum maximal matchings

In this paper, we consider the minimum maximal matching problem in some classes of graphs such as regular graphs. We show that the minimum maximal matching problem is NP-hard even in regular bipartite graphs, and a polynomial time exact algorithm is given for almost complete regular bipartite graphs. From the approximation point of view, it is well known that any maximal matching guarantees the approximation ratio of 2 but surprisingly very few improvements have been obtained. In this paper we give improved approximation ratios for several classes of graphs. For example any algorithm is shown to guarantee an approximation ratio of (2-o(1)) in graphs with high average degree. We also propose an algorithm guaranteeing for any graph of maximum degree Δ an approximation ratio of (2?1/Δ), which slightly improves the best known results. In addition, we analyse a natural linear-time greedy algorithm guaranteeing a ratio of (2?23/18k) in k-regular graphs admitting a perfect matching.