Что такое expressiveness GNN и связь с тестом Weisfeiler-Lehman?

Expressiveness (выразительность) GNN (Graph Neural Networks) — это способность модели различать различные структуры графов и эффективно кодировать их свойства.

Тест Weisfeiler-Lehman (WL-тест) — классический алгоритм для проверки изоморфизма графов, который итеративно обновляет метки вершин на основе меток соседей. Если после нескольких итераций метки двух графов совпадают, они считаются изоморфными с точки зрения WL-теста.

Связь с GNN:

• Многие GNN архитектуры эквивалентны по выразительности WL-тесту 1-го порядка, то есть они могут различать графы не хуже, чем этот тест.
• Это означает, что если WL-тест не может отличить два графа, стандартный GNN тоже не сможет.
• Для повышения выразительности разрабатывают более сложные GNN, которые превосходят WL-тест или используют дополнительные механизмы.

Таким образом, WL-тест служит теоретическим ориентиром для оценки возможностей GNN в различении графовых структур.