Uma introdução amigável às redes neurais de grafos

• Redes neurais de grafos (GNNs) são modelos que tratam conjuntamente nós, arestas, contexto global e estrutura de conexões, sendo adequados para dados em que o mesmo grafo deve ser interpretado com o mesmo significado mesmo que a ordem dos nós mude
• Além de moléculas, redes sociais e redes de citações, a grade de pixels de uma imagem e a sequência de tokens de um texto também podem ser vistas como grafos, mas grafos são difíceis de tratar como uma entrada em arranjo comum porque seu tamanho e conectividade variam bastante
• Os problemas de predição com GNN se dividem em nível de grafo inteiro, nó e aresta, e uma mesma família de modelos pode prever rótulos em níveis diferentes preservando a estrutura de entrada
• A operação central é o message passing, que agrega e atualiza informações de nós e arestas vizinhas; ao empilhar várias camadas, a representação passa a incorporar informações de vizinhos k-hops mais distantes
• O desempenho real depende da profundidade das camadas, da dimensão dos embeddings, da função de agregação e do fluxo de mensagens entre representações de nós, arestas e contexto global; aumentar parâmetros ou profundidade nem sempre produz o melhor resultado

---

Conceitos básicos de dados em grafos e GNNs

• Um grafo é composto por nós (nodes), que representam entidades, e arestas (edges), que representam relações entre nós
• Nós, arestas e o grafo como um todo podem armazenar informações adicionais
  • Em nós, podem entrar características como tipo de átomo, valores RGB de pixel ou embeddings de documentos
  • Em arestas, podem entrar informações como tipo de ligação ou tipo de relação
  • No grafo inteiro, pode existir um contexto global
• As arestas podem ser representadas como directed edges, com direção, ou undirected edges, sem direção
• Uma GNN transforma nós, arestas e contexto global de forma aprendível, ao mesmo tempo em que deve tratar a mesma estrutura de grafo com o mesmo significado mesmo se a ordem dos nós mudar

Dados que podem ser representados como grafos

• Imagens geralmente são representadas como arranjos como 244×244×3, mas também podem ser vistas como um grafo regular em que cada pixel é um nó e pixels adjacentes são conectados por arestas
  • Pixels que não estão na borda têm exatamente 8 vizinhos
  • Cada nó armazena um vetor de 3 dimensões que representa os valores RGB
• Texto pode ser visto como um grafo direcionado em que caracteres, palavras ou tokens são nós, com arestas apontando para o próximo token
  • Isso se conecta à representação sequencial de tokens em RNNs
  • Transformers podem ser vistos como grafos totalmente conectados que aprendem relações entre tokens
• Imagens e texto têm estrutura muito regular, então a representação em grafo pode ser redundante
  • A matriz de adjacência de uma imagem tem uma estrutura em faixas por causa das conexões em grade
  • A matriz de adjacência de texto se aproxima de uma estrutura diagonal, já que cada palavra se conecta apenas às palavras anterior e posterior
• Moléculas são convenientemente representadas como grafos em que átomos são nós e ligações covalentes são arestas
  • A distância varia conforme o par de átomos e o tipo de ligação, como ligação simples ou dupla
• Redes sociais modelam pessoas, instituições e organizações como nós, e relações como arestas
• Redes de citações representam artigos como nós, e a relação em que um artigo cita outro como uma aresta direcionada
  • Cada nó de artigo pode incluir informações como embeddings das palavras do resumo
• Objetos de cena em visão computacional, modelos de machine learning, código de programação e equações matemáticas também podem ser representados como grafos em que variáveis ou objetos são nós, e operações ou relações são arestas

Os três níveis dos problemas de predição em grafos

• Graph-level task prevê uma única propriedade do grafo inteiro
  • Exemplos incluem prever qual cheiro um grafo molecular tem ou se ele se ligará a um receptor associado a uma doença
  • É análogo a classificação de imagem ou análise de sentimento de frases, em que um único rótulo é atribuído à entrada inteira
• Node-level task prevê propriedades ou papéis de cada nó dentro do grafo
  • O conjunto de dados Zach's karate club trata de classificar cada pessoa quanto a qual dos dois clubes ela apoiaria após um conflito político
  • É semelhante a rotular o papel de cada pixel em segmentação de imagens ou prever a classe gramatical de cada palavra em uma frase
• Edge-level task prevê propriedades das arestas ou sua existência
  • Um exemplo é, em entendimento de cenas de imagem, usar objetos como nós e prever se existe relação entre pares de objetos
  • Também é possível assumir conectividade total entre todos os pares de nós e então remover arestas com base nas previsões para criar um grafo esparso
• Geração de grafos e explicação de predições em grafos também fazem parte de áreas de pesquisa relacionadas

Dificuldades ao transformar grafos em entrada para redes neurais

• Modelos tradicionais de machine learning normalmente foram feitos para entradas em arranjos retangulares ou em grade, então é difícil inserir diretamente a estrutura de conexões de um grafo
• Um grafo pode conter até quatro tipos de informação
  • nós
  • arestas
  • contexto global
  • conectividade
• Nós, arestas e contexto global podem virar matrizes de características, mas representar a conectividade é mais complicado
• Matrizes de adjacência são fáceis de transformar em tensores, mas têm limitações
  • O número de nós de um grafo pode chegar a milhões
  • O número de arestas por nó pode variar bastante
  • A matriz de adjacência fica muito esparsa, com baixa eficiência de espaço
  • A mesma conectividade de grafo pode ser representada por várias matrizes de adjacência, então não há garantia de que a rede neural sempre produza o mesmo resultado
• Listas de adjacência são mais adequadas para grafos esparsos
  • A informação de que a aresta e_k conecta os nós n_i e n_j é armazenada como uma tupla (i, j)
  • Em vez de O(n_nodes^2) da matriz de adjacência, é possível uma representação O(n_edges), proporcional ao número de arestas
• Em representações tensoriais reais, os valores de nós, arestas e contexto global não são escalares, mas vetores
  • O tensor de nós não tem forma [n_nodes], e sim [n_nodes, node_dim]

Camadas de GNN e pooling

• A GNN mais simples ainda não usa a conectividade do grafo dentro da camada, aplicando um MLP separado a nós, arestas e contexto global para aprender novos embeddings
  • Cada vetor de nó é atualizado da mesma forma
  • Cada vetor de aresta também é atualizado
  • O vetor de contexto global também é atualizado como um embedding
• Uma GNN não altera a conectividade do grafo de entrada
  • O grafo de saída mantém a mesma lista de adjacência e o mesmo número de vetores de características
  • O que muda são os embeddings de nós, arestas e contexto global
• Para predição, usa-se pooling
  • Os embeddings a serem reunidos são coletados com gather e concatenados em uma matriz
  • Os embeddings reunidos geralmente são agregados com uma operação como sum
• Em predição de nós, se a informação do nó já estiver presente, é possível aplicar um classificador linear a cada embedding de nó
• Se a informação necessária para prever nós estiver apenas nas arestas, a informação das arestas deve ser agrupada e passada aos nós
• Se a informação necessária para prever arestas estiver apenas nos nós, a informação dos nós é reunida em direção às arestas para a predição
• Em predição do grafo inteiro, todas as informações de nós ou arestas são reunidas e agregadas em uma representação global
  • Isso desempenha um papel semelhante ao Global Average Pooling em CNNs
  • Exemplos incluem prever se uma molécula é tóxica ou se tem um cheiro específico

Usando a estrutura de conexões com message passing

• Uma GNN simples não usa a conectividade do grafo dentro da camada, usando-a apenas no pooling logo antes da predição
• GNNs mais fortes executam message passing dentro da camada, refletindo a estrutura de conexões na atualização dos embeddings
• O message passing funciona em três etapas
  • Cada nó faz gather dos embeddings ou mensagens dos nós vizinhos
  • As mensagens são agregadas com uma função como sum
  • As mensagens reunidas passam por uma função de atualização aprendível
• Message passing é semelhante à convolução padrão
  • Em imagens, um pixel reúne informações de um número fixo de pixels vizinhos
  • Em grafos, um nó reúne informações de um número variável de nós vizinhos
• Ao empilhar várias camadas de GNN, informações de nós mais distantes passam a ser refletidas
  • Após 3 camadas, um nó pode incluir informações de nós a 3 passos de distância
• Message passing pode ocorrer não apenas entre nós, mas também entre arestas e entre nós e arestas

Representações de arestas e representações globais

• Nem todo conjunto de dados sempre contém informações de nós, arestas e contexto global ao mesmo tempo
• Se só houver informação de arestas e a tarefa exigir predição em nós, pode-se fazer pooling das arestas e passá-las aos nós
• Informações de nós e arestas podem ter tamanhos ou formas diferentes, então a forma de combiná-las é uma escolha de projeto
  • É possível aprender um mapeamento linear do espaço de arestas para o espaço de nós, ou o contrário
  • Também é possível concatenar as duas representações e então passá-las para a função de atualização
• A ordem em que cada propriedade do grafo é atualizada também faz parte do projeto da GNN
  • Pode-se atualizar primeiro os nós e depois as arestas
  • Pode-se atualizar primeiro as arestas e depois os nós
  • Também é possível um esquema do tipo weave, combinando representações node-to-node, edge-to-edge, node-to-edge e edge-to-node
• Nós muito distantes podem ter dificuldade para trocar informações de forma eficiente mesmo com várias rodadas de message passing
  • Com k camadas, a informação se propaga no máximo por k passos
• A representação global U pode funcionar como um master node ou vetor de contexto conectado a todos os nós e arestas
  • Ela serve como ponte para transferência de informação entre nós e arestas distantes
  • Também pode formar uma representação mais rica do grafo como um todo
• Um novo embedding de nó pode ser condicionado concatenando nós vizinhos, arestas conectadas e informação global
  • Também é possível aplicar um mapeamento linear antes de somar ou usar feature-wise modulation

GNN Playground e exemplo de predição de cheiro molecular

• O GNN Playground trata de um problema de predição em nível de grafo com pequenos grafos moleculares
• Os dados vêm do Leffingwell Odor Dataset e incluem moléculas e rótulos de percepção de cheiro
• O experimento classifica com um único rótulo binário se um grafo molecular tem cheiro “pungent”
  • pungent significa um cheiro forte e marcante
  • Exemplos incluem alho e mostarda, que podem conter allyl alcohol, e piperitone, usado em balas sabor peppermint
• Moléculas são representadas com átomos como nós e ligações como arestas
  • Os nós têm identidade atômica de Carbon, Nitrogen, Oxygen e Fluorine codificada em one-hot
  • As arestas têm tipo de ligação single, double, triple ou aromatic codificado em one-hot
• O template do modelo consiste em camadas sequenciais de GNN seguidas por um modelo linear com ativação sigmoid
• As escolhas de projeto são controladas por quatro eixos
  • número de camadas de GNN, isto é, a profundidade
  • dimensão do embedding de cada propriedade
  • função de agregação do pooling: max, mean, sum
  • quais propriedades entre nós, arestas e representações globais serão atualizadas e usadas em message passing
• O Playground executado no navegador roda sobre tfjs
• Embeddings de grafo de alta dimensão são reduzidos para 2D com PCA para visualizar representações próximas à fronteira de decisão

Tendências de projeto de GNN observadas nos experimentos

• O desempenho varia conforme os dados, a forma de construir o grafo e a forma de caracterizá-lo
• Havia correlação entre maior número de parâmetros e melhor desempenho, mas a GNN também conseguiu encontrar modelos de alto desempenho com poucos parâmetros
  • Foram encontrados modelos de alto desempenho com cerca de 3k parâmetros
• Embeddings de maior dimensão tendiam a melhorar o desempenho médio e o piso de desempenho, mas os melhores modelos também apareceram em dimensões pequenas
• O aumento do número de camadas tendia a elevar o desempenho médio, mas os melhores modelos não apareceram com 3 ou 4 camadas, e sim com 2 camadas
  • Com 4 camadas, o piso de desempenho caiu
  • Mais camadas difundem informação para mais longe, mas trazem risco de diluir a representação dos nós com muitas iterações
• Entre as funções de agregação, sum parecia ligeiramente melhor no desempenho médio, mas max e mean também conseguiam produzir modelos igualmente bons
• Quanto maior a troca de mensagens entre propriedades de nós, arestas e contexto global, melhor tendia a ser o desempenho médio do modelo
  • Como a tarefa era centrada em representação global, aprender explicitamente a propriedade global tendia a melhorar o desempenho
  • Representações de nós pareciam mais úteis do que representações de arestas, porque continham mais informação

Grafos mais complexos e aprendizado em lote

• O framework de message passing pode ser aplicado a estruturas de grafos mais complexas
• Em um multigraph, o mesmo par de nós pode compartilhar vários tipos de aresta
  • Em redes sociais, tipos de relação como acquaintance, friend e family podem ser usados como tipos de aresta
  • É possível ter etapas diferentes de message passing para cada tipo de aresta
• Em um nested graph, um nó pode voltar a representar um grafo
  • Em uma rede de moléculas, um nó pode ser uma molécula e uma aresta pode representar a reação que transforma uma molécula em outra
  • Pode-se alternar o treinamento entre uma GNN em nível molecular e outra em nível de rede de reações
• Em um hypergraph, uma aresta pode se conectar a vários nós, e não apenas a dois
  • É possível identificar comunidades de nós e usar uma hyper-edge conectada à comunidade inteira
• Como grafos não têm número fixo de nós e arestas, o aprendizado em minibatches de tamanho fixo é difícil
• O ponto central do aprendizado em lote para grafos é criar subgrafos que preservem propriedades importantes do grafo maior
  • Em redes de citação, amostrar subgrafos pode ser natural
  • Em moléculas, um subgrafo representa uma molécula nova e menor, então pode ser uma manipulação forte
• Amostragem de grafos é especialmente importante quando o grafo grande não cabe na memória
  • Estruturas e estratégias de treino como Cluster-GCN e GraphSaint se relacionam a isso

Viés indutivo adequado a grafos

• Modelos tendem a ter melhor desempenho preditivo, menor tempo de treinamento, menos parâmetros e melhor generalização quando são projetados para explorar simetrias e regularidades dos dados
• Modelos para imagens usam convoluções translation invariant para explorar a propriedade de que um objeto é o mesmo independentemente de onde apareça na imagem
• Em texto, a ordem dos tokens importa, então RNNs processam sequencialmente, e modelos da família Transformer podem prestar atenção a diferentes partes da frase
• Em grafos, as relações entre arestas, nós e elementos globais são importantes, então é necessário um viés indutivo relacional
  • É preciso preservar a estrutura de adjacência, que explicita as relações
  • É preciso preservar a simetria do grafo, isto é, a invariância a permutação
  • O modelo deve funcionar independentemente da ordem de nós ou arestas e lidar com entradas de quantidade variável

Escolha da operação de agregação

• Fazer pooling das informações de nós e arestas vizinhas é uma etapa central de arquiteturas de GNN mais poderosas
• Cada nó tem um número diferente de vizinhos e o resultado precisa ser independente da ordem de entrada, então é necessária uma função de agregação diferenciável e invariante a permutação
• Candidatos representativos são sum, mean, max
  • Todos aceitam um número variável de entradas e produzem saída independente da ordem
• Nenhuma operação é sempre a melhor
  • mean é útil quando o número de vizinhos varia muito ou quando se precisa de uma visão normalizada das características da vizinhança local
  • max é útil quando se quer destacar uma única característica marcante da vizinhança local
  • sum mostra a distribuição das características locais e, por não ser normalizado, também pode enfatizar outliers
• Na prática, sum é usado com frequência
• Principal Neighborhood Aggregation concatena várias operações de agregação e adiciona uma função de scaling que varia conforme o grau de conexão
• Também é possível projetar operações de agregação especializadas para o domínio, como Tetrahedral Chirality

GCN, multiplicação de matrizes e percurso em grafos

• Um GCN ou MPNN com k camadas e consulta a vizinhos de grau 1 pode ser visto como uma rede neural operando sobre embeddings de subgrafos de tamanho k
  • A representação atualizada de um nó reflete de forma limitada informações de vizinhos dentro de distância k
  • Representações de arestas podem ser interpretadas da mesma forma
• O produto da matriz de adjacência A com a matriz de características dos nós X, isto é, AX, implementa um message passing simples com agregação sum
  • Um caso em que A_i,k é positivo corresponde à existência de uma aresta entre node_i e node_k
  • A multiplicação de matrizes pode ser vista como uma operação que reúne valores de uma dimensão específica das características dos nós vizinhos
• Quando A é esparsa, não é necessário somar todos os termos iguais a 0, então a lista de adjacência é mais eficiente
• Implementações baseadas em lista de adjacência também facilitam o uso de funções de agregação além de sum
• Potências da matriz de adjacência A^K se conectam a walks de comprimento K
  • A^2_ij conta o número de walks de comprimento 2 de node_i até node_j
  • Essa intuição se estende de A^3 até A^k

Attention, explicabilidade e modelos generativos

• Graph Attention Networks não apenas somam informações dos vizinhos, mas as reúnem por soma ponderada
  • A função de pontuação f(node_i, node_j) calcula a relevância entre o nó central e o nó vizinho
  • A normalização por softmax permite dar mais peso aos vizinhos importantes para a tarefa
  • O cálculo de pontuação por pares preserva a invariância a permutação
• Transformers podem ser vistos como GNNs com mecanismo de attention
  • Elementos como tokens de caracteres são modelados como nós em um grafo totalmente conectado
  • A attention calcula embeddings de arestas e pesos para cada par de nós
  • A diferença é que GNNs assumem padrões de conexão esparsos, enquanto Transformers modelam todas as conexões
• A explicabilidade em GNNs pode ser importante para confiabilidade do modelo, debugging e descoberta científica
  • Em moléculas, a presença de certos subgrafos pode ser importante
  • Em redes de citação, o grau de conexão de um artigo pode ser importante
  • GNNExplainer aborda isso extraindo subgrafos relevantes para a tarefa
  • Técnicas de attribution atribuem importância a partes do grafo
• Modelos generativos de grafos amostram novos grafos da distribuição aprendida ou completam um grafo dado um ponto de partida
  • Uma aplicação é projetar novos grafos moleculares com propriedades específicas como candidatos a fármacos
• A principal dificuldade da geração de grafos é modelar a topologia do grafo
  • A topologia pode variar muito de tamanho e pode incluir termos N_nodes^2
  • Matrizes de adjacência podem ser modeladas diretamente como imagens em um autoencoder
  • Também é possível prever apenas arestas existentes e parte das inexistentes para reduzir o custo de N_nodes^2
  • Outra abordagem é construir o grafo sequencialmente por meio de ações discretas repetidas, como adicionar e remover nós e arestas

Resumo

• Grafos são um tipo de dado estrutural com forças e limitações diferentes de imagens e texto
• GNNs atualizam nós, arestas e contexto global do grafo enquanto lidam com a estrutura de conexões e a invariância a permutação
• Pooling, message passing, representações de arestas, representações globais e escolha da função de agregação são elementos centrais no projeto de GNNs
• O desempenho real depende fortemente não só de profundidade, dimensão e número de parâmetros, mas também de quais propriedades do grafo trocam mensagens entre si e de como o grafo é construído

[GN⁺]

Comentários do Hacker News

• Há muitos artigos que usam simulação física (por exemplo, dinâmica de fluidos computacional) com GNNs. Isso acontece porque, nessas aplicações, as malhas não estruturadas usadas para discretizar o domínio do problema se encaixam muito bem na estrutura de grafo
  Na prática, cada malha/grafo costuma ser usada uma única vez para resolver um problema específico, então treinar uma GNN para um grafo específico não faz muito sentido. Ainda assim, a maioria dos artigos fez isso, aparentemente porque ainda não encontraram uma forma de criar GNNs que se adaptem bem a diferentes malhas/grafos e parâmetros de simulação. Fico curioso para saber se em breve surgirá algum avanço que permita esse tipo de generalização

  • Parece que as palavras dentro e fora de uma frase também funcionam como nós-folha que referenciam ou são referenciados por outras palavras, formando uma espécie de grafo. Vendo o sucesso do mecanismo de atenção nos LLMs modernos, fico pensando quão bem eles iriam se saíssem treinados para processar grafos de fato
    Para obter desempenho ideal, provavelmente seria necessário outro tokenizador
  • Um solucionador de grafos de propósito geral teria que ser uma inteligência de propósito geral. Afinal, ele poderia modelar com sucesso até teoria das categorias

• A qualidade do trabalho é altíssima, então é uma pena que o distill.pub não tenha encontrado um caminho sustentável [1]
  Um dos motivos de GNNs serem menos discutidas pode ser a falta de conjuntos de dados [2]. Isso também afetou a área da web semântica
  [1] https://distill.pub/2021/distill-hiatus/
  [2] https://huggingface.co/datasets?task_categories=task_categor...

  • Antes de mergulhar direto em um artigo de uma área desconhecida, eu costumo pesquisar por “ explained” no YouTube
    Se for uma área popular, há muita gente incentivada a fazer vídeos curtos e envolventes, então a qualidade costuma ser boa mesmo em matemática relativamente abstrata. Recursos visuais ajudam muito a criar intuição para conceitos abstratos, e o 3Blue1Brown já provou isso. Com GNN, basta ver alguns bons vídeos de menos de 10 minutos para ganhar base e então entrar na literatura
  • Sinceramente, quando vi isso na primeira página, achei que a distill tivesse encontrado um jeito de seguir em frente, mas não era o caso

• Pessoalmente, GNNs foram bem decepcionantes. Tentei aplicá-las algumas vezes em pesquisa, mas nunca funcionaram muito bem
  Por muito tempo, GNNs foram apresentadas como uma generalização das CNNs, mas CNNs são mais poderosas porque os “pesos de vizinhança” são mais significativos. Elas aprendem relações de posição relativa. GNNs normalmente dependem de pooling, como explicado aqui. CNNs conseguem gerar imagens, mas gerar grafos com GNNs não é nada fácil. A topologia ainda precisa ser definida de antemão e, às vezes, até durante o treinamento. E o golpe final é o desempenho. GNNs são inacreditavelmente lentas em comparação com CNNs
  Hoje em dia, por esses motivos, parece que a atenção substituiu bastante as GNNs. Dá para criar GNNs com atenção em vez de pooling, mas isso não parece ter muito valor. Em geral, o grafo é percorrido só para montar uma matriz de máscara, e o resto é um transformer comum. Se já existe alguma métrica de distância, muitas vezes nem a adjacência do grafo é necessária
  Talvez GNNs sejam extremamente úteis para alguém em algum lugar, mas, na minha experiência, elas pareceram mais um martelo procurando prego

  • Há pelo menos um caso em que GNNs são úteis. Quando os dados são um conjunto de átomos cujas interações definem um item de dado único, esse conjunto é grande demais para simplesmente empurrar com atenção, existe uma estrutura de vizinhança/geometria definida por interações dentro do conjunto, preservar isso dá ao dado equivariância a permutação, e não se consegue encontrar uma forma significativa de representar essa geometria implicitamente. Por exemplo, quando a estrutura muda de amostra para amostra, então a estrutura de vizinhança/interação é passada como entrada para ser processada
    Em quase todos os outros casos, dá para aproveitar estrutura extra e construir algo mais eficiente. Se você consegue definir uma ordem, usa um modelo sequencial; se há estrutura euclidiana/riemanniana, usa CNN ou modelo consciente de variedade; se não é necessário estado global, usa redes de nuvem de pontos; se existe hierarquia explícita, usa alguma versão de U-Net daquela modalidade
    O que torna GNNs interessantes é que 1) elas codificam o próprio conceito de relação e 2) têm boa ligação com equações diferenciais discretizadas totalmente gerais. Para quem vem de sistemas complexos/dinâmicos isso é fascinante, mas, se for possível especializar, ainda há métodos mais simples
  • Imagino que você esteja falando de dados regulares, como visão computacional
    Pelos motivos que você citou, acho que não é coincidência GNNs fazerem mais sucesso em áreas como recomendação, em que o próprio modelo do domínio já parece um grafo. Nesses casos, o salto até uma topologia útil é menor
    O que me frustrava ainda mais é que, em muitos desses domínios em forma de grafo, os dados de máquinas/pessoas baseados em comportamento, como logs, também têm muitas dimensões categóricas. A parte do grafo ajuda, mas capturar bem as dimensões categóricas é igualmente importante, e para fazer isso bem muitas vezes você acaba indo para métodos fora desse mundo, como random forests. Começar por aí é mais fácil, e a parte de GNN vira muito trabalho extra por “um pouquinho mais de ganho”
    Claro, se esse for o negócio principal e houver milhões de dólares em jogo, isso pode se justificar. Mesmo assim, é difícil para a maioria das equipes de operação. Na prática, muitas vezes acabam fazendo algo com pygraphistry e xgboost + umap e seguindo em frente. Só fazer um RGCN funcionar bem já dá bastante trabalho
  • O GraphCast do Google é uma GNN: https://deepmind.google/discover/blog/graphcast-ai-model-for...
  • Tive experiência parecida. Vi muitas propostas de usar GNNs em problemas que antes usavam modelos “planos”, por exemplo prevendo rótulos de páginas levando em conta a estrutura HTML. Mesmo em casos que superficialmente pareciam combinar muito bem, não funcionou
  • Acompanhei GNNs na biologia e tentei aplicá-las em alguns domínios, mas até agora os resultados foram decepcionantes. Isso foi um pouco surpreendente, porque outras abordagens baseadas em grafos já foram usadas com sucesso em biologia

• GNNs parecem operar sobre topologia fixa. Como fazer se quisermos aproximar alguma transformação da topologia do grafo? Por exemplo, aprender o layout de um grafo ou transformar a árvore de sintaxe abstrata de um programa em um grafo de fluxo de dados?

• O ponto central de GNN é generalizar para topologias arbitrárias ao condicionar explicitamente o conceito de “vizinho” por meio de um grafo que define a topologia. Layout de grafos foi testado aqui e recebeu bastante atenção em https://github.com/limbo018/DREAMPlace, mas recentemente também houve controvérsias relacionadas https://www.semanticscholar.org/paper/The-False-Dawn%3A-Reev...
  Transformação de grafos também está sendo pesquisada https://arxiv.org/abs/2012.01470. No entanto, é um problema complicado porque é preciso resolver implicitamente o problema de correspondência de grafos

  • Homologia talvez possa ajudar. É como uma espécie de cálculo para estruturas discretas, contando quantos buracos N-dimensionais existem ao longo do tempo. Não sei bem sobre redes neurais, mas isso pode ser usado assim em fMRI

• Seria bom se o distill voltasse

• É realmente uma pena que o distill.pub não esteja aceitando novas submissões

• Fico curioso sobre qual é aquele software de visualização interativa. É D3.js?

• Estou me sentindo burro demais. Naquela página há um exemplo com 4 nós (a,b,c,d) e mostra que o total de combinações possíveis é 24
  Queria saber qual é a fórmula generalizada para calcular isso quando o número de nós é dado, e quando as arestas também precisam ser consideradas. Parece que o texto não explica isso, e imagino que talvez seja fatorial

  • Em combinatória, isso geralmente pode ser calculado rapidamente com fatorial. Se há 4 opções possíveis e, em cada caso, você escolhe exatamente uma vez cada uma das 4, então é 4!. Intuitivamente, você tem 4 opções na primeira escolha, depois 3, depois 2, e por fim sobra 1. Então 4 * 3 * 2 * 1 = 24
    Se quiser ganhar mais familiaridade, este site parece oferecer uma boa visão geral: https://www.geeksforgeeks.org/mathematics-combinatorics-basi...
  • Acho que isso pode ser calculado com coeficientes binomiais ou coeficientes binomiais aninhados. Por exemplo, algo como (n choose 4)
    Como cada aresta pode existir ou não, talvez também fosse possível multiplicar o coeficiente binomial por 2