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

A incorporação de gráficos aprende um mapeamento de uma rede para um espaço vetorial, enquanto preserva as propriedades de rede relevantes.

Os espaços vetoriais são mais adequados à ciência de dados do que os gráficos. Os gráficos contêm arestas e nós, essas relações de rede só podem usar 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 costumam ser mais simples e rápidas do que as operações gráficas equivalentes.

Um exemplo é localizar os vizinhos mais próximos. Você pode realizar “saltos” de um nó para outro em um gráfico. Em muitos gráficos do mundo real, após alguns saltos, há poucas informações significativas (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 de cosseno). Se você tiver métricas de distância quantitativas em um espaço vetorial significativo, encontrar os vizinhos mais próximos é simples.

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

O que são embeddings de gráfico? “Embeddings de gráfico” é uma área importante atualmente no aprendizado de máquina. Basicamente, significa encontrar uma “representação vetorial latente” de gráficos que captura a topologia (no sentido mais básico) do gráfico. Podemos tornar essa “representação vetorial” rica considerando também as relações vértice-vértice, informações de borda etc. Existem aproximadamente dois níveis de embeddings no gráfico (é claro que podemos definir mais níveis a qualquer momento, dividindo logicamente todo o gráfico em subgráficos de vários tamanhos):

• Embeddings 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 os vértices “semelhantes” são plotados mais próximos uns dos outros do que aqueles que são diferentes ou menos relacionados. Este é o mesmo trabalho que é feito em “DeepWalk” por Perozzi.
• Embeddings de gráfico – 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 (clusters) etc. Você pode usar esses vetores e representá-los no espaço e encontre todas as informações acima. Este é o trabalho que é feito em “Deep Graph Kernels” por Yanardag.

Aplicativos – Olhando com atenção, os embeddings são representações “latentes”, o que significa que se um gráfico tem um | V | * | V | matriz de adjacência onde | V | = 1M, é difícil de usar ou processar números de 1M * 1M em um algoritmo. Portanto, a incorporação latente da dimensão “d”, onde d < < | V |, faria a matriz de adjacência | V | * d e relativamente mais fácil de usar. Outra aplicação poderia ser – Considere um cenário simples em que queremos recomendar produtos para pessoas que têm interesses semelhantes em uma rede social.Ao obter embeddings de vértices (aqui significa representação vetorial de cada pessoa), podemos encontrar os semelhantes traçando esses vetores e isso torna a recomendação fácil. Estes são alguns aplicativos e existem outros. Você pode consultar um bom artigo de pesquisa – Técnicas de incorporação de gráficos, uma pesquisa .

De onde veio tudo isso? Muitos trabalhos foram feitos nessa área e quase todos vêm da pesquisa inovadora no campo do processamento de linguagem natural – “Word2Vec” de Mikolov. Se você quiser começar com a pesquisa sobre embeddings de gráficos, recomendo primeiro entender como funciona o Word2Vec. Você pode encontrar boas explicações – Aprendizado de parâmetros do Word2Vec explicado e Palestra de Stanford . Então você pode pular para os papéis que listou. Esses trabalhos podem ser categorizados como:

• Trabalhos baseados em “Embeddings de vértices”: – DeepWalk , Node2Vec , LINE .

• Funciona com base em “Graph Embeddings”: – Deep Graph Kernels , Subgraph2Vec .

Comentários

• Uau !! Esta é uma resposta absolutamente perfeita. Muito obrigado 🙂 Muito bem feito 🙂
• Olá Mausam Jain. Você pode me dizer se posso usar embeddings de gráfico para identificar nós importantes na rede?
• Olá, Volka. Para responder a essa pergunta, preciso saber em que tipo de gráfico você está trabalhando; é twitter, facebook, reddit ou outra coisa?
• Obrigado por sua resposta. Na verdade, estou trabalhando em uma rede social em que desejo identificar as pessoas mais sociais 🙂
• Aqui ‘ está uma versão mais elaborada desta resposta. paradatascience.com/…

No artigo Um teorema de limite central para uma incorporação abrangente de gráficos de produto escalar aleatório por Levin et.al. papel, um tipo específico de incorporação de gráfico (a incorporação de 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 obter mais informações.

Comentários

• bem-vindo ao fórum. Se você quiser mencionar um artigo, por favor, escreva seu nome como parte do texto também (porque os links podem ser quebrados).