0Pricing
Learn AI with Python · Lekcja

Teoria grafów na potrzeby uczenia maszynowego

Węzły, krawędzie, macierz sąsiedztwa, typy grafów, cechy grafów, reprezentacje sieci społecznościowych.

Teoria grafów na potrzeby uczenia maszynowego to bezpłatna lekcja Learn AI with Python na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Learn AI with Python, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Learn AI with Python zawiera 4 lekcji w sumie.

Czym jest graf

Graf modeluje encje oraz relacje między nimi. Formalnie graf to G = (V, E), gdzie V jest zbiorem wierzchołków (węzłów), a E jest zbiorem krawędzi łączących pary węzłów. Wiele rzeczywistych systemów ma naturalnie postać grafów.

Węzły i krawędzie

Każdy węzeł reprezentuje encję (użytkownika, atom, stronę internetową). Każda krawędź reprezentuje relację (przyjaźń, wiązanie chemiczne, hiperłącze). Uczenie maszynowe na grafach korzysta z tej struktury połączeń, a nie tylko z izolowanych próbek.

Macierz sąsiedztwa

Macierz sąsiedztwa A koduje informacje o tym, które węzły są połączone. Dla n węzłów macierz A ma rozmiar n na n; A[i][j] = 1, jeśli krawędź łączy węzeł i z węzłem j, a w przeciwnym razie 0.

import numpy as np

# Triangle: 0-1, 1-2, 0-2
A = np.array([
    [0, 1, 1],
    [1, 0, 1],
    [1, 1, 0],
])

Cechy węzłów X

Oprócz struktury każdy węzeł zwykle ma własny wektor cech. Po ułożeniu ich jeden pod drugim tworzą macierz cech X o kształcie (num_nodes, num_features). W grafie społecznościowym jeden wiersz może zawierać wiek użytkownika, liczbę jego postów i wiek konta.

X = np.array([
    [25, 120, 3.0],   # node 0
    [31,  45, 5.5],   # node 1
    [22, 300, 1.2],   # node 2
])

Macierz stopni

Stopień węzła to liczba jego krawędzi. Macierz stopni D jest diagonalna, a każdy element na przekątnej jest równy stopniowi danego węzła. Stanowi ona podstawowy element laplasjanu grafu.

D = np.diag(A.sum(axis=1))
# Each diagonal entry = number of neighbors

Laplasjan grafu

Laplasjan grafu definiuje się jako L = D - A. Opisuje on różnice wartości między połączonymi węzłami i ma fundamentalne znaczenie w spektralnej teorii grafów oraz w wielu sformułowaniach GNN.

L = D - A
print(L)

Dlaczego laplasjan ma znaczenie

Wartości własne i wektory własne laplasjanu ujawniają globalną strukturę: spójność, klastry i gładkość. Sploty grafowe często wyprowadza się z laplasjanu, dlatego zrozumienie L = D - A jest kluczowe dla zrozumienia GNN.

Grafy skierowane i nieskierowane

W grafie nieskierowanym krawędź nie ma kierunku (jak przyjaźń), więc macierz A jest symetryczna. W grafie skierowanym krawędzie mają określony kierunek (jak obserwowanie użytkownika lub cytowanie), dlatego macierz A może być niesymetryczna: A[i][j] może różnić się od A[j][i].

# Directed: 0 -> 1 but not 1 -> 0
A_dir = np.array([
    [0, 1, 0],
    [0, 0, 1],
    [0, 0, 0],
])

Grafy ważone

Krawędzie mogą mieć wagi reprezentujące siłę lub odległość. Wtedy elementy macierzy sąsiedztwa są liczbami rzeczywistymi, a nie tylko wartościami 0/1. W sieci drogowej krawędzie można ważyć czasem przejazdu, a w grafie podobieństwa — podobieństwem kosinusowym.

Wydajne reprezentowanie krawędzi

W przypadku dużych, rzadkich grafów macierz sąsiedztwa marnuje pamięć, ponieważ większość jej elementów ma wartość zero. Zamiast tego frameworki ML przechowują krawędzie jako listę krawędzi (format COO): dwie tablice zawierające źródło i cel każdej krawędzi. PyTorch Geometric nazywa tę strukturę edge_index.

# Triangle edges as edge_index [2, num_edges]
edge_index = [
    [0, 0, 1],   # sources
    [1, 2, 2],   # targets
]

Zastosowania ML na grafach

Grafy występują wszędzie:

  • społecznościowe: rekomendowanie znajomych, wykrywanie społeczności
  • molekularne: przewidywanie właściwości cząsteczek (atomy = węzły, wiązania = krawędzie)
  • grafy wiedzy: predykcja połączeń między encjami i relacjami
  • internetowe/cytowań: ranking i klasyfikacja

Szybki sprawdzian

Proszę sprawdzić swoją wiedzę z teorii grafów.

Podsumowanie

Poznali Państwo podstawy teorii grafów potrzebne w ML:

  • Graf to G = (V, E) z węzłami i krawędziami
  • Macierz sąsiedztwa A koduje połączenia, a X przechowuje cechy węzłów
  • Laplasjan grafu to L = D - A
  • Grafy mogą być skierowane lub nieskierowane, ważone lub nieważone
  • Zastosowania obejmują grafy społecznościowe, molekularne i grafy wiedzy

Często zadawane pytania

Czy lekcja „Teoria grafów na potrzeby uczenia maszynowego” jest bezpłatna?

Tak — pełny tekst „Teoria grafów na potrzeby uczenia maszynowego” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Learn AI with Python, przejdź na CoddyKit PRO. Kurs Learn AI with Python zawiera 4 lekcji w sumie.

Co nauczysz się w „Teoria grafów na potrzeby uczenia maszynowego”?

Węzły, krawędzie, macierz sąsiedztwa, typy grafów, cechy grafów, reprezentacje sieci społecznościowych. Ćwiczysz Learn AI with Python z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Learn AI with Python?

Nie wymagamy żadnego doświadczenia. Learn AI with Python w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.

Ile czasu zajmuje lekcja „Teoria grafów na potrzeby uczenia maszynowego”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Learn AI with Python?

Tak. Każda lekcja Learn AI with Python zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Teoria grafów na potrzeby uczenia maszynowego
  2. Grafowe sieci konwolucyjne (GCN)
  3. Klasyfikacja węzłów za pomocą GNN
  4. Predykcja krawędzi i klasyfikacja grafów
← Powrót do Learn AI with Python