Equivariant poset representations

Dr Shubhendu Trivedi

Leonardo Cotta

Abstract

g28.png

Partially-ordered data is pervasive across a wide range of domains: from online user forums, to natural language understanding, to computer programs and, to bioinformatics. To develop successful applications in these domains, we need to learn representations mapping a hierarchy to a meaningful vector space. Partially ordered sets (posets) are combinatorial objects encoding such hierarchies. Despite the recent plethora of works on equivariant representations for other combinatorial structures, such as graphs and sets, posets have been consistently neglected in this context. In this project we will first discuss learning equivariant representations over combinatorial structures in general and then posets in particular. As a first model we will consider representing the poset as a Directed Acyclic Graph (DAG) and applying a Graph Neural Network (GNN) over it. We will then show how the DAG view does not explicitly encode all known aspects of a poset. Instead, we will consider applying a GNN over the poset zeta matrix (the analogous of the adjacency matrix for a poset). Finally, we will explore non-GNN-based equivariant architectures for representing posets. We will take inspiration from related notions of convolution over powersets to motivate the development of such a machinery.