O que são incorporação de gráficos?

12

Recentemente me deparei com a incorporação de gráficos, como o DeepWalk e o LINE. No entanto, ainda não tenho uma ideia clara do significado de incorporação de gráficos e quando usá-lo (aplicativos)? Todas as sugestões são bem-vindas!

Volka
fonte
1
Uma incorporação de gráfico é uma incorporação de gráficos! Portanto, é necessário um gráfico e retorna as inserções para o gráfico, arestas ou vértices. Os casamentos permitem busca por similaridade e geralmente facilitam o aprendizado de máquina, fornecendo representações .
Emre
@Emre, o que significa incorporação? :)
Volka
1
Como o significado da incorporação vai, consertando as coisas em alguma coisa. A incorporação de gráficos é como fixar vértices em uma superfície e desenhar arestas para representar, digamos, uma rede. Assim, o exemplo como ser gráfico planar pode ser incorporado em um superfície sem cruzamento borda. Os pesos podem ser atribuídos às arestas e os comprimentos das arestas apropriados, viz. nos ajuda a entender / estimativa a @Emre mencionado semelhança procurar etc.2D
Kiritee Gak
@KiriteeGak Obrigado :) Quais são as aplicações do mundo real? Eles dizem que podem ser usados ​​para recomendação e tudo mais? mas como?
Volka
1
A recomendação de vídeo do YouTube pode ser visualizada como um modelo em que o vídeo que você está assistindo atualmente é o nó em que você está e os próximos vídeos que estão em sua recomendação são os mais parecidos com você, com base no que usuários similares assistiram a seguir e muitos mais fatores, é claro, que é uma enorme rede para atravessar. Este artigo é uma boa leitura simples sobre como entender a aplicação.
Kiritee Gak

Respostas:

18

A incorporação de gráfico aprende um mapeamento de uma rede para um espaço vetorial, preservando as propriedades relevantes da rede.

Os espaços vetoriais são mais acessíveis à ciência de dados do que aos gráficos. Os gráficos contêm arestas e nós; esses relacionamentos de rede podem usar apenas um subconjunto específico de matemática, estatística e aprendizado de máquina. Os espaços vetoriais têm um conjunto de ferramentas mais rico desses domínios. Além disso, as operações vetoriais são geralmente mais simples e rápidas que as operações gráficas equivalentes.

Um exemplo é encontrar vizinhos mais próximos. Você pode executar "saltos" de nó para outro nó em um gráfico. Em muitos gráficos do mundo real após alguns saltos, há pouca informação significativa (por exemplo, recomendações de amigos de amigos de amigos). No entanto, em espaços vetoriais, você pode usar métricas de distância para obter resultados quantitativos (por exemplo, distância euclidiana ou semelhança cosseno). Se você possui métricas quantitativas de distância em um espaço vetorial significativo, é fácil encontrar vizinhos mais próximos.

" Técnicas de incorporação de gráficos, aplicativos e desempenho: uma pesquisa " é um artigo de visão geral que entra em mais detalhes.

Brian Spiering
fonte
24

O que são Embeddings gráficos? "Graph Embeddings" é uma área quente hoje em aprendizado de máquina. Basicamente, significa encontrar "representação vetorial latente" de gráficos que captura a topologia (no sentido muito básico) do gráfico. Podemos enriquecer essa "representação vetorial", considerando também as relações vértice-vértice, informações de arestas, etc. subgráficos de vários tamanhos):

  • Incorporação de vértices - Aqui você encontra a representação vetorial latente de cada vértice no gráfico fornecido. Você pode então comparar os diferentes vértices, plotando esses vetores no espaço e, curiosamente, vértices "semelhantes" são plotados mais próximos um do outro do que os que são diferentes ou menos relacionados. Este é o mesmo trabalho feito no "DeepWalk" por Perozzi.
  • Incorporação de gráficos - Aqui você encontra a representação vetorial latente de todo o gráfico. Por exemplo, você tem um grupo de compostos químicos para os quais deseja verificar quais compostos são semelhantes entre si, quantos tipos de compostos existem no grupo (agrupamentos) etc. Você pode usar esses vetores e plotá-los no espaço e encontre todas as informações acima. Este é o trabalho que é feito em "Deep Graph Kernels", de Yanardag.

Aplicativos - Observando atentamente, os incorporamentos são representações "latentes", o que significa que se um gráfico tiver | V | * | V | matriz de adjacência onde | V | = 1M, é difícil usar ou processar números de 1M * 1M em um algoritmo. Portanto, a incorporação latente da dimensão 'd', em que d << | V |, tornaria a matriz de adjacência | V | * de relativamente fácil de usar. Outra aplicação pode ser: considere um cenário simples em que queremos recomendar produtos para pessoas que têm interesses semelhantes em uma rede social. Com a incorporação de vértices (aqui significa representação vetorial de cada pessoa), podemos encontrar os semelhantes plotando esses vetores e isso facilita as recomendações. Estas são algumas aplicações e outras. Você pode consultar um bom documento de pesquisa - Graph Embedding Techniques, uma Pesquisa .

De onde veio tudo isso? Existem muitos trabalhos nessa área e quase todos vêm da pesquisa inovadora no campo do processamento de linguagem natural - "Word2Vec", de Mikolov. Se você deseja iniciar a pesquisa sobre incorporação de gráficos, eu recomendo que primeiro entenda como o Word2Vec funciona. Você pode encontrar explicações interessantes - o aprendizado de parâmetros do Word2Vec é explicado e a Stanford Lecture . Depois, você pode pular para os papéis que listou. Esses trabalhos podem ser classificados como:

flyingDope
fonte
2
Wowww !! Esta é absolutamente uma resposta perfeita. Muito obrigado :) Muito bem feito :)
Volka
Oi Mausam Jain. Você pode me informar se eu posso usar combinações de gráficos para identificar nós importantes na rede?
Volka
Olá Volka. Para responder a essa pergunta, preciso saber em que tipo de gráfico você está trabalhando; é twitter, facebook, reddit ou algo mais?
flyingDope
Obrigado por sua resposta. Na verdade, estou trabalhando em uma rede social onde eu quero identificar mais pessoas sociais :)
Volka
0

No artigo Um teorema do limite central para uma incorporação omnibus de gráficos de produtos de pontos aleatórios por Levin et.al. papel, um tipo específico de incorporação de gráfico (a incorporação Omnibus) define a incorporação de gráfico como uma metodologia "na qual os vértices de um gráfico são mapeados para vetores em um espaço euclidiano de baixa dimensão". Verifique o link para mais informações.

goatboy3million
fonte
Bem-vindo ao fórum. Se você quiser mencionar um artigo, anote seu nome como parte do texto também (porque os links podem ser quebrados).
Mark.F