Personalized PageRank

Índice

• O que é
• Como Funciona
  • Objetivo no Kairos
  • O Grafo ESCO como Substrato do PPR
  • Normalização PPR/PR: Por que ela Importa
  • Parâmetros do PPR
• Demonstração / Exemplos
• ADR's Relacionadas

O que é

O PageRank é um algoritmo de análise de grafos originalmente desenvolvido pelo Google para ranquear páginas web. Ele modela um "caminhante aleatório" que navega pelo grafo: a cada passo, o caminhante segue uma aresta aleatória com probabilidade d (damping factor) ou "teletransporta" para um nó aleatório do grafo com probabilidade 1 - d. A cada vez que o caminhante visita um nó, ele acumula um score, então nós que receberem mais visitas terão scores maiores, o que costuma acontecer com nós que possuem muitas conexões em sua direção. Na abordagem do Google, isso serve para identificar páginas web com mais referências nos outros sites, trazendo ao usuário páginas mais confiáveis e relevantes.

O Personalized PageRank (PPR) é uma variante onde o vetor de teletransporte não é uniforme — em vez de se teletransportar para qualquer nó com igual probabilidade, o caminhante se teletransporta apenas para um conjunto-semente de nós de interesse. Isso concentra a propagação de scores na vizinhança topológica desse conjunto.

PageRank padrão:     teletransporte → qualquer nó (distribuição uniforme)
Personalized PR:     teletransporte → nós-semente (distribuição personalizada)

Como Funciona

Objetivo no Kairos

O PPR é o segundo estágio do "Diamante de Convergência" dentro do algoritmo de Entity Linking. Após o KNN retornar candidatos semanticamente próximos (via similaridade vetorial), o PPR valida esses candidatos usando a estrutura hierárquica da ontologia ESCO persistida no Neo4j.

A intuição é: se uma competência candidata é semanticamente correta para o contexto, ela deve também ser topologicamente coerente com as demais competências do conjunto-semente. competências que recebem votos de múltiplos vizinhos da ontologia (via [:BROADER], [:NARROWER], [:ESSENTIAL]) são mais confiáveis do que competências que aparecem no Top-K apenas por coocorrência semântica.

Dessa forma, enquanto o KNN é uma heurística de recall (focando-se em não descartar candidatos corretos), o PPR é uma heurística de precisão (focando-se em filtrar os candidatos considerados erroneamente como corretos).

O Grafo ESCO como Essência do PPR

O PPR opera sobre o grafo de habilidades ESCO persistido no Neo4j:

O PPR inicia com pesos não-nulos de teleporte apenas nos nós Top-K retornados pelo KNN, os quais recebem o mesmo peso de 1/K de chance de teleporte, sendo denominados conjunto-semente. A propagação flui pelas arestas do grafo, e competências que estão em regiões densamente conectadas ao conjunto-semente acumulam score mais alto.

Parâmetros do PPR

Como é calculada a pontuação final de um candidato?

PageRank Global ($score_{PR\_global}$)

Na etapa de construção inicial do grafo de conhecimento onde as competências ESCO são indexadas, cada nó recebe um score de PageRank global. Esse score ajuda a identificar hubs de conexões que tendem a ter pontuações mais altas tanto no PageRank padrão como no PPR.

Personalized PageRank ($score_{PPR}$)

Durante a execução do PPR, cada candidato recebe um score de PPR que reflete sua relevância topológica em relação ao conjunto-semente.

Normalização PPR/PR: Por que ela Importa

Sem normalização, nós com alto grau de conectividade na ontologia (hubs) acumulam PageRank alto naturalmente e tendem a dominar o resultado do PPR mesmo quando não são os melhores matches semânticos. Com essa normalização, são priorizados os nós que pertençam ao top-K e que sejam habilidades mais específicas e não hubs genéricos de conexões, o que auxilia a destacar competências mais relevantes e específicas para o contexto, em vez de competências genéricas que aparecem em muitos contextos.

Similaridade por cosseno

Por mais que a normalização PPR/PR possua maior influência, são ambos algoritmos não determinísticos e, portanto, as competências finais tendem a variar, porém o top-K vai ser sempre o mesmo. Então isso ajudou na definição do threshold de score final, de 0.59, ajudando a manter uma certa consistência nos resultados e com uma margem mais evidente de diferenciação entre positivos e falsos positivos.

Demonstração / Exemplos

Parâmetros

No artigo original, o Google utilizava damping = 0.85. Para o Kairos, optou-se por um damping mais baixo de 0.6 para aumentar a influência do conjunto-semente de candidatos retornados pelo KNN.

A quantidade de iterações foi definida de forma empírica: aumentava a quantidade de iterações e reduzia o damping para aumentar a influência topológica do conjunto-semente, mas isso também aumentava o custo computacional. O valor de 25 iterações foi um ponto de equilíbrio onde os scores já estavam razoavelmente estabilizados sem exigir um tempo de execução muito alto.

Quando ao threshold, também foi definido de forma empírica, com validação humana e não automatizada, buscando-se um ponto de corte que trouxesse candidatos mais relevantes pensando do ponto de vista do usuário.

PPR Inverte a Ordem do KNN

"Gerir projetos de desenvolvimento de conteúdos" estava em 8ª posição no KNN e alcançou score PPR de 0.918, o maior de todos, enquanto "gestão de projetos lean", em 4ª posição no KNN, foi eliminado por não receber visitas suficientes na propagação do PPR, sendo, provavelmente, um nó mais isolado ou menos conectado à região do grafo onde os demais candidatos estão.

PPR Elimina Candidatos Hub

• Competência Extraída: Comunicação
• Hub Genérico: "operar equipamento de comunicação"
• Competência Específica: "comunicar com colegas e clientes"

Para habilidades de comunicação, a normalização deu maior relevância a "comunicar com colegas e clientes", que é uma habilidade mais específica e relevante, do que "operar equipamento de comunicação", que é um hub genérico.

ADR's Relacionadas