Jia Jiang, Zihan Tan, Wenke Huang, Bin Yang, Mang Ye
原文摘要
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.
Given an undirected unweighted graph $G$ on $n$ vertices and a set $P$ of $p$ pairs of its vertices, a distance preserver is a sparse subgraph of $G$ that exactly preserves the shortest-path distances between all pairs in $P$. In this paper, we prove a new upper bound of $O(n^{8/9} p^{4/9})$ for distance preservers when $p\in [n^{1/2}, n]$. Our result improves the previous bound of $O\big(n^{2/3}p^{2/3}+np^{1/3}\big)$ by Bodwin and Vassilevska Williams and $O(\min\{n+n^{1/2}p,\,np^{1/2}\})$ by Coppersmith and Elkin, particularly in the regime $p\in [n^{7/10}, n]$, and narrows the gap toward the conjectured $O(n^{2/3}p^{2/3}+n)$ bound. Using the techniques developed for distance preservers, we are also able to obtain pairwise additive $+2$ spanners with $O(n+n^{9/10}p^{2/5})$ edges, pairwise additive $+4$ spanners with $O(n+n^{24/25}p^{8/25})$ edges, and new bounds for sourcewise spanners, improving upon previous results in certain parameter regimes.
We give a unified framework for one-sided testability (constant-query testing) of metric families. For a broad class of families defined by fixed local predicates, we prove that testability is equivalent to two structural properties: \emph{packing amplification}, which turns many edge-disjoint local violations into a positive density of violations, and \emph{completion stability}, which allows locally consistent partial matrices with few missing entries to be cheaply completed. This characterization yields a common proof strategy and simpler proofs of classical testability results for ultrametrics, tree pseudometrics, Euclidean pseudometrics in fixed dimension, and several others. Our framework also gives new quantitative bounds for metric testing: a nonadaptive one-sided upper bound for matrices with entries in the bounded range $[1,C]$, and two-sided nonadaptive and adaptive lower bounds for general metrics.
A tree cover of an $n$-point metric space is a collection of $k$ trees such that every pairwise distance is approximately preserved in at least one tree. For fixed $k$, the best known distortion upper bound is $\tilde{O}(n^{1/k})$ and the best known lower bound is $Ω_k(n^{1/2^{k-1}})$. In this paper, we prove a lower bound of $Ω_k(n^{1/(k-1)^2})$ for all $k\ge 3$, significantly narrowing the gap towards the upper bound. Our approach makes use of a novel algebraic topological notion that we call the \emph{agreement index}: the equivariant topological index of a simplicial complex encoding pairwise agreement among tree labels. This notion helps characterize the power and limit of algebraic and topological methods for analyzing tree covers, and we believe it will also find applications to other problems.