Research

EDoG: Adversarial Edge Detection For Graph Neural Networks

8 min. czytania

Pobierz PDF

EDoG: Adversarial Edge Detection For Graph Neural Networks

Metadane

Streszczenie

EDoG (Edge Detection of Graph) to ogólny pipeline wykrywania adversarial edges w Graph Neural Networks (GNN) bez wymagania wiedzy o strategii ataku. Praca adresuje problem wykrywania subtilnych ataków polegających na dodaniu/usunięciu niewielkiej liczby krawędzi w grafie w celu wprowadzenia błędów klasyfikacji węzłów. Główne wyzwania to: mała skala perturbacji, dyskretna natura danych grafowych oraz zróżnicowane zachowania wynikające z różnych typów ataków.

EDoG składa się z trzech komponentów wykrywających: Link Prediction (LP), Graph Generation Detection (GGD) opartej na generatywnym modelu grafów trenowanym na podpróbkowanych podgrafach oraz Outlier Detection (OD) wykorzystującej cechy strukturalne do identyfikacji outlierów. Kluczowa intuicja polega na wykorzystaniu trade-off między stealthiness (trudność wykrycia jako outlier) a sparsity (trudność próbkowania w podgrafach) - adversarial edges są albo wystarczająco rzadkie aby nie pojawić się w większości podgrafów treningowych, albo wystarczająco liczne aby być wykrytymi jako outliery.

Eksperymenty na trzech rzeczywistych grafach (Cora, Citeseer, prywatny graf transakcyjny) oraz grafach syntetycznych (Erdos-Renyi, scale-free) pokazują, że EDoG osiąga >0.8 AUC przeciwko czterem state-of-the-art niewidzianym wcześniej atakom bez wiedzy o ich typie, oraz ~0.85 AUC z wiedzą o typie ataku, znacząco przewyższając baseline’y.

Kluczowe Wnioski

  • EDoG osiąga detection AUC >0.8 bez wiedzy o typie ataku i >0.85 z wiedzą o jego typie, znacząco przewyższając tradycyjne metody (ALD, Katz index)
  • GraphGenDetect skutecznie wykrywa single-edge i multi-edge indirect attacks dzięki trenowaniu na czystych podgrafach (>99% podgrafów bez adversarial edges dla single-edge attack)
  • OutlierDetect osiąga AUC >0.9 dla węzłów wysokiego stopnia (degree >10), wykorzystując “collective power” principle - wiele malicious edges wzajemnie potwierdza swoją legitymność
  • Adaptive attack z pełną wiedzą o pipeline’ie jest trudny do przeprowadzenia - attack success rate spada o >50% w większości przypadków
  • EDoG jest odporny na random edges (nie mylą go z adversarial), w przeciwieństwie do baseline’ów które traktują randomness jako anomalie
  • Link prediction filtering przed GraphGenDetect znacząco poprawia stabilność (~50% top malicious edges jest odfiltrowywanych)
  • Performance na scale-free graphs (>92% avg AUC) jest lepszy niż na Erdos-Renyi (~80%), co pokazuje wykorzystanie strukturalnych właściwości grafów

Metodologia

Typy rozważanych ataków:

  1. Single-edge attack - dodanie tylko jednej adversarial edge
  2. Multi-edge direct attack - liczba dodanych krawędzi ≤ degree(target), wszystkie bezpośrednio połączone z targetem
  3. Multi-edge indirect attack - liczba dodanych krawędzi ≤ degree(target), ale NIE bezpośrednio z targetem
  4. Meta attack - do 5% liczby krawędzi, bez konkretnego target node

Komponenty EDoG:

  1. LinkPred (LP) - 2-layer GCN do obliczenia embeddings θu, następnie bilinear layer f^GNN_{u,v} = σ(θ^T_u W_edge θ_v) połączony z 5 tradycyjnymi features (common neighbors, distance, preferential attachment, feature similarity). Trenowany end-to-end z logistic regression.

  2. GraphGenDetect (GGD) - generatywny model grafów inspirowany sequence generation:

    • Sampelowanie podgrafów (2-hop neighborhoods) z G’
    • Model f_gen generuje graf edge-by-edge: e^(t) ~ P[(u,v) | (u,v) ∉ E]
    • GCN + bilinear output: s^(t-1)_{uv} = (θ^(t-1)_u)^T W θ^(t-1)_v
    • Softmax dla prawdopodobieństwa następnej krawędzi
    • Training loss: binary cross-entropy na E’ ∪ E_nonexist
    • Union bound zapewnia że >90% podgrafów jest czystych dla multi-edge attacks

  3. Filtering (LinkPred + GraphGenDetect) - LP usuwa top 50% suspicious edges przed trenowaniem GGD, co stabilizuje model i redukuje poisoning

  4. OutlierDetect (OD) - one-class SVM z RBF kernel na 10-wymiarowym feature vector:

    • Dla każdego węzła: liczba różnych klas sąsiadów, średnia częstość pojawienia się klasy, max częstość, 2nd max, std dev, log betweenness centrality
    • Dla każdej krawędzi: konkatenacja features obu węzłów
    • GNN prediction jako proxy dla ground truth labels

Pipeline EDoG:

  • Dla edges między high-degree nodes (sum of degrees > 6): średnia z LP+GGD, OD, GGD
  • Dla low-degree: średnia z LP+GGD i GGD
  • Agregacja scores dla finalnej predykcji

Implementacja:

  • PyTorch dla detection models, scikit-learn dla OD i baselines
  • GraphGenDetect: Adam optimizer, 15 epochs, lr=0.001, averaging epochs 6-15 dla stability
  • LinkPred: SGD, 500 epochs, lr=0.01, balanced sampling
  • 2-hop neighborhood subgraph sampling

Główne Koncepcje

  • Adversarial Edge Detection - wykrywanie subtilnie dodanych/usuniętych krawędzi w grafie które mają na celu wprowadzenie modelu GNN w błąd, poprzez przypisanie score’u prawdopodobieństwa bycia malicious każdej krawędzi

  • Collective Power of Malicious Edges - zjawisko gdzie wiele adversarial edges podłączonych do jednego węzła wzajemnie potwierdza swoją legitymność, czyniąc je trudniejszymi do wykrycia przez metody link prediction/generative, ale łatwiejszymi do wykrycia jako outliery

  • Union Bound for Clean Subgraph Sampling - matematyczna gwarancja że przy małej liczbie adversarial edges w dużym grafie, większość losowo sampelowanych podgrafów będzie wolna od malicious edges (>99% dla single-edge, >90% dla multi-edge)

  • Stealthiness vs Sparsity Trade-off - fundamentalny trade-off w atakach: niskie sparsity (mało krawędzi) zwiększa stealthiness ale edges mogą być wykryte przez generative models, wysokie sparsity zmniejsza stealthiness i prowadzi do outlier detection

  • Graph Generation for Detection - użycie autoregresywnego modelu generatywnego (f_gen) który generuje graf krawędź-po-krawędzi aby nauczyć się rozkładu benign graph structures i identyfikować edges o niskim prawdopodobieństwie generacji

  • Kerckhoffs’s Principle for GNN Security - założenie najsilniejszego ataczkera z whitebox access do trained GNN (architektura, parametry) w celu best-case evaluation zdolności detekcyjnych

  • Feature Attack vs Structure Attack - dwie główne kategorie: feature attack modyfikuje wektory cech węzłów (continuous optimization), structure attack dodaje/usuwa krawędzie (discrete optimization, główny focus pracy)

  • Link Prediction as Filtering - wykorzystanie tradycyjnego link prediction (GCN structural features + 5 heuristics) jako preprocessing do odfiltrowywania suspicious edges przed trenowaniem graph generative model, co poprawia robustness

Wyniki

Performance bez wiedzy o attack type (Table II):

  • EDoG: 0.861 (single-edge), 0.755 (multi-direct), 0.829 (multi-indirect), 0.728 (meta)
  • Katz baseline: 0.850, 0.621, 0.799, 0.696
  • ALD baseline: 0.599, 0.429, 0.350, 0.476

Performance z wiedzą o attack type (Table III - selected):

  • Cora single-edge: LP+GGD = 0.909, EDoG = 0.911
  • Citeseer multi-direct high-degree (15+): OD = 0.922, EDoG = 0.922
  • Rule meta attack: EDoG = 0.972

Adaptive attack resistance (Table V):

  • Standard attack success: Cora single-edge 47.5%, multi-direct 72.9%
  • Adaptive attack success: Cora single-edge 7.0%, multi-direct 48.6%
  • Rule meta: 0.0% adaptive success (24.0% standard)

Synthetic graphs (Table IV):

  • Scale-free (BA): avg >92% AUC na wszystkich tasks
  • Erdos-Renyi: avg ~80% AUC
  • Pokazuje że EDoG wykorzystuje structural properties

Component analysis (Table VIII):

  • LP+GGD best dla single-edge (avg 0.9+)
  • OD best dla high-degree direct attacks (>0.9 dla degree >10)
  • GGD best dla multi-indirect (ResearcherTrustworthy dla sparse graphs)

Benign accuracy (Table VI):

  • Cora: 81.9%, Citeseer: 69.7%, Rule: 85.9%

Random edge resilience (Table IX):

  • EDoG: 9.64-52.35% (Cora), 22.21-45.19% (Citeseer) - bliżej 50% = lepiej
  • Baselines: często <20%, mylą random za malicious

Przydatne Cytaty

“Detecting such adversarial attacks on GNNs involves several challenges. First, such adversarial attacks focus on local graph properties and aim to create ‘unnoticeable’ perturbations. Therefore, the manipulation of a small number of local edges is not obvious enough to be detected by traditional Sybil detection methods.” (str. 1)

“We found that adversarial edges in the first type of attacks can be characterized by graph generative models which are trained with a large number of subsampled graphs… since the original graph contains a small number of adversarial edges, based on the union bound these sub-graphs will not contain malicious edges with high probability.” (str. 2)

“We attribute this to a principle of the collective power of malicious edges which can be understood as: when there are many malicious edges connecting to one node, they confirm the legitimacy of each other mutually.” (str. 5)

“By leveraging the intrinsic tradeoff between the stealthiness (hard to appear as ‘outliers’) and sparsity (hard to be sampled in subgraphs) of attacks, the proposed EDoG is able to effectively identify adversarial edges effectively based on at least one of these properties.” (str. 2)

“We show that the adaptive attack success rate remains very low given our detection pipeline… the attack success rate is greatly reduced. In most cases the success rate is reduced by over 50%.” (str. 11)

“We can observe that baseline approaches will consider random edges as some malicious behaviour, while ours will ignore those randomness and focus only on those malicious edges.” (str. 12, Appendix D)

“The detection AUC of EDoG can reach 0.8 without any knowledge of attack types and over 0.85 when we know the attack type. In both scenarios, the proposed EDoG approach outperforms other baseline methods.” (str. 2)

Datasety

  • Cora - Citation network benchmark, 2,708 nodes, 5,429 edges, 7-way node classification, evaluation dla wszystkich typów ataków
  • Citeseer - Sparse citation network, 3,327 nodes, 4,732 edges, 6-way classification, testowanie wpływu sparsity na detection
  • Transaction Rule Graph (prywatny, eBay) - 719 nodes, 3,375 edges, binary classification (test rule detection), najlepsze wyniki detection (EDoG meta: 97.2%)
  • Erdos-Renyi Synthetic - Random graphs G_{n,p} z n=1000 (p=ln(n)/n i 2ln(n)/n), controlled environment, ~80% avg detection AUC
  • Barabasi-Albert Scale-Free - Scale-free graph z 1,000 nodes (m=1), power-law distribution, >92% avg detection AUC - najlepsza performance ze względu na strukturę podobną do real-world networks

Powiązane Tematy

  • Robust Graph Neural Networks - adversarial training, certified robustness
  • Adversarial attacks on GNNs - Nettack, Metattack, RL-S2V
  • Graph anomaly detection - Sybil detection, fraud detection w sieciach społecznościowych
  • Link prediction methods - common neighbors, Katz index, Adamic-Adar
  • Graph generative models - GraphRNN, NetGAN, GraphVAE
  • Defense mechanisms dla continuous data - adversarial training, feature squeezing, defensive distillation
  • Node embedding security - attacks na DeepWalk, Node2Vec
  • Graph attention networks dla robustness - PeerNets
  • One-class classification - SVM dla outlier detection
  • Subgraph sampling strategies - k-hop neighborhoods, random walks

Notatki

Elementów w folderze: 0.