Osnovni pojmovi teorije grafova¶

Definicija 1: Graf $G$ predstavlja uređeni par $(V,E)$. Elementi skupa $V$ se nazivaju čvorovi (eng. vertex), a elementi skupa $E$ grane (eng. edge) grafa $G$ gde je $E \subseteq V \times V$. Dva čvora $u,v$ su susedni ako su spojeni granom $e=(u,v)$. Za čvor $u$ i granu $e$ tada kažemo da su incidentni.

Grafovi se prema usmerenosti mogu podeliti na:

Neusmerene grafove, za koje važi da nemaju svojstvo usmerenja između čvorova sa kojima su incidenti, zbog čega grane smatramo skupovima čvorova i pišemo, npr. $e=\{u,v\}$.
Usmerene grafove, za koje važi da grane imaju svojstvo usmerenja od jednog čvora, koji se naziva izlazni čvor ka drugom čvoru koji se naziva ulazni čvor. U tom slučaju, grane grafa ne smatramo skupovima već uređenim parovima i pišemo, npr, $e=(u,v), e=(v,u)$, u zavisnosti od smera usmerenja grane e incidentne sa čvorovima $u,v$.

Grafovi se grafički predstavljaju na sledeći način:

Svaki čvor se predstavlja jednim krugom
Svaka grana se predstavlja linijom koja povezuje čvorove sa kojima je incidentna. Ako je graf usmeren, onda se koristi strelica u smeru od izlaznog čvora ka ulaznom čvoru incidentinim sa tom granom.

Na slici su dati primeri 2 grafa:

Graf $G_1=(V_1, E_1)$, gde je $V_1=\{a, b, c\}, E_1=\{ (a, b), (b, c), (c, b), (c, a)\}$, primer je usmerenog grafa.
Graf $G_2=(V_2, E_2)$, gde je $V_2=\{a, b, c, d\}, E_2=\{ (a, b), (c, b), (a, d), (c, d)\}$, primer je neusmerenog grafa.

In [5]:

%matplotlib inline

import matplotlib.pyplot as plt
import matplotlib.image as mpimg
from matplotlib import rcParams

rcParams["figure.figsize"] = 15, 10

img_A = mpimg.imread("pictures/da.png")
img_B = mpimg.imread("pictures/ne.png")

fig, ax = plt.subplots(1,2)
ax[0].imshow(img_A)
ax[1].imshow(img_B);

Grafovi su apstraktni pojmovi koji se mogu susresti u svakodnevnom životu i značajni su jer se veliki broj koncepata može modelovati njima. Ako posmatramo neku geografsku mapu sa mnoštvom gradova koji su povezani nekim putevima-dobijamo jedan graf. Strukturna formula nekog molekula ili jedinjenja predstavlja takođe jedan graf . Društvene mreže se prirodno mogu opisati grafom u kojem se svakom korisniku društvene mreže dodeljuje čvor, a grana između dva čvora postoji ukoliko su korisnici 'prijatelji' (facebook, neusmeren graf), ili ako jedan korisnik 'prati' drugog korisnika (Twitter, usmeren graf).

Računarska reprezentacija grafova¶

S obzirom da postoji veliki broj podataka u problemima koji se modeluju grafovima, postavlja se pitanje izbora njihove reprezentacije u računarima. Najčešće se za predstavljanje grafova koristi matrična reprezentacija.

Definicija 2: Matrica susedstva $A$ grafa $G=(V,E)$, dimenzija $\vert V \vert \times \vert V \vert$, definiše se na sledeći način:

$$A_{ij}= \begin{cases} 1 & (i, j) \in E \\ 0 & (i, j) \notin E \\ \end{cases} $$

Ako je graf neusmeren, onda je matrica A simetrična, pa nije potrebno čuvati sve elemente matrice, već samo njenu gornje-trougaonu reprezentaciju. Čak i ako grafovi nisu neusmereni, oni su često retki, odnosno, nemaju veliki broj grana, pa se matrice susedstava čuvaju u specifičnim strukturama podataka koje se nazivaju retke matrice. One imaju dve značajne pogodnosti za korišćenje u odnosu na ne-retke matrice.

Ne-retke matrice zahtevaju memorijski prostor asimptotske složenosti $O(\vert V \vert^2)$, dok retke matrice zahtevaju memorijski prostor asimptotske složenosti $O(\vert E \vert)$.
Operacije koje se izvršavaju nad retkim matricama su efikasnije u odnosu na operacije nad uobičajenim reprezentacijama matricama. U algoritmima mašinskog učenja, značajna operacija je množenje matrica i vektora. Složenost je ista kao i u prethodnom primeru, i to značajno ubrzava proces.

Grafovske konvolutivne neuronske mreže¶

Konvolutivne neuronske mreže (CNNs) su uspešno rešavale probleme klasifikacije slika ili semantičke segmentacije, gde podaci imaju strukturu nalik mreži. Međutim mnogi zanimljivi problemi uključuju podatke koji se ne mogu predstaviti u mrežnoj strukturi i koji se zasnivaju na neregularnom domenu. Ovo je slučaj sa društvenim mrežama, telekomunikacionim mrežama, moždanim konektorima itd. Takvi podaci se obično mogu predstaviti u obliku grafa (kao što je opisano u prethodnim primerima).

Pravilo propagacije kod grafovskih neuronskih mreža je definisano na sledeći način:

$$ H^{(k+1)} = \sigma \bigl(\hat{A}H^{(k)}W^{(k)}\bigr) $$

gde je sa $k$ numerisan sloj mreže, $\sigma$ je aktivaciona funkcija, $H^{(0)}=X$, tj. ulazna matrica prediktora, $\hat{A} = \tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$ simetrična normalizovana matrica susedstva grafa $G$ sa dodatim petljama za svaki čvor, gde je $\tilde{A} = A+I_N$ ($N$ je broj čvorova, $A$ je matrica susedstva) i $\tilde{D}_{ii} = \sum_{j}^{}\tilde{A}_{ij}$, $W^{(k)}$ je matrica parametara modela za sloj $k$. Matrica susedstva se normalizuje da bi proces optimizacije kroz duboku neuronsku mrežu bio stabilniji. Dakle, arhitektura je slična kao kod potpuno povezanih neuronskih mreža, samo što je dodata i matrica susedstva čvorova grafa.
Primer grafovske neuronske mreže sa dva sloja je:

$$ f(X,A) = \text{softmax}\bigl(\hat{A} \hspace{1.2mm} \text{LeakyReLU}(\hat{A}XW^{(0)})W^{(1)}\bigr) $$

Gde je $W^{(0)} \in \mathbb{R}^{d \times h^{(0)}}$ matrica parametara za sloj koji spaja ulazne podatke dimenzije $d$ i podatke prvog skrivenog sloja dimenzije $h^{(0)}$, a $W^{(1)} \in \mathbb{R}^{h^{(0)} \times h^{(1)}}$ je matrica parametara za sloj koji spaja skrivene podatke i izlazne podatke. Na izlazu iz ulaznog sloja primenjuje se aktivaciona funkcija LeakyReLU, a na izlazu iz skrivenog sloja primenjuje se aktivaciona funkcija softmax. Ove dve funkcije su definisane sledećim formulama:

$$ \text{LeakyReLU(x)} = \max(\alpha x, x), \alpha >0 $$$$ \text{softmax}(x_j) = \frac{\exp(x_j)}{\sum_{i}^{}\exp(x_i)} $$

Grafovi¶

Osnovni pojmovi teorije grafova¶

Računarska reprezentacija grafova¶

Grafovske konvolutivne neuronske mreže¶