Erdos-Renyi Synthetic Graphs
Informacje podstawowe
- Nazwa: Erdos-Renyi Random Graphs (G_{n,p})
- Alias: ER graphs, random graphs
- Dziedzina: Graph Theory, Graph Neural Networks
- Typ: Synthetic graph data
Źródło
- URL: Generated synthetically using standard algorithms
- Paper: “On random graphs” (Erdős & Rényi, 1959)
- Organizacja: Mathematical Institute of the Hungarian Academy of Sciences
- Rok: 1959 (theoretical foundation)
Charakterystyka
- Rozmiar: n = 1,000 nodes
- Parametry:
- G_{n,p1} with p1 = ln(n)/n
- G_{n,p2} with p2 = 2*ln(n)/n
- Klasy/Kategorie: Binary classification (generated based on node features)
- Format: Graph structure with 20-dimensional binary feature vectors
- Licencja: N/A (synthetic, generated on demand)
Opis
Erdos-Renyi graphs to model teoretyczny grafów losowych, gdzie każda możliwa krawędź między n węzłami istnieje z prawdopodobieństwem p, niezależnie od innych krawędzi. W kontekście badań GNN, ER graphs są używane jako controlled environment do testowania algorytmów na grafach o znanej strukturze probabilistycznej.
Generacja dla eksperymentów EDoG:
- Utworzenie ER graph G_{n,p} z n=1000 węzłami
- Przypisanie początkowych 20-wymiarowych random features e_u dla każdego węzła
- Skorelowanie features ze strukturą grafu poprzez iterację:
- e_u = Σ_{v∈N(u)} e_v
- e_u = e_u / ||e_u||_2
- Powtórzenie 3 razy
- Generacja binary feature vector x_u: P[x^(i)_u = 1] = sigmoid(e^(i)_u)
- Generacja labels: y_u = 1 if Σ_i x^(i)_u > 0, else 0
Rezultat: node features są strukturalnie powiązane z topologią grafu, umożliwiając meaningful node classification (~80% accuracy).
Zastosowania
- Controlled experiments dla GNN robustness
- Testowanie adversarial detection methods w środowisku o znanej strukturze
- Porównanie z real-world graphs (citation networks, scale-free)
- Ablation studies - wpływ graph properties na detection performance
Używany w publikacjach
- xu-edog-adversarial-2023 - Synthetic evaluation dataset dla EDoG pipeline, testowanie czy detection methods generalizują na grafy o kontrolowanych właściwościach; dwa warianty z różnymi prawdopodobieństwami p
Benchmarki
| Model | Metric (Detection AUC) | Score | Typ Ataku | Publikacja |
|---|---|---|---|---|
| EDoG | AUC (avg) | ~80% | All attacks | Xu et al. 2023 |
| Katz | AUC (avg) | ~43% | All attacks | Xu et al. 2023 |
| ALD | AUC (avg) | ~61% | All attacks | Xu et al. 2023 |
| Model | Metric (Node Classification) | Score | Publikacja |
|---|---|---|---|
| GCN | Accuracy | ~80% | Xu et al. 2023 |
Uwagi
- Dwa warianty z różnymi p (ln(n)/n vs 2ln(n)/n) pozwalają testować wpływ gęstości grafu
- Performance EDoG na ER graphs (~80% AUC) jest niższy niż na scale-free graphs (~92%), co sugeruje że EDoG lepiej wykorzystuje strukturalne właściwości real-world graphs
- ER graphs nie mają charakterystycznych właściwości real-world networks (brak communities, power-law degree distribution)
- Feature generation process zapewnia że features są meaningfully related do graph structure
- Wybrano 2 target nodes: najniższy i najwyższy degree dla różnych attack types
- Baseline methods czasem radzą sobie lepiej na clean synthetic data niż na noisy real-world graphs
Tagi
dataset synthetic graph-theory random-graphs controlled-experiments gnn-robustness