Przejdź do treści
Wróć do wyników wyszukiwania

Predykcja powiązań — wnioskowanie o brakujących i przyszłych krawędziach w sieciach

Rok
2003
Typ
Network inference task

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Predykcja powiązań to zadanie analizy sieci, które szacuje, które krawędzie brakuje w obserwowanym grafie lub które krawędzie prawdopodobnie powstaną w przyszłości.

Sformalizowana przez Liben-Nowell i Kleinberg (2003, 2007), obejmuje ona spektrum podejść — od prostych wskaźników podobieństwa strukturalnego, takich jak Wspólni Sąsiedzi, współczynnik Jaccarda i Adamic-Adar, po faktoryzację macierzy i metody grafowych sieci neuronowych (GNN) — i jest oceniana za pomocą AUC i Średniej Precyzji, aby uwzględnić silnie niezbalansowany stosunek rzeczywistych do nieistniejących krawędzi.

Intuicja stojąca za metodą

W każdej sieci świata rzeczywistego zarejestrowane krawędzie stanowią tylko ułamek rzeczywistych połączeń: platformy społecznościowe pomijają nieujawnione więzi, bazy danych cytowań pomijają niezindeksowane artykuły, a testy interakcji białek pozostawiają wiele par nieprzetestowanych. Predykcja powiązań pyta: na podstawie połączeń, które możemy zobaczyć, które nieobserwowane pary najprawdopodobniej będą połączone? Podstawowa intuicja polega na tym, że dwa węzły dzielące wielu wspólnych sąsiadów lub znajdujące się blisko siebie w nauczonej przestrzeni osadzeń, są bardziej prawdopodobnie połączone niż dwa węzły odległe strukturalnie. Wskaźniki oparte na podobieństwie ujmują to w jednym wzorze; podejścia oparte na GNN uczą się, które wzorce strukturalne najlepiej przewidują łączność na podstawie oznakowanych przykładów.

Historia

Zadanie zostało formalnie zdefiniowane przez Liben-Nowell i Kleinberg w artykule SODA z 2003 r. i jego rozszerzonej wersji JASIST z 2007 r., gdzie porównali proste wskaźniki podobieństwa strukturalnego na sieciach współautorstwa i pokazali, że sama topologia niesie silny sygnał predykcyjny. Kolejne prace rozszerzyły zadanie na faktoryzację macierzy i probabilistyczne modele generatywne. Dziedzina została znacząco rozwinięta przez Zhanga i Chena (2018), którzy zaproponowali framework Seal — wyodrębniający lokalne otaczające podgrafy i klasyfikujący je za pomocą GNN — demonstrując, że nauczone cechy strukturalne konsekwentnie przewyższają ręcznie tworzone wskaźniki podobieństwa w różnych sieciach benchmarkowych.

Kiedy stosować

Predykcja powiązań pasuje do każdego problemu, w którym sieć jest niekompletna lub ewoluuje, a celem jest odzyskanie lub przewidzenie krawędzi. Odpowiednie scenariusze obejmują rekomendowanie nowych połączeń w sieciach społecznościowych, przewidywanie przyszłych cytowań lub współpracy, wnioskowanie o interakcjach białko-białko i uzupełnianie grafów wiedzy. Metoda wymaga co najmniej 50 węzłów i wystarczającej gęstości obserwowanych krawędzi, aby można było nauczyć się wzorców strukturalnych. Gdy dostępnych jest mniej niż 20 węzłów, bezpieczniejszym wyborem jest analiza centralności. Obserwowana część grafu musi być reprezentatywna; jeśli mechanizm próbkowania jest silnie obciążony, wnioskowane krawędzie mogą odzwierciedlać artefakty próbkowania, a nie prawdziwą strukturę.

Ograniczenia i uwagi

  • Wydajność krytycznie zależy od strategii próbkowania negatywnego; różne strategie mogą prowadzić do różnych wniosków z tego samego modelu.
  • Metody oparte na GNN wymagają wystarczająco dużego zbioru oznakowanych krawędzi i znacznych zasobów obliczeniowych.
  • Wskaźniki strukturalne zakładają, że podobieństwo w obserwowanej topologii implikuje przyszłą łączność, co może nie być prawdą w sieciach o strukturze heterofilnej.
  • Czasowy podział na zbiory treningowe i testowe jest niezbędny, ale wymaga wiarygodnych znaczników czasu; bez nich wyciek informacji zawyża pozorowaną wydajność.

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Obejmuje szeroki zakres złożoności — proste wskaźniki Jaccarda lub Adamic-Adara nie wymagają treningu i działają bezpośrednio na topologii grafu, podczas gdy metody oparte na GNN uczą się złożonych wzorców strukturalnych.
  • Model-free wskaźniki podobieństwa są szybkie, interpretowalne i odporne na rzadkich grafach z ograniczonym sygnałem treningowym.
  • Podejścia GNN dobrze generalizują się w różnych domenach (społecznych, biologicznych, grafów wiedzy) i wychwytują topologię wyższego rzędu.
  • Ramy ewaluacyjne AUC/AP są odporne na silne niezbalansowanie klas między rzeczywistymi a nieistniejącymi krawędziami.

Zastosowania

  • Rekomendacja znajomych lub połączeń w sieciach społecznościowych (Ludzie, których możesz znać na Facebooku, LinkedIn).
  • Przewidywanie przyszłych współpracy badawczej lub relacji cytowań w sieciach akademickich.
  • Wnioskowanie o brakujących interakcjach białko-białko w sieciach biologicznych na podstawie częściowych danych eksperymentalnych.
  • Uzupełnianie grafów wiedzy poprzez przewidywanie relacji między jednostkami.
  • Predykcja interakcji lek-cel w sieciach farmakologicznych.

Jak to działa

Jak to działa

1

Sieć jest tworzona z obserwowanych krawędzi i dzielona na zbiory treningowe i testowe za pomocą podziału czasowego lub losowego. Preferowany jest podział czasowy, gdy dostępne są znaczniki czasu, ponieważ zapobiega on wyciekowi informacji: przyszłe krawędzie nie mogą informować modelu o przeszłych. Graf treningowy jest jedynym grafem, który metoda punktacji może obserwować.

2

Ponieważ ogromna większość par węzłów nie jest połączona, ocena każdej nieobecnej pary jest niepraktyczna. Strategia próbkowania negatywnego wybiera zbiór nieistniejących krawędzi, które służą jako przykłady negatywne. Rozmiar i strategia próbkowania (losowe, trudne negatywne, zrównoważone stopniem) znacząco wpływają na mierzoną wydajność i muszą być zgłaszane wraz z wynikami.

3

Każda para kandydatów otrzymuje ocenę prawdopodobieństwa. Wskaźniki strukturalne obliczają ocenę na podstawie obserwowanej topologii grafu — Wspólni Sąsiedzi zliczają wspólnych sąsiadów, Jaccard normalizuje tę liczbę przez sumę, a Adamic-Adar waży wspólnych sąsiadów odwrotnością logarytmu ich stopnia. Metody faktoryzacji macierzy rozkładają macierz sąsiedztwa na czynniki ukryte, których iloczyn skalarny przybliża prawdopodobieństwo krawędzi. Metody oparte na GNN, w szczególności framework Seal Zhanga i Chena (2018), wyodrębniają lokalne podgrafy wokół każdej pary kandydatów i trenują klasyfikator grafu, aby odróżnić rzeczywiste krawędzie od fałszywych, wychwytując wzorce strukturalne wyższego rzędu, których brakuje w prostych wskaźnikach.

4

Prognozy są rangowane według oceny i porównywane z odłożonymi na bok krawędziami pozytywnymi i negatywnymi. AUC-ROC mierzy prawdopodobieństwo, że losowa para pozytywna zostanie sklasyfikowana wyżej niż losowa para negatywna. Średnia Precyzja (AP) podsumowuje precyzję w całym rankingu i jest bardziej informacyjna, gdy przykłady pozytywne są rzadkie. Obie metryki muszą być zgłaszane; sama dokładność jest myląca przy silnym niezbalansowaniu klas.

Częste pułapki

  • Wprowadzanie przyszłych krawędzi do grafu treningowego — zawsze używaj podziałów czasowych lub ściśle losowych i weryfikuj, czy żadna krawędź testowa nie pojawia się w macierzy sąsiedztwa treningowego.
  • Zgłaszanie tylko dokładności; ponieważ nieistniejące krawędzie znacznie przewyższają liczbę prawdziwych krawędzi, dokładność jest prawie bezużyteczna — zawsze zgłaszaj AUC i AP.
  • Ignorowanie strategii próbkowania negatywnego podczas porównywania metod; zmiana próbkowania może odwrócić rankingi między modelami.
  • Stosowanie predykcji powiązań do grafów z mniej niż 20 węzłami — przy tak małej liczbie węzłów wzorce strukturalne są zbyt rzadkie, aby uzyskać wiarygodne predykcje; preferuj analizę centralności.
  • Traktowanie obciążonego grafu obserwowanego jako reprezentatywnej próbki — jeśli obserwowane krawędzie systematycznie pomijają pewne typy węzłów, predykcje odziedziczą to obciążenie.

Najczęściej zadawane pytania

Które podejście wybrać — wskaźnik podobieństwa czy GNN?

Wskaźniki podobieństwa (Wspólni Sąsiedzi, Jaccard, Adamic-Adar) są dobrym punktem wyjścia: nie wymagają treningu, są interpretowalne i zaskakująco dobrze działają na rzadkich grafach. Metody oparte na GNN, takie jak Seal, przewyższają wskaźniki na sieciach o złożonej strukturze wyższego rzędu, ale wymagają wystarczającej liczby oznakowanych krawędzi i większych zasobów obliczeniowych. Gdy dane są ograniczone lub ważna jest interpretowalność, zacznij od wskaźników.

Jak podzielić graf do oceny bez wycieku informacji?

Jeśli twoje krawędzie mają znaczniki czasu, użyj podziału czasowego: trenuj na krawędziach zaobserwowanych przed pewnym czasem odcięcia i testuj na krawędziach utworzonych po nim. Bez znaczników czasu odłóż losową część krawędzi jako pozytywne i pobierz równą lub ustaloną liczbę nieistniejących krawędzi jako negatywne, upewniając się, że żadna odłożona krawędź nie pojawi się w macierzy sąsiedztwa treningowego.

Dlaczego AUC jest preferowane nad dokładnością?

W każdej rzeczywistej sieci liczba brakujących krawędzi znacznie przewyższa liczbę istniejących — często o kilka rzędów wielkości. Trywialny model, który przewiduje „brak krawędzi” dla każdej pary, osiąga prawie doskonałą dokładność, jednocześnie nie przewidując niczego użytecznego. AUC-ROC i Średnia Precyzja to metryki oparte na rankingu, które są niewrażliwe na to niezbalansowanie i bezpośrednio mierzą jakość rankingu.

Czy predykcję powiązań można zastosować do grafów skierowanych lub ważonych?

Tak. Dla grafów skierowanych, oceny można obliczać oddzielnie w każdym kierunku, a niektóre frameworki GNN natywnie obsługują skierowaną sąsiedztwo. Dla grafów ważonych, wskaźniki podobieństwa mogą uwzględniać wagi krawędzi w obliczeniach sąsiedztwa, a metody GNN mogą używać cech krawędzi. Jednak większość badań porównawczych dotyczy grafów nieważonych i nieskierowanych, więc przy adaptacji metod należy zachować dodatkową ostrożność.

Pokrewne metody

Źródła

  1. Liben-Nowell, D. & Kleinberg, J. (2007). The Link-Prediction Problem for Social Networks. Journal of the American Society for Information Science and Technology, 58(7), 1019-1031.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Zhang, M. & Chen, Y. (2018). Link Prediction Based on Graph Neural Networks. Advances in Neural Information Processing Systems (NeurIPS), 31.

    Otwórz odnośnik do publikacji
    Skopiowano.