[번역] Frequent Subgraph Mining Algorithms – A Survey

원문 Frequent Subgraph Mining Algorithms – A Survey (2015)

Abstract

Graphs are common data structures used to represent / model real-world systems. Graph Mining is one of the arms of Data mining in which voluminous complex data are represented in the form of graphs and mining is done to infer knowledge from them. Frequent sub graph mining is a sub section of graph mining domain which is extensively used for graph classification, building indices and graph clustering purposes. The frequent sub graph mining is addressed from various perspectives and viewed in different directions based upon the domain expectations. In this paper, a survey is done on the approaches in targeting frequent sub graphs and various scalable techniques to find them.

그래프는 실제 시스템을 표현/모델링하는데 사용되는 일반적인 데이터 구조입니다. 그래프 마이닝은 대량의 복잡한 데이터가 그래프 형식으로 표시되고 그로부터 지식을 유추하기 위해 마이닝이 수행되는 데이터 마이닝의 무기 중 하나입니다. 빈번한 하위 그래프 마이닝은 그래프 분류, 인덱스 작성 및 그래프 클러스터링 목적으로 광범위하게 사용되는 그래프 마이닝 도메인의 하위 섹션입니다. 빈번한 하위 그래프 마이닝은 다양한 관점에서 다루어지며 도메인 예상에 따라 다른 방향으로 볼 수 있습니다. 본 논문에서는 빈번한 서브 그래프와 다양한 확장 가능한 기술을 대상으로하는 접근 방식을 조사했다.

1. Introduction

In recent years, many authors have deployed many algorithms and tools for converting voluminous data into useful and meaningful information [1].Frequent graph mining is one of the arms of such techniques when the data are represented in the form of graphs [2].Identification of frequent graphs / sub graphs in a graph database or in a single large graph is a part of frequent graph mining which can be used for classification tasks [3], graph clustering and building indices. Frequent sub graph discovery is a process of identifying frequently occurring sub graphs from a set of graphs (graph database) or a single large graph with frequency of occurrence is no less than a specified threshold. Since subgraph discovery is a portion of FSM (frequent subgraph mining), the term ‘FSM’ is used in the rest of this paper. The frequent sub graph mining is addressed from various perspectives based upon the requirement and domain expectations. Also it is viewed from various directions using various approaches. For example, Borgelt and Berthold [4] studied HIV-screening dataset and found active chemical structures in it by contrasting the support of frequent graphs between various different classes. Deshpande et.al [5] classified chemical structures by considering frequent patterns as a cardinal feature. Huan et.al [6] studied protein structure families by applying frequent graph mining techniques. To perform graph search in a faster manner, Yan et.al [7] used frequent graph patterns as indexing features.
Also in most of the chemical applications, the end-user is not only interested in finding frequent graphs (which reveal about the prediction of biochemical activities) but in identifying significant patterns (which may serve as catalysts for some biochemical activities) which seldom occur. So with regard to graph classification, still investigations are carried out to identify which substructure (frequent sub graphs / significant sub graphs) has the cardinal influence (biggest contribution) to the classification. In this paper, a survey is limited on enunciating few existing scalable techniques to find frequent sub graphs in a graph database / in a single large graph.

최근에는 많은 저자들이 방대한 데이터를 유용하고 의미있는 정보로 변환하기위한 많은 알고리즘과 도구를 배포했습니다 [1]. 그래프의 형태로 데이터를 표현할 때 빈번한 그래프 마이닝은 이러한 기술의 장점 중 하나입니다 [2]. 그래프 데이터베이스 또는 하나의 큰 그래프에서 빈번한 그래프 / 하위 그래프의 식별은 분류 작업 [3], 그래프 클러스터링 및 빌딩 인덱스에 사용할 수 있는 빈번한 그래프 마이닝의 일부입니다. 빈번한 하위 그래프 발견은 일련의 그래프 (그래프 데이터베이스)에서 자주 발생하는 하위 그래프를 식별하는 프로세스이거나 발생 빈도가 지정된 하나의 큰 그래프가 지정된 임계값 이상입니다. 하위 그래프 검색은 FSM (자주 하위 그래프 마이닝)의 일부이므로 이 백서의 나머지 부분에서 ‘FSM’이라는 용어가 사용됩니다. 하위 그래프 마이닝 빈도는 요구 사항 및 도메인 기대치를 기반으로 다양한 관점에서 해결됩니다. 또한 다양한 접근 방식을 사용하여 다양한 방향에서 볼 수 있습니다. 예를 들어 Borgelt와 Berthold [4]는 HIV 선별 데이터 세트를 연구하고 다양한 클래스 간 빈번한 그래프의 지원을 대조하여 활성 화학 구조를 발견했습니다. Deshpande 등 [5]은 빈번한 패턴을 기본 특징으로 간주하여 화학 구조를 분류했습니다. Huan 등 [6]은 빈번한 그래프 마이닝 기법을 적용하여 단백질 구조 패밀리를 연구했습니다. Yan et.al [7]은 더 빠른 방식으로 그래프 검색을 수행하기 위해 빈번한 그래프 패턴을 색인 기능으로 사용했습니다.
또한 대부분의 화학 응용 분야에서 최종 사용자는 빈번한 그래프 (생화학 적 활동 예측에 관한)를 찾는 것뿐만 아니라 거의 발생하지 않는 중요한 패턴 (일부 생화학 적 활동의 촉매제 역할을 할 수 있음)을 찾는데 관심이 있습니다. 따라서 그래프 분류와 관련하여 분류에 주요 영향을 미치는 하위 구조 (자주 하위 그래프 / 유의 하위 그래프)를 식별하기 위해 여전히 조사가 수행됩니다. 본 논문에서는 그래프 데이터베이스에서 하나의 큰 그래프로 빈번한 하위 그래프를 찾기 위해 기존의 확장 가능한 기술 몇 가지를 발표하는 설문 조사로 제한됩니다.

2. Strategy for finding Frequent Subgraphs

As stated earlier, frequent sub graphs are more useful in classification tasks, graph clustering and characterization of graph sets. As the sub graph size decreases drastically, the graph pattern size grows exponentially. This may tend to drag some serious issues like

  • Identification of frequent sub graphs may take more time.
  • More sub graphs information may possibly hinder the task of identifying graphs which are more interesting but not frequent and which are not but still frequent.

To effectively solve the first task, scalable algorithms are recommended which generate frequent sub graphs in a search space [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 and 21]. The second task can be solved by preciously identifying significant graphs / patterns in a given graph database or in a single large graph and how frequently they occur [22, 24, 25, 26]. It is also to be noted that, finding frequently occurring sub graphs in a graph directly implies to the problem of enumerating sub graphs in a given graph which is a NP-Hard Problem [8].

앞서 언급 한 것처럼 빈번한 하위 그래프는 분류 작업, 그래프 클러스터링 및 그래프 세트 특성 분석에 더 유용합니다. 하위 그래프 크기가 ​​급격히 감소함에 따라 그래프 패턴 크기가 기하급수적으로 증가합니다. 이것은 다음과 같은 심각한 문제를 유발할 수 있습니다

  • 빈번한 하위 그래프를 식별하는 데 시간이 더 걸릴 수 있습니다.
  • 더 많은 서브 그래프 정보는 아마도 더 흥미롭지만 빈번하지 않은 그래프를 식별하는 작업을 방해 할 수 있습니다.

첫 번째 작업을 효과적으로 해결하려면 검색 공간에서 빈번한 하위 그래프를 생성하는 확장 가능한 알고리즘이 권장됩니다 [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 및 21]. 두 번째 과제는 주어진 그래프 데이터베이스 나 하나의 큰 그래프에서 중요한 그래프 / 패턴을 귀중하게 식별하고 얼마나 자주 발생 하는지를 파악하여 해결할 수 있습니다 [22, 24, 25, 26]. 그래프에서 자주 발생하는 서브 그래프를 찾는 것은 NP-Hard 문제인 주어진 그래프에서 서브 그래프를 열거하는 문제를 직접적으로 의미합니다.

3. Approaches in targeting Frequent subgraph discovery problem

The approaches for identifying FSM generate candidate sub graphs which are used to count how many instances are present in the given graph database.

FSM을 수행하는 방법은 주어진 그래프 데이터베이스에 몇 개의 인스턴스가 있는지 계산하는 데 사용될 후보 하위 그래프를 생성하는 방법으로 접근합니다.

3.1 Candidate Generation

It is one of the phases in frequent subgraph mining in which candidate subgraphs are systematically generated. Some of the strategies which identify candidate subgraphs are listed below:

  1. Level- wise Join:
    Two subgraphs of size ‘k’ are combined together to form a (k+1) candidate subgraph.
  2. Rightmost path extension:
    In this candidate generation strategy, vertices are added on the rightmost path of a k-subtree to form (k+1) subtree.

And other strategies such as Extension and Join, Right-and-Left tree Join and Equivalence class based extension are also used in candidate generation phase.

후보 하위 그래프가 체계적으로 생성되는 빈번한 하위 그래프 마이닝의 단계 중 하나입니다. 후보 하위 그래프를 식별하는 몇 가지 전략은 다음과 같습니다.

  • 수준별 조인 : 크기가 k 인 두 개의 하위 그래프가 결합되어 (k + 1) 후보 하위 그래프를 형성합니다.
  • 가장 오른쪽 경로 확장 : 이 후보 생성 전략에서 정점은 k- 하위 트리의 가장 오른쪽 경로에 추가되어 (k + 1) 하위 트리를 형성합니다.

또한 확장 및 결합, 오른쪽 및 왼쪽 트리 결합 및 동등성 클래스 기반 확장과 같은 다른 전략도 후보 생성 단계에서 사용됩니다.

There are two approaches by which frequent sub graphs can be found in a given graph / database.

주어진 그래프/데이터베이스에서 빈번한 하위 그래프를 찾을 수 있는 두 가지 방법이 있습니다.

  • Apriori-based approach
  • Pattern-growth approach

The quint essential behind apriori –based sub graph discovery problem is to join two frequently occurring subgraphs namely G1 and G2 and check whether the resultant graph (whose size is one vertex more than the two sub graphs G1and G2) is frequent or not(Figure 1).

Apriori 기반의 하위 그래프 발견 문제의 근본 원인은 자주 발생하는 두 개의 하위 그래프 인 G1 및 G2를 결합하고 결과 그래프 (그 크기가 두 개의 하위 그래프 G1 및 G2보다 하나 이상의 정점이 더 있는지)가 빈번하지 않은지 확인하는 것입니다 (그림 1 ).

3.2 Apriori – Based Algorithms

The Apriori-based approach is similar to frequent item-set mining and it is Recursive [27]. Some of the Apriori-based frequent sub graph mioning algorithms are listed below.

Apriori 기반 접근 방식은 빈번한 항목 세트 마이닝과 유사하며 재귀 적입니다 [27]. Apriori 기반 빈번한 서브 그래프 마이닝 알고리즘 중 일부는 다음과 같습니다.

  • AGM[11]
  • FSG[12]
  • Edge disjoint path-join algorithm[13]

AGM

This algorithm generates candidate graphs, merges any two candidate graphs at an instant and check whether the resultant graph is a sub graph in a given graph / graph database or not.Here, the size of a graph is denoted by the number of vertices present in that graph. Two graph of size ‘k’ can be merged together to form a resultant graph of size ‘k+1’.One or more resultant graphs of size ‘k+1’ is again fed into the apriori algorithm to obtain a resultant graph of size ‘k+2’. So, in each and every iteration of this algorithm, two graphs (arbitrarily chosen from the candidate set) are merged together to form a resultant graph whose size is increased by one vertex. In short, it is a vertex-based candidate generation algorithm.

이 알고리즘은 후보 그래프를 생성하고 두 개의 후보 그래프를 즉시 병합하고 결과 그래프가 주어진 그래프 / 그래프 데이터베이스의 하위 그래프인지 여부를 확인합니다. 여기서 그래프의 크기는 그 그래프에 있는 정점의 수로 표시됩니다. 크기 ‘k’의 두 그래프를 병합하여 크기 ‘k + 1’의 결과 그래프를 형성 할 수 있습니다. 크기 ‘k + 1’의 하나 이상의 결과 그래프를 다시 Apriori 알고리즘에 공급하여 크기의 결과 그래프를 얻습니다. ‘k + 2’. 따라서이 알고리즘을 반복 할 때마다 두 개의 그래프 (후보 세트에서 임의로 선택됨)가 병합되어 크기가 하나의 정점 씩 증가하는 결과 그래프가 형성됩니다. 요컨대, 이것은 버텍스 기반 후보 생성 알고리즘입니다.

FSG

It adopts with edge-based candidate generation method. Here, the size of a graph denotes the number of edges present that graph. Similar to vertex based candidate generation method, two graphs of size ‘k’ are merged together to form resultant graphs of size ‘k+1’ which should also be frequent. So in and every iteration, it generates candidate sub graphs whose size is exactly 1 greater than the previous frequent ones. Candidate pruning is also done if the generated candidate does not satisfy the minimum threshold.

Edge 기반 후보 생성 방법을 채택합니다. 여기서 그래프의 크기는 해당 그래프에있는 Edge 수를 나타냅니다. Vertex 기반 후보 생성 방법과 유사하게 크기 ‘k’의 두 개의 그래프가 병합되어 크기 ‘k + 1’의 결과 그래프가 형성됩니다. 따라서 모든 반복에서 크기가 이전의 빈번한 크기보다 정확히 1 인 후보 하위 그래프를 생성합니다. 생성 된 후보가 최소 임계 값을 만족하지 않는 경우 후보 제거도 수행됩니다.

Edge – disjoint path join algorithm

This algorithm abides with apriori – based approach which uses edge-disjoint paths as building blocks. Here, the measuring factor is the number of disjoint paths (Two paths are said to be disjoint if they do not share a common edge) a graph possesses. Two candidate graphs of ‘k’ disjoint paths are merged together to form a resultant graph containing ‘k+1’ disjoint paths.

이 알고리즘은 경계 분리 경로를 빌딩 블록으로 사용하는 선험 기반 접근 방식을 따릅니다. 여기서 측정 계수는 그래프에있는 분리 된 경로의 수입니다 (두 개의 경로가 공통 에지를 공유하지 않으면 두 개의 경로가 분리 된 것으로 나타납니다). ‘k’분리 경로의 두 후보 그래프가 병합되어 ‘k + 1’분리 경로를 포함하는 결과 그래프를 형성합니다.

Comparative study between AGM and FSG

In AGM, the candidate generation of the frequent induced sub graph is constructed by the level-wise search in terms of the size of the sub graph. The adjacency matrix of the graph representation is combined with this efficient level-wise search of the frequent canonical matrix code [28].Overall analysis showed that the computational time complexity of directed graphs is less than that of undirected graphs due to the fact that the possible edge directions in directed graphs bear more sub graph patterns and their frequency will ultimately be less. Also the computational complexity of small graphs is lesser than larger graphs. Experiments reported in [16] showed that AGM achieves good performance in dense synthetic graph datasets and took 40 minutes to 8 days (approx.) to tabulate all frequent sub graphs in a dataset containing 300 chemical compounds, as the minimum support threshold varies between 10% to 20%.

AGM에서, 빈번한 유도 서브 그래프의 후보 생성은 서브 그래프의 크기 측면에서 레벨 단위 검색에 의해 구성된다. 그래프 표현의 인접 행렬은 빈번한 표준 행렬 코드의 효율적인 수준별 검색과 결합됩니다 [28]. 전체 분석에 따르면 방향 그래프의 계산 시간 복잡도는 방향 그래프의 계산 시간 복잡도가 무지향 그래프보다 작다는 사실이 밝혀졌습니다. 유방향 그래프에서 가능한 에지 방향은 더 많은 서브 그래프 패턴을 가지며 그 주파수는 궁극적으로 적습니다. 또한 작은 그래프의 계산 복잡도는 큰 그래프보다 작습니다. [16]에보고 된 실험에 따르면 AGM은 밀도가 높은 합성 그래프 데이터 세트에서 우수한 성능을 달성하고 최소 지원 임계 값이 10 사이에서 변하기 때문에 300 개의 화합물을 포함하는 데이터 세트에서 빈번한 하위 그래프를 모두 표시하는 데 40 분에서 8 일 (약)이 걸렸습니다. 10 % 내지 20 %.

In FSG, frequent 1-edge and 2-edge graphs are enumerated and from these two basic sets candidate graphs whose size greater than the previous ones are generated. It only finds subgraphs that are connected. This is beneficial because it is necessary to consider disconnected combinations of frequent sub graphs. It uses canonical labelling (A canonical code is a unique code of a given graph and it is always be the same no matter how the graphs are represented, as long as those graphs have the same topological structure and the same labelling of edges and vertices) to compare two sub graphs. Computing canonical labels is equivalent to determining isomorphism between graphs. If two graphs have the same canonical labelling then they are isomorphic with each other and further it is under investigation whether they belong to class P or NP-Complete[29].

FSG에는 빈번한 1- 에지 및 2- 에지 그래프가 열거되며이 두 가지 기본 집합에서 이전보다 큰 크기의 후보 그래프가 생성됩니다. 연결된 하위 그래프만 찾습니다. 이것은 빈번한 하위 그래프의 연결이 끊긴 조합을 고려해야 하기 때문에 유리합니다. 표준 레이블링을 사용합니다 (표준 코드는 주어진 그래프의 고유한 코드이며 그래프가 동일한 토폴로지 구조와 가장자리 및 정점의 동일한 레이블을 갖는 한 그래프가 어떻게 표시 되든 상관없이 항상 동일합니다) 두 개의 하위 그래프를 비교합니다. 표준 레이블을 계산하는 것은 그래프 간 동형을 결정하는 것과 같습니다. 만약 두 개의 그래프가 동일한 표준 레이블링을 가지고 있다면, 그것들은 서로 동형이며 클래스 P에 속하는지 아니면 NP-Complete [29]에 속하는지 조사 중입니다.

3.3 Pattern Growth Approach

A pattern-growth approach extends a frequent sub graph by adding an extra edge in every possible position. The overhead in joining two sub graphs of size ‘k’( where ‘k’ is large) to form a graph of size ‘k+1’ is avoided in this approach. But the significant drawback here is while adding an extra edge in every possible position, the same sub graph can be discovered many times leading to duplication in candidate generation phase. This can be considerably eliminated by using rightmost extension technique. PatternGrowth approach algorithm include SPIN[17], Mofa[4], gSpan[35], FFSM[16], and Gaston[19].

패턴 성장 접근법은 가능한 모든 위치에 여분의 모서리를 추가하여 빈번한 하위 그래프를 확장합니다. 이 방법에서는 크기 ‘k + 1’의 두 개의 하위 그래프 ‘k'(여기서 ‘k’가 큰)를 결합하여 오버 헤드를 피할 수 있습니다. 그러나 여기서 중요한 단점은 가능한 모든 위치에 여분의 에지를 추가하는 동안 동일한 하위 그래프가 여러 번 발견되어 후보 생성 단계에서 중복을 초래할 수 있다는 것입니다. 가장 오른쪽 확장 기술을 사용하면이를 제거 할 수 있습니다. PatternGrowth 접근 알고리즘에는 SPIN [17], Mofa [4], gSpan [35], FFSM [16] 및 Gaston [19]이 포함됩니다.

MoFa: (Molecular Fragments Identification Technique)

It finds core structures (sub graphs) which are found in all given molecular structures and generates an embedding list. In the next level, each and every structure present in the embedding list is extended by adding an edge in all possible ways which generates different structures. It uses pruning technique to suppress support computation and performing extension operation only to the embedding list structures.
Here multiple reporting of the same substructure (redundancy) arises and it can be suppressed by maintaining a list of frequent substructures and withdrawing new ones that are identical to already known/existing ones.

주어진 모든 분자 구조에서 발견되고 포함 목록을 생성하는 핵심 구조 (하위 그래프)를 찾습니다. 다음 단계에서, 매입 목록에 존재하는 각각의 모든 구조는 다른 구조를 생성하는 가능한 모든 방법으로 Edge를 추가하여 확장됩니다. 프루닝 기술을 사용하여 지원 계산을 억제하고 임베드 목록 구조에 대해서만 확장 조작을 수행합니다.
여기서 동일한 하위 구조 (중복성)에 대한 여러보고가 발생하며 빈번한 하위 구조 목록을 유지하고 이미 알려진 / 기존 구조와 동일한 새 구조를 철회하여 억제 할 수 있습니다.

SPIN: (Spanning Tree based Maximal Graph Mining)

The crux of this algorithm is to mine sub graphs that are not a part of any other frequent sub graph. It uses spanning tree approach to discover maximal frequent sub graphs.First this algorithm generates maximal frequent tree pattern from a Graph database and enumerates the equivalence class of a tree. Then it constructs maximal frequent sub graph from the constructed trees.

이 알고리즘의 핵심은 다른 빈번한 하위 그래프의 일부가 아닌 하위 그래프를 마이닝 하는 것입니다. 스패닝 트리 접근 방식을 사용하여 최대 빈번한 하위 그래프를 발견합니다. 먼저이 알고리즘은 그래프 데이터베이스에서 최대 빈번한 트리 패턴을 생성하고 트리의 등가 클래스를 열거합니다. 그런 다음 구성된 트리에서 최대 빈번한 하위 그래프를 구성합니다.

gSpan

This algorithm generates a tree-like structure (DFS Code tree) over all possible patterns (subgraphs), in which each and every node represents a DFS Code[35] for a graph pattern. The i th level of the code tree contains DFS Code of all subgraphs of size (i-1). Each (i-1) subgraph is generated by adding one extra edge to subgraphs which are present in the (i-2) th level of the tree.Instead of embedding the entire subgraph in each and every node it only preserves the transaction list for each discovered subgraph. Also pruning is done by deleting nodes which do not satisfy minimal DFS Code[35].

이 알고리즘은 가능한 모든 패턴 (서브 그래프)에 대해 트리와 유사한 구조 (DFS 코드 트리)를 생성합니다. 여기서 각 노드는 그래프 패턴에 대한 DFS 코드 [35]를 나타냅니다. 코드 트리의 i 번째 레벨에는 크기 (i-1)의 모든 하위 그래프에 대한 DFS 코드가 포함됩니다. 각 (i-1) 서브 그래프는 트리의 (i-2) 번째 레벨에있는 서브 그래프에 하나의 추가 에지를 추가하여 생성됩니다. 각 서브 그래프를 각 노드마다 임베드하는 대신 트랜잭션 목록 만 보존합니다. 각각의 발견 된 하위 그래프. 또한 최소 DFS 코드를 만족하지 않는 노드를 삭제하여 제거를 수행합니다 [35].

All the above algorithms are based upon Prefix Span[33],TreeMinerV[15] and FREQT[32].

Most of the pattern-growth approaches use edge-extension strategy and a potential problem with edge -extension is that the same subgraph can be discovered many times. Among these algorithms, gSPAN avoids the duplicated graph discovery by right most extension technique, in which the extension is possible only on the right-most path[34]. Any depth first path from a source Vo to an arbitrary sink Vn is declared as the right most path from Vo to Vn.

대부분의 패턴 성장 접근법은 Edge 확장 전략을 사용하며 Edge 확장의 잠재적 문제점은 동일한 하위 그래프를 여러번 발견할 수 있다는 것입니다. 이 알고리즘들 중에서 gSPAN은 가장 오른쪽의 확장 기술에 의해 중복된 그래프 발견을 피하며, 가장 오른쪽 경로에서만 확장이 가능하다 [34]. 소스 Vo에서 임의의 싱크 Vn까지의 깊이 우선 경로는 Vo에서 Vn까지의 가장 오른쪽 경로로 선언됩니다.

Apart from frequent sub graph mining algorithms, constraint based subgraph mining have also been proposed. Mining coherent subgraph were studied by Huan et al[6].To discover exact dense frequent sub graphs, Yan et al[31] proposed two algorithms called as Splat and Closecut. Wang et al[23] developed a frequent graph mining algorithm(disk-based) for a voluminous graph database. To mine closed and maximal frequent subtrees, Chi et.al[26] proposed a new algorithm called as CMTreeMiner. There are also some studies to find frequent subgraphs in a large graph. While defining the support of a graph in a large graph, there exists two or more same sub graphs which are frequent and are overlapped (multiple embedding of a subgraph in a large graph may overlap). If multiple non- identical embeddings of subgraphs are allowed, then there is a possibility of violation of anti-monocity property ( if the k-size subgraph is frequent only if all of its subgrpahs are frequent) which is a cardinal feature for the most frequent mining algorithm. Therefore in order to find an appropriate support definition, Kuramochi and Karypsis[12] coined definitions for overlaps and framed two algorithms namely HSIGRAM (horizontal approach abiding Breadth-First-Strategy) and VSIGRAM (vertical approach abiding depth first strategy) to discover all frequent subgraphs.

하위 그래프 마이닝 알고리즘을 자주 사용하는 것 외에도 제약 기반 하위 그래프 마이닝도 제안되었습니다. Yanan 등 [31]은 Huan et al [6]에 의해 마이닝 코 히어 런트 서브 그래프가 연구되었으며, 정확한 고밀도 자주 서브 그래프를 발견하기 위해 Splat과 Closecut이라는 두 가지 알고리즘이 제안되었다. Wang 등 [23]은 방대한 그래프 데이터베이스를위한 빈번한 그래프 마이닝 알고리즘 (디스크 기반)을 개발했습니다. Chi et.al [26]은 폐쇄적이고 최대 빈번한 서브 트리를 채굴하기 위해 CMTreeMiner라는 새로운 알고리즘을 제안했다. 큰 그래프에서 빈번한 하위 그래프를 찾는 연구도 있습니다. 큰 그래프에서 그래프의 지원을 정의하는 동안 빈번하고 겹치는 두 개 이상의 동일한 하위 그래프가 있습니다 (큰 그래프에서 하위 그래프를 여러 개 포함하면 겹칠 수 있음). 여러 개의 동일하지 않은 하위 그래프 임베딩이 허용되는 경우, 가장 빈번한 기본 기능인 반 모노시티 속성 (k- 크기 하위 그래프가 모든 하위 그룹이 빈번한 경우에만 빈번한 경우)을 위반할 가능성이 있습니다. 마이닝 알고리즘. 따라서 적절한 지원 정의를 찾기 위해 Kuramochi와 Karypsis [12]는 중복에 대한 정의를 만들어 두 가지 알고리즘, 즉 HSIGRAM (가로 우선 접근을 가로로하는 수평 접근)과 VSIGRAM (깊이 우선 전략을 따르고 수직으로 접근)이라는 두 알고리즘을 정의하여 모든 빈번한 하위 그래프 발견했습니다.

3.4 Significant Subgraphs

While deploying graph applications based on frequent graph discovery, first all the frequent sub graphs are mined and then significant patterns are identified and selected based upon objective functions (user-defined)for different graph applications. Inorder to identify frequently occurring sub graphs it is necessary to populate all sub graphs and calculate their p-value one after the other. This is a very time consuming process because a low frequency threshold means an exponential pattern set and the mining process is slow. Also most of the frequent patterns are redundant and not worth computing at all. So there are some recent studies to mine significant sub graphs based upon objective functions (user-defined) to overcome the scalability issues. For example, Kudo et al[20] proposed a branch-and-bound approach, Gboost, for graph classification and Saigo et al[25] proposed an intuitive mining algorithm based on PLS(partial least square regression) to mine significant pattern. GrapSig algorithm is proposed by Ramu & Singh[24] to mine Significant and Frequent subgraph in which graphs are represented as feature vectors. And a structural Leap Search Mining Strategy is proposed by Yan et al.[14] to identify significant Subgraphs.

빈번한 그래프 탐색을 기반으로 그래프 응용 프로그램을 배포하는 동안 먼저 모든 빈번한 하위 그래프가 마이닝 된 다음 다른 그래프 응용 프로그램에 대한 목적 함수 (사용자 정의)를 기반으로 중요한 패턴이 식별되고 선택됩니다. 자주 발생하는 하위 그래프를 식별하려면 모든 하위 그래프를 채우고 p- 값을 하나씩 계산해야합니다. 낮은 주파수 임계 값은 지수 패턴 세트를 의미하고 마이닝 프로세스는 느리기 때문에 시간이 많이 걸리는 프로세스입니다. 또한 대부분의 빈번한 패턴은 중복되어 전혀 컴퓨팅 할 가치가 없습니다. 따라서 확장 성 문제를 극복하기 위해 목적 함수 (사용자 정의)를 기반으로 중요한 하위 그래프를 마이닝하는 최근 연구가 있습니다. 예를 들어, Kudo et al [20]은 그래프 분류를 위해 Gboost (branch-and-bound) 접근법을 제안했고 Saigo et al [25]는 중요한 패턴을 채굴하기 위해 PLS (partial least square square regression)에 기반한 직관적 인 마이닝 알고리즘을 제안했습니다. Ramu & Singh [24]는 GrapSig 알고리즘을 제안하여 그래프가 특징 벡터로 표현되는 중요하고 빈번한 서브 그래프를 채굴합니다. 그리고 Yan 등은 구조적 도약 검색 전략을 제안한다. 중요한 하위 그래프를 식별합니다.

3.5 Other Applications

Apart from Graph classification, Clustering and indexing FSM has many applications in interdisciplinary research such as chemical informatics [4], bioinformatics [30]. For example, Maximal subgraph mining is used in discovering structure motifs in a graph of homology protein where they encode the maximal structure commonalities within the group. It also has a cardinal influence in social networking and ego networks as well.

그래프 분류 외에도 클러스터링 및 색인화 FSM은 화학 정보학 [4], 생물 정보학 [30]과 같은 학제 간 연구에 많은 응용 분야를 가지고 있습니다. 예를 들어, Maximal subgraph mining은 그룹 내에서 최대 구조 공통성을 인코딩하는 상 동성 단백질의 그래프에서 구조 모티프를 발견하는 데 사용됩니다. 또한 소셜 네트워킹 및 자아 네트워크에도 중요한 영향을 미칩니다.

Below tabular column shows a list of FSM algorithms in a 2D matrix form in which i th row and j th column has a value x.

아래 표 열에는 i 번째 행과 j 번째 열의 값이 x 인 2D 행렬 형식의 FSM 알고리즘 목록이 표시됩니다.

Where:

  • (ith row) i – denotes the name of the Algorithm
  • (jth row) j – candidate generation method
  • x – candidate graph representation

4. Conclusion

In this paper, few frequent subgraph mining algorithms are discussed. In general, mining frequent graph patterns takes a long time so several methods to explore significant subgraphs without generating the entire pattern set are also considered. These methods usually reduce the computational complexity but still more investigations are being carried out to identify what kind of subgraphs are most compact and representative for a given application. Since the generated candidate set is also too large and all the frequent patterns are not useful, new emerging techniques deploy approximate algorithms to find frequent sub graphs.

본 논문에서는 빈번한 하위 그래프 마이닝 알고리즘에 대해 설명하지 않습니다. 일반적으로 빈번한 그래프 패턴 마이닝에는 시간이 오래 걸리므로 전체 패턴 세트를 생성하지 않고 중요한 하위 그래프를 탐색하는 몇 가지 방법도 고려됩니다. 이러한 방법은 일반적으로 계산 복잡성을 감소 시키지만 주어진 응용 분야에 대해 어떤 종류의 하위 그래프가 가장 콤팩트하고 대표적인지를 식별하기 위해 더 많은 조사가 수행되고 있습니다. 생성된 후보 세트도 너무 커서 모든 빈번한 패턴이 유용하지 않기 때문에 새로운 신기술은 근사 알고리즘을 사용하여 빈번한 하위 그래프를 찾습니다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중

%d 블로거가 이것을 좋아합니다: