Graph Coarsening

Follow this topic Ask about this topic

Graph coarsening groups vertices or contracts edges to create a smaller graph, making learning and optimization on large networks more manageable. Methods include heuristic and learned clustering, spectral and geometric approaches, and task-specific graph minors; coarsened graphs are used with GNNs, recommendation systems, segmentation, and combinatorial optimization. Evaluation spans node-classification benchmarks, large real-world networks, and application-specific tasks, with goals such as lower memory and runtime or preserved predictive accuracy. The central tension is that compression can discard task-relevant structure: preserving signal propagation may increase smoothing, while sparsification may retain signal diversity but alter propagation, and the right trade-off depends on the task and graph.

Latest papers

19 papers2 papers in the last four weeks, down 33% on the four weeks before. 0.0% of all new papers.

Score-Based Learning of Cluster DAGs from Interventions
Oct 8, 2026Gaetano Tedesco, Alex MarkhamScore-Based Causal Discovery Causal Structure Learning
Informatics Institute, University of Amsterdam · Department of Mathematical Sciences, University of Copenhagen
Aggregating User Preferences while Ensuring Equity, Diversity, and Inclusion using Graph Summarization
Oct 5, 2026Adji Marieme Sita Cissé, Malek MouhoubGroup Fairness Rank Aggregation
Université Paris-Saclay, UVSQ, France · Department of Computer Science, University of Regina, Regina, SK, Canada
Dual-GNN Multilevel Coarsening for Maximum Independent Set
Sep 21, 2026Tianfeng Chen, Xianyue LiGraph Coarsening Combinatorial Optimization
School of Mathematics and Statistics Lanzhou University
Geometric Flow enhanced Graph Coarsening
Sep 14, 2026Chaoqun Fei, Guoxuan Li, Tinglve Zhou +2Graph Neural Networks Graph Coarsening
School of Artificial Intelligence, South China Normal University, Foshan 528225, China · State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China
GNN-Guided Graph Coarsening and Adaptive QUBO Penalties for the Capacitated Vehicle Routing Problem with Time Windows on a Quantum Annealer
Sep 4, 2026Youssef Kamel Rezk, Paweł GoraQuantum Annealing Graph Coarsening
Alamein International University, Alamein, Egypt · Jagiellonian University, Kraków, Poland · Fundacja Quantum AI, Warsaw, Poland
CoRe-GNN: Multilevel Message passing on Coarsened graphs
Aug 3, 2026Antonin Joly, Nicolas Keriven, Aline RoumyGraph Neural Networks Graph Coarsening
CNRS, IRISA, Rennes, FRANCE · INRIA, Rennes, FRANCE
Train Small, Deploy Large: Zero-Shot GNN Transfer Through Geometric Renormalization
Jul 30, 2026Robert Jankowski, Pedro Almagro-Blanco, Marián Boguñá +2Zero-Shot Learning Graph Neural Networks
TU Delft · University of Seville · University of Barcelona +2
Does Graph Compression Preserve Signal Propagation?
Jul 25, 2026Kawshik Banerjee, Khaled Mohammed SaifuddinGraph Signal Processing Graph Coarsening
School of Computing, Southern Illinois University, Carbondale, IL, USA
Efficient Recommendations via Graph Coarsening and Label Propagation
Jul 24, 2026Alessandro Sbandi, Federico Siciliano, Fabrizio SilvestriGraph Coarsening Recommender Systems
Sapienza University of Rome, Rome, Italy · TIM S.p.A.
Remedying Coarsening-Based GNN Training under Heterophily via Adaptive Complementary Enhancement
Jul 24, 2026Guoming Li, Jian Yang, Xukun Wang +3Graph Neural Networks Graph Coarsening
Department of Computer Science, Hong Kong Baptist University, Hong Kong SAR, China · School of Information, Renmin University of China, Beijing, China · Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China +2
SEMIR: Topology-Preserving Graph Minors for Thin-Structure Segmentation
Jun 22, 2026Luke James Miller, Yugyung LeeImage Segmentation Thin-Structure Segmentation
University of Missouri-Kansas City, Kansas City MO 64110, USA
Hierarchical Pooling for Sheaf Neural Networks
Jun 18, 2026Dionisia Naddeo, Carlo Abate, Pietro Liò +2Graph Neural Networks Graph Coarsening
UiT The Arctic University of Norway · UiT The Arctic University of Norway NORCE Norwegian Research Centre AS
Graph Reduction in Multirelational Networks: A Spreading-Oriented Reduction Benchmark
Jun 10, 2026Mateusz Stolarski, Michał Czuba, Piotr Bielak +1Graph Coarsening Graph Sparsification
Wrocław University of Science and Technology, Wrocław, Poland
Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle
May 13, 2026Xu Bai, Bin Lu, Kun Zhang +4Graph Coarsening
School of Information Science and Electronic Engineering, Shanghai Jiao Tong University, Shanghai, China · School of Environment Science and Engineering, Shanghai Jiao Tong University, Shanghai, China · School of Artificial Intelligence, Nanchang University, Nanchang, China +2
SEMIR: Semantic Minor-Induced Representation Learning on Graphs for Visual Segmentation
May 12, 2026Luke James Miller, Yugyung LeeGraph Structure Learning Image Segmentation
Department of Computing, Analytics and Mathematics; University of Missouri-Kansas City, Kansas City, United States.
Diversity Curves for Graph Representation Learning
May 7, 2026Katharina Limbeck, Nadja Häusermann, Martin Carrasco +2Graph Representation Learning Graph Coarsening
1Helmholtz Munich · 2Technical University of Munich · 5Université de Fribourg +2
Efficient and Scalable Granular-ball Graph Coarsening Method for Large-scale Graph Node Classification
Mar 31, 2026Guan Wang, Shuyin Xia, Lei Qian +4Graph Coarsening Graph Neural Networks
School of Computer Science and Technology, Chongqing Key Laboratory of Computational Intelligence, Key Laboratory of Cyberspace Big Data Intelligent Security, Ministry of Education, Sichuan-Chongqing Co-construction Key Laboratory of Digital Economy Intelligence and Key Laboratory of Big Data Intelligent Computing, Chongqing University of Posts and Telecommunications, 400065, Chongqing, China. · School of Computer Science and Technology, School of Cyber Security and Information Law, Chongqing University of Posts and Telecommunications, 400065, Chongqing, China. · Chongqing Key Laboratory of Brain-Inspired Cognitive Computing and Educational Rehabilitation for Children with Special Needs, Chongqing Normal University, Chongqing, 401331, China. +1
CTS-Bench: Benchmarking Graph Coarsening Trade-offs for GNNs in Clock Tree Synthesis
Feb 22, 2026Barsat Khadka, Kawsher Roxy, Md Rubel AhmedGraph Coarsening Electronic Design Automation
The University of Southern Mississippi, Hattiesburg, Mississippi, USA · Intel Corporation, Hillsboro, Oregon, USA · Louisiana Tech University, Ruston, Louisiana, USA
NervePool: A Simplicial Pooling Layer
May 10, 2023Sarah McGuire Scullen, Ernst Röell, Elizabeth Munch +2Graph Coarsening Graph Pooling
Pacific Northwest National Lab, USA · Helmholtz Munich and Technical University of Munich, Germany · Michigan State University, USA +1

Oct 8, 2026J/K move · Enter open · S save

Score-Based Learning of Cluster DAGs from Interventions

Gaetano Tedesco, Alex Markham

Informatics Institute, University of Amsterdam · Department of Mathematical Sciences, University of Copenhagen

Score-Based Causal Discovery Causal Structure Learning Causal Discovery Causal Abstraction Graph Coarsening Causal Intervention

Open paper AskPDF arXiv

Graphical approaches to causal abstraction transform a low-level causal directed acyclic graph (DAG) over many measured variables into a smaller, high-level DAG whose nodes cluster the original variables and whose edges summarize the causal relations between clusters. Such cluster DAGs are easier to interpret, but learning them requires finding the clusters and recovering the edges between them. Madaleno et al. (2026) learn the interventional coarsening (the cluster DAG that merges variables the interventions cannot distinguish) in two constraint-based phases: first the clusters, then the edges. We introduce COARSE, the first score-based method for this task: it keeps the two-phase structure but, under linear Gaussian assumptions, swaps the constraint-based edge phase for a score-based one. We show that the interventions themselves identify a causal order over the clusters, and learning the edges reduces to a single local search per cluster under a cluster-level BIC score. We prove that the procedure runs in polynomial time and, provided the variables affected by each intervention are correctly identified, that it is consistent. On synthetic and real-world interventional data, COARSE matches state-of-the-art edge recovery given enough samples, with an edge phase up to two orders of magnitude faster, including on dense graphs with hundreds of nodes.