Pesquisadores estão se voltando para a matemática das interações de ordem superior para modelar melhor as conexões complexas em seus dados.
A teoria dos grafos não é suficiente.
A linguagem matemática para falar sobre conexões, que geralmente depende de redes – vértices (pontos) e arestas (linhas que os conectam) – tem sido uma forma inestimável de modelar fenômenos do mundo real desde pelo menos o século XVIII. Mas, algumas décadas atrás, o surgimento de conjuntos de dados gigantescos forçou os pesquisadores a expandir suas caixas de ferramentas e, ao mesmo tempo, deu-lhes amplas caixas de areia para aplicar novos insights matemáticos. Desde então, disse Josh Grochow, cientista da computação da Universidade do Colorado, em Boulder, tem havido um período emocionante de rápido crescimento, à medida que os pesquisadores desenvolveram novos tipos de modelos de rede que podem encontrar estruturas e sinais complexos no ruído de big data.
Grochow está entre um coro crescente de pesquisadores que apontam que, quando se trata de encontrar conexões em big data, a teoria dos gráficos tem seus limites. Um gráfico representa cada relacionamento como uma díade, ou interação entre pares. No entanto, muitos sistemas complexos não podem ser representados apenas por conexões binárias. O progresso recente no campo mostra como seguir em frente.
Considere tentar forjar um modelo de rede de paternidade. Claramente, cada pai tem uma conexão com um filho, mas o relacionamento dos pais não é apenas a soma dos dois links, como a teoria dos gráficos pode modelar. O mesmo vale para tentar modelar um fenômeno como a pressão dos pares.
“Existem muitos modelos intuitivos. O efeito da pressão dos pares na dinâmica social só é capturado se você já tiver grupos em seus dados”, disse Leonie Neuhäuser, da RWTH Aachen University, na Alemanha. Mas as redes binárias não capturam as influências do grupo.
Matemáticos e cientistas da computação usam o termo “interações de ordem superior” para descrever essas formas complexas pelas quais a dinâmica de grupo, em vez de ligações binárias, pode influenciar o comportamento individual. Esses fenômenos matemáticos aparecem em tudo, desde as interações de emaranhamento na mecânica quântica até a trajetória de uma doença que se espalha pela população. Se um farmacologista quisesse modelar interações medicamentosas, por exemplo, a teoria dos gráficos poderia mostrar como dois medicamentos respondem um ao outro – mas e três? Ou quatro?
Embora as ferramentas para explorar essas interações não sejam novas, foi apenas nos últimos anos que os conjuntos de dados de alta dimensão se tornaram um motor de descoberta, dando aos matemáticos e teóricos de rede novas ideias. Esses esforços produziram resultados interessantes sobre os limites dos gráficos e as possibilidades de aumento de escala.
“Agora sabemos que a rede é apenas a sombra da coisa”, disse Grochow. Se um conjunto de dados tem uma estrutura subjacente complexa, modelá-lo como um gráfico pode revelar apenas uma projeção limitada de toda a história.
“Percebemos que as estruturas de dados que usamos para estudar as coisas, de uma perspectiva matemática, não se encaixam muito bem no que vemos nos dados”, disse a matemática Emilie Purvine, do Pacific Northwest National Laboratory.
É por isso que matemáticos, cientistas da computação e outros pesquisadores estão cada vez mais se concentrando em maneiras de generalizar a teoria dos grafos – em suas várias formas – para explorar fenômenos de ordem superior. Os últimos anos trouxeram uma torrente de maneiras propostas para caracterizar essas interações e verificá-las matematicamente em conjuntos de dados de alta dimensão.
Para Purvine, a exploração matemática das interações de ordem superior é como o mapeamento de novas dimensões. “Pense em um gráfico como a base de um terreno bidimensional”, disse ela. Os edifícios tridimensionais que podem ser colocados no topo podem variar significativamente. “Quando você está no nível do solo, eles parecem iguais, mas o que você constrói no topo é diferente.”
Entrar no hipergrafo
A busca por essas estruturas de dimensões superiores é onde a matemática se torna especialmente turva – e interessante. O análogo de ordem superior de um gráfico, por exemplo, é chamado de hipergrafo e, em vez de arestas, possui “hipergramas”. Eles podem conectar vários nós, o que significa que podem representar relacionamentos de múltiplas vias (ou multilineares). Em vez de uma linha, uma hipercarga pode ser vista como uma superfície, como uma lona fixada em três ou mais lugares.
O que é bom, mas ainda há muito que não sabemos sobre como essas estruturas se relacionam com suas contrapartes convencionais. Os matemáticos estão atualmente aprendendo quais regras da teoria dos grafos também se aplicam a interações de ordem superior, sugerindo novas áreas de exploração.
Para ilustrar os tipos de relacionamento que um hipergrafo pode extrair de um grande conjunto de dados – e um gráfico comum não pode -, Purvine aponta para um exemplo simples perto de casa, o mundo da publicação científica. Imagine dois conjuntos de dados, cada um contendo artigos em coautoria de até três matemáticos; para simplificar, vamos chamá-los de A, B e C. Um conjunto de dados contém seis artigos, com dois artigos de cada um dos três pares distintos (AB, AC e BC). O outro contém apenas dois artigos no total, cada um com a co-autoria dos três matemáticos (ABC).
Uma representação gráfica da coautoria, retirada de qualquer conjunto de dados, pode parecer um triângulo, mostrando que cada matemático (três nós) colaborou com os outros dois (três links). Se sua única pergunta fosse quem colaborou com quem, então você não precisaria de um hipergrafo, disse Purvine
Mas se você tivesse um hipergrafo, também poderia responder a perguntas sobre estruturas menos óbvias. Um hipergrafo do primeiro conjunto (com seis artigos), por exemplo, poderia incluir hiperviscos mostrando que cada matemático contribuiu para quatro artigos. Uma comparação dos hipergrafos dos dois conjuntos mostraria que os autores dos artigos diferiram no primeiro conjunto, mas eram os mesmos no segundo.
Hipergrafos em estado selvagem
Esses métodos de ordem superior já se mostraram úteis em pesquisas aplicadas, como quando ecologistas mostraram como a reintrodução de lobos no Parque Nacional de Yellowstone na década de 1990 desencadeou mudanças na biodiversidade e na estrutura da cadeia alimentar. E em um artigo recente, Purvine e seus colegas analisaram um banco de dados de respostas biológicas a infecções virais, usando hipergrafos para identificar os genes mais críticos envolvidos. Eles também mostraram como essas interações teriam sido perdidas pela análise de pares usual fornecida pela teoria dos grafos.
“Esse é o tipo de poder que vemos nos hipergrafos, para ir além dos gráficos”, disse Purvine.
No entanto, generalizar de gráficos para hipergrafos fica rapidamente complicado. Uma maneira de ilustrar isso é considerar o problema do corte canônico da teoria dos grafos, que pergunta: Dados dois nós distintos em um gráfico, qual é o número mínimo de arestas que você pode cortar para cortar completamente todas as conexões entre os dois? Muitos algoritmos podem encontrar prontamente o número ideal de cortes para um determinado gráfico.
Mas que tal cortar um hipergrafo? “Há muitas maneiras de generalizar essa noção de corte para um hipergrafo”, disse Austin Benson, um matemático da Universidade Cornell. Mas não há uma solução clara, disse ele, porque uma hyperedge pode ser cortada de várias maneiras, criando novos grupos de nós.
Junto com dois colegas, Benson recentemente tentou formalizar todas as diferentes maneiras de dividir um hipergrafo. O que eles descobriram indicava uma variedade de complexidades computacionais: para algumas situações, o problema foi prontamente resolvido em tempo polinomial, o que basicamente significa que um computador poderia processar soluções em um tempo razoável. Mas para outros, o problema era basicamente insolúvel – era impossível saber com certeza se uma solução existia.
“Ainda há muitas questões em aberto”, disse Benson. “Alguns desses resultados de impossibilidade são interessantes porque você não pode reduzi-los a gráficos. E do lado da teoria, se você não reduziu a algo que poderia ter encontrado com um gráfico, isso está mostrando que há algo novo lá.”
O Sanduíche Matemático
Mas o hipergrafo não é a única maneira de explorar interações de ordem superior. Topologia – o estudo matemático de propriedades geométricas que não mudam quando você estica, comprime ou transforma objetos – oferece uma abordagem mais visual. Quando um topólogo estuda uma rede, ele procura formas, superfícies e dimensões. Eles podem notar que a borda que conecta dois nós é unidimensional e perguntar sobre as propriedades de objetos unidimensionais em redes diferentes. Ou eles podem ver a superfície triangular bidimensional formada pela conexão de três nós e fazer perguntas semelhantes.
Os topologistas chamam essas estruturas de complexos simpliciais. Esses são, efetivamente, hipergrafos visualizados por meio da estrutura da topologia. As redes neurais, que se enquadram na categoria geral de aprendizado de máquina, oferecem um exemplo revelador. Eles são conduzidos por algoritmos projetados para imitar como os neurônios do nosso cérebro processam as informações. Redes neurais gráficas (GNNs), que modelam conexões entre coisas como conexões de pares, são excelentes para inferir dados que estão faltando em grandes conjuntos de dados, mas, como em outras aplicações, podem perder interações que surgem apenas de grupos de três ou mais. Nos últimos anos, os cientistas da computação desenvolveram redes neurais simples, que usam complexos de ordem superior para generalizar a abordagem de GNNs para encontrar esses efeitos.
Complexos simples conectam a topologia à teoria dos grafos e, como os hipergrafos, levantam questões matemáticas convincentes que irão conduzir a investigações futuras. Por exemplo, em topologia, tipos especiais de subconjuntos de complexos simpliciais também são complexos simpliciais e, portanto, têm as mesmas propriedades. Se o mesmo fosse verdadeiro para um hipergrafo, os subconjuntos incluiriam todos os hipergramas dentro – incluindo todas as arestas bidirecionais incorporadas.
Mas nem sempre é o caso. “O que estamos vendo agora é que os dados caem neste meio-termo, onde nem todo hyperedge, nem toda interação complexa, tem o mesmo tamanho que todos os outros”, disse Purvine. “Você pode ter uma interação de três vias, mas não as interações de pares.” Os conjuntos de big data mostraram claramente que a influência do grupo muitas vezes supera a influência de um indivíduo, seja em redes de sinalização biológica ou em comportamentos sociais, como a pressão dos pares.
Purvine descreve os dados como preenchendo o meio de uma espécie de sanduíche matemático, limitado por cima por essas idéias da topologia e por baixo pelas limitações dos gráficos. Os teóricos de redes agora são desafiados a encontrar as novas regras para interações de ordem superior. E para os matemáticos, ela disse, “há espaço para brincar”.
Caminhadas aleatórias e matrizes
Esse senso de “jogo” criativo se estende a outras ferramentas também. Existem todos os tipos de belas conexões entre gráficos e outras ferramentas para descrever dados, disse Benson. “Mas assim que você muda para a configuração de ordem superior, essas conexões são mais difíceis de encontrar.”
Isso fica especialmente claro quando você tenta considerar uma versão de dimensão superior de uma cadeia de Markov, disse ele. Uma cadeia de Markov descreve um processo de vários estágios em que o próximo estágio depende apenas da posição atual de um elemento; pesquisadores usaram modelos de Markov para descrever como coisas como informação, energia e até mesmo dinheiro fluem através de um sistema. Talvez o exemplo mais conhecido de uma cadeia de Markov seja um passeio aleatório, que descreve um caminho onde cada etapa é determinada aleatoriamente a partir da anterior. Um passeio aleatório também é um gráfico específico: qualquer passeio ao longo de um gráfico pode ser mostrado como uma sequência que se move de um nó para outro ao longo de links.
Mas como escalar algo tão simples como uma caminhada? Os pesquisadores recorrem às cadeias de Markov de ordem superior, que, em vez de depender apenas da posição atual, podem considerar muitos dos estados anteriores. Essa abordagem se mostrou útil para modelar sistemas como comportamento de navegação na web e fluxos de tráfego de aeroportos. Benson tem ideias de outras maneiras de estendê-lo: ele e seus colegas descreveram recentemente um novo modelo para processos estocásticos, ou aleatórios, que combina cadeias de Markov de ordem superior com outra ferramenta chamada tensores. Eles o testaram em comparação com um conjunto de dados de viagens de táxi na cidade de Nova York para ver o quão bem ele poderia prever trajetórias. Os resultados foram mistos: seu modelo previu o movimento das cabines melhor do que uma corrente de Markov normal, mas nenhum dos modelos era muito confiável.
Os próprios tensores representam mais uma ferramenta para estudar as interações de ordem superior que se destacou nos últimos anos. Para entender os tensores, primeiro pense em matrizes, que organizam os dados em uma matriz de linhas e colunas. Agora imagine matrizes feitas de matrizes, ou matrizes que possuem não apenas linhas e colunas, mas também profundidade ou outras dimensões de dados. Esses são tensores. Se cada matriz correspondesse a um dueto musical, então os tensores incluiriam todas as configurações possíveis de instrumentos.
Tensores não são novidade para os físicos, que há muito os usam para descrever, por exemplo, os diferentes estados quânticos possíveis de uma partícula, mas os teóricos da rede adotaram essa ferramenta para expandir o poder das matrizes em conjuntos de dados de alta dimensão. E os matemáticos os estão usando para descobrir novas classes de problemas. Grochow usa tensores para estudar o problema do isomorfismo, que essencialmente pergunta como você sabe se dois objetos são, de alguma forma, iguais. Seu trabalho recente com Youming Qiao produziu uma nova maneira de identificar problemas complexos que podem ser difíceis ou impossíveis de resolver.
Como hipergrafar com responsabilidade
O modelo de táxi inconclusivo de Benson levanta uma questão abrangente: quando os pesquisadores realmente precisam de ferramentas como hipergrafos? Em muitos casos, sob as condições certas, um hipergrafo fornecerá exatamente o mesmo tipo de previsões e análises que um gráfico. “Se algo já está encapsulado na rede, é realmente necessário modelar o sistema [como de ordem superior]?” perguntou Michael Schaub da RWTH Aachen University.
Depende do conjunto de dados, disse ele. “Um gráfico é uma boa abstração para uma rede social, mas as redes sociais são muito mais. Com sistemas de ordem superior, existem mais maneiras de modelar.” A teoria dos gráficos pode mostrar como os indivíduos estão conectados, por exemplo, mas não capturar as maneiras pelas quais grupos de amigos nas redes sociais influenciam o comportamento uns dos outros.
As mesmas interações de ordem superior não surgirão em todos os conjuntos de dados, então novas teorias são, curiosamente, impulsionadas pelos dados – o que desafia o sentido lógico subjacente que atraiu Purvine para o campo em primeiro lugar. “O que adoro na matemática é que se baseia na lógica e, se você seguir a direção certa, terá a resposta certa. Mas às vezes, quando você está definindo áreas totalmente novas da matemática, há essa subjetividade de qual é a maneira certa de fazer isso”, diz ela. “E se você não reconhece que existem várias maneiras de fazer isso, você pode levar a comunidade na direção errada.”
Em última análise, disse Grochow, essas ferramentas representam uma espécie de liberdade, não apenas permitindo que os pesquisadores entendam melhor seus dados, mas permitindo que matemáticos e cientistas da computação explorem novos mundos de possibilidades. “Há uma infinidade de coisas para explorar. É interessante e bonito, e uma fonte de muitas perguntas excelentes.”
Publicado em 21/08/2021 10h39
Artigo original:
Achou importante? Compartilhe!