มีความท้าทายหลายประการของการทำเหมืองลิงก์ ดังนี้:
ความสัมพันธ์ทางตรรกะ vs ทางสถิติ (Logical versus statistical dependencies) — มีสองประเภทของความสัมพันธ์ในโครงสร้างลิงก์กราฟ (แสดงความสัมพันธ์ตรรกะระหว่างวัตถุ) และความสัมพันธ์ทางความน่าจะเป็น (statistical relationships เช่น ความสัมพันธ์เชิงสหสัมพันธ์ระหว่างแอตทริบิวต์ของวัตถุที่โดยทั่วไปมีความสัมพันธ์ทางตรรกะ) การจัดการความสัมพันธ์เหล่านี้อย่างสอดคล้องก็เป็นความท้าทายสำหรับการทำเหมืองข้อมูลหลายสัมพันธ์ ซึ่งข้อมูลที่จะทำเหมืองอยู่ในหลายตาราง ต้องค้นหาความสัมพันธ์ตรรกะที่เป็นไปได้ระหว่างวัตถุ เพิ่มจากค้นหาความสัมพันธ์ทางความน่าจะเป็นมาตรฐานระหว่างแอตทริบิวต์ ทำให้ได้พื้นที่ค้นหาอย่างกว้างใหญ่ ซึ่งทำให้การหาโมเดลคณิตศาสตร์ที่เหมาะสมซับซ้อนขึ้น วิธีที่พัฒนาใน inductive logic programming อาจนำมาใช้ได้ ซึ่งเน้นการค้นหาความสัมพันธ์ทางตรรกะ
การสร้างคุณลักษณะ (Feature construction) — ในการจัดประเภทแบบลิงก์ (link-based classification) พิจารณาแอตทริบิวต์ของวัตถุและแอตทริบิวต์ของวัตถุที่เชื่อมโยงกับมัน อีกทั้งลิงก์เองก็อาจมีแอตทริบิวต์ วัตถุประสงค์ของการสร้างคุณลักษณะคือสร้างคุณลักษณะเดียวที่นิยามแอตทริบิวต์เหล่านี้ อาจรวม feature selection และ feature aggregation ใน feature selection จะมีเฉพาะคุณลักษณะที่แบ่งแยกได้ดีที่สุด
อินสแตนซ์ vs คลาส (Instances versus classes) — หมายถึงว่าโมเดลอ้างอิงถึงบุคคล (individuals) หรือคลาส (หมวดหมู่ทั่วไป) ของบุคคลอย่างชัดเจน ข้อดีของโมเดลแรกคือสามารถเชื่อมโยงบุคคลเฉพาะด้วยความน่าจะเป็นสูง ข้อดีของโมเดลหลังคือสามารถทำให้เป็นทั่วไปไปสู่สถานการณ์ใหม่กับบุคคลหลายคนได้
การใช้ข้อมูลที่มีป้ายกำกับและไม่มีป้ายกำกับอย่างมีประสิทธิภาพ (Effective use of labeled and unlabeled data) — กลยุทธ์ล่าสุดในการเรียนรู้คือผสมผสานข้อมูลที่มีป้ายกำกับและไม่มีป้ายกำกับ ข้อมูลไม่มีป้ายกำกับช่วยอนุมานการกระจายแอตทริบิวต์ของวัตถุ ลิงก์ระหว่างข้อมูลไม่มีป้ายกำกับ (test) ช่วยให้ใช้แอตทริบิวต์ของวัตถุที่เชื่อมโยงได้ ลิงก์ระหว่างข้อมูลมีป้ายกำกับ (training) และไม่มีป้ายกำกับ (test) ก่อให้เกิดความสัมพันธ์ที่ช่วยสร้างการอนุมานที่แม่นยำขึ้น
การทำนายลิงก์ (Link prediction) — ความท้าทายในการทำนายลิงก์คือ ความน่าจะเป็นก่อนหน้า (prior probability) ของลิงก์เฉพาะระหว่างวัตถุมักต่ำมาก มีวิธีการทำนายลิงก์หลายวิธีที่เสนอขึ้นจากหลายขนาดสำหรับวิเคราะห์ความใกล้ชิดของโหนดในเครือข่าย โมเดลความน่าจะเป็นก็ถูกเสนอเช่นกัน สำหรับชุดข้อมูลขนาดใหญ่ อาจมีประสิทธิภาพมากกว่าที่จะสร้างโมเดลลิงก์ในระดับสูงกว่า
สมมติฐานโลกปิด vs โลกเปิด (Closed versus open-world assumption) — วิธีแบบดั้งเดิมส่วนใหญ่สมมติว่าเรารู้เอนทิตีที่เป็นไปได้ทั้งหมดในโดเมน สมมติฐาน "โลกปิด" นี้ไม่เป็นจริงในแอปพลิเคชันโลกจริง การทำงานในพื้นที่นี้เกี่ยวข้องกับการนำเสนอภาษาสำหรับกำหนดการกระจายความน่าจะเป็นบนโครงสร้างสัมพันธ์ที่มีชุดวัตถุหลายชุด
