CS224W & Representation Learning - Standford - Parte 1 (aulas 1 a 5)

Material -> http://web.stanford.edu/class/cs224w/

Playlist -> https://www.youtube.com/watch?v=JAB_plj2rbA&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn 

A operação de projeção permite separar um grafo bipartido U-V em dois subgrafos U e V

Os autores 1, 2 e 3 tem arestas entre eles em U pq os 3 tinham arestas ligando a publicação A em U-V. O grafo U é um grafo de co-autoria. 

As publicações B, C, D possuem arestas entre elas pq os 3 tem o autor 5 em comum. 

Most real-world networks are sparse
Consequence: Adjacency  matrix is filled with zeros! => Adjacency list

Def: Induced subgraph is another graph,  formed from a subset  of vertices  and all of the edges
connecting  the vertices in that subset.

Def: Graph Isomorphism: Two graphs  which  contain the same number of nodes connected  in the same way are said to be isomorphic.

Graphlets: Rooted connected induced non-isomorphic subgraphs

Kernel: ML para predição a nível do grafo (e não nó ou arestas)

K (G, G') mede a similaridade entre dois grafos. Matrix kernel K =  (K (G, G')) G, G', matriz simétrica

Ideia geral: Representar G como um Bag of Nodes Degrees

K = [1, 3, 0] ... 1 nó de grau 1, 3 nós de grau 2, 0 nós de grau 3, ... cada posição tem o número de nós com o grau correspondente

- Graphlet Kernel (Bag of Graphlets)

Kernel considerando o número de graphlet como k arestas para cada forma / composição

K (G, G') = fG T fG' se tiverem o mesmo tamanho

K (G, G') = hG T hG', onde hG = fG / Sum (fG) ... normalizar por causa da diferença de tamanho

Contar os graphlets é custoso computacionalmente (exponencial)

- Weisfeiler-Lehman Kernel

Kernel considerando o grau dos nós em relação a vizinhança com K-hops, aplicar uma função de hash para cada lista de vizinhança (com esquema de cores). Tempo de computar é linear em relação a quantidade de arestas

... próximo a GNN, eficiente para medir similaridade entre grafos

Graph Representation Learning ... aprender as características sem precisar de Feature Engeneering (manual) de modo independente da tarefa

Encode a informação da estrutura da rede

d-dimensional embeddings onde d entre 64 e 1024 mas depende do tamanho da rede

shallow: onde a matriz Z tem uma coluna por nó e d linhas (lookup)

Encoder+Decoder: baseado em similaridade dos nós, existem formas diferentes de calcular essa similaridade

Random Walks: probabilidade de visitar o nó v em caminhos aleatórios iniciando no nó u (co ocorrência de u e v em um caminho gerado aleatoriamente), em cada passo o próximo vizinho visitado é aleatório

node2vec: aplica random walk de modo diferente, alterna entre BFS e DFS para criar uma vizinhança que explora semelhanças locais e globais, um parâmetro para a distância máxima na DFS (e retornar as nó de partida) e outro para a alternância. Complexidade linear e pode ser calculado em paralelo.

Abordagens para gerar embeddings de um grafo inteiro ou de sub-grafos como por exemplo Anonymous Walks. A dimensionalidade das representações dependem do tamanho dos grafos e dos caminhos.

PageRank ~= Random Walk

The Web as a Direct Graph. Algumas páginas são mais importantes que outras. 

Acaba por calcular qual a probabilidade de estar na página p em (t+1) usando uma matriz de adjacência estocástica M e a probabilidade p em (t). 

Algoritmo: inicializa cada nó com um valor (time 0) e calcula o page rank de cada item até convergir (a diferença entre t e t-1 < um valor). Usualmente são calculadas em até 50 iterações. 

Problemas com o percurso do grafo são contornados com "pulos aleatórios" para páginas não linkadas a página corrente. 

Grafos Bipartidos e Sistemas de Recomendação

Conceito de "related" ou "proximity" entre entidades para recomendar outras: shortest path, vizinhos em comum, ... qual métrica usar? É possível usar uma opção de Page Rank personalizado onde os nós mais visitados com o random walk seriam os mais próximos. Essa similaridade considera múltiplas conexões, múltiplos caminhos, conexões diretas e indiretas e o grau dos nós.

Similaridade entre dois nós: se u e v estão conectados então o produto entre seus embeddings { z(v) T z(u) } deve estar próximo de 1 e caso contrário mais próximo de 0 pq na matriz de adjacência A é assim que a conectividade será representada. Então ZT * Z = A

A dimensão d, ou seja, número de linhas em Z é bem menor que o número de nós n. 

O objetivo do aprendizado é gerar embeddings tal que:

O decoder para definir a similaridade com base na conectividade dos nós é equivalente a fatorização de matriz. 

Com DeepWalk e node2vec cada nó adicionado é preciso recomputar todos os embeddings do grafo e não é possível capturar similaridade em termos estruturais e de vizinhança. Por isso Deep Representantion Learning e Graph Neural Networks cobrem essas limitações.

Como associar labels a nós? Considerar que alguns rótulos estão faltantes e outros são imprecisos / errados. 

Message Passing over the Network: explorar correlações, ou seja, nós que compartilham rótulos tendem a estar conectados.Três técnicas para Collective Classification: Relational classification, Interative classification e Belief propagation

Homofilia: pessoas com características em comum (similares) tendem a formar conexões sociais. Tendência de clusterização de nós com os mesmo rótulos.

SERIA POSSÍVEL IDENTIFICAR O FENÔMENO DE HOMOFILIA EM TERMOS DOS TEMAS ASSOCIADOS A MEIO AMBIENTE???? Ver esse vídeo https://youtu.be/6g9vtxUmfwM

Influência: conexões sociais tendem a influenciar as pessoas conectadas de modo a aumentar as características em comum

Se um nó v está ligado a outro nó u com o rótulo X então esse nó v também tende a ter o rótulo X.O que pode influenciar: as features de v, as features dos vizinhos de v e os rótulos dos vizinhos de v. 

Aprendizado semi-supervisionado (alguns nós tem rótulos), premissa é que deve existir homofilia na rede: framework probabilístico que usa a premissa Markov, ou seja, a probabilidade do nó v possuir o rótulo X depende do rótulo do seu conjunto de vizinhos N .... P (Xv) = P (Xv | Nv)

Etapas: (1) classificador local associa rótulos iniciais ao nós sem rótulo baseado em suas características isoladamente, (2) classificador relacional captura as correlações entre os nós e aprende um modelo para prever os rótulos baseado nas características e o rótulos dos vizinhos e (3) a inferência coletiva propaga essa correlações pela rede atualizando os rótulos até convergir / estabilizar. 

Probabilistic Relational Classifier: somente os rótulos, não considera as características. Para cada classe X de nó: os nós com rótulos X iniciam com probabilidade 1 (pq são ground-truth), os nós com rótulos diferentes de X iniciam com probabilidade 0 (também são ground-truth) e os desconhecidos recebem a probabilidade 0,5. Atualiza a probabilidade dos desconhecidos em uma ordem fixa como a média das probabilidade de seus vizinhos normalizada até convergir (não é atualizada a probabilidade) mas a convergência não é garantida.

Iterative Classifier: usar os atributos / características. Tratam-se de dois classificadores: um que considera somente as features para a predição e o segundo que além da features, usa um resumo dos rótulos dos vizinhos. Esse resumos pode ser um histograma de cada rótulos dos vizinhos (convertidos em vetor). Os nós com rótulos desconhecidos são inicializados com o resultado do primeiro classificador. Depois o segundo classificador é aplicado e o resumo dos rótulos é recalculado a cada iteração até convergir (não é atualizada o rótulo) mas a convergência não é garantida. 

Loopy Belief Propagation: abordagem de programação dinâmica, a ordem dos nós (caminho) é definido para a propagação da mensagem. Cada nós recebe a probabilidade de suas arestas de entrada, atualiza a própria probabilidade e envia através das arestas de saída. Ainda é possível usar em caso de ciclos mas as mensagens deixam de ser independentes.