Coarsening disassortative graphs

Many real-world applications require us to study large-scale graphs which are computationally expensive to process and difficult to understand intuitively.

To solve this issue, graph coarsening (or, sometimes, "pooling") techniques allow us to reduce the size of a graph while preserving its overall characteristics. Many works have been proposed recently to tackle this problem, especially in the field of graph neural networks, but it remains a challenging and open research direction.

Most techniques for graph coarsening assume that the input graph is assortative, that is, a graph in which neighboring nodes are likely to be similar. Conversely, many real-world graphs are disassortative graphs in which connections are heterophilous.
For example, scale-free graphs (in which nodes with small degree are likely to be connected to nodes with a high degree) are very frequent in nature and technology.

In this project, we will attempt to develop a coarsening algorithm for strongly disassortative graphs. This will require us to discard many assumptions that are usually exploited in the design of coarsening algorithms, and chiefly the assumption that clusters of nodes can be identified in densely connected communities.

First, we will study the effect of typical coarsening algorithms when applied to disassortative graphs. Then, we will formulate our coarsening problem as an optimization to obtain a desired degree of disassortativity in the coarse graph. Finally, we will identify one or more solutions to the problem, either through procedural techniques or end-to-end learning.

Project timezone: C