More Is Better? Exploring Latent Correspondence in Federated Hypergraph Learning

Bo Yan; Siming Zhang; Siqi Li; Hang Yu

cs.LGOct 29, 2026

More Is Better? Exploring Latent Correspondence in Federated Hypergraph Learning

Authors: Bo Yan, Siming Zhang, Siqi Li, Hang Yu

Organizations: Tsinghua University · Shanghai University

Abstract

Federated hypergraph learning with latent cross-client hyperedge correspondence poses fundamental identifiability and computational challenges, as the same local release can correspond to multiple global hypergraph structures. We characterize the tractability of recovering these latent correspondences, showing tractable pairwise assignment but generally intractable multi-client hyperedge matching. Building on this characterization, we derive a cross-entropy decomposition that reveals when local prediction can outperform predictors fitted with additional cross-client information. Motivated by this principle, we introduce Federated Adaptive Spectral Training with Representation Alignment (FedASTRA), which learns correspondence-invariant diffusion representations through adaptive heat diffusion and masked latent prediction while communicating model parameters only. We establish its asymptotic optimality with respect to the permitted local information and prove global population-risk convergence under explicit conditions on recovery, representation, and update alignment. Experiments on eight real-world datasets demonstrate the effectiveness of FedASTRA against identifier-free federated graph and hypergraph methods. On ogbn-papers100M, FedASTRA reaches the performance-communication Pareto frontier, achieving 50.07 Accuracy and 29.73 Macro-F1 while communicating only 59.60 MiB per round.

Figures & tables

Figure 1: From complete hyperedges to latent hyperedge correspondences. (a) A complete care episode is represented as a hyperedge connecting its clinical events, e.g., blood pressure (BP), electrocardiogram (ECG), and surgery. (b) A episode may span multiple hospitals, e.g., BP measurement and ECG examination may be performed at hospital A, while the subsequent surgery is carried out at hospital B. Each hospital observes only a local fragment of the original hyperedge, leading to higher-order truncation . (c) Once cross-hospital record correspondences are latent, the same local releases can admit multiple compatible global matchings, resulting in hyperedge aliasing .

Method	CoraCA		DBLP4k		IMDB4k		Trivago
	Acc. (%)	Macro-F1 (%)	Acc. (%)	Macro-F1 (%)	Acc. (%)	Macro-F1 (%)	Acc. (%)	Macro-F1 (%)
Fed-HGNN	68.64 $\pm$ 1.45	64.35 $\pm$ 1.71	77.63 $\pm$ 1.35	76.98 $\pm$ 1.18	48.85 $\pm$ 1.29	48.59 $\pm$ 1.23	21.85 $\pm$ 0.19	4.27 $\pm$ 0.20
Fed-HNHN	54.73 $\pm$ 1.17	50.42 $\pm$ 1.76	69.58 $\pm$ 1.18	68.79 $\pm$ 1.12	44.96 $\pm$ 1.50	43.05 $\pm$ 1.24	25.68 $\pm$ 1.02	7.72 $\pm$ 0.24
Fed-HyperGCN	64.02 $\pm$ 1.64	58.07 $\pm$ 1.95	72.69 $\pm$ 0.77	71.46 $\pm$ 0.86	44.14 $\pm$ 1.16	40.86 $\pm$ 2.38	9.17 $\pm$ 0.20	0.13 $\pm$ 0.02
Fed-AllDeepSets	39.63 $\pm$ 1.83	27.08 $\pm$ 2.04	39.35 $\pm$ 0.55	32.45 $\pm$ 1.71	40.32 $\pm$ 1.15	34.12 $\pm$ 2.20	10.88 $\pm$ 0.15	0.27 $\pm$ 0.01
Fed-AllSetTransformer	30.22 $\pm$ 0.00	6.63 $\pm$ 0.00	30.99 $\pm$ 1.29	21.81 $\pm$ 0.86	37.04 $\pm$ 0.05	18.10 $\pm$ 0.07	8.99 $\pm$ 0.00	0.10 $\pm$ 0.00

Table 1: Performance on identifier-free native hypergraphs. Results are averaged over

K\in\{3,6,9\}

Figure 2: Ablation study on the adaptive diffusion (left) and the masked prediction (right).

Method	Cora			CiteSeer			Facebook			Average communication traffic
	$K=3$	$K=6$	$K=9$	$K=3$	$K=6$	$K=9$	$K=3$	$K=6$	$K=9$	Model/round	Auxiliary/run
FedSage	70.35 $\pm$ 1.96	63.18 $\pm$ 0.97	58.65 $\pm$ 1.85	65.08 $\pm$ 0.96	63.73 $\pm$ 0.74	62.93 $\pm$ 1.72	72.63 $\pm$ 0.73	65.64 $\pm$ 1.81	60.41 $\pm$ 1.61	4.82	0
FedGCN (0-hop)	74.07 $\pm$ 1.57	65.90 $\pm$ 2.05	62.07 $\pm$ 1.79	68.68 $\pm$ 1.50	65.83 $\pm$ 0.56	65.14 $\pm$ 1.80	75.14 $\pm$ 0.95	67.87 $\pm$ 1.71	64.30 $\pm$ 1.22	2.41	0
FedSage+	69.67 $\pm$ 0.71	63.11 $\pm$ 1.66	61.02 $\pm$ 1.40	63.16 $\pm$ 1.17	62.53 $\pm$ 1.66	62.95 $\pm$ 1.62	68.17 $\pm$ 0.33	61.85 $\pm$ 0.95	58.56 $\pm$ 1.33	4.82	17314.45
FedGCN (2-hop)	84.05 $\pm$ 1.17	84.05 $\pm$ 1.16	84.12 $\pm$ 0.92	72.20 $\pm$ 1.44	72.27 $\pm$ 1.53	72.38 $\pm$ 1.50	83.21 $\pm$ 0.76	82.84 $\pm$ 0.50	82.73 $\pm$ 0.85	2.41	673.79
FedCog	84.29 $\pm$ 1.50	84.34 $\pm$ 1.06	83.92 $\pm$ 0.78	72.21 $\pm$ 1.49	72.38 $\pm$ 1.04	72.51 $\pm$ 1.42	82.46 $\pm$ 0.69	82.50 $\pm$ 0.84	82.15 $\pm$ 0.94	2.41	752.27

Table 2: Performance against federated graph learning methods. Communication traffic (MiB) is averaged across datasets and client counts, with model traffic per round and auxiliary traffic per run.

Method	Acc. (%)	Macro-F1 (%)	#Parameters	Parameter trafffic/round
Fed-MLP	33.61	13.74	983,380	60.02
Fed-SIGN	38.42	16.56	984,442	60.09
Fed-HGNN	31.04	9.97	982,672	59.98
Fed-HNHN	35.93	13.46	34,672	2.12
Fed-HyperGCN	40.38	21.44	984,442	60.09
Fed-GCN	39.70	17.40	983,380	60.02

Table 3: Performance on complete ogbn-papers100M dataset. Nodes are partitioned across 8 clients. Traffic counts bidirectional trainable-parameter per round (MiB). BatchNorm buffers stay local.

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
$\mathcal{H}=(V,\mathcal{E},X,r,w)$	Finite node-attributed, typed, weighted multihypergraph.
$A_{e},r_{e},w_{e}$	Support, type in $\mathcal{R}$ , and positive weight of relation instance $e\in\mathcal{E}$ .
$w_{r}(A)$	Aggregate weight of type- $r$ instances with support $A$ .
$M_{q,r}^{\mathcal{H}}(S)$	Weighted type- $r$ order- $q$ co-membership count for $S\in\binom{V}{q}$ .
$\mathsf{Z}$ , $z$ , $V_{k}$	Random node-to-client assignment, one realization, and the nodes assigned to client $k$ .
$c$ , $\upsilon_{e,k}$	Minimum visible fragment size and the analyst’s local/cross status mark.

Appendix

Table 4: Core notation for the observation model, identification results, algorithm, and experiments.

$R$	$L_{\rm tail}$	Forward tail	Time-gradient tail	Relative $\ell_{2}$ residual	CPU median (ms)
2	11	$2.95{\times}10^{-8}$	$2.87{\times}10^{-7}$	$3.07{\times}10^{-8}$	26.30
4	15	$4.35{\times}10^{-8}$	$2.98{\times}10^{-7}$	$2.26{\times}10^{-8}$	33.72
6	18	$9.34{\times}10^{-8}$	$5.26{\times}10^{-7}$	$1.48{\times}10^{-8}$	33.27
8	21	$1.06{\times}10^{-7}$	$5.34{\times}10^{-7}$	$2.20{\times}10^{-8}$	42.99

Appendix

Table 5: Heat-basis evaluation on one CoraCA client at

K=6

L_{\rm tail}

is selected using the

10^{-6}

tail criterion in Equation ( 59 ), and residuals are measured against a reference evaluation with tolerance

10^{-12}

. CPU timings are reported in milliseconds (ms) on identical local inputs.

Protocol item	Declared scope
Server receives	Online model parameters from each participating client.
Server broadcasts	The aggregated online model parameters.
Fixed aggregation metadata	Each client’s labeled-training count, fixed before training.
client-local state	Raw attributes, labels, incidence tables, relation membership, relation identifiers, round-local optimizer state, heat powers, latent states, and the local EMA target context encoder reset at each round.
Auxiliary learned-state payload	Zero bytes. No embeddings, relation summaries, or target parameters are transmitted.
Structural access claim	Direct cross-client node, edge, and source-hyperedge identifiers are absent.

Appendix

Table 6: Server-visible information and client-local state for FedASTRA.

	CoraCA	DBLP4k	IMDB4k	Trivago	Cora	CiteSeer	Facebook	ogbn-papers100M
#Nodes	2,708	4,057	4,278	172,738	2,708	3,327	22,470	111,059,956
#Graph edges	–	–	–	–	5,278	4,552	85,424	1,614,062,356
#Hyperedges	1,072	22,051	7,338	233,202	2,708	3,327	22,470	111,059,956
#Incidences	4,585	110,330	17,106	726,861	13,264	12,431	193,318	3,339,184,668
#Classes	7	4	3	160	7	6	4	172
#Features	1,433	334	3,066	300	1,433	3,703	4,714	128

Appendix

Table 7: Statistics of the datasets used in the experiments.

	Standard experiments	Trivago
Hyperedge input	Type-marginalized binary incidence, unit weights	Type-marginalized binary incidence, unit weights
Online model	Hidden dimension 64, dropout $0.35$	Hidden dimension 128, dropout $0.20$
Optimization	Adam, learning rate $10^{-2}$ , weight decay $5\times 10^{-4}$ , gradient clip $5.0$	Adam, learning rate $3\times 10^{-3}$ , weight decay $5\times 10^{-4}$ , gradient clip $5.0$
Heat basis	$R=4$ , increment floor $10^{-4}$ , tail tolerance $10^{-6}$	$R=8$ , increment floor $10^{-4}$ , tail tolerance $10^{-6}$
Predictive path	Two masks with probability $0.40$ , $\lambda_{\rm pred}=1$ , EMA decay $0.99$	Two masks with probability $0.30$ , $\lambda_{\rm pred}=1$ , EMA decay $0.996$

Appendix

Table 8: Configurations of FedASTRA in the standard experiments and on Trivago.

CoraCA
Method	$K=3$		$K=6$		$K=9$
	Acc. (%)	Macro-F1 (%)	Acc. (%)	Macro-F1 (%)	Acc. (%)	Macro-F1 (%)
FedASTRA	76.27 $\pm$ 0.54	74.33 $\pm$ 0.72	74.97 $\pm$ 0.63	72.79 $\pm$ 0.93	74.27 $\pm$ 0.73	71.52 $\pm$ 0.97
Fed-HGNN	71.44 $\pm$ 1.90	67.79 $\pm$ 2.12	67.97 $\pm$ 1.38	63.57 $\pm$ 1.50	66.52 $\pm$ 2.32	61.68 $\pm$ 3.02
Fed-HNHN	57.30 $\pm$ 0.82	54.40 $\pm$ 1.21	54.16 $\pm$ 2.46	49.08 $\pm$ 3.29	52.74 $\pm$ 1.13	47.77 $\pm$ 2.57
Fed-HyperGCN	67.38 $\pm$ 1.01	63.08 $\pm$ 1.64	63.84 $\pm$ 2.16	57.65 $\pm$ 2.56	60.85 $\pm$ 2.56	53.47 $\pm$ 3.07

Appendix

Table 9: Complete native-hypergraph results under different number of clients.

Cora
Method	$K=3$		$K=6$		$K=9$
	Acc. (%)	Macro-F1 (%)	Acc. (%)	Macro-F1 (%)	Acc. (%)	Macro-F1 (%)
FedSage	70.35 $\pm$ 1.96	67.77 $\pm$ 1.67	63.18 $\pm$ 0.97	58.59 $\pm$ 0.87	58.65 $\pm$ 1.85	52.17 $\pm$ 2.81
FedGCN (0-hop)	74.07 $\pm$ 1.57	71.24 $\pm$ 1.86	65.90 $\pm$ 2.05	61.96 $\pm$ 3.34	62.07 $\pm$ 1.79	57.44 $\pm$ 2.91
FedSage+	69.67 $\pm$ 0.71	66.87 $\pm$ 0.30	63.11 $\pm$ 1.66	57.78 $\pm$ 1.63	61.02 $\pm$ 1.40	55.05 $\pm$ 3.65
FedGCN (2-hop)	84.05 $\pm$ 1.17	83.01 $\pm$ 1.23	84.05 $\pm$ 1.16	83.12 $\pm$ 1.20	84.12 $\pm$ 0.92	82.92 $\pm$ 0.78

Appendix

Table 10: Complete results under different cross-client information-access settings.

Method	Exchanged or accessed information	Accuracy (%)	Macro-F1 (%)
Cora
FedASTRA	Model parameters only, with no direct cross-client identifiers	75.11 $\pm$ 0.99	73.34 $\pm$ 1.13
FedSage+	Locally generated boundary features and cross-client reconstruction gradients, with no direct identifiers	64.60 $\pm$ 1.11	59.90 $\pm$ 1.71
FedGCN (2-hop)	Cross-client node IDs, edges, and pre-aggregated neighbor features	84.07 $\pm$ 1.03	83.02 $\pm$ 1.04
FedCog	Cross-client node IDs, edges, and intermediate embeddings	84.18 $\pm$ 1.04	83.08 $\pm$ 1.03
CiteSeer

Appendix

Table 11: Summarized results of federated graph baselines under different cross-client information-access settings. Results are aggregated across client counts

K\in\{3,6,9\}

Dataset	Reported condition	Parameters	Accuracy (%)	Macro-F1 (%)
CoraCA	$R=1,\ \lambda_{\mathrm{pred}}=0$	126,407	67.26 $\pm$ 1.48	62.94 $\pm$ 1.75
CoraCA	$R=1,\ \lambda_{\mathrm{pred}}=1$	126,407	74.27 $\pm$ 0.56	71.96 $\pm$ 0.58
CoraCA	$R=4,\ \lambda_{\mathrm{pred}}=0$	177,671	69.32 $\pm$ 0.69	65.31 $\pm$ 1.15
CoraCA	$R=4,\ \lambda_{\mathrm{pred}}=1$	177,671	74.97 $\pm$ 0.63	72.79 $\pm$ 0.93
DBLP4k	$R=1,\ \lambda_{\mathrm{pred}}=0$	55,684	77.54 $\pm$ 0.70	76.77 $\pm$ 0.78
DBLP4k	$R=1,\ \lambda_{\mathrm{pred}}=1$	55,684	79.58 $\pm$ 0.67	78.99 $\pm$ 0.49

Appendix

Table 12: Ablation study of adaptive diffusion and masked prediction at

K=6

. This study is separate from the heat-width sweep in Appendix D .

Dataset	Reported condition	Accuracy (%)	Macro-F1 (%)
CoraCA	Low-truncation	77.99 $\pm$ 0.58	76.40 $\pm$ 0.74
CoraCA	Reference	75.58 $\pm$ 1.33	73.27 $\pm$ 1.07
CoraCA	High-truncation	73.97 $\pm$ 0.80	71.34 $\pm$ 0.80
DBLP4k	Low-truncation	78.23 $\pm$ 1.76	77.54 $\pm$ 1.59
DBLP4k	Reference	79.46 $\pm$ 1.23	78.85 $\pm$ 1.13
DBLP4k	High-truncation	79.24 $\pm$ 1.49	78.66 $\pm$ 1.49

Appendix

Table 13: Controlled-truncation results at

K=6

$q$	Releases	Eligible strata	Point identified	Median relative width	$q$ -mass floor	Oracle coverage
2	20	30	0/30	36.37%	18.18%	20/20
3	20	30	0/30	70.56%	35.28%	20/20
4	20	30	0/30	86.62%	43.31%	20/20
5	20	30	0/30	93.71%	46.85%	20/20

Appendix

Table 14: Two-client structural identification audit on four native datasets. For each order

q

, the audit contains 20 releases and 30 eligible strata. Relative endpoint width is

(\Phi_{q}^{+}-\Phi_{q}^{-})/\Phi_{q}^{+}

. By Corollary 2 , half of this normalized width gives the corresponding minimax lower bound for observable point estimation of the same order-

q

mass.

Dataset	$q=2$	$q=3$	$q=4$	$q=5$
CoraCA	6,714	69,204	469,120	2,631,843
DBLP4k	3,752,114	983,644,998	$2.1971{\times}10^{11}$	$4.2294{\times}10^{13}$
IMDB4k	18,587	205,338	1,581,947	10,490,694
Trivago	410,593	3,263,206	23,744,190	209,428,691

Appendix

Table 15: Median absolute sharp-endpoint gaps over five two-client diagnostic partitions, measured in order-

q

tuple units. The values preserve the original dataset scale, complementing the normalized endpoint widths reported in Table 14 .

Release change	Cells	Numeric endpoint	Audited conclusion
Merge observed type strata	40	Available	The coarsened endpoint hull contains the exact hull in 40/40 cells.
Remove local/cross marks	40	Bound required	Finite endpoints require a public cross-row count and support bound.
Delete 10% of one-side fragments	40	Bound required	Finite endpoints require public missing-row count, weight, and support bounds.

Appendix

Table 16: Evaluator-only audit of relaxed observation assumptions on CoraCA and DBLP4k. The 40 cells consist of five fixed partitions and

q\in\{2,3,4,5\}

for each dataset.

Figure 3: Predictive utility and cost of the heat-basis width . We fix

K=6

and

\lambda_{\mathrm{pred}}=1

on all three datasets. The

R=0

control retains masked prediction and removes diffusion.

Dataset	$R$	Accuracy (%)	Macro-F1 (%)	Parameters	Runtime (s)
CoraCA	0	70.67 $\pm$ 0.94	67.85 $\pm$ 1.64	109,319	55.0 $\pm$ 1.7
	1	73.97 $\pm$ 1.16	71.44 $\pm$ 1.58	126,407	164.9 $\pm$ 0.3
	2	76.68 $\pm$ 2.26	74.35 $\pm$ 1.96	143,495	199.8 $\pm$ 4.7
	4	73.97 $\pm$ 0.87	71.43 $\pm$ 1.12	177,671	264.6 $\pm$ 1.8
	8	73.91 $\pm$ 1.17	71.09 $\pm$ 1.24	246,023	451.5 $\pm$ 2.9
DBLP4k	0	78.66 $\pm$ 0.87	78.16 $\pm$ 0.87	38,788	54.8 $\pm$ 0.4

Appendix

Table 17: Heat-basis width at

K=6

and

\lambda_{\rm pred}=1

. Parameter counts include the online model and predictive head. Runtime uses the synchronized fitting boundary described in Appendix D .

Method	Parameters	Parameter traffic per round (MiB)	Wall-clock (s)	Roots/s	Peak GPU (GiB)
Fed-MLP	983,380	60.02	47.2	511,594	0.58
Fed-SIGN	984,442	60.09	47.6	506,887	0.68
Fed-HGNN	982,672	59.98	54.6	442,051	1.52
Fed-HNHN	34,672	2.12	312.5	77,259	0.54
Fed-HyperGCN	984,442	60.09	406.6	59,386	8.89
Fed-GCN	983,380	60.02	61.8	390,637	2.92

Appendix

Table 18: Results on full-data ogbn-papers100M under the official split. Wall-clock training time covers 20 rounds and is reported in seconds (s). Throughput counts training roots per second. Peak memory is reported in gibibytes (GiB), where

1\,\mathrm{GiB}=2^{30}

bytes. Communication counts bidirectional trainable-parameter traffic, excluding client-local BatchNorm buffers for all methods.

Hypergraph Learning

Hypergraph learning models relationships among groups of entities to capture interactions that pairwise graphs cannot represent.

See all 56 papers

Rethinking One-Shot Federated Graph Learning: Training-Free Statistical Estimation
Sep 5, 2026Shutong Zheng, Sijia ChenShrinkage Estimation Federated Graph Learning
Sun Yat-sen University · The Hong Kong University of Science and Technology (Guangzhou)
FlatLand: Personalized Graph Federated Learning via Tailored Lorentz Space
Aug 21, 2026Jiahong Liu, Ram Samarth B B, Xinyu Fu +4Federated Graph Learning Federated Learning
Department of Computer Science and Engineering, The Chinese University of Hong Kong, Hong Kong SAR, China
Latent Information Sharing for Accelerating Federated Learning
Oct 1, 2026Seungjun Lee, Ensieh Khazaei, Dimitrios Hatzinakos +2Federated Learning Aggregation Federated Learning
Inha University · University of Toronto · University of Birmingham

Sep 5, 2026J/K move · Enter open · S save

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

Shutong Zheng, Sijia Chen

Sun Yat-sen University · The Hong Kong University of Science and Technology (Guangzhou)

Shrinkage Estimation Federated Graph Learning Non-IID Federated Learning Prototype Learning

Open paper AskPDF arXiv

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 .

Abstract

Hypergraph Learning

Explore similar work

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

FlatLand: Personalized Graph Federated Learning via Tailored Lorentz Space

Latent Information Sharing for Accelerating Federated Learning