Journal articles: 'Subgraph matching'

1

Qiao, Miao, Hao Zhang, and Hong Cheng. "Subgraph matching." Proceedings of the VLDB Endowment 11, no. 2 (October 2017): 176–88. http://dx.doi.org/10.14778/3149193.3149198.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Sun, Yunhao, Guanyu Li, Mengmeng Guan, and Bo Ning. "Subgraph-Indexed Sequential Subdivision for Continuous Subgraph Matching on Dynamic Knowledge Graph." Complexity 2020 (December 22, 2020): 1–18. http://dx.doi.org/10.1155/2020/8871756.

Full text

Abstract:

Continuous subgraph matching problem on dynamic graph has become a popular research topic in the field of graph analysis, which has a wide range of applications including information retrieval and community detection. Specifically, given a query graph q , an initial graph G 0 , and a graph update stream △ G i , the problem of continuous subgraph matching is to sequentially conduct all possible isomorphic subgraphs covering △ G i of q on G i (= G 0 ⊕ △ G i ). Since knowledge graph is a directed labeled multigraph having multiple edges between a pair of vertices, it brings new challenges for the problem focusing on dynamic knowledge graph. One challenge is that the multigraph characteristic of knowledge graph intensifies the complexity of candidate calculation, which is the combination of complex topological and attributed structures. Another challenge is that the isomorphic subgraphs covering a given region are conducted on a huge search space of seed candidates, which causes a lot of time consumption for searching the unpromising candidates. To address these challenges, a method of subgraph-indexed sequential subdivision is proposed to accelerating the continuous subgraph matching on dynamic knowledge graph. Firstly, a flow graph index is proposed to arrange the search space of seed candidates in topological knowledge graph and an adjacent index is designed to accelerate the identification of candidate activation states in attributed knowledge graph. Secondly, the sequential subdivision of flow graph index and the transition state model are employed to incrementally conduct subgraph matching and maintain the regional influence of changed candidates, respectively. Finally, extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms.

APA, Harvard, Vancouver, ISO, and other styles

3

Došlić, Tomislav. "All Pairs of Pentagons in Leapfrog Fullerenes Are Nice." Mathematics 8, no. 12 (December 1, 2020): 2135. http://dx.doi.org/10.3390/math8122135.

Full text

Abstract:

A subgraph H of a graph G with perfect matching is nice if G−V(H) has perfect matching. It is well-known that all fullerene graphs have perfect matchings and that all fullerene graphs contain some small connected graphs as nice subgraphs. In this contribution, we consider fullerene graphs arising from smaller fullerenes via the leapfrog transformation, and show that in such graphs, each pair of (necessarily disjoint) pentagons is nice. That answers in affirmative a question posed in a recent paper on nice pairs of odd cycles in fullerene graphs.

APA, Harvard, Vancouver, ISO, and other styles

4

Schellewald, C., and C. Schnörr. "Subgraph Matching with Semidefinite Programming." Electronic Notes in Discrete Mathematics 12 (March 2003): 279–89. http://dx.doi.org/10.1016/s1571-0653(04)00493-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Yuan, Ye, Guoren Wang, Jeffery Yu Xu, and Lei Chen. "Efficient distributed subgraph similarity matching." VLDB Journal 24, no. 3 (March 7, 2015): 369–94. http://dx.doi.org/10.1007/s00778-015-0381-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Nie, Weizhi, Hai Ding, Anan Liu, Zonghui Deng, and Yuting Su. "Subgraph learning for graph matching." Pattern Recognition Letters 130 (February 2020): 362–69. http://dx.doi.org/10.1016/j.patrec.2018.07.005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Li, Faming, and Zhaonian Zou. "Subgraph matching on temporal graphs." Information Sciences 578 (November 2021): 539–58. http://dx.doi.org/10.1016/j.ins.2021.07.071.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Moorman, Jacob D., Thomas K. Tu, Qinyi Chen, Xie He, and Andrea L. Bertozzi. "Subgraph Matching on Multiplex Networks." IEEE Transactions on Network Science and Engineering 8, no. 2 (April 1, 2021): 1367–84. http://dx.doi.org/10.1109/tnse.2021.3056329.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Xu, Zifeng, Fucai Zhou, Yuxi Li, Jian Xu, and Qiang Wang. "Privacy-Preserving Subgraph Matching Protocol for Two Parties." International Journal of Foundations of Computer Science 30, no. 04 (June 2019): 571–88. http://dx.doi.org/10.1142/s0129054119400136.

Full text

Abstract:

Graph data structure has been widely used across many application areas, such as web data, social network, and cheminformatics. The main benefit of storing data as graphs is there exists a rich set of graph algorithms and operations that can be used to solve various computing problems, including pattern matching, data mining, and image processing. Among these graph algorithms, the subgraph isomorphism problem is one of the most fundamental algorithms that can be utilized by many higher level applications. The subgraph isomorphism problem is defined as, given two graphs [Formula: see text] and [Formula: see text], whether [Formula: see text] contains a subgraph that is isomorphic to [Formula: see text]. In this paper, we consider a special case of the subgraph isomorphism problem called the subgraph matching problem, which tests whether [Formula: see text] is a subgraph of [Formula: see text]. We propose a protocol that solve the subgraph matching problem in a privacy-preserving manner. The protocol allows two parties to jointly compute whether one graph is a subgraph of the other, while protecting the private information about the input graphs. The protocol is secure under the semi-honest setting, where each party performs the protocol faithfully.

APA, Harvard, Vancouver, ISO, and other styles

10

Shan, Xiaohuan, Haihai Li, Chunjie Jia, Dong Li, and Baoyan Song. "Supergraph Topology Feature Index for Personalized Interesting Subgraph Query in Large Labeled Graphs." Complexity 2021 (June 29, 2021): 1–18. http://dx.doi.org/10.1155/2021/9274429.

Full text

Abstract:

Interesting subgraph query aims to find subgraphs that are isomorphic to the given query graph from a data graph and rank the subgraphs according to their interestingness scores. However, the existing subgraph query approaches are inefficient when dealing with large-scale labeled data graph. This is caused by the following problems: (i) the existing work mainly focuses on unweighted query graphs, while ignoring the impact of query constraints on query results. (ii) Excessive number of subgraph candidates or complex joins between nodes in the subgraph candidates reduce the query efficiency. To solve these problems, this paper proposes an intelligent solution. Firstly, an Isotype Structure Graph Compression (ISGC) strategy is proposed to compress similar nodes in a graph to reduce the size of the graph and avoid unnecessary matching. Then, an auxiliary data structure Supergraph Topology Feature Index (STFIndex) is designed to replace the storage of the original data graph and improve the efficiency of an online query. After that, a partition method based on Edge Label Step Value (ELSV) is proposed to partition the index logically. In addition, a novel Top-K interest subgraph query approach is proposed, which consists of the multidimensional filtering (MDF) strategy, upper bound value (UBV) (Size-c) matching, and the optimizational join (QJ) method to filter out as many false subgraph candidates as possible to achieve fast joins. We conduct experiments on real and synthetic datasets. Experimental results show that the average performance of our approach is 1.35 higher than that of the state-of-the-art approaches when the query graph is unweighted, and the average performance of our approach is 2.88 higher than that of the state-of-the-art approaches when the query graph is weighted.

APA, Harvard, Vancouver, ISO, and other styles

11

Bunke, H., and B. T. Messmer. "Recent Advances in Graph Matching." International Journal of Pattern Recognition and Artificial Intelligence 11, no. 01 (February 1997): 169–203. http://dx.doi.org/10.1142/s0218001497000081.

Full text

Abstract:

A powerful and universal data structure with applications invarious subfields of science and engineering is graphs. In computer vision and image analysis, graphs are often used for the representation of structured objects. For example, if the problem is to recognize instances of known objects in an image, then often models, or prototypes, of the known objects are represented by means of graphs and stored in a database. The unknown objects in the input image are extracted by means of suitable preprocessing and segmentation algorithms, and represented by graphs that are analogous to the model graphs. Thus, the problem of object recognition is transformed into a graph matching problem. In this paper, it is assumed that there is an input graph that is given on-line, and a number of model, or prototype, graphs that are known a priori. We present a new approach to subgraph isomorphism detection which is based on a compact representation of the model graphs that is computed off-line. Subgraphs that appear multiple times within the same or within different model graphs are represented only once, thus reducing the computational effort to detect them in an input graph. In the extreme case where all model graphs are highly similar, the run time of the new algorithm becomes independent of the number of model graphs. We also describe an extension of this method to error-correcting graph matching. Furthermore, an approach to subgraph isomorphism detection based on decision trees is proposed. A decision tree is generated from the models in an off-line phase. This decision tree can be used for subgraph isomorphism detection. The time needed for decision tree traversal is only polynomial in terms of the number of nodes of the input graph. Moreover, the time complexity of the decision tree traversal is completely independent on the number of model graphs, regardless of their similarity. However, the size of the decision tree is exponential in the number of nodes of the models. To cut down the space complexity of the decision tree, some pruning strategies are discussed.

APA, Harvard, Vancouver, ISO, and other styles

12

Chen, Wei, Jia Liu, Ziyang Chen, Xian Tang, and Kaiyu Li. "PBSM: An Efficient Top-K Subgraph Matching Algorithm." International Journal of Pattern Recognition and Artificial Intelligence 32, no. 06 (February 21, 2018): 1850020. http://dx.doi.org/10.1142/s0218001418500209.

Full text

Abstract:

Top-K subgraph matching is one of the hot research issues in graph data management, which is to find, from the data graph, K subgraphs isomorphic to the query graph with the largest sum of weights. The existing methods of Top-K subgraph matching on large graphs usually use the filter-and-verify strategy. However, they all suffer from inefficiency in both stages. In the filtering stage, there exists repeated enumeration of vertices and the excessive memory cost of the filtering. In the verification stage, there exists redundant verification. Regarding to the above problems, we propose to use the preprocessing of the graph compression based on equivalent vertices to reduce the enumeration. In the filtering stage, we propose to reduce the memory cost by only considering the direct neighbors. In the verification stage, we take the vertex with the minimum number of candidate vertices in the query graph as the start vertex of the matching order, and use the idea of Ranking While Matching (RWM) to terminate the execution of the algorithm as early as possible by estimating the upper bound of the weights, so as to reduce redundant verification and improve the overall performance. Finally, the experimental results show that our method is much more efficient than existing methods in compression and the processing time.

APA, Harvard, Vancouver, ISO, and other styles

13

Baskararaja, GnanaJothi Raja, and MeenaRani Sundaramoorthy Manickavasagam. "Subgraph Matching Using Graph Neural Network." Journal of Intelligent Learning Systems and Applications 04, no. 04 (2012): 274–78. http://dx.doi.org/10.4236/jilsa.2012.44028.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Yang, Xu, Hong Qiao, and Zhi-Yong Liu. "Partial correspondence based on subgraph matching." Neurocomputing 122 (December 2013): 193–97. http://dx.doi.org/10.1016/j.neucom.2013.06.031.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Lai, Longbin, Zhu Qing, Zhengyi Yang, Xin Jin, Zhengmin Lai, Ran Wang, Kongzhang Hao, et al. "Distributed subgraph matching on timely dataflow." Proceedings of the VLDB Endowment 12, no. 10 (June 2019): 1099–112. http://dx.doi.org/10.14778/3339490.3339494.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Peng, Hao, Jianxin Li, Qiran Gong, Yuanxin Ning, Senzhang Wang, and Lifang He. "Motif-Matching Based Subgraph-Level Attentional Convolutional Network for Graph Classification." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 5387–94. http://dx.doi.org/10.1609/aaai.v34i04.5987.

Full text

Abstract:

Graph classification is critically important to many real-world applications that are associated with graph data such as chemical drug analysis and social network mining. Traditional methods usually require feature engineering to extract the graph features that can help discriminate the graphs of different classes. Although recently deep learning based graph embedding approaches are proposed to automatically learn graph features, they mostly use a few vertex arrangements extracted from the graph for feature learning, which may lose some structural information. In this work, we present a novel motif-based attentional graph convolution neural network for graph classification, which can learn more discriminative and richer graph features. Specifically, a motif-matching guided subgraph normalization method is developed to better preserve the spatial information. A novel subgraph-level self-attention network is also proposed to capture the different impacts or weights of different subgraphs. Experimental results on both bioinformatics and social network datasets show that the proposed models significantly improve graph classification performance over both traditional graph kernel methods and recent deep learning approaches.

APA, Harvard, Vancouver, ISO, and other styles

17

Xiao, Hong, Yuan Li, Jian-Feng Yu, and Hui Cheng. "Dynamic assembly simplification for virtual assembly process of complex product." Assembly Automation 34, no. 1 (January 28, 2014): 1–15. http://dx.doi.org/10.1108/aa-12-2012-093.

Full text

Abstract:

Purpose – Virtual assembly process plays an important role in assembly design of complex product and is typically time- and resource-intensive. This paper aims to investigate a dynamic assembly simplification approach in order to demonstrate and interact with virtual assembly process of complex product in real time. Design/methodology/approach – The proposed approach regards the virtual assembly process of complex product as an incremental growth process of dynamic assembly. During the growth process, the current-assembled-state assembly model is simplified with appearance preserved by detecting and removing its invisible features, and the to-be-assembled components are simplified with assembly features preserved using conjugated subgraphs matching method based on an improved subgraph isomorphism algorithm. Findings – The dynamic assembly simplification approach is applied successfully to reduce the complexity of computer aided design models during the virtual assembly process and it is proved by several cases. Originality/value – A new assembly features definition is proposed based on the notion of “conjugation” to assist the assembly features recognition, which is a main step of the dynamic assembly simplification and has been translated into conjugated subgraphs matching problem. And an improved subgraph isomorphism algorithm is presented to address this problem.

APA, Harvard, Vancouver, ISO, and other styles

18

HUANG, Yun, Jia-ming HONG, and Zun-yue QIN. "Approximate subgraph matching based on dual index." Journal of Computer Applications 32, no. 7 (August 26, 2013): 1994–97. http://dx.doi.org/10.3724/sp.j.1087.2012.01994.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Sun, Zhao, Hongzhi Wang, Haixun Wang, Bin Shao, and Jianzhong Li. "Efficient subgraph matching on billion node graphs." Proceedings of the VLDB Endowment 5, no. 9 (May 2012): 788–99. http://dx.doi.org/10.14778/2311906.2311907.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Chen Chuang, 陈闯, 王亚 Wang Ya, and 贾文武 Jia Wenwu. "A Subgraph Learning Method for Graph Matching." Laser & Optoelectronics Progress 57, no. 6 (2020): 061003. http://dx.doi.org/10.3788/lop57.061003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Gupta, Sushmita, and Sanjukta Roy. "Stable Matching Games: Manipulation via Subgraph Isomorphism." Algorithmica 80, no. 9 (October 27, 2017): 2551–73. http://dx.doi.org/10.1007/s00453-017-0382-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Jin, Fusheng, Yifeng Yang, Shuliang Wang, Ye Xue, and Zhen Yan. "TBSGM." International Journal of Data Warehousing and Mining 14, no. 4 (October 2018): 67–89. http://dx.doi.org/10.4018/ijdwm.2018100104.

Full text

Abstract:

Subgraph matching, which belongs to NP-hard, faces significant challenges on a large scale graph with billions of nodes, and existing methods are usually confronted with greater challenges from both stability and efficiency. In this article, a subgraph matching method in a distributed system, tree model-based subgraph matching method (TBSGM) is proposed. The authors provide a transformed efficient query tree as a replacement for a query graph. In order to get the tree, they present a cost evaluation model which may help to generate the efficient query tree according to network communication-cost and calculation-cost evaluation. Also, a key set based indexing strategy for intermediate results is given to simplify the matching results during network communication. Extensive experiments with real-world datasets show that TBSGM significantly outperforms other methods in the aspects of scalability and efficiency.

APA, Harvard, Vancouver, ISO, and other styles

23

KOSTOCHKA, ALEXANDR, and MATTHEW YANCEY. "Large Rainbow Matchings in Edge-Coloured Graphs." Combinatorics, Probability and Computing 21, no. 1-2 (February 2, 2012): 255–63. http://dx.doi.org/10.1017/s0963548311000605.

Full text

Abstract:

Arainbow subgraphof an edge-coloured graph is a subgraph whose edges have distinct colours. Thecolour degreeof a vertexvis the number of different colours on edges incident withv. Wang and Li conjectured that fork≥ 4, every edge-coloured graph with minimum colour degreekcontains a rainbow matching of size at least ⌈k/2⌉. A properly edge-colouredK4has no such matching, which motivates the restrictionk≥ 4, but Li and Xu proved the conjecture for all other properly coloured complete graphs. LeSaulnier, Stocker, Wenger and West showed that a rainbow matching of size ⌊k/2⌋ is guaranteed to exist, and they proved several sufficient conditions for a matching of size ⌈k/2⌉. We prove the conjecture in full.

APA, Harvard, Vancouver, ISO, and other styles

24

Liamwiset, Chalida, and Vatanawood Wiwat. "Detection of Design Patterns in Software Design Model Using Graph." Applied Mechanics and Materials 411-414 (September 2013): 559–62. http://dx.doi.org/10.4028/www.scientific.net/amm.411-414.559.

Full text

Abstract:

Detection of design patterns in software design phase possibly ensures the non-functional requirements, regarding performance features, before investing the implementation. We formalize the structural UML class diagram using graph. By applying graph matching technique, we propose an alternative of subgraph matching algorithm to extract the local properties of the UML class diagrams and perform the detecting of subgraph of possible design patterns found in the target software design model.

APA, Harvard, Vancouver, ISO, and other styles

25

Yuan, Ling, Jiali Bin, and Peng Pan. "Optimized Distributed Subgraph Matching Algorithm Based on Partition Replication." Electronics 9, no. 1 (January 18, 2020): 184. http://dx.doi.org/10.3390/electronics9010184.

Full text

Abstract:

At present, with the explosive growth of data scale, subgraph matching for massive graph data is difficult to satisfy with efficiency. Meanwhile, the graph index used in existing subgraph matching algorithm is difficult to update and maintain when facing dynamic graphs. We propose a distributed subgraph matching algorithm based on Partition Replica (noted as PR-Match) to process the partition and storage of large-scale data graphs. The PR-Match algorithm first splits the query graph into sub-queries, then assigns the sub-query to each node for sub-graph matching, and finally merges the matching results. In the PR-Match algorithm, we propose a heuristic rule based on prediction cost to select the optimal merging plan, which greatly reduces the cost of merging. In order to accelerate the matching speed of the sub-query graph, a vertex code based on the vertex neighbor label signature is proposed, which greatly reduces the search space for the subquery. As the vertex code is based on the increment, the problem that the feature-based graph index is difficult to maintain in the face of the dynamic graph is solved. An abundance of experiments on real and synthetic datasets demonstrate the high efficiency and strong scalability of the PR-Match algorithm when handling large-scale data graphs.

APA, Harvard, Vancouver, ISO, and other styles

26

Dahm, Nicholas, Horst Bunke, Terry Caelli, and Yongsheng Gao. "Efficient subgraph matching using topological node feature constraints." Pattern Recognition 48, no. 2 (February 2015): 317–30. http://dx.doi.org/10.1016/j.patcog.2014.05.018.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Tian, Y., R. C. McEachin, C. Santos, D. J. States, and J. M. Patel. "SAGA: a subgraph matching tool for biological graphs." Bioinformatics 23, no. 2 (November 16, 2006): 232–39. http://dx.doi.org/10.1093/bioinformatics/btl571.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Hou, Xinmin, Hong-Jian Lai, and Cun-Quan Zhang. "On Perfect Matching Coverings and Even Subgraph Coverings." Journal of Graph Theory 81, no. 1 (March 4, 2015): 83–91. http://dx.doi.org/10.1002/jgt.21863.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Rivero, Carlos R., and Hasan M. Jamil. "Efficient and scalable labeled subgraph matching using SGMatch." Knowledge and Information Systems 51, no. 1 (July 5, 2016): 61–87. http://dx.doi.org/10.1007/s10115-016-0968-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Wong, E. K. "Model matching in robot vision by subgraph isomorphism." Pattern Recognition 25, no. 3 (March 1992): 287–303. http://dx.doi.org/10.1016/0031-3203(92)90111-u.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

WANLESS, IAN M. "Counting Matchings and Tree-Like Walks in Regular Graphs." Combinatorics, Probability and Computing 19, no. 3 (February 10, 2010): 463–80. http://dx.doi.org/10.1017/s0963548309990678.

Full text

Abstract:

The number of closed tree-like walks in a graph is closely related to the moments of the roots of the matching polynomial for the graph. Thus, by counting these walks up to a given length it is possible to find approximations for the matching polynomial. This approach has been used in two separate problems involving asymptotic enumerations of 1-factorizations of regular graphs. Nevertheless, a systematic way to count the required walks had not previously been found.In this paper we give an algorithm to count closed tree-like walks in a regular graph up to a given length. For smallm, this provides expressions for the number ofm-matchings in the graph in terms of the numbers of copies of certain small subgraphs that appear in the graph. The simplest of these expressions were already known, having been rediscovered by numerous authors usingad hocmethods. We offer the first general method for producing the expressions. We also find generating functions that isolate the contribution from the simplest kind of subgraph – namely a single cycle of arbitrary length.

APA, Harvard, Vancouver, ISO, and other styles

32

Farrell, E. J., and Earl Glen Whitehead. "Connections between the matching and chromatic polynomials." International Journal of Mathematics and Mathematical Sciences 15, no. 4 (1992): 757–66. http://dx.doi.org/10.1155/s016117129200098x.

Full text

Abstract:

The main results established are (i) a connection between the matching and chromatic polynomials and (ii) a formula for the matching polynomial of a general complement of a subgraph of a graph. Some deductions on matching and chromatic equivalence and uniqueness are made.

APA, Harvard, Vancouver, ISO, and other styles

33

Wu, Keshou, Guanfeng Liu, and Junwen Lu. "Graph-Based Node Finding in Big Complex Contextual Social Graphs." Complexity 2020 (February 26, 2020): 1–13. http://dx.doi.org/10.1155/2020/7909826.

Full text

Abstract:

Graph pattern matching is to find the subgraphs matching the given pattern graphs. In complex contextual social networks, considering the constraints of social contexts like the social relationships, the social trust, and the social positions, users are interested in the top-K matches of a specific node (denoted as the designated node) based on a pattern graph, rather than the entire set of graph matching. This inspires the conText-Aware Graph pattern-based top-K designated node matching (TAG-K) problem, which is NP-complete. Targeting this challenging problem, we propose a recurrent neural network- (RNN-) based Monte Carlo Tree Search algorithm (RN-MCTS), which automatically balances exploring new possible matches and extending existing matches. The RNN encodes the subgraph and maps it to a policy which is used to guide the MCTS. The experimental results demonstrate that our proposed algorithm outperforms the state-of-the-art methods in terms of both efficiency and effectiveness.

APA, Harvard, Vancouver, ISO, and other styles

34

Raveaux, Romain, Jean-Christophe Burie, and Jean-Marc Ogier. "A graph matching method and a graph matching distance based on subgraph assignments." Pattern Recognition Letters 31, no. 5 (April 2010): 394–406. http://dx.doi.org/10.1016/j.patrec.2009.10.011.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Agarwal, Shubhangi, Sourav Dutta, and Arnab Bhattacharya. "ChiSeL." Proceedings of the VLDB Endowment 13, no. 10 (June 2020): 1654–68. http://dx.doi.org/10.14778/3401960.3401964.

Full text

Abstract:

Subgraph querying is one of the most important primitives in many applications. Although the field is well studied for deterministic graphs, in many situations, the graphs are probabilistic in nature. In this paper, we address the problem of subgraph querying in large probabilistic labeled graphs. We employ a novel algorithmic framework, called ChiSeL, that uses the idea of statistical significance for approximate subgraph matching on uncertain graphs that have uncertainty in edges. For each candidate matching vertex in the target graph that matches a query vertex, we compute its statistical significance using the chi-squared statistic. The search algorithm then proceeds in a greedy manner by exploring the vertex neighbors having the largest chi-square score. In addition to edge uncertainty, we also show how ChiSeL can handle uncertainty in labels and/or vertices. Experiments on large real-life graphs show the efficiency and effectiveness of our algorithm.

APA, Harvard, Vancouver, ISO, and other styles

36

Lian, Xiang, Lei Chen, and Guoren Wang. "Quality-Aware Subgraph Matching Over Inconsistent Probabilistic Graph Databases." IEEE Transactions on Knowledge and Data Engineering 28, no. 6 (June 1, 2016): 1560–74. http://dx.doi.org/10.1109/tkde.2016.2518683.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Lerouge, Julien, Maroua Hammami, Pierre Héroux, and Sébastien Adam. "Minimum cost subgraph matching using a binary linear program." Pattern Recognition Letters 71 (February 2016): 45–51. http://dx.doi.org/10.1016/j.patrec.2015.11.026.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Zhu, Yixiao, Hui Li, Jiangtao Cui, and Yong Ma. "Verifiable Subgraph Matching With Cryptographic Accumulators in Cloud Computing." IEEE Access 7 (2019): 169636–45. http://dx.doi.org/10.1109/access.2019.2955243.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Xu, Qiang, Xin Wang, Jianxin Li, Qingpeng Zhang, and Lele Chai. "Distributed Subgraph Matching on Big Knowledge Graphs Using Pregel." IEEE Access 7 (2019): 116453–64. http://dx.doi.org/10.1109/access.2019.2936465.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Choi, Dojin, Kyoungsoo Bok, and Jaesoo Yoo. "An Efficient Continuous Subgraph Matching Scheme Considering Data Reuse." Journal of KIISE 46, no. 8 (August 31, 2019): 842–51. http://dx.doi.org/10.5626/jok.2019.46.8.842.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Gao, Jiu-Ru, Wei Chen, Jia-Jie Xu, An Liu, Zhi-Xu Li, Hongzhi Yin, and Lei Zhao. "An Efficient Framework for Multiple Subgraph Pattern Matching Models." Journal of Computer Science and Technology 34, no. 6 (November 2019): 1185–202. http://dx.doi.org/10.1007/s11390-019-1969-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Aparo, Antonino, Vincenzo Bonnici, Giovanni Micale, Alfredo Ferro, Dennis Shasha, Alfredo Pulvirenti, and Rosalba Giugno. "Fast Subgraph Matching Strategies Based on Pattern-Only Heuristics." Interdisciplinary Sciences: Computational Life Sciences 11, no. 1 (February 21, 2019): 21–32. http://dx.doi.org/10.1007/s12539-019-00323-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Wang, Xin, Lele Chai, Qiang Xu, Yajun Yang, Jianxin Li, Junhu Wang, and Yunpeng Chai. "Efficient Subgraph Matching on Large RDF Graphs Using MapReduce." Data Science and Engineering 4, no. 1 (March 2019): 24–43. http://dx.doi.org/10.1007/s41019-019-0090-z.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Houbraken, Maarten, Sofie Demeyer, Tom Michoel, Pieter Audenaert, Didier Colle, and Mario Pickavet. "The Index-Based Subgraph Matching Algorithm with General Symmetries (ISMAGS): Exploiting Symmetry for Faster Subgraph Enumeration." PLoS ONE 9, no. 5 (May 30, 2014): e97896. http://dx.doi.org/10.1371/journal.pone.0097896.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

WANG, XIUMEI, SUJING ZHOU, and YIXUN LIN. "BIPARTITE MATCHING EXTENDABILITY AND TOUGHNESS." Discrete Mathematics, Algorithms and Applications 02, no. 01 (March 2010): 33–44. http://dx.doi.org/10.1142/s1793830910000450.

Full text

Abstract:

Let G be a simple graph containing a perfect matching. G is said to be bipartite matching extendable (BM-extendable) if every matching M which is a perfect matching of an induced bipartite subgraph extends to a perfect matching of G. In this paper, we study some relations between toughness and BM-extendability of a graph, including some sufficient or necessary conditions about toughness for a graph to be BM-extendable, and a sufficient condition for a BM-extendable graph to be 1-tough.

APA, Harvard, Vancouver, ISO, and other styles

46

KUNER, PETER, and BIRGIT UEBERREITER. "PATTERN RECOGNITION BY GRAPH MATCHING—COMBINATORIAL VERSUS CONTINUOUS OPTIMIZATION." International Journal of Pattern Recognition and Artificial Intelligence 02, no. 03 (September 1988): 527–42. http://dx.doi.org/10.1142/s0218001488000303.

Full text

Abstract:

A generalization of subgraph isomorphism for the fault-tolerant interpretation of disturbed line images has been achieved. Object recognition is effected by optimal matching of a reference graph to the graph of a distorted image. This optimization is based on the solution of linear and quadratic assignment problems. The efficiency of the procedures developed for this objective has been proved in practical applications. NP-complete problems such as subgraph recognition need exhaustive computation if exact (branch-and-bound) algorithms are used. In contrast to this, heuristics are very fast and sufficiently reliable for less complex relational structures of the kind investigated in the first part of this paper. Constrained continuous optimization techniques, such as relaxation labeling and neural network strategies, solve recognition problems within a reasonable time, even in rather complex relational structures where heuristics can fail. They are also well suited to parallelism. The second part of this paper is devoted exclusively to them.

APA, Harvard, Vancouver, ISO, and other styles

47

Moskin, N. D. "Metric for comparing graphs with ordered vertices based on the maximum common subgraph." Prikladnaya Diskretnaya Matematika, no. 52 (2021): 105–13. http://dx.doi.org/10.17223/20710410/52/7.

Full text

Abstract:

The work is devoted to methods for comparing and classifying graphs. This trend is known as "graph matching". An overview of metrics for comparing graphs based on the maximum common subgraph is given. A modification of the distance based on the maximum common subgraph, which takes into account the ordering of the vertices, is proposed. It is shown that this function satisfies all the properties of the metric (non-negativity, identity, symmetry, triangle inequality).

APA, Harvard, Vancouver, ISO, and other styles

48

Demeyer, Sofie, Tom Michoel, Jan Fostier, Pieter Audenaert, Mario Pickavet, and Piet Demeester. "The Index-Based Subgraph Matching Algorithm (ISMA): Fast Subgraph Enumeration in Large Networks Using Optimized Search Trees." PLoS ONE 8, no. 4 (April 19, 2013): e61183. http://dx.doi.org/10.1371/journal.pone.0061183.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Hong, Liang, Lei Zou, Xiang Lian, and Philip S. Yu. "Subgraph Matching with Set Similarity in a Large Graph Database." IEEE Transactions on Knowledge and Data Engineering 27, no. 9 (September 1, 2015): 2507–21. http://dx.doi.org/10.1109/tkde.2015.2391125.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Hu, Sen, Lei Zou, Jeffrey Xu Yu, Haixun Wang, and Dongyan Zhao. "Answering Natural Language Questions by Subgraph Matching over Knowledge Graphs." IEEE Transactions on Knowledge and Data Engineering 30, no. 5 (May 1, 2018): 824–37. http://dx.doi.org/10.1109/tkde.2017.2766634.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Subgraph matching'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles