This paper proposes a method for searching for graphs in the database which are contained as subgraphs by a given query. In the proposed method, the search index does not require any knowledge of the query set or the ...
详细信息
This paper proposes a method for searching for graphs in the database which are contained as subgraphs by a given query. In the proposed method, the search index does not require any knowledge of the query set or the frequent subgraph patterns. In conventional techniques, enumerating and selecting frequent subgraph patterns is computationally expensive, and the distribution of the query set must be known in advance. Subsequent changes to the query set require the frequent patterns to be selected again and the index to be reconstructed. The proposed method overcomes these difficulties through graph coding, using a tree structured index that contains infrequent subgraph patterns in the shallow part of the tree. By traversing this code tree, we are able to rapidly determine whether multiple graphs in the database contain subgraphs that match the query, producing a powerful pruning or filtering effect. Furthermore, the filtering and verification steps of the graph search can be conducted concurrently, rather than requiring separate algorithms. As the proposed method does not require the frequent subgraph patterns and the query set, it is significantly faster than previous techniques;this independence from the query set also means that there is no need to reconstruct the search index when the query set changes. A series of experiments using a real-world dataset demonstrate the efficiency of the proposed method, achieving a search speed several orders of magnitude faster than the previous best.
In this paper we introduce the concept of ordered graph and ordered graph isomorphism that provides a natural representation of many objects in applications such as computer vision and pattern recognition. While no ef...
详细信息
In this paper we introduce the concept of ordered graph and ordered graph isomorphism that provides a natural representation of many objects in applications such as computer vision and pattern recognition. While no efficient (polynomial-bound) isomorphism algorithm for general graphs exists today, we show that the ordered graph isomorphism problem can be optimally solved in quadratic time. An experimental evaluation demonstrates the superior performance of the new method. Our ordered graph isomorphism algorithm is simple and can be easily implemented. It is therefore expected to be practically useful in many applications. (C) 1999 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.
Ordered graph and ordered graph isomorphism provide a natural representation of many objects in applications such as computational geometry, computer vision and pattern recognition. In the present paper we propose a c...
详细信息
Ordered graph and ordered graph isomorphism provide a natural representation of many objects in applications such as computational geometry, computer vision and pattern recognition. In the present paper we propose a coding procedure for ordered graphs that improves an earlier one based on Eulerian circuits of graphs in terms of both simplicity and computational efficiency. Using our coding approach, we show that the ordered graph isomorphism problem can be optimally solved in quadratic time, although no efficient (polynomial-bound) isomorphism algorithm for general graphs exists today. An experimental evaluation demonstrates the superior performance of the new method.
In this paper we present a coder for polygon mesh connectivity that delivers the best connectivity compression rates meshes reported so far. Our coder is an extension of the vertex-based coder for triangle mesh connec...
详细信息
ISBN:
(纸本)1568811837
In this paper we present a coder for polygon mesh connectivity that delivers the best connectivity compression rates meshes reported so far. Our coder is an extension of the vertex-based coder for triangle mesh connectivity by Touma and Gotsman [26]. We code polygonal connectivity as a sequence of face and vertex degrees and exploit the correlation between them for mutual predictive compression. Because low-degree vertices are likely to be surrounded by high-degree faces and vice versa, we predict vertex degrees based on neighboring face degrees and face degrees based on neighboring vertex degrees.
Link prediction is a fundamental research issue in complex network, which can reveal the potential relationships between users. Most of link prediction algorithms are heuristic and based on topology structure. Weisfei...
详细信息
Link prediction is a fundamental research issue in complex network, which can reveal the potential relationships between users. Most of link prediction algorithms are heuristic and based on topology structure. Weisfeiler-Lehman Neural Machine (WLNM), regarded as a new-generation method, has shown promising performance and thus got attention in link prediction. WLNM extracts an enclosing subgraph of each target link and encodes the subgraph as an adjacency matrix. But it does not consider the relationship between other links of the enclosing subgraph and target links. Therefore, WLNM does not make full use of the topology information around the link, and the extracted enclosing subgraph can only partially represent the topological features around the target link. In this work, a novel approach is proposed, named weighted enclosing subgraph-based link prediction (WESLP). It incorporates the link weights in the enclosing subgraph to reflect their relationship with the target link, and the Katz index between nodes is used to measure the relationship between two links. The prediction models are trained by different classifiers based on these weighted enclosing subgraphs. Experiments show that our proposed method consistently performs well on different real-world datasets.
暂无评论