8.7 — Graph Theory (গ্রাফ তত্ত্ব)¶

এই অধ্যায়ে কী শিখব: গ্রাফ (graph) কী, কীভাবে তাকে node/vertex (নোড/শীর্ষ), edge (এজ/ধার), degree (ডিগ্রি/মাত্রা), adjacency matrix (সন্নিহিতি ম্যাট্রিক্স) $A$ আর degree matrix (ডিগ্রি ম্যাট্রিক্স) $D$ দিয়ে গণিতে লেখা যায়; graph Laplacian (গ্রাফ ল্যাপ্লাসিয়ান) $L = D - A$ কী এবং কেন সে symmetric positive semidefinite (প্রতিসম ও অঋণাত্মক-নিশ্চায়ক); গ্রাফে symmetry (প্রতিসাম্য), automorphism (স্বয়ংরূপতা) আর permutation invariance (বিন্যাস-অপরিবর্তনীয়তা) মানে কী; permutation matrix (বিন্যাস ম্যাট্রিক্স) $P$ কীভাবে নোডের নাম বদলায় ($A' = PAP^\top$); গ্রাফের ওপর vector field / signal (ভেক্টর ক্ষেত্র / সংকেত) কী; আর সবশেষে Weisfeiler–Lehman (WL) test কীভাবে দুটো graph isomorphic (সমরূপ) কিনা যাচাই করে — এবং এই সবকিছু কীভাবে GNN (Graph Neural Network)-এর ভিত্তি তৈরি করে।

উৎস (source): Mathematical Foundations of Geometric Deep Learning — Borde ও Bronstein।

১. কেন শিখব? (Motivation)¶

আগের অধ্যায়গুলোতে আমরা ধারাবাহিক (continuous) জ্যামিতি দেখেছি — মসৃণ curve (বক্ররেখা), surface (তল), manifold (বহুবিস্তার)। কিন্তু বাস্তব পৃথিবীর অনেক data ধারাবাহিক নয়, বরং বিচ্ছিন্ন (discrete) — গোনা যায় এমন আলাদা আলাদা টুকরো দিয়ে গড়া। এই বিচ্ছিন্ন জ্যামিতির (discrete geometry) সবচেয়ে গুরুত্বপূর্ণ অংশ হলো গ্রাফ তত্ত্ব (graph theory), আর Geometric Deep Learning-এ এর প্রয়োগই হলো GNN — সম্ভবত এই ক্ষেত্রের সবচেয়ে প্রতিনিধিত্বমূলক (quintessential) নিউরাল নেটওয়ার্ক স্থাপত্য।

কেন গ্রাফ এত গুরুত্বপূর্ণ? কারণ অসংখ্য data স্বাভাবিকভাবেই গ্রাফ:

অণু (molecule): পরমাণু = node, রাসায়নিক বন্ধন = edge। ওষুধ আবিষ্কার, প্রোটিন ভাঁজ — সবই গ্রাফের সমস্যা।
সামাজিক নেটওয়ার্ক (social network): মানুষ = node, বন্ধুত্ব = edge।
সুপারিশ ব্যবস্থা (recommendation system): ব্যবহারকারী ও পণ্য = node, কেনাকাটা = edge (এটা একটা bipartite graph)।
3D mesh (জাল): কম্পিউটার গ্রাফিক্সে একটা তল = অসংখ্য শীর্ষ, ধার আর মুখ (face) দিয়ে গড়া জাল — আর এটাও আসলে একটা গ্রাফ।

কিন্তু গ্রাফের একটা মৌলিক সমস্যা আছে যা ছবি বা ধ্বনির নেই: নোডের নম্বর দেওয়া সম্পূর্ণ ইচ্ছাধীন (arbitrary)। একটা অণুর পরমাণুগুলোকে $1, 2, 3, \dots$ নম্বর দিই নাকি অন্য যেকোনো ক্রমে দিই — অণুটা একই থাকে। তাই গ্রাফ-শেখা model-কে অবশ্যই এই symmetry সম্মান করতে হবে: নোডের নাম বদলালে (permutation) উত্তর যেন না বদলায়। এটাই permutation invariance — আর এটাই GNN-কে সঠিকভাবে কাজ করতে বাধ্য করে। যে model এই symmetry মানে না, সে একই অণুকে দুবার আলাদা করে "শিখবে", অর্থহীনভাবে।

মূল স্বজ্ঞা

একটা গ্রাফ মানে দুটো জিনিস: কে কার সঙ্গে যুক্ত (connectivity — adjacency matrix $A$) আর প্রতিটা নোডে কী তথ্য বসে আছে (feature/signal — feature matrix $X$)। GNN হলো এমন একটা ফাংশন যা এই দুই জিনিসকে একসঙ্গে নিয়ে কাজ করে, কিন্তু নোডের নামকরণের ওপর নির্ভর করে না। "নাম বদলালে উত্তর বদলায় না" — এই একটামাত্র নিয়ম (permutation invariance) থেকেই GNN-এর গোটা কাঠামো, এমনকি তার সীমাবদ্ধতা (WL test), যুক্তি দিয়ে বেরিয়ে আসে।

২. মূল ধারণা (Core idea)¶

২.১ গ্রাফ কী এবং তার notation (node, edge, degree, adjacency, Laplacian)¶

গ্রাফ কী? একটা গ্রাফ (graph) হলো একটা ক্রমিক জোড়া (ordered tuple):

\[ G = (V, E), \]

যেখানে $V$ হলো node/vertex-এর set। Directed graph-এ $E\subseteq V\times V$ ordered pair-এর set; undirected graph-এ $E$ unordered pair $\{u,v\}$-এর set। সহজ কথায়: বিন্দুগুলো node, আর কোন node-জোড়া যুক্ত তা edge ধরে।

Diagram of a graph with nodes in gray and edges in black

চিত্র ১: একটা গ্রাফের চিত্র — ধূসর বৃত্তগুলো হলো node/vertex (নোড/শীর্ষ), কালো রেখাগুলো হলো edge (এজ/ধার)। একটা গ্রাফ মানে কেবল "কে কার সঙ্গে যুক্ত" — বিন্দুগুলোর প্রকৃত অবস্থান বা আকার এখানে অর্থহীন।

দিকযুক্ত না দিকহীন? edge দুরকম হতে পারে —

দিকযুক্ত (directed) edge: ordered pair $(v_i,v_j)$, যেখানে প্রথমটি source ও দ্বিতীয়টি target। আলাদা node-এর জন্য $(v_i,v_j)$ ও $(v_j,v_i)$ আলাদা ordered pair; একটি edge থাকলে reverse edge থাকতেই হবে না।
দিকহীন (undirected) edge: unordered pair $\{v_i,v_j\}$। তাই $\{v_i,v_j\}=\{v_j,v_i\}$। চাইলে একে $V\times V$-এর symmetric relation হিসেবেও encode করা যায়: $(v_i,v_j)\in E\iff(v_j,v_i)\in E$; ordered pair-দুটো তখনও সমান নয়।

যদি কোনো edge একটা নোডকে নিজের সঙ্গেই যোগ করে, তাকে বলে self-loop (স্ব-ফাঁস), লেখা হয় $(v_i, v_i)$।

প্রতিবেশ (neighborhood): নোড $v_i$-এর (এক-ধাপ) প্রতিবেশ হলো ঐসব নোডের সেট যারা $v_i$-এর সঙ্গে একটা edge শেয়ার করে:

\[ \mathcal{N}(v_i)=\{v_j\mid \{v_i,v_j\}\in E\}\quad\text{(undirected)}. \]

Directed graph-এ $(v_i,v_j)\in E$ ধরে একই formula out-neighborhood দেয়; in-neighborhood-এর জন্য $(v_j,v_i)\in E$ নিতে হয়।

উপগ্রাফ (subgraph): $H = (V_H, E_H)$ হলো $G = (V_G, E_G)$-এর একটা উপগ্রাফ যদি $V_H \subseteq V_G$ এবং $E_H \subseteq E_G$। বিশেষভাবে, $\{v_i\} \cup \mathcal{N}(v_i)$ নোডগুলো আর তাদের মধ্যেকার সব edge নিলে যে উপগ্রাফ পাওয়া যায়, তাকে বলে $v_i$-এর neighborhood subgraph — GNN ঠিক এই স্থানীয় প্রতিবেশেই হিসাব করে।

সন্নিহিতি ম্যাট্রিক্স (adjacency matrix): গ্রাফকে ম্যাট্রিক্স দিয়ে লেখা যায়। $N = |V|$ সংখ্যক নোডের গ্রাফের জন্য তার adjacency matrix $A \in \mathbb{R}^{N \times N}$ নোডদের মধ্যে সংযোগ-কাঠামো ধরে রাখে। ওজনযুক্ত directed graph-এ $A_{ij}=w(v_i,v_j)$। Undirected graph-এ $A_{ij}=A_{ji}=w(\{v_i,v_j\})$। ওজনহীন হলে entry $0$ বা $1$।

\[ A_{ij} = \begin{cases} 1 & \text{if } v_i\sim v_j, \\ 0 & \text{otherwise}, \end{cases} \]

যেখানে directed graph-এ $v_i\sim v_j$ মানে $(v_i,v_j)\in E$, আর undirected graph-এ মানে $\{v_i,v_j\}\in E$।

তাই ওজনহীন ও দিকহীন গ্রাফের adjacency matrix binary ও symmetric: $\{v_i,v_j\}\in E$ হলে একই undirected edge দুই symmetric entry-তে $A_{ij}=A_{ji}=1$ দেয়। Digraph-এ reverse edge স্বাধীন, তাই matrix সাধারণত asymmetric; তবে কোনো particular digraph-এর $A$ accidentalভাবে symmetric হতেও পারে।

ডিগ্রি ম্যাট্রিক্স (degree matrix): কর্ণ-ঘেঁষা (diagonal) ম্যাট্রিক্স $D \in \mathbb{R}^{N \times N}$, যার প্রতিটা কর্ণ-উপাদান হলো adjacency matrix-এর ঐ সারির যোগফল:

\[ D_{ii} = \sum_j A_{ij}. \]

অর্থাৎ $D_{ii}$ হলো নোড $v_i$-এর degree (ডিগ্রি/মাত্রা) — কতগুলো edge তার সঙ্গে যুক্ত। দিকহীন গ্রাফে $D$-ও symmetric (আসলে diagonal বলে trivially symmetric)।

degree centrality: নোডের গুরুত্ব মাপার সবচেয়ে সরল পরিমাপ হলো তার degree:

\[ \deg(v_i) = \sum_j A_{ij} = \sum_j A_{ji}. \]

দিকযুক্ত গ্রাফে দুটো আলাদা degree থাকে — ভেতরে-আসা edge গোনে in-degree $\deg_{\text{in}}(v_i) = \sum_j A_{ji}$, আর বাইরে-যাওয়া edge গোনে out-degree $\deg_{\text{out}}(v_i) = \sum_j A_{ij}$।

সংযুক্তি ও দূরত্ব (connectivity ও distance): একটা গ্রাফ connected (সংযুক্ত) যদি প্রতিটা নোড-জোড়ার মধ্যে একটা path (পথ) থাকে। shortest path / graph geodesic (সংক্ষিপ্ততম পথ / গ্রাফ জিওডেসিক) দূরত্ব হলো দুটো নোড জোড়ার মধ্যে যেকোনো পথের সর্বনিম্ন মোট ওজন:

\[ d_G(v_i, v_j) = \min_{P \in \mathcal{P}_{ij}} \sum_{e_k \in P} w(e_k), \]

যেখানে $\mathcal{P}_{ij}$ হলো $v_i$ থেকে $v_j$-এর সব path-এর set। Positive edge-weight-সহ connected undirected graph-এ $d_G$ একটি genuine metric। Disconnected graph-এ unreachable pair-এর distance $\infty$, তাই এটি extended metric; directed graph-এ distance asymmetric-ও হতে পারে। Connected finite graph-এর diameter হলো $\operatorname{diam}(G)=\max_{i,j}d_G(v_i,v_j)$।

গ্রাফের প্রকারভেদ (types of graphs): connectivity-কাঠামো অনুযায়ী কিছু গুরুত্বপূর্ণ প্রকার —

point cloud / null graph $N_N$: যার edge-সেট খালি, $E = \varnothing$ (কোনো সংযোগ নেই)।
complete graph $K_N$: প্রতিটা আলাদা নোড-জোড়া একটা edge দিয়ে যুক্ত — সর্বাধিক সম্ভাব্য edge। (মজার দিক: Transformer-এর attention আসলে একটা complete graph-এর ওপর হিসাব করে, যেখানে $N$ হলো token-সংখ্যা।)
bipartite graph: নোডকে দুটো অসংযোগী উপসেট $V_1, V_2$-এ ভাগ করা যায়, edge কেবল দুই সেটের মধ্যে (সুপারিশ ব্যবস্থার আদর্শ মডেল)।
path graph $P_N$, cycle graph $C_N$, tree (বৃক্ষ), DAG (directed acyclic graph): সরল রৈখিক শৃঙ্খল, বদ্ধ চক্র, ফাঁস-হীন সংযুক্ত গ্রাফ, ফাঁস-হীন দিকযুক্ত গ্রাফ।
regular graph: প্রতিটা নোডের degree সমান; সবার degree $k$ হলে $k$-regular (যেমন $C_N$ হলো 2-regular, $K_N$ হলো $(N{-}1)$-regular)।

geometric graph (জ্যামিতিক গ্রাফ): এখানে প্রতিটা নোড $v_i$ জ্যামিতিক জগতে (সাধারণত $\mathbb{R}^2$ বা $\mathbb{R}^3$) একটা বিন্দুর সঙ্গে যুক্ত, আর edge নির্ধারিত হয় নোডদের অবস্থান দিয়ে — যেমন distance threshold $d(v_i, v_j) \le \epsilon$ (unit disk graph) বা $k$-nearest neighbor ($k$-NN graph)। এটাই অণু-জীববিজ্ঞানের প্রাণভোমরা:

Geometric graphs can be used as mathematical abstractions of biomolecules

চিত্র ২: একটা জৈব-অণুর (biomolecule) geometric graph (জ্যামিতিক গ্রাফ) হিসেবে গাণিতিক বিমূর্তায়ন। প্রতিটা node শুধু "কার সঙ্গে যুক্ত" (adjacency matrix) নয়, তার একটা 3D অবস্থান আর জ্যামিতিক feature-ও (যেমন বেগ) থাকে।

mesh ও অন্যান্য বিচ্ছিন্ন কাঠামো: একটা mesh (জাল) হলো কোনো জ্যামিতিক অঞ্চলের বিচ্ছিন্ন প্রতিনিধিত্ব — শীর্ষ, ধার আর মুখ (সাধারণত ত্রিভুজ) দিয়ে গড়া, যা একটা ধারাবাহিক তলকে আসন্ন করে। গুরুত্বপূর্ণ: একটা mesh আসলে একটা গ্রাফ (শীর্ষ = node, ধার = edge), তাই গ্রাফের সব যন্ত্রপাতি এর ওপরও খাটে।

The Stanford Bunny mesh

চিত্র ৩: Stanford Bunny — কম্পিউটার গ্রাফিক্সের সবচেয়ে পরিচিত 3D পরীক্ষামূলক মডেল (Greg Turk ও Marc Levoy, ১৯৯৪)। এটা একটা mesh (জাল), অর্থাৎ শীর্ষ-ধার-মুখ দিয়ে গড়া একটা গ্রাফ; তাই তার ওপর signal ও graph Laplacian-এর ভাষা সরাসরি প্রযোজ্য।

২.২ গ্রাফে symmetry ও automorphism, permutation invariance¶

কেন symmetry? যেহেতু নোডের নম্বর দেওয়া সম্পূর্ণ ইচ্ছাধীন, তাই আমরা চাই এমন model যা নোড পুনঃক্রম (reordering) করলেও একই থাকে। এখানেই আসে symmetric group (প্রতিসম গ্রুপ) ও permutation-invariant aggregator (বিন্যাস-অপরিবর্তনীয় সমাহারক)।

$|S| = N$ হলে $S$-এর symmetric group $S_N$ হলো $S$ থেকে $S$-এ সব bijection (এক-এক ও উপরি সংশ্লেষ)-এর সেট: $S_N = \{ \sigma : S \to S \mid \sigma \text{ is a bijection} \}$। প্রতিটা $\sigma$ হলো একটা permutation (বিন্যাস) — অর্থাৎ নোডদের নাম বদলানোর একটা উপায়।

একটা permutation-invariant aggregator হলো এমন ফাংশন $\bigoplus : \mathcal{X}^N \to \mathcal{Y}$ যা সন্তুষ্ট করে

\[ \bigoplus(x_1, x_2, \dots, x_N) = \bigoplus(x_{\sigma(1)}, x_{\sigma(2)}, \dots, x_{\sigma(N)}), \]

যেকোনো $\sigma \in S_N$-এর জন্য। সাধারণ উদাহরণ: যোগফল $\sum_i x_i$, গড় $\frac{1}{N}\sum_i x_i$, সর্বোচ্চ $\max_i x_i$ — এদের কাছে ইনপুটের ক্রম অর্থহীন। GNN-এর শেষে ঠিক এই ধরনের aggregator দিয়ে সব নোডের feature-কে একটা vector-এ pool করা হয়, যা দিয়ে graph-স্তরের শ্রেণিবিন্যাস/রিগ্রেশন করা যায়।

permutation matrix (বিন্যাস ম্যাট্রিক্স): নোড পুনঃক্রমকে ম্যাট্রিক্সে লেখার হাতিয়ার। $P$ হলো একটা বর্গাকার binary ম্যাট্রিক্স যেখানে প্রতিটা সারি ও প্রতিটা কলামে ঠিক একটা $1$ আছে, বাকি সব $0$:

\[ P_{ij} = \begin{cases} 1 & \text{if node } i \text{ maps to node } j, \\ 0 & \text{otherwise}. \end{cases} \]

এমন প্রতিটা ম্যাট্রিক্স $S_N$-এর একটা সদস্যের সঙ্গে এক-এক মেলে। permutation matrix orthogonal (লম্ব), তাই $P^{-1} = P^\top$ এবং $PP^\top = P^\top P = I$। একটা গ্রাফে $P$ প্রয়োগ করলে তার adjacency matrix রূপান্তরিত হয়:

\[ A' = P A P^\top, \]

যেখানে $A'$ একই graph-এর relabeled adjacency matrix। Spectrum, degree multiset ও connectivity structure permutation-invariant; কিন্তু indexed degree vector node-এর সঙ্গে permute করে, অর্থাৎ equivariant। এই distinction graph-learning model-এর symmetry বোঝার ভিত্তি।

automorphism (স্বয়ংরূপতা): কখনো কখনো একটা গ্রাফের নিজের একটা symmetry থাকে — এমন নোড-পুনঃনামকরণ যা গ্রাফটাকে হুবহু একই রাখে। গণিতে, একটা automorphism হলো এমন permutation $P$ যার জন্য $P A P^\top = A$। এমন সব $P$ একসঙ্গে একটা group গঠন করে, যাকে বলে গ্রাফের automorphism group $\operatorname{Aut}(G)$। এটা গ্রাফের "নিজস্ব symmetry-র সংগ্রহ"।

homomorphism ও isomorphism: দুই গ্রাফের সম্পর্ক বোঝাতে —

graph homomorphism: map $F:V_G\to V_H$ যেখানে $u\sim_G v\Rightarrow F(u)\sim_H F(v)$ — adjacency preserve করে, কিন্তু একাধিক node-কে একটায় map করতে পারে।
graph isomorphism: bijection $F$ যেখানে $u\sim_Gv\iff F(u)\sim_HF(v)$। দুটো graph isomorphic মানে তারা "একই graph, শুধু node-এর নাম আলাদা"।

Weisfeiler–Lehman (WL) test: দুটো graph isomorphic কিনা তা নিশ্চিতভাবে বলা কঠিন সমস্যা। WL test একটা দ্রুত, পুনরাবৃত্তিমূলক পদ্ধতি যা নোডের প্রতিবেশ-তথ্য দিয়ে নোডের "রং" (label) ধাপে ধাপে পরিশোধন (refine) করে দুটো graph আলাদা করার চেষ্টা করে।

The Weisfeiler-Lehman (WL) test

চিত্র ৪: Weisfeiler–Lehman (WL) test প্রতিবেশের ভিত্তিতে node label বারবার refine করে। Standard permutation-invariant message-passing GNN-এর distinguishing power 1-WL-এর চেয়ে বেশি নয়; injective aggregation ও update থাকলে উপযুক্ত setting-এ 1-WL-এর power match করতে পারে, অন্যথায় strictly weaker হতে পারে।

WL test-এর এক ধাপ এভাবে কাজ করে: প্রতিটা নোড শুরুতে একই রং পায়; তারপর প্রতিটা ধাপে নোডের নতুন রং = (তার পুরোনো রং, প্রতিবেশীদের রঙের multiset)-কে hash করে পাওয়া নতুন সংকেত। রং স্থির (stable) না হওয়া পর্যন্ত এটা চলে। দুই graph-এর প্রতিটা ধাপে রঙের histogram (কোন রং কতবার) তুলনা করা হয়: কোনো ধাপে histogram আলাদা হলে graph দুটো নিশ্চিতভাবে isomorphic নয়; histogram সবসময় মিললে test অমীমাংসিত (তারা isomorphic হতেও পারে, নাও হতে পারে)। এই "প্রতিবেশ থেকে তথ্য নিয়ে নিজের label হালনাগাদ" — এটাই GNN-এর message passing-এর সঙ্গে সরাসরি সংযুক্ত (নিচে ২.৩ দেখো)।

২.৩ গ্রাফে vector field / signal (ভেক্টর ক্ষেত্র / সংকেত)¶

এতক্ষণ কেবল connectivity নিয়ে কথা হলো। কিন্তু বাস্তবে প্রতিটা নোডে তথ্য বসে থাকে। নোড $v_i$-তে একটা feature vector (বৈশিষ্ট্য ভেক্টর) $x_i$ হলো একটা $D$-মাত্রিক ভেক্টর যা ঐ নোডের বৈশিষ্ট্য ধরে রাখে। সব নোডের feature একসঙ্গে সাজালে পাওয়া যায় ম্যাট্রিক্স $X \in \mathbb{R}^{N \times D}$, যার $i$-তম সারি হলো $x_i^\top$।

আগের অধ্যায়ের ভাষায়, এটাকে একটা feature vector field (বৈশিষ্ট্য ভেক্টর ক্ষেত্র) $F$ হিসেবেও দেখা যায় — গ্রাফের নোড-জগৎ থেকে $\mathbb{R}^D$-এ একটা প্রতিচিত্র:

\[ F : V \to \mathbb{R}^D, \qquad F(v_i) = x_i \in \mathbb{R}^D, \quad \forall v_i \in V. \]

অর্থাৎ গ্রাফের ওপর "signal" মানে প্রতিটা নোডে একটা করে মান/ভেক্টর বসানো — ঠিক যেমন তলের ওপর তাপমাত্রা বা বায়ুর বেগ। permutation এই signal-কেও পুনঃক্রম করে: নোডের নাম বদলালে $X \to PX$ হয়, কিন্তু sum/mean/max aggregator-এর আউটপুট অপরিবর্তিত থাকে (§৪-এ সংখ্যাসহ দেখব)।

graph Laplacian (গ্রাফ ল্যাপ্লাসিয়ান): spectral graph theory-র প্রাণকেন্দ্র। সংজ্ঞা সরল:

\[ L = D - A, \]

যেখানে $A$ ও $D$ যথাক্রমে adjacency ও degree matrix। দিকহীন গ্রাফে $L$ symmetric ও positive-semidefinite (PSD, অঋণাত্মক-নিশ্চায়ক)। কেন PSD? তার সবচেয়ে সুন্দর প্রমাণ আসে তার quadratic form (দ্বিঘাত রূপ) থেকে:

\[ x^\top L x =\frac{1}{2}\sum_{i,j=1}^{n}w_{ij}(x_i-x_j)^2 =\sum_{\{v_i,v_j\}\in E}w_{ij}(x_i-x_j)^2, \]

যেখানে $w_{ij}$ হলো edge $(v_i, v_j)$-এর ওজন। এই রাশিটা আসলে গ্রাফের ওপর একটা gradient-সদৃশ (ঢালসদৃশ) পরিমাণ মাপে — signal-টা প্রতিবেশী নোডদের মধ্যে কতটা মসৃণ (smooth) তা বলে দেয়। প্রতিটা পদ $w_{ij}(x_i - x_j)^2$ শাস্তি দেয় যখন যুক্ত দুই নোডের মান আলাদা। এই পরিমাণকে বলে graph Dirichlet energy (গ্রাফ ডিরিশ্লে শক্তি) — যা ধারাবাহিক জগতের $\langle \nabla f, \nabla f \rangle$-এর সরাসরি সাদৃশ্য। homophily-র সঙ্গে সংযোগ: যুক্ত নোডরা একই রকম feature ধরে (homophilic) মানে Dirichlet energy কম, অর্থাৎ signal মসৃণ।

normalized graph Laplacian: undirected nonnegative-weight graph-এ, isolated vertex না থাকলে,

\[ L_{\text{norm}} = I - D^{-1/2} A D^{-1/2}, \]

এর eigenvalue $[0,2]$-এর মধ্যে থাকে, আর $0$-এর multiplicity graph-এর connected component-এর সংখ্যা। Isolated vertex থাকলে এই statement বজায় রাখতে normalized Laplacian-এর সেই diagonal entry আলাদাভাবে $0$ define করা হয়। শুধু $D^{-1/2}_{ii}=0$ বসিয়ে full identity-সহ $I-D^{-1/2}AD^{-1/2}$ লিখলে isolate-এর diagonal $1$ হবে; তখন multiplicity statement-এ isolate count হবে না।

spectral / graph Fourier: যেহেতু $L$ symmetric ও PSD, তার eigen-decomposition আছে:

\[ L = U \Lambda U^\top, \]

যেখানে $U=[u_1,\dots,u_N]$ হলো orthonormal eigenbasis (graph Fourier basis) এবং $\Lambda=\operatorname{diag}(\lambda_1,\dots,\lambda_N)$। Graph signal processing-এ $\lambda_k$-কে spectral frequency/roughness parameter বলা হয়: ছোট $\lambda_k$ smooth mode, বড় $\lambda_k$ বেশি edge-wise variation। এটি ordinary angular frequency-এর সঙ্গে হুবহু এক নয়। যেকোনো signal $f:V\to\mathbb R$-এর graph Fourier transform $\hat f=U^\top f$, inverse $f=U\hat f$।

message passing (বার্তা-প্রেরণ): GNN-এ আমরা বলি গ্রাফের ওপর একটা signal শিখছি, যেখানে গ্রাফ-কাঠামো নোডদের মধ্যে তথ্যপ্রবাহ নিয়ন্ত্রণ করে। একটা message-passing GNN স্তর $l$ এভাবে হিসাব করে:

\[ x_i^{(l+1)} = \phi\!\left( x_i^{(l)}, \bigoplus_{j \in \mathcal{N}(v_i)} \psi\big( x_i^{(l)}, x_j^{(l)} \big) \right), \]

যেখানে $\psi$ ও $\phi$ অরৈখিক ফাংশন, আর $\bigoplus$ হলো একটা permutation-invariant সমাহারক (নাহলে প্রতিবেশীদের ক্রমের ওপর উত্তর নির্ভর করত — যা ভুল!)। এটাকে তিনটা নিয়মে ভাঙা যায়:

\[ m_{ij}^{(l)} \leftarrow \psi\big( x_i^{(l)}, x_j^{(l)} \big) \qquad \text{(Message)} \]

\[ a_i^{(l)} \leftarrow \bigoplus_{j \in \mathcal{N}(v_i)} m_{ij}^{(l)} \qquad \text{(Aggregate)} \]

\[ x_i^{(l+1)} \leftarrow \phi\big( x_i^{(l)}, a_i^{(l)} \big) \qquad \text{(Update)} \]

এই local aggregation WL color refinement-এর সঙ্গে ঘনিষ্ঠভাবে related। Standard message-passing GNN graph distinguish করার ক্ষমতায় 1-WL-এর চেয়ে বেশি শক্তিশালী নয়। উপযুক্ত countable/bounded feature setting-এ multiset aggregation এবং update দুটোই injective হলে 1-WL match করা যায়; raw sum একাই arbitrary multiset-এ injective নয়।

৩. সংজ্ঞা ও উপপাদ্য¶

সংজ্ঞা: গ্রাফ (graph)

একটা graph হলো $G=(V,E)$। Directed graph-এ $E\subseteq V\times V$ এবং edge ordered pair $(v_i,v_j)$। Undirected graph-এ $E$ হলো unordered pair $\{v_i,v_j\}$-দের set (অথবা equivalently $V\times V$-এর symmetric relation)। Undirected neighborhood $\mathcal N(v_i)=\{v_j:\{v_i,v_j\}\in E\}$; directed ক্ষেত্রে in- ও out-neighborhood আলাদা।

সংজ্ঞা: adjacency matrix (সন্নিহিতি ম্যাট্রিক্স) ও degree matrix (ডিগ্রি ম্যাট্রিক্স)

$N=|V|$ node-এর graph-এর adjacency matrix $A\in\mathbb R^{N\times N}$: unweighted ক্ষেত্রে $A_{ij}=1$ যদি $v_i\sim v_j$, নাহলে $0$; weighted ক্ষেত্রে সংশ্লিষ্ট edge-weight। Unweighted undirected graph-এ $A$ binary ও symmetric ($A=A^\top$)।

degree matrix $D \in \mathbb{R}^{N \times N}$ হলো diagonal ম্যাট্রিক্স যেখানে

\[ D_{ii} = \sum_j A_{ij} = \deg(v_i), \]

অর্থাৎ প্রতিটা কর্ণ-উপাদান হলো $A$-এর সংশ্লিষ্ট সারির যোগফল, আর কর্ণ-বহির্ভূত সব উপাদান $0$।

সংজ্ঞা: graph Laplacian (গ্রাফ ল্যাপ্লাসিয়ান)

গ্রাফ $G = (V, E)$-এর graph Laplacian ম্যাট্রিক্স

\[ L = D - A, \]

যেখানে $A$ ও $D$ যথাক্রমে adjacency ও degree matrix। দিকহীন গ্রাফে $L$ symmetric ও positive-semidefinite। normalized graph Laplacian হলো $L_{\text{norm}} = I - D^{-1/2} A D^{-1/2}$, যার eigenvalue $[0, 2]$-এর মধ্যে থাকে এবং eigenvalue $0$-এর multiplicity গ্রাফের connected component-এর সংখ্যার সমান।

সংজ্ঞা: permutation matrix ও automorphism group (স্বয়ংরূপতা গ্রুপ)

একটা permutation matrix (বিন্যাস ম্যাট্রিক্স) $P$ হলো বর্গাকার binary ম্যাট্রিক্স যেখানে প্রতিটা সারি ও কলামে ঠিক একটা $1$; এটা symmetric group $S_N$-এর একটা সদস্যের সঙ্গে এক-এক মেলে এবং orthogonal ($P^{-1} = P^\top$)। নোড-পুনঃনামকরণে adjacency matrix রূপান্তরিত হয় $A' = P A P^\top$।

গ্রাফ $G$-এর একটা automorphism (স্বয়ংরূপতা) হলো এমন permutation $P$ যার জন্য $P A P^\top = A$ (গ্রাফটা নিজের সঙ্গে সমরূপ থাকে)। সব automorphism মিলে group $\operatorname{Aut}(G)$ গঠন করে।

সংজ্ঞা: graph isomorphism ও Weisfeiler–Lehman (WL) test

দুই graph-এর মধ্যে graph isomorphism হলো bijection $F:V_G\to V_H$ যেখানে $u\sim_Gv\iff F(u)\sim_HF(v)$।

1-WL test নোডের রং $c^{(0)}(v)$ একইভাবে শুরু করে, তারপর পুনরাবৃত্ত করে

\[ c^{(t+1)}(v) = \operatorname{HASH}\!\Big( c^{(t)}(v), \; \{\!\{ c^{(t)}(u) : u \in \mathcal{N}(v) \}\!\} \Big), \]

যেখানে $\{\!\{ \cdot \}\!\}$ প্রতিবেশীদের রঙের multiset (বহুসেট)। রং স্থির না হওয়া পর্যন্ত এটা চলে। দুই graph-এর কোনো ধাপে রঙের histogram আলাদা হলে তারা isomorphic নয়; সবসময় মিললে test অমীমাংসিত।

উপপাদ্য: $L = D - A$ symmetric ও positive-semidefinite

দিকহীন গ্রাফের graph Laplacian $L = D - A$ symmetric, এবং যেকোনো $x \in \mathbb{R}^N$-এর জন্য $x^\top L x \ge 0$ (positive-semidefinite)।

প্রমাণ। symmetric: $D$ diagonal, তাই $D^\top = D$; দিকহীন গ্রাফে $A$ symmetric, তাই $A^\top = A$। ফলে $L^\top = (D - A)^\top = D^\top - A^\top = D - A = L$, অর্থাৎ $L$ symmetric।

positive-semidefinite: সব ক্রমিক জোড়া $(i, j)$-এর ওপর যোগ করে quadratic form বিস্তার করি। প্রথমে,

\[ x^\top D x = \sum_i d_i x_i^2, \qquad x^\top A x = \sum_{i, j} A_{ij} x_i x_j = \sum_{i, j} w_{ij} x_i x_j. \]

এখন $\sum_j w_{ij} = d_i$ ব্যবহার করে বিখ্যাত সদৃশতা:

\[ \frac{1}{2} \sum_{i, j} w_{ij} (x_i - x_j)^2 = \frac{1}{2} \sum_{i, j} w_{ij} \big( x_i^2 - 2 x_i x_j + x_j^2 \big) = \sum_i d_i x_i^2 - \sum_{i, j} w_{ij} x_i x_j. \]

ডান পক্ষ ঠিক $x^\top D x - x^\top A x = x^\top L x$। অতএব

\[ x^\top L x = \frac{1}{2} \sum_{i, j} w_{ij} (x_i - x_j)^2 \ge 0, \]

যেহেতু ওজন $w_{ij} \ge 0$ এবং বর্গ $(x_i - x_j)^2 \ge 0$। তাই $L$ positive-semidefinite। $\square$

অনুসিদ্ধান্ত: graph invariant permutation-এ অপরিবর্তিত

যদি $A' = P A P^\top$ (নোড-পুনঃনামকরণ), তবে $A$ ও $A'$-এর eigenvalue-সমষ্টি অভিন্ন। কারণ $P$ orthogonal, তাই $A' = P A P^\top = P A P^{-1}$ হলো একটা similarity transform (সদৃশতা-রূপান্তর) — আর similarity transform eigenvalue পাল্টায় না। একইভাবে degree-বহুসেট, connected-component সংখ্যা, Laplacian spectrum সবই অপরিবর্তিত থাকে। এটাই permutation invariance-এর গাণিতিক ভিত্তি। $\square$

৪. উদাহরণ ও Analogy¶

একটা ছোট গ্রাফের $A, D, L$ (সংখ্যাসহ)। ধরা যাক ৪-নোডের ওজনহীন-দিকহীন গ্রাফ, edge-সেট $E = \{ (v_1, v_2), (v_1, v_3), (v_2, v_3), (v_3, v_4) \}$। অর্থাৎ $v_1, v_2, v_3$ একটা ত্রিভুজ, আর $v_4$ কেবল $v_3$-এর সঙ্গে ঝোলানো (pendant)।

adjacency matrix — $A_{ij} = 1$ যেখানে edge আছে:

\[ A = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \]

লক্ষ করো $A = A^\top$ (symmetric), কারণ গ্রাফ দিকহীন।

degree matrix — প্রতিটা কর্ণ = সারির যোগফল: $d_1 = 2, d_2 = 2, d_3 = 3, d_4 = 1$:

\[ D = \begin{bmatrix} 2 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \]

graph Laplacian $L = D - A$:

\[ L = \begin{bmatrix} 2 & -1 & -1 & 0 \\ -1 & 2 & -1 & 0 \\ -1 & -1 & 3 & -1 \\ 0 & 0 & -1 & 1 \end{bmatrix} \]

দ্রুত যাচাই: $L$-এর প্রতিটা সারির যোগফল $0$ (যেমন সারি ৩: $-1 -1 + 3 - 1 = 0$)। এর মানে ধ্রুবক ভেক্টর $\mathbf{1} = [1,1,1,1]^\top$ হলো eigenvalue $0$-এর eigenvector, কারণ $L\mathbf{1} = \mathbf{0}$। যেহেতু গ্রাফ সংযুক্ত (একটাই টুকরো), eigenvalue $0$-এর multiplicity ঠিক $1$।

একটা automorphism। নোড $v_1$ ও $v_2$ পুরোপুরি বিনিময়যোগ্য — দুজনেরই degree $2$, দুজনেই পরস্পরের ও $v_3$-এর সঙ্গে যুক্ত, কেউ $v_4$-এর সঙ্গে যুক্ত নয়। তাই $\sigma = (v_1\, v_2)$ একটা automorphism। এর permutation matrix:

\[ P = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \]

$P A P^\top$ হিসাব করলে (সারি ১↔২ ও কলাম ১↔২ অদলবদল) হুবহু $A$ ফিরে আসে — তাই $P A P^\top = A$, অর্থাৎ এটা সত্যিই একটা automorphism।

WL test-এর এক ধাপ। ওপরের গ্রাফে সব নোড শুরুতে একই রং "$\bullet$" পায় ($c^{(0)}$ সবার সমান)। প্রথম ধাপে প্রতিটা নোডের নতুন রং = (নিজের রং, প্রতিবেশীদের রঙের multiset):

$v_1$: প্রতিবেশী $\{v_2, v_3\}$ → $(\bullet, \{\!\{\bullet, \bullet\}\!\})$ → রং A (২ প্রতিবেশী)
$v_2$: প্রতিবেশী $\{v_1, v_3\}$ → $(\bullet, \{\!\{\bullet, \bullet\}\!\})$ → রং A
$v_3$: প্রতিবেশী $\{v_1, v_2, v_4\}$ → $(\bullet, \{\!\{\bullet, \bullet, \bullet\}\!\})$ → রং B (৩ প্রতিবেশী)
$v_4$: প্রতিবেশী $\{v_3\}$ → $(\bullet, \{\!\{\bullet\}\!\})$ → রং C (১ প্রতিবেশী)

অর্থাৎ WL-এর প্রথম ধাপ ঠিক degree পুনরুদ্ধার করে: $\{v_1, v_2\}$ পায় রং A, $v_3$ পায় B, $v_4$ পায় C। আর যেহেতু $v_1, v_2$ একই রং পেল (আমাদের automorphism-এর সঙ্গে সঙ্গতিপূর্ণ!), WL কখনো এদের আলাদা করতে পারবে না — ঠিক যেমন একটা GNN-ও এদের একই আচরণ দেবে। এটাই message passing আর WL-এর সরাসরি সংযোগ: এক ধাপ WL = এক স্তর message passing (এখানে "বার্তা" = রং, "সমাহার" = multiset নেওয়া)।

permutation invariance (সংখ্যাসহ)। $N = 3, D = 2$ ধরি। feature matrix

\[ X = \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ 5 & 6 \end{bmatrix}, \qquad x_1 = [1,2]^\top,\; x_2 = [3,4]^\top,\; x_3 = [5,6]^\top. \]

নোড ১ ও ২ অদলবদলকারী permutation-এর ম্যাট্রিক্স $P = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}$ প্রয়োগ করলে

\[ PX = \begin{bmatrix} 3 & 4 \\ 1 & 2 \\ 5 & 6 \end{bmatrix}. \]

এখন sum aggregator দেখি:

\[ \sum_{i=1}^{3} x_i = \begin{bmatrix} 1+3+5 \\ 2+4+6 \end{bmatrix} = \begin{bmatrix} 9 \\ 12 \end{bmatrix}, \qquad \sum_{i=1}^{3} (PX)_i = \begin{bmatrix} 3+1+5 \\ 4+2+6 \end{bmatrix} = \begin{bmatrix} 9 \\ 12 \end{bmatrix}. \]

দুটো সমান! একইভাবে mean ও max-ও অপরিবর্তিত: $\operatorname{mean}(X) = \operatorname{mean}(PX) = [3, 4]^\top$, আর $\max_i x_i = \max_i (PX)_i = [5, 6]^\top$। এই কারণেই GNN-এর pooling-এ এই aggregator ব্যবহৃত হয় — নোডের ক্রম বদলালেও graph-স্তরের উত্তর অটল থাকে।

Analogy (উপমা)

permutation invariance = ক্লাসের গড় নম্বর। একটা ক্লাসের গড় নম্বর বের করতে ছাত্রদের কোন ক্রমে সাজালাম তাতে কিছু যায়-আসে না — গড় একই। GNN-এর pooling ঠিক তেমন।

WL test = গুজব/পরিচয় ছড়ানো। প্রথমে সবাই "অজানা"। প্রতি রাউন্ডে প্রত্যেকে তার প্রতিবেশীদের বর্তমান "পরিচয়ের তালিকা" শুনে নিজের নতুন পরিচয় ঠিক করে। কয়েক রাউন্ড পরে পরিচয়গুলো স্থির হয়ে যায়। দুটো নেটওয়ার্কে যদি পরিচয়ের সংখ্যাতত্ত্ব (histogram) কখনো আলাদা হয়, তারা নিশ্চিতভাবে ভিন্ন গঠনের।

graph Laplacian = অমসৃণতার শাস্তি। $x^\top L x = \frac{1}{2}\sum w_{ij}(x_i - x_j)^2$ — যুক্ত নোডদের মান যত আলাদা, তত বেশি "শক্তি"। মসৃণ signal-এর শক্তি কম; এটাই টানা-রাবার-চাদরের (elastic sheet) স্থিতিশক্তির গ্রাফ-সংস্করণ।

৫. সাধারণ ভুল (Common mistakes)¶

নোডের ক্রমকে "তথ্য" ভাবা। নোড $1, 2, 3, \dots$ নম্বরিং সম্পূর্ণ ইচ্ছাধীন — এতে কোনো অর্থ নেই। যে model নম্বরিংয়ের ওপর নির্ভর করে (যেমন সরল MLP-তে সারি-সারি বসিয়ে দেওয়া) সে permutation invariance ভাঙে এবং একই গ্রাফকে ভিন্ন ভাবে "দেখে"।
degree matrix $D$-কে ভরা (dense) ম্যাট্রিক্স ভাবা। $D$ সবসময় diagonal — কেবল কর্ণে degree, বাকি সব $0$। $D$ কখনোই $A$-এর মতো সংযোগ-প্যাটার্ন ধরে না।
$L = D - A$ আর $L = A - D$ গুলিয়ে ফেলা। সঠিক সংজ্ঞা $L = D - A$ (degree আগে)। উল্টোটা নিলে $L$ negative-semidefinite হয়ে যায়, eigenvalue-এর চিহ্ন উল্টে যায়, spectral বিশ্লেষণ ভুল হয়।
WL test মিললে "isomorphic নিশ্চিত" ভাবা। WL histogram মিললে test অমীমাংসিত — graph দুটো isomorphic হতেও পারে, নাও পারে। WL কেবল আলাদা করতে পারলে নিশ্চিত রায় দেয় ("isomorphic নয়")। মিললে কোনো নিশ্চয়তা নেই (যেমন $C_6$ বনাম $2 \times C_3$)।
সব aggregator-কে permutation-invariant ভাবা। sum/mean/max invariant, কিন্তু "প্রথম প্রতিবেশী", "concatenation ক্রম অনুসারে", বা RNN-এ ক্রম-নির্ভর feed — এগুলো নয়। GNN-এর $\bigoplus$ অবশ্যই invariant হতে হবে, নাহলে গোটা কাঠামো ভেঙে পড়ে।
directed গ্রাফে $A$-কে symmetric ভাবা। digraph-এ সাধারণত $A_{ij} \neq A_{ji}$, তাই $A$ অপ্রতিসম, এবং তখন $L = D - A$-এর PSD/eigen-decomposition-এর সুন্দর ধর্মগুলো সরাসরি খাটে না (ঐগুলো দিকহীন ক্ষেত্রের জন্য)।
disconnected গ্রাফে দূরত্বকে সসীম ভাবা। যদি $v_i, v_j$-এর মধ্যে কোনো পথ না থাকে, $d_G(v_i, v_j) = \infty$। আর Laplacian-এ eigenvalue $0$-এর multiplicity $>1$ হলে সেটা সতর্কসংকেত: গ্রাফ একাধিক টুকরোয় বিভক্ত।

৬. এক্সারসাইজ (Exercises)¶

নিচের গ্রাফ $G_\star$ ব্যবহার করো যেখানে দরকার: $V = \{v_1, v_2, v_3, v_4\}$, ওজনহীন-দিকহীন edge-সেট $E = \{(v_1, v_2), (v_2, v_3), (v_3, v_4), (v_4, v_1)\}$ — অর্থাৎ ৪-নোডের একটা চক্র (cycle) $C_4$।

(সহজ) $G_\star$-এর জন্য adjacency matrix $A$ লেখো এবং দেখাও এটা symmetric।
(সহজ) $G_\star$-এর degree matrix $D$ বের করো এবং $D_{ii} = \sum_j A_{ij}$ যাচাই করো। এই গ্রাফ কি $k$-regular? হলে $k = ?$
(সহজ) $L = D - A$ বের করো এবং যাচাই করো প্রতিটা সারির যোগফল $0$। এই ধর্মটা কোন eigenvector সম্পর্কে কী বলে?
(মাঝারি) যুক্তি দিয়ে দেখাও: যেকোনো ওজনহীন-দিকহীন গ্রাফের adjacency matrix সবসময় symmetric — কেন?
(মাঝারি) $G_\star$-এর একটা অ-তুচ্ছ (non-trivial) automorphism খুঁজে বের করো, তার permutation matrix $P$ লেখো, এবং $P A P^\top = A$ যাচাই করো।
(মাঝারি) $N = 3, D = 2$ এবং $X = \begin{bmatrix} 2 & 0 \\ 0 & 4 \\ 6 & 2 \end{bmatrix}$। নোড ১ ও ৩ অদলবদলকারী $P$-এর জন্য $PX$ বের করো এবং দেখাও sum ও mean aggregator অপরিবর্তিত — এই ধর্মটা GNN-এ কেন জরুরি?
(মাঝারি-কঠিন) $G_\star$-এর জন্য signal $x = [1, -1, 1, -1]^\top$ নাও। $x^\top L x$ সরাসরি ম্যাট্রিক্স-গুণে এবং $\frac{1}{2}\sum_{(i,j)\in E} (x_i - x_j)^2$ সূত্রে — দুইভাবে হিসাব করে দেখাও ফল একই। এই মান কী নির্দেশ করে?
(কঠিন) দুটো গ্রাফ: $G_1 = C_6$ (৬-নোডের একটা চক্র) আর $G_2 = 2 \times C_3$ (দুটো আলাদা ত্রিভুজ)। এক ধাপ (এবং তারপরও) 1-WL চালাও। WL কি এদের আলাদা করতে পারে? এর সঙ্গে GNN-এর কোন সীমাবদ্ধতা যুক্ত?
(কঠিন) ব্যাখ্যা করো কেন graph Laplacian-এর eigenvalue $0$-এর multiplicity গ্রাফের connected component সংখ্যার সমান। একটা disconnected উদাহরণ (যেমন দুটো আলাদা edge) দিয়ে যাচাই করো।

৭. সমাধান (ব্যাখ্যাসহ)¶

১-নং সমাধান দেখাও

$C_4$-এ edge আছে $(v_1,v_2), (v_2,v_3), (v_3,v_4), (v_4,v_1)$ — অর্থাৎ $v_1{-}v_2{-}v_3{-}v_4{-}v_1$ একটা বদ্ধ চক্র। ওজনহীন হওয়ায় $A_{ij} = 1$ যেখানে edge:

\[ A = \begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{bmatrix} \]

symmetric যাচাই: $A_{12} = A_{21} = 1$, $A_{14} = A_{41} = 1$, $A_{23} = A_{32} = 1$, $A_{34} = A_{43} = 1$ — সব $A_{ij} = A_{ji}$, তাই $A = A^\top$। কারণ প্রতিটা unordered edge $\{v_i,v_j\}$ দুই symmetric matrix entry-তে encode হয়।

২-নং সমাধান দেখাও

প্রতিটা নোডের degree = সারির যোগফল। প্রতিটা নোড ঠিক ২টা প্রতিবেশীর সঙ্গে যুক্ত: $d_1 = d_2 = d_3 = d_4 = 2$। তাই

\[ D = \begin{bmatrix} 2 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 2 \end{bmatrix} \]

যাচাই: সারি ১-এর যোগফল $0+1+0+1 = 2 = D_{11}$। সব নোডের degree সমান ($=2$), তাই গ্রাফটা 2-regular — যা আসলে সব cycle graph $C_N$-এর সাধারণ ধর্ম।

৩-নং সমাধান দেখাও

$L = D - A$:

\[ L = \begin{bmatrix} 2 & -1 & 0 & -1 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & -1 \\ -1 & 0 & -1 & 2 \end{bmatrix} \]

প্রতিটা সারির যোগফল: $2 - 1 + 0 - 1 = 0$ (সব সারিতেই)। এর মানে $L \mathbf{1} = \mathbf{0}$, যেখানে $\mathbf{1} = [1,1,1,1]^\top$। অর্থাৎ ধ্রুবক ভেক্টর $\mathbf{1}$ হলো eigenvalue $\lambda = 0$-এর eigenvector। যেহেতু $C_4$ সংযুক্ত (একটাই টুকরো), $0$-এর multiplicity ঠিক $1$ — এটাই বলছে গ্রাফটা এক-খণ্ড।

৪-নং সমাধান দেখাও

ওজনহীন-undirected graph-এ edge হলো unordered pair $\{v_i,v_j\}$। Adjacency matrix সেই এক edge-কে দুই orientation-এ encode করে। তাই

\[ A_{ij}=1\iff \{v_i,v_j\}\in E\iff A_{ji}=1. \]

প্রতিটা $(i,j)$-এর জন্য $A_{ij}=A_{ji}$, অতএব $A=A^\top$। Digraph-এ $(v_i,v_j)$ ও $(v_j,v_i)$ independent edge, তাই এই implication থাকে না এবং $A$ asymmetric হতে পারে।

৫-নং সমাধান দেখাও

$C_4$-এর একটা স্বাভাবিক symmetry হলো "চক্র বরাবর এক ধাপ ঘোরানো": $v_1 \to v_2 \to v_3 \to v_4 \to v_1$, অর্থাৎ $\sigma(1)=2, \sigma(2)=3, \sigma(3)=4, \sigma(4)=1$। এর permutation matrix ($P_{ij}=1$ যদি নোড $i$ নোড $j$-এ যায়):

\[ P = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix} \]

$P A P^\top$ মানে $A$-এর সারি ও কলাম উভয়কে এই ঘূর্ণন অনুসারে সাজানো। যেহেতু $C_4$-এর প্রতিটা নোড একইভাবে দুই প্রতিবেশীর সঙ্গে যুক্ত, ঘোরানোর পরও চক্র-প্যাটার্ন অটুট থাকে — ফলে $P A P^\top = A$। তাই এটা একটা automorphism। (আসলে $C_4$-এর automorphism group হলো dihedral group $D_4$, ৮টা সদস্য: ৪টা ঘূর্ণন + ৪টা প্রতিফলন।)

৬-নং সমাধান দেখাও

নোড ১ ও ৩ অদলবদলকারী permutation matrix $P = \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}$। প্রয়োগ করলে (সারি ১ ও ৩ অদলবদল):

\[ PX = \begin{bmatrix} 6 & 2 \\ 0 & 4 \\ 2 & 0 \end{bmatrix} \]

sum: $\sum_i x_i = \begin{bmatrix} 2+0+6 \\ 0+4+2 \end{bmatrix} = \begin{bmatrix} 8 \\ 6 \end{bmatrix}$, আর $\sum_i (PX)_i = \begin{bmatrix} 6+0+2 \\ 2+4+0 \end{bmatrix} = \begin{bmatrix} 8 \\ 6 \end{bmatrix}$ — সমান।

mean: দুটোই $\frac{1}{3}\begin{bmatrix} 8 \\ 6 \end{bmatrix} = \begin{bmatrix} 8/3 \\ 2 \end{bmatrix}$ — সমান।

কেন জরুরি: GNN-এর শেষে সব নোডের feature pool করে graph-স্তরের একটা vector বানানো হয়। নোডের নামকরণ ইচ্ছাধীন বলে এই pooling permutation-invariant না হলে একই গ্রাফ ভিন্ন নামকরণে ভিন্ন উত্তর দিত — যা অর্থহীন। sum/mean এই invariance নিশ্চিত করে।

৭-নং সমাধান দেখাও

$x = [1, -1, 1, -1]^\top$, $L$ হলো ৩-নং সমাধানের ম্যাট্রিক্স।

সরাসরি: প্রথমে $Lx$। সারি ১: $2(1) + (-1)(-1) + 0(1) + (-1)(-1) = 2 + 1 + 0 + 1 = 4$। প্রতিসাম্যের কারণে $Lx = [4, -4, 4, -4]^\top = 4x$ (অর্থাৎ $x$ হলো $\lambda = 4$-এর eigenvector)। তাই

\[ x^\top L x = x^\top (4x) = 4 \, \|x\|^2 = 4 \times 4 = 16. \]

সূত্রে: $\frac{1}{2}\sum_{(i,j)\in E} (x_i - x_j)^2$ যেখানে প্রতিটা অক্রমিক edge দুবার (উভয় দিকে) গোনা হয়, তা $\sum_{\text{edge}} (x_i - x_j)^2$-এর সমান। ৪টা edge: $(v_1,v_2): (1-(-1))^2 = 4$; $(v_2,v_3): 4$; $(v_3,v_4): 4$; $(v_4,v_1): 4$। যোগফল $= 16$। দুইভাবেই $16$ — মিলে গেল।

অর্থ: $x$ প্রতিবেশী নোডে বিপরীত চিহ্ন নেয় ($+1, -1$ পর্যায়ক্রমে), তাই এটা সবচেয়ে "অমসৃণ" signal — উচ্চ Dirichlet energy, বড় eigenvalue। এটাই গ্রাফের সর্বোচ্চ-কম্পাঙ্ক (highest-frequency) mode।

৮-নং সমাধান দেখাও

$G_1 = C_6$: প্রতিটা নোড 2-regular, দুই প্রতিবেশীও 2-regular। $G_2 = 2 \times C_3$: দুটো ত্রিভুজ, প্রতিটা নোডও 2-regular, প্রতিবেশীও 2-regular।

1-WL চালাই। শুরুতে সব নোড একই রং $\bullet$। প্রথম ধাপে প্রতিটা নোডের রং = $(\bullet, \{\!\{\bullet, \bullet\}\!\})$ — দুই গ্রাফের সব নোড অভিন্ন, কারণ সবার degree ঠিক $2$। দ্বিতীয় ধাপেও প্রতিটা নোডের প্রতিবেশী একই রঙের, তাই রং আর বদলায় না — স্থির হয়ে যায় সবাই একই রঙে।

ফলে দুই গ্রাফের রঙের histogram সবসময় অভিন্ন ("৬টা নোড একই রঙে")। WL এদের আলাদা করতে পারে না — যদিও $G_1$ সংযুক্ত আর $G_2$ দুই-খণ্ড, তাই তারা isomorphic নয়!

GNN সংযোগ: যেহেতু message-passing GNN 1-WL-এর চেয়ে বেশি শক্তিশালী নয়, একটা সাধারণ GNN-ও $C_6$ আর $2\times C_3$ আলাদা করতে পারবে না। এটাই GNN-এর বিখ্যাত expressivity সীমাবদ্ধতা — এবং এই কারণেই higher-order GNN, positional encoding (Laplacian eigenvector দিয়ে), বা subgraph-ভিত্তিক পদ্ধতি উদ্ভাবিত হয়েছে।

৯-নং সমাধান দেখাও

ধরো গ্রাফের $c$টা connected component। নোডগুলোকে component অনুযায়ী সাজালে $L$ ব্লক-diagonal হয়: $L = \operatorname{diag}(L_1, L_2, \dots, L_c)$, যেখানে $L_m$ হলো $m$-তম component-এর Laplacian।

প্রতিটা connected component-এর জন্য: সেই block-এর সারি-যোগফল $0$, তাই ঐ component-এর ওপর ধ্রুবক ভেক্টর $\mathbf{1}_m$ (ঐ component-এ $1$, বাইরে $0$) হলো $\lambda = 0$-এর eigenvector। আর একটা সংযুক্ত গ্রাফে $\lambda = 0$-এর eigenspace ঠিক এক-মাত্রিক (কারণ $x^\top L x = \frac{1}{2}\sum w_{ij}(x_i-x_j)^2 = 0$ মানে প্রতিটা যুক্ত জোড়ায় $x_i = x_j$, আর সংযুক্ত বলে পুরো component-এ $x$ ধ্রুবক)।

তাই $c$টা component থেকে $c$টা রৈখিকভাবে-স্বাধীন eigenvector ($\mathbf{1}_1, \dots, \mathbf{1}_c$) — অর্থাৎ eigenvalue $0$-এর multiplicity $= c$।

যাচাই: দুটো আলাদা edge, $\{(v_1,v_2)\}$ ও $\{(v_3,v_4)\}$ (২টা component)। এখানে $L = \begin{bmatrix} 1 & -1 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 0 & 0 & 1 & -1 \\ 0 & 0 & -1 & 1 \end{bmatrix}$। eigenvalue: $\{0, 0, 2, 2\}$ — $0$-এর multiplicity $= 2 = $ component সংখ্যা। মিলে গেল।

৮. সারসংক্ষেপ ও Checklist¶

এই অধ্যায়ে গ্রাফ তত্ত্বের যে ভিত্তি Geometric Deep Learning-কে দাঁড় করায়, তা এক জায়গায়:

গ্রাফ $G = (V, E)$ — node/vertex আর edge; দিকযুক্ত বা দিকহীন; প্রতিবেশ $\mathcal{N}(v_i)$।
ম্যাট্রিক্স-রূপ: adjacency $A$ (দিকহীন-ওজনহীন হলে binary ও symmetric), degree $D$ (diagonal, $D_{ii} = \sum_j A_{ij}$), graph Laplacian $L = D - A$ (symmetric, PSD)।
symmetry: নোড-নামকরণ ইচ্ছাধীন → permutation matrix $P$, রূপান্তর $A' = PAP^\top$; automorphism মানে $PAP^\top = A$; graph invariant permutation-এ অটল।
permutation invariance: sum/mean/max aggregator নোড-ক্রম নির্বিশেষে একই — GNN-এর pooling ও message-passing-এর অপরিহার্য শর্ত।
signal ও spectral: feature vector field $F: V \to \mathbb{R}^D$; $x^\top L x = \frac{1}{2}\sum w_{ij}(x_i-x_j)^2$ = graph Dirichlet energy (মসৃণতার পরিমাপ); $L = U\Lambda U^\top$ → graph Fourier basis; eigenvalue $0$-এর multiplicity = component সংখ্যা।
WL test ও GNN: color refinement দিয়ে isomorphism-যাচাই; message-passing GNN $\le$ 1-WL শক্তি — তাই কিছু গ্রাফ (যেমন $C_6$ বনাম $2\times C_3$) GNN আলাদা করতে পারে না।

Checklist — নিজেকে যাচাই করো:

[ ] একটা ছোট গ্রাফ থেকে $A$, $D$, $L = D - A$ হাতে-কলমে লিখতে পারি এবং $L$-এর সারি-যোগফল $0$ যাচাই করতে পারি।
[ ] বলতে পারি কেন দিকহীন-ওজনহীন $A$ সবসময় symmetric, আর digraph-এ কেন নয়।
[ ] একটা গ্রাফের অ-তুচ্ছ automorphism ও তার permutation matrix $P$ খুঁজে $PAP^\top = A$ যাচাই করতে পারি।
[ ] sum/mean/max যে permutation-invariant তা সংখ্যাসহ দেখাতে পারি এবং GNN-এ কেন জরুরি ব্যাখ্যা করতে পারি।
[ ] $x^\top L x = \frac{1}{2}\sum w_{ij}(x_i-x_j)^2$ প্রমাণ করতে পারি এবং একে Dirichlet energy/মসৃণতা হিসেবে ব্যাখ্যা করতে পারি।
[ ] $L$ কেন symmetric ও positive-semidefinite বোঝাতে পারি।
[ ] WL test-এর এক ধাপ চালাতে পারি এবং message passing-এর সঙ্গে সংযোগ বলতে পারি।
[ ] WL/GNN-এর সীমাবদ্ধতা ($C_6$ বনাম $2\times C_3$) উদাহরণসহ ব্যাখ্যা করতে পারি।
[ ] eigenvalue $0$-এর multiplicity ও connected component-এর সম্পর্ক বলতে পারি।

➡️ সমাপ্তি: এই Part-এর সব গণিত মিলে Geometric Deep Learning-এর ভিত্তি। মূল সূচিতে ফিরে যাও।