Pinterest PinSage / Pixie (Related Pins)

01 · CONTEXTO

Recomendar a partir de um grafo de pins e boards

No Pinterest, as pessoas organizam pins em boards, que reúnem pins relacionados por tema. O PinSage e o Pixie tratam esse ambiente como um grafo bipartido de pins e boards.

Nas escalas relatadas, o grafo do PinSage tem 3 bilhões de nós e 18 bilhões de arestas; o do Pixie, já podado, tem 3 bilhões de nós e 17 bilhões de arestas.

O Pixie percorre o grafo com random walks para recomendar sob demanda. O PinSage aprende embeddings de pins com uma rede convolucional em grafo, um problema de design de sistemas de ML. Segundo o artigo do PinSage, o método do Pixie não gera embeddings de pins e era, na época, o estado da arte no Pinterest para certas tarefas.

02 · PIXIE EM TEMPO REAL

Pixie: random walks sob demanda

O Pixie nasce de um requisito de latência: o artigo define tempo real como menos de 100 milissegundos por requisição. Se o cálculo fosse lento demais para o usuário esperar, as recomendações de todos os usuários teriam de ser pré-calculadas e materializadas.

1. O pipeline Hadoop reúne as arestas entre boards e pins e envia o arquivo bruto ao armazenamento global.

2. O compilador do grafo baixa o arquivo, poda o grafo e o grava em formato binário.

3. O servidor Pixie, que verifica periodicamente se há grafo novo, carrega o grafo mais recente na memória.

4. O app envia ao servidor o conjunto de pins de consulta, montado a partir dos pins com que a pessoa interagiu.

5. O servidor simula caminhadas curtas a partir dos pins de consulta e conta as visitas a cada pin.

6. Os pins com mais visitas voltam ao app como recomendações.

A base é simples: a partir do pin de consulta, simulam-se muitas caminhadas curtas no grafo e conta-se quantas vezes cada pin é visitado; quanto mais visitas, mais relacionado ele é ao pin de consulta. O tempo do procedimento é constante e independe do tamanho do grafo, pois é determinado pelo parâmetro N.

Sobre essa base o Pixie acrescenta melhorias: viés por usuário na escolha das arestas, pesos diferentes para cada pin de consulta, preferência por candidatos ligados a vários pins de consulta e parada antecipada, que encerra as caminhadas quando o conjunto dos melhores candidatos fica estável.

Como a caminhada visita pins e boards, os dois tipos de objeto podem ser recomendados. Para mostrar pins novos, o Pixie recomenda primeiro boards e depois serve os pins novos salvos neles.

03 · PIXIE E O GRAFO EM MEMÓRIA

O grafo cabe numa máquina, por projeto

O grafo vem de um pipeline Hadoop e de um compilador de grafo, e esse processo roda uma vez por dia. O compilador roda em uma única máquina com RAM da ordem de terabytes, poda o grafo e o grava em formato binário, que pode ser compartilhado facilmente entre máquinas. Esse fluxo é um pipeline de dados em lote que alimenta o serviço online.

A poda remove do grafo os boards de entropia alta de tópicos e descarta arestas de pins de grau alto. Segundo o artigo, ela reduz o grafo e a memória em seis vezes e deixa as recomendações 58% mais relevantes.

Com isso, o grafo podado de 3 bilhões de nós e 17 bilhões de arestas cabe em cerca de 120 GB de memória principal. A random walk não precisa cruzar máquinas, e a capacidade cresce adicionando máquinas ao cluster. Cada servidor reinicia uma vez por dia para carregar o grafo mais recente.

04 · PINSAGE E A CONVOLUÇÃO EM GRAFO

PinSage: embeddings que unem grafo e conteúdo

Uma rede convolucional em grafo (GCN) aprende a agregar iterativamente informação de atributos da vizinhança local de cada nó. As GCNs aproveitam tanto o conteúdo quanto a estrutura do grafo, e os pins têm atributos de texto e de imagem. O desafio apontado pelo artigo é escalar treino e inferência para grafos com bilhões de nós e dezenas de bilhões de arestas.

Em vez de usar todos os vizinhos, o PinSage simula random walks a partir do nó e define a vizinhança como os nós com as maiores contagens de visita normalizadas. Essas contagens viram os pesos de uma média ponderada na agregação, chamada de importance pooling.

Os parâmetros dos módulos convolucionais são compartilhados entre todos os nós, e por isso a complexidade de parâmetros independe do tamanho do grafo de entrada.

1. Os pares positivos de treino, de pins relacionados, vêm do histórico de engajamento dos usuários.

2. A lista de adjacência e a matriz de atributos ficam na memória da CPU, de onde o produtor as lê.

3. O produtor, limitado por CPU, amostra as vizinhanças dos nós; a CPU também cuida da amostragem de negativos.

4. Os minibatches prontos seguem para a GPU, que não precisa se comunicar com a CPU durante a convolução.

5. O modelo treinado fica guardado para a etapa de inferência, tratada a seguir.

O treino adota o padrão produtor-consumidor: um produtor de memória grande, limitado por CPU, amostra as vizinhanças, e um modelo TensorFlow limitado por GPU consome os grafos de computação já montados. A lista de adjacência e a matriz de atributos ficam na memória da CPU.

Para o modelo separar itens parecidos, cada exemplo positivo ganha hard negatives: itens um pouco relacionados à consulta, mas menos que o item positivo, amostrados aleatoriamente entre as posições 2000 a 5000 do ranking. Um currículo de treino não os usa na primeira época e os adiciona nas épocas seguintes.

05 · PINSAGE: INFERÊNCIA E SERVIÇO

Embeddings pré-calculados, busca online

Calcular embeddings nó a nó com o algoritmo ingênuo leva a cálculos repetidos. O PinSage usa um pipeline MapReduce que roda a inferência do modelo sem cálculos repetidos, e o vetor latente de cada nó é calculado uma só vez. É outro exemplo de pipeline de dados em lote.

1. Com o modelo já treinado, os jobs MapReduce leem o grafo e os atributos dos pins.

2. Os jobs projetam todos os pins num espaço latente e juntam essas representações aos boards em que cada pin aparece.

3. O processo se repete para as camadas seguintes, usando como entrada as representações da camada anterior.

4. Os embeddings, cada um calculado sem repetição, são salvos no banco de embeddings.

5. Para recomendar pins relacionados, o app envia um pin de consulta ao serviço de busca.

6. O serviço busca no banco os embeddings mais próximos do pin de consulta, com apoio de hashing sensível à localidade.

O modelo é treinado offline e os embeddings de todos os nós são calculados via MapReduce e salvos num banco. Assim, a busca eficiente por vizinhos mais próximos permite servir recomendações online. O artigo cita locality sensitive hashing como forma de obter KNN aproximado.

Na avaliação offline, o PinSage chegou a 67% de hit-rate e 0,59 de MRR. Em testes A/B no homefeed, a taxa de repin melhorou de 10% a 30% sobre as alternativas de anotação e visuais. A inferência para 3 bilhões de itens termina em menos de 24 horas.

06 · COMPARAÇÃO

Pixie e PinSage lado a lado