GraphX และ PageRank

1การแทนกราฟในระบบกระจาย

กราฟมีหลายชนิด และชนิดนั้นเปลี่ยนคำตอบ

Property Graph: ไม่ได้มีแต่จุดกับเส้นเปล่า ๆ

ในงานจริง Vertex และ Edge มักมีข้อมูลกำกับ Vertex ลูกค้าอาจมี segment และจังหวัด ส่วน Edge การซื้อมีเวลา ยอดเงิน และช่องทาง GraphX ใช้แนวคิด Property Graph ซึ่งเป็น Directed Multigraph ที่มี property บนทั้ง Vertex และ Edge ทำให้โครงสร้างกับข้อมูลประกอบอยู่ใน abstraction เดียวกัน

// Vertex: (VertexId, property)
val users: RDD[(VertexId, (String, String))] = sc.parallelize(Seq(
  (1L, ("Anan", "Bangkok")),
  (2L, ("Mali", "Chiang Mai")),
  (3L, ("Niran", "Bangkok"))
))

// Edge: srcId, dstId, property
val follows: RDD[Edge[String]] = sc.parallelize(Seq(
  Edge(1L, 2L, "follows"),
  Edge(2L, 3L, "follows"),
  Edge(3L, 1L, "follows")
))

val graph = Graph(users, follows)

Adjacency Matrix, Adjacency List และ Edge List

Dense กับ Sparse Graph

กราฟที่มี Vertex |V| ตัวอาจมี Edge ได้สูงสุดระดับ |V|² แต่กราฟโลกจริงจำนวนมากเป็น Sparse คือจำนวน Edge ใกล้เคียง O(|V|) มากกว่า O(|V|²) Adjacency Matrix จองพื้นที่ทุกคู่แม้ไม่มีเส้น จึงเหมือนพิมพ์สมุดโทรศัพท์ที่เว้นช่องสำหรับคนทุกคู่บนโลก ส่วน Adjacency List และ Edge List เก็บเฉพาะความสัมพันธ์ที่มีจริง

Degree Distribution และ Hub

กราฟหลายชนิดมี Degree Distribution ที่เอียงมาก Vertex ส่วนใหญ่มีเพื่อนบ้านน้อย แต่ Hub บางตัวมี Edge หลายล้านเส้น ค่าเฉลี่ยจึงหลอกเราได้ การแบ่ง Vertex เท่ากันคนละ 1 ล้านตัวไม่ได้แปลว่างานเท่ากัน เพราะ partition ที่มี Hub อาจถือ Edge มากกว่าที่อื่นหลายร้อยเท่า

Graph Partitioning: เราไม่ได้แบ่งเพียงข้อมูล แต่แบ่งความสัมพันธ์

ในตาราง เราอาจ hash ตาม key แล้วแต่ละแถวอยู่ partition เดียว แต่ Edge เชื่อม Vertex สองฝั่ง ถ้าสองฝั่งอยู่คนละเครื่อง การส่งข้อความตาม Edge ต้องข้ามเครือข่าย การลด Edge Cut ช่วยลดการสื่อสาร แต่การจับชุมชนให้อยู่เครื่องเดียวอาจทำให้งานไม่สมดุลเมื่อชุมชนมีขนาดต่างกัน

2Parallel BFS: ค้นกราฟทีละแนวหน้า

Breadth-First Search เริ่มจากจุดหนึ่ง แล้วขยายไปยังเพื่อนบ้านทีละระดับ โหนดที่กำลังจะถูกขยายเรียกว่า frontier เมื่อทำแบบขนาน worker หลายตัวช่วยกันเปิดรายชื่อเพื่อนบ้านของ frontier ได้ แต่ต้องตกลงกันว่าโหนดใดเคยพบแล้ว และต้องรอให้ระดับปัจจุบันเสร็จก่อนเริ่มระดับถัดไป

PBFS จึงสอนบทเรียนสำคัญว่า การขนานไม่ได้หมายถึงแบ่ง loop อย่างเดียว เราต้องแบ่งทั้งข้อมูล งาน และการสื่อสารให้เหมาะสมด้วย

BFS เป็น Wavefront Algorithm

จากจุดเริ่มต้น s เรากำหนดระยะของ s = 0 แล้วส่งข้อเสนอระยะ 1 ไปยังเพื่อนบ้าน โหนดที่เพิ่งค้นพบจะเป็น Frontier ของรอบถัดไป ขั้นตอนเดินเป็นคลื่นออกจากต้นทาง จึงหา Shortest Path ในกราฟไม่มีน้ำหนักได้ เพราะโหนดถูกพบครั้งแรกผ่านจำนวน Edge น้อยที่สุด

distance[source] = 0
frontier = {source}

while frontier is not empty:
    candidates = frontier.flatMap(v =>
        neighbors(v).map(u => (u, distance[v] + 1))
    )
    next = candidates
        .reduceByKey(min)
        .filter((u, d) => d < distance[u])
    update distance with next
    frontier = vertices in next

ทำไมต้อง Reduce ด้วย Min

หลาย Vertex ใน Frontier อาจพบปลายทางเดียวกันพร้อมกัน แต่ระยะที่เสนออาจเท่ากันหรือต่างกันเมื่อขยายเป็นอัลกอริทึมทั่วไป การรวมด้วย min ลดข้อความซ้ำก่อนอัปเดตสถานะ เหมือนหลายทีมรายงานเส้นทางไปจุดเดียวกัน ศูนย์ประสานงานไม่ต้องเก็บรายงานทั้งหมด เพียงเก็บระยะสั้นที่สุด

Top-down กับ Bottom-up BFS

Top-down BFS เริ่มจาก Frontier แล้วตรวจเพื่อนบ้านออกไป เหมาะเมื่อ Frontier เล็ก แต่เมื่อ Frontier ครอบคลุม Vertex จำนวนมาก เราอาจตรวจ Edge ซ้ำมหาศาล Bottom-up BFS กลับมุมมอง: ให้ Vertex ที่ยังไม่ถูกพบตรวจว่ามีเพื่อนบ้านคนใดอยู่ใน Frontier หรือไม่ และหยุดเมื่อพบหนึ่งคน วิธี Direction-optimizing BFS สลับสองทิศตามขนาด Frontier กับจำนวน Edge ที่คาดว่าจะตรวจ

Push กับ Pull เป็นรูปแบบที่พบซ้ำใน Graph Processing

Top-down คล้าย Push คือ Vertex ที่ Active ส่งข้อมูลออก ส่วน Bottom-up คล้าย Pull คือ Vertex ปลายทางดึงหรือมองหาข้อมูลจากเพื่อนบ้าน ทั้งสองให้ผลทางตรรกะคล้ายกัน แต่ปริมาณการอ่านและส่งข้อความต่างกัน การเลือกทิศจึงเป็น optimization จากโครงสร้างกราฟ ไม่ใช่เปลี่ยนอัลกอริทึมหลัก

Diameter กำหนดจำนวนรอบ

ต่อให้แต่ละรอบขนานได้สมบูรณ์ BFS ยังต้องเดินตามระดับ หากปลายทางห่างจากต้นทาง 100 Edge ก็มี dependency ต่อเนื่องอย่างน้อย 100 รอบ เราไม่สามารถเพิ่มเครื่องแล้วข้าม causal chain นี้ได้ กราฟเส้นยาวจึงมี Parallelism ต่อรอบน้อย ต่างจากกราฟที่ Frontier แตกกว้างอย่างรวดเร็ว

Frontier ขนาดเล็กทำให้คลัสเตอร์ใหญ่ช่วยได้น้อย

ช่วงต้น BFS อาจมี Frontier เพียง 1–10 Vertex ถึงมี worker 1,000 ตัวก็มีงานไม่พอแบ่ง ช่วงกลาง Frontier โตและใช้ parallelism ได้ดี ก่อนจะเล็กลงอีกครั้งเมื่อใกล้จบ รูปร่างของ Frontier จึงทำให้ Scalability เปลี่ยนไปตามรอบ ไม่ใช่ค่าคงที่ของ Algorithm

Visited Set ในระบบกระจาย

Visited Set ป้องกันการวนและการส่ง Vertex เดิมซ้ำ แต่ถ้าเก็บรวมศูนย์จะเป็นคอขวด จึงกระจาย state ตาม Vertex ID แล้วใช้ Message Aggregation รวมข้อเสนอ ก่อน Join กับสถานะเดิม ทุก iteration มีทั้งการส่งข้อความ การรวม และการอัปเดต Property ของ Vertex

จาก BFS ไปสู่ Connected Components

รูปแบบส่ง Label ไปหาเพื่อนบ้านและรับ Label ที่เล็กที่สุดสามารถใช้หา Connected Components ได้ Vertex เริ่มด้วย ID ของตัวเอง แล้วทำซ้ำจนสมาชิกใน Component เดียวกันถือ Label เดียวกัน นี่ทำให้เห็นรูปแบบร่วมของ Graph Algorithm หลายตัว: Vertex เก็บสถานะ Edge เป็นช่องทางส่ง Message และระบบทำ Superstep จนไม่มีการเปลี่ยนแปลง

3PageRank: การคำนวณซ้ำจนคะแนนนิ่ง

พจน์ผลรวมคือคะแนนที่ไหลมาตามลิงก์ ส่วน (1-d)/N คือโอกาสที่ผู้ใช้หยุดคลิกลิงก์แล้ว Teleport ไปหน้าใดหน้าหนึ่ง การใช้ d ≈ 0.85 เป็นค่าที่พบได้บ่อยในตัวอย่าง แต่ไม่ใช่กฎธรรมชาติที่ห้ามเปลี่ยน ต้องดูนิยามและ implementation ที่ใช้

หนึ่ง Vote ไม่ได้มีน้ำหนักเท่ากันทุกหน้า

การนับ In-degree อย่างเดียวให้ทุกลิงก์หนึ่งคะแนน PageRank เปลี่ยนเป็น “ลิงก์จากหน้าที่สำคัญมีน้ำหนักมากกว่า” และหน้าที่ลิงก์ออกจำนวนมากต้องแบ่งคะแนนให้หลายปลายทาง หน้า A ที่มีคะแนน 0.6 และลิงก์ออกสองแห่งจึงส่งแห่งละ 0.3 ก่อนคูณ damping ส่วนหน้า B ที่มีคะแนน 0.6 แต่ลิงก์ออก 100 แห่งส่งเพียงแห่งละ 0.006

ตัวอย่างคำนวณกราฟเล็ก

สมมุติมีสามหน้า A, B และ C โดย A ลิงก์ไป B และ C, B ลิงก์ไป C, C ลิงก์กลับ A เริ่มต้นให้ทุกหน้ามีคะแนน 1/3 และใช้ d = 0.85

เมื่อแทนค่าเริ่มต้น 1/3 เราได้คะแนนรอบใหม่ประมาณ A = 0.333, B = 0.192 และ C = 0.475 รอบต่อไปใช้ค่าชุดใหม่นี้คำนวณต่อ การเปลี่ยนจะเล็กลงเรื่อย ๆ จนเข้าใกล้ Stationary Distribution

Matrix View: PageRank คือ Power Iteration

ถ้าสร้าง Transition Matrix M ที่คอลัมน์ t แจก 1/C(t) ไปยังหน้าที่ t ลิงก์ถึง เราเขียนการอัปเดตเป็นเวกเตอร์ได้ว่า

การทำซ้ำคือ Power Iteration เพื่อหาเวกเตอร์คงตัวของ Markov Chain มุมนี้เชื่อม PageRank กับ Linear Algebra ขณะที่มุม Message Passing เชื่อมกับการประมวลผลแบบกระจาย ทั้งสองอธิบาย Algorithm เดียวกันคนละระดับ

Teleportation แก้ปัญหาอะไร

• Spider Trap: กลุ่มหน้าที่ลิงก์วนกันแต่ไม่มีทางออกจะดูดคะแนนไว้ หากผู้ใช้คลิกลิงก์อย่างเดียว
• Disconnected Components: เว็บมีส่วนที่เดินตามลิงก์จากบางจุดไปไม่ถึง
• Periodicity: กราฟบางรูปแบบทำให้ความน่าจะเป็นสลับไปมาแทนการนิ่ง

Teleportation ทำให้ Random Surfer มีโอกาสกระโดดออกจากกับดักและไปยังส่วนอื่น ภายใต้เงื่อนไขที่เหมาะสมจึงมี Stationary Distribution ที่ชัดเจนและการทำซ้ำลู่เข้า

Dangling Node: คะแนนไม่ได้หายทางคณิตศาสตร์ถ้าจัดการถูก

Dangling Node คือหน้าไม่มี Outlink ถ้าสร้าง Transition Matrix ตรง ๆ คอลัมน์นั้นมีผลรวมศูนย์และมวลความน่าจะเป็นจะหาย วิธีทั่วไปคือถือว่าหน้านั้นแจกคะแนนตาม Teleportation Distribution หรือรวบรวม Dangling Mass ในแต่ละรอบแล้วกระจายกลับตามกฎเดียวกัน Implementation อาจทำใน pass แยกหรือรวมในขั้นตอนอื่น แต่หลักคือต้องรักษาผลรวมของ Probability Mass ตามนิยาม Algorithm

// Pseudo-code แบบ MapReduce (จากเอกสารต้นฉบับ)
class Mapper {
  def map(id: Long, n: Node) = {
    emit(id, n)                              // ส่งโครงสร้างกราฟต่อไปยังรอบถัดไป
    p = n.PageRank / n.adjacencyList.length   // แจก PageRank เท่า ๆ กันให้ทุก outlink
    for (m <- n.adjacencyList) emit(m, p)
  }
}
class Reducer {
  def reduce(id: Long, objects: Iterable[Object]) = {
    var s = 0; var n: Node = null
    for (p <- objects) {
      if (isNode(p)) n = p else s += p       // รวม PageRank ที่ไหลเข้ามา
    }
    n.PageRank = s
    emit(id, n)
  }
}
// ทำซ้ำหลายรอบจนกว่าค่า PageRank จะลู่เข้า (convergence)

ในการคำนวณแบบกระจาย ค่าใช้จ่ายเกิดขึ้นทุกครั้งที่ส่งคะแนนข้ามเครื่องและรอจบรอบ การแบ่งกราฟที่ดีจึงพยายามเก็บโหนดที่เชื่อมกันมากไว้ใกล้กัน และรวม contribution ภายในเครื่องก่อนส่งออกไป

Convergence: เมื่อไรจึงเรียกว่า “นิ่ง”

PageRank ทางทฤษฎีทำซ้ำไปเรื่อย ๆ แต่ระบบจริงต้องหยุด เราอาจกำหนดจำนวนรอบคงที่ หรือหยุดเมื่อความต่างของคะแนนต่ำกว่า tolerance เช่นใช้ L1 norm

Tolerance เล็กให้คำตอบนิ่งกว่าแต่ต้องทำรอบมากขึ้น จำนวนรอบยังขึ้นกับ damping factor และโครงสร้างกราฟ การกำหนด max iterations ป้องกันงานวิ่งนานเกิน SLA แม้ยังไม่ถึง tolerance

Fixed Iteration กับ Dynamic Convergence

PageRank ใน MapReduce แพงตรงไหน

แต่ละ iteration ต้องอ่านโครงสร้างกราฟ แจก contribution, Shuffle ตาม destination, Reduce และเขียนผลสำหรับรอบถัดไป หากใช้ MapReduce แบบดั้งเดิม ผลชั่วคราวมักผ่าน distributed storage ทุกครั้ง Spark/GraphX จึงได้ประโยชน์จากการ cache โครงสร้างและสถานะที่ใช้ซ้ำ แต่ยังหนี Network, Barrier และ Lineage ที่ยาวไม่ได้ทั้งหมด

รวม Message ก่อนข้าม Network

ถ้า Vertex ปลายทางได้รับ contribution หลายรายการจาก Edge ใน partition เดียว เราอาจรวมบางส่วนในเครื่องก่อนส่ง เหมือน Combiner ของ MapReduce หลัก Associativity ช่วยให้ sum รวมเป็นชั้นได้ ลดจำนวน message และ serialization โดยไม่เปลี่ยนผลเชิงคณิตศาสตร์เกินข้อควรระวังเรื่อง Floating-point order

Floating-point และผลที่ไม่เหมือนกันทุก Bit

การบวกเลขทศนิยมไม่ associative แบบคณิตศาสตร์สมบูรณ์ ลำดับการรวมที่เปลี่ยนตาม partition อาจทำให้ค่าท้ายต่างกันเล็กน้อย ระบบกระจายจึงอาจให้ผลไม่เหมือนกันแบบ bit-for-bit แม้ความหมายและ tolerance เท่ากัน เราควรเปรียบเทียบภายใน tolerance ไม่ใช่ใช้ equality ตรง ๆ

Personalized PageRank

PageRank แบบทั่วไป Teleport ไปทุกหน้าอย่างสม่ำเสมอ Personalized PageRank เปลี่ยนเวกเตอร์ v ให้เน้น Seed บางชุด เช่นผู้ใช้คนหนึ่ง หัวข้องานวิจัย หรือสินค้าที่สนใจ คะแนนจึงสะท้อนความใกล้เชิงโครงสร้างจาก Seed ไม่ใช่ความสำคัญทั่วโลกเพียงค่าเดียว

PageRank ไม่ได้เท่ากับคุณภาพหรือความจริง

PageRank วัดความสำคัญตามโครงสร้างลิงก์และแบบจำลอง Random Surfer หน้าที่มีคะแนนสูงอาจเป็นที่นิยม มีตำแหน่งดี หรืออยู่ในโครงสร้างที่ส่งคะแนนให้ ไม่ได้แปลว่าเนื้อหาถูกต้อง เป็นธรรม หรือเหมาะกับทุก query Search Engine จึงต้องรวมข้อความ ความสด ความน่าเชื่อถือ spam detection และสัญญาณอื่นจำนวนมาก

Manipulation และ Link Spam

เมื่อคะแนนมีผลต่อการมองเห็น ผู้คนย่อมพยายามสร้างลิงก์เพื่อเพิ่มคะแนน Link Farm เชื่อมหน้าหลายชุดเพื่อหมุนคะแนนและส่งไปยังเป้าหมาย Algorithm จัดอันดับจึงกลายเป็นเกมระหว่างผู้วัดกับผู้ถูกวัด การใช้ Graph Signal ต้องคิด adversarial behavior ไม่ใช่เชื่อว่า Edge ทุกเส้นเกิดตามธรรมชาติ

PageRank กับ Centrality แบบอื่น

ไม่มี Centrality ที่ดีที่สุดโดยไม่ระบุคำถาม ผู้มีเพื่อนมาก ผู้ได้รับการอ้างจากคนสำคัญ และผู้เชื่อมสองชุมชนเป็น “คนสำคัญ” คนละความหมาย

4GraphX: Property Graph บน Spark

GraphX เพิ่ม Graph abstraction เหนือ RDD โดยมองกราฟเป็น Directed Multigraph ที่ Vertex และ Edge มี Property ผู้พัฒนาจึงใช้ทั้ง operation แบบกราฟ เช่น subgraph, aggregateMessages และ operation แบบ RDD เพื่อ Join หรือวิเคราะห์ผลต่อได้

ชนิดข้อมูลหลัก

Triplet: หน่วยคิดที่มีต้นทุน

Triplet สะดวกเพราะ expression หนึ่งมองเห็น Property ทั้งต้นทางและปลายทาง แต่การนำ Vertex Property ไปอยู่ใกล้ Edge อาจต้องมี routing และ replication GraphX พยายามส่งเฉพาะ property ที่ operation ต้องใช้ผ่าน TripletFields แต่ผู้เขียน Algorithm ควรรู้ว่า “มองเห็นทุกอย่าง” ไม่ได้ฟรี

Graph Operators ที่ควรรู้

// กรองเฉพาะผู้ใช้ในกรุงเทพฯ และ edge ที่ยังใช้ได้
val activeGraph = graph.subgraph(
  vpred = (id, user) => user.city == "Bangkok",
  epred = edge => edge.attr.active
)

// เพิ่ม out-degree เข้า property ของ vertex
val withDegree = graph.outerJoinVertices(graph.outDegrees) {
  (id, user, degree) => (user, degree.getOrElse(0))
}

// แปลง property โดยคง topology เดิม
val scoreGraph = graph.mapVertices {
  case (id, user) => 1.0
}

aggregateMessages: ส่งแล้วรวม

aggregateMessages เป็น primitive สำคัญ Vertex/Edge Triplet สร้าง Message ไปยัง Source หรือ Destination แล้วระบบรวม Message ต่อ Vertex ด้วย associative function รูปแบบนี้ตรงกับ Algorithm จำนวนมาก

val neighborAgeSum: VertexRDD[(Int, Int)] =
  graph.aggregateMessages[(Int, Int)](
    ctx => {
      ctx.sendToSrc((ctx.dstAttr.age, 1))
      ctx.sendToDst((ctx.srcAttr.age, 1))
    },
    (a, b) => (a._1 + b._1, a._2 + b._2)
  )

val averageNeighborAge = neighborAgeSum.mapValues {
  case (sum, count) => sum.toDouble / count
}

แทนที่จะส่งอายุของเพื่อนบ้านทุกคนเป็น list เราส่งคู่ (sum,count) แล้วรวมบางส่วนได้ทันที State เล็กลงและ Network ลดลง นี่คือ Monoidification แบบเดียวกับที่พบใน MapReduce และ Streaming

PartitionStrategy ใน GraphX

GraphX มี Partition Strategy หลายแบบ เช่น RandomVertexCut, CanonicalRandomVertexCut, EdgePartition1D และ EdgePartition2D แต่ละแบบกำหนดว่า Edge ไป partition ใดและ Vertex ต้องถูกทำสำเนามากเพียงใด Strategy ที่เหมาะขึ้นกับ Degree Distribution, Direction และ Algorithm

Cache และ Unpersist ใน Iterative Graph Algorithm

PageRank ใช้ topology ซ้ำหลายรอบ จึงควร persist graph/state ที่คุ้ม แต่ทุก iteration สร้างสถานะใหม่ ถ้าไม่ unpersist รุ่นเก่า memory จะเต็มและเกิด spill/GC การจัดวงจรชีวิตของ cached RDD เป็นส่วนหนึ่งของ Algorithm ไม่ใช่งานดูแลหลังเขียนเสร็จ

5Pregel: คิดเป็น Vertex, Message และ Superstep

Pregel เป็นโมเดล Bulk Synchronous Parallel สำหรับ Graph Processing ในแต่ละ Superstep Vertex ที่ Active รับ Message จากรอบก่อน อัปเดตสถานะ ส่ง Message ไปยังเพื่อนบ้าน แล้วรอ Barrier ก่อนเข้ารอบถัดไป GraphX มี Pregel-like API ที่ทำให้รูปแบบนี้เขียนได้ตรงกับ Algorithm

val initialGraph = graph.mapVertices {
  case (id, _) => if (id == sourceId) 0.0 else Double.PositiveInfinity
}

val shortest = initialGraph.pregel(Double.PositiveInfinity)(
  // Vertex Program
  (id, distance, message) => math.min(distance, message),

  // Send Message
  triplet => {
    val candidate = triplet.srcAttr + triplet.attr.weight
    if (candidate < triplet.dstAttr)
      Iterator((triplet.dstId, candidate))
    else Iterator.empty
  },

  // Merge Message
  (a, b) => math.min(a, b)
)

Vote to Halt ไม่ได้แปลว่า Vertex หายไป

Vertex ที่ไม่มีงานใหม่สามารถหยุด Active ชั่วคราว และกลับมา Active เมื่อได้รับ Message วิธีนี้ช่วยลดงานใน Algorithm ที่การเปลี่ยนแปลงกระจายเป็นบางพื้นที่ เช่น Shortest Path หลังระยะนิ่งแล้ว แต่ PageRank แบบมาตรฐานยังมี contribution ต่อเนื่องทุก Vertex การตรวจ Message ว่างทุก iteration จึงอาจไม่คุ้มและ semantics ต่างกัน

Barrier ทำให้เหตุผลชัด แต่ต้องรอคนช้าที่สุด

Bulk Synchronous Model แบ่งแต่ละรอบชัดเจน Message ของรอบ k ใช้อัปเดตรอบ k+1 จึง debug และ reasoning ง่าย แต่ Superstep จบเมื่อ worker ทุกตัวเสร็จ Task ที่มี Hub หรือเครื่องช้าหนึ่งตัวทำให้ทั้งหมดรอ เรียกว่า Straggler Problem

Message Volume เป็นตัววัดสำคัญ

จำนวน Vertex และ Edge บอกขนาดกราฟ แต่ค่าใช้จ่ายต่อรอบขึ้นกับ Edge ที่ถูกเปิดและ Message ที่ส่ง Algorithm ที่ Active Vertex เพียง 1% อาจประหยัดมากถ้า API สามารถข้าม Edge ของ Vertex ที่ไม่ Active ได้ เราจึงควรวัด Message Count, Active Vertex, Replication และ Network ไม่ใช่ดู CPU อย่างเดียว

Associativity ของ Merge Function

ระบบอาจรวม Message คนละลำดับตาม partition ฟังก์ชัน Merge จึงควร associative และ ideally commutative เช่น min, max, sum ภายใต้ข้อจำกัด Floating-point ถ้าใช้ฟังก์ชันที่ผลขึ้นกับลำดับ เราอาจได้คำตอบต่างกันเมื่อจำนวน partition เปลี่ยน

Pregel กับ MapReduce

6Graph Algorithm อื่นที่ควรรู้จัก

PageRank เป็นตัวอย่างสำคัญ แต่ Graph Analytics มีหลายครอบครัว การรู้ว่าคำถามอยู่ครอบครัวใดช่วยเลือก Algorithm และต้นทุนได้ถูกกว่าเริ่มจากชื่อ Library

Triangle ไม่ได้มีความหมายเดียวในทุกโดเมน

ใน Social Graph สามเหลี่ยมอาจสื่อว่าคนสองคนมีเพื่อนร่วมและมีแนวโน้มรู้จักกัน ใน Fraud Graph สามเหลี่ยมของการโอนเงินอาจเป็นวงจรน่าสงสัย แต่ใน Supply Chain อาจเป็นเส้นทางสำรองที่ดี Algorithm บอกโครงสร้าง ส่วนมนุษย์ต้องตีความตามโดเมน

Connected Components กับ Entity Resolution

ถ้า record สองตัวเชื่อมเมื่อมี email, เบอร์โทร หรืออุปกรณ์ร่วมกัน Connected Components อาจรวม record ที่เชื่อมทางอ้อมเป็น Entity เดียว แต่ Edge ผิดเพียงไม่กี่เส้นอาจเชื่อม Component ใหญ่เข้าด้วยกันจนเกิด false merge การสร้าง Edge จึงสำคัญพอ ๆ กับ Algorithm หลังจากนั้น

Graph Motif และ Pattern

บางคำถามไม่ต้อง iterate ทั้งกราฟ แต่ค้นรูปแบบเล็ก เช่น A โอนให้ B, B โอนให้ C และ C โอนกลับ A ภายใน 24 ชั่วโมง GraphFrames มี Motif Finding ที่เขียน pattern แล้วกรอง Property ต่อด้วย DataFrame expression ได้ ความท้าทายคือจำนวน candidate combination โตเร็ว จึงต้องกรองเวลาและประเภท Edge ให้เร็ว

7กรณีศึกษาประยุกต์: จาก EdgeRank สู่ Feed Ranking

Feed Ranking เป็น Pipeline ไม่ใช่สูตรเดียว

ระบบสมัยใหม่มักแยกเป็น Candidate Generation, Feature Computation, Ranking, Re-ranking และ Policy Filter Graph ช่วยสร้าง candidate จากคนที่ติดตาม เพื่อนของเพื่อน กลุ่ม หรือความสนใจใกล้เคียง จากนั้น ML ประเมินโอกาสเกิดปฏิสัมพันธ์หลายแบบ แล้ว Re-ranking ปรับเรื่องความหลากหลาย ความสด ความปลอดภัย และข้อจำกัดทางธุรกิจ

Feedback Loop: การจัดอันดับเปลี่ยนข้อมูลที่ใช้ฝึกรอบต่อไป

เนื้อหาที่ระบบแสดงมีโอกาสถูกคลิกมากกว่า สิ่งที่ไม่แสดงไม่มีโอกาสสร้าง label ระบบจึงเรียนจากข้อมูลที่ตัวเองเลือกให้เกิด Popular Item อาจยิ่งได้ exposure และยิ่งดูเป็นที่นิยม การประเมิน Feed Ranking ต้องคิด Exploration, Position Bias และ Counterfactual ไม่ใช่ดู CTR อย่างเดียว

Optimization Objective ไม่ได้มีค่าเดียว

ถ้า optimize เวลาใช้งานอย่างเดียว Feed อาจชอบเนื้อหาที่เร้าอารมณ์แต่ลดคุณภาพระยะยาว ระบบจริงต้องชั่ง engagement, satisfaction, diversity, safety และ ecosystem health บางเป้าหมายขัดกัน จึงไม่มีสูตรเดียวที่ “ดีที่สุด” โดยไม่ระบุคุณค่าที่แพลตฟอร์มเลือก

8GraphFrames: Graph ที่พูดภาษา DataFrame

GraphFrames แทน Vertex และ Edge ด้วย DataFrame ทำให้ใช้ SQL expression, Catalyst และภาษา Python/Scala/Java ได้ง่ายขึ้น Vertex DataFrame ต้องมีคอลัมน์ id ส่วน Edge DataFrame ต้องมี src และ dst แล้วเพิ่ม Property อื่นได้ตาม schema

from graphframes import GraphFrame

vertices = spark.createDataFrame([
    ("a", "Anan", 34),
    ("b", "Mali", 29),
    ("c", "Niran", 41)
], ["id", "name", "age"])

edges = spark.createDataFrame([
    ("a", "b", "follow"),
    ("b", "c", "follow"),
    ("c", "a", "follow")
], ["src", "dst", "relationship"])

g = GraphFrame(vertices, edges)
g.inDegrees.show()
g.pageRank(resetProbability=0.15, maxIter=10).vertices.show()

DataFrame ช่วยเรื่องอะไร

• อ่าน Vertex/Edge จาก Parquet, Delta หรือ Table ได้ตรง ๆ
• กรอง Property และ Join กับข้อมูลธุรกิจด้วย SQL/DataFrame API
• ใช้ Python ได้โดยไม่ต้องเขียน GraphX Scala API โดยตรง
• เชื่อมผล Graph Algorithm กลับเข้า Feature Pipeline ได้สะดวก

Motif Finding

// หาเส้นทาง a -> b -> c และ c -> a
val cycles = g.find("(a)-[ab]->(b); (b)-[bc]->(c); (c)-[ca]->(a)")
  .filter("a.id != b.id AND b.id != c.id AND a.id != c.id")

Motif เป็น pattern ทางโครงสร้าง แต่เราสามารถกรองเวลา ยอดเงิน หรือประเภท Edge ต่อได้ เช่นวงจรธุรกรรมต้องเกิดภายใน 24 ชั่วโมง การใส่ Property constraint เร็วช่วยลด candidate ที่ขยายแบบ combinatorial

GraphFrames ก็ยังต้องจ่ายค่า Join และ Shuffle

การเขียนเป็น DataFrame ไม่ได้ทำให้ Graph Traversal กลายเป็นฟรี Motif และ Pregel ถูกแปลงเป็น DataFrame operations หลายรอบ ซึ่งอาจมี Join, Shuffle, Checkpoint และ Storage ต้นทุนยังมาจาก topology เดิม เพียงมี optimizer และ ecosystem ช่วยจัดการมากขึ้น

GraphX กับ GraphFrames เลือกอย่างไร

9จาก Graph Feature ไปสู่ Graph Machine Learning

ก่อนพูดถึง GNN ควรเห็นว่างาน ML ใช้ Graph ได้หลายระดับ ไม่จำเป็นต้องเริ่มจาก Neural Network เราสามารถคำนวณ Degree, PageRank, Component, Triangle หรือ Personalized PageRank แล้ว Join กลับเป็น Feature ในโมเดลตารางทั่วไป

สามระดับของ Graph ML

Node Embedding

Embedding แปลง Vertex เป็น Vector ให้ Vertex ที่มีบริบทโครงสร้างคล้ายกันอยู่ใกล้กัน Random Walk-based method สร้างลำดับ Vertex คล้ายประโยคแล้วเรียน representation ส่วน GNN รวมข้อความจากเพื่อนบ้านผ่านหลายชั้น Vector ที่ได้ใช้ทำ Classification, Clustering, Similarity และ Link Prediction ได้

Message Passing ใน GNN คล้าย Pregel แต่เรียนพารามิเตอร์

โครงส่ง–รวม–อัปเดตเหมือน Graph Algorithm แบบเดิม แต่ f และ update อาจเป็น Neural Network ที่เรียนจากข้อมูล สิ่งที่เพิ่มคือ Gradient, Mini-batch Sampling และ Parameter Training ขณะที่ปัญหา Degree Skew, Neighborhood Explosion และ Partition ยังอยู่

Neighborhood Explosion

ถ้าแต่ละ Vertex มีเพื่อนเฉลี่ย 100 คน GNN สองชั้นอาจแตะเพื่อนระดับสองราว 10,000 คนต่อ Seed และสามชั้นอาจโตถึงล้านก่อนหักการซ้ำ การ Sampling เพื่อนบ้านจึงจำเป็นในกราฟใหญ่ แต่ทำให้เกิด variance และอาจพลาดสัญญาณจากเพื่อนที่ไม่ได้ถูกสุ่ม

GNN ไม่ได้แทน PageRank ทุกกรณี

PageRank ไม่ต้องมี Label อธิบายได้ด้วย Random Surfer และคำนวณ Global Importance ได้ตรงไปตรงมา GNN ยืดหยุ่นกว่าแต่ต้องมี Objective, Training Data และการควบคุม Overfitting หากโจทย์ต้องการเพียง Feature ความสำคัญหรือ Candidate Generation PageRank อาจเรียบง่าย ถูกกว่า และตรวจสอบง่ายกว่า

Graph Feature Leakage

ถ้าสร้าง Graph จาก Edge ที่เกิดหลังเวลาทำนาย Feature เช่น Degree หรือ PageRank จะเห็นอนาคต แม้โมเดลตารางแบ่ง Train/Test ถูกแล้ว Temporal Split ต้องใช้กับการสร้างกราฟด้วย เช่นทำนาย Fraud ณ วันที่ 1 สิงหาคม ต้องสร้าง Graph จากธุรกรรมก่อนเวลานั้น ไม่ใช่ใช้ Graph เต็มเดือนแล้วตัดเฉพาะ Label

10เมื่อยุคเปลี่ยน: จาก GraphX สู่ GraphFrames และ Graph ML

สิ่งที่เปลี่ยนกับสิ่งที่ยังเหมือนเดิม

ไม่ควรเริ่มต้นโครงการด้วยคำว่า “ต้องใช้ Graph Database”

Graph Data Model, Graph Processing Engine และ Graph Database เป็นคนละเรื่อง เราอาจเก็บ Edge ใน Parquet แล้วคำนวณด้วย GraphFrames หรือเก็บใน Graph Database เพื่อ Query เส้นทางแบบ Online การเลือกเริ่มจาก Workload: Batch Analytics, Interactive Traversal, Transactional Update หรือ ML Training ไม่ใช่เริ่มจากคำว่า Graph แล้วซื้อเครื่องมือทุกชนิด

11กรณีศึกษา: เครือข่ายธุรกรรมและ Fraud Ring

สมมุติธนาคารพบว่าการตรวจบัญชีทีละรายจับพฤติกรรมผิดปกติได้ไม่ครบ เพราะบัญชีแต่ละตัวโอนเงินไม่เกินเกณฑ์ แต่หลายบัญชีร่วมกันรับเงิน กระจายต่อ และวนกลับมายังกลุ่มเดิม ปัญหานี้มีความหมายอยู่ที่รูปแบบความสัมพันธ์มากกว่ายอดของบัญชีใดบัญชีหนึ่ง

ขั้นที่ 1: ออกแบบ Vertex และ Edge

Vertex อาจมีหลายประเภท ได้แก่ Account, Device, Phone, IP และ Merchant ส่วน Edge มี TRANSFERRED_TO, USED_DEVICE, LOGGED_IN_FROM พร้อมเวลาและ Property การใช้ Heterogeneous Graph ช่วยเชื่อมบัญชีที่ดูไม่เกี่ยวกันผ่านอุปกรณ์หรือผู้รับร่วม

ขั้นที่ 2: กำหนดเวลาให้ Graph

สร้าง Graph Snapshot จากธุรกรรม 30 วันก่อนเวลาตัดสินใจ Edge เก่ากว่าอาจลดน้ำหนักหรือถูกตัดออก ถ้าใช้ธุรกรรมหลังเกิด Fraud มาสร้าง Graph Feature เราจะรู้เครือข่ายด้วยข้อมูลอนาคตและประเมินโมเดลสูงเกินจริง

ขั้นที่ 3: สร้าง Feature หลายระดับ

• Local: In-degree, Out-degree, ยอดเข้าออก, จำนวนคู่สัญญา
• Neighborhood: สัดส่วนเพื่อนบ้านเสี่ยง, จำนวน Device ร่วม, Two-hop exposure
• Component: ขนาด Component, จำนวนประเทศ, ความหนาแน่น
• Centrality: PageRank หรือ Personalized PageRank จากบัญชีที่ยืนยันแล้วว่าเสี่ยง
• Motif: วงจรสามเหลี่ยม, fan-in แล้ว fan-out, เงินวนกลับในเวลาสั้น

ขั้นที่ 4: Personalized PageRank จาก Seed เสี่ยง

Global PageRank อาจยกคะแนนให้ Merchant ใหญ่เพราะมี Edge มาก แต่ Personalized PageRank ที่ Teleport กลับไปยัง Seed Fraud ช่วยวัดความใกล้เชิงเครือข่ายจากกลุ่มเสี่ยง อย่างไรก็ตามคะแนนสูงคือสัญญาณเพื่อสอบสวน ไม่ใช่หลักฐานความผิด เพราะบัญชีปกติอาจเชื่อมกับ Seed ผ่านร้านค้าสาธารณะ

ขั้นที่ 5: ควบคุม Hub ที่เกิดตามธรรมชาติ

Payment Gateway, Mobile Carrier NAT หรือร้านค้ารายใหญ่อาจเป็น Hub ที่เชื่อมคนดีและคนเสี่ยงจำนวนมาก เราอาจ down-weight Edge, แยก Vertex Type, ตัด Shared Infrastructure ที่ไม่มี discriminative value หรือใช้ Meta-path ที่กำหนดชนิดเส้นทาง ไม่เช่นนั้น Component ใหญ่หนึ่งก้อนจะกลืนทั้งกราฟ

ขั้นที่ 6: อธิบายผลให้ผู้ตรวจสอบ

แทนที่จะรายงานเพียง risk score ระบบควรแสดง subgraph และเหตุผล เช่น “บัญชีนี้รับเงินจาก 14 บัญชีภายใน 20 นาที แล้วส่ง 93% ไปยังบัญชีเดียวซึ่งอยู่ห่างจาก Seed Fraud สอง Hop” Graph มีข้อดีด้านการสร้างหลักฐานเชิงโครงสร้าง แต่ visualization ต้องจำกัดขนาด ไม่เช่นนั้นกลายเป็นใยแมงมุมที่ไม่มีใครอ่านออก

ขั้นที่ 7: ประเมินแบบ Group และ Time Split

ถ้าบัญชีใน Fraud Ring เดียวกันกระจายทั้ง Train และ Test โมเดลอาจจำรูปแบบกลุ่มได้ง่าย คะแนนจึงสูงเกินความสามารถจับ Ring ใหม่ ควรแบ่งตามเวลาและอาจ hold out บาง Component เพื่อทดสอบ Generalization ไปยังเครือข่ายที่ไม่เคยเห็น

12กรณีศึกษา: Citation Graph และการค้นงานวิจัย

ใน Citation Graph Vertex คือบทความและ Edge ชี้จากบทความที่อ้างไปยังบทความที่ถูกอ้าง การนับ Citation ดิบให้ทุกการอ้างหนึ่งเสียง PageRank เพิ่มแนวคิดว่าการถูกอ้างโดยงานที่ได้รับความสำคัญเองมีน้ำหนักมากกว่า แต่ยังต้องระวังความต่างระหว่างสาขา อายุงาน และรูปแบบการอ้าง

ปัญหาของ Citation Count

• งานเก่ามีเวลาสะสม Citation มากกว่า
• สาขาที่มีชุมชนใหญ่และรายการอ้างอิงยาวได้ Citation มากกว่า
• Review Paper มักได้ Citation สูงจากบทบาทสรุป ไม่ได้แปลว่ามี Contribution แบบเดียวกับ Method Paper
• Self-citation และ Citation Cartel ทำให้โครงสร้างถูกจัดฉากได้

Personalized PageRank สำหรับ Literature Discovery

เริ่ม Teleport Distribution จากบทความที่ผู้เรียนสนใจ แล้วเดินตาม Citation ไปข้างหน้า/ย้อนกลับตาม Graph ที่ออกแบบ จะได้งานที่อยู่ใกล้ Seed เชิงโครงสร้าง วิธีนี้เติมเต็ม Keyword Search เพราะบทความอาจใช้ศัพท์ต่างกันแต่เชื่อมผ่าน Citation Network

Heterogeneous Academic Graph

เพิ่ม Author, Venue, Institution และ Topic เป็น Vertex Type แล้วใช้ Meta-path เช่น Author–Paper–Author เพื่อดูการร่วมงาน หรือ Paper–Venue–Paper เพื่อหางานในชุมชนเดียวกัน แต่ Meta-path แต่ละแบบแฝงนิยาม “ความใกล้” คนละอย่าง ต้องเลือกจากคำถาม

Temporal Bias

บทความใหม่ยังไม่มีเวลารับ Citation จึงถูก PageRank แบบตรง ๆ กดคะแนน ระบบแนะนำอาจผสม Content Embedding, Freshness และ Citation Signal เพื่อให้ค้นงานใหม่ได้ การใช้ Graph อย่างเดียวจึงมี Cold-start ทั้งกับ Vertex และ Edge

13ออกแบบและวัดระบบ Graph Processing

ก่อนรัน Algorithm ควรทำ Graph Profile เพราะจำนวน Vertex/Edge อย่างเดียวไม่พอ Degree Distribution, Component Size, Self-loop, Duplicate Edge และ Property Completeness มีผลต่อทั้งความหมายกับประสิทธิภาพ

Checklist ก่อนคำนวณ

Metric ทางระบบ

• เวลาต่อ Iteration และจำนวน Iteration
• Active Vertex และ Message Count ต่อรอบ
• Shuffle Read/Write และ Network I/O
• Vertex Replication Factor
• Partition Edge Count และ Task Skew
• Cache hit, Spill, GC และ Checkpoint Time

Metric ทาง Algorithm

PageRank ดู Delta/Convergence และ Rank Stability, Community Detection ดู Modularity หรือ Stability, Link Prediction ดู Precision@K/Recall@K และ Negative Sampling, Graph Feature ใน Fraud ดู Metric แบบ Time/Group Split การวัดเวลารันโดยไม่วัดคุณภาพอาจทำให้ Algorithm เร็วขึ้นเพราะหยุดก่อนคำตอบใช้ได้

Reproducibility ของ Graph

ต้องบันทึก Vertex Snapshot, Edge Snapshot, Direction Rule, Deduplication, Weighting, Partition Count, Algorithm Parameter และ Library Version Graph ที่สร้างจากข้อมูลเดียวกันแต่ตัด Edge คนละเวลาอาจให้ Component และ PageRank ต่างกันมาก การบันทึกเพียง Model Version จึงไม่พอ

Incremental Graph Processing

กราฟจริงเปลี่ยนทุกวัน แต่การคำนวณ PageRank ทั้งกราฟใหม่แพง เราอาจคำนวณเป็นรอบ Batch, ใช้ previous score เป็นค่าเริ่ม, ประมวลผลเฉพาะบริเวณที่ residual สูง หรือใช้ระบบ incremental เฉพาะทาง ข้อแลกเปลี่ยนคือความซับซ้อนและการสะสม error ต้องมี full recomputation เป็นระยะหรือ validation เทียบ baseline

14สรุปและขั้นตอนถัดไป

บทนี้เริ่มจากการเปลี่ยนหน่วยคิดจาก Row ไปเป็น Vertex และ Edge เมื่อความสัมพันธ์เป็นข้อมูลหลัก ปัญหาใหม่จึงเกิดขึ้นทั้ง Degree Skew, Random Access, Graph Partitioning, Message Volume และ Barrier ของ Iterative Algorithm Parallel BFS แสดงให้เห็น Wavefront และ Frontier ส่วน PageRank แสดงการแจก–รวมคะแนนจนลู่เข้า พร้อม Teleportation และ Dangling Mass เพื่อให้ Probability Model สมบูรณ์

GraphX และ Pregel ทำให้รูปแบบ Vertex State, Message และ Superstep ชัดขึ้น ขณะที่ GraphFrames เชื่อม Graph เข้ากับ DataFrame/SQL และภาษา Python ได้สะดวกกว่า Graph ML เพิ่มความสามารถในการเรียน Representation แต่ไม่ได้ลบ Algorithm แบบเดิม การเลือกควรเริ่มจากคำถาม ความหมายของ Edge และ Workload ไม่ใช่เริ่มจากเครื่องมือที่ดูทันสมัยที่สุด

ขั้นตอนถัดไป คือ Scalable Machine Learning ซึ่งจะนำแนวคิดจาก DataFrame, Streaming และ Graph มารวมกับการฝึกโมเดลขนาดใหญ่ เราจะถามต่อว่าเมื่อข้อมูล Feature และ Parameter ไม่พอดีกับเครื่องเดียว ควรกระจายข้อมูล กระจายโมเดล หรือปรับ Algorithm อย่างไร และความเร็วที่เพิ่มขึ้นคุ้มกับ Communication และ Statistical Efficiency หรือไม่