Детальный ВНН

алгоритм

Это 8-й день моего участия в ноябрьском испытании обновлений.Подробности о событии:Вызов последнего обновления 2021 г.

Introduction

Поскольку вы зашли в этот блог, я предполагаю, что вы понимаете самые основные концепции графов, включая, помимо прочего, определения ориентированных графов и неориентированных графов.

Нейронная сеть графа — это нейронная сеть, которая работает непосредственно со структурами графа. Типичным применением GNN являетсяКлассификация узлов. По сути, каждый узел в графе связан с меткой. Как показано на рисунке ниже, вектор узла представлен как[0.3, 0.02, 7, 4, ...], и отправить вектор в нисходящий поток для продолжения классификации, чтобы получить категорию узла a

Как именно получается векторное представление узла а, я подробно объясню позже, а здесь можно просто подумать, векторное представление узла а должно отличаться от исходного.соседний узелисоседний крайСуществует связь, предполагающая, что каждый узелvvГорячий вектор представлен какXvX_v,но

hv=f(Xv,Xco[v],hne[v],Xne[v])h_v=f(X_v, X_{co[v]}, h_{ne[v]},X_{ne[v]})

вXco[v]X_{co[v]}значит сvvГорячее представление связанных ребер,hne[v]h_{ne[v]}значит сvvВложение соседних узлов,Xne[v]X_{ne[v]}значит сvvГорячее представление соседних узлов. наконец-тоhvh_vВекторы и реальные метки рассчитывают потери, но есть и места, гдеhvh_vвекторная суммаXvX_vПосле раунда слияния подсчитываются потери, например

Ov=g(hv,Xv)loss=∑i=1p(ti−oi)\begin{aligned} O_v&=g(h_v,X_v)\\ loss &= \sum_{i=1}^p (t_i-o_i) \end{aligned}

Приведенные выше формулы и символы могут быть трудны для понимания, но здесь можно сравнить Word2Vec. В Word2Vec вводом является однократное, соответствующее каждому слову, то естьXvX_v. Выход представляет собой вложение, соответствующее слову, то естьhvh_v

DeepWalk: первый алгоритм неконтролируемого обучения внедрению узлов

DeepWalk можно описать одним предложением: случайным образом сгенерировать последовательность узлов графа, а затем выполнить Word2Vec для этой последовательности.

В частности, для данного графа мы случайным образом выбираем узел для начала, а затем случайным образом «ходим» к соседним узлам, пока длина последовательности узлов не достигнет заданного максимального значения. Например, на рисунке ниже выберите d, e и f в качестве начальной точки для обхода и получите три последовательности узлов.

В этом случае мы можем рассматривать узлы и последовательности узлов как «слова» и «предложения» соответственно, а затем использовать алгоритм skip-gram или cbow для обучения получению встраивания каждого узла.

node2vec: смещение случайного блуждания

Общая формула случайного блуждания

P(ci=x∣ci−1=v)={1∣N(v)∣, if (v,x)еE0, otherwise {P}\left(c_{i}=x \mid c_{i-1}=v\right)=\left\{\begin{array}{cc} \frac{1}{|N(v)|}, & \text { if }(v, x) \in E \\ 0, & \text { otherwise } \end{array}\right.

в,∣N(v)∣|N(v)|выражатьvvколичество узлов-соседей узла,ci−1c_{i-1}представляет текущий узел,cic_iузел, представляющий следующий выбор

Общее случайное блуждание имеет следующие проблемы:

  1. Если это взвешенный граф, то влияние весов ребер не учитывается.
  2. Слишком случайно для того, чтобы модель узнала, в какую сторону идти лучше

На самом деле обход графа делится на две категории, а именно DFS и BFS.

Чтобы ввести веса ребер и выбрать DFS или BFS в соответствии с вероятностью, нам сначала нужно изменить общую формулу случайного блуждания

P(ci=x∣ci−1=v)={число ПиvxZ, if (v,x)еE0, otherwise {P}\left(c_{i}=x \mid c_{i-1}=v\right)=\left\{\begin{array}{cc} \frac{\pi_{vx}}{Z}, & \text { if }(v, x) \in E \\ 0, & \text { otherwise } \end{array}\right.

в,число ПиvxZ\frac{\pi_{vx}}{Z}по стоимости с1∣N(v)∣\frac{1}{|N(v)|}равны,ZZМожет пониматься как нормализованный коэффициент масштабирования

установить узелvvиxxГраничный вес междуwvxw_{vx}, тогда ты можешьчисло Пиvx\pi_{vx}переписать какαpq(t,x)⋅wvx\alpha_{pq}(t,x)\cdot w_{vx}

αpq(t,x)={1p, if dtx=01, if dtx=11q, if dtx=2\alpha_{{pq}}(t, x)=\left\{\begin{array}{l} \frac{1}{p}, &\quad{ \text { if } d_{t x}=0} \\ 1, &\quad{\text { if } d_{t x}=1} \\ \frac{1}{q}, &\quad{ \text { if } d_{t x}=2} \end{array}\right.

в,dtxd_{tx}Указывает текущий узелvvСоседи первого порядка узла к узлуttрасстояние

  • pp: Контролирует, как часто случайное блуждание «возвращается»
  • qq: контролирует, будет ли случайное блуждание смещено в сторону DFS или BFS.
    • qqбольше(q>1)(q>1), стремящийся к БФС
    • qqменьше(q<1)(q<1), стремящийся к DFS
  • p=q=1p=q=1час,число Пиvx=wvx\pi_{vx}=w_{vx}

Пока я не буду описывать алгоритм встраивания узла в GNN, на самом деле есть много лучших алгоритмов, таких как LINE, Struct2vec и т. д., но лично мне кажется, что эти алгоритмы встраивания не важны, или они не являются ядром части GNN., просто используйте его как инструмент, аналогичный статусу Word Embedding в Transformer

References

Категории