Phase 01: Math Foundations

نظرية الرسومات للتعلم الآلي

الرسوم البيانية هي بنية البيانات للعلاقات. إذا كانت البيانات لديك اتصالات، فأنت بحاجة إلى نظرية الرسوم البيانية.

Type: Build

Language:بايثون

Prerequisites: Phase 1, Lessons 01-03 (linear algebra, matrices)

Time: ~90 minutes

أهداف التعلم

بناء فئة الرسم البياني مع تمثيلات المصفوفات / القائمة المجاورة وتنفيذ عبورات BFS و DFS
احسب الرسم البياني لابلاسي واستخدام قيمه الخاصة للكشف عن المكونات المتصلة والعقدة
تنفيذ جولة واحدة من رسالة نمط GNN تمر كمراتب متراكم المجاورة المعتاد
تطبيق التجميع الطيفي للفصل الرسمي باستخدام متجه Fiedler

المشكلة

الشبكات الاجتماعية والجزيئات قواعد المعرفة وشبكات الاقتباسات وخرائط الطرق كلها هي الرسوم البيانية. تعامل المعلومات التقليدية مع البيانات كجدول مسطحة. كل سطر مستقل. كل صفة هي عمود. ولكن عندما تكون هيكل العلاقات مهمة، تفشل الجداول.

فكر في شبكة اجتماعية. تريد التنبؤ بال منتج الذي سيشتريه المستخدم. تاريخ شراءهم مهم. ولكن تاريخ شراء أصدقائهم مهم أكثر. الاتصالات تحمل الإشارة.

أو فكر في جزيء. تريد أن تتوقع ما إذا كان يربط بروتين. الذرات مهمة، ولكن ما يهم حقا هو كيفية ربط الذرات مع بعضها البعض. الهيكل هو البيانات.

شبكات العصبية الرسمية (GNNs) هي المنطقة الأكثر نمواً في التعلم العميق. وهي تعمل على اكتشاف المخدرات والتوصية الاجتماعية وكشف الاحتيال والنظرية الرسمية المعرفة. كل GNN تبني على نفس الأساس: نظرية الرسم البياني الأساسية.

تحتاج إلى أربعة أشياء:

طريقة لتمثيل الرسوم البيانية كالمصفوفات (لذلك يمكنك مضاعفةها)
خوارزميات عبورية لاستكشاف هيكل الرسم البياني
اللابلاسي -- المصفوفة الوحيدة الأكثر أهمية في نظرية الرسوم البياني الطيفية
نقل الرسائل -- العملية التي تجعل GNNs تعمل

المفهوم

الرسوم البيانية: العقد والحواف

يتكون الرسم البياني G = (V، E) من الروافع (العقد) V والحواف E. كل حافة تربط عقدين.

Directed vs undirected.في الرسم البياني غير الموجّه، يعني الحافة (u، v) أن u يصل إلى v و v يصل إلى u. في الرسم البياني الموجّه، يعني الحافة (u، v) أن u تشير إلى v، ولكن ليس بالضرورة العكس.

Weighted vs unweighted.في الرسم البياني غير الموزن، الحواف إما موجودة أو لا موجودة. في الرسم البياني الموزن، لكل حافة وزن عددي -- مسافة، تكلفة، قوة.

Graph type	Example
Undirected, unweighted	Facebook friendship network
Directed, unweighted	Twitter follow network
Undirected, weighted	Road map (distances)
Directed, weighted	Web page links (PageRank scores)

المصفوفة المجاورة

المصفوفة المجاورة A هي تمثيل الأساس. بالنسبة لرسم البياني مع n عقد:

A[i][j] = 1    if there is an edge from node i to node j
A[i][j] = 0    otherwise

بالنسبة للجرافات غير الموجزة، A هو متماثل: A[i][j] = A[j][i]. بالنسبة للجرافات الموزعة، A[i][j] = وزن الحافة (i، j).

Example -- a triangle:

Nodes: 0, 1, 2
Edges: (0,1), (1,2), (0,2)

A = [[0, 1, 1],
     [1, 0, 1],
     [1, 1, 0]]

المصفوفة المجاورة هي المدخلات لكل GNN. عمليات المصفوفة على A تتوافق مع عمليات على الرسم البياني.

درجة

درجة العقد هو عدد الحواف المتصلة بها. بالنسبة للجرافات الموجزة ، لديك درجة (الحواف الدخول) والدرجة الخارجة (الحواف الخروج).

المصفوفة D هي متناحية:

D[i][i] = degree of node i
D[i][j] = 0    for i != j

على سبيل المثال مثل مثلث: D = diag(2,2,2) لأن كل عقدة ترتبط بأخرى اثنين.

درجة تخبرك عن أهمية العقدة. درجة عالية = عقدة العقدة. توزيع درجة الشبكة يكشف عن بنيته. تتبع الشبكات الاجتماعية قوانين الطاقة (قليل من العقدة، العديد من عقدة الورق). الرسوم البيانية العشوائية لديها درجات موزعة بويسون.

الـ BFS و الـ DFS

الخوارزميات الرئيسية لتحويل الرسوم البياني.

Breadth-First Search (BFS):استكشف جميع الجيران أولاً، ثم جيران الجيران.

BFS from node 0:
  Visit 0
  Queue: [1, 2]        (neighbors of 0)
  Visit 1
  Queue: [2, 3]        (add neighbors of 1)
  Visit 2
  Queue: [3]           (neighbors of 2 already visited)
  Visit 3
  Queue: []            (done)

يجد BFS أقصر المسارات في الرسوم البيانية غير الموزعة. المسافة من البداية إلى أي عقدة تساوي مستوى BFS الذي يتم اكتشاف العقدة الأولى. لهذا السبب يستخدم BFS لمسافات العد الهوب في الشبكات الاجتماعية.

Depth-First Search (DFS):إذهب بعمق قدر الإمكان قبل التراجع. تستخدم كومة (LIFO) أو التكرار.

DFS from node 0:
  Visit 0
  Stack: [1, 2]        (neighbors of 0)
  Visit 2               (pop from stack)
  Stack: [1, 3]         (add neighbors of 2)
  Visit 3               (pop from stack)
  Stack: [1]
  Visit 1               (pop from stack)
  Stack: []             (done)

DFS مفيد لل:

العثور على المكونات المتصلة (تشغيل DFS من العقد غير المرصدة)
كشف الدورة (الجوارب الخلفية في شجرة DFS)
التصفية الترتيبية (تسلسل الانتهاء من DFS العكس)

Algorithm	Data structure	Finds	Use case
BFS	Queue	Shortest paths	Social network distance, knowledge graph traversal
DFS	Stack	Components, cycles	Connectivity, topological sort

الرسم البياني لابلاسي

L = D - A. أهم ماتريكس في نظرية الرسومات الطيفية.

بالنسبة للثلث:

D = [[2, 0, 0],    A = [[0, 1, 1],    L = [[2, -1, -1],
     [0, 2, 0],         [1, 0, 1],         [-1, 2, -1],
     [0, 0, 2]]         [1, 1, 0]]         [-1, -1,  2]]

اللابلاسي لديه خصائص ملحوظة:

L is positive semi-definite.جميع القيم الخاصة هي >= 0.

The number of zero eigenvalues equals the number of connected components.الرسم البياني المتصل لديه قيمة خاصة واحدة صفر. الرسم البياني مع 3 مكونات منفصلة لديه ثلاثة قيم خاصة صفر.

The smallest non-zero eigenvalue (Fiedler value) measures connectivity.قيمة فيدر كبيرة تعني أن الرسم البياني متصلة بشكل جيد. قيمة فيدر صغيرة تعني أن الرسم البياني لديه نقطة ضعيفة -- عقدة زجاجة.

The eigenvector of the Fiedler value (Fiedler vector) reveals the best split.العقد مع القيم الإيجابية تذهب في مجموعة واحدة، العقد مع القيم السلبية تذهب في الأخرى. هذا هو التجميع الطيفي.

graph TD
    subgraph "Graph to Matrices"
        G["Graph G"] --> A["Adjacency Matrix A"]
        G --> D["Degree Matrix D"]
        A --> L["Laplacian L = D - A"]
        D --> L
    end
    subgraph "Spectral Analysis"
        L --> E["Eigenvalues of L"]
        L --> V["Eigenvectors of L"]
        E --> C["Connected components (zeros)"]
        E --> F["Connectivity (Fiedler value)"]
        V --> S["Spectral clustering"]
    end

الخصائص المتطرفة

وتكشف القيم الخاصة للمصفوفة المجاورة واللابلاسي عن الخصائص الهيكلية دون أي عبور.

Spectral clusteringيعمل على هذا النحو:

احسب اللابلاسي L
العثور على أصغر متجهات خاصة من L (تغطي الأول، وهو واحد لكل الرسوم البيانية المتصلة)
استخدم هذه المتجهات الخاصة كنسائق جديدة لكل عقد
إشغال المتوسطات k على تلك الإحداثيات

لماذا يعمل هذا؟ يرمز المتجهات الخاصة ل L "أسرع" الوظائف على الرسم البياني. العقدات التي ترتبط بشكل جيد تحصل على قيم متجهات ذاتية مماثلة. العقدات المنفصلة عن طريق عنق الزجاجة تحصل على قيم مختلفة. المتجهات ذاتية بشكل طبيعي تفصل المجموعات.

Random walk connection.يرتبط اللابلاسي المعادلة بالمشيات العشوائية على الرسم البياني. التوزيع الثابت للمشي العشوائي متناسب مع درجة العقدة. يعتمد وقت الاختلاط (كم سرعة التقارب في المشي) على الفجوة الطيفية.

إرسال الرسالة

العملية الأساسية للشبكات العصبية الرسمية. كل عقد يجمع الرسائل من جيرانه، ويمجملها، ويحديث حالته الخاصة.

h_v^(k+1) = UPDATE(h_v^(k), AGGREGATE({h_u^(k) : u in neighbors(v)}))

في أبسط شكل، جمع = متوسط، وتحديث = تحويل خطي + تفعيل:

h_v^(k+1) = sigma(W * mean({h_u^(k) : u in neighbors(v)}))

هذا هو مضاعفة المصفوفة في التنكر. إذا كان H هو المصفوفة من جميع ميزات العقدة و A هو المصفوفة المجاورة:

H^(k+1) = sigma(A_norm * H^(k) * W)

حيث A_norm هي المصفوفة المجاورة المعيارية (كل سطر يصل إلى 1).

تسمح جولة واحدة من إرسال الرسائل لكل عقدة "بإبصار" جيرانها المباشرين. جولتين تسمح لها برؤية جير جير جير جيرانها. جولات K تعطى كل عقدة معلومات من حي K-hop.

graph LR
    subgraph "Round 0"
        A0["Node A: [1,0]"]
        B0["Node B: [0,1]"]
        C0["Node C: [1,1]"]
    end
    subgraph "Round 1 (aggregate neighbors)"
        A1["Node A: avg(B,C) = [0.5, 1.0]"]
        B1["Node B: avg(A,C) = [1.0, 0.5]"]
        C1["Node C: avg(A,B) = [0.5, 0.5]"]
    end
    A0 --> A1
    B0 --> A1
    C0 --> A1
    A0 --> B1
    C0 --> B1
    A0 --> C1
    B0 --> C1

المفاهيم وتطبيقات ML

Concept	ML Application
Adjacency matrix	GNN input representation
Graph Laplacian	Spectral clustering, community detection
BFS/DFS	Knowledge graph traversal, path finding
Degree distribution	Node importance, feature engineering
Message passing	GNN layers (GCN, GAT, GraphSAGE)
Eigenvalues of L	Community detection, graph partitioning
Spectral clustering	Unsupervised node grouping
PageRank	Node importance, web search

بناءها

الخطوة الأولى: صف الرسم البياني من الصفر

pythonclass Graph:
    def __init__(self, n_nodes, directed=False):
        self.n = n_nodes
        self.directed = directed
        self.adj = {i: {} for i in range(n_nodes)}

    def add_edge(self, u, v, weight=1.0):
        self.adj[u][v] = weight
        if not self.directed:
            self.adj[v][u] = weight

    def neighbors(self, node):
        return list(self.adj[node].keys())

    def degree(self, node):
        return len(self.adj[node])

    def adjacency_matrix(self):
        import numpy as np
        A = np.zeros((self.n, self.n))
        for u in range(self.n):
            for v, w in self.adj[u].items():
                A[u][v] = w
        return A

    def degree_matrix(self):
        import numpy as np
        D = np.zeros((self.n, self.n))
        for i in range(self.n):
            D[i][i] = self.degree(i)
        return D

    def laplacian(self):
        return self.degree_matrix() - self.adjacency_matrix()

قائمة الحيطة (self.adjتُستخدم تحويل المصفوفة المجاورة numpy لأن جميع العمليات الطيفية تحتاج إليها.

الخطوة الثانية: BFS و DFS

pythonfrom collections import deque

def bfs(graph, start):
    visited = set()
    order = []
    distances = {}
    queue = deque([(start, 0)])
    visited.add(start)
    while queue:
        node, dist = queue.popleft()
        order.append(node)
        distances[node] = dist
        for neighbor in graph.neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return order, distances


def dfs(graph, start):
    visited = set()
    order = []
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbor in reversed(graph.neighbors(node)):
            if neighbor not in visited:
                stack.append(neighbor)
    return order

يستخدم BFS ديك (صف المزدوج) ل O(1) popleft. DFS يستخدم قائمة كمركز. كلتا الزيارات كل عقدة مرة بالضبط - O(V + E) وقت.

الخطوة الثالثة: المكونات المتصلة والقيم الخاصة لبلاتسي

pythondef connected_components(graph):
    visited = set()
    components = []
    for node in range(graph.n):
        if node not in visited:
            order, _ = bfs(graph, node)
            visited.update(order)
            components.append(order)
    return components


def laplacian_eigenvalues(graph):
    import numpy as np
    L = graph.laplacian()
    eigenvalues = np.linalg.eigvalsh(L)
    return eigenvalues

eigvalshهو للمصفوفات التناظرية -- اللابلاسي هو متناظري دائما للخطوط غير الموجزة. يعيد القيم الخاصة في الترتيب الصاعد. احتساب الصفر للعثور على عدد المكونات المتصلة.

الخطوة الرابعة: التجميع المتطويع

pythondef spectral_clustering(graph, k=2):
    import numpy as np
    L = graph.laplacian()
    eigenvalues, eigenvectors = np.linalg.eigh(L)
    features = eigenvectors[:, 1:k+1]

    labels = np.zeros(graph.n, dtype=int)
    for i in range(graph.n):
        if features[i, 0] >= 0:
            labels[i] = 0
        else:
            labels[i] = 1
    return labels

بالنسبة k=2 ، فإن علامة متجه Fiedler تقسم الرسم البياني إلى مجموعتين. بالنسبة k>2 ، يمكنك تشغيل k- المتوسط على الممرات الخاصة الأولى k (باستثناء المتجهات الخاصة البسيطة للجميع).

الخطوة 5: إرسال الرسالة

pythondef message_passing(graph, features, weight_matrix):
    import numpy as np
    A = graph.adjacency_matrix()
    row_sums = A.sum(axis=1, keepdims=True)
    row_sums[row_sums == 0] = 1
    A_norm = A / row_sums
    aggregated = A_norm @ features
    output = aggregated @ weight_matrix
    return output

هذه جولة واحدة من إرسال رسالة GNN. هي الميزات الجديدة لكل عقدة المتوسط الموزن لميزات جيرانها، والتي تحولت بواسطة المصفوفة الوزن. قم بتجميع جولات متعددة لنشر المعلومات بشكل أكبر.

استخدمها

مع networkx و numpy، نفس العمليات هي خط واحد:

pythonimport networkx as nx
import numpy as np

G = nx.karate_club_graph()

A = nx.adjacency_matrix(G).toarray()
L = nx.laplacian_matrix(G).toarray()

eigenvalues = np.linalg.eigvalsh(L.astype(float))
print(f"Smallest eigenvalues: {eigenvalues[:5]}")
print(f"Connected components: {nx.number_connected_components(G)}")

communities = nx.community.greedy_modularity_communities(G)
print(f"Communities found: {len(communities)}")

pr = nx.pagerank(G)
top_nodes = sorted(pr.items(), key=lambda x: x[1], reverse=True)[:5]
print(f"Top 5 PageRank nodes: {top_nodes}")

networkx يُعامل الرسوم البيانية من أي حجم مع خلفيات C المثلى. استخدمها في الإنتاج. استخدم تنفيذك من الصفر لفهم ما تفعله.

تحليل الطيف النمبي

pythonimport numpy as np

A = np.array([
    [0, 1, 1, 0, 0],
    [1, 0, 1, 0, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 1, 0, 1],
    [0, 0, 0, 1, 0]
])

D = np.diag(A.sum(axis=1))
L = D - A

eigenvalues, eigenvectors = np.linalg.eigh(L)
print(f"Eigenvalues: {np.round(eigenvalues, 4)}")
print(f"Fiedler value: {eigenvalues[1]:.4f}")
print(f"Fiedler vector: {np.round(eigenvectors[:, 1], 4)}")

fiedler = eigenvectors[:, 1]
group_a = np.where(fiedler >= 0)[0]
group_b = np.where(fiedler < 0)[0]
print(f"Cluster A: {group_a}")
print(f"Cluster B: {group_b}")

وكتور فيدر يقوم بالرفع الثقيل. إدخالات إيجابية في مجموعة واحدة، سلبية في الأخرى. لا حاجة إلى تحسين متكرر - مجرد واحد التكوين الخاص.

أرسله

هذا الدرس ينتج عن:

outputs/skill-graph-analysis.md-- مرجع مهارات تحليل البيانات المهيكلة على الرسم البياني

العلاقات

Concept	Where it shows up
Adjacency matrix	GCN, GAT, GraphSAGE input
Laplacian	Spectral clustering, ChebNet filters
BFS	Knowledge graph traversal, shortest path queries
Message passing	Every GNN layer, neural message passing
Spectral gap	Graph connectivity, mixing time of random walks
Degree distribution	Power-law networks, node feature engineering
Connected components	Preprocessing, handling disconnected graphs
PageRank	Node importance ranking, attention initialization

تستحق GNNs ذكرًا خاصًا. عملية تحويل الرسم البياني في GCN (Kipf & Welling ، 2017) تستخدم المصفوفة المجاورة مع إضافة حلقات ذاتية ، A_hat = A + I:

textH^(l+1) = sigma(D_hat^(-1/2) * A_hat * D_hat^(-1/2) * H^(l) * W^(l))

حيث A_hat = A + I (الجاذبية بالإضافة إلى الحلقات الذاتية) و D_hat هي المصفوفة الدرجة من A_hat. تتأكد الحلقات الذاتية أن كل عقدة تضم خصائصها الخاصة أثناء التجميع. هذه هي بالضبط الرسالة التي تمر مع التطبيع التناظر. D_hat^(-1/2) A_hat D_hat^(-1/2) هي المصفوفة المجاورة المعيارية. يظهر اللابلاسي لأن هذا التطبيع مرتبط بـ L_sym = I - D^(-1/2) A D^(-1/2). فهم اللابلاكية يعني فهم سبب عمل المواد المضادة

التمارين

Implement PageRank from scratch.تبدأ من درجات متساوية. في كل خطوة: درجة ((v) = (1-د) / n + d * جمع ((درجة ((u) / خارج_درجة ((u))) لجميع u التي تشير إلى v. استخدم d = 0.85. اجري حتى التقارب (تغيير < 1e-6). اختبار على الرسم البياني على شبكة صغيرة.

Find communities using spectral clustering.قم بإنشاء الرسم البياني مع مجموعة منفصلة بوضوح (على سبيل المثال ، اثنين من المجموعات المتصلة بحافة واحدة). قم بتشغيل التجميع الطيفي والتحقق من أنه يجد التقسيم الصحيح. ماذا يحدث عندما تضيف المزيد من حواف الحجم المتقاطعة؟

Implement Dijkstra's algorithmللمسارات الأقصر في الرسوم البيانية الموزعة. مقارنة النتائج مع BFS على نفس الرسوم البيانية ذات الوزن المتساوي.

Build a 2-layer message passing network.تطبيق الرسالة المرور مرتين مع مختلف المصفوفات الوزن. أظهر أنه بعد جولتين، كل عقدة لديها معلومات من حي 2 جولة.

Analyze a real-world graph.استخدم الرسم البياني لـ Karate Club (34 عقدة و 78 حافة). قم بتحساب توزيع درجة، وقيم خاصة لابلاكية، والتمزيق الطيفي. مقارنة نتيجة التجميع الطيفي بتقسيم الحقيقة الأرضية المعروفة.

الشروط الرئيسية

Term	What people say	What it actually means
Graph	"Nodes and edges"	A mathematical structure G=(V,E) encoding pairwise relationships
Adjacency matrix	"The connection table"	An n x n matrix where A[i][j] = 1 if nodes i and j are connected
Degree	"How connected a node is"	The number of edges touching a node
Laplacian	"D minus A"	L = D - A, the matrix whose eigenvalues reveal graph structure
Fiedler value	"The algebraic connectivity"	The smallest non-zero eigenvalue of L, measuring how well-connected the graph is
BFS	"Level-by-level search"	Traversal that visits all neighbors before going deeper, finds shortest paths
DFS	"Go deep first"	Traversal that follows one path to its end before backtracking
Message passing	"Nodes talk to neighbors"	Each node aggregates information from its neighbors, the core of GNNs
Spectral clustering	"Cluster by eigenvectors"	Partition a graph using eigenvectors of its Laplacian
Connected component	"A separate piece"	A maximal subgraph where every node can reach every other node