ml/ library Learn by doing
ALGORITHM 95 · PYTHON / JAVASCRIPT

Graph Embedding

เปลี่ยนโหนดในเครือข่ายเป็นเวกเตอร์ที่รักษาความสัมพันธ์

LEARNING LEVEL4
ขั้นสูงควรรู้มาก่อน · Spectral Clustering, graph และ MLP
ลองใน Playground

01Overall Concept

OVERALL CONCEPT

ไอเดียหลัก — Graph embedding เรียนเวกเตอร์ต่อโหนดจาก adjacency, random walks หรือ message passing เพื่อให้โหนดที่เชื่อมโยงหรือมีบริบทคล้ายกันอยู่ใกล้กันใน latent space

ลองนึกภาพว่า — เหมือนวางสมาชิกเครือข่ายบนแผนที่ให้เพื่อนและคนที่มีวงสังคมคล้ายกันอยู่ใกล้กัน

ตัวอย่างการนำไปใช้ — แนะนำเพื่อน ทำนายลิงก์ จำแนกโหนด และค้นหาชุมชน

02อธิบายภาษาคนเข้าใจง่ายๆ

เล่าแบบไม่ใช้ศัพท์ยาก

Graph Embedding เริ่มจากคำถามง่าย ๆ ว่า เปลี่ยนโหนดในเครือข่ายเป็นเวกเตอร์ที่รักษาความสัมพันธ์ วิธีนี้ไม่ได้มองข้อมูลทุกชนิดเหมือนกัน จึงต้องเตรียมข้อมูลให้ตรงกับสิ่งที่อัลกอริทึมใช้คำนวณ

เหมือนวางสมาชิกเครือข่ายบนแผนที่ให้เพื่อนและคนที่มีวงสังคมคล้ายกันอยู่ใกล้กัน ภาพเปรียบเทียบนี้ช่วยจำแก่นของวิธี แต่ตอนใช้งานจริงคอมพิวเตอร์ทำงานกับตัวเลขและกฎที่กำหนดไว้อย่างชัดเจน

Graph embedding เรียนเวกเตอร์ต่อโหนดจาก adjacency, random walks หรือ message passing เพื่อให้โหนดที่เชื่อมโยงหรือมีบริบทคล้ายกันอยู่ใกล้กันใน latent space พารามิเตอร์หลักใน Playground คือ จำนวนมิติ embedding เมื่อเลื่อนค่า ระบบจะคำนวณผลใหม่จากข้อมูลชุดเดิม จึงเปรียบเทียบการเปลี่ยนแปลงได้ตรง ๆ

ข้อมูลตัวอย่างบนหน้าใช้รูปแบบ รายการ edges หรือ adjacency matrix พร้อม feature ของโหนดถ้ามี · ตัวอย่าง 60–150 แถว เราแยกสิ่งที่อัลกอริทึมรับเข้าออกจากผลลัพธ์ เพื่อไม่เผลอส่งข้อมูลคำตอบหรือข้อมูลอนาคตเข้าไปตอนฝึก

งานที่เหมาะ เช่น แนะนำเพื่อน ทำนายลิงก์ จำแนกโหนด และค้นหาชุมชน ก่อนใช้จริงควรกำหนด metric ที่สัมพันธ์กับเป้าหมาย แล้วเปรียบเทียบกับวิธีพื้นฐานที่ง่ายกว่า

ภาพจำ: เวกเตอร์ต่อโหนดและ similarity ใน latent space · Playground แสดงผลเมื่อปรับ จำนวนมิติ embedding พร้อมจำข้อจำกัดสำคัญว่า นิยามเพื่อนบ้านกำหนดความหมายของ embedding และกราฟที่ลำเอียงส่งต่อความลำเอียงไปยังเวกเตอร์

03How it works

ค่อยๆ ทำไปด้วยกัน ตั้งแต่ข้อมูลแถวแรกจนถึงการตรวจคำตอบ

  1. เตรียมข้อมูลให้ตรงโจทย์

    รายการ edges หรือ adjacency matrix พร้อม feature ของโหนดถ้ามี ตรวจค่าที่หาย หน่วยของแต่ละคอลัมน์ และแยกข้อมูลประเมินก่อนเรียนรู้พารามิเตอร์จากข้อมูล

  2. ตั้งค่าที่ควบคุมพฤติกรรม

    ใช้ dimensions เพื่อกำหนดความจุของเวกเตอร์แต่ละโหนด และบันทึกค่าเริ่มต้นหรือ random seed เมื่อวิธีมีการสุ่ม เพื่อให้ทำซ้ำและเปรียบเทียบได้

  3. คำนวณแก่นของวิธี

    สร้างบริบทจาก random walks หรือเพื่อนบ้าน จากนั้น ทำนายโหนดบริบทจากเวกเตอร์ต้นทาง Playground ใช้ข้อมูลสาธิตชุดเดิมทุกครั้งเพื่อให้เห็นผลของ slider โดยไม่ถูกความสุ่มกลบ

  4. สร้างผลลัพธ์ที่นำไปอ่านได้

    อัปเดต embeddings ให้คู่จริงใกล้และคู่ลบไกล ผลที่ได้คือ เวกเตอร์ต่อโหนดและ similarity ใน latent space ตัวเลขหรือกลุ่มที่ได้ยังต้องตีความร่วมกับบริบทของข้อมูล

  5. ตรวจว่าคำตอบใช้ได้จริง

    เปรียบเทียบหลายค่าของ dimensions ด้วย metric ที่เหมาะ ดูทั้งผลรวมและกรณีที่พลาด แล้วทดสอบกับข้อมูลที่ไม่ใช้ปรับค่า โดยคำนึงถึงข้อจำกัดว่า นิยามเพื่อนบ้านกำหนดความหมายของ embedding และกราฟที่ลำเอียงส่งต่อความลำเอียงไปยังเวกเตอร์

เปิดตัวอย่างโค้ดเพื่อลองทำตาม →ตัวอย่างตัวเลขในเรื่องใช้ช่วยอธิบาย ส่วนโค้ดและ Playground ใช้ชุดข้อมูลสาธิตของแต่ละหน้าอ่านเอกสารอ้างอิงของเทคนิคนี้ ↗

ข้อมูล พารามิเตอร์ และภาพรวมการคำนวณ

DATA INX · features · no target yรายการ edges หรือ adjacency matrix พร้อม feature ของโหนดถ้ามี · ตัวอย่าง 60–150 แถว
CALCULATEGraph Embedding
dimensionsrandom_statevalidation
RESULTcluster labels + centersเวกเตอร์ต่อโหนดและ similarity ใน latent space · Playground แสดงผลเมื่อปรับ จำนวนมิติ embedding
เส้นทางของข้อมูล: จากค่าที่รับเข้า ผ่านการคำนวณด้วยพารามิเตอร์ ไปเป็นผลลัพธ์
INPUT

ข้อมูลที่รับเข้ามา

รายการ edges หรือ adjacency matrix พร้อม feature ของโหนดถ้ามี

รายการ edges หรือ adjacency matrix พร้อม feature ของโหนดถ้ามี · ตัวอย่าง 60–150 แถว
PARAMETERS

พารามิเตอร์ที่ใช้

dimensions
กำหนดความจุของเวกเตอร์แต่ละโหนด
random_state
ตรึงการสุ่มเพื่อให้ทดลองซ้ำและเปรียบเทียบได้
validation
เก็บข้อมูลส่วนหนึ่งไว้ตรวจคุณภาพกับตัวอย่างที่ไม่ใช้ฝึก
OUTPUT

ผลลัพธ์ที่ได้

เวกเตอร์ต่อโหนดและ similarity ใน latent space

เวกเตอร์ต่อโหนดและ similarity ใน latent space · Playground แสดงผลเมื่อปรับ จำนวนมิติ embedding
CALCULATION

คำนวณทีละขั้น

  1. 01

    สร้างบริบทจาก random walks หรือเพื่อนบ้าน

  2. 02

    ทำนายโหนดบริบทจากเวกเตอร์ต้นทาง

  3. 03

    อัปเดต embeddings ให้คู่จริงใกล้และคู่ลบไกล

ควรรู้อีกนิด — นิยามเพื่อนบ้านกำหนดความหมายของ embedding และกราฟที่ลำเอียงส่งต่อความลำเอียงไปยังเวกเตอร์

04Make it yours

Python · NumPy
# ติดตั้ง: pip install numpy# ดาวน์โหลด sample.csv จากหน้านี้ แล้ววางไว้ข้างสคริปต์import numpy as npdata = np.genfromtxt("graph-embedding-sample.csv", delimiter=",", skip_header=1)dimensions = 8edges = data[:, :2].astype(int); n = int(edges.max()) + 1A = np.zeros((n,n)); A[edges[:,0], edges[:,1]] = 1; A += A.TD = np.diag(A.sum(1)); L = D-Aeigenvalues, eigenvectors = np.linalg.eigh(L)embedding = eigenvectors[:, 1:1+min(dimensions, n-1)]print("Eigenvalues:", eigenvalues[:8])print("Node embeddings:\n", embedding)

โค้ดเปลี่ยนตามค่าที่เลือกใน Playground · แต่ละภาษาใช้ข้อมูลตัวอย่างตามที่ระบุในโค้ด

05Learn by playing

จำนวนมิติเท่าใดรักษาเพื่อนบ้านและลิงก์ได้พอ?

Graph Embedding / ภาพกลไกที่พารามิเตอร์ควบคุม● คำนวณใหม่เมื่อปรับค่า
กำหนดความจุของเวกเตอร์แต่ละโหนด
ดูภาพอย่างไร

กราฟซ้ายคือ edges จริง ส่วนจุดขวาคือตำแหน่งใน latent space

เมื่อเพิ่มค่า

เวกเตอร์มีความจุมากขึ้นและรักษาความสัมพันธ์ซับซ้อนได้

ลองเปรียบเทียบ

ดูว่าคู่ที่มี edge อยู่ใกล้กว่าคู่สุ่มหรือไม่

กราฟและ edges จริงตำแหน่งใน embedding space
Link distortion15.014
Embedding dimensions8
พารามิเตอร์ที่ลอง8

Playground เป็น implementation เพื่อการเรียนรู้ที่คำนวณในเบราว์เซอร์ ส่วนโค้ด Python ใช้ NumPy จึงอาจให้ค่าต่างกันเล็กน้อยจากรายละเอียดการ optimize และค่าเริ่มต้นของไลบรารี ผลนี้ไม่ใช่ benchmark บนข้อมูลจริง