SBBD 2021- Tutorial - Aprendizado de Máquina e Grafos

Introdução

Linguagem Geral (ou Modelo)? Linguagem de Modelagem

Foco na generalização e relacionamentos entre instâncias de dados. 

Tarefas podem ser realizadas em diferentes escalas, níveis: nó, relação, comunidade, grafo completo

Features extraídas estatisticamente como o grau.

Matriz de Adjacência é esparsa, Multigrafos, Conectividade de Grafos

ML:acurácia é a proporção de exemplo que o modelo classifica corretamente. Entrada é um vetor de features e saída podem ser rótulos de classes, um indicador de regressão,o cluster que pertencem ou um vetor latente de representação. Objetivo é minimizar o erro empírico (função de custo) de classificação (usar L1, L2, Entropia Cruzada ...), pode ser usado o Gradiente Descendente para otimizar a função de custo. 

Redes neurais: feed foward cada camada está conectada a camada seguinte, redes convolucionais recebem a entrada em partes para achatar o vetor e gerar a predição

Machine Learning Tasks on Graphs

O grau do nó pode ser uma feature mas trata os vizinhos de modo igual. Medidas de centralidade capturam melhor o conceito de importância (eigenvector, betweeness, closeness). Coeficiente de clusterização conta o número de triângulos fechados (graphlets de 3 nós totalmente conectados) saindo de um nó. Graphlets são todos os sub-grafos possíveis de tamanho até x, onde x é no máximo n-1.

Similaridade entre nós pode estar relacionado com a probabilidade de haver uma aresta entre eles. Tarefas de predição de Links. Essa similaridade pode ser calculada com shortest-path (feature baseada em distância) ou sobreposição local/global de vizinhos (jaccard). Separar as arestas de treinamento e testes do grafo. Em métodos locais, se os nós não tiverem vizinhos em comum então a similaridade é zero. Métodos globais não tem essa característica. 

Features a nível de grafos: métodos kernel. Usar Bag of Nodes e agregar as estatísticas dos nós. Contar os graphlets. Essas features não são completamente independentes e agrupar pode gerar problemas ao serem usados em algoritmos de ML.

Embeddings de Nós: Encoder -> Decoder. A similaridade entre os embeddings podem regerar a própria matriz de adjacências. 

Abordagem tradicional: Shallow embeddings ... uma coluna por nó (vetor) na matriz de embeddings. A matriz é d x |V| , onde d é a dimensão do vetor. 

Decoder: Método de Fatorização da Matriz como o produto interno entre os vetores.

Decoder: Random Walk para identificar nós que co-ocorrem em caminhos aleatórios de tamanho t. DeepWalk e node2vec (BFS ou DFS)

É possível usar Redes Neurais para gerar os embeddings: Deep Autoencoders

- Cada nó tem uma representação de ALTA dimensionalidade na entrada, a dimensão do vetor é |V| -> isso é um problema, e o vetor é esparso

Taxonomia de Técnicas para Graph Embeddings (imagem importante) ... artigo 2018 "A Comprehensive Survey of Graph Emebddings ....

Shallow não compartilham informações entre nós, requerem que seja retreinado caso incluam novos nós ou arestas, 

GNN

2020 A Comprehensive Survey on Graph Neural ... 

Redes são mais complexas que imagem e texto para serem inputados em uma rede neural

Cada camada na rede de convolução faz a informação de um nó se propagar aos seus vizinhos. 

A agregação de vizinhança é análogo ao pooling de redes convolucionais convencionais. A diferença entre os métodos está justamente no pooling e update. 

Split do grafo em Treinamento, Validação e Teste: esconder o label dos nós do processo de treinamento para classificação de nós

Split do grafo em Treinamento, Validação e Teste: remover arestas do processo de treinamento para predição de links

Quais são as limitações dessas abordagens: over-smoothing e over-squashing 

Pesquisas

Embeddings de Grafos Dinâmicos

Bibliotecas e GraphDBs

AliGraph é do Alibaba