CS Paper Radar

Structural Entropy-Driven Graph Diffusion Generation for One-Shot Federated Graph Learning

Shutong Zheng, Lele Fu, Sheng Huang, Wei Yang Bryan Lim, Chuan Chen

cs.LG ·submitted 2026-09-06 09:31 UTC · v1

Abstract

One-shot federated graph learning (FGL) requires the server to estimate client contributions from highly compressed information, yet conventional volume-based weighting captures the amount of client data while overlooking how its connectivity is organized. In this paper, we propose SPIRE, a Structural Entropy-Driven Graph Diffusion Generation method that introduces topology-aware client differentiation into one-shot FGL. Specifically, we employ first-order degree-distribution structural entropy as a compact descriptor of degree-mass dispersion and use it to derive structural client weights, providing an inductive bias that accounts for differences in graph topology beyond data volume. On the generation side, a graph diffusion model on the server synthesizes pseudographs conditioned on the weighted client prototypes, capturing both semantic and structural information without requiring additional client-side training. The generated pseudographs are then assembled via disjoint union fusion to train a global graph neural network. Extensive experiments on seven real-world graph datasets demonstrate that SPIRE consistently outperforms conventional and one-shot FGL methods, with particularly strong gains under highly heterogeneous (non-IID) and graph-perturbed settings.

Comment
11 pages, 5 figures

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.LG ·2026-09-05 ·Shutong Zheng, Sijia Chen
code/data similarity 0.75
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

One-Shot Federated Graph Learning via High-Fidelity Proxies and Transferability-Guided Collaboration

cs.LG ·2026-11-09 ·Jia Jiang, Zihan Tan, Wenke Huang, Bin Yang, Mang Ye
top venuecode/data similarity 0.71
Abstract · Accepted at NeurIPS 2026

One-shot Federated Graph Learning (OFGL) has emerged as a communication-efficient paradigm for federated graph learning under strict bandwidth constraints, compressing collaboration into a single transmission round. Nevertheless, this extreme setting suffers from a fundamental Single-Transmission Bottleneck, which limits both the quality and utility of exchanged knowledge. First, while existing methods attempt to distill private graphs into shareable proxies, their aggressive one-shot compression inherently triggers a fidelity crisis. This compression distorts local graph topology and semantics across clients, leading to externalized knowledge underexpression. Second, although the server aggregates these proxies to update global models, current integration schemes suffer from transferability agnosticism. The server cannot reliably identify cross-client collaboration potential, thus resulting in integrated knowledge underutilization. To tackle these dual challenges, we propose FedHFT, an effective One-Shot Personalized Federated Graph Learning (OPFGL) framework that addresses this bottleneck from two perspectives, namely High-Fidelity Knowledge Externalization and Transferability-Ware Knowledge Integration. We use Fidelity-Driven Proxy Refinement to preserve client-side knowledge fidelity, and Transferability-Steered Personalized Collaboration to enable adaptive server-side collaboration. The superiority of FedHFT is validated through extensive experiments on both homophilic and heterophilic graphs. The code is available at https://github.com/Jumpy-Juice/FedHFT.

0.32

FlatLand: Personalized Graph Federated Learning via Tailored Lorentz Space

cs.LG ·2026-08-21 ·Jiahong Liu, Ram Samarth B B, Xinyu Fu, Menglin Yang, Weixi Zhang +2 more
top venue similarity 0.67
Abstract · 34 pages, 9 figures, 8 tables. Accepted at ICML 2026 (Oral)

Federated learning enables privacy-preserving collaborative training, but highly heterogeneous client data remain challenging, especially in graph federated learning where clients possess structurally diverse graphs. Existing personalized federated learning (PFL) methods ignore the intrinsic geometric properties of diverse graph structures. We propose FlatLand, a novel personalized federated learning method that embeds different clients' data in tailored Lorentz space of hyperbolic geometry. Our key insight is that hyperbolic geometry naturally accommodates the intrinsic negative curvature prevalent in real-world graphs, while the time-like dimension in Lorentz space provides a principled way to encode client-specific heterogeneity. We develop a parameter decoupling strategy that separates heterogeneous information (captured in time-like parameters) from common knowledge (preserved in space-like parameters), enabling direct aggregation without requiring client similarity estimation and extra calculation modules. Empirical results on diverse federated graph learning tasks demonstrate that FlatLand achieves superior performance, particularly in low-dimensional settings.

0.59

Two-level domain-decomposition AdaGrad method for scalable training of graph neural networks

cs.LG math.NA ·2026-08-23 ·Laurynas Varnas, Julien Herrmann, Alexander Heinlein, Serge Gratton, Alena Kopaničáková
hot direction similarity 0.66
Abstract

Graph neural networks (GNNs) have emerged as a powerful framework for learning from graph-structured data. However, their efficient training remains challenging, particularly in distributed computing environments. This challenge arises from the use of message passing, which couples all graph nodes, leading to expensive optimization steps, high memory requirements, and substantial communication overhead. To alleviate these limitations, we propose a novel domain-decomposition (DD) variant of AG2m, an AdaGrad method enhanced with second-order curvature information and momentum, denoted by DD-AG2m. The proposed DD-AG2m alternates between AG2m optimization on the original (global) graph and AG2m optimization on the partitioned graphs. To incorporate global information at reduced cost, we further introduce a two-level variant (2DD-AG2m) that performs global optimization steps on a coarse graph obtained by randomly subsampling nodes within each subdomain. Numerical experiments spanning graph classification, node-level regression, and spatiotemporal forecasting tasks demonstrate that the proposed DD methods reduce the computational cost required to achieve the same predictive performance by a factor of 4-8. Moreover, for the fixed computational cost, they improve the predictive performance of GNNs by up to 22% compared with the baseline AG2m.

0.33

Columnar-Embedder: A Biologically Inspired Cortical Architecture for Binary Sparse Distributed Graph Representations

cs.NE ·2026-08-12 ·Mohamed Abidalrekab, Dan Hammerstrom
similarity 0.66
Abstract

Finding a representative description of graph entities that captures their structural roles and homophily is a challenging goal for graph embedding techniques due to the non-Euclidean nature of graphs. Traditionally, Graph embeddings achieve top performance via random-walk methods and graph neural networks. However, these methods are transductive and utilize an expensive global optimization via softmax or a dense representation trained in an end-to-end pipeline with gradient descent. Nonetheless, other variants of GNNs can map to unseen nodes; they still rely on iterative message passing and backpropagation, incurring high computational and memory costs. Conversely, the mammalian cortex solves structurally similar problems by learning to map its input stream of patterns into a compact representation for downstream regions. We present the biologically inspired Columnar-Embedder architecture for learning binary Sparse Distributed Representations (SDRs) of graph nodes. The learning is driven by a local Bienenstock-Cooper-Munro (BCM) Hebbian rule modulated by positive pointwise mutual information (PPMI) computed from online streams of random walks. Continuous learning from streaming random-walk pairs without labels, backpropagation, or supervision enables the architecture to exhibit natural resistance to catastrophic forgetting. Across five graph benchmarks, the performance of SDRs is competitive with that of real-valued dense embeddings on node classification and link prediction, while the architecture exhibits portability, resilience to noise, and robustness to data corruption.

0.04

Certifying Graph Neural Networks Against Label and Structure Poisoning

cs.LG ·2026-11-02 ·Lukas Gosch, Xichuan Chen, Yan Scholten, Stephan Günnemann
top venue similarity 0.66
Abstract · Published at the International Conference on Machine Learning (ICML) 2026

Robust machine learning for graph-structured data has made significant progress against test-time attacks, yet certified robustness to poisoning - where adversaries manipulate the training data - remains largely underexplored. For image data, state-of-the-art poisoning certificates rely on partitioning-and-aggregation schemes. However, we show that these methods fail when applied in the graph domain due to the inherent label and structure sparsity found in common graph datasets, making effective graph-partitioning difficult. To address this challenge, we propose a novel semi-supervised learning framework called deep Self-Training Graph Partition Aggregation (ST-GPA), which enriches each graph partition with informative pseudo-labels and synthetic edges, enabling effective certification against node-label and graph-structure poisoning under sparse conditions. Our method is architecture-agnostic, scales to large numbers of partitions, and consistently and significantly improves robustness guarantees against both label and structure poisoning across multiple benchmarks, while maintaining strong clean accuracy. Overall, our results establish a promising direction for certifiably robust learning on graph-structured data against poisoning under sparse conditions.

0.46

SAC-GCL: Structure-Aware Compression for Graph Contrastive Learning

cs.LG cs.SI ·2026-10-27 ·Muhammad Ifte khairul Islam, Tanvir Hossain, Esra Akbas
benchmark similarity 0.65
Abstract

Graph Contrastive Learning (GCL) has achieved remarkable success in self-supervised representation learning by maximizing agreement between augmented views of a graph. Although augmented view generation is the central step in GCL, existing models rely on stochastic augmentation of the input graph, such as edge perturbation and node masking, which lack structural awareness and frequently destroy critical topology or introduce semantically inconsistent views. While recent adaptive methods improve upon random perturbations, they primarily operate on localized node or edge neighborhoods and fail to capture higher-order, macro-level structural organization crucial for graph classification. To address this limitation, we propose Structure-aware Compression for Graph Contrastive Learning (SAC-GCL), a novel framework that employs structural decomposition and graph compression as a principled view generation strategy. Moving beyond random augmentations, SAC-GCL leverages structural decomposition techniques to extract cohesive subgraphs and condense them into supernodes, constructing coarsened graph views that preserve local density and capture higher-level structural patterns while reducing noise and redundancy. We leverage multiple cohesive subgraph models to derive complementary views of the graph, each capturing distinct structural properties. To capture multi-resolution information, a hierarchical view encoder processes these compressed views by initializing super-node features with shared-weight cohesive subgraph embeddings. Our results from extensive experiments on six benchmark datasets demonstrate that structure-aware compression provides a powerful alternative to random perturbations, yielding more robust and discriminative graph representations for graph classification tasks.

0.15

Discrete Diffusion for Large Graph Generation via Structural Candidate Restriction

cs.AI cs.SI ·2026-10-02 ·Yassin Mohamadi, Zeno Geradts, Marcel Worring
similarity 0.65
Abstract

Synthesizing realistic graphs at scale is vital when the graphs of interest are large and real-world samples are limited or access-sensitive. Diffusion-based generators have recently driven much of the progress, offering high modeling capacity, but most such methods have quadratic computational complexity and are hence restricted to small-scale networks, currently up to 3k nodes. Existing non-quadratic methods remain limited by memorization issues and a trade-off between scalability and generation quality. Our goal is to generate large graphs whose structural statistics --- e.g., degree distribution, clustering, and path length --- faithfully reflect those of real-world sparse graphs, without resorting to memorizing the training data. We introduce a discrete graph diffusion model that restricts training to a structurally motivated subset of node pairs --- observed edges and their wedge non-edges --- reducing training complexity below quadratic in the number of nodes. To keep the noisy graph informative throughout both the forward and reverse trajectories, we design a three-class absorbing forward process governed by a \emph{degree-aware, floored} cosine noise schedule: unlike a structure-blind schedule that adds noise to every pair identically, ours adapts to each node's degree and never fully erases the graph's structure, keeping the noisy graph informative at every step. Experiments across diverse datasets show that our model consistently ranks among the top methods for structural fidelity against existing discrete diffusion baselines in large graph generation.

0.25