MeliGraph

Motor de Recomendação baseado em Grafos para Elixir.

Inspirado nos sistemas WTF (Who to Follow) e GraphJet do Twitter, e nos padrões OTP do Oban.

Features

Grafo em memória com segmentação temporal (GraphJet-style)
Pesos nas arestas (v0.2.1) — insert_edge/5 aceita weight opcional, usado pelo LightGCN para construir Ã = D^(-1/2)·W·D^(-1/2) ponderada
PageRank Personalizado via Monte Carlo random walks
SALSA para grafos bipartidos (hubs/authorities)
SimilarItems — co-ocorrência 2-hop com normalização Jaccard/Cosine
GlobalRank — ranking global por in-degree para cold start
LightGCN — embeddings aprendidos via Nx.Defn + BPR loss (v0.2) com fallback automático para SALSA
Single-writer / multi-reader via GenServer + ETS
Múltiplas instâncias isoladas via Registry
Telemetry-first — todas as operações emitem eventos
Modo de testing :sync — testes determinísticos sem processos async
Plugin system — Pruner, CacheCleaner extensíveis

Instalação

def deps do
  [
    {:meli_graph, "~> 0.2.1"},
    # Recomendado para o LightGCN em produção:
    {:exla, "~> 0.9"}    # backend XLA (CPU/GPU) para o trainer
  ]
end

Mudança em v0.2.1: :nx agora é dependência obrigatória do meli_graph (era optional). Não precisa declará-la nas suas deps — vem transitivamente.

E configure o EXLA como compilador padrão de Nx.Defn:

# config/config.exs (ou config/runtime.exs no app caller)
config :nx, default_backend: EXLA.Backend
config :nx, :default_defn_options, compiler: EXLA

Sem EXLA o LightGCN ainda compila e roda (via Nx.BinaryBackend), mas é ordens de magnitude mais lento — em produção, EXLA é obrigatório para treinos noturnos caberem em janela de horas. Quando o trainer detecta a ausência de EXLA, emite um Logger.warning uma vez por VM no primeiro treino.

Quick Start

# Iniciar uma instância
{:ok, _} = MeliGraph.start_link(
  name: :my_graph,
  graph_type: :bipartite,
  testing: :sync
)

# Inserir arestas (usuário → conteúdo). Peso opcional (default 1.0).
MeliGraph.insert_edge(:my_graph, "user:1", "post:a", :like)
MeliGraph.insert_edge(:my_graph, "user:2", "post:a", :like)
MeliGraph.insert_edge(:my_graph, "user:2", "post:b", :comment, 1.5)

# Recomendações
{:ok, recs} = MeliGraph.recommend(:my_graph, "user:1", :content,
  algorithm: :salsa, seed_size: 10, top_k: 5)

# Explorar o grafo
MeliGraph.neighbors(:my_graph, "user:1", :outgoing)
# => ["post:a"]

MeliGraph.edge_count(:my_graph)
# => 3

Múltiplas Instâncias

# Em uma Application supervision tree
children = [
  {MeliGraph, name: :follows, graph_type: :directed},
  {MeliGraph, name: :interactions, graph_type: :bipartite}
]

Supervisor.start_link(children, strategy: :one_for_one)

# Cada instância é isolada
MeliGraph.insert_edge(:follows, "user:1", "user:2", :follow)
MeliGraph.insert_edge(:interactions, "user:1", "post:a", :like)

Algoritmos

Algoritmo	Tipo de Grafo	Caso de Uso
PageRank	Dirigido	"Who to Follow", Circle of Trust
SALSA	Bipartido	"Posts para você", recomendação de conteúdo
SimilarItems	Bipartido	"Professores similares a X", itens co-consumidos
GlobalRank	Qualquer	Top itens para anônimos, cold start
LightGCN	Bipartido	Recomendação personalizada via embeddings aprendidos

Algoritmos customizados podem ser adicionados implementando o behaviour MeliGraph.Algorithm.

Pesos nas Arestas (v0.2.1)

Toda aresta carrega um campo weight :: float() (default 1.0) que representa a força do sinal user↔item. Pesos são consumidos pelo LightGCN ao construir a matriz de adjacência ponderada Ã = D^(-1/2) · W · D^(-1/2). Os demais algoritmos (PageRank, SALSA, SimilarItems, GlobalRank) ignoram o peso na v0.2.1 — comportamento idêntico ao de v0.2.0.

# Click é sinal mais forte que like; like mais que view.
MeliGraph.insert_edge(:feed, "profile:42", "post:7", :view, 0.5)
MeliGraph.insert_edge(:feed, "profile:42", "post:7", :like, 1.0)
MeliGraph.insert_edge(:feed, "profile:42", "post:7", :comment, 1.5)

Acumulação de pesos

Quando múltiplas arestas conectam o mesmo par (user, item), o LightGCN soma os pesos ao construir W. No exemplo acima, o par profile:42 ↔ post:7 entra na matriz com W[u,i] = 3.0 (0.5 + 1.0 + 1.5). Interpretação: cada interação positiva adiciona evidência ao sinal.

Mudança de comportamento (v0.2.1, importante): chamar insert_edge repetidamente para o mesmo par não é mais idempotente do ponto de vista do LightGCN — cada chamada adiciona peso. Em v0.2.0 inserções duplicadas eram deduplicadas. Para grafos do tipo :directed (ex.: follows recíprocos), evite inserir o mesmo par duas vezes — ou aceite que o LightGCN tratará como sinal acumulado.

Recomendações sobre escolha de pesos

Range pequeno e estável funciona melhor (0.5 a 3.0). Pesos grandes desbalanceiam a normalização D^(-1/2) e dominam o ranking.
Sinais implícitos (view, click) costumam pesar menos que explícitos (like, comentário, favorito).
Se o range natural dos pesos for amplo (ex.: dwell time em segundos), aplique :math.log/1 ou clamp manual antes de inserir.
Pesos em testes A/B: comece uniforme (1.0 em tudo), valide o pipeline fim-a-fim com SALSA/LightGCN, e só depois introduza pesos diferenciados comparando recall@K.

LightGCN (v0.2)

Modelo de embedding colaborativo (paper He et al., SIGIR 2020) treinado via Nx.Defn + BPR loss. A lib não persiste embeddings — produz e consome binary; o app caller decide onde guardar (Postgres, R2, S3...).

A v0.2.1 incorpora pesos das arestas na matriz de adjacência: Ã = D^(-1/2) · W · D^(-1/2) em vez da A binária do paper original. Pesos somam quando múltiplas arestas conectam o mesmo par user↔item.

# 1. Treinar — lê o grafo atual e devolve um binary serializado
{:ok, binary} = MeliGraph.train_embeddings(:professor_graph,
  user_prefix: "profile:",
  embedding_dim: 64,
  layers: 3,
  epochs: 1000
)

# 2. App persiste o binary onde quiser (Postgres bytea, R2, etc.)
Repo.insert(%GraphEmbedding{graph_name: "professor_graph", data: binary})

# 3. Carregar embeddings na instância (ETS com TTL :infinity)
:ok = MeliGraph.load_embeddings(:professor_graph, binary)

# 4. Recomendar — top-K via dot product
{:ok, recs} = MeliGraph.recommend(:professor_graph, "profile:42", :content,
  algorithm: :lightgcn, top_k: 16)

# 5. Health check — fallback automático para SALSA quando false
MeliGraph.embeddings_ready?(:professor_graph)
# => true

Quando os embeddings ainda não foram carregados, algorithm: :lightgcn faz fallback transparente para SALSA — o caller não precisa tratar esse caso. Veja docs/lightgcn.md para arquitetura, fluxo de treino, hiperparâmetros e validação empírica.

Recomendação para feed heterogêneo (posts + reviews + ads)

LightGCN não distingue tipos de item — ele só vê uma matriz bipartida users × items. Para um feed que mistura posts normais, reviews de professor e anúncios, basta unificar tudo num pool de itens com IDs namespaced (post:42, review:128, ad:7).

Exemplo end-to-end: monte o grafo a partir das tabelas do app, diferenciando o sinal por tipo de interação via weight:

# config/config.exs
config :meli_graph,
  weights: %{
    view: 0.5,
    like: 1.0,
    comment: 1.5,
    click: 2.0
  }

# Pipeline de ingestão (ex.: job noturno + stream de eventos novos)
defmodule MyApp.GraphIngestion do
  @weights Application.compile_env(:meli_graph, :weights)

  def rebuild_graph! do
    {:ok, _} = MeliGraph.start_link(
      name: :feed,
      graph_type: :bipartite,
      segment_max_edges: 5_000_000
    )

    # Posts normais — likes
    Repo.all(
      from l in Like,
        join: p in Post, on: p.id == l.post_id,
        where: l.like_type == "upvote" and p.type == "normal" and not p.removed,
        select: {l.profile_id, l.post_id}
    )
    |> Enum.each(fn {profile_id, post_id} ->
      MeliGraph.insert_edge(
        :feed,
        "profile:#{profile_id}",
        "post:#{post_id}",
        :like,
        @weights.like
      )
    end)

    # Posts normais — comentários (sinal mais forte)
    Repo.all(
      from c in Comment,
        join: p in Post, on: p.id == c.post_id,
        where: not c.removed and p.type == "normal" and not p.removed,
        select: {c.profile_id, c.post_id}
    )
    |> Enum.each(fn {profile_id, post_id} ->
      MeliGraph.insert_edge(
        :feed,
        "profile:#{profile_id}",
        "post:#{post_id}",
        :comment,
        @weights.comment
      )
    end)

    # Reviews de professor (posts type=sobre_professor) — likes
    Repo.all(
      from l in Like,
        join: p in Post, on: p.id == l.post_id,
        where: l.like_type == "upvote" and p.type == "sobre_professor" and not p.removed,
        select: {l.profile_id, l.post_id}
    )
    |> Enum.each(fn {profile_id, post_id} ->
      MeliGraph.insert_edge(
        :feed,
        "profile:#{profile_id}",
        "review:#{post_id}",
        :like,
        @weights.like
      )
    end)

    # Ads — cliques (sinal mais forte de todos)
    Repo.all(from c in Click, select: {c.profile_id, c.ad_id})
    |> Enum.each(fn {profile_id, ad_id} ->
      MeliGraph.insert_edge(
        :feed,
        "profile:#{profile_id}",
        "ad:#{ad_id}",
        :click,
        @weights.click
      )
    end)
  end
end

# Job noturno: treina embeddings e persiste o binary
defmodule MyApp.NightlyTrain do
  def run do
    MyApp.GraphIngestion.rebuild_graph!()

    {:ok, binary} = MeliGraph.train_embeddings(:feed,
      user_prefix: "profile:",
      embedding_dim: 64,
      layers: 3,
      epochs: 1_000
    )

    Repo.insert!(%GraphEmbedding{
      graph_name: "feed",
      data: binary,
      trained_at: DateTime.utc_now()
    })

    :ok = MeliGraph.load_embeddings(:feed, binary)
  end
end

# Endpoint do feed
def get_feed(profile_id) do
  {:ok, recs} = MeliGraph.recommend(:feed, "profile:#{profile_id}", :content,
    algorithm: :lightgcn, top_k: 50)

  # Cada rec é {namespaced_id, score}. O caller resolve o tipo pelo prefixo:
  Enum.map(recs, fn {item_id, score} ->
    case String.split(item_id, ":", parts: 2) do
      ["post", id]   -> {:post, String.to_integer(id), score}
      ["review", id] -> {:review, String.to_integer(id), score}
      ["ad", id]     -> {:ad, String.to_integer(id), score}
    end
  end)
end

Pontos importantes:

IDs colidem entre tabelas (posts.id = 42 e ads.id = 42 coexistem). O namespacing (post:42, ad:42) resolve isso e é a chave que aparece no resultado de recommend/4 — o caller decompõe pelo prefixo.
Ranking misto: o feed final mistura naturalmente os três tipos conforme o sinal histórico do usuário. Se quiser garantir presença mínima de cada tipo, faça pós-filtragem no caller (ex.: pegar top-20 posts, top-10 reviews, top-5 ads do resultado).
Cold start: usuário sem interações cai no fallback SALSA — que por sua vez precisa de pelo menos algum vizinho. Para anônimos, use algorithm: :global_rank direto.
Frequência de treino: ads entram/saem rápido. Considere treino diário + stream de inserções incremental no grafo (próximo treino reaprende). Retreino incremental fica para v0.3.

Configuração

MeliGraph.start_link(
  name: :my_graph,                         # obrigatório
  graph_type: :bipartite,                  # obrigatório (:directed | :bipartite)
  segment_max_edges: 1_000_000,            # arestas por segmento
  segment_ttl: :timer.hours(24),           # TTL dos segmentos
  result_ttl: :timer.minutes(30),          # TTL do cache
  testing: :disabled,                      # :disabled | :sync
  plugins: [
    {MeliGraph.Plugins.Pruner, interval: :timer.minutes(5)},
    {MeliGraph.Plugins.CacheCleaner, interval: :timer.minutes(1)}
  ]
)

Telemetry

Eventos emitidos para observabilidade:

[:meli_graph, :ingestion, :insert_edge, :start | :stop | :exception]
[:meli_graph, :query, :recommend, :start | :stop | :exception]
[:meli_graph, :graph, :create_segment, :start | :stop | :exception]
[:meli_graph, :plugin, :prune, :start | :stop | :exception]
[:meli_graph, :plugin, :cache_clean, :start | :stop | :exception]

Testes

# Testes unitários (sem dependências externas)
mix test

181 tests, 0 failures, 37 excluded (integration)

Veja docs/testing.md para testes de integração com dados reais.

Documentação Técnica

Arquitetura — Camadas, supervision tree e fluxo de dados
Graph Storage — Segmentação temporal, ETS e ID mapping
Estruturas de Dados — Cada estrutura usada, justificativa e trade-offs
Algoritmos — PageRank, SALSA, extensibilidade
LightGCN (v0.2) — Arquitetura, fluxo de treino, dependências e validação empírica
Plano LightGCN v0.2 — Plano de implementação fase a fase
Padrões OTP — Config struct, Registry, plugins, telemetry
Testing — Modo :sync, helpers, exemplos de testes
API Reference — Referência completa da API pública

Estrutura do Projeto

lib/
├── meli_graph.ex                    # API pública
├── meli_graph/
│   ├── config.ex                    # Config struct centralizado
│   ├── config_holder.ex             # Registra config no Registry
│   ├── registry.ex                  # Registry helpers
│   ├── supervisor.ex                # Supervision tree
│   ├── telemetry.ex                 # Telemetry spans
│   ├── graph/
│   │   ├── edge.ex                  # Struct de aresta
│   │   ├── id_map.ex                # Mapeamento de IDs
│   │   ├── segment.ex               # Segmento temporal
│   │   └── segment_manager.ex       # Gerenciador de segmentos
│   ├── ingestion/
│   │   └── writer.ex                # Single-writer + graceful shutdown
│   ├── algorithm/
│   │   ├── algorithm.ex             # Behaviour genérico
│   │   ├── pagerank.ex              # Monte Carlo random walks
│   │   ├── salsa.ex                 # Subgraph SALSA
│   │   ├── similar_items.ex         # Co-ocorrência 2-hop (Jaccard/Cosine)
│   │   ├── global_rank.ex           # Ranking global por in-degree
│   │   └── lightgcn.ex              # Inferência via dot product (v0.2)
│   ├── lightgcn/                    # v0.2 — embeddings aprendidos
│   │   ├── matrix.ex                # Ã = D^(-1/2)·A·D^(-1/2) via Nx
│   │   ├── trainer.ex               # BPR loss + Adam em defn
│   │   └── embedding_store.ex       # Ciclo de vida do payload no ETS
│   ├── query/
│   │   └── query.ex                 # Cache-first + fallback :lightgcn → :salsa
│   ├── store/
│   │   ├── store.ex                 # Store behaviour
│   │   └── ets.ex                   # ETS + TTL (numérico ou :infinity)
│   └── plugins/
│       ├── plugin.ex                # Plugin behaviour
│       ├── pruner.ex                # Remove segmentos expirados
│       ├── cache_cleaner.ex         # TTL cleanup
│       └── supervisor.ex            # Supervisor dos plugins
test/
├── meli_graph_test.exs              # Testes de integração da API pública
├── meli_graph/                      # Testes unitários por módulo
│   ├── config_test.exs
│   ├── registry_test.exs
│   ├── telemetry_test.exs
│   ├── graph/
│   ├── ingestion/
│   ├── algorithm/
│   ├── query/
│   ├── store/
│   └── plugins/
├── integration/                     # Testes com dados reais (tag :integration)
│   ├── dataset_stats_test.exs       # Valida integridade dos CSVs
│   ├── follows_graph_test.exs       # Who to Follow com dados reais
│   ├── likes_graph_test.exs         # Feed de recomendações com dados reais
│   └── professors_graph_test.exs    # Recomendação de professores (SALSA, SimilarItems, GlobalRank)
└── support/
    ├── graph_helpers.ex             # Helpers para testes unitários
    └── dataset_loader.ex            # Carrega CSVs de produção
tmp/
├── meli_graph_follows.csv              # Exportado do banco (não versionado)
├── meli_graph_likes.csv
├── meli_graph_posts.csv
├── meli_graph_professors.csv           # Metadados dos professores
├── meli_graph_professor_ratings.csv    # Avaliações profile → professor
└── meli_graph_professor_posts.csv      # Posts sobre professores

Roadmap

v0.1

[x] Config struct + Registry + Supervisor
[x] Graph storage com ETS + segmentação temporal
[x] ID mapping global
[x] Single-writer ingestion + graceful shutdown
[x] PageRank Personalizado (Monte Carlo)
[x] SALSA (Subgraph)
[x] SimilarItems (co-ocorrência 2-hop com Jaccard/Cosine)
[x] GlobalRank (ranking global por in-degree)
[x] Store ETS com TTL
[x] Query layer (sync + cache) com suporte a algoritmos globais
[x] Plugin system (Pruner + CacheCleaner)
[x] Telemetry spans
[x] Modo de testing :sync

v0.2 — LightGCN

[x] Store.ETS com TTL :infinity (embeddings nunca expiram por tempo)
[x] LightGCN.Matrix — Ã = D^(-1/2)·A·D^(-1/2) via Nx
[x] LightGCN.Trainer — BPR loss + Adam manual em defn, autodiff via value_and_grad
[x] LightGCN.EmbeddingStore — ciclo de vida no ETS, payload validado
[x] Algorithm.LightGCN — inferência via dot product
[x] Query — fallback transparente para SALSA quando embeddings não estão prontos
[x] API pública: train_embeddings/2, load_embeddings/2, embeddings_ready?/1
[x] EXLA opcional para JIT do trainer (treino Gowalla 500u/100ep em ~99s)
[x] Validação empírica no dataset Gowalla do paper (recall@20 18.6× acima de random)
[x] 181 testes unitários (94 → 181, +87 desde v0.1)

v0.2.1 (atual) — Pesos + Nx obrigatório

[x] Campo weight :: float() em MeliGraph.Graph.Edge (default 1.0)
[x] MeliGraph.insert_edge/5 aceita peso opcional
[x] Segment armazena {src, dst, type, weight} em ETS (tabela :bag)
[x] LightGCN.Matrix constrói Ã = D^(-1/2)·W·D^(-1/2) ponderada
[x] Pesos somam quando múltiplas arestas conectam o mesmo par (u, i)
[x] :nx agora é dependência obrigatória do hex (era optional)
[x] :exla segue opcional, com Logger.warning no primeiro treino sem ele
[x] Algoritmos legados (PageRank, SALSA, SimilarItems, GlobalRank) — comportamento idêntico (ignoram peso)
[x] 183 testes unitários (181 → 183, +2 cobertura de pesos no Matrix)

Breaking changes (v0.2.0 → v0.2.1)

MeliGraph.insert_edge/4 → /5 com weight opcional. Chamadas antigas (insert_edge(name, src, dst, type)) seguem funcionando — o peso default é 1.0.
MeliGraph.neighbors_*/2 retornam {id, type, weight} (era {id, type}). Quem desestruturava a tupla precisa adicionar _weight.
insert_edge não é mais idempotente do ponto de vista do LightGCN — inserir o mesmo par duas vezes soma pesos. Em v0.2.0 era deduplicado.
:nx virou dep obrigatória. Quem usava meli_graph só para PageRank e listava {:nx, ..., optional: true} pode remover essa linha.

v0.3 (planejado)

[ ] Matriz sparse no LightGCN (escalar para grafos > 50k nós)
[ ] Retreinamento incremental (warm start)
[ ] Pesos respeitados por PageRank (random walk ponderado) e SALSA
[ ] PageRank via Nx power method
[ ] Sonar (health check do Writer) + Backpressure
[ ] Precomputer plugin

v0.4 (futuro)

[ ] Peer behaviour + distribuição
[ ] Algoritmos adicionais (Node2Vec)

Referências

Gupta et al., "WTF: The Who to Follow Service at Twitter", WWW 2013
Sharma et al., "GraphJet: Real-Time Content Recommendations at Twitter", VLDB 2016
Lempel & Moran, "SALSA: The Stochastic Approach for Link-Structure Analysis", ACM TOIS 2001
Fogaras et al., "Towards Scaling Fully Personalized PageRank", Internet Mathematics 2005
Page et al., "The PageRank Citation Ranking", Stanford 1999

Licença

Veja LICENSE.

Next Page → LICENSE