Skip to yearly menu bar Skip to main content


Poster

UGC: Universal Graph Coarsening

Mohit Kataria · Sandeep Kumar · Jayadeva Dr

[ ] [ Project Page ]
Fri 13 Dec 4:30 p.m. PST — 7:30 p.m. PST

Abstract: In the era of big data, graphs have emerged as a natural representation of intricate relationships. However, graph sizes often become unwieldy, leading to storage, computation, and analysis challenges. A crucial demand arises for methods that can effectively downsize large graphs while retaining vital insights. Graph coarsening seeks to simplify large graphs while maintaining essential features. Most published methods are suitable for homophilic datasets, limiting their universal use. We propose **U**niversal **G**raph **C**oarsening (UGC), a framework equally suitable for homophilic and heterophilic datasets. UGC integrates node attributes and adjacency information, leveraging the dataset's heterophily factor. Results on benchmark datasets demonstrate that UGC preserves spectral similarity while coarsening. In comparison to existing methods, UGC is 4$\times$ to 15$\times$ faster, has lower eigen-error, and yields superior performance on downstream processing tasks even at 70% coarsening ratios.

Live content is unavailable. Log in and register to view live content