Research map / Graph learning / Graph algorithms and clustering

UGC: Universal Graph Coarsening

NeurIPS 2024 · Graph learning › Graph algorithms and clustering · approach: Graph distance and retrieval · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes UGC, a hashing-based (LSH) graph coarsening framework that uses heterophily-weighted augmented node features and adjacency vectors to build a coarsening matrix in linear time, supporting both homophilic and heterophilic graphs.

Problem

Graph coarsening for large graphs preserving spectral properties and epsilon-similarity, which existing methods handle poorly for heterophilic graphs and which are computationally expensive.

Approach

Augment each node's feature vector with its adjacency vector weighted by a heterophily factor, then use p-stable locality-sensitive hashing to assign nodes to super-nodes, decoupling mapping learning from adjacency aggregation (Ac = C^T A C), with an optional closed-form feature re-learning step for tighter epsilon bounds.

Key results

• UGC is reported as 4x to 15x faster than existing coarsening methods, e.g., about 6x faster than the fastest baseline on Physics and 9x on Squirrel.
• At a 50% coarsening ratio, UGC gives the best relative eigen error on 8 of 12 datasets (Table 2).
• With GCN trained on a 50%-coarsened graph, UGC reaches 86.30% on Cora and 31.62% on Squirrel, outperforming baselines on 7 of 9 datasets (Table 4).

Measured effects reported in the paper

Surprising findings

• Coarsening with the augmented features gives large gains on heterophilic graphs such as Squirrel (31.62% vs about 20% for baselines) and Chameleon (48.7% vs about 33%).
• On Physics, GCN accuracy with UGC at 50% coarsening (96.12%) exceeds the accuracy reported in the baselines' table, though accuracy drops at 70% on some datasets.

Limitations

• Concatenating adjacency vectors makes augmented feature vectors long for large graphs, requiring sparse implementations.
• Coarsened-graph GNN accuracy declines as the coarsening ratio increases (e.g., at 70%), so there is a trade-off between compression and quality.
• Bin-width must be tuned per dataset to hit a target coarsening ratio, and the paper explores only one hash family.

Experimental setup

Datasets: Cora Citeseer PubMed CS Physics DBLP Flickr Yelp Reddit Squirrel Chameleon Cornell

Benchmarks: Cora Citeseer PubMed CS Physics DBLP Flickr Reddit Yelp Squirrel Chameleon Cornell

Metrics: running time relative eigen error hyperbolic error epsilon-similarity node classification accuracy

Baselines: Variation Neighborhoods Variation Edges Variation Cliques Heavy Edge Matching Algebraic Distance Affinity GS Kron reduction GCond SFGC

Builds on: Locality Sensitive Hashing spectral graph coarsening (Loukas) FGC GCN

Closest papers by meaning

• A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening (NeurIPS 2019 · similarity 0.88)
• Taxonomy of reduction matrices for Graph Coarsening (NeurIPS 2025 · similarity 0.86)
• Revisiting, Benchmarking and Understanding Unsupervised Graph Domain Adaptation (NeurIPS 2024 · similarity 0.86)
• Smoothness Really Matters: A Simple Yet Effective Approach for Unsupervised Graph Domain Adaptation (AAAI 2025 · similarity 0.86)
• Beyond Redundancy: Information-aware Unsupervised Multiplex Graph Structure Learning (NeurIPS 2024 · similarity 0.85)
• Structure-Aware Spectral Sparsification via Uniform Edge Sampling (NeurIPS 2025 · similarity 0.85)