ในการขุดโครงสร้างเคอร์เนลกราฟคือฟังก์ชันเคอร์เนลที่คำนวณผลคูณภายในบนกราฟ [ ^{1 ]} เคอร์เนลกราฟสามารถเข้าใจได้โดยสัญชาตญาณว่าเป็นฟังก์ชันที่วัดความคล้ายคลึงกันของกราฟเป็นคู่ๆ ฟังก์ชันเหล่านี้ช่วยให้อัลกอริธึ มการ ^{เรียน} รู้ แบบเคอร์เนลเช่นเครื่องสนับสนุนเวกเตอร์สามารถทำงานบนกราฟได้โดยตรง โดยไม่ต้องทำการสกัดคุณลักษณะ เพื่อแปลงเป็น เวกเตอร์คุณลักษณะที่มีความยาวคงที่และมีค่าเป็นจำนวนจริงฟังก์ชันเหล่านี้พบได้ในชีวสารสนเทศศาสตร์ในเคมีสารสนเทศศาสตร์ (ในฐานะ เคอร์เนลโมเลกุลประเภทหนึ่ง^{[ 2 ]} ) และใน การ วิเคราะห์เครือข่ายสังคม^{[ 1 ]}

แนวคิดของเคอร์เนลกราฟมีมาตั้งแต่ปี 1999 เมื่อ D. Haussler ^{[ 3 ]}ได้แนะนำเคอร์เนลแบบคอนโวลูชันบนโครงสร้างแบบไม่ต่อเนื่อง คำว่าเคอร์เนลกราฟได้รับการบัญญัติอย่างเป็นทางการมากขึ้นในปี 2002 โดย RI Kondor และJ. Lafferty ^{[ 4 ]} ในฐานะเคอร์เนลบนกราฟ กล่าวคือ ฟังก์ชันความคล้ายคลึงกันระหว่างโหนดของกราฟเดียว โดยมีกราฟไฮเปอร์ลิงก์ของเวิลด์ไวด์เว็บ เป็นแอปพลิเคชันที่แนะนำ ในปี 2003 Gärtner et al. ^{[ 5 ]} และ Kashima et al. ^{[ 6 ]} ได้กำหนดเคอร์เนลระหว่างกราฟ ในปี 2010 Vishwanathan et al.ได้นำเสนอกรอบการทำงานที่เป็นหนึ่งเดียวของพวกเขา^{[ 1 ]}ในปี 2018 Ghosh et al. ^{[ 7 ]}ได้อธิบายประวัติของเคอร์เนลกราฟและวิวัฒนาการของมันในช่วงสองทศวรรษ

เคอร์เนลกราฟแบบมาร์จินัลได้รับการพิสูจน์แล้วว่าช่วยให้สามารถทำนายพลังงานอะตอมของโมเลกุลอินทรีย์ขนาดเล็กได้อย่างแม่นยำ^{[ 8 ]}

ตัวอย่างของเคอร์เนลระหว่างกราฟคือเคอร์เนลการเดินแบบสุ่ม^{[ 5 ] [ 6 ]}ซึ่งในเชิงแนวคิดจะทำการเดินแบบสุ่มบนกราฟสองกราฟพร้อมกัน จากนั้นนับจำนวนเส้นทางที่สร้างขึ้นโดย การเดิน ทั้งสองครั้งซึ่งเทียบเท่ากับการทำการเดินแบบสุ่มบนผลคูณโดยตรงของกราฟทั้งสองคู่ และจากสิ่งนี้ สามารถสร้างเคอร์เนลที่สามารถคำนวณได้อย่างมีประสิทธิภาพ^{[ 1 ]}

ตัวอย่างอื่นคือเคอร์เนลกราฟ Weisfeiler-Leman ^{[ 9 ]}ซึ่งคำนวณหลายรอบของอัลกอริทึม Weisfeiler-Lemanจากนั้นคำนวณความคล้ายคลึงกันของกราฟสองกราฟเป็นผลคูณภายในของเวกเตอร์ฮิสโตแกรมของกราฟทั้งสอง ในเวกเตอร์ฮิสโตแกรมเหล่านั้น เคอร์เนลจะรวบรวมจำนวนครั้งที่สีปรากฏในกราฟในแต่ละรอบ โปรดทราบว่าในทางทฤษฎีเคอร์เนล Weisfeiler-Leman มีมิติอนันต์ เนื่องจากจำนวนสีที่เป็นไปได้ที่กำหนดโดยอัลกอริทึม Weisfeiler-Leman นั้นเป็นอนันต์ การจำกัดเฉพาะสีที่ปรากฏในกราฟทั้งสอง การคำนวณยังคงเป็นไปได้

• เคอร์เนลของต้นไม้เป็นกรณีพิเศษของกราฟที่ไม่เป็นวัฏจักร
• การขุดค้นโมเลกุลซึ่งเป็นกรณีพิเศษของกราฟหลายป้ายกำกับขนาดเล็ก