빈번한 하부 구조의 발견은 일반적으로 두 단계로 구성됩니다. 첫 번째 단계에서는 자주 하위 구조 후보를 만들 수 있습니다. 모든 후보자의 빈도는 두 번째 단계에서 테스트됩니다. 빈번한 하위 구조 발견에 대한 대부분의 연구는 첫 번째 단계의 최적화에 초점을 맞추고 있습니다. 두 번째 단계는 계산 복잡성이 과도하게 높은(즉, NP-완전) 하위 그래프 동형 테스트를 포함하기 때문입니다.
빈번한 하부 구조 마이닝에는 다음과 같은 다양한 방법이 있습니다 -
선험적 접근 방식 − Apriori 기반의 빈번한 하위 구조 마이닝 알고리즘은 Apriori 기반의 빈번한 항목 집합 마이닝 알고리즘과 동일한 기능을 보냅니다. 빈번한 그래프 검색은 "크기"가 작은 그래프에서 시작하여 후보에 추가 정점, 모서리 또는 경로를 갖도록 하는 상향식 방식으로 진행됩니다. 그래프 크기의 표현은 사용된 알고리즘을 기반으로 합니다.
Apriori 기반 하위 구조 마이닝 알고리즘의 주요 설계 복잡성은 후보 생성 단계입니다. 빈번한 아이템 집합 마이닝의 후보 생산은 사실입니다. 예를 들어, 크기가 3인 두 개의 빈번한 항목 집합((abc) 및 (bcd))이 있다고 가정합니다.
그들로부터 생성된 크기 4의 빈번한 항목 집합 후보는 조인에서 쉽게(abcd) 변경됩니다. 그러나 빈번한 하위 구조 마이닝의 후보 생성 문제는 두 개의 하위 구조를 결합하는 방법이 많기 때문에 빈번한 항목 집합 마이닝보다 어렵습니다.
패턴 성장 접근 방식 − Apriori 기반 접근 방식은 수준별 후보 생성 때문에 BFS(Breadth-First Search) 전략을 사용해야 합니다. size-(k + 1) 그래프가 자주 발생하는지 확인하려면 해당하는 모든 size-k 하위 그래프를 확인하여 빈도의 상한을 얻어야 합니다. 따라서 크기(k +1) 하위 그래프를 마이닝하기 전에 Apriori와 같은 접근 방식은 일반적으로 크기 k 하위 그래프의 마이닝을 완료해야 합니다.
따라서 Apriori와 같은 접근 방식에는 BFS가 필요합니다. 대조적으로, 패턴 성장 방법은 검색 방법과 관련하여 더 역동적입니다. 너비 우선 검색과 깊이 우선 검색(DFS)을 모두 사용할 수 있으며, DFS는 메모리를 덜 사용합니다.
패턴 성장 그래프는 간단하지만 효율적이지 않습니다. 병목 현상은 그래프 확장의 비효율에 있습니다. 같은 그래프를 여러 번 찾을 수 있습니다. 예를 들어, 동일한 n-에지 그래프로 확장될 수 있는 n개의 서로 다른 (n - 1)-에지 그래프가 존재할 수 있습니다. 동일한 그래프의 반복적인 발견은 계산적으로 비효율적입니다. 두 번째로 발견되는 그래프를 중복 그래프라고 합니다.
중복된 그래프의 생성을 줄일 수 있으므로 각 빈번한 그래프는 가능한 한 보수적으로 확장해야 합니다. 이 원칙은 몇 가지 새로운 알고리즘의 설계로 이어집니다. 스패닝 알고리즘은 중복 그래프의 생성을 줄이기 위해 설계되었습니다. 중복 탐지를 위해 이전에 발견된 빈번한 그래프를 검색할 필요가 없습니다. 중복 그래프를 확장하지는 않지만 빈번한 그래프의 전체 집합을 검색하도록 보장합니다.