📖 একটি ছোট গল্প
Facebook-এর friend suggestion, Google Maps-এর route, molecule-এর structure, এমনকি Transformer-এর attention — সবকিছু আসলে Graph। নোড আর edge-এর গণিতই আজকের GNN (Graph Neural Network)-এর ভিত্তি।
Graph: Nodes ও Edges
G = (V, E) যেখানে V = nodes (vertices), E = edges। Directed/undirected, weighted/unweighted হতে পারে।
Adjacency Matrix: A[i][j] = 1 যদি (i, j) ∈ E
- Degree = একটি node-এর neighbor সংখ্যা
- Path, Cycle, Connected component
- DAG (Directed Acyclic Graph) → backprop computation graph
Matrix Representation
Graph operations আসলে matrix operations:
- A²[i][j] = i থেকে j-তে 2-step path সংখ্যা
- Laplacian: L = D − A (D = degree matrix)
- Eigenvalues of L → spectral clustering, GCN
Graph Neural Networks
প্রতিটি node তার neighbor থেকে message aggregate করে:
h_v⁽ᵏ⁺¹⁾ = σ( W · AGG({h_u⁽ᵏ⁾ : u ∈ N(v)}) )
- GCN: neighbor average
- GraphSAGE: sample + aggregate
- GAT: attention-weighted neighbor
✨ টিপ
Transformer আসলে fully-connected graph-এর উপর GAT — প্রতিটি token অন্য সব token-এর সাথে edge ধরে।
Python: BFS দিয়ে shortest path
pythonPython · NumPy
from collections import deque
def bfs_shortest(graph, start, goal):
q = deque([(start, [start])])
seen = {start}
while q:
node, path = q.popleft()
if node == goal: return path
for nb in graph[node]:
if nb not in seen:
seen.add(nb); q.append((nb, path + [nb]))
return None
graph = {"A":["B","C"], "B":["D"], "C":["D","E"], "D":["F"], "E":["F"], "F":[]}
print(bfs_shortest(graph, "A", "F"))Summary · সারসংক্ষেপ
- Graph = nodes + edges; adjacency matrix-এ encode করা যায়।
- GNN = neighbor aggregation, Transformer তার fully-connected special case।
- Recommendation, molecular AI, knowledge graph — সব graph-driven।