Việc khám phá các cấu trúc con phổ biến thường bao gồm hai bước. Ở bước đầu tiên, tạo ra các ứng viên cấu trúc con phổ biến. Tần suất của mỗi ứng viên được kiểm tra ở bước thứ hai. Hầu hết các nghiên cứu về khám phá cấu trúc con phổ biến tập trung vào việc tối ưu hóa bước đầu tiên vì bước thứ hai liên quan đến kiểm tra đẳng cấu đồ thị con có độ phức tạp tính toán quá cao (tức là NP-complete).
Có nhiều phương pháp khai thác cấu trúc con phổ biến:
Phương pháp dựa trên Apriori – Các thuật toán khai thác cấu trúc con phổ biến dựa trên Apriori chia sẻ các đặc điểm giống với thuật toán khai thác tập mục phổ biến dựa trên Apriori. Tìm kiếm đồ thị phổ biến bắt đầu từ các đồ thị có "kích thước" nhỏ, và tiến triển theo cách bottom-up bằng cách tạo ứng viên có thêm đỉnh, cạnh hoặc đường dẫn. Biểu diễn kích thước đồ thị dựa trên thuật toán được sử dụng.
Độ phức tạp thiết kế chính của các thuật toán khai thác cấu trúc con dựa trên Apriori là bước tạo ứng viên. Tạo ứng viên trong khai thác tập mục phổ biến là đơn giản. Ví dụ, giả sử có hai tập mục phổ biến kích thước-3: (abc) và (bcd). Ứng viên tập mục phổ biến kích thước-4 được tạo từ chúng dễ dàng là (abcd), thu được từ một phép join. Tuy nhiên, vấn đề tạo ứng viên trong khai thác cấu trúc con phổ biến khó hơn khai thác tập mục phổ biến, vì có nhiều cách để join hai cấu trúc con.
Phương pháp tăng trưởng mẫu (Pattern-Growth Approach) – Phương pháp dựa trên Apriori phải sử dụng chiến lược tìm kiếm theo chiều rộng (BFS) do tạo ứng viên theo cấp độ. Để xác định xem một đồ thị kích thước-(k+1) có phổ biến không, phải kiểm tra tất cả các đồ thị con kích thước-k tương ứng để lấy giới hạn trên của tần suất. Do đó, trước khi khai thác bất kỳ cấu trúc con kích thước-(k+1) nào, phương pháp kiểu Apriori thường phải hoàn thành khai thác cấu trúc con kích thước-k.
Do đó, BFS là cần thiết cho phương pháp kiểu Apriori. Ngược lại, phương pháp tăng trưởng mẫu linh hoạt hơn về chiến lược tìm kiếm. Nó có thể sử dụng cả BFS và tìm kiếm theo chiều sâu (DFS), phương pháp sau tiêu tốn ít bộ nhớ hơn.
Đồ thị tăng trưởng mẫu đơn giản nhưng không hiệu quả. Nút thắt cổ chai nằm ở việc mở rộng đồ thị không hiệu quả. Cùng một đồ thị có thể được tìm thấy nhiều lần. Ví dụ, có thể tồn tại n đồ thị (n-1)-cạnh khác nhau có thể được mở rộng thành cùng một đồ thị n-cạnh. Việc khám phá lại cùng một đồ thị nhiều lần là không hiệu quả về mặt tính toán. Chúng ta gọi một đồ thị được khám phá lần thứ hai là đồ thị trùng lặp.
Để giảm việc tạo ra đồ thị trùng lặp, mỗi đồ thị phổ biến nên được mở rộng càng bảo thủ càng tốt. Nguyên tắc này dẫn đến thiết kế một số thuật toán mới. Thuật toán spanning được thiết kế để giảm việc tạo ra đồ thị trùng lặp. Nó không cần tìm kiếm các đồ thị phổ biến đã khám phá trước đó để phát hiện trùng lặp. Nó không mở rộng bất kỳ đồ thị trùng lặp nào, nhưng vẫn đảm bảo khám phá tập hợp hoàn chỉnh các đồ thị phổ biến.