Có một số thách thức của khai thác liên kết như sau:
Phụ thuộc logic so với thống kê – Hai loại phụ thuộc nằm trong cấu trúc liên kết đồ thị (biểu diễn quan hệ logic giữa các đối tượng) và phụ thuộc xác suất (biểu diễn quan hệ thống kê, như tương quan giữa thuộc tính của các đối tượng, thường các đối tượng này có quan hệ logic). Việc xử lý mạch lạc các phụ thuộc này cũng là thách thức cho khai thác dữ liệu đa quan hệ, nơi dữ liệu cần khai thác tồn tại trong nhiều bảng. Cần tìm kiếm qua nhiều quan hệ logic có thể có giữa các đối tượng, ngoài việc tìm kiếm tiêu chuẩn qua các phụ thuộc xác suất giữa các thuộc tính. Điều này tạo ra không gian tìm kiếm khổng lồ, làm phức tạp thêm việc tìm mô hình toán học hợp lý. Các phương pháp phát triển trong lập trình logic quy nạp có thể được áp dụng ở đây, tập trung vào tìm kiếm qua các quan hệ logic.
Xây dựng đặc trưng – Trong phân loại dựa trên liên kết, xem xét các thuộc tính của một đối tượng và các thuộc tính của các đối tượng được kết nối với nó. Hơn nữa, các liên kết cũng có thể có thuộc tính. Mục tiêu của xây dựng đặc trưng là xây dựng một đặc trưng đơn lẻ định nghĩa các thuộc tính này. Có thể bao gồm chọn lọc đặc trưng và tổng hợp đặc trưng. Trong chọn lọc đặc trưng, chỉ các đặc trưng phân biệt nhất được bao gồm.
Thể hiện so với lớp – Điều này ám chỉ mô hình có đề cập rõ ràng đến các cá nhân hay các lớp (thể loại chung) của cá nhân. Lợi thế của mô hình trước là có thể kết nối các cá nhân cụ thể với xác suất cao. Ưu điểm của mô hình sau là có thể khái quát hóa cho các tình huống mới, với nhiều cá nhân.
Sử dụng hiệu quả dữ liệu có nhãn và không nhãn – Một chiến lược gần đây trong học tập là kết hợp cả dữ liệu có nhãn và không nhãn. Dữ liệu không nhãn có thể hỗ trợ suy luận phân phối thuộc tính đối tượng. Liên kết giữa dữ liệu không nhãn (test) cho phép sử dụng thuộc tính của các đối tượng liên kết. Liên kết giữa dữ liệu có nhãn (huấn luyện) và không nhãn (test) gây ra các phụ thuộc có thể giúp tạo ra suy luận chính xác hơn.
Dự đoán liên kết – Thách thức trong dự đoán liên kết là xác suất tiên nghiệm của một liên kết cụ thể giữa các đối tượng thường cực thấp. Có nhiều phương pháp dự đoán liên kết được đề xuất dựa trên các phép đo phân tích sự gần gũi của nút trong mạng. Các mô hình xác suất cũng đã được đề xuất. Với tập dữ liệu lớn, có thể hiệu quả hơn để mô hình hóa liên kết ở mức cao hơn.
Giả định thế giới đóng so với mở – Hầu hết các phương pháp truyền thống giả định rằng chúng ta biết tất cả các thực thể tiềm năng trong miền. Giả định "thế giới đóng" này không thực tế trong ứng dụng thực tế. Công việc trong lĩnh vực này liên quan đến việc giới thiệu một ngôn ngữ để định nghĩa phân phối xác suất trên các cấu trúc quan hệ chứa nhiều tập hợp đối tượng.