CS Paper Radar

Dual-GNN Multilevel Coarsening for Maximum Independent Set

Tianfeng Chen, Xianyue Li

cs.LG math.CO ·submitted 2026-09-21 07:24 UTC · v2

Abstract

The maximum independent set (MIS) problem is a fundamental NP-hard combinatorial optimization problem with applications in scheduling, resource allocation, and network analysis. Exact solvers can provide high-quality solutions or optimality certificates, but their computational cost grows rapidly with graph size, while hand-crafted heuristics improve scalability at the expense of guarantees. Learning-based methods offer an alternative by exploiting structural patterns across graph instances, yet directly predicting independent sets can make global coordination difficult on large graphs. We instead use learning to guide multilevel graph coarsening while retaining combinatorial search for final decision making. Our Dual-GNN Multilevel Coarsening framework uses a Partition GNN to score candidate contractions and a Representative GNN to select top-k local independent-set states for each final cluster. Experiments on Erdős--Rényi graphs with up to 2,000 vertices demonstrate a favorable quality--runtime trade-off. On 500-vertex instances with certified optima, our method achieves an average independent-set size of 19.20, corresponding to 99.5\% of the optimal value of 19.30, while reducing the mean wall-clock time from 643.57 seconds for exact solving to 3.41 seconds, yielding an approximately 189$\times$ speedup. On larger graphs with 1,000 and 2,000 vertices, our method achieves the best mean solution quality among all evaluated methods. Moreover, although trained only on Erdős--Rényi graphs with edge probability $p=0.35$, the learned coarsening policy generalizes effectively across both unseen graph densities and structurally different graph families.

Comment
12 pages, 5 figures, and 6 tables

Closest papers

Nearest neighbours by meaning across the whole index.

MegaGraph: Towards Efficient Training of Large-Scale Graph Transformers with Automated Hybrid Parallelism

cs.LG ·2026-09-28 ·Tong Qiao, Ao Zhou, Yingjie Qi, Chunming Hu, Jianlei Yang
published similarity 0.62
Abstract · 8 pages,10 figures, accepted by ICCD2026

Graph Transformers (GTs) offer superior representation capabilities by overcoming the depth limitations and over-smoothing issues of traditional Graph Neural Networks (GNNs). However, scaling GTs to large graphs poses critical bottlenecks. Specifically, the attention score matrix and its associated topology-aware bias matrix jointly incur significant per-layer memory overhead, and heavy graph embedding layers result in severe workload imbalances. These characteristics are unique to GT training and are not addressed by parallelism techniques designed for either conventional GNNs or Transformers, making a dedicated solution necessary. This paper introduces MegaGraph, the first automated hybrid parallelism framework designed for efficient GT training. MegaGraph designs three specialized strategies, namely graph-aware context parallelism, heterogeneous pipeline parallelism, and hybrid data parallelism, to support efficient training on large-scale graphs. However, coordinating these three parallelism strategies yields an exponentially large configuration space. To address this complexity, an automatic search engine leverages precise cost models via a Profile - Model - Search workflow to identify the optimal parallelism configuration. Evaluations demonstrate that MegaGraph enables training on large-scale graphs where state-of-the-art baselines fail due to out-of-memory (OOM) errors. The framework reduces per-device peak memory by up to 77.8\% and achieves up to 4.51$\times$ training speedup while maintaining model accuracy.

0.28

HiGFRL: Hierarchical Graph Fusion-Driven Reinforcement Learning for Dependency-Aware Task Scheduling in Heterogeneous Cloud

cs.LG ·2026-09-14 ·Tiangang Li, Shi Ying, Xiangbo Tian
code/data similarity 0.61
Abstract · 16 pages, 13 figures

Online scheduling of dependency-aware tasks in heterogeneous cloud clusters is a fundamental yet challenging problem due to the complex interplay between DAG topologies and multi-dimensional resource constraints. While DRL has shown promise, existing GNN-based approaches often struggle to efficiently model high-order topological dependencies and suffer from loose coupling between task and resource states, leading to myopic scheduling decisions. To address these limitations, we propose HiGFRL, a Hierarchical Graph Fusion-Driven Reinforcement Learning framework. HiGFRL constructs a novel three-level state representation comprising a Static Hypergraph, a Dynamic Global Graph, and a Local Bipartite Graph to explicitly model the interplay between task dependencies and real-time cluster dynamics. Specifically, we design a fusion-driven dual-network architecture to optimize RL decision-making, where a Context Fusion Allocator integrates local bipartite matching features with fused global context to execute precise task-to-node allocation, and a Global State Evaluator leverages the global dynamic graph representation to accurately estimate expected long-term cumulative reward. Furthermore, we incorporate a topology-prior-guided hybrid reward mechanism that distills static topological priors into the learning process to accelerate convergence. Extensive experiments using real-world Alibaba cluster traces demonstrate that HiGFRL significantly outperforms heuristics and DRL baselines. Specifically, in challenging large-scale high-load scenarios, HiGFRL reduces the Makespan by up to 32.55%, and optimizes the average task flow time and average task wait time by 13.58% and 13.79%, respectively. Experimental results confirm that HiGFRL not only significantly improves cluster throughput but also ensures superior QoS by substantially reducing queuing delays. Code Release:https://github.com/igeng/HiGFRL.

0.25

Safe Hypergraph Contraction via Capacity-Aware Repair Certificates

cs.DS ·2026-10-01 ·Yu Deng, Xinyi Yang, Keren Zhu
theory similarity 0.60
Abstract

Multilevel partitioners shrink circuit hypergraphs through vertex contractions, yet a contraction that satisfies block capacity can still eliminate every optimal balanced bipartition. We develop certified safe coarsening (CSC) to identify contractions that preserve an optimum without computing that optimum. CSC certifies a repair for any feasible partition that splits a candidate group: the repair must respect the fixed block capacities and must not increase the cut-net objective. Its bounds exclude hyperedges that capacity constraints force to be cut. A pair certificate checks individual merges, while a directed minimum-cut test certifies groups whose savings emerge only when vertices move together. We prove that certified disjoint batches and successive rounds with recertification retain at least one globally optimal feasible partition for hypergraphs with positive integer vertex and net weights. Experiments on exactly solvable instances confirm optimum preservation for every tested configuration; integration with KaHyPar lowers the sum of per-instance best cuts on circuit benchmarks, with additional runtime.

0.35

Graph-dependent pooling: adaptive granularity in hierarchical graph neural networks

cs.AI cs.LG ·2026-10-24 ·Bohan Yoon, Hyejin Jang
similarity 0.60
Abstract

Graph Neural Networks are widely used to learn structural representations of relational data. Hierarchical graph pooling learns multi-level representations by progressively coarsening graphs; however, prior methods rely on predefined cluster numbers or fixed pooling ratios, limiting adaptability to individual graphs. We propose Graph-Dependent Pooling (GDPool), which dynamically determines pooling granularity for each graph. We analyze optimization conflicts among layer-wise objectives through gradient alignment, showing that independently supervised pooling levels can send conflicting gradients to shared parameters. GDPool uses self-attention to select graph-specific anchors representing structurally important nodes and constructs coarse graphs through soft node assignment. Experiments on metal-organic framework and molecular graph benchmarks show that GDPool consistently achieves the best predictive performance across all benchmarks. Evaluations using modularity and the effective number of clusters show that GDPool achieves consistently higher modularity than existing methods while the number of active clusters decreases monotonically with depth. Sensitivity analyses confirm stable behavior across hyperparameter and architectural choices.

0.13

Exact computation of the network modularity with branch-and-bound

cs.SI stat.CO ·2026-10-03 ·Emily Weng, Georg Hahn
publishedbenchmark similarity 0.60
Abstract

We consider the computation of the network modularity, a common measure of the structure of networks or graphs that quantifies the division of a network into modules or clusters. The computation of the network modularity is an NP-hard problem, thus making its exact computation often infeasible in practice. This has resulted in the development of several heuristics in the literature. In this work, we consider the exact computation of the network modularity with the help of a branch-and-bound algorithm. Our algorithm is guaranteed to find the optimal clustering that maximizes the network modularity, however it achieves this without a full exploration of the search space. This is accomplished by bounding partial solutions and discarding them if it can be foreseen that a partial solution will not yield an improvement over an existing solution. We assess our algorithm with respect to accuracy and runtime and compare it to a brute-force approach as well as two benchmark algorithms, simulated annealing and the Louvain method.

0.40

Rethinking One-Shot Federated Graph Learning: Training-Free Statistical Estimation

cs.LG ·2026-09-05 ·Shutong Zheng, Sijia Chen
code/data similarity 0.59
Abstract · 23 pages, 9 figures, including supplementary material

One-shot federated graph learning generally aims to train Graph Neural Networks (GNNs) across clients with disconnected subgraphs in a single communication round. Existing methods predominantly design advanced optimization strategies under the premise that local GNN training is indispensable. However, empirical observations reveal that under extreme non-IID conditions, local GNN training suffers from severe cross-client representation misalignment, becoming a major source of error rather than a remedy. Motivated by this, we reformulate one-shot FGL as a statistical estimation problem. We propose SPEAR (Statistical Prototype Estimation with Adaptive Reliability), a completely training-free framework that directly computes topology-smoothed class prototypes from local graphs in the original feature space. The server then aggregates these prototypes using a sample-size-adaptive shrinkage estimator that down-weights unreliable local estimates, producing robust global class prototypes. Extensive experiments across seven benchmarks demonstrate that SPEAR consistently achieves state-of-the-art accuracy under extreme heterogeneity. Moreover, SPEAR delivers at least an order-of-magnitude speedup over all baselines, reaching several orders of magnitude against generative and distillation-based methods. Our findings suggest that training-free statistical estimation, rather than local GNN optimization, provides the key to robust and efficient one-shot federated graph learning. The code is available at https://github.com/Yodeesy/SPEAR .

0.60

FairPGT: Partitioned Graph Transformers for Dual-Level Fair Graph Clustering

cs.LG cs.AI ·2026-11-17 ·Siamak Ghodsi, Amjad Seyedi, Sahar Tahmasebi, Eirini Ntoutsi, Sören Auer
theorycode/data similarity 0.59
Abstract · Under review. 36 pages, 8 figures, 5 tables. Code: https://github.com/SiamakGhodsi/FairPGT

Clustering on attributed graphs can produce demographically biased clusters, particularly when communities align with protected groups. Graph transformers can amplify this bias through same-group attention, while global attention limits scalability. We propose FairPGT, a partitioned graph transformer for fair graph clustering. FairPGT restricts attention to METIS partitions and connects them through routing tokens, which divides the quadratic cost of attention by the number of partitions. A graph-aware self-training target guides clustering, with a provably bounded deviation from the standard DEC target. Fairness is imposed at two levels: a mutual-information term promotes demographic parity in cluster assignments, while a normalized cross-group attention ratio (nCGAR) guides attention toward group neutrality through self-distillation. We prove that the nCGAR correction moves attention toward neutrality and establish a condition preventing overshooting. Across seven benchmarks, FairPGT achieves the best clustering performance and statistical parity on the three largest graphs (Credit, Pokec-n, Pokec-z), with a statistical-parity gap approximately ten times lower than DMoN, and is Pareto-dominated on only one dataset. On controlled stochastic block models, FairPGT attains 97% of the derived upper bound on NMI for exactly fair clustering when communities and protected groups coincide. These graphs further show that, under strong alignment, assignment-level fairness alone makes the attention group-heterophilous, whereas attention-level fairness alone improves neutrality without ensuring fair clusters. Code for reproducibility is available at https://github.com/SiamakGhodsi/FairPGT.

0.42

Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering

cs.LG math.ST ·2026-09-24 ·Yordan P. Raykov, Max A. Little
theory similarity 0.58
Abstract

Exact Euclidean \(K\)-means partitions \(n\) observations into \(K\) unlabelled clusters, but the unrestricted search is generally exponential. We use data-derived geometric graphs to precondition an exact subset dynamic program: as a result only connected vertex subsets are admitted as clusters, while sum-of-squared-errors (SSE) loss is unchanged. A remaining-set recurrence minimises fixed-\(K\) or penalised SSE, with exact factorisation over the connected components of each remaining set. The central question we study is how much computational support can be removed while preserving an unrestricted optimum. Graph inclusion gives monotone coverage and support relations, and a bottleneck threshold identifies the first covering graph in a nested hierarchy. For fixed \(K\) and dimension, under compact ball support and density bounds, retaining \(q=O(\log n)\) nearest neighbours per observation preserves an empirical SSE optimum with probability tending to one, using an \(O(\log n/n)\) fraction of complete-graph edges. Truncated Gaussian mixtures with unequal weights and covariances satisfy these conditions. The rate we provide is a sufficient upper bound rather than a result implying polynomial optimisation complexity. Objective-matched synthetic and full-data comparisons assess coverage, compression, and reference-label agreement. As a secondary application, we illustrate how the proposed scaffold preconditioning can be utilized to improve the efficiency of split-merge proposals that preserve unrestricted mixture posteriors.

0.17