Powerful Learning Models for Graphs and Hypergraphs

In practice, depending on the type of data at hand and the problem at hand, often we need to design suitable neural architecture to produce efficient and effective learning models. Many practical problems from our use-domains operate on (hyper-)graph types of data. Wang’s team has explored the following:

Graph transformer type of models have been considered to be better at capturing long range interaction. However, transformer is originally just a sequence-to-sequence permutation-equivariant map, and one has to inject the “graph information” via some sort of position encoding. Two common ways of position encodings are: absolute position encoding (APE) where graph information is encoded at the node level, and relative position encoding (RPE) where graph information is encoded as a 2-tensor (for each pair of nodes) and used to augment the attention. In [Black et al., ICML 2024], Wang and collaborators showed relative pros/cons and relations of these two types of PEs. The observations can help guide model selection for future tasks. In a related work, [Cai, Yu & Wang, AISTATS 2024], Wang and collaborators also explore higher-order sparse graph transformers to be able to capture relations among multiple nodes.

In joint work with Qualcomm, Wang’s team combined several theoretical insights from graph neural networks, as well as topological methods, to develop an effective learning model for property prediction of circuit netlists (from Chip Design) ([Luo et al., AISTATS 2024]). Interestingly, this work is also based on our theoretical understanding of universal representation of permutation invariant function on vectors (sets) and tensors (hypergraphs) ([Tabaghi & Wang, ALT 2024]).