Graphs have been widely used in fields ranging from chemical informatics to social network analysis.Graph-related problems become increasingly significant,with subgraph matching standing out as one of the most challen...Graphs have been widely used in fields ranging from chemical informatics to social network analysis.Graph-related problems become increasingly significant,with subgraph matching standing out as one of the most challenging tasks.The goal of subgraph matching is to find all subgraphs in the data graph that are isomorphic to the query graph.Traditional methods mostly rely on search strategies with high computational complexity and are hard to apply to large-scale real datasets.With the advent of graph neural networks(GNNs),researchers have turned to GNNs to address subgraph matching problems.However,the multi-attributed features on nodes and edges are overlooked during the learning of graphs,which causes inaccurate results in real-world scenarios.To tackle this problem,we propose a novel model called subgraph matching on multi-attributed graph network(SGMAN).SGMAN first utilizes improved line graphs to capture node and edge features.Then,SGMAN integrates GNN and contrastive learning(CL)to derive graph representation embeddings and calculate the matching matrix to represent the matching results.We conduct experiments on public datasets,and the results affirm the superior performance of our model.展开更多
With the development of information technology, the amount of power grid topology data has gradually increased. Therefore, accurate querying of this data has become particularly important. Several researchers have cho...With the development of information technology, the amount of power grid topology data has gradually increased. Therefore, accurate querying of this data has become particularly important. Several researchers have chosen different indexing methods in the filtering stage to obtain more optimized query results because currently there is no uniform and efficient indexing mechanism that achieves good query results. In the traditional algorithm, the hash table for index storage is prone to "collision" problems, which decrease the index construction efficiency. Aiming at the problem of quick index entry, based on the construction of frequent subgraph indexes, a method of serialized storage optimization based on multiple hash tables is proposed. This method mainly uses the exploration sequence to make the keywords evenly distributed; it avoids conflicts of the stored procedure and performs a quick search of the index. The proposed algorithm mainly adopts the "filterverify" mechanism; in the filtering stage, the index is first established offline, and then the frequent subgraphs are found using the "contains logic" rule to obtain the candidate set. Experimental results show that this method can reduce the time and scale of candidate set generation and improve query efficiency.展开更多
Subgraph matching problem is identifying a target subgraph in a graph. Graph neural network (GNN) is an artificial neural network model which is capable of processing general types of graph structured data. A graph ma...Subgraph matching problem is identifying a target subgraph in a graph. Graph neural network (GNN) is an artificial neural network model which is capable of processing general types of graph structured data. A graph may contain many subgraphs isomorphic to a given target graph. In this paper GNN is modeled to identify a subgraph that matches the target graph along with its characteristics. The simulation results show that GNN is capable of identifying a target sub-graph in a graph.展开更多
Bollobas and Gyarfas conjectured that for n 〉 4（k - 1） every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n - 2k ＋ 2 vertices. Liu, et al. proved that the conjecture holds when...Bollobas and Gyarfas conjectured that for n 〉 4（k - 1） every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n - 2k ＋ 2 vertices. Liu, et al. proved that the conjecture holds when n 〉 13k - 15. In this note, we characterize all the 2-edge-colorings of Kn where each monochromatic k-connected subgraph has at most n - 2k ＋ 2 vertices for n ≥ 13k - 15.展开更多
High-throughput techniques,such as the yeast-two-hybrid system,produce mass protein-protein interaction data. The new technique makes it possible to predict protein complexes by com-putation. A novel method,named DSDA...High-throughput techniques,such as the yeast-two-hybrid system,produce mass protein-protein interaction data. The new technique makes it possible to predict protein complexes by com-putation. A novel method,named DSDA,has been put forward to predict protein complexes via dense subgraph because the proteins among a protein complex have a much tighter relation among them than with others. This method chooses a node with its neighbors to form the initial subgraph,and chooses a node which has the tightest relation with the subgraph according to greedy strategy,then the chosen node is added into the initial subgraph until the subgraph density is below the threshold value. The ob-tained subgraph is then removed from the network and the process continues until no subgraph can be detected. Compared with other algorithms,DSDA can predict not only non-overlap protein com-plexes but also overlap protein complexes. The experiment results show that DSDA predict as many protein complexes as possible. And in Y78K network the accuracy of DSDA is as twice times as that of RNSC and MCL.展开更多
Alavi and his fellows defined the concept of ascending subgraph decomposition of a graph and conjectured that every graph with positive size has an ascending subgraph decomposition in paper [1]. Paper [2] proved that ...Alavi and his fellows defined the concept of ascending subgraph decomposition of a graph and conjectured that every graph with positive size has an ascending subgraph decomposition in paper [1]. Paper [2] proved that K n-R n-1 has a star ascending subgraph decomposition,here K n is the complete graph with order n and R n-1 is a subgraph of K n with size at most n-1. In paper [3],Ma Kejie and Chen Huaitang proved that K n-R n has an ascending subgraph decomposition when the size of R n is not greater than n. In this paper we will prove K n-R has an ascending subgraph decomposition when the size of R is less than 3n/2. This paper will also give the concept of comet and prove that K n-R n-1 has a comet ascending subgraph decomposition.展开更多
文摘Graphs have been widely used in fields ranging from chemical informatics to social network analysis.Graph-related problems become increasingly significant,with subgraph matching standing out as one of the most challenging tasks.The goal of subgraph matching is to find all subgraphs in the data graph that are isomorphic to the query graph.Traditional methods mostly rely on search strategies with high computational complexity and are hard to apply to large-scale real datasets.With the advent of graph neural networks(GNNs),researchers have turned to GNNs to address subgraph matching problems.However,the multi-attributed features on nodes and edges are overlooked during the learning of graphs,which causes inaccurate results in real-world scenarios.To tackle this problem,we propose a novel model called subgraph matching on multi-attributed graph network(SGMAN).SGMAN first utilizes improved line graphs to capture node and edge features.Then,SGMAN integrates GNN and contrastive learning(CL)to derive graph representation embeddings and calculate the matching matrix to represent the matching results.We conduct experiments on public datasets,and the results affirm the superior performance of our model.
基金supported by the State Grid Science and Technology Project (Title: Research on High Performance Analysis Technology of Power Grid GIS Topology Based on Graph Database, 5455HJ160005)
文摘With the development of information technology, the amount of power grid topology data has gradually increased. Therefore, accurate querying of this data has become particularly important. Several researchers have chosen different indexing methods in the filtering stage to obtain more optimized query results because currently there is no uniform and efficient indexing mechanism that achieves good query results. In the traditional algorithm, the hash table for index storage is prone to "collision" problems, which decrease the index construction efficiency. Aiming at the problem of quick index entry, based on the construction of frequent subgraph indexes, a method of serialized storage optimization based on multiple hash tables is proposed. This method mainly uses the exploration sequence to make the keywords evenly distributed; it avoids conflicts of the stored procedure and performs a quick search of the index. The proposed algorithm mainly adopts the "filterverify" mechanism; in the filtering stage, the index is first established offline, and then the frequent subgraphs are found using the "contains logic" rule to obtain the candidate set. Experimental results show that this method can reduce the time and scale of candidate set generation and improve query efficiency.
文摘Subgraph matching problem is identifying a target subgraph in a graph. Graph neural network (GNN) is an artificial neural network model which is capable of processing general types of graph structured data. A graph may contain many subgraphs isomorphic to a given target graph. In this paper GNN is modeled to identify a subgraph that matches the target graph along with its characteristics. The simulation results show that GNN is capable of identifying a target sub-graph in a graph.
基金Supported by the National Natural Science Foundation of China(10701065 and 11101378)Zhejiang Provincial Natural Science Foundation(LY14A010009)
文摘Bollobas and Gyarfas conjectured that for n 〉 4（k - 1） every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n - 2k ＋ 2 vertices. Liu, et al. proved that the conjecture holds when n 〉 13k - 15. In this note, we characterize all the 2-edge-colorings of Kn where each monochromatic k-connected subgraph has at most n - 2k ＋ 2 vertices for n ≥ 13k - 15.
基金Supported by the National Natural Science Foundation of China (60803025)
文摘High-throughput techniques,such as the yeast-two-hybrid system,produce mass protein-protein interaction data. The new technique makes it possible to predict protein complexes by com-putation. A novel method,named DSDA,has been put forward to predict protein complexes via dense subgraph because the proteins among a protein complex have a much tighter relation among them than with others. This method chooses a node with its neighbors to form the initial subgraph,and chooses a node which has the tightest relation with the subgraph according to greedy strategy,then the chosen node is added into the initial subgraph until the subgraph density is below the threshold value. The ob-tained subgraph is then removed from the network and the process continues until no subgraph can be detected. Compared with other algorithms,DSDA can predict not only non-overlap protein com-plexes but also overlap protein complexes. The experiment results show that DSDA predict as many protein complexes as possible. And in Y78K network the accuracy of DSDA is as twice times as that of RNSC and MCL.
文摘Alavi and his fellows defined the concept of ascending subgraph decomposition of a graph and conjectured that every graph with positive size has an ascending subgraph decomposition in paper [1]. Paper [2] proved that K n-R n-1 has a star ascending subgraph decomposition,here K n is the complete graph with order n and R n-1 is a subgraph of K n with size at most n-1. In paper [3],Ma Kejie and Chen Huaitang proved that K n-R n has an ascending subgraph decomposition when the size of R n is not greater than n. In this paper we will prove K n-R has an ascending subgraph decomposition when the size of R is less than 3n/2. This paper will also give the concept of comet and prove that K n-R n-1 has a comet ascending subgraph decomposition.
