More Is Better? Exploring Latent Correspondence in Federated Hypergraph Learning

M ORE I S B ETTER ? E XPLORING L ATENT C ORRESPON DENCE IN F EDERATED H YPERGRAPH L EARNING Bo Yan1 , Siming Zhang2 , Siqi Li1 , Hang Yu2 1 Tsinghua University, 2 Shanghai University

arXiv:2610.39362v1 [cs.LG] 29 Oct 2026

A BSTRACT 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.

1

I NTRODUCTION

Federated learning enables collaborative model training without sharing data records (McMahan et al., 2017). For applications involving group-wise interactions, hypergraphs provide a natural representation of memberships in care teams, coauthor sets, and biochemical interactions (Feng et al., 2019; Chien et al., 2022; Wang et al., 2023). However, when hypergraph data are anonymized across clients, local memberships may remain observable while their cross-client correspondence is lost, making the underlying global hypergraph potentially non-identifiable from local observations alone. Consider two hospitals that share care episodes, as illustrated in Figure 1. After episode identifiers are removed, Hospital A retains anonymous records of backache and BP/ECG, while Hospital B retains records of surgery and headache/drug. Same-order matching yields compatible episodes of sizes two and four, whereas cross-order matching yields two episodes of size three. Thus, even this minimal two-client example admits distinct global compatible structures consistent with the same local observations, raising a natural question: which global hypergraph properties remain identifiable under latent hyperedge correspondence? We answer this question by establishing sharp identification bounds and computational boundaries under latent hyperedge correspondence. For two clients, the compatible global structures reduce to bipartite assignments, yielding sharp identification bounds and a double-centering criterion for point identification. Beyond two clients, correspondence becomes a multiway hypergraph-matching problem. It is NP-complete for every fixed client count above two, yet fixed-parameter tractable jointly in client count and matching size. When the client count is unbounded, it becomes W[1]-complete when parameterized only by the matching size. This characterization raises another question: when does additional cross-client information improve prediction, and when can exploiting it be detrimental? Additional information may provide useful label signal, but uncertain correspondence can also increase prediction variability and fitting error. We decompose cross-entropy risk into information gain and fitting error, yielding a sufficient condition 1

Care episode 1

backache Headache

Drug

Record 1

ECG

Surgery

(a) Complete Hyperedges

Surgery

backache Record 2

Care episode 2

BP

Record 1

BP

ECG

Record 2

Headache

Hospital A

Drug

Hospital B

(b) Higher-order Truncation

A.1

B.1

A.2

B.2

Same-order size (2,4)

Compatible ℋ𝟏 Latent correspondences

A.1

B.1

A.2

B.2

Cross-order size (3,3)

Compatible ℋ𝟐 (c) Hyperedge Aliasing

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. under which a local predictor outperforms a fitted predictor with additional information under the same evaluation law. Motivated by this tradeoff, together with the communication and privacy costs of richer cross-client exchanges (Shi et al., 2025), we introduce FedASTRA, which learns correspondence-invariant local diffusion representations through adaptive heat filtering and masked latent prediction (LeCun, 2022; Assran et al., 2023), with a client-local exponential moving-average (EMA) target and parameteronly FedAvg (McMahan et al., 2017). We show that effectively exploiting the task-relevant local information can be sufficient without resolving latent cross-client correspondences or completing the global hypergraph, yielding asymptotic optimality relative to the permitted local information. Under explicit representation and update-alignment conditions, we further establish global population-risk convergence along the implemented federated updates. Our contributions are fourfold. First, we establish sharp identification bounds and a computational hierarchy for latent hyperedge correspondence: polynomial-time two-client assignment, NP-complete yet fixed-parameter tractable matching for any fixed client count above two, and W[1]-complete matching when the client count is unbounded. Second, we characterize when additional cross-client information helps or hurts prediction through a cross-entropy decomposition that connects information gain, fitting error, prediction variation, and assignment geometry. Third, we develop FedASTRA and establish asymptotic optimality relative to the permitted local information, together with global population-risk convergence under explicit representation and update-alignment conditions. Fourth, experiments on eight real-world datasets demonstrate consistent improvements over identifier-free federated graph and hypergraph methods; on ogbn-papers100M, FedASTRA reaches the performancecommunication Pareto frontier.

2

R ELATED W ORK

Federated graph learning. Existing federated graph learning methods differ in whether crossclient graph correspondence is available. Identifier-free methods leave cross-client node identities latent (Zhang et al., 2021; Baek et al., 2023; Li et al., 2023; Fu et al., 2025), as in FedSage (Zhang et al., 2021) operating on local subgraphs, while FedSage+ (Zhang et al., 2021) generates crossclient neighbor features. Methods with explicit correspondence, such as FedGCN (Yao et al., 2023) and FedCog (Lei et al., 2023), exploit shared cross-client node or edge identities to incorporate additional graph information. For hypergraph, FedHGL (Luo et al., 2025) instead assumes shared hyperedge identifiers and utilzes local differential privacy (LDP) (Kasiviswanathan et al., 2011) to support structure completion. Despite progress, these methods trade cross-client communication and privacy exposure for predictive performance. In contrast, we study an identifier-free setting in which cross-client hyperedge correspondence is latent and only local incidence is available. 2

Hypergraph representation learning. Most hypergraph neural networks assume observed nodehyperedge memberships and focus on how to encode higher-order structure, including spectral propagation on hypergraph operators (Feng et al., 2019; Wang et al., 2023), graph-reduction approaches that approximate hyperedges with pairwise structures (Yadati et al., 2019), and direct higher-order aggregation through message passing or permutation-invariant set functions (Dong et al., 2020; Chien et al., 2022; Huang & Yang, 2021). Beyond supervised learning, self-supervised methods learn transferable hypergraph representations through multi-level contrastive learning (Lee & Shin, 2023) and generative pretext tasks (Kim et al., 2024). More recently, large-scale hypergraph pretraining and foundation models have emerged for cross-task and cross-domain transfer Gao et al. (2026). FedASTRA targets a more realistic federated scenario by learning effective representations from anonymous client-local incidence when cross-client hyperedge correspondence remains latent.

3

L EARNING D IFFICULTY UNDER L ATENT H YPEREDGE C ORRESPONDENCE

3.1

O BSERVATION MODEL

Let H = (𝑉, E, 𝑋, 𝑟, 𝑤) be a finite node-attributed, typed, weighted multihypergraph. Here 𝑉 is the node set, E is the multiset of hyperedge instances, 𝑋 is the node-feature matrix, and 𝑟 and 𝑤 collect hyperedge types and weights. hyperedge instance 𝑒 ∈ E has a support node set 𝐴𝑒 ⊆ 𝑉, a type 𝑟 𝑒 in the finite type set R, and a positive weight 𝑤 𝑒 . Multiple instances may share the same
support and type, and a type label carries no instance identity. For an integer 1 ≤ 𝑞 ≤ |𝑉 |, let 𝑉𝑞 be the collection of 𝑞-node subsets. Aggregating all hyperedge instances with the same support 𝐴 and type 𝑟, we define ∑︁ 𝑤 𝑟 ( 𝐴) = 𝑤𝑒, (1) 𝑒:𝐴𝑒 =𝐴, 𝑟𝑒 =𝑟 H 𝑀𝑞,𝑟 (𝑆) =

∑︁

𝑤 𝑟 ( 𝐴),

𝑟 ∈ R,

  𝑉 𝑆∈ . 𝑞

(2)

𝐴⊇𝑆 H (𝑆) is the weighted inclusion count of the 𝑞-node subset 𝑆 among hyperedges of type 𝑟. The Thus 𝑀𝑞,𝑟 H (𝑆)} is the invertible Boolean-zeta transform of the aggregate weights {𝑤 ( 𝐴)}. full collection {𝑀𝑞,𝑟 𝑟 In particular, the 𝑞 = 2 and 𝑞 = 3 coordinates capture observable pairwise and triple co-membership patterns before client partitioning. The notation collection is provided in Appendix B.1.

A fixed node-to-client assignment 𝑧 : 𝑉 → [𝐾], with 𝑘 ∈ [𝐾] := {1, . . . , 𝐾 }, partitions 𝑉 into local node set 𝑉𝑘 = {𝑣 ∈ 𝑉 : 𝑧(𝑣) = 𝑘 } for each client k and induces local hyperedge fragments 𝐹𝑒,𝑘 = 𝐴𝑒 ∩ 𝑉𝑘 . At a visibility threshold 𝑐 ≥ 1, client 𝑘 retains each fragment 𝐹𝑒,𝑘 with |𝐹𝑒,𝑘 | ≥ 𝑐, together with its type 𝑟 𝑒 , weight 𝑤 𝑒 , and a status indicator 𝜐𝑒,𝑘 ∈ {0, 1} specifying whether hyperedge 𝑒 is fully contained in client 𝑘. Crucially, cross-client hyperedge identifiers are withheld. Let Γ collect the public assumptions governing the observation process, including the visibility rule and any exact constraints on the number of retained fragments. Write [𝑇𝑘 ] row for the equivalence class of client 𝑘’s retained fragment table under arbitrary row permutations. The analyst release is then defined by the deterministic observation map:     𝐾 𝑌A = O𝑧,Γ (H ) = (𝑉𝑘 , 𝑋𝑉𝑘 ), (𝐹𝑒,𝑘 , 𝑟 𝑒 , 𝑤 𝑒 , 𝜐𝑒,𝑘 ) : |𝐹𝑒,𝑘 | ≥ 𝑐 row ,Γ . (3) 𝑘=1

Uppercase 𝑌A denotes the analyst release as a random element and lowercase 𝑦 A a realized release. Within the latent hypergraph class M Γ permitted by the public assumptions Γ, define the analyst compatibility class FA (𝑦 A , Γ) = {H ′ ∈ M Γ : O𝑧,Γ (H ′ ) = 𝑦 A }. (4) In contrast to the richer analyst release, the learner, representing the actual training algorithm, receives a coarsened release. Accordingly, let 𝐵 𝑘 be the binary node-fragment incidence matrix induced by 𝑇𝑘 , with one column for each row of 𝑇𝑘 . Define [𝐵 𝑘 ] col = {𝐵 𝑘 Π : Π is a column permutation} and thus arbitrary row permutations of 𝑇𝑘 correspond to column permutations 𝐵 𝑘 ↦→ 𝐵 𝑘 Π. The learner coarsened release is therefore
𝐾 𝑌L = 𝜌(𝑌A ) = (𝑋 𝑘 , [𝐵 𝑘 ] col ) 𝑘=1 , 𝑋 𝑘 := 𝑋𝑉𝑘 . (5) 3

It retains only local node features and anonymous incidence structure, omitting hyperedge types, weights, status indicators, and row identities. For a fixed training protocol P containing the released labels, task split, participation schedule, and hyperparameters, and algorithmic randomness 𝜉, any learner operating under this observation model is a measurable function of (𝑌L , P, 𝜉). In native comparisons, the same realized release is provided to all learners. For each 𝑞-node subset 𝑆, the client partition determines whether its co-membership information is retained. For 𝑞 ≥ 𝑐, we define H e𝑞,𝑟 (𝑆, 𝑧) = 𝑀𝑞,𝑟 𝑀 (𝑆)1{𝑧 is constant on 𝑆},

(6)

so the contribution of 𝑆 is retained exactly when all nodes in 𝑆 are assigned to the same client. We quantify the erased fraction by Í e 𝑟 ∈ R ∥ 𝑀𝑞,𝑟 (·, 𝑧) ∥ 1 𝜏𝑞 (H , 𝑧) = 1 − Í , (7) H 𝑟 ∈ R ∥ 𝑀𝑞,𝑟 ∥ 1 with 𝜏𝑞 (H , 𝑧) = 0 for a zero denominator. We call the erased mass higher-order truncation, as illustrated in Figure 1. Independently permuted client fragment tables may also admit multiple compatible cross-client matchings. We call this ambiguity hyperedge aliasing. These two effects can alter global higher-order statistics. We therefore consider a class of linear co-membership targets Φ𝑞, 𝜓 . For any finite type-indexed test function 𝜓𝑞,𝑟 , define ∑︁ ∑︁ Φ𝑞, 𝜓 (H ) = 𝑤𝑒 𝜓𝑞,𝑟𝑒 (𝑆, 𝑋𝑆 ). (8) 𝑒∈ E 𝑆 ∈ ( 𝐴𝑞𝑒 ) Here, 𝜓𝑞,𝑟 (𝑆, 𝑋𝑆 ) specifies the contribution of each 𝑞-node subset 𝑆, allowing Φ𝑞, 𝜓 to cover both total order-𝑞 co-membership mass and more general feature-dependent higher-order statistics. Equation (7) quantifies the co-membership mass loss under a fixed partition. Appendices B.2, C.5– C.6 give the Boolean-zeta inversion and show how the co-membership quantities can be estimated under a randomized partition using Horvitz-Thompson estimation (Horvitz & Thompson, 1952). 3.2

E XACT TWO - CLIENT COMPATIBILITY SETS

Two clients form the smallest nontrivial setting with an exact correspondence analysis. We use the richer analyst release with observed status indicators 𝜐𝑒,𝑘 , and exact type 𝑟 and weight 𝜔, together with 𝑐 = 1 and equal numbers of retained fragment rows across the two clients. Thus, each crossclient hyperedge leaves one nonempty row per client. Let 𝑚 ℎ denote the common row count in stratum ℎ = (𝑟, 𝜔). Within stratum ℎ, fragments 𝐹1𝑖ℎ ⊆ 𝑉1 and 𝐹2ℎ𝑗 ⊆ 𝑉2 , indexed by 𝑖, 𝑗 ∈ [𝑚 ℎ ], are matched by an unobserved 𝜛ℎ ∈ Sym(𝑚 ℎ ), the symmetric group on [𝑚 ℎ ]. Let Φobs collect the client-local and within-fragment contributions that are invariant across all compatible matchings. For a candidate cross-client pair (𝐹1𝑖ℎ , 𝐹2ℎ𝑗 ), the mixed matching-dependent contribution is ∑︁ 𝐶𝑖ℎ𝑗 = 𝜔 𝜓𝑞,𝑟 (𝑆, 𝑋𝑆 ). (9) 𝐹 ℎ ∪𝐹 ℎ

𝑆 ∈ ( 1𝑖 𝑞 2 𝑗 ) : ℎ ≠∅, 𝑆∩𝐹 ℎ ≠∅ 𝑆∩𝐹1𝑖 2𝑗

The cost matrix 𝐶 ℎ exposes exactly which part of the target Φ𝑞, 𝜓 depends on the missing correspondence. Define the identified set of Φ𝑞, 𝜓 under the analyst release as its attainable values over all compatible latent hypergraphs: I𝑞, 𝜓 (𝑦 A ) = {Φ𝑞, 𝜓 (H ′ ) : H ′ ∈ FA (𝑦 A , Γ)}. Theorem 1 (Compatible target values under an unobserved permutation). Assume 𝐾 = 2, 𝑐 = 1, observed status indicators, exactly one nonempty cross fragment at each client for every cross-client hyperedge, exact type-and-weight strata, and equal row counts within every stratum. Then the compatible values and their sharp endpoints are ( ) 𝑚ℎ ∑︁ ∑︁ ℎ I𝑞, 𝜓 (𝑦 A ) = Φobs + 𝐶𝑖, 𝜛ℎ (𝑖) : 𝜛ℎ ∈ Sym(𝑚 ℎ ) , (10) ℎ − Φ𝑞, 𝜓 = Φobs +

∑︁ ℎ

𝑖=1

min ⟨𝐶 ℎ , Λ⟩𝐹 ,

Λ∈B𝑚ℎ

Φ+𝑞, 𝜓 = Φobs +

∑︁ ℎ

4

max ⟨𝐶 ℎ , Λ⟩𝐹 ,

Λ∈B𝑚ℎ

(11)

where B𝑚 = {Λ ∈ R+𝑚×𝑚 : Λ1 = 1, Λ⊤ 1 = 1} is the Birkhoff polytope and ⟨𝐴, 𝐵⟩𝐹 = tr( 𝐴⊤ 𝐵) is the Frobenius inner product. Each condition below characterizes point identification within a stratum, independently of the probability distribution over matchings compatible with the observed release: 𝐽𝑚ℎ 𝐶 ℎ 𝐽𝑚ℎ = 0, 𝐶𝑖ℎ𝑗 = 𝛼𝑖ℎ + 𝛽 ℎ𝑗 , 𝐶𝑖ℎ𝑗 + 𝐶𝑖ℎ′ 𝑗 ′ − 𝐶𝑖ℎ𝑗 ′ − 𝐶𝑖ℎ′ 𝑗 = 0 for all 𝑖, 𝑖 ′ , 𝑗, 𝑗 ′ ∈ [𝑚 ℎ ],

(12) (13) (14)

with centering matrix 𝐽𝑚 = 𝐼𝑚 − 11⊤ /𝑚 and vectors 𝛼 ℎ , 𝛽 ℎ ∈ R𝑚ℎ in Equation (13). Each compatible assignment selects one entry from every row and column of 𝐶 ℎ , thereby forming a permutation matrix. By Birkhoff-von Neumann integrality Birkhoff (1946), both endpoints are attainable. Double centering in Equation (12) removes additive row and column effects, leaving only the interaction that can vary with the latent correspondence, in a subspace of dimension at most (𝑚 ℎ − 1) 2 . Equation (14) checks whether any such interaction remains. Appendix C.1 gives the proof and dual certificates. Appendix B.3 further discusses weaker observation assumptions. Coarsening the analyst release enlarges the compatible class. Hence, if 𝜙 − and 𝜙+ are attainable endpoints under the richer release, any randomized scalar estimator using the coarser learner release has worst-case absolute risk at least (𝜙+ − 𝜙 − )/2 (Appendix C.7). This diagnostic uses two clients, while model training uses 𝐾 ∈ {3, 6, 9} and correspondence-invariance result holds for any 𝐾. Prediction can still be accurate when the local label signal survives unresolved global structure. Graph Í matching versus hypergraph matching. Total order-𝑞 mass admits sharp sorting bounds in 𝑂 ( ℎ 𝑚 ℎ log 𝑚 ℎ ) time (Appendices C.2–C.3). To isolate relation size, consider 𝐾 clients with 𝑚 distinct singleton rows each and explicitly listed rewarded tuples E+ ⊆ [𝑚] 𝐾 . Each listed tuple has reward one, all others zero. A completion with at least 𝑏 rewarded relations exists exactly when these candidate 𝐾-node hyperedges contain a matching of size 𝑏. For 𝐾 = 2, this is polynomial bipartite graph matching. For fixed 𝐾 ≥ 3, it is complete for nondeterministic polynomial time (NP-complete) but fixed-parameter tractable (FPT) in 𝐾 𝑏, meaning time 𝑓 (𝐾 𝑏) poly(𝐿 in ) for input length 𝐿 in . With unbounded 𝐾, it is complete for W[1], the first level of the W hierarchy, in 𝑏 (Appendix C.4). This separates pairwise from multiway correspondence under the same observation and reward rules, independently of the optimization difficulty of a neural classifier.

4

B ENEFIT B OUNDS OF A DDITIONAL I NFORMATION

Given these fundamental identifiability and computational challenges under hyperedge correspondence, a natural thought is to exploit more information beyond local observations for better prediction. Yet a subtle tradeoff arises here: additional information can reveal label signal, while correspondence uncertainty can induce prediction variation and fitting error. In other words, its benefit is bounded. In this section, we characterize these benefit bounds through cross-entropy decomposition. Information value and fitting cost. For class 𝑦 ∈ [𝐶] = {1, . . . , 𝐶}, 𝐶 ≥ 2, predictor 𝐹 uses S0 : client attributes, anonymous incidence, and the parameter-only transcript through validation, excluding held-out labels. Predictor 𝐺 additionally uses 𝐴aux and its derived training states, giving S1 = S0 ∨ 𝜎( 𝐴aux ). Let 𝑝 𝑖 = Pr(𝑦 = Í · | S𝑖 ), 𝑖 = 0, 1, and 𝑞 𝐹 , 𝑞 𝐺 be their predictions. Kullback– Leibler (KL) divergence 𝐷 KL ( 𝑝∥𝑞) = 𝑐 𝑝 𝑐 log( 𝑝 𝑐 /𝑞 𝑐 ) yields the information and fitting terms Iadd = E𝐷 KL ( 𝑝 1 ∥ 𝑝 0 ), E 𝐹 = E𝐷 KL ( 𝑝 0 ∥𝑞 𝐹 ), E𝐺 = E𝐷 KL ( 𝑝 1 ∥𝑞 𝐺 ), (15) Then Iadd can measure new label information and E 𝐹 , E𝐺 measure fitting error to the respective optima. For measurable predictions with finite log risk R log (𝑞) = E[− log 𝑞 𝑦 ], conditional entropy yields the exact risk decomposition below, whose derivation is given in Appendix C.10: R log (𝑞 𝐺 ) − R log (𝑞 𝐹 ) = E𝐺 − E 𝐹 − Iadd . (16) |{z} | {z } difference in fitting error

additional label information

Thus 𝐹 has strictly lower risk exactly when E𝐺 − E 𝐹 > Iadd , with the reverse strict inequality favoring 𝐺. Additional information weakly improves ideal risk because it can be ignored (Blackwell, 1953). For fitted models, however, its gain competes with approximation, estimation, and optimization errors. When 𝑝 1 = 𝑝 0 , fitting quality alone determines which predictor has lower risk. 5

How correspondence creates a prediction cost. To quantify this cost, remove the class mean from enriched logits 𝑠𝐺 ∈ R𝐶 and set 𝑠¯𝐺 = E[𝑠𝐺 | S0 ]. For cross-entropy risk R CE (𝑠) = R log (softmax(𝑠)) and finite-risk local logits 𝑠 𝐹 , define 𝑉aux = E∥𝑠𝐺 − 𝑠¯𝐺 ∥ 22 , Δlabel = E∥ 𝑝 1 − 𝑝 0 ∥ 22 , and 𝛿 𝐹 = R CE (𝑠 𝐹 ) − R CE ( 𝑠¯𝐺 ). Under ∥𝑠𝐺 ∥ ∞ ≤ 𝐵logit < ∞ almost surely, Theorem 6 gives √︁ 𝑒 −2𝐵logit 𝑉aux > Δlabel𝑉aux + 𝛿 𝐹 2𝐶

=⇒

R CE (𝑠𝐺 ) > R CE (𝑠 𝐹 ).

(17)

Hence local prediction has lower risk when variation cost exceeds the label-alignment bound plus the signed fitting gap. The criterion is sufficient, since Cauchy–Schwarz bounds label alignment. When Δlabel = 0 and 𝛿 𝐹 ≤ 0, any 𝑉aux > 0 certifies a strict local advantage. Moreover, Proposition 5 computes this variation from the double-centered matching costs of Theorem 1 for affine logits under independent uniform matchings, linking the identification result to this prediction-risk comparison. Communication and privacy boundary. Additional exchanges incur communication costs and can expose sensitive information (Shi et al., 2025). Parameter-only exchange avoids these auxiliary disclosures, although model updates still require protection against information leakage.

5

F EDASTRA: L EARNING FROM L OCAL S TRUCTURE

Section 4 yields a design principle: local prediction can outperform a fitted richer-information model when its fitting cost exceeds the label-information gain. Guided by this principle, F EDASTRA stays within the observable local release: it learns diffusion scales from anonymous incidence, predicts masked representations, and communicates parameters only, eliminating the need for cross-client pairing. Under probabilistic recovery and approximation conditions, FedASTRA is asymptotically optimal relative to permitted local information. Under representation and task-alignment conditions, its actual updates achieve global population-risk convergence with an 𝑂 (1/𝑇) optimization term. Learning diffusion scales. For binary incidence 𝐵 𝑘 with nonempty columns, let 𝐷 𝑣,𝑘 = diag(𝐵 𝑘 1), 𝐷 𝑒,𝑘 = diag(𝐵⊤𝑘 1), and 𝐼0,𝑘 = diag(1{(𝐷 𝑣,𝑘 ) 𝑣𝑣 = 0}). Using the Moore–Penrose inverse †, define the node-to-node transition on these observed local memberships by −1 ⊤ 𝑃 𝑘 = 𝐷 †𝑣,𝑘 𝐵 𝑘 𝐷 𝑒,𝑘 𝐵 𝑘 + 𝐼0,𝑘 .

(18)

This walk averages over incident relations and their members, leaving isolated nodes fixed (Zhou et al., 2006). For latent width 𝑑, encode 𝑈 𝑘 = 𝐸 𝜃enc (𝑋 𝑘 ) ∈ R |𝑉𝑘 | ×𝑑 and use 𝑅 ≥ 0 positive-time channels with increments 𝜂 ∈ R𝑅×𝑑 . The context parameters 𝜗 = ctx(𝜃) = (𝜃 enc , 𝜂) belong to the online state 𝜃. The positive floor 𝜖ord > 0 orders each coordinate’s diffusion times: ∞ ∑︁ 𝑡ℓ K 𝑘 (𝑡) = exp{𝑡 (𝑃 𝑘 − 𝐼)} = 𝑒 −𝑡 𝑃ℓ𝑘 , 𝑡 ≥ 0, (19) ℓ! ℓ=0 𝑡𝑏 𝑗 =

𝑏 ∑︁

{softplus(𝜂 𝑎 𝑗 ) + 𝜖 ord },

𝑏 ∈ [𝑅],

𝑗 ∈ [𝑑],

(20)

𝑎=1

[K 𝑘 (𝒕 𝑏 )𝑈 𝑘 ] : 𝑗 := K 𝑘 (𝑡 𝑏 𝑗 )𝑈 𝑘,: 𝑗 ,

𝑊 𝑘 (𝑋 𝑘 | 𝜗) = [ 𝑈 𝑘 , K 𝑘 (𝒕 1 )𝑈 𝑘 , . . . , K 𝑘 (𝒕 𝑅 )𝑈 𝑘 ].

(21)

Each channel mixes walk lengths with Poisson weights (Kondor & Lafferty, 2002), while 𝑅 = 0 retains only 𝑈 𝑘 . Each 𝑡 𝑏 𝑗 is the expected walk length for coordinate 𝑗. Learning these times adapts the extent of local mixing, while the undiffused channel retains the original encoded attributes. Thus 𝑅 controls scales, independently of observation order 𝑞. Write 𝑊 𝑘, 𝜃 (𝑋) = 𝑊 𝑘 (𝑋 | ctx(𝜃)). Column relabeling preserves both features and coupled training updates. Appendices C.8–C.9 prove stability and give a shared recurrence with Poisson-tail error control for each learned diffusion time. Local prediction and federation. Two masked views predict a full-view exponential moving average (EMA) target through Lpred,k , combining cosine alignment, variance–covariance regularization, and view agreement (Appendix D.1). For classifier 𝑐 𝜃𝑘 : R (𝑅+1) 𝑑 → R𝐶 , context 𝜗𝑘 = ctx(𝜃 𝑘 ), labeled set V𝑘tr of size 𝑛tr𝑘 > 0, and predictive weight 𝜆pred ≥ 0, the local training objective is ∑︁ L 𝑘 = (𝑛tr𝑘 ) −1 CE(𝑐 𝜃𝑘 (𝑊 𝑘 (𝑋 𝑘 | 𝜗𝑘 ) 𝑣 ), 𝑦 𝑣 ) + 𝜆 pred Lpred,𝑘 . (22) tr 𝑣 ∈ V𝑘

6

Algorithm 1 FedASTRA with an ordered client-local diffusion basis Require: Rounds 𝑇, steps 𝑆loc , clients C𝑢 ⊆ [𝐾], counts 𝑛tr𝑘 , weight 𝜆pred , momentum 𝜇. 1: Initialize 𝜃 0 and client-local operators 𝑃 𝑘 . 2: for 𝑢 = 0, . . . , 𝑇 − 1 do 3: for 𝑘 ∈ C𝑢 in parallel do 4: Set 𝜃 𝑘 ← 𝜃 𝑢 and 𝜗¯ 𝑘 ← ctx(𝜃 𝑘 ). 5: Repeat 𝑆loc times: update 𝜃 𝑘 on Equation (22), then set 𝜗¯ 𝑘 ← 𝜇 𝜗¯ 𝑘 + (1 − 𝜇) ctx(𝜃 𝑘 ). 6: Return 𝜃 𝑢+1 ← 𝜃 𝑘 and discard the target. 𝑘 7: end for Í 𝑛tr 𝜃 𝑢+1 8: 𝜃 𝑢+1 ← 𝑘Í∈C𝑢 𝑘 𝑛tr𝑘 . 𝑘 ∈C𝑢

𝑘

9: end for 10: Select one validation checkpoint and evaluate test data once.

Here CE is cross-entropy for 𝑦 𝑣 ∈ [𝐶]. Algorithm 1 updates target 𝜗¯ 𝑘 with momentum 𝜇 ∈ [0, 1) and transmits only online parameters, weighted by each client’s number of labeled training nodes. Local information and optimal prediction. Under the rank, attribute, and incidence-recovery conditions of Theorem 7 in Appendix C.11, the optimal cross-entropy gap between the complete heat representation and local information is 𝑂 (𝜀 𝑛 log(1/𝜀 𝑛 )), where 𝜀 𝑛 → 0 bounds joint failure on 𝑛 nodes. On successful recovery, the complete heat representation determines the permitted local release. The residual risk bound accounts for decoder failure through its binary entropy and the finite label alphabet. Thus any local prediction rule can be reproduced on the event of successful recovery. pop

From client risks to federated risk. Let 𝑤 𝑘 be test-client probabilities and R fed their weighted Í cross-entropy. For the model b 𝜃 selected after 𝑇 rounds on 𝑁 = 𝑘 𝑛tr𝑘 labels, Theorem 8 gives " # " # ∑︁ ∑︁ pop ∗ pop b E R fed ( 𝜃) − 𝑤 𝑘 R loc,𝑘 ≤ E 𝑤 𝑘 (𝑑 𝑘 + 𝑎 𝑘 ) + 𝑎 share + 2𝑢 𝑁 + 𝑒 𝑁 ,𝑇 . (23) 𝑘

𝑘

∗ Here R loc,𝑘 is client 𝑘’s optimal local-information risk. The terms 𝑑 𝑘 , 𝑎 𝑘 , 𝑎 share measure information loss, local approximation error, and shared-parameter cost. Finally, 𝑢 𝑁 bounds expected uniform

training-to-population discrepancy, and 𝑒 𝑁 ,𝑇 bounds empirical optimization error, addressed next. Global convergence along the implemented updates. Let 𝐽 𝑁 be evaluation-mode training crossentropy on domain Θ, convex in the final affine head at fixed features. After round 𝑢 0 , assume each representation admits a head within distance 𝐷 cls > 0 of the current head and loss at most inf Θ 𝐽 𝑁 + 𝑎 ctx , with 𝑎 ctx ≥ 0. If the actual-update decrease bound (Proposition 9) is at least 𝛾 > 0 times the squared head-gradient norm, Theorem 9 bounds 𝑒 𝑁 ,𝑇 = E[𝐽 𝑁 ( b 𝜃) − inf Θ 𝐽 𝑁 ] by " # 𝐷 2cls 𝑒 𝑁 ,𝑇 ≤ E 𝑎 ctx + + 𝑠sel 𝑇 > 𝑢0 . (24) 𝑁 ,𝑇 , 𝛾(𝑇 − 𝑢 0 ) 𝑇 b Here 𝑠sel 𝑁 ,𝑇 = [𝐽 𝑁 ( 𝜃) − 𝐽 𝑁 (𝜃 )] + accounts for validation selection, with [𝑥] + = max{𝑥, 0}. Substitution into Equation (23) gives the population-risk bound. For fixed 𝑢 0 and uniformly bounded E[𝐷 2cls /𝛾], the optimization term is 𝑂 (1/𝑇). Vanishing residual terms then give local-information Bayes consistency. Appendix C.12 also covers imperfect update alignment.

6

E XPERIMENTS

We evaluate FedASTRA through four research questions (RQ1-RQ4) concerning predictive performance, mechanism validation, information access, and scalability: • RQ1: How effective is FedASTRA on identifier-free native hypergraphs? • RQ2: Do the empirical results support the proposed analysis and FedASTRA’s design? • RQ3: How does FedASTRA compare under different information-access settings? • RQ4: Can FedASTRA scale to large real-world hypergraphs without sampling? 7

Additional experimental settings and results are provided in Appendices D and E, respectively. Datasets. We evaluate two groups of datasets. (1) Native hypergraph datasets including CoraCA coauthorship, DBLP4k bibliographic, IMDB4k movie, and Trivago hotel-session data (Yadati et al., 2019; Sun et al., 2011; Fu et al., 2020; Feng et al., 2019; Gao et al., 2023; Li et al., 2026). (2) Graph datasets including Cora and CiteSeer citation networks, the Facebook Page-Page social network (Yang et al., 2016; Rozemberczki et al., 2021), and the large-scale ogbn-papers100M dataset (Hu et al., 2020). Appendix D.3 details the datasets. Baselines. We consider two groups of baselines. (1) Federated adaptations (FedAvg (McMahan et al., 2017)) of native-hypergraph methods, including Fed-HGNN (HGNN (Feng et al., 2019)), Fed-HNHN (HNHN (Dong et al., 2020)), Fed-HyperGCN (HyperGCN (Yadati et al., 2019)), Fed-AllDeepSets (DeepSets (Zaheer et al., 2017)), Fed-AllSetTransformer (AllSet (Chien et al., 2022)), Fed-UniGCNII (UniGCNII (Huang & Yang, 2021)) and Fed-ED-HNN (ED-HNN (Wang et al., 2023)). (2) Federated graph learning methods with different levels of cross-client information access, including FedSage with no access and FedSage+ with generated information (Zhang et al., 2021), FedGCN (Yao et al., 2023) and FedCog (Lei et al., 2023) with direct access to correspondence. Details of baselines are presented in Appendix D.4. Implementation Details. Fed-HNHN uses the configuration reported by FedHGL (Luo et al., 2025), and Fed-HyperGCN uses the local HyperGCN projection. FedASTRA uses two masks, a local EMA target, and parameter-only FedAvg (McMahan et al., 2017; Kingma & Ba, 2015). Results are averaged over five runs, except three for Fed-HNHN and all Trivago-related experiments. We report node classification accuracy (Acc.) and Macro-F1. The nodes are partitioned across 𝐾 ∈ {3, 6, 9} clients using class-conditioned Dirichlet sampling (Luo et al., 2025). All methods follow the same data splits and training and evaluation protocols. Appendix D details the experimental protocols. RQ1: performance on identifier-free native hypergraphs. As shown in Table 1, FedASTRA achieves the best Accuracy and Macro-F1 across all four hypergraph datasets from distinct domains, especially on CoraCA, outperforming the baseline by 6.5 and 8.5 percentage points, respectively. The consistent cross-domain gains support FedASTRA’s correspondence-invariant design, which avoids global structure recovery while approaching the optimum permitted by local information under the stated conditions. In contrast, direct FedAvg adaptations of traditional hypergraph models may under-exploit local information when global structure is fragment. More detailed results under different number of clients are reported in Appendix E.1. Table 1: Performance on identifier-free native hypergraphs. Results are averaged over 𝐾 ∈ {3, 6, 9}. Method

CoraCA Acc. (%) Macro-F1 (%)

Fed-HGNN 68.64 ± 1.45 Fed-HNHN 54.73 ± 1.17 Fed-HyperGCN 64.02 ± 1.64 Fed-AllDeepSets 39.63 ± 1.83 Fed-AllSetTransformer 30.22 ± 0.00 Fed-UniGCNII 59.54 ± 1.31 Fed-ED-HNN 59.62 ± 1.65 FedASTRA 75.17 ± 0.42

64.35 ± 1.71 50.42 ± 1.76 58.07 ± 1.95 27.08 ± 2.04 6.63 ± 0.00 50.11 ± 3.86 53.28 ± 2.30 72.88 ± 0.60

DBLP4k Acc. (%) Macro-F1 (%) 77.63 ± 1.35 69.58 ± 1.18 72.69 ± 0.77 39.35 ± 0.55 30.99 ± 1.29 77.35 ± 2.26 72.10 ± 2.54 79.22 ± 0.98

76.98 ± 1.18 68.79 ± 1.12 71.46 ± 0.86 32.45 ± 1.71 21.81 ± 0.86 75.98 ± 2.60 71.36 ± 2.55 78.61 ± 0.80

IMDB4k Acc. (%) Macro-F1 (%) 48.85 ± 1.29 44.96 ± 1.50 44.14 ± 1.16 40.32 ± 1.15 37.04 ± 0.05 41.62 ± 0.74 43.46 ± 0.89 51.13 ± 0.97

48.59 ± 1.23 43.05 ± 1.24 40.86 ± 2.38 34.12 ± 2.20 18.10 ± 0.07 30.57 ± 3.32 36.58 ± 1.05 51.06 ± 0.77

Trivago Acc. (%) Macro-F1 (%) 21.85 ± 0.19 25.68 ± 1.02 9.17 ± 0.20 10.88 ± 0.15 8.99 ± 0.00 9.15 ± 0.13 9.19 ± 0.29 29.09 ± 1.19

4.27 ± 0.20 7.72 ± 0.24 0.13 ± 0.02 0.27 ± 0.01 0.10 ± 0.00 0.15 ± 0.03 0.13 ± 0.03 7.96 ± 0.10

RQ2: validation on proposed analysis and mechanism. We first validate the proposed identification analysis through two-client audits. Among 120 evaluated cells, no higher-order co-membership target is point identified, and the median endpoint-hull width increases from 36.37% at 𝑞 = 2 to 93.71% at 𝑞 = 5. Type coarsening preserves endpoint containment in all 40 audited cells, while 32 column permutations leave 𝑃 𝑘 , heat features, and logits unchanged. These results confirm the predicted ambiguity under latent correspondence and the correspondence-invariant property of the learner representation. Higher-order truncation exhibits different predictive trends across datasets, indicating that its impact depends on how the lost higher-order structure aligns with task-relevant signal. Complete audit configurations and results are reported in Appendix E.3. For mechanism ablations, we evaluate heat-basis width 𝑅 ∈ {0, 1, 2, 4, 8} and the masked prediction objective. Figure 2 shows that removing diffusion (𝑅 = 0) degrades performance, while moderate heat widths improve accuracy. Removing the predictive objective (𝜆 𝑝𝑟 𝑒𝑑 = 0) also consistently reduces performance, demonstrating its complementary role in FedASTRA. Complete results are reported in Appendix E.3. 8

CoraCA

DBLP4k

84 82 80 78 76 74

82 Accuracy (%)

CoraCA

78 74 70 66 0

1

2

4

Heat channels R

8

DBLP4k

78

81

74

80 79

0

1

2

4

Heat channels R

8

70

78

66

77 (1, 0) (1, 1) (4, 0) (4, 1)

(1, 0) (1, 1) (4, 0) (4, 1)

Each tuple denotes (R, λpred)

Each tuple denotes (R, λpred)

Figure 2: Ablation study on the adaptive diffusion (left) and the masked prediction (right). RQ3: performance against baselines with varying information access. We empirically contrast the information-access regimes discussed in Section 4, as depicted in Table 2. FedASTRA outperforms FedSage and FedGCN (0-hop), which use only local information, and also surpasses FedSage+, despite the latter using additional communication to generate cross-client information. Although FedGCN (2-hop) and FedCog are stronger under a different setting with known correspondence, the gap is substantially narrowed, suggesting that the remaining gap is not solely missing cross-client information, but also how effectively the local structure is represented and exploited. The stable performance of FedASTRA as the client number grows further indicates that stronger local modeling can partially offset increasing structural information loss. Appendix E.2 provides complete metrics, information-access details, and traffic accounting. 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

𝐾 =3

Cora 𝐾 =6

𝐾 =9

𝐾 =3

CiteSeer 𝐾 =6

𝐾 =9

𝐾 =3

Facebook 𝐾 =6

𝐾 =9

FedSage 70.35 ± 1.96 63.18 ± 0.97 58.65 ± 1.85 65.08 ± 0.96 63.73 ± 0.74 62.93 ± 1.72 72.63 ± 0.73 65.64 ± 1.81 60.41 ± 1.61 FedGCN (0-hop) 74.07 ± 1.57 65.90 ± 2.05 62.07 ± 1.79 68.68 ± 1.50 65.83 ± 0.56 65.14 ± 1.80 75.14 ± 0.95 67.87 ± 1.71 64.30 ± 1.22 FedSage+ 69.67 ± 0.71 63.11 ± 1.66 61.02 ± 1.40 63.16 ± 1.17 62.53 ± 1.66 62.95 ± 1.62 68.17 ± 0.33 61.85 ± 0.95 58.56 ± 1.33 FedGCN (2-hop) 84.05 ± 1.17 84.05 ± 1.16 84.12 ± 0.92 72.20 ± 1.44 72.27 ± 1.53 72.38 ± 1.50 83.21 ± 0.76 82.84 ± 0.50 82.73 ± 0.85 FedCog 84.29 ± 1.50 84.34 ± 1.06 83.92 ± 0.78 72.21 ± 1.49 72.38 ± 1.04 72.51 ± 1.42 82.46 ± 0.69 82.50 ± 0.84 82.15 ± 0.94 FedASTRA 77.54 ± 1.08 74.45 ± 1.60 73.33 ± 1.22 67.61 ± 2.32 68.00 ± 1.86 67.92 ± 1.88 76.88 ± 1.44 75.57 ± 0.94 75.12 ± 1.49

Average communication traffic Model/round Auxiliary/run 4.82 2.41 4.82 2.41 2.41 13.53

0 0 17314.45 673.79 752.27 0

RQ4: scalability on large-scale data. We evaluate FedASTRA on ogbn-papers100M after local onehop lifting, as summarized in Table 3. We also include Fed-MLP, Fed-GCN (Kipf & Welling, 2017), and Fed-SIGN (Frasca et al., 2020) as baselines. FedASTRA outperforms the strongest baseline by up to 9.69 percentage points under comparable communication overhead. Its scalability stems from the correspondence-free local diffusion design and the strong performance further suggests that adaptive diffusion can better exploit local structures. Appendix E.4 details the results. 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. Method Fed-MLP Fed-SIGN Fed-HGNN Fed-HNHN Fed-HyperGCN Fed-GCN FedASTRA

7

Acc. (%) Macro-F1 (%) #Parameters Parameter trafffic/round 33.61 38.42 31.04 35.93 40.38 39.70 50.07

13.74 16.56 9.97 13.46 21.44 17.40 29.73

983,380 984,442 982,672 34,672 984,442 983,380 976,504

60.02 60.09 59.98 2.12 60.09 60.02 59.60

C ONCLUSION

We establish identification and computational boundaries for latent hyperedge correspondence and quantify when fitting costs outweigh the benefit of additional information. FedASTRA combines invariant local diffusion, masked prediction, and parameter-only communication. Under stated assumptions, information-preservation and global risk bounds connect observable memberships to prediction. Results on native hypergraphs, federated subgraphs, and large-scale ogbn-papers100M data support this approach under explicit information-access and communication constraints. 9

R EFERENCES Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844–856, 1995. Mahmoud Assran, Quentin Duval, Ishan Misra, Piotr Bojanowski, Pascal Vincent, Michael Rabbat, Yann LeCun, and Nicolas Ballas. Self-supervised learning from images with a joint-embedding predictive architecture. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 15619–15629, 2023. doi: 10.1109/CVPR52729.2023.01499. URL https://openaccess.thecvf.com/content/CVPR2023/html/Assran_ Self-Supervised_Learning_From_Images_With_a_Joint-Embedding_ Predictive_Architecture_CVPR_2023_paper.html. Jinheon Baek, Wonyong Jeong, Jiongdao Jin, Jaehong Yoon, and Sung Ju Hwang. Personalized subgraph federated learning. In ICML, volume 202 of Proceedings of Machine Learning Research, pp. 1396–1415. PMLR, 2023. Yikun Bai, Rocio Diaz Martin, Abihith Kothapalli, Hengrong Du, Xinran Liu, and Soheil Kolouri. Partial gromov-wasserstein metric. In The Thirteenth International Conference on Learning Representations, 2025. URL https://proceedings.iclr.cc/paper_files/paper/2025/ hash/3322a9a72a1707de14badd5e552ff466-Abstract-Conference.html. Garrett Birkhoff. Tres observaciones sobre el álgebra lineal. Universidad Nacional de Tucumán, Revista A, 5:147–151, 1946. David Blackwell. Equivalent comparisons of experiments. The Annals of Mathematical Statistics, 24(2):265–272, 1953. doi: 10.1214/aoms/1177729032. URL https://doi.org/10.1214/ aoms/1177729032. Guy Bresler, Chenghao Guo, and Yury Polyanskiy. Thresholds for reconstruction of random hypergraphs from graph projections. In Shipra Agrawal and Aaron Roth (eds.), Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pp. 632–647. PMLR, 30 Jun–03 Jul 2024. URL https://proceedings.mlr. press/v247/bresler24a.html. Guy Bresler, Chenghao Guo, Yury Polyanskiy, and Andrew Yao. Partial and exact recovery of a random hypergraph from its graph projection. In Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pp. 534–593. PMLR, 2025. URL https://proceedings.mlr.press/v291/bresler25a.html. Shuxiao Chen, Edgar Dobriban, and Jane H. Lee. A group-theoretic framework for data augmentation. Journal of Machine Learning Research, 21(245):1–71, 2020. URL https://www.jmlr.org/ papers/v21/20-163.html. Yang Chen, Cong Fang, Zhouchen Lin, and Bing Liu. Relational learning in pre-trained models: A theory from hypergraph recovery perspective. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 6666–6698. PMLR, 21–27 Jul 2024. URL https://proceedings. mlr.press/v235/chen24l.html. Eli Chien, Chao Pan, Jianhao Peng, and Olgica Milenkovic. You are AllSet: A multiset function framework for hypergraph neural networks. In The Tenth International Conference on Learning Representations, 2022. URL https://openreview.net/forum?id=hpBTIv2uy_E. Samir Chowdhury, Tom Needham, Ethan Semrad, Bei Wang, and Youjia Zhou. Hypergraph cooptimal transport: Metric and categorical properties. Journal of Applied and Computational Topology, 8(5):1171–1230, 2024. doi: 10.1007/s41468-023-00142-9. URL https://doi. org/10.1007/s41468-023-00142-9. Yihe Dong, Will Sawin, and Yoshua Bengio. HNHN: Hypergraph networks with hyperedge neurons. arXiv preprint arXiv:2006.12278, 2020. URL https://arxiv.org/abs/2006.12278. Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness II: on completeness for W[1]. Theor. Comput. Sci., 141(1&2):109–131, 1995. 10

Ivan P. Fellegi and Alan B. Sunter. A theory for record linkage. Journal of the American Statistical Association, 64(328):1183–1210, 1969. doi: 10.1080/01621459.1969.10501049. URL https: //doi.org/10.1080/01621459.1969.10501049. Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. Hypergraph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3558–3565, 2019. doi: 10.1609/aaai.v33i01.33013558. URL https://ojs.aaai.org/index.php/AAAI/ article/view/4235. Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Benjamin Chamberlain, Michael Bronstein, and Federico Monti. SIGN: Scalable inception graph neural networks. In ICML 2020 Workshop on Graph Representation Learning and Beyond, 2020. URL https://arxiv.org/abs/2004. 11198. Lele Fu, Bowen Deng, Sheng Huang, Tianchi Liao, Shirui Pan, and Chuan Chen. Less is more: Federated graph learning with alleviating topology heterogeneity from A causal perspective. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pp. 17727–17745. PMLR, 2025. URL https: //proceedings.mlr.press/v267/fu25a.html. Xinyu Fu, Jiani Zhang, Ziqiao Meng, and Irwin King. MAGNN: Metapath aggregated graph neural network for heterogeneous graph embedding. In Proceedings of The Web Conference 2020, pp. 2331–2341. ACM, 2020. doi: 10.1145/3366423.3380297. URL https://doi.org/10. 1145/3366423.3380297. Yue Gao, Yifan Feng, Shuyi Ji, and Rongrong Ji. HGNN+: General hypergraph neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(3):3181–3199, 2023. doi: 10.1109/ TPAMI.2022.3182052. URL https://doi.org/10.1109/TPAMI.2022.3182052. Yue Gao, Yifan Feng, Shiquan Liu, Xiangmin Han, Shaoyi Du, Zongze Wu, and Han Hu. Hypergraph foundation model. IEEE Trans. Pattern Anal. Mach. Intell., 48(4):4063–4080, 2026. Daniel G. Horvitz and Donovan J. Thompson. A generalization of sampling without replacement from a finite universe. Journal of the American Statistical Association, 47(260):663–685, 1952. doi: 10.1080/01621459.1952.10483446. Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Advances in Neural Information Processing Systems, volume 33, 2020. URL https://proceedings.neurips.cc/paper_files/paper/2020/ hash/fb60d411a5c5b72b2e7d3527cfc84fd0-Abstract.html. Jing Huang and Jie Yang. UniGNN: A unified framework for graph and hypergraph neural networks. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, pp. 2563–2569, 2021. doi: 10.24963/ijcai.2021/353. URL https://www.ijcai.org/ proceedings/2021/0353.pdf. Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher (eds.), Complexity of Computer Computations, pp. 85–103. Plenum Press, 1972. doi: 10.1007/978-1-4684-2001-2_9. URL https://doi.org/10.1007/ 978-1-4684-2001-2_9. Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. What can we learn privately? SIAM J. Comput., 40(3):793–826, 2011. Sunwoo Kim, Shinhwan Kang, Fanchen Bu, Soo Yong Lee, Jaemin Yoo, and Kijung Shin. Hypeboy: Generative self-supervised representation learning on hypergraphs. In ICLR. OpenReview.net, 2024. Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015. URL https://arxiv.org/abs/1412. 6980. 11

Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017. URL https://openreview. net/forum?id=SJU4ayYgl. Risi Imre Kondor and John Lafferty. Diffusion kernels on graphs and other discrete input spaces. In Proceedings of the 19th International Conference on Machine Learning, pp. 315–322, 2002. URL https://people.cs.uchicago.edu/~risi/papers/ diffusion-kernels.pdf. Harold W. Kuhn. The hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1–2):83–97, 1955. doi: 10.1002/nav.3800020109. URL https://doi.org/10. 1002/nav.3800020109. Yann LeCun. A path towards autonomous machine intelligence, 2022. URL https:// openreview.net/forum?id=BZ5a1r-kVsf. Version 0.9.2, position paper. Dongjin Lee and Kijung Shin. I’m me, we’re us, and i’m us: Tri-directional contrastive learning on hypergraphs. In AAAI, pp. 8456–8464. AAAI Press, 2023. Kyuhan Lee, Geon Lee, and Kijung Shin. MARIOH: Multiplicity-aware hypergraph reconstruction. In 2025 IEEE 41st International Conference on Data Engineering, pp. 3113–3125, 2025. doi: 10.1109/ICDE65448.2025.00233. URL https://doi.org/10.1109/ICDE65448.2025. 00233. Runze Lei, Pinghui Wang, Junzhou Zhao, Lin Lan, Jing Tao, Chao Deng, Junlan Feng, Xidian Wang, and Xiaohong Guan. Federated learning over coupled graphs. IEEE Transactions on Parallel and Distributed Systems, 34(4):1159–1172, 2023. doi: 10.1109/TPDS.2023.3240527. Fan Li, Xiaoyang Wang, Wenjie Zhang, Ying Zhang, and Xuemin Lin. DHG-Bench: A comprehensive benchmark for deep hypergraph learning. In The Fourteenth International Conference on Learning Representations, 2026. URL https://openreview.net/forum?id=lhsb1ChUDF. Xunkai Li, Zhengyu Wu, Wentao Zhang, Yinlin Zhu, Ronghua Li, and Guoren Wang. Fedgta: Topology-aware averaging for federated graph learning. Proc. VLDB Endow., 17(1):41–50, 2023. Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019. URL https://openreview.net/forum?id= Bkg6RiCqY7. Linfeng Luo, Zhiqi Guo, Fengxiao Tang, Zihao Qiu, and Ming Zhao. Federated hypergraph learning with local differential privacy: Toward privacy-aware hypergraph structure completion. In 2025 IEEE International Conference on Data Mining, pp. 1400–1409, 2025. doi: 10.1109/ICDM65498. 2025.00149. URL https://doi.org/10.1109/ICDM65498.2025.00149. Charles F. Manski. Partial Identification of Probability Distributions. Springer Series in Statistics. Springer, New York, 2003. doi: 10.1007/b97478. URL https://doi.org/10.1007/ b97478. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficient learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pp. 1273–1282. PMLR, 2017. URL https://proceedings. mlr.press/v54/mcmahan17a.html. Gabriel Peyré, Marco Cuturi, and Justin Solomon. Gromov-wasserstein averaging of kernel and distance matrices. In Proceedings of the 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 2664–2672. PMLR, 2016. URL https://proceedings.mlr.press/v48/peyre16.html. William P. Pierskalla. Letter to the editor—the multidimensional assignment problem. Operations Research, 16(2):422–431, 1968. doi: 10.1287/opre.16.2.422. URL https://doi.org/10. 1287/opre.16.2.422. 12

Gathika Ratnayaka, James Nichols, and Qing Wang. Learning partial graph matching via optimal partial transport. In Y. Yue, A. Garg, N. Peng, F. Sha, and R. Yu (eds.), International Conference on Learning Representations, volume 2025, pp. 83575–83595, 2025. URL https://proceedings.iclr.cc/paper_files/paper/2025/file/ cfa8440d500a6a6867157dfd4eaff66e-Paper-Conference.pdf. Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In ICLR. OpenReview.net, 2018. Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9(2):cnab014, 2021. doi: 10.1093/comnet/cnab014. URL https://doi. org/10.1093/comnet/cnab014.

Shanghao Shi, Ning Wang, Yang Xiao, Chaoyu Zhang, Yi Shi, Y. Thomas Hou, and Wenjing Lou. Scale-MIA: A scalable model inversion attack against secure federated learning via latent space reconstruction. In Network and Distributed System Security Symposium, 2025. doi: 10. 14722/ndss.2025.240644. URL https://www.ndss-symposium.org/ndss-paper/ scale-mia-a-scalable-model-inversion-attack-against-secure-federated-learning-viaYizhou Sun, Jiawei Han, Xifeng Yan, Philip S. Yu, and Tianyi Wu. PathSim: Meta path-based top-k similarity search in heterogeneous information networks. Proceedings of the VLDB Endowment, 4(11):992–1003, 2011. doi: 10.14778/3402707.3402736. URL https://www.vldb.org/ pvldb/vol4/p992-sun.pdf. Titouan Vayer, Laetitia Chapel, Rémi Flamary, Romain Tavenard, and Nicolas Courty. Optimal transport for structured data with application on graphs. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6275–6284. PMLR, 2019. URL https://proceedings.mlr.press/v97/ titouan19a.html. Peihao Wang, Shenghao Yang, Yunyu Liu, Zhangyang Wang, and Pan Li. Equivariant hypergraph diffusion neural operators. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=RiTjKoscnNd. Yanbang Wang and Jon Kleinberg. From graphs to hypergraphs: Hypergraph projection and its reconstruction. In The Twelfth International Conference on Learning Representations, 2024. URL https://proceedings.iclr.cc/paper_files/paper/2024/hash/ e92b8441b702d142435f243806f9ec5a-Abstract-Conference.html. Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Vikram Nitin, Anand Louis, and Partha Talukdar. HyperGCN: A new method for training graph convolutional networks on hypergraphs. In Advances in Neural Information Processing Systems, volume 32, 2019. URL https://proceedings.neurips.cc/paper/2019/hash/ 1efa39bcaec6f3900149160693694536-Abstract.html. Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In Proceedings of the 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 40–48. PMLR, 2016. URL https: //proceedings.mlr.press/v48/yanga16.html. Yuhang Yao, Weizhao Jin, Srivatsan Ravi, and Carlee Joe-Wong. FedGCN: Convergencecommunication tradeoffs in federated training of graph convolutional networks. In Advances in Neural Information Processing Systems, volume 36, pp. 79748–79760, 2023. doi: 10.52202/ 075280-3491. URL https://proceedings.neurips.cc/paper_files/paper/ 2023/hash/fc07feae9af49dd3f1a1e049b77f4e17-Abstract-Conference. html. Jean-Gabriel Young, Giovanni Petri, and Tiago P. Peixoto. Hypergraph reconstruction from network data. Communications Physics, 4:135, 2021. doi: 10.1038/s42005-021-00637-w. URL https: //doi.org/10.1038/s42005-021-00637-w. 13

Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander J. Smola. Deep sets. In Advances in Neural Information Processing Systems, volume 30, 2017. URL https://proceedings.neurips.cc/paper_files/paper/ 2017/hash/f22e4747da1aa27e363d86d40ff442fe-Abstract.html. Ke Zhang, Carl Yang, Xiaoxiao Li, Lichao Sun, and Siu Ming Yiu. Subgraph federated learning with missing neighbor generation. In Advances in Neural Information Processing Systems, volume 34, 2021. URL https://proceedings.neurips.cc/paper/2021/hash/ 34adeb8e3242824038aa65460a47c29e-Abstract.html. Stephen Y. Zhang, Fangfei Lan, Youjia Zhou, Agnese Barbensi, Michael P. H. Stumpf, Bei Wang, and Tom Needham. Geometry of the space of partitioned networks: A unified theoretical and computational framework. Information and Inference: A Journal of the IMA, 15(3):iaag022, 2026. doi: 10.1093/imaiai/iaag022. URL https://doi.org/10.1093/imaiai/iaag022. Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. Learning with hypergraphs: Clustering, classification, and embedding. In Advances in Neural Information Processing Systems, volume 19, 2006. URL https://proceedings.neurips.cc/paper_files/paper/ 2006/hash/dff8e9c2ac33381546d96deea9922999-Abstract.html.

14

Appendix Contents A

More Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

B

Formal Results and Identification Boundaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

C

D

E

B.1

Important Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

B.2

Observation Channel and Design-based Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

B.3

Two-client Assumptions and Weight-stratum Boundary . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 C.1

Two-client Completion and Point Identification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

C.2

Order-𝑞 Mass Identification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

C.3

Structured Tractable Class: Anti-Monge Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

C.4

Multi-client Computational Boundary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

C.5

Boolean-zeta Inversion and Partition Censoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

C.6

Horvitz–Thompson Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

C.7

Observational Equivalence and a Two-point Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

C.8

Released-data Factorization and Observable Spectral Approximation . . . . . . . . . . . . . . 24

C.9

Observable Diffusion and Predictive Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

C.10

Downstream Risk with Additional Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

C.11

Randomized Recovery from Diffusion Features and Local Prediction Risk . . . . . . . . . 29

C.12

Stochastic Federated Optimization and Risk Transfer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

Experimental Protocols and Implementation Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 D.1

FedASTRA Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

D.2

Graph Partitions and Lifts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

D.3

Dataset Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

D.4

Experimental Configurations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

Additional Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 E.1

Performance on Native Hypergraphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .40

E.2

Performance Against Baselines with Varying Information Access . . . . . . . . . . . . . . . . . . 41

E.3

Validation on Proposed Analysis and Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

E.4

Scalability on Large-scale Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

15

A

M ORE R ELATED W ORK

Latent correspondence and partial identification. Unknown correspondence is classical in record linkage (Fellegi & Sunter, 1969), where latent pairings between records must be inferred from incomplete identifying information. Partial identification instead retains the set of target values compatible with the observations when point identification is unavailable (Manski, 2003). Our setting combines these perspectives at the level of higher-order relations: client-local hyperedge fragments are observed, but their cross-client instance correspondence is not. Rather than selecting or estimating one global linkage, we characterize the full compatibility class induced by the released fragments and derive sharp target bounds over all compatible alignments. Alignment under latent correspondence. When object identities are not shared, relational alignment is often formulated through latent couplings. Gromov–Wasserstein and fused Gromov– Wasserstein formulations compare structured objects without requiring a common coordinate system (Peyré et al., 2016; Vayer et al., 2019), while recent partial formulations relax full-mass or fullmatching requirements (Bai et al., 2025; Ratnayaka et al., 2025). For higher-order structures, HyperCOT develops transport-based comparisons of hypergraphs (Chowdhury et al., 2024), and recent partitioned-network geometry unifies graph and hypergraph alignment within a common metric framework (Zhang et al., 2026). These approaches optimize an alignment or distance under a specified geometry. But more specifically here, we are more concerned with which target values remain invariant to latent cross-client correspondence and which vary within the compatibility class induced by a fixed federated release. Hypergraph reconstruction from coarsened observations. Some existing papers study whether higher-order structure can be reconstructed from lower-order or otherwise coarsened observations. Early work develops statistical reconstruction from network data (Young et al., 2021). Wang and Kleinberg characterize information loss under hypergraph projection and study reconstruction with additional structural knowledge (Wang & Kleinberg, 2024). For random uniform hypergraphs, recent work gives information-theoretic and algorithmic thresholds for exact recovery (Bresler et al., 2024), followed by a characterization of both partial and exact recovery across hyperedge sizes and multiplicity regimes (Bresler et al., 2025). Multiplicity-aware supervised reconstruction provides a complementary algorithmic approach (Lee et al., 2025), while recent learning theory has also formulated relational learning itself through a hypergraph-recovery model (Chen et al., 2024). These works primarily ask when a latent source hypergraph is recoverable under projection or a specified generative model. Our observation is however different: clients retain higher-order fragments themselves, but their cross-client instance identities are suppressed. We therefore retain all compatible global hypergraphs and characterize what is identifiable without directly assuming that one global completion can be recovered. Assignment and multiway matching complexity. Two-way correspondence is closely related to classical linear assignment and bipartite matching (Birkhoff, 1946; Kuhn, 1955), whereas multidimensional assignment and three-dimensional matching exhibit fundamentally different computational behavior (Pierskalla, 1968; Karp, 1972). Parameterized algorithms for set packing and matching draw on tools such as color coding, while the W-hierarchy distinguishes fixed-parameter tractability from parameterized intractability (Alon et al., 1995; Downey & Fellows, 1995). Recent partial graph matching still exposes tractable assignment structure in important pairwise settings (Ratnayaka et al., 2025). Our result places these phenomena within one latent-correspondence problem: under the same observation and reward rules, two-client correspondence is polynomial, fixed-client multiway matching is NP-complete but fixed-parameter tractable in the stated joint parameter, and unbounded client count is W[1]-complete in matching size.

B

F ORMAL R ESULTS AND I DENTIFICATION B OUNDARIES

This section records the observation assumptions used in the proofs: which fragment attributes are retained, when partition censoring admits unbiased correction, and when unknown correspondence is exactly a bipartite assignment.

16

B.1

I MPORTANT N OTATION

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

Meaning

H = (𝑉, E, 𝑋, 𝑟, 𝑤) 𝐴𝑒 , 𝑟 𝑒 , 𝑤 𝑒 𝑤 𝑟 ( 𝐴) H (𝑆) 𝑀𝑞,𝑟 Z, 𝑧, 𝑉𝑘

Finite node-attributed, typed, weighted multihypergraph. Support, type in R, and positive weight of relation instance 𝑒 ∈ E. Aggregate weight of type-𝑟 instances with support 𝐴.
Weighted type-𝑟 order-𝑞 co-membership count for 𝑆 ∈ 𝑉𝑞 . Random node-to-client assignment, one realization, and the nodes assigned to client 𝑘. Minimum visible fragment size and the analyst’s local/cross status mark. Public observation assumptions and its allowed latent-hypergraph class. Analyst release as a random element and one realized value. Coarsened learner release 𝑌L = 𝜌(𝑌A ) and one realized value. Analyst and learner compatibility classes defined in Equation (4) and Corollary 2. Retained type-𝑟 coordinates and the type-aggregated erased-mass fraction. Inclusion probability of a 𝑞-set and its common value under an exchangeable randomized partition design. Values of Φ𝑞, 𝜓 over FA (𝑦 A , Γ). Exact type-and-weight stratum, its assignment cost, and the Birkhoff polytope. Client incidence matrix, node and relation degrees, and isolated-node indicator. Observable Markov operator and its symmetric representative on positive-degree nodes. Continuous-time local diffusion exp{𝑡 (𝑃 𝑘 − 𝐼)} at time 𝑡 ≥ 0. Number of positive heat channels, channel-𝑏 time for feature 𝑗, and its positive increment floor. Heat-basis representation and its shorthand with 𝜗 = ctx(𝜃). Shared recurrence degree and its deterministic Poisson-tail tolerance. Complete online state, its context coordinates (𝜃 enc , 𝜂), and the client-local EMA target context. Rowwise predictor, rowwise classifier, and class label of node 𝑣. View-agreement weight, predictive-loss weight, and target momentum. Fixed training protocol, algorithmic randomness, and the transcript through round 𝑇.

𝑐, 𝜐𝑒,𝑘 Γ, M Γ 𝑌A , 𝑦 A 𝑌L , 𝑦 L FA , FL e𝑞,𝑟 (·, 𝑧), 𝜏𝑞 𝑀 𝜋𝑆 , 𝜋𝑞 I𝑞, 𝜓 (𝑦 A ) ℎ = (𝑟, 𝜔), 𝐶 ℎ , B𝑚ℎ 𝐵 𝑘 , 𝐷 𝑣,𝑘 , 𝐷 𝑒,𝑘 , 𝐼0,𝑘 sym 𝑃𝑘 , 𝑃𝑘 K 𝑘 (𝑡) 𝑅, 𝑡 𝑏 𝑗 , 𝜖 ord 𝑊 𝑘 (𝑋 𝑘 | 𝜗), 𝑊 𝑘, 𝜃 (𝑋 𝑘 ) 𝐿 tail , 𝜀 tail 𝜃, 𝜗, 𝜗¯ 𝑝 𝜃 , 𝑐 𝜃 , 𝑦𝑣 𝛾view , 𝜆 pred , 𝜇 P, 𝜉, T𝑇

Probability and conditioning convention. Unless a statement says otherwise, H , 𝑧, Γ, and the realized release are fixed. Expectations and variances in Theorem 3 are taken over the declared random partition Z. Corollary 3 explicitly averages over a uniform latent matching. Algorithmic laws average over 𝜉 ∼ 𝜈, where the fixed law 𝜈 is independent of H . The auxiliary variable 𝑁𝑡aux below only expresses deterministic Poisson coefficients and tail bounds and is absent from implementation sampling. Appendix C.10 separately defines its downstream evaluation law. B.2 B.2.1

O BSERVATION C HANNEL AND D ESIGN - BASED R ECOVERY AGGREGATE SUPPORT– TYPE WEIGHTS AND B OOLEAN - ZETA COORDINATES

The analyst release retains each fragment occurrence with its exact type, weight, and local/cross status. Assignment strata use these individual rows, including duplicates. Co-membership coordinates instead depend on 𝑤 𝑟 ( 𝐴), the total weight of rows with support 𝐴 and type 𝑟. Aggregation loses the allocation of weight among duplicate occurrences, so it cannot replace the Í row-level table in the matching analysis. Erasing types further reduces the observation to 𝑀𝑞 = 𝑟 𝑀𝑞,𝑟 . The following inclusion describes the resulting uncertainty on the same latent class M Γ . Corollary 1 (Coarsened or missing type marks enlarge identified sets). Let 𝜒 : R → R 𝜒 merge or suppress type labels, and let 𝜒# apply this map to the release while preserving its other fields. For an exact-type release 𝑦 ex , set 𝑦 𝜒 = 𝜒# 𝑦 ex and O 𝜒 = 𝜒# ◦ O𝑧,Γ , with public type restrictions pushed forward accordingly. On the common class M Γ , define Fex (𝑦 ex , Γ) = {H ∈ M Γ : O𝑧,Γ (H ) = 𝑦 ex }, F𝜒 (𝑦 𝜒 , Γ) = {H ∈ M Γ : O 𝜒 (H ) = 𝑦 𝜒 }. (25) For a scalar target 𝜙 : M Γ → R, write I𝜙,ex = 𝜙(Fex (𝑦 ex , Γ)) and I𝜙,𝜒 = 𝜙(F𝜒 (𝑦 𝜒 , Γ)). Then Fex (𝑦 ex , Γ) ⊆ F𝜒 (𝑦 𝜒 , Γ), I𝜙,ex ⊆ I𝜙,𝜒 . (26) 17

When the scalar endpoints are finite, this inclusion gives inf I𝜙, 𝜒 ≤ inf I𝜙,ex ≤ sup I𝜙,ex ≤ sup I𝜙,𝜒 .

(27)

Thus type coarsening can only preserve or widen the sharp endpoint interval. Proof. Every hypergraph reproducing the exact marked table also reproduces its 𝜒-coarsening, which proves the first inclusion. Taking the image under 𝜙 proves the second, and nested scalar sets give the endpoint inequalities. □ B.2.2

I NDEPENDENT AND FIXED - CAPACITY DESIGNS
For fixed H and 𝑞 ≥ 𝑐, a coordinate 𝑆 ∈ 𝑉𝑞 survives when all its nodes share a client. Independent assignments with 𝑝 𝑣𝑘 = Pr{Z(𝑣) = 𝑘 } give 𝜋 𝑆 = Pr{Z| 𝑆 is constant} =

𝐾 Ö ∑︁

𝑝 𝑣𝑘 .

(28)

𝑘=1 𝑣 ∈𝑆

For a uniformly random partition with fixed capacities (𝑛1 , . . . , 𝑛 𝐾 ), exchangeability gives 𝑛𝑘
𝐾 ∑︁ 𝑞 𝜋𝑞 = . |𝑉 |
𝑘=1

(29)

𝑞

Positive inclusion probabilities permit coordinatewise Horvitz–Thompson weighting (Horvitz & Thompson, 1952). Its unbiasedness concerns repeated randomized partitions. Proportions from a fixed institutional partition alone actually fail to specify the required assignment law. B.2.3

C ONDITIONS FOR COORDINATE - WISE PARTITION CENSORING

Equation (6) requires retained multiplicity, exact weight, type, and 𝑞 ≥ 𝑐. Deduplication would change the count, so the data interface preserves duplicate and singleton columns. For 𝑐 > 1, some nonempty fragments disappear. Completion analysis then requires constraints on original hyperedge counts or orders. The exact two-client result uses 𝑐 = 1. B.3

T WO - CLIENT A SSUMPTIONS AND W EIGHT- STRATUM B OUNDARY

Theorem 1 assumes two clients, 𝑐 = 1, observed local/cross status, one nonempty row at each client per cross-client hyperedge, and exact type-and-weight strata ℎ = (𝑟, 𝜔) with 𝑚 1ℎ = 𝑚 2ℎ =: 𝑚 ℎ . Each compatible completion is then a bijection within every stratum. Missing fragments, uncertain counts, or further clients change this feasible set. Weight bins also enlarge it: the public model must specify the allowed underlying weights, and endpoints must be optimized over that range rather than evaluated at an assumed bin midpoint. Under the exact assumptions, general two-client targets admit assignment bounds, while total order-𝑞 mass admits sorting bounds. General three-client targets are NP-hard. For any client count, anchoradditive costs remain tractable because the objective separates into 𝐾 − 1 independent bipartite assignments (Proposition 1).

C

P ROOFS

We prove the structural bounds first, then connect observable heat features to prediction risk and the shared-model federated objective. C.1

T WO - CLIENT C OMPLETION AND P OINT I DENTIFICATION

Fix a stratum ℎ = (𝑟, 𝜔). Under the exact two-client assumptions, every 𝜛 ∈ Sym(𝑚 ℎ ) is compatible. Each 𝑞-set in 𝐹1𝑖ℎ ∪ 𝐹2,ℎ 𝜛 (𝑖) lies within one fragment or intersects both. Summing the withinfragment terms over 𝑖 is matching-invariant, while the mixed terms give 𝐶𝑖,ℎ 𝜛 (𝑖) . Adding known local 18

contributions proves Equation (10). By Birkhoff–von Neumann integrality, the vertices of B𝑚 are exactly the permutation matrices (Birkhoff, 1946). Both linear-program endpoints therefore attain compatible matchings and are sharp. Each costs 𝑂 (𝑚 3ℎ ) by Hungarian assignment (Kuhn, 1955). The assignment dual also provides a certificate for the computed bound. For each stratum, the lower-endpoint dual is ∑︁ ∑︁ max 𝑢𝑖 + 𝑣 𝑗 s.t. 𝑢 𝑖 + 𝑣 𝑗 ≤ 𝐶𝑖ℎ𝑗 . (30) 𝑢,𝑣 𝑖

𝑗

The upper endpoint has a minimization dual with 𝑢 𝑖 + 𝑣 𝑗 ≥ 𝐶𝑖ℎ𝑗 . Dual feasibility and equality of primal and dual values certify an endpoint, with equality on every pair in an optimal matching. Í Í If 𝐶𝑖 𝑗 = 𝛼𝑖 + 𝛽 𝑗 , every permutation sums to 𝑖 𝛼𝑖 + 𝑗 𝛽 𝑗 . Conversely, equality of all permutation sums implies equality after exchanging any two assigned columns, hence 𝐶𝑖 𝑗 + 𝐶𝑖 ′ 𝑗 ′ − 𝐶𝑖 𝑗 ′ − 𝐶𝑖 ′ 𝑗 = 0.

(31)

When all such rectangular cross-differences vanish, set 𝛼𝑖 = 𝐶𝑖1 and 𝛽 𝑗 = 𝐶1 𝑗 − 𝐶11 . The cycle using row 1 and column 1 gives 𝐶𝑖 𝑗 = 𝛼𝑖 + 𝛽 𝑗 . For 𝑚 = 1 this representation is immediate. Finally, 𝐽𝑚 𝐶𝐽𝑚 = 0 if and only if 𝐶 lies in the kernel of double centering, which is exactly the row–column-additive subspace. Thus the quotient of cost matrices by the kernel of assignment variation is represented uniquely by 𝐽𝑚 𝐶𝐽𝑚 . Since 𝐽𝑚 has rank 𝑚 − 1, this image has dimension (𝑚 − 1) 2 . The quotient maps injectively into the following (𝑚 − 1) 2 base four-cycle coordinates:
𝑚 𝐶𝑖 𝑗 − 𝐶𝑖1 − 𝐶1 𝑗 + 𝐶11 𝑖, 𝑗=2 (32) Zero base coordinates imply row–column additivity, so these (𝑚 − 1) 2 coordinates are independent on the quotient. The dimension is attainable with 𝑞 = 2 and unit-weight singleton fragments by setting 𝜓2,𝑟 ({𝑎 𝑖 , 𝑏 𝑗 }, 𝑋 {𝑎𝑖 ,𝑏 𝑗 } ) = 𝐶𝑖 𝑗 . Repeated fragments or restricted test functions may reduce the realized dimension, without changing the endpoint argument. Since strata vary independently, point identification requires additivity in every stratum. □ C.2

O RDER -𝑞 M ASS I DENTIFICATION

For a general target, the preceding proof requires an assignment solver. Total order-𝑞 mass has more structure: with 𝑞 ≥ 2, its mixed cost depends only on fragment sizes. This allows both endpoints to be computed by sorting. Within stratum ℎ = (𝑟, 𝜔), set 𝑎 𝑖ℎ = |𝐹1𝑖ℎ |, 𝑏 ℎ𝑗 = |𝐹2ℎ𝑗 |, and 𝜔 ℎ = 𝜔. Vandermonde’s identity and its discrete mixed difference give       𝑞−1 ∑︁  𝑎   𝑏  𝑎+𝑏 𝑎 𝑏 𝜅 𝑞 (𝑎, 𝑏) = − − = , (33) 𝑞 𝑞 ℓ 𝑞−ℓ 𝑞 ℓ=1 ′ −1 𝑏 ′ −1  𝑎∑︁ ∑︁ 𝑥 + 𝑦  ′ ′ ′ ′ 𝜅 𝑞 (𝑎, 𝑏) + 𝜅 𝑞 (𝑎 , 𝑏 ) − 𝜅 𝑞 (𝑎, 𝑏 ) − 𝜅 𝑞 (𝑎 , 𝑏) = ≥0 (34) 𝑞−2 𝑥=𝑎 𝑦=𝑏 for 𝑎 ≤ 𝑎 ′ and 𝑏 ≤ 𝑏 ′ . Same-order pairing maximizes the total mass at 𝑇𝑞+ , while opposite-order pairing minimizes it at 𝑇𝑞− . Writing the released local mass as 𝑀𝑞obs gives sharp erased-mass bounds: 𝜏𝑞− = 1 − 𝑀𝑞obs /𝑇𝑞− ,

𝜏𝑞+ = 1 − 𝑀𝑞obs /𝑇𝑞+ .

(35)

The zero-total convention and explicit formulas for 𝑇𝑞± appear in Appendix C.3. Point identification holds exactly when the mixed Í difference vanishes throughout every stratum. Sorting computes both attainable endpoints in 𝑂 ( ℎ 𝑚 ℎ log 𝑚 ℎ ) time by sorting fragment sizes within each stratum. To determine when these bounds coincide, take the constant-one test. Its stratum cost is 𝐶𝑖ℎ𝑗 = 𝜔 ℎ 𝜅 𝑞 (𝑎 𝑖ℎ , 𝑏 ℎ𝑗 ). Equation (34) yields the exact rectangular 2 × 2 cross-difference within each fixed type-and-weight stratum: 𝑎𝑖ℎ′ −1 𝑏 𝑗 ′ −1 

ℎ ∑︁ ∑︁ 𝑥 + 𝑦  𝐶𝑖ℎ𝑗 + 𝐶𝑖ℎ′ 𝑗 ′ − 𝐶𝑖ℎ𝑗 ′ − 𝐶𝑖ℎ′ 𝑗 = 𝜔 ℎ . 𝑞−2 ℎ ℎ

𝑥=𝑎𝑖 𝑦=𝑏 𝑗

19

(36)

Theorem 1 makes vanishing of all these quantities necessary and sufficient for point identification. If both lists vary, take 𝑎 𝑖ℎ′ = max𝑖 𝑎 𝑖ℎ and 𝑏 ℎ𝑗′ = max 𝑗 𝑏 ℎ𝑗 with strictly smaller 𝑎 𝑖ℎ , 𝑏 ℎ𝑗 . When 𝑎 𝑖ℎ′ + 𝑏 ℎ𝑗′ ≥ 𝑞, the summand at (𝑥, 𝑦) = (𝑎 𝑖ℎ′ − 1, 𝑏 ℎ𝑗′ − 1) is positive, so point identification fails. For 𝑞 = 2 every nonempty summand equals one. Thus, at 𝑞 = 2, all cross-differences vanish exactly when at least one size list is constant in each stratum. For general 𝑞, if one list is constant then all rectangles are empty in that direction. If both vary but max𝑖 𝑎 𝑖ℎ + max 𝑗 𝑏 ℎ𝑗 < 𝑞, every mixed 𝑞-node-subset count is zero. Together with the preceding strict argument, these are the only point-identified cases. □ C.3

S TRUCTURED T RACTABLE C LASS : A NTI -M ONGE B OUNDS

Vandermonde’s identity gives Equation (33) by removing the two within-fragment terms. For
𝑛
𝑏 𝑞 (𝑛) = 𝑞𝑛 , Pascal’s identity gives 𝑏 𝑞 (𝑛 + 2) − 2𝑏 𝑞 (𝑛 + 1) + 𝑏 𝑞 (𝑛) = 𝑞−2 . Summing this difference over 𝑥 = 𝑎, . . . , 𝑎 ′ − 1 and 𝑦 = 𝑏, . . . , 𝑏 ′ − 1 proves Equation (34), since row-only and column-only terms cancel. ℎ . If a proposed matching pairs 𝑎 ℎ ≤ 𝑎 ℎ with 𝑏 ℎ > 𝑏 ℎ , the Within each stratum, sort 𝑎 1ℎ ≤ · · · ≤ 𝑎 𝑚 𝑖 𝑖′ 𝑗 𝑗′ ℎ anti-Monge inequality shows that swapping the two targets weakly increases the total mixed count. Repeating adjacent swaps proves that equal-order pairing maximizes it. Applying the same argument to the reversed 𝑏 order proves the minimum. Non-negative retained weights preserve the inequality within each fixed stratum, and strata add. With invariant local mass 𝑀𝑞obs , the completed mass under Í Í 𝝕 = (𝜛ℎ ) ℎ is 𝑇𝑞 (𝝕) = 𝑀𝑞obs + ℎ 𝜔 ℎ 𝑖 𝜅 𝑞 (𝑎 𝑖ℎ , 𝑏 ℎ𝜛ℎ (𝑖) ). Since 1 − 𝑀𝑞obs /𝑇𝑞 is nondecreasing in 𝑇𝑞 for 𝑇𝑞 > 0, the claimed truncation bounds follow. If 𝑇𝑞− = 0, then 𝑀𝑞obs = 0: the zero-total convention gives the lower endpoint zero, while the upper endpoint is one if 𝑇𝑞+ > 0 and zero otherwise, exactly as in Equation (35). Sorting the fragment-size lists computes both sharp endpoints in 𝑂 (𝑚 log 𝑚) time. □

C.4

M ULTI - CLIENT C OMPUTATIONAL B OUNDARY

For three clients, anchoring the first fragment index leaves two permutations 𝜛, 𝜍 ∈ Sym(𝑚) and the objective 𝑚 ∑︁ Φobs + 𝐶𝑖, 𝜛 (𝑖), 𝜍 (𝑖) . (37) 𝑖=1

For any finite tensor 𝑇, create unit-weight singleton fragments {𝑎 𝑖 }, {𝑏 𝑗 }, {𝑐 𝑘 } in one type/weight stratum, set 𝑞 = 3, fix one type 𝑟, define 𝜓3,𝑟 ({𝑎 𝑖 , 𝑏 𝑗 , 𝑐 𝑘 }, 𝑋 {𝑎𝑖 ,𝑏 𝑗 ,𝑐𝑘 } ) = 𝑇𝑖 𝑗 𝑘 , and set the test function to zero on every other triple. Each completed hyperedge has exactly one 𝑞-node subset, so its cost tensor is exactly 𝑇. The 𝑚 3 test-function table is an explicit polynomial-size part of the endpoint instance. For a three-dimensional-matching instance, choose 𝑇𝑖 𝑗 𝑘 = 0 on an allowed triple and 𝑇𝑖 𝑗 𝑘 = 1 otherwise. A completion with value zero exists if and only if the three-dimensional-matching instance has a perfect matching. The latter is NP-complete (Karp, 1972). Hence the lower endpoint is NP-hard for three clients. More clients contain this construction by adding singleton fragment lists and defining the 𝑞 = 3 test to be zero on every triple involving an added client. Their permutations leave the objective unchanged. Together, all these prove hardness for general linear co-membership targets. For a sparse binary-reward target, correspondence reduces to hypergraph matching. The following result separates the effects of client count and desired matching size. Theorem 2 (Parameterized complexity of hyperedge matching). In one exact all-client stratum, let each of 𝐾 ≥ 2 clients have 𝑚 distinct singleton fragments, with one common type and unit weight. Set 𝑞 = 𝐾. The input lists favorable tuples E+ ⊆ [𝑚] 𝐾 and assigns the order-𝐾 query value one to them and zero to all other tuples. This sparse default-zero encoding includes all client-row lists, so 𝐾𝑚 is bounded by the input length. For permutations 𝜛2 , . . . , 𝜛𝐾 of [𝑚], define Φ+ (E+ ) =

max

𝑚 ∑︁

𝜛2 ,..., 𝜛𝐾

1{(𝑖, 𝜛2 (𝑖), . . . , 𝜛𝐾 (𝑖)) ∈ E+ }.

(38)

𝑖=1

For 1 ≤ 𝑏 ≤ 𝑚, deciding Φ+ ≥ 𝑏 is polynomial-time solvable when 𝐾 = 2 and NP-complete for every fixed 𝐾 ≥ 3. It is fixed-parameter tractable in 𝐾 𝑏, and hence in 𝑏 for fixed 𝐾. When 𝐾 is unbounded 20

it is W[1]-complete parameterized by 𝑏. A direct randomized algorithm has one-sided error at most 𝛿cc ∈ (0, 1) and time 𝑂 ((2𝑒) 𝐾 𝑏 poly(𝐿 in ) log(2/𝛿cc )), where 𝐿 in is the input length. Proof. Treat client-row pairs (𝑘, 𝑖) as vertices in 𝐾 disjoint parts. A favorable tuple is a 𝐾-uniform hyperedge containing one vertex from each part. Rewarded tuples in a completion are pairwise disjoint. Conversely, any 𝑏 disjoint favorable tuples extend to a full completion: each part has 𝑚 − 𝑏 unused rows, which can be paired arbitrarily. Thus the endpoint decision is exactly the existence of a 𝑏-edge matching in the explicitly supplied 𝐾-partite hypergraph. For 𝐾 = 2 this is bipartite matching. For 𝐾 = 3, 𝑏 = 𝑚 it is perfect three-dimensional matching (Karp, 1972). For larger fixed 𝐾, copy the first coordinate into each new coordinate. This preserves disjointness and proves NP-hardness. A list of 𝑏 tuples is a polynomially checkable witness, establishing NP membership. For fixed-parameter tractability, put 𝑠 = 𝐾 𝑏 and color every client-row independently and uniformly with 𝑠 colors. The 𝑠 distinct rows of any fixed witness all receive different colors with probability 𝑠!/𝑠 𝑠 ≥ 𝑒 −𝑠 . Discard tuples whose vertices repeat a color. Use a Boolean dynamic program over color subsets, starting from the empty subset and adjoining the 𝐾 colors of any tuple disjoint from the current subset. Reaching all 𝑠 colors certifies exactly 𝑏 disjoint tuples. Disjoint color masks cannot share a row, so every reported witness is valid. One trial costs 𝑂 (2𝑠 |E+ |𝐾 + 𝐾𝑚). Repeating ⌈𝑒 𝑠 log(2/𝛿cc )⌉ times yields the claimed one-sided error and running time. Perfect-hash families derandomize color-coding to give deterministic fixed-parameter tractability (Alon et al., 1995). For W[1] membership, form the conflict graph with one vertex per favorable tuple and an edge between tuples sharing any client-row. The desired matching is an independent set of size 𝑏, a parameter-preserving reduction to Independent Set (Downey & Fellows, 1995). For hardness, take an Independent Set instance 𝐻 = (𝑈, 𝐹𝐻 ) with 𝑁 = |𝑈| vertices and target 𝑏. Create one private client and one client for each edge of 𝐻, adding a harmless client if needed to make 𝐾 ≥ 2. Every client has 𝑚 = 𝑁 rows. For each 𝑣 ∈ 𝑈, list one favorable tuple 𝑡 𝑣 . Its private-client row is unique to 𝑣. At the client for edge {𝑢, 𝑣}, tuples 𝑡𝑢 , 𝑡 𝑣 share a row, and all other tuples use distinct rows different from that shared row. Exactly 𝑁 − 1 rows are used there, which is feasible. A harmless client assigns distinct rows to all tuples. Two favorable tuples share a row precisely when their vertices in 𝐻 are adjacent. The construction is polynomial and preserves 𝑏. Therefore an independent set of size 𝑏 exists precisely when the constructed endpoint is at least 𝑏, proving W[1]-hardness and completeness. □ Here candidate hyperedges have rank 𝐾. The fixed-rank and variable-rank classifications concern this sparse reward problem, including its supplied query function. They do not classify arbitrary dense costs or neural-network training. For any client count, separation across a designated anchor gives the following tractable exception. Proposition 1 (Additive multi-client costs with one designated anchor). Consider an exact allclient stratum with 𝑚 rows per client, one row from each compatible original hyperedge at every client, and independently feasible one-to-one matchings anchored at client 1. A fully additive Í tensor 𝐶𝑖1 ,...,𝑖𝐾 = 𝑘 𝑎 𝑖(𝑘𝑘 ) is point identified. When the cost adds across the anchor–client pairs, Í𝐾 Í ) 𝐶𝑖1 ,...,𝑖𝐾 = 𝑎 𝑖1 + 𝑘=2 𝐶𝑖(𝑘 , each sharp endpoint is the constant 𝑖 𝑎 𝑖 plus the corresponding optima 1 𝑖𝑘 Í of 𝐾 − 1 independent bipartite assignments. Thus each endpoint costs 𝑂 ( ℎ (𝐾 − 1)𝑚 3ℎ ) by solving one independent bipartite assignment for each anchor-client pair within every stratum. Proof of Proposition 1. Anchoring client 1 makes the feasible set Sym(𝑚) 𝐾 −1 . For a fully additive cost, 𝑚 𝑚 𝐾 ∑︁ 𝑚 ∑︁ ∑︁ ∑︁ ) 𝐶𝑖, 𝜛2 (𝑖),..., 𝜛𝐾 (𝑖) = 𝑎 𝑖(1) + 𝑎 (𝑘 𝜛 (𝑖) 𝑘

𝑖=1

=

𝑖=1 𝐾 ∑︁ 𝑚 ∑︁

𝑘=2 𝑖=1 ) 𝑎 (𝑘 𝑗 ,

(39)

𝑘=1 𝑗=1

because each 𝜛𝑘 is a permutation, proving identification. Anchor-additive costs instead give 𝑚 𝐾 ∑︁ 𝑚 ∑︁ ∑︁ 𝑎𝑖 + 𝐶𝑖,(𝑘𝜛) (𝑖) . 𝑘

𝑖=1

𝑘=2 𝑖=1

21

(40)

Each summand has its own feasible permutation, so the total optimum is the sum of independent Í assignment optima. Their integrality proves sharpness and gives 𝑂 ( ℎ (𝐾 − 1)𝑚 3ℎ ) time. Interactions among non-anchor indices would break this separation. □ C.5

B OOLEAN - ZETA I NVERSION AND PARTITION C ENSORING

The assignment results describe uncertainty about how fragments fit together. We next justify the co-membership coordinates used to measure the information removed by partitioning. Before partitioning, the full collection determines aggregate support weights. After partitioning, each coordinate is either retained exactly or erased, under the observation assumptions stated in Appendix B.2. Proposition 2 (Invertible Boolean-zeta representation and censoring). For every type 𝑟 ∈ R, the H complete nonempty collection 𝑀 |𝑆 (𝑆) determines the aggregate support–type weights through |,𝑟 ∑︁ 𝑤 𝑟 ( 𝐴) = (−1) | 𝐵| − | 𝐴| 𝑀 |H𝐵|,𝑟 (𝐵). (41) 𝐵⊇ 𝐴

If multiplicity, exact retained weight, and type are observed, then Equation (6) holds for every 𝑞 ≥ 𝑐. Proof. Fix a type 𝑟 and regard 𝑤 𝑟 as a function on the Boolean lattice 2𝑉 , with zero mass on the empty Í H relation. Equation (2) is its upper zeta transform: 𝑀 |𝑆 (𝑆) = 𝐴⊇𝑆 𝑤 𝑟 ( 𝐴). The Möbius function |,𝑟 on the interval [𝑆, 𝐴] is (−1) | 𝐴| − |𝑆 | , so Boolean-lattice Möbius inversion gives Equation (41). This inversion applies separately to each observed relation type. For the mask, a copy of 𝑆 contributed by relation instance 𝑒 appears in a local fragment if and only if all nodes in 𝑆 have the same client label. If they do, exactly one client contains that copy. Otherwise none does. Summing over all 𝐴𝑒 ⊇ 𝑆 proves Equation (6). The complete and retained order-𝑞 masses therefore satisfy the two identities below for every observed type 𝑟 and order 𝑞:   ∑︁ | 𝐴𝑒 | H ∥ 𝑀𝑞,𝑟 ∥1 = 𝑤𝑒 , 𝑞 𝑒:𝑟𝑒 =𝑟  𝐾  ∑︁ ∑︁ | 𝐴 𝑒 ∩ 𝑉𝑘 | e𝑞,𝑟 (·, 𝑧) ∥ 1 = . (42) ∥𝑀 𝑤𝑒 𝑞 𝑒:𝑟 =𝑟 𝑘=1 𝑒

Their ratio is exactly the retained order-𝑞 co-membership mass in (7) for type 𝑟. C.6

□

H ORVITZ –T HOMPSON E STIMATION

The masking identity immediately suggests inverse-probability weighting under a known random partition design. It also reveals the cost of this correction: coordinates that rarely remain within one client acquire large variance. The theorem below gives both statements for each coordinate and then sums their squared errors. Theorem 3 (Known randomized assignment). Fix a latent hypergraph H , an order 𝑐 ≤ 𝑞 ≤ |𝑉 |, a
type 𝑟 ∈ R, and a node subset 𝑆 ∈ 𝑉𝑞 . Let Z : 𝑉 → [𝐾] follow the declared randomized partition design and assume 𝜋 𝑆 = Pr{Z| 𝑆 is constant} > 0. The coordinate estimator satisfies H b𝑞,𝑟 (𝑆) = 𝑀𝑞,𝑟 EZ 𝑀 (𝑆),

b𝑞,𝑟 (𝑆) = 𝑀 e𝑞,𝑟 (𝑆, Z)/𝜋 𝑆 , 𝑀 H b𝑞,𝑟 (𝑆)] = 𝑀𝑞,𝑟 VarZ [ 𝑀 (𝑆) 2 (𝜋 𝑆−1 − 1).

If every q-set has positive inclusion probability, the mean squared Frobenius error is ∑︁ H 2 H b𝑞,𝑟 − 𝑀𝑞,𝑟 EZ ∥ 𝑀 ∥𝐹 = 𝑀𝑞,𝑟 (𝑆) 2 (𝜋 𝑆−1 − 1). 𝑆 ∈ (𝑉 𝑞)

(43) (44)

(45)

Under uniform independent assignment, the relative coordinate variance of a nonzero coordinate is 𝐾 𝑞−1 − 1. If 𝜋 𝑆 = 0, no estimator measurable from the censored order-𝑞 co-membership array is design-unbiased for that coordinate over all type-𝑟 hypergraphs with size-𝑞 relation supports.

22

e𝑞,𝑟 (𝑆, Z) = Proof. Let 𝐼𝑆 (Z) = 1{Z| 𝑆 is constant}. Then 𝐼𝑆 (Z) ∼ Bernoulli(𝜋 𝑆 ) and 𝑀 H 𝐼𝑆 (Z) 𝑀𝑞,𝑟 (𝑆), which gives (43)–(44). Linearity of expectation applied to the sum of squared coordinate errors gives (45). Dependence among the indicators is allowed. Uniform assignment has 𝜋 𝑆 = 𝐾 (1/𝐾) 𝑞 = 𝐾 1−𝑞 . For 𝜋 𝑆 = 0, compare a q-uniform hypergraph with and without a weight-𝑎 edge on 𝑆. Their censored order-𝑞 co-membership arrays agree almost surely but the target coordinate differs by 𝑎. □ C.7

O BSERVATIONAL E QUIVALENCE AND A T WO - POINT B OUND

Randomized-design unbiasedness concerns repeated releases of a fixed structure. With one release held fixed, the question is different: can two compatible structures have different target values? If they can, any estimator based on that release has the same output law under both structures and must incur error on at least one. We first state the resulting bound for the learner’s coarsened release, then prove the underlying two-point argument. Corollary 2 (Identification-to-learning bridge under release coarsening). Let 𝑦 L = 𝜌(𝑦 A ) and hold the released training labels 𝑌 tr fixed across all candidate structures. For the same fixed 𝑧 and Γ, define FL (𝑦 L , Γ) = {H ∈ M Γ : 𝜌(O𝑧,Γ (H )) = 𝑦 L }. Deterministic coarsening gives FA (𝑦 A , Γ) ⊆ FL (𝑦 L , Γ). Let 𝜙 : M Γ → R be a scalar structural functional whose attainable endpoints on FA (𝑦 A , Γ) are 𝜙 − and 𝜙+ . The minimax absolute risk over randomized rules 𝜙b = 𝑎(𝑦 L , 𝑌 tr , 𝜉), with algorithmic randomness 𝜉 independent of H , satisfies this bound over the compatible class: inf

sup

𝑎

H ∈ FL ( 𝑦L ,Γ)

E 𝜉 | 𝜙b − 𝜙(H )| ≥ (𝜙+ − 𝜙 − )/2.

(46)

The proof uses the two endpoint structures, which remain indistinguishable after coarsening and therefore induce the same conditional output law. Proposition 3 (Fixed-release observational equivalence). Fix 𝑧, Γ, and a metric space (Θ, 𝑑). A functional 𝜙 : M Γ → Θ is point identified from the deterministic analyst release if and only if it is constant on every nonempty class FA (𝑦 A , Γ). If H0 , H1 ∈ FA (𝑦 A , Γ) and 𝑑 (𝜙(H0 ), 𝜙(H1 )) = Δ, every randomized estimator 𝜙b = 𝑎(𝑦 A , 𝜉) with 𝜉 ∼ 𝜈 independent of the latent hypergraph obeys max E 𝜉 𝑑 ( 𝜙b, 𝜙(H𝑏 )) ≥ Δ/2.

𝑏∈ {0,1}

(47)

Proof. If 𝜙 = 𝑔 ◦ O𝑧,Γ , equal analyst releases imply equal values of 𝜙, so 𝜙 is constant on each compatible class. Conversely, if 𝜙 is constant on every class, define 𝑔(𝑦 A ) as that common value for any H ∈ FA (𝑦 A , Γ). Constancy makes this definition independent of the representative. For the lower bound, 𝜙b = 𝑎(𝑦 A , 𝜉) has the same distribution at both compatible structures. Pointwise, the triangle inequality yields the following deterministic relation between the two endpoint errors: Δ ≤ 𝑑 ( 𝜙b, 𝜙(H0 )) + 𝑑 ( 𝜙b, 𝜙(H1 )). Taking expectation over the common law 𝜈 of 𝜉 shows that one endpoint risk reaches at least Δ/2.

(48) □

Proof of Corollary 2. If H ∈ FA (𝑦 A , Γ), applying 𝜌 to its analyst release gives 𝑦 L , hence H ∈ FL (𝑦 L , Γ). Theorem 1 supplies compatible structures attaining 𝜙 − and 𝜙+ . A rule measurable from 𝜎(𝑌L , 𝑌 tr , 𝜉) has one conditional output law under both endpoint structures because their training labels are held fixed. Their two absolute errors sum to at least 𝜙+ − 𝜙 − , so one endpoint risk reaches (𝜙+ − 𝜙 − )/2. This holds for every measurable rule, and taking the infimum gives Equation (46). □ Corollary 3 (Matching under hyperedge aliasing). In the two-client construction of Section 3.2, assume each side’s 𝑚 cross-status fragment rows are pairwise distinct and nonempty, share uninformative type and weight marks, and have no shared cross-client hyperedge identifier. A latent matching 𝜛 ∼ Unif (Sym(𝑚)) is recovered completely with probability at most 1/𝑚!. An estimator returning 𝑠 proposed matches has at most 𝑠/𝑚 correct matches in expectation. Proof. The observation is invariant under all 𝑚! permutations. Conditional on it, each full permutation is equiprobable. A fixed proposed pair is correct with probability 1/𝑚. Linearity of expectation yields 𝑠/𝑚 without an independence assumption across all returned proposals. □ 23

C.8

R ELEASED - DATA FACTORIZATION AND O BSERVABLE S PECTRAL A PPROXIMATION

We establish that FedASTRA’s complete trajectory factors through the learner release, then characterize the stability and expressiveness of its observable heat basis. Proposition 4 (Permutation invariance and heat stability). For every relation-column permutation Π, sym −1/2 𝑃 𝑘 (𝐵 𝑘 Π) = 𝑃 𝑘 (𝐵 𝑘 ) and 𝑊 𝑘, 𝜃 is unchanged. On the nonisolated block, 𝑃 𝑘 = 𝐷 1/2 𝑣,𝑘 𝑃 𝑘 𝐷 𝑣,𝑘 has sym

spectrum in [0, 1]. Hence ∥𝑒 𝑡 ( 𝑃𝑘 the same nodes satisfy ∥𝑒 𝑡 ( 𝑃

−𝐼 )

sym −𝐼 )

∥ 2 ≤ 1 for 𝑡 ≥ 0, and two such symmetric representatives on esym −𝐼 )

− 𝑒𝑡 ( 𝑃

esym ∥ 2 . ∥ 2 ≤ 𝑡 ∥𝑃sym − 𝑃

(49)

Proof. For 𝐵′ = 𝐵Π, 𝐷 ′𝑒 = Π ⊤ 𝐷 𝑒 Π, while 𝐷 𝑣 and 𝐼0 are fixed. Thus 𝐵′ (𝐷 ′𝑒 ) −1 (𝐵′ ) ⊤ = 𝐵Π(Π ⊤ 𝐷 𝑒 Π) −1 Π ⊤ 𝐵⊤ = 𝐵𝐷 𝑒−1 𝐵⊤ ,

(50)

proving invariance of 𝑃 and all heat features. On the nonisolated block, 𝑃sym = 𝐷 𝑣−1/2 𝐵𝐷 𝑒−1 𝐵⊤ 𝐷 𝑣−1/2 = 𝐺𝐺 ⊤ ,

𝐺 = 𝐷 𝑣−1/2 𝐵𝐷 𝑒−1/2 .

(51)

Positive semidefiniteness and similarity to the row-stochastic 𝑃 give spectrum in [0, 1] and contraction. Isolated rows are absorbing. Duhamel’s identity gives ∫ 𝑡 sym sym esym esym )𝑒 𝑠 ( 𝑃esym −𝐼 ) 𝑑𝑠, 𝑒 𝑡 ( 𝑃 −𝐼 ) − 𝑒 𝑡 ( 𝑃 −𝐼 ) = 𝑒 (𝑡 −𝑠) ( 𝑃 −𝐼 ) (𝑃sym − 𝑃 (52) 0

whose norm is bounded by Equation (49).

□

For one release, contraction in symmetric coordinates is equivalent to contraction in ∥𝑥∥ 𝐷𝑣 = ∥𝐷 1/2 𝑣 𝑥∥ 2 ; the perturbation bound compares symmetric representatives. In the two-client model, joining 𝐹1𝑖ℎ to 𝐹2,ℎ 𝜛ℎ (𝑖) gives Î {H𝝕 : 𝝕 ∈ ℎ Sym(𝑚 ℎ )} ⊆ FA (𝑦 A , Γ) ⊆ FL (𝜌(𝑦 A ), Γ). (53) These matchings range over Equation (10) while preserving all local fragment multisets and hence the learner release. Theorem 4 (Factorization of the complete federated learning trajectory). Let P fix the task split, training and validation labels, participation schedule, training-count aggregation weights, checkpoint rule, and hyperparameters; let 𝜉 collect initialization, masking, minibatch, and optimizer randomness. Under exact arithmetic, for any client count and horizon 𝑇, the transcript T𝑇 of all broadcasts, online, EMA and optimizer states, uploads, selected checkpoint, and final logits admits a measurable map
T𝑇 (H , 𝜉) = 𝐹𝑇 𝜌(O𝑧,Γ (H )), P, 𝜉 . (54) Thus compatible completions have identical transcripts under coupled 𝜉, and identical conditional laws under a common H -independent distribution for 𝜉. Proof. Equation (50) makes 𝑃 𝑘 a measurable function of [𝐵 𝑘 ] col . Initialization, masked attributes, heat features, losses and gradients therefore depend only on (𝑌L , P, 𝜉) and current states. An optimizer step and the EMA recursion preserve this dependence. Induction over local steps gives the uploads; training-count-weighted aggregation gives the next broadcast. Induction over rounds, followed by the fixed validation rule and final forward pass, proves the factorization. Coupling, then integration over 𝜉, gives the two equalities. □ Corollary 4 (Downstream invariance on learner compatibility classes). Under the preceding assumptions, equal learner releases imply, throughout training, 𝜃 𝑢 (H ) = 𝜃 𝑢 (H ′ ),

𝑢 𝑢 logit 𝑘,𝑣 (H ) = logit 𝑘,𝑣 (H ′ ).

(55)

This includes intermediate local and server states, validation selection, and final predictions, with equal conditional laws after averaging over 𝜉. Proof. Apply Theorem 4; fixed evaluation labels also give identical Accuracy and Macro-F1. 24

□

Corollary 5 (Density within observable spectral filters). For symmetric 𝑃sym (𝑌L ) with spectrum in [0, 1], every 𝑓 ∈ 𝐶 ( [0, 1]), 𝛿 > 0, and Δ > 𝜖ord admit a finite 𝑀 𝑓 and coefficients depending only on ( 𝑓 , 𝛿, Δ) such that 𝑀𝑓 ∑︁ sym sym 𝑓 (𝑃 ) − 𝑎 0 𝐼 − 𝑎 𝑏 𝑒 𝑏Δ( 𝑃 −𝐼 ) < 𝛿. (56) 𝑏=1

2

The grid 𝑡 𝑏 = 𝑏Δ is feasible in Equation (20). Proof. The change of variable 𝑥 = 𝑒 Δ(𝜆−1) maps [0, 1] homeomorphically to [𝑒 −Δ , 1]. Polynomial Í𝑀 approximation of 𝑓 (1 + log(𝑥)/Δ) gives 𝑝(𝑥) = 𝑏=0𝑓 𝑎 𝑏 𝑥 𝑏 with uniform error below 𝛿. The spectral theorem yields Equation (56); choosing each softplus increment as Δ − 𝜖 ord > 0 realizes the grid. □ Corollary 6 (Information-boundary compliance and observable spectral approximation). On a positive-degree client block, define 𝑓 (𝑃) = 𝐷 𝑣−1/2 𝑓 (𝑃sym )𝐷 1/2 and 𝐺 𝑀 𝑓 (𝑃) = 𝑎 0 𝐼 + 𝑣 Í𝑀 𝑓 𝑏Δ( 𝑃−𝐼 ) using the preceding coefficients. For every conformable 𝑈, 𝑎 𝑒 𝑏=1 𝑏 ∥ ( 𝑓 (𝑃) − 𝐺 𝑀 𝑓 (𝑃))𝑈 ∥ 𝐷𝑣 ,𝐹 ≤ 𝛿∥𝑈 ∥ 𝐷𝑣 ,𝐹 ,

∥𝑈 ∥ 𝐷𝑣 ,𝐹 = ∥𝐷 1/2 𝑣 𝑈 ∥𝐹 .

(57)

Both these transforms and the complete training transcript are shared across the learner compatibility class, for fixed P and 𝜉. Proof. Conjugate Equation (56) by 𝐷 1/2 𝑣 and use ∥ 𝐴𝑈 ∥ 𝐹 ≤ ∥ 𝐴∥ 2 ∥𝑈 ∥ 𝐹 . Invariance follows from Theorem 4. □ Density concerns the union of finite basis widths. It gives neither fixed-𝑅 universality nor a prediction or optimization guarantee for a fitted classifier. Certified evaluation. All times share the recurrence 𝑈, 𝑃𝑈, 𝑃2𝑈, . . .. For the auxiliary analytic variable 𝑁𝑡aux ∼ Poisson(𝑡), deterministic tail-collapsed evaluation is ! 𝐿−1 𝐿−1 ℓ ℓ ∑︁ ∑︁ −𝑡 𝑡 ℓ −𝑡 𝑡 b 𝑃 𝐿 𝑈. (58) K𝑡 ,𝐿 𝑈 = 𝑒 𝑃 𝑈+ 1− 𝑒 ℓ! ℓ! ℓ=0 ℓ=0 For active times Theat = {𝑡 𝑏 𝑗 : 𝑏 ∈ [𝑅], 𝑗 ∈ [𝑑]}, choose the smallest integer 𝐿 tail satisfying max Pr(𝑁𝑡aux > 𝐿 tail ) ≤ 𝜀tail ,

𝑡 ∈ Theat

max {Pr(𝑁𝑡aux = 𝐿 tail ) + 2 Pr(𝑁𝑡aux > 𝐿 tail )} ≤ 𝜀 tail .

𝑡 ∈ Theat

(59)

These bound forward and time-derivative coefficient masses. We use 𝜀 tail = 10−6 , float64 logspace probabilities, and record both bounds and 𝐿 tail for each validation-selected native checkpoint. Online and EMA branches use their own times. At 𝑅 = 0, bypass the recurrence and set 𝐿 tail = 0; configurations requiring 𝐿 tail > 4096 are refused. Floating-point propagation and accumulation errors are separate from this coefficient certificate. C.9

O BSERVABLE D IFFUSION AND P REDICTIVE DYNAMICS

Diffusion time evolves features at fixed incidence and encoder; local training steps evolve the encoder and its EMA target. The following results distinguish these two processes. Theorem 5 (Continuous-time diffusion under observational equivalence). Fix 𝑦 L , client 𝑘, and 𝑈 𝑘0 ∈ R |𝑉𝑘 | ×𝑑 . Put 𝑑 𝑘,𝑣 = (𝐷 𝑣,𝑘 ) 𝑣𝑣 and 𝑉𝑘,+ = {𝑣 : 𝑑 𝑘,𝑣 > 0}. Let 𝐷 𝑘,+ be 𝐷 𝑣,𝑘 restricted to these nodes, and use + likewise for other restrictions. For 𝑡 ≥ 0, the trajectory 𝑈 𝑘 (𝑡) = 𝑒 𝑡 ( 𝑃𝑘 −𝐼 ) 𝑈 𝑘0

(60)

uniquely solves 𝑈¤ 𝑘 = (𝑃 𝑘 − 𝐼)𝑈 𝑘 , 𝑈 𝑘 (0) = 𝑈 𝑘0 . For the incidence-induced components G𝑘 on 𝑉𝑘,+ , define Í 0 𝑢∈𝐶 𝑑 𝑘,𝑢 𝑈 𝑘,𝑢 0 (Q 𝑘,+𝑈 𝑘,+ ) 𝑣 = Í , 𝑣 ∈ 𝐶 ∈ G𝑘 . (61) 𝑢∈𝐶 𝑑 𝑘,𝑢 25

0 and ∥ 𝐴∥ 2 ⊤ Writing 𝐴 = 𝑈 𝑘,+ (𝑡) − Q 𝑘,+𝑈 𝑘,+ 𝐷 𝑘,+ ,𝐹 = tr( 𝐴 𝐷 𝑘,+ 𝐴) gives

𝑑 1 ∥ 𝐴∥ 2𝐷𝑘,+ ,𝐹 = − tr[ 𝐴⊤ 𝐷 𝑘,+ (𝐼 − 𝑃 𝑘,+ ) 𝐴] 𝑑𝑡 2 1 ∑︁ 1 ∑︁ ∥𝑈 𝑘,𝑢 (𝑡) − 𝑈 𝑘,𝑣 (𝑡) ∥ 22 ≤ 0, =− 2 𝑒 𝑑 𝑒,𝑘 𝑢,𝑣∈𝑒

(62)

where 𝑒 ranges over retained columns and 𝑑 𝑒,𝑘 = (𝐷 𝑒,𝑘 )𝑒𝑒 . If the nonstationary subspace is nonzero, let sym sym −1/2 𝜆gap,𝑘 = min{1 − 𝜆 : 𝜆 ∈ spec(𝑃 𝑘,+ ), 𝜆 < 1} > 0, 𝑃 𝑘,+ = 𝐷 1/2 (63) 𝑘,+ 𝑃 𝑘,+ 𝐷 𝑘,+ . Then

0 0 0 ∥𝑈 𝑘,+ (𝑡) − Q 𝑘,+𝑈 𝑘,+ ∥ 𝐷𝑘,+ ,𝐹 ≤ 𝑒 −𝜆gap,𝑘 𝑡 ∥𝑈 𝑘,+ − Q 𝑘,+𝑈 𝑘,+ ∥ 𝐷𝑘,+ ,𝐹 .

(64)

A zero nonstationary subspace gives zero residual. Isolated nodes stay fixed, and compatible completions with equal initial features have identical trajectories. Proof. The matrix exponential uniquely solves the finite linear system, and column invariance −1 𝐵⊤ is symmetric and 𝑃 gives the common trajectory. On 𝑉𝑘,+ , 𝐷 𝑘,+ 𝑃 𝑘,+ = 𝐵 𝑘,+ 𝐷 𝑒,𝑘 𝑘,+ Q 𝑘,+ = 𝑘,+ Q 𝑘,+ 𝑃 𝑘,+ = Q 𝑘,+ . Differentiating the energy and expanding the quadratic form gives 1 ∑︁ 1 ∑︁ tr[ 𝐴⊤ 𝐷 𝑘,+ (𝐼 − 𝑃 𝑘,+ ) 𝐴] = ∥ 𝐴𝑢 − 𝐴𝑣 ∥ 22 . (65) 2 𝑒 𝑑 𝑒,𝑘 𝑢,𝑣∈𝑒 Its null space consists of componentwise constant matrices. In symmetric coordinates, Q 𝑘,+ is the orthogonal eigenvalue-one projection; every other heat multiplier is at most 𝑒 −𝜆gap,𝑘 𝑡 . The spectral theorem proves convergence. The isolated block is the identity. □ Corollary 7 (Ordered sampling of the diffusion trajectory). Equation (20) gives, for each coordinate 𝑗, ( 𝑗) 0 = 𝑡0 𝑗 < 𝑡1 𝑗 < · · · < 𝑡 𝑅 𝑗 , 𝑊 𝑘, 𝜃 = [𝑈 𝑘,: 𝑗 (𝑡 0 𝑗 ), . . . , 𝑈 𝑘,: 𝑗 (𝑡 𝑅 𝑗 )], (66) ( 𝑗)

0 . The feasible grid 𝑡 = 𝑏Δ, where 𝑊 𝑘, 𝜃 selects columns 𝑗, 𝑑 + 𝑗, . . . , 𝑅𝑑 + 𝑗 and 𝑈 𝑘,: 𝑗 (𝑡) = K 𝑘 (𝑡)𝑈 𝑘,: 𝑏 𝑗 Δ > 𝜖ord , yields the dense algebra

span{1, 𝑒 𝑏Δ(𝜆−1) : 𝑏 ≥ 1} ⊂ 𝐶 ( [0, 1]).

(67)

Density over increasing finite widths follows from Corollary 5. Masked prediction and target dynamics. Within round 𝑢, let 𝑠 index local steps, 𝑜 denote optimizer state, 𝑌L,𝑘 = (𝑋 𝑘 , [𝐵 𝑘 ] col ), and 𝜉 𝑘,𝑢,𝑠 contain masks, minibatches, and optimizer randomness. The update has the form
(𝜃 𝑘,𝑢,𝑠 , 𝑜 𝑘,𝑢,𝑠 ) = Ψ𝑘,𝑢,𝑠 𝜃 𝑘,𝑢,𝑠−1 , 𝑜 𝑘,𝑢,𝑠−1 , 𝜗¯ 𝑘,𝑢,𝑠−1 , 𝑌L,𝑘 , P, 𝜉 𝑘,𝑢,𝑠 . (68) With 𝜗𝑘,𝑢,𝑠 = ctx(𝜃 𝑘,𝑢,𝑠 ) containing the encoder and raw time increments, the target satisfies 𝜗¯ 𝑘,𝑢,𝑠 = 𝜇 𝜗¯ 𝑘,𝑢,𝑠−1 + (1 − 𝜇)𝜗𝑘,𝑢,𝑠 = 𝜇 𝑠 𝜗¯ 𝑘,𝑢,0 + (1 − 𝜇)

𝑠 ∑︁

𝜇 𝑠−𝑎 𝜗𝑘,𝑢,𝑎 .

(69)

𝑎=1

For 𝑒 𝑘,𝑢,𝑠 = 𝜗𝑘,𝑢,𝑠 − 𝜗¯ 𝑘,𝑢,𝑠 and Δ 𝑘,𝑢,𝑠 = 𝜗𝑘,𝑢,𝑠 − 𝜗𝑘,𝑢,𝑠−1 , subtraction and iteration give 𝑒 𝑘,𝑢,𝑠 = 𝜇𝑒 𝑘,𝑢,𝑠−1 + 𝜇Δ 𝑘,𝑢,𝑠 ,

∥𝑒 𝑘,𝑢,𝑠 ∥ ≤ 𝜇 𝑠 ∥𝑒 𝑘,𝑢,0 ∥ + 𝜇

𝑠 ∑︁

𝜇 𝑠−𝑎 ∥Δ 𝑘,𝑢,𝑎 ∥.

(70)

𝑎=1

Thus a frozen online context has lag contraction factor 𝜇. The input masking moments in Equation (110) do not imply unbiased nonlinear encodings or gradients. Lemma 1 (Observation invariance throughout training). For fixed P and coupled 𝜉, the masked loss, online, optimizer and EMA states, uploads, broadcasts, selected checkpoint, and final logits are measurable in (𝑌L , P, 𝜉) and agree across its compatibility class.

26

Proof. This is Theorem 4 applied to the local recursions above and the aggregation Í tr 𝑢+1 𝑘∈C 𝑛 𝜃 𝑢+1 𝑢 𝑢+1 𝜃 𝑘 = U 𝑘,𝑢 (𝜃 , 𝑌L,𝑘 , P, 𝜉 𝑘,𝑢 ), 𝜃 = Í 𝑢 𝑘 tr𝑘 . 𝑘 ∈ C𝑢 𝑛 𝑘

(71) □

Diffusion dissipation and EMA lag concern distinct dynamics; neither is a Lyapunov function for joint nonlinear training. Observation invariance also supplies no formal privacy guarantee for communicated updates. C.10

D OWNSTREAM R ISK WITH A DDITIONAL I NFORMATION

We compare fitted predictors under one joint law of data, training randomness, and held-out query nodes. Conditional averaging and information comparison are classical (Blackwell, 1953; Chen et al., 2020); here they connect prediction variation to the assignment geometry of Theorem 1. Information and fitted risk. For a queried node with class 𝑦 ∈ [𝐶], 𝐶 ≥ 2, let 𝑂 𝑘 contain client features and anonymous incidence, the query, the parameter-only transcript through validation selection, and exogenous randomness. Held-out labels, test outcomes, auxiliary messages, and states trained using those messages are excluded. Set S0 = 𝜎(𝑂 𝑘 ); the FedASTRA predictor 𝐹 is S0 -measurable. This permits federated parameter exchange while keeping structural computation local. Let 𝐴aux include arbitrary additional information and any training state needed for an enriched predictor 𝐺, measurable in S1 = S0 ∨ 𝜎( 𝐴aux ). The predictors may have different learned parameters. A conditional structural audit may fix analyst releases and cost arrays in the base, but such conditioning does not grant deployment access to them. Define, with one-hot label 𝒆 𝑦 , 𝑝 0 = E[𝒆 𝑦 | S0 ], 𝑠 𝐹 = 𝐽𝐶 logit𝐹 ,

𝑝 1 = E[𝒆 𝑦 | S1 ], 𝑠𝐺 = 𝐽𝐶 logit𝐺 ,

𝐽𝐶 = 𝐼𝐶 − 11⊤ /𝐶, 𝑠¯𝐺 = E[𝑠𝐺 | S0 ].

(72) (73)

Í Assume square-integrable logits. Centering preserves softmax. Write lse(𝑠) = log 𝑐 𝑒 𝑠𝑐 , R CE (𝑠) = E[lse(𝑠) − 𝑠 𝑦 ], and R log (𝑞) = E[− log 𝑞 𝑦 ] with the usual convention at zero. Conditional log risk equals conditional entropy plus expected KL divergence. Consequently, inf

𝑞 S0 -measurable

R log (𝑞) −

inf

𝑞 S1 -measurable

R log (𝑞) = Iadd := E𝐷 KL ( 𝑝 1 ∥ 𝑝 0 ) ≥ 0.

(74)

Indeed, the minimizers are 𝑝 0 , 𝑝 1 and the tower property identifies the entropy difference. For fitted probability rules of finite log risk, put E 𝐹 = E𝐷 KL ( 𝑝 0 ∥𝑞 𝐹 ) and E𝐺 = E𝐷 KL ( 𝑝 1 ∥𝑞 𝐺 ). Subtracting R log (𝑞 𝐹 ) = 𝐻 (𝑦 | S0 ) + E 𝐹 from R log (𝑞 𝐺 ) = 𝐻 (𝑦 | S1 ) + E𝐺 proves Equation (16). Thus 𝐹 strictly improves on 𝐺 exactly when E𝐺 − E 𝐹 > Iadd . Theorem 6 (Cross-entropy comparison with arbitrary additional information). In the model above, define 𝑉aux = E∥𝑠𝐺 − 𝑠¯𝐺 ∥ 22 , 𝛿 𝐹 = R CE (𝑠 𝐹 ) − R CE ( 𝑠¯𝐺 ),

Δlabel = E∥ 𝑝 1 − 𝑝 0 ∥ 22 , 𝐶label = E⟨𝑝 1 − 𝑝 0 , 𝑠𝐺 − 𝑠¯𝐺 ⟩.

(75) (76)

For 𝐷 lse (𝑎, 𝑏) = lse(𝑎) − lse(𝑏) − ⟨∇ lse(𝑏), 𝑎 − 𝑏⟩, R CE (𝑠𝐺 ) − R CE (𝑠 𝐹 ) = E𝐷 lse (𝑠𝐺 , 𝑠¯𝐺 ) − 𝐶label − 𝛿 𝐹 .

(77)

If ∥𝑠𝐺 ∥ ∞ ≤ 𝐵logit < ∞ almost surely, then √︁ 𝑒 −2𝐵logit 𝑉aux − Δlabel𝑉aux − 𝛿 𝐹 . (78) 2𝐶 A positive right side gives strictly smaller risk for 𝐹. Under label sufficiency 𝑝 1 = 𝑝 0 , the alignment term 𝐶label vanishes. R CE (𝑠𝐺 ) − R CE (𝑠 𝐹 ) ≥

27

Proof. Put 𝑟 = 𝑠𝐺 − 𝑠¯𝐺 , so E[𝑟 | S0 ] = 0. The Bregman linear term has zero expectation, and E⟨𝒆 𝑦 , 𝑟⟩ = E⟨𝑝 1 , 𝑟⟩ = E⟨𝑝 1 − 𝑝 0 , 𝑟⟩ = 𝐶label .

(79)

Subtracting risks proves Equation (77); in particular, taking 𝑠 𝐹 = 𝑠¯𝐺 (so 𝛿 𝐹 = 0) gives R CE (𝑠𝐺 ) − R CE ( 𝑠¯𝐺 ) = E𝐷 lse (𝑠𝐺 , 𝑠¯𝐺 ) − 𝐶label . For 𝑝 = softmax(𝑠) with ∥𝑠∥ ∞ ≤ 𝐵logit , 𝑝 𝑐 ≥ 𝑒 −2𝐵logit /𝐶. For 𝑣 ⊥ 1 and 𝑎 = 𝑝 ⊤ 𝑣, 𝑣 ⊤ ∇2 lse(𝑠)𝑣 =

∑︁

𝑝 𝑐 (𝑣 𝑐 − 𝑎) 2 ≥

𝑐

𝑒 −2𝐵logit ∑︁ 𝑒 −2𝐵logit (𝑣 𝑐 − 𝑎) 2 ≥ ∥𝑣∥ 22 . 𝐶 𝐶 𝑐

(80)

The segment from 𝑠¯𝐺 to 𝑠𝐺 remains bounded and centered. Integral Taylor remainder gives 𝐷 lse (𝑠𝐺 , 𝑠¯𝐺 ) ≥ 𝑒 −2𝐵logit ∥𝑟 ∥ 22 /(2𝐶), proving the bound and Equation (17). □ The Bregman term charges variation around the base-conditional mean; 𝐶label credits alignment with new label signal, and the signed 𝛿 𝐹 retains fitting quality. If 𝐴aux is base-measurable, both 𝑉aux and Δlabel vanish. Proposition 5 (Assignment geometry of auxiliary prediction variation). Condition on base information fixing the cost arrays and intercepts. In the exact strata of Theorem 1, declare independent uniform candidate permutations 𝜛ℎ ∈ Sym(𝑚 ℎ ) and affine logits [logit𝐺 ] 𝑐 = 𝑏 𝑐 +

𝑚ℎ ∑︁ ∑︁ ℎ

Set 𝐶¯ ℎ = 𝐶 −1

Í

[𝐶𝑐ℎ ] 𝑖, 𝜛ℎ (𝑖) ,

𝑐 ∈ [𝐶].

(81)

𝐶 1 ∑︁ eℎ 2 ∥𝐶 ∥ . 𝑚 − 1 𝑐=1 𝑐 𝐹 ℎ:𝑚 ≥2 ℎ

(82)

𝑖=1

ℎ ℎ eℎ ¯ℎ 𝑐 𝐶𝑐 and 𝐶𝑐 = 𝐽𝑚ℎ (𝐶𝑐 − 𝐶 )𝐽𝑚ℎ . Then

E[∥𝑠𝐺 − 𝑠¯𝐺 ∥ 22 | S0 ] =

∑︁ ℎ

. A scalar cost 𝐶 ℎ has variance ∥𝐽

Averaging gives 𝑉aux strata have zero variance.

𝑚ℎ 𝐶

ℎ𝐽

2 𝑚ℎ ∥ 𝐹 /(𝑚 ℎ − 1) for 𝑚 ℎ ≥ 2; singleton

Proof. Double centering Í a fixed cost 𝐶∗ changes assignment sums by a constant. For 𝐷 ∗ = 𝐽𝑚 𝐶∗ 𝐽𝑚 and uniform 𝜛, 𝑆 = 𝑖 [𝐷 ∗ ] 𝑖, 𝜛 (𝑖) has zero mean. Equal-row terms in E𝑆 2 contribute ∥𝐷 ∗ ∥ 2𝐹 /𝑚; distinct-row terms give ∑︁ ∑︁ ∥𝐷 ∗ ∥ 2𝐹 1 [𝐷 ∗ ] 𝑖 𝑗 [𝐷 ∗ ] 𝑖 ′ 𝑗 ′ = . 𝑚(𝑚 − 1) 𝑖≠𝑖 ′ 𝑗≠ 𝑗 ′ 𝑚(𝑚 − 1)

(83)

Í The equality uses 𝑖 ′ ≠𝑖, 𝑗 ′ ≠ 𝑗 [𝐷 ∗ ] 𝑖 ′ 𝑗 ′ = [𝐷 ∗ ] 𝑖 𝑗 , from zero row and column sums. Adding gives Var(𝑆) = ∥𝐷 ∗ ∥ 2𝐹 /(𝑚 − 1). Class centering replaces 𝐶𝑐ℎ by 𝐶𝑐ℎ − 𝐶¯ ℎ ; summing the scalar identities over classes and independent strata proves the claim. □ Thus the same interaction detects nonidentification and measures variation under the declared matching law. A scalar assignment interval of width 𝑤 ∗ gives variance at most 𝑤 2∗ /4. Uniform endpoint bounds for 𝐶𝑐ℎ − 𝐶¯ ℎ , together with uniformly bounded centered intercepts, can supply 𝐵logit across base realizations. Class centering is essential because common logit shifts do not affect predictions. Nonlinear auxiliary rules remain covered by Theorem 6. Corollary 8 (A conditional advantage for the fitted FedASTRA predictor). Under the bounded-logit assumptions above, let 𝐹𝑅 be the fitted parameter-only FedASTRA predictor with 𝑅 positive heat channels. If 𝛿 𝐹𝑅 ≤ 𝜀 𝑅 for a stated 𝜀 𝑅 ≥ 0, then √︁ 𝑒 −2𝐵logit 𝑉aux − Δlabel𝑉aux > 𝜀 𝑅 =⇒ R CE (𝑠 𝐹𝑅 ) < R CE (𝑠𝐺 ). (84) 2𝐶 For a conditionally label-independent candidate channel, the square-root term is zero; affine assignment logits have the variance in Proposition 5. 28

Proof. Transcript factorization makes 𝐹𝑅 base-measurable. Substitute the residual bound into Equation (78); conditional label independence gives 𝑝 1 = 𝑝 0 . □ Under label sufficiency 𝑝 1 = 𝑝 0 , equivalently 𝑦 ⊥ 𝐴aux | S0 , the two information levels have the same conditional entropy. Hence, for 𝑝 𝐹𝑅 = softmax(𝑠 𝐹𝑅 ) and 𝑝 𝐺 = softmax(𝑠𝐺 ), R log ( 𝑝 𝐺 ) − R log ( 𝑝 𝐹𝑅 ) = E𝐷 KL ( 𝑝 0 ∥ 𝑝 𝐺 ) − E𝐷 KL ( 𝑝 0 ∥ 𝑝 𝐹𝑅 ). (85) If the fixed-𝑅 class approximates 𝑝 0 arbitrarily well in expected KL, its infimum equals both information-specific Bayes risks. A fitted error at most 𝜀 𝑅 strictly improves on a specified 𝐺 with larger KL error. Label sufficiency, fixed-model approximation, and fitting are separate assumptions; spectral density and correspondence invariance imply none of them. Proposition 6 (Target direction of the masked alignment component). Freeze the EMA context 𝜗¯ 𝑘 for one local update. Let 𝑂 mask be the predictor’s masked representation and 𝑈tar its full-view, layer-normalized and unit-normalized target, with ∥𝑈tar ∥ 2 = 1 almost surely. Then inf E[1 − ⟨𝑢(𝑂 mask ), 𝑈tar ⟩] = 1 − E∥E[𝑈tar | 𝑂 mask ] ∥ 2 . (86) 𝑢: ∥𝑢(𝑂mask ) ∥ 2 =1

For 𝑚 = E[𝑈tar | 𝑂 mask ] ≠ 0, the minimizing direction is 𝑚/∥𝑚∥ 2 ; when 𝑚 = 0, every unit direction is optimal. Proof. Conditional expected alignment is ⟨𝑢, 𝑚⟩ ≤ ∥𝑚∥ 2 by Cauchy–Schwarz, with equality in the stated directions. Integrate the optimum. □ This concerns the frozen-target alignment component with unrestricted directions. Anti-collapse regularization, two-view agreement, moving targets, and finite predictors remain in the full objective (112) and its optimization analysis. Classification metrics. For base-measurable 𝑝 𝐹 = softmax(𝑠 𝐹 ), let ℎ 𝐹 = arg max𝑐 𝑝 𝐹,𝑐 and ℎ0 = arg max𝑐 𝑝 0,𝑐 with a fixed tie rule. Comparing their selected coordinates and applying Pinsker √︁ and Cauchy–Schwarz bounds classification regret by E∥ 𝑝 0 − 𝑝 𝐹 ∥ 1 ≤ 2E𝐷 KL ( 𝑝 0 ∥ 𝑝 𝐹 ). This is regret against the base Bayes rule; a surrogate-risk ordering alone need not order two fitted classifiers’ accuracies. If additionally 𝑝 1 = 𝑝 0 , the top-two conditional probability gap is at least 𝜅cls > 0, and ℎ 𝐹𝑅 = ℎ0 almost surely, then Acc(𝐹𝑅 ) − Acc(𝐺) ≥ 𝜅 cls Pr(ℎ𝐺 ≠ ℎ0 ) by conditioning on S1 . Macro-F1 also depends on classwise confusion probabilities: increased true positives and decreased false positives and false negatives suffice, whereas cross-entropy ordering alone does not determine it. Both metrics use the same held-out evaluation protocol. C.11

R ANDOMIZED R ECOVERY FROM D IFFUSION F EATURES AND L OCAL P REDICTION R ISK

Heat features retain permitted local information when they recover the diffusion operator and its pairwise projection, and that projection determines the observed incidence. These are separate conditions, independent of unknown correspondence across clients. Incidence is binary; column multiplicities are retained unless simplicity is assumed. Lemma 2 (Projection and recovery from diffusion features). Let 𝐵 have 𝑛 rows and nonempty columns, and let 𝑃 be Equation (18), including absorbing isolated nodes. For 𝑖 ≠ 𝑗, 𝑃𝑖 𝑗 > 0 exactly when a column contains both nodes, so its off-diagonal support determines the pairwise projection 𝐺 (𝐵). Fix Δ > 0, 𝑑, ℓ ≥ 1, 𝑈 ∈ R𝑛×𝑑 , and 𝐻Δ = 𝑒 Δ( 𝑃−𝐼 ) . Define 𝑄 − = [𝑈, 𝐻Δ𝑈, . . . , 𝐻Δℓ −1𝑈], 𝑄 + = [𝐻Δ𝑈, . . . , 𝐻Δℓ 𝑈]. (87) If rank(𝑄 − ) = 𝑛, then in exact arithmetic 𝐻Δ = 𝑄 + 𝑄 †− , 𝑃 = 𝐼 + Δ−1 log 𝐻Δ , (88) using the Moore–Penrose inverse and principal matrix logarithm. Times 𝑏Δ are permitted commontime ordered heat channels when Δ > 𝜖 ord . Í Proof. For positive-degree 𝑖, 𝑃𝑖 𝑗 = 𝑑𝑖−1 𝑒 𝐵𝑖𝑒 𝐵 𝑗𝑒 /|𝑒|; nonnegativity proves the support claim, and isolated rows add no pairs. Since 𝑄 + = 𝐻Δ 𝑄 − , full row rank proves the first inverse. On positivedegree nodes, 𝑃 is similar to the positive semidefinite symmetric matrix 𝐷 𝑣−1/2 𝐵𝐷 𝑒−1 𝐵⊤ 𝐷 𝑣−1/2 and is stochastic; its spectrum lies in [0, 1]. The isolated block is the identity. Thus 𝑃 is diagonalizable with real spectrum and log 𝑒 Δ( 𝑃−𝐼 ) = Δ(𝑃 − 𝐼). □ 29

Randomized full rank. Retain 𝑈 = [𝑋, 𝑍], where 𝑍 ∈ R𝑛×𝑑pr has independent standard Gaussian entries independent of the hypergraph, attributes, and labels. Let 𝑛eig count the distinct eigenvalues of 𝑃, with largest multiplicity 𝑔max . Then ℓ ≥ 𝑛eig and 𝑑pr ≥ 𝑔max give rank(𝑄 − ) = 𝑛 almost surely. Indeed, in 𝑃 = 𝑆Λ𝑆 −1 , each eigenspace block of 𝑆 −1 𝑍 has full row rank almost surely. A vector annihilating the Krylov matrix yields a Vandermonde system in the distinct eigenvalues of 𝐻Δ ; invertibility forces every eigenspace coefficient, and hence the vector, to vanish. In particular, 𝑑pr ≥ 𝑛, ℓ = 1 suffices for every 𝑃. These probes remain local and are absent from reported runs; the finite attribute encoder needs its own rank check. A reconstructible random family. Let E 𝑛 ⊆ A 𝑛 be any random simple hypergraph, where candidate supports 𝑒 ∈ A 𝑛 satisfy |𝑒| ≥ 2. Let Ω2 contain unordered distinct edge pairs with intersection size at least two, and Ω3 unordered triples supporting a Berge triangle: distinct 𝑢, 𝑣, 𝑤 and an ordering 𝑒, 𝑓 , 𝑔 with {𝑢, 𝑣} ⊂ 𝑒, {𝑣, 𝑤} ⊂ 𝑓 , {𝑤, 𝑢} ⊂ 𝑔. Define ∑︁ ∑︁ 𝜀 all Pr(𝑒, 𝑓 ∈ E 𝑛 ) + Pr(𝑒, 𝑓 , 𝑔 ∈ E 𝑛 ). (89) 𝑛 = {𝑒, 𝑓 } ∈Ω2

{𝑒, 𝑓 ,𝑔} ∈Ω3

These are actual joint inclusion probabilities; edges need not be independent, uniform in size, or bounded in degree. The condition concerns the local incidence law, since partitioning can create singletons or duplicates. Proposition 7 (Nonuniform and dependent reconstruction family). A deterministic decoder recovers [𝐵] col from 𝐺 (𝐵) with probability at least 1 − 𝜀 all 𝑛 . For every projected edge 𝑢𝑣, it forms {𝑢, 𝑣} ∪ (𝑁𝐺 (𝑢) ∩ 𝑁𝐺 (𝑣)) and removes repeated sets. An adjacency-matrix implementation costs 𝑂 (𝑛3 ) operations. Proof. The union bound excludes both configurations with probability at least 1 − 𝜀 all 𝑛 . Then each projected pair 𝑢𝑣 belongs to a unique edge 𝑒. Its other members are common neighbors. An external common neighbor 𝑤 would give edges containing 𝑢𝑤 and 𝑣𝑤: if equal they overlap 𝑒 twice, and if distinct they form a Berge triangle with 𝑒. Thus each candidate equals 𝑒. Every edge contains a pair; scanning at most 𝑛2 pairs and 𝑛 neighbors proves recovery and the cost. □ Incidence forests have 𝜀 all 𝑛 = 0, permitting dependent, nonuniform edges and order-𝑛 edge counts. More generally, 𝜀 all → 0 suffices. The following transfer also accepts other decoders with proved 𝑛 failure bounds, including reconstruction results for independent uniform hypergraphs (Bresler et al., 2025). Theorem 7 (Heat recovery and asymptotic preservation of local information). Let 𝑂 𝑛 = (𝑋𝑛 , [𝐵𝑛 ] col ) have any joint law with 𝑦 𝑛 ∈ [𝐶], where 𝐶 ≥ 2 is fixed. Suppose a decoder from 𝐺 (𝐵𝑛 ) recovers pr [𝐵𝑛 ] col with failure probability at most 𝜀 rec 𝑛 . Let 𝑇𝑛 = Ψ𝑛 (𝑂 𝑛 , 𝜉 𝑛 ), where Ψ𝑛 is fixed and measurable pr and 𝜉 𝑛 is independent of (𝑂 𝑛 , 𝑦 𝑛 ). Suppose 𝑇𝑛 retains the features in Lemma 2 and enough information to recover 𝑋𝑛 , with joint rank/attribute-recovery failure probability at most 𝜀 obs 𝑛 . A pr obs . For 𝜀 ≤ 1/2, decoder from (𝑇𝑛 , 𝜉 𝑛 ) then recovers 𝑂 𝑛 with error at most 𝜀 𝑛 = 𝜀 rec + 𝜀 𝑛 𝑛 𝑛 ∗ ∗ 0 ≤ R heat,n − R loc,n ≤ ℎ2 (𝜀 𝑛 ) + 𝜀 𝑛 log 𝐶 =: 𝑑 𝑛 ,

(90)

pr

∗ ∗ where R heat,n = 𝐻 (𝑦 𝑛 | 𝑇𝑛 , 𝜉 𝑛 ), R loc,n = 𝐻 (𝑦 𝑛 | 𝑂 𝑛 ), and ℎ2 (𝑢) = −𝑢 log 𝑢 − (1 − 𝑢) log(1 − 𝑢), with 0 log 0 = 0. Hence 𝑑 𝑛 = 𝑂 (𝜀 𝑛 log(1/𝜀 𝑛 )) → 0 when 𝜀 𝑛 → 0.

Proof. On simultaneous success, Equation (88) recovers 𝑃, its positive off-diagonal support gives 𝐺 (𝐵𝑛 ), and the incidence and attribute decoders give 𝑂 𝑛 . The union bound proves the error claim. Data processing gives the nonnegative entropy gap. If 𝐸 indicates decoder failure, 𝑂 𝑛 is determined pr by (𝑇𝑛 , 𝜉 𝑛 , 𝐸 = 0), so pr

𝐼 (𝑦 𝑛 ; 𝑂 𝑛 | 𝑇𝑛 , 𝜉 𝑛 ) ≤ 𝐻 (𝐸) + Pr(𝐸 = 1) log 𝐶 ≤ ℎ2 (𝜀 𝑛 ) + 𝜀 𝑛 log 𝐶. Independence of the seed and deterministic generation of 𝑇𝑛 identify this mutual information with the entropy gap; Bayes cross-entropy equals conditional entropy. □

30

Why incidence recovery needs an assumption. On six vertices, E1 = {123, 145, 246, 356} and E2 = {124, 135, 236, 456} have degree two and identical pair co-incidences. Thus 𝐵1 𝐵1⊤ = 𝐵2 𝐵2⊤ and 𝑃1 = 𝑃2 = 𝐵1 𝐵1⊤ /6, despite different column-permutation classes. Identical attributes give identical heat features at every time. A uniform mixture, padded with common isolated nodes, has reconstruction error at least 1/2. Duplicating all columns also preserves 𝑃 for multihypergraphs. Additional heat channels cannot remove either ambiguity. Recovery at a queried node. For a simple hypergraph E with edge sizes at least two, let 𝑉amb (E) contain endpoints of pairs lying in two distinct edges and the three cycle vertices of each Berge query triangle. Put 𝑝 𝑛,𝑣 = Pr(𝑣 ∗ = 𝑣 | E 𝑛 ) for the queried vertex 𝑣 ∗ . Proposition 8 (Query-weighted recovery and prediction risk). For 𝑣 ∉ 𝑉amb (E), its incident edge set satisfies b(𝑣) = unique{{𝑣, 𝑢} ∪ (𝑁𝐺 (𝑣) ∩ 𝑁𝐺 (𝑢)) : 𝑢 ∈ 𝑁𝐺 (𝑣)} = E (𝑣), E (91) where E (𝑣) = {𝑒 ∈ E : 𝑣 ∈ 𝑒} and unique removes repeats. Under any joint edge law, failure at 𝑣 ∗ has probability at most 𝑛 ∑︁ query query 𝜀𝑛 =E 𝑝 𝑛,𝑣 1{𝑣 ∈ 𝑉amb (E 𝑛 )}, (92) 𝑣=1

equal to E|𝑉amb (E 𝑛 )|/𝑛 for an independent uniform query. More generally, let 𝑂 𝑛 include all pr permitted local information and the query, and let 𝑆 task 𝑛 be measurable from 𝑂 𝑛 . If 𝑇𝑛 = Ψ𝑛 (𝑂 𝑛 , 𝜉 𝑛 ) pr for fixed measurable Ψ𝑛 and a seed independent of (𝑂 𝑛 , 𝑦 𝑛 ), 𝑦 𝑛 ∈ [𝐶], and (𝑇𝑛 , 𝜉 𝑛 ) recovers 𝑆 task 𝑛 with error at most 𝛿 𝑛 ≤ 1/2, then pr

0 ≤ 𝐻 (𝑦 𝑛 | 𝑇𝑛 , 𝜉 𝑛 ) − 𝐻 (𝑦 𝑛 | 𝑂 𝑛 ) ≤ 𝐼 (𝑦 𝑛 ; 𝑂 𝑛 | 𝑆 task 𝑛 ) + ℎ2 (𝛿 𝑛 ) + 𝛿 𝑛 log 𝐶.

(93)

Proof. For 𝑣 ∉ 𝑉amb each pair 𝑣𝑢 has a unique source edge 𝑒. An external common neighbor would create either a repeated pair through 𝑣 or a Berge triangle with cycle vertex 𝑣, exactly as in Proposition 7. Thus the decoder returns precisely all incident edges, including the empty set at an isolated vertex. Conditioning on E 𝑛 proves the failure bound. The failure-indicator argument above pr pr task | gives 𝐼 (𝑦 𝑛 ; 𝑆 task | 𝑇𝑛 , 𝜉 𝑛 ) ≤ ℎ2 (𝛿 𝑛 ) + 𝛿 𝑛 log 𝐶. Use 𝐻 (𝑦 𝑛 | 𝑇𝑛 , 𝜉 𝑛 ) ≤ 𝐻 (𝑦 𝑛 | 𝑆 task 𝑛 𝑛 ) + 𝐼 (𝑦 𝑛 ; 𝑆 𝑛 pr 𝑇𝑛 , 𝜉 𝑛 ), subtract 𝐻 (𝑦 𝑛 | 𝑂 𝑛 ), and apply measurability and data processing. □ If 𝑆 task 𝑛 contains the query, its incident edges and their member attributes (including its own when query isolated), the rank and attribute assumptions give 𝛿 𝑛 ≤ 𝜀 𝑛 + 𝜀 obs 𝑛 . Only the probability of querying task an affected vertex must vanish; 𝐼 (𝑦 𝑛 ; 𝑂 𝑛 | 𝑆 𝑛 ) separately charges label information beyond this neighborhood. No locality of the dense heat operator is assumed. For known two-node simple graphs, projection recovers every edge, including those in cycles. For a concrete separation, put 𝑚 𝑛 → ∞, 𝑚 𝑛 /𝑛 → 0 disjoint six-node examples among 𝑛 vertices, choose their incidences independently and uniformly, and put a fixed incidence forest elsewhere. With fixed noninformative attributes, an encoder independent of these choices, and a retained query index, all 2𝑚𝑛 incidences have identical heat features, even with independent probes. Full reconstruction query succeeds with probability at most 2−𝑚𝑛 , yet 𝜀 𝑛 ≤ 6𝑚 𝑛 /𝑛. Label each block vertex by its block choice and forest vertices by zero. Full incidence determines the labels; for a uniform query the optimal full-matrix heat cross-entropy is (6𝑚 𝑛 /𝑛) log 2 → 0. These are information bounds for the complete local heat matrix. Its decoder need not be expressible by the implemented finite encoder and rowwise classifier. The next bound retains that approximation error, shared-parameter cost, and training error; neither private probes nor a reconstruction stage is added to the implementation or its payload. C.12

S TOCHASTIC F EDERATED O PTIMIZATION AND R ISK T RANSFER

Population risk and shared parameters. Let a random node belong to client 𝑘 with probability Í testpop pop 𝑤 𝑘 , and write R 𝑘 (𝜃) = E[− log 𝑞 𝜃 ,𝑘 (𝑦)], R fed (𝜃) = 𝑘 𝑤 𝑘 R 𝑘 (𝜃) for the actual prediction rule. Í Evaluation weights may differ from FedAvg weights 𝑤 tr𝑘 = 𝑛tr𝑘 / 𝑗 𝑛tr𝑗 . All posterior risks include the same permitted training-side information and exclude held-out labels. If conditioning on a training transcript, include the realized probe seed in both local and heat information: the representation 31

is then deterministic given these data, and recovery bounds must hold under the conditional law. Unconditional probe independence need not survive this conditioning. Expectations also average over training and algorithmic randomness. Theorem 8 (From local information to shared-model population risk). Let Θ be a nonempty shared parameter domain with finite risks and b 𝜃 ∈ Θ. For each client suppose the optimal local and heat ∗ ∗ risks satisfy 0 ≤ R heat,𝑘 − R loc,𝑘 ≤ 𝑑 𝑘 , using Theorem 7 or Proposition 8. Define   ∗ 𝑎 𝑘 = inf R 𝑘 (𝜃) − R heat,𝑘 , 𝜃 ∈Θ + ∑︁ ∑︁ pop pop 𝑎 share = inf 𝑤 𝑘 R 𝑘 (𝜃) − 𝑤 𝑘 inf R 𝑘 (𝜃) ≥ 0. (94) 𝜃 ∈Θ

𝜃 ∈Θ

𝑘

𝑘

Here [𝑥] + = max{𝑥, 0}; 𝑎 𝑘 includes finite-encoder and rowwise-readout restrictions, and 𝑎 share charges shared parameters. For fixed empirical training cross-entropy 𝐽 𝑁 on 𝑁 labels, suppose E sup |𝐽 𝑁 (𝜃) − R fed (𝜃)| ≤ 𝑢 𝑁 , E[𝐽 𝑁 ( b 𝜃) − inf 𝐽 𝑁 (𝜃)] ≤ 𝑒 𝑁 ,𝑇 . (95) 𝜃 ∈Θ

𝜃 ∈Θ

Then, without independence across clients, " # " # ∑︁ ∑︁ pop pop ∗ 𝑤 𝑘 (𝑑 𝑘 + 𝑎 𝑘 ) + 𝑎 share + 2𝑢 𝑁 + 𝑒 𝑁 ,𝑇 . E R fed ( b 𝜃) − 𝑤 𝑘 R loc,𝑘 ≤ E 𝑘

(96)

𝑘

Expectations include any conditioning information on which the risks depend. 𝜃) ≤ E inf Θ R fed + 2𝑢 𝑁 + 𝑒 𝑁 ,𝑇 . Substitute the Proof. Two uniform-discrepancy bounds give ER fed ( b ∗ definition of 𝑎 share and inf Θ R 𝑘 − R loc,𝑘 ≤ 𝑎 𝑘 + 𝑑 𝑘 . For transcript-conditioned risks apply these inequalities conditionally and average. □ The random-test-node objective needs weighted recovery errors, not simultaneous recovery at every client. A single parameter sequence approaching all positively weighted client optima suffices for 𝑎 share = 0; separate local approximation does not. If cross-entropies lie in [0, 𝑀], 𝑢 𝑁 is at most the training-weighted uniform sampling deviation plus 𝑀 ∥𝑤 tr − 𝑤 pop ∥ 1 /2. Dependent hypergraphs supply no automatic independent-node concentration rate. Actual displacements and task progress. Let 𝑑 𝑘,𝑢,𝑠 = 𝜃 𝑘,𝑢,𝑠 −𝜃 𝑘,𝑢,𝑠+1 be the realized displacement at local step 𝑠 of round 𝑢, with 𝑆 𝑘,𝑢 steps. Full-participation FedAvg gives 𝐷 𝑢 = 𝜃 𝑢 − 𝜃 𝑢+1 =

∑︁ 𝑘

𝑤 tr𝑘

𝑆𝑘,𝑢 ∑︁−1

𝑑 𝑘,𝑢,𝑠 .

(97)

𝑠=0

Masks, minibatches, dropout, clipping, optimizer moments, weight decay, numerical heat evaluation, and target motion enter through these displacements. Different step counts are allowed; subsampling uses normalized participating-client weights. Proposition 9 (Task-risk bound along the implemented trajectory). Let 𝐽 𝑁 be evaluation-mode empirical cross-entropy with exact heat, and let 𝐿 𝑢 ≥ 0 bound its largest Hessian eigenvalue on {𝜃 𝑢 − 𝑎𝐷 𝑢 : 0 ≤ 𝑎 ≤ 1}. For every prefix of every finite realized trajectory, ∑︁  𝐽 𝑁 (𝜃 𝑡 ) ≤ 𝐽 𝑁 (𝜃 0 ) − ⟨∇𝐽 𝑁 (𝜃 𝑢 ), 𝐷 𝑢 ⟩ − 12 𝐿 𝑢 ∥𝐷 𝑢 ∥ 22 . (98) 𝑢<𝑡

A positive bracket guarantees strict reduction that round. The inequality holds simultaneously for all prefixes, including any validation-selected checkpoint; its right side minus inf Θ 𝐽 𝑁 , followed by expectation, bounds 𝑒 𝑁 ,𝑇 . ∫1 2 𝑢 2 Proof. Taylor’s integral remainder is 0 (1 − 𝑎)𝐷 ⊤ 𝑢 ∇ 𝐽 𝑁 (𝜃 − 𝑎𝐷 𝑢 )𝐷 𝑢 𝑑𝑎 ≤ 𝐿 𝑢 ∥𝐷 𝑢 ∥ 2 /2; sum over rounds. This is pathwise and requires neither unbiased gradients, a fixed teacher, nor gradient domination. The native evaluation network’s linear maps, GELU, softplus, matrix exponential, positive-epsilon LayerNorm, and cross-entropy are smooth, giving finite curvature on each finite segment. The scale model also uses LayerNorm and a smooth closed-form heat operator. Predictive anti-collapse losses affect 𝐷 𝑢 but are absent from 𝐽 𝑁 ; baseline BatchNorm buffers are outside this proof. □ 32

logit

If implemented logits differ from exact logits by at most 𝜖 𝑢 in infinity norm at checkpoint 𝑢, logit logit the 2-Lipschitz property of cross-entropy adds only 2𝜖0 + 2𝜖 𝑡 to the implemented-loss bound. Gradients and curvatures refer to exact heat; intermediate numerical errors enter 𝐷 𝑢 . Classifier, Adam, and target identities. Split parameters into context 𝜗, classifier 𝜃 cls , and masked predictor 𝜃 pred . The predictive loss does not use the classifier, so ∇ 𝜃cls Lpred,k = 0,

∇ 𝜃cls L 𝑘 = ∇ 𝜃cls LCE,k .

(99)

Joint clipping can rescale this gradient, and context updates change its inputs. Suppress client/round clip indices, let 𝑔𝑠 be the realized stochastic gradient, 𝑐 𝑠 ∈ [0, 1] its clipping multiplier, ℓ𝑠 > 0 the clip learning rate, and 𝜆wd ≥ 0 weight decay. Coupled Adam uses 𝑧 𝑠 = 𝑐 𝑠 𝑔𝑠 + 𝜆wd 𝜃 𝑠 . From zero moments, 𝑚 b𝑠 = 𝑧 𝑠 +

∑︁ (1 − 𝛽1 ) 𝛽 𝑠− 𝑗 𝑗<𝑠

1 1 − 𝛽1𝑠+1

(𝑧 𝑗 − 𝑧 𝑠 ),

√︁ 𝑑 𝑠 = ℓ𝑠 diag( b 𝑣 𝑠 + 𝜖 Adam ) −1 𝑚 b𝑠 ,

(100)

𝑠− 𝑗 ⊙2 𝑠+1 𝑗 ≤𝑠 𝛽2 𝑧 𝑗 /(1 − 𝛽2 ), 𝛽1 , 𝛽2 ∈ [0, 1), 𝜖 Adam > 0, and ⊙2 is coordinatewise clip squaring. AdamW instead sets 𝑧 𝑠 = 𝑐 𝑠 𝑔𝑠 and adds ℓ𝑠 𝜆wd 𝜃 𝑠 to 𝑑 𝑠 . The native optimizer resets each

where b 𝑣 𝑠 = (1 − 𝛽2 )

Í

round. The target also resets to 𝜗¯0 = 𝜗0 , and post-step EMA gives ∑︁ ∑︁ ¯𝑠 = − 𝜗¯𝑠 = 𝜗0 − (1 − 𝜇 𝑠− 𝑗 )𝑑 ctx , 𝜗 − 𝜗 𝜇 𝑠− 𝑗 𝑑 ctx 𝑠 𝑗 𝑗 . 𝑗<𝑠

(101)

𝑗<𝑠

These exact identities enter Equation (98), even when moving-target updates are not gradients of one fixed loss. EMA controls lag to the current context, not distance to a fixed reference teacher. Neither these identities nor the architecture guarantees task alignment; general Adam can fail even on convex problems (Reddi et al., 2018). Conditional convergence through the affine output layer. Write 𝜃 = (𝜃 rest , 𝜃 out ), where 𝜃 out consists of the final affine classification weights and bias. With 𝜃 rest fixed, evaluation cross-entropy is convex in this block, which also satisfies Equation (99). This applies to both FedASTRA implementations and the optional deeper classifier, whose preceding layers belong to 𝜃 rest . Theorem 9 (Global task-risk convergence along actual updates). Use 𝐽 𝑁 , 𝐷 𝑢 , 𝐿 𝑢 from Proposition 9, ∗ = inf 𝑢 ∗ let 𝐽 𝑁 𝜃 ∈Θ 𝐽 𝑁 (𝜃) > −∞ and 𝐸 𝑢 = 𝐽 𝑁 (𝜃 ) − 𝐽 𝑁 . Fix 0 ≤ 𝑢 0 < 𝑇. For every 𝑢 = 𝑢 0 , . . . , 𝑇, assume a comparator with actual and comparison parameters in Θ satisfying 𝑢,◦ 𝑢 ∗ 𝐽 𝑁 (𝜃 rest , 𝜃 out ) ≤ 𝐽𝑁 + 𝑎 ctx ,

𝑢,◦ 𝑢 ∥𝜃 out − 𝜃 out ∥ 2 ≤ 𝐷 cls ,

(102)

with 𝑎 ctx ≥ 0 and 0 < 𝐷 cls < ∞. This assumption concerns affine-head adequacy on each realized representation, separately from full-model approximation over Θ. Define Δ𝑢 = ⟨∇𝐽 𝑁 (𝜃 𝑢 ), 𝐷 𝑢 ⟩ − 𝐿 𝑢 ∥𝐷 𝑢 ∥ 22 /2. Suppose 𝛾𝑢 > 0, 𝜁𝑢 ≥ 0 satisfy Δ𝑢 ≥ 𝛾𝑢 ∥∇ 𝜃out 𝐽 𝑁 (𝜃 𝑢 ) ∥ 22 − 𝜁𝑢 ,

𝑢 = 𝑢 0 , . . . , 𝑇 − 1.

(103)

Then, pathwise, 𝐸 𝑢+1 ≤ 𝐸 𝑢 −

𝛾𝑢 (𝐸 𝑢 − 𝑎 ctx )+2 + 𝜁𝑢 . 𝐷 2cls

(104)

If all deficits 𝜁𝑢 vanish, then " 𝐸𝑇 ≤ 𝑎 ctx + 𝑟 𝑢0 ,𝑇 ,

−2 𝑟 𝑢0 ,𝑇 := (𝐸 𝑢0 − 𝑎 ctx )+−1 + 𝐷 cls

𝑇 −1 ∑︁

# −1 𝛾𝑢

,

(105)

𝑢=𝑢0

with 𝑟 𝑢0 ,𝑇 = 0 if (𝐸 𝑢0 − 𝑎 ctx )+ = 0. In particular, 𝛾𝑢 ≥ 𝛾 > 0 gives 𝑟 𝑢0 ,𝑇 ≤ 𝐷 2cls /[𝛾(𝑇 − 𝑢 0 )]. For general deficits, v t Í −1 𝐸 𝑢0 + 𝑇𝑢=𝑢 𝜁 0 𝑢 min (𝐸 𝑢 − 𝑎 ctx )+ ≤ 𝐷 cls . (106) Í𝑇 −1 𝑢0 ≤𝑢<𝑇 𝑢=𝑢0 𝛾𝑢

33

Proof. Affine-head convexity and Equation (102) give 𝑢,◦ 𝑢 𝐸 𝑢 − 𝑎 ctx ≤ ⟨∇ 𝜃out 𝐽 𝑁 (𝜃 𝑢 ), 𝜃 out − 𝜃 out ⟩ ≤ 𝐷 cls ∥∇ 𝜃out 𝐽 𝑁 (𝜃 𝑢 ) ∥ 2 .

Combining with 𝐸 𝑢+1 ≤ 𝐸 𝑢 − Δ𝑢 proves the recurrence. For zero deficits, 𝐸 𝑢 is nonincreasing. Put 𝛿𝑢 = (𝐸 𝑢 − 𝑎 ctx )+ and 𝜅𝑢 = 𝛾𝑢 /𝐷 2cls . Whenever 𝛿𝑢+1 > 0, 𝛿𝑢+1 ≤ 𝛿𝑢 (1 − 𝜅𝑢 𝛿𝑢 ) with 𝜅 𝑢 𝛿𝑢 < 1, −1 ≥ 𝛿 −1 + 𝜅 . A zero 𝛿 stays zero. Summing proves the reciprocal rate. For arbitrary hence 𝛿𝑢+1 𝑢 𝑢 𝑢 −2 Í 𝛾 𝛿 2 ≤ 𝐸 + Í 𝜁 ; bounding the deficits, summing the recurrence and using 𝐸𝑇 ≥ 0 gives 𝐷 cls 𝑢0 𝑢 𝑢 𝑢 𝑢 𝑢 minimum by the weighted mean proves the last claim. □ The coefficients 𝛾𝑢 measure realized task progress and are not Adam learning rates. For any chosen 𝛾𝑢 > 0, the deficit 𝜁𝑢 = [𝛾𝑢 ∥∇ 𝜃out 𝐽 𝑁 (𝜃 𝑢 ) ∥ 22 − Δ𝑢 ] + makes the deficit bound applicable. The 𝑂 ((𝑇 − 𝑢 0 ) −1 ) conclusion additionally requires adequate realized contexts, zero deficits, and progress coefficients bounded away from zero. The architecture supplies affine-head convexity; it does not establish these trajectory conditions. No unbiased-gradient or full-network Polyak–Lojasiewicz condition is used. Corollary 9 (Global population convergence of the returned model). Assume Theorems 8 and 9, with 𝜁𝑢 = 0 on the stated interval. For the actual validation-selected b 𝜃 𝑁 ,𝑇 define 𝑠sel 𝑁 ,𝑇 = Í pop 𝑇 [𝐽 𝑁 ( b 𝜃 𝑁 ,𝑇 ) − 𝐽 𝑁 (𝜃 )] + , and put 𝐴 𝑁 = E[ 𝑘 𝑤 𝑘 (𝑑 𝑘 + 𝑎 𝑘 ) + 𝑎 share ] + 2𝑢 𝑁 . Then " # ∑︁ pop ∗ E R fed ( b 𝜃 𝑁 ,𝑇 ) − 𝑤 𝑘 R loc,𝑘 ≤ 𝐴 𝑁 + E[𝑎 ctx + 𝑟 𝑢0 ,𝑇 + 𝑠sel (107) 𝑁 ,𝑇 ]. 𝑘

Expectations include all path-dependent quantities. If 𝛾𝑢 ≥ 𝛾 > 0 and E𝐷 2cls is uniformly bounded, the reciprocal term is 𝑂 ((𝑇 − 𝑢 0 ) −1 ) in expectation. Vanishing 𝐴 𝑁 , E𝑎 ctx , E𝑟 𝑢0 ,𝑇 , and E𝑠sel 𝑁 ,𝑇 along a joint data-size and training-horizon limit give local-information Bayes consistency. ∗ ≤ 𝐸 + 𝑠 sel . Insert Equation (105) into Theorem 8; the stated Proof. By definition, 𝐽 𝑁 ( b 𝜃 𝑁 ,𝑇 ) − 𝐽 𝑁 𝑇 𝑁 ,𝑇 rate and limit follow. □

The selection term covers the implementation’s validation Accuracy/Macro-F1 rule. Nonzero alignment deficits retain only Equation (106)’s best-iterate guarantee, unless selection is controlled separately. These conditional rates do not follow from finite experiments or from the choice of Adam, EMA, and FedAvg alone. Predictive-surrogate mismatch. The same decomposition for one predictor class makes objective mismatch explicit. Corollary 10 (Conditional local Bayes consistency). Let 𝑑 𝑛 be from Theorem 7, and let Q 𝑁 be an available predictor class measurable from retained heat information, with population cross-entropy ∗ b𝑁 (𝑞) − 𝑅(𝑞) and approximation error 𝑎 𝑁 = inf 𝑞∈ Q 𝑁 𝑅(𝑞) − R heat,n ≥ 0. Suppose E sup𝑞∈ Q 𝑁 | 𝑅 𝑅(𝑞)| ≤ 𝑢 𝑁 and the returned 𝑞b𝑁 ,𝑇 ∈ Q 𝑁 satisfies b𝑁 (b b𝑁 (𝑞)] ≤ 𝜅 𝑁 + 𝑒 𝑁 ,𝑇 , E[ 𝑅 𝑞 𝑁 ,𝑇 ) − inf 𝑅 𝑞∈ Q 𝑁

(108)

where 𝜅 𝑁 , 𝑒 𝑁 ,𝑇 ≥ 0 bound surrogate/readout mismatch and optimization. Then ∗ E𝑅(b 𝑞 𝑁 ,𝑇 ) − R loc,n ≤ 𝑑 𝑛 + 𝑎 𝑁 + 2𝑢 𝑁 + 𝜅 𝑁 + 𝑒 𝑁 ,𝑇 .

(109)

Thus 𝜀 𝑛 , 𝑎 𝑁 , 𝑢 𝑁 , 𝜅 𝑁 , 𝑒 𝑁 ,𝑇 → 0 imply local Bayes consistency. Proof. Two uniform-deviation bounds yield E𝑅(b 𝑞 𝑁 ,𝑇 ) ≤ inf Q 𝑁 𝑅 + 2𝑢 𝑁 + 𝜅 𝑁 + 𝑒 𝑁 ,𝑇 ; substitute b𝑁 + 𝜆pred b 𝑎 𝑁 and Equation (90). For a fixed-teacher joint objective 𝐽 𝑁 = 𝑅 𝐿 pred,N , let 𝑞 index ◦ the complete model, including auxiliary heads. If a comparator 𝑞 𝑁 has CE gap at most 𝜅 CE 𝑁 and pred predictive-loss gap at most 𝜅 𝑁 , both relative to their infima over Q 𝑁 , an 𝑒 𝑁 ,𝑇 -optimal solution of pred 𝐽 𝑁 satisfies Equation (108) with 𝜅 𝑁 = 𝜅 CE 𝑁 +𝜆 pred 𝜅 𝑁 . This follows by subtracting the predictive-loss lower bound. It requires a fixed surrogate; moving-teacher updates do not automatically optimize that objective. □ 34

Information recovery controls 𝑑 𝑛 ; the finite representation/readout controls 𝑎 𝑁 ; the data law and training procedure must control 𝑢 𝑁 , 𝜅 𝑁 , 𝑒 𝑁 ,𝑇 . Under label sufficiency in Section 4, the local Bayes limit equals the enriched-information limit, and Equation (17) gives the criterion for beating a particular fitted enriched predictor.

D

E XPERIMENTAL P ROTOCOLS AND I MPLEMENTATION D ETAILS

D.1

F EDASTRA I MPLEMENTATION

Network and heat parameterization. The context encoder applies a linear map, layer normalization, and GELU to the raw attributes, followed by encoder dropout. Let its width be 𝑑. The training forward pass uses the type-marginalized binary incidence matrix from Equation (18). Relation types are not used as model inputs, and repeated relation instances remain separate columns. The standard experiments use 𝑅 = 4, while Trivago uses 𝑅 = 8. The time increments in Equation (20) are initialized at zero, giving initial diffusion times close to 𝑏 log 2, with 𝜖ord = 10−4 . The classifier receives (𝑅 + 1)𝑑 coordinates, applies layer normalization and dropout, and uses one linear readout. The predictive head maps (𝑅 + 1)𝑑 to 2𝑑, applies layer normalization and GELU, and maps back to (𝑅 + 1)𝑑. For each local update, two independent Bernoulli masks remove attribute coordinates. The removal probability is 0.40 on the established tasks and 0.30 on Trivago, with retained values divided by 0.60 and 0.70, respectively. Incidence indices, relation columns, and node membership remain fixed across both online views and the target view. At the start of each round, the EMA target context is initialized from the broadcast context encoder, including the attribute map and ordered-time increments. The target is updated after each local step with momentum 𝜇 = 0.99 on the standard experiments and 𝜇 = 0.996 on Trivago. It remains client-local and is discarded at the end of each round. Mask variance and target memory. Write the coordinate-removal probability as 𝑝 < 1 and let iid 𝛿 𝑗 ∼ Bernoulli(1 − 𝑝). The inverted mask M 𝑝 (𝑥) = 𝛿 ⊙ 𝑥/(1 − 𝑝) obeys exactly 𝑝 E 𝛿 M 𝑝 (𝑥) = 𝑥, E 𝛿 ∥M 𝑝 (𝑥) − 𝑥∥ 22 = ∥𝑥∥ 22 . (110) 1− 𝑝 Thus, the masking variance is determined directly by 𝑝. Within one client round, write 𝜗𝑠 = ctx(𝜃 𝑠 ) and 𝜗¯𝑠 for the online and target context states after local step 𝑠, with the round reset 𝜗¯0 = 𝜗0 . The update 𝜗¯𝑠 = 𝜇 𝜗¯𝑠−1 + (1 − 𝜇)𝜗𝑠 expands over the complete local context history as 𝜗¯𝑠 = 𝜇 𝑠 𝜗0 + (1 − 𝜇)

𝑠 ∑︁

𝜇 𝑠− 𝑗 𝜗 𝑗 .

(111)

𝑗=1

The EMA therefore weights earlier context states geometrically by 𝜇 𝑠− 𝑗 . The corresponding memory scale is approximately (1 − 𝜇) −1 local steps. Both masking and EMA updates are client-local. For every fixed 𝑝 < 1 and 𝜇 ∈ [0, 1), coupling their randomness preserves the complete observation invariance in Corollary 4. In the masked-prediction ablation, 𝑝 and 𝜇 are held fixed across paired conditions so that only the predictive component changes. Exact local objective. Each local update encodes two masked views online. At client 𝑘, let 𝜗𝑘 = ctx(𝜃 𝑘 ) and let 𝜗¯ 𝑘 = ( 𝜃¯𝑘,enc , 𝜂¯ 𝑘 ) denote the round-local EMA copy of the complete context encoder, including its learned time increments. The target branch forms 𝑍 𝑘tar = 𝑊 𝑘 (𝑋 𝑘 | 𝜗¯ 𝑘 ), and b(𝑎) = 𝑝 𝜃𝑘 (𝑊 𝑘 ( 𝑋 e(𝑎) | 𝜗𝑘 )) with 𝑎 ∈ {1, 2}. Here each masked online view produces a prediction 𝑍 𝑘 𝑘 (𝑅+1) 𝑑 (𝑅+1) 𝑑 the row-wise predictor is 𝑝 𝜃𝑘 : R → R and the row-wise classifier for 𝐶 classes is 𝑐 𝜃𝑘 : R (𝑅+1) 𝑑 → R𝐶 . Let 𝑛 𝑘 = |𝑉𝑘 | and we use LN for row-wise layer normalization, sg for stop Í tar b(𝑎) gradient, and cos for cosine similarity. Set A 𝑘(𝑎) = 𝑛 −1 𝑣∈𝑉𝑘 [1 − cos(LN( 𝑍 𝑘,𝑣 ), sg(LN(𝑍 𝑘,𝑣 )))]. 𝑘 With an anti-collapse regularizer R ac inspired by variance–invariance–covariance regularization (VICReg), and a fixed view-agreement weight 𝛾view ≥ 0, we define " # 2 ∑︁ 1 ∑︁ (𝑎) 1 (𝑎) (1) (2) b ))] + 𝛾view 1 − b ,𝑍 b ) . Lpred,𝑘 = [A + R ac (LN( 𝑍 cos( 𝑍 (112) 𝑘 𝑘,𝑣 𝑘,𝑣 2 𝑎=1 𝑘 𝑛 𝑘 𝑣∈𝑉 𝑘

35

Í𝑛 Í𝑛 For 𝐴 ∈ R𝑛×ℎ , define 𝐴 𝑗 = 𝑛 −1 𝑖=1 ( 𝐴𝑖 𝑗 − 𝐴 𝑗 ) 2 /max(𝑛 − 1, 1). Thus the 𝐴𝑖 𝑗 and Var𝑛 ( 𝐴 · 𝑗 ) = 𝑖=1 implementation uses sample variance for 𝑛 > 1 and the zero variance for 𝑛 = 1. Define  ℎ  √︃ 1 ∑︁ 1 − Var𝑛 ( 𝐴 · 𝑗 ) + 10−4 , (113) V ( 𝐴) = ℎ 𝑗=1 + ! 2 e⊤ 𝐴 e 𝐴· 𝑗 − 𝐴 𝑗 1 𝐴 e· 𝑗 = √︁ , 𝐴 C( 𝐴) = offdiag . (114) ℎ max(𝑛 − 1, 1) Var𝑛 ( 𝐴 · 𝑗 ) + 10−4 𝐹 The anti-collapse term in Equation (112) is R ac ( 𝐴) = 0.10V ( 𝐴) + 0.005C( 𝐴) and receives 𝐴 = b(𝑎) ), the rowwise layer-normalized predictor matrix defined before Equation (112). The LN( 𝑍 𝑘 term A 𝑘(𝑎) averages the nodewise target-alignment cosine losses. The view-agreement weight is 𝛾view = 0.10. The fixed predictive coefficient is 𝜆pred = 1. Supervised cross-entropy is evaluated only on the training mask. Prediction uses all client-local nodes, attributes, and incidence. The validation-selected checkpoint uses Accuracy with Macro-F1 tie-breaking and is tested once. Shared matrix powers across diffusion times. The required powers of 𝑃 𝑘 applied to 𝑈 𝑘 are computed recursively and shared across all diffusion times, with time-specific Poisson coefficients. Let 𝐿 tail be the recurrence degree chosen by Equation (59), let E 𝑘rel be the retained relation columns, and let Ω 𝑘 = {(𝑣, 𝑒) : 𝐵 𝑘,𝑣𝑒 = 1} be the client incidence list. One application of 𝑃 𝑘 costs 𝑂 (|Ω 𝑘 |𝑑) time and 𝑂 ((|𝑉𝑘 | + |E 𝑘rel |)𝑑) working storage. The complete basis computation therefore has the following time and storage complexity:   𝑂 (𝐿 tail |Ω 𝑘 |𝑑 + 𝐿 tail 𝑅|𝑉𝑘 |𝑑) time, 𝑂 (𝑅 + 1)|𝑉𝑘 |𝑑 + |E 𝑘rel |𝑑 + |Ω 𝑘 | storage. (115) Increasing 𝑅 adds coefficient accumulation and representation width, but does not require additional incidence traversals for each channel. The current maximum learned time and fixed tolerance determine the degree 𝐿 tail . Although the target heat operator has infinite Poisson support, Equation (58) evaluates it at finite degree with certified forward and time-gradient errors. Table 5 reports the recurrence degree, numerical error, and local evaluation cost under the finitetask implementation. The evaluated client has 445 nodes, 485 anonymous relation columns, 774 incidences, and 64 feature channels. Each CPU median is computed over five timing runs. Across all settings, the maximum absolute residual is 2.38 × 10−7 . The results show that the heat-basis computation meets the prescribed error tolerance, while maintaining small numerical residuals and moderate local computation cost. Table 5: Heat-basis evaluation on one CoraCA client at 𝐾 = 6. 𝐿 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. 𝑅

𝐿tail

Forward tail

Time-gradient tail

Relative ℓ2 residual

CPU median (ms)

2 4 6 8

11 15 18 21

2.95×10 −8 4.35×10 −8 9.34×10 −8 1.06×10 −7

2.87×10 −7 2.98×10 −7 5.26×10 −7 5.34×10 −7

3.07×10 −8 2.26×10 −8 1.48×10 −8 2.20×10 −8

26.30 33.72 33.27 42.99

Communication protocol and privacy boundary. Table 6 summarizes the information available to the server and the state retained locally. Under this protocol, FedASTRA communicates only the online model parameters, while auxiliary training states remain client-local. FedAvg aggregates client updates with weights proportional to their fixed labeled-training counts 𝑛tr𝑘 . The local EMA target is reset at each round, while learned node states, incidence data, and numerical heat buffers remain client-local. This communication protocol does not by itself provide end-to-end differential privacy. Model updates may still reveal information about attributes or labels, and secure aggregation alone does not eliminate the risk of aggregate inversion attacks (Shi et al., 2025). Record-level privacy would require an explicit threat model together with additional mechanisms such as calibrated randomization, privacy accounting, and compatible secure aggregation.

36

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

Declared scope

Server receives Server broadcasts Fixed aggregation metadata client-local state

Online model parameters from each participating client. The aggregated online model parameters. Each client’s labeled-training count, fixed before training. 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. Zero bytes. No embeddings, relation summaries, or target parameters are transmitted. Direct cross-client node, edge, and source-hyperedge identifiers are absent. Secure aggregation and differential privacy require their own mechanism, parameters, and accountant.

Auxiliary learned-state payload Structural access claim Privacy extension

D.2

G RAPH PARTITIONS AND L IFTS

Main graph partition. For the main experiments, following (Yao et al., 2023; Luo et al., 2025), we fix the task split before client assignment and partition nodes across 𝐾 ∈ {3, 6, 9} clients using class-conditioned Dirichlet sampling. Client allocation probabilities are drawn from a symmetric Dirichlet distribution with concentration 104 , subject to the declared load cap and minimum client size. The resulting assignment is precomputed from the full class labels, fixed before model training, and shared by all compared methods. For graph datasets, this node partition is also fixed before constructing client-local one-hop relations from the induced subgraphs. Truncation-controlled graph partition. We construct low-, reference-, and high-truncation partitions while preserving each client’s load and label histogram. Each paired comparison begins from one balanced label allocation and permits swaps between nodes of the same class. Every proposal therefore Í preserves each client’s load and label histogram. With nonnegative fixed weights 𝛼2 , 𝛼3 and 𝜌 𝑘 = 𝑛 𝑘 / 𝑗 𝑛 𝑗 , the three objectives are ∑︁ 𝐽low (𝑧) = 𝛼𝑞 𝜏𝑞 (𝑧), 𝑞 ∈ {2,3}

# !2

" ∑︁

𝐽ref (𝑧) =

𝛼𝑞 𝜏𝑞 (𝑧) − 1 −

𝑞 ∈ {2,3}

𝐽high (𝑧) = −

∑︁

∑︁

𝜌 𝑞𝑘

,

s.t.

|𝑉𝑘 | = 𝑛 𝑘 ,

hist(𝑌𝑉𝑘 ) = ℎ 𝑘 .

(116)

𝑘

𝛼𝑞 𝜏𝑞 (𝑧),

𝑞 ∈ {2,3}

Í Here, 1 − 𝑘 𝜌 𝑞𝑘 is the expected order-𝑞 truncation level under independent allocation with client proportions 𝜌 𝑘 . We minimize the corresponding objective for the low-truncation, independentallocation reference, and high-truncation partitions. Each pass proposes 2,048 same-class cross-client swaps, accepts strict improvements, and stops after at most 16 passes or after a pass accepts zero swaps. The three partitions thus have identical client loads and client-by-label histograms while their truncation coordinates differ. Hyperedges are treated as sets, relation multiplicity and type are retained, and every objective is invariant to stored member order. We assign equal weight to the pair and triple coordinates, 𝛼2 = 𝛼3 = 1. Graph lifting. For graph datasets, we adopt a partition-then-lift protocol. Each client first receives the induced subgraph 𝐺 [𝑉𝑘 ], from which one-hop relations are constructed without remote endpoints or cross-client edges. The following proposition clarifies its relation to the alternative lift-thenpartition construction. Proposition 10 (Lift-then-partition and partition-then-lift protocols). Let the rooted global one-hop relation be 𝑒 𝑣 = {𝑣} ∪ 𝑁𝐺 (𝑣). For a local root 𝑣 ∈ 𝑉𝑘 , the two graph-lift protocols obey the exact identity below for every client and every locally assigned root under one-hop lifting: 𝑒 𝑣 ∩ 𝑉𝑘 = {𝑣} ∪ 𝑁𝐺 [𝑉𝑘 ] (𝑣).

(117)

Thus a local-root one-hop fragment has the same members under both constructions. Lift-thenpartition additionally creates fragments on client 𝑘 for roots 𝑣 ∉ 𝑉𝑘 . Partition-then-lift contains locally rooted columns. For multi-hop relations, even a local root can differ because a path may leave 𝑉𝑘 and return. This identity locates the extra globally constructed information in lift-then-partition and isolates globally supplied fragments from edges removed by the induced client graph. 37

Table 7: Statistics of the datasets used in the experiments. #Nodes #Graph edges #Hyperedges #Incidences #Classes #Features

D.3

CoraCA

DBLP4k

IMDB4k

Trivago

Cora

CiteSeer

Facebook

ogbn-papers100M

2,708 – 1,072 4,585 7 1,433

4,057 – 22,051 110,330 4 334

4,278 – 7,338 17,106 3 3,066

172,738 – 233,202 726,861 160 300

2,708 5,278 2,708 13,264 7 1,433

3,327 4,552 3,327 12,431 6 3,703

22,470 85,424 22,470 193,318 4 4,714

111,059,956 1,614,062,356 111,059,956 3,339,184,668 172 128

DATASET D ETAILS

We use two types of datasets for evaluation, including native hypergraph datasets and graph datasets. For graph datasets, #Graph edges counts distinct non-self undirected edges used for the one-hop lift, with duplicate and reciprocal entries counted once. Table 7 summarizes the statistics of the datasets used in the experiments. Native hypergraph datasets. CoraCA, DBLP4k, and IMDB4k are loaded from the public dataset release accompanying HGNN and HGNN+ (Feng et al., 2019; Gao et al., 2023). CoraCA uses coauthorship relations (Yadati et al., 2019). DBLP4k retains paper and term relations, and IMDB4k retains director and actor relations as separate channels (Sun et al., 2011; Fu et al., 2020). Trivago follows the public DHG-Bench release (Li et al., 2026), where browsing sessions define hyperedges. Distinct source relation instances are retained even when they contain the same set of nodes. FedASTRA combines all released incidence columns in one observable operator. Relation types are used only to define analysis strata and are not provided as categorical embeddings to the model. Graph datasets. The graph-derived experiments use the Cora and CiteSeer paper citation networks (Yang et al., 2016), the Facebook page mutual-like network (Rozemberczki et al., 2021), and the large-scale ogbn-papers100M paper citation network (Hu et al., 2020). Following the partition-thenlift protocol in Appendix D.2, nodes are first assigned to clients and each local root 𝑣 ∈ 𝑉𝑘 then defines the closed one-hop relation {𝑣} ∪ (𝑁𝐺 (𝑣) ∩ 𝑉𝑘 ). Thus, every retained incidence is visible to its assigned client through the common released hyperedge. The ogbn-papers100M experiment follows its official implementation and processes all nodes and citations without sampling. D.4

E XPERIMENTAL C ONFIGURATIONS

Training and evaluation protocols. Within each comparison, we use the same data splits, released inputs, communication rounds, local updates, and validation-selection rule. Following (Luo et al., 2025), training fractions are 0.10, 0.06, and 0.06 for CoraCA, DBLP4k, and IMDB4k, respectively, with validation and test fractions of 0.20 and 0.40. The remaining unlabeled nodes retain their structural roles and, together with labeled nodes, provide attributes and released local structure to the transductive encoders. Trivago uses a per-class stratified 0.50/0.25/0.25 train/validation/test split that assigns every node once following DHG-Bench (Li et al., 2026). For graph datasets, Cora and CiteSeer use the 0.10/0.20/0.40 ratios, while Facebook uses 0.008/0.20/0.40, following (Luo et al., 2025). For all datasets except ogbn-papers100M, the splits are stratified by class and fixed before client assignment. Ogbn-papers100M uses its official temporal split Hu et al. (2020). Training labels are used for model fitting, validation performance is used for checkpoint selection, and the selected model is evaluated once on the test set. The standard experiments use 150 communication rounds with three local updates per round, while Trivago uses 30 rounds. Results use five repetitions, except for Fed-HNHN and Trivago experiments, which use three. The ogbn-papers100M scale experiment uses 20 communication rounds with one local epoch per round and is reported from a single full-data run. Node classification is evaluated using Accuracy and Macro-F1. Macro-F1 averages the per-class F1 scores over the full label set, assigning zero to any class absent from the test split. The evaluator also computes 𝜏2 and 𝜏3 from the source hypergraph and the fixed experimental partition. These quantities measure pair- and triple-order truncation and are used only for evaluation, not for model fitting, checkpoint selection, or inference. For summaries over 𝐾 ∈ {3, 6, 9}, we first average the

38

results across the three client counts within each repetition, and then report the mean and sample standard deviation across repetitions. Baseline configurations. For the native-hypergraph comparison, all baselines use the same clientlocal attributes and anonymous incidence columns as FedASTRA, with independently indexed columns across clients. Only trainable model parameters are communicated. We report baseline results only when the dataset, task split, client assignment, observed structure, communication rounds, local updates, and evaluation protocol match those of FedASTRA. Fed-HNHN follows the FedHGL implementation with bias-free linear maps, mean aggregation, and hidden BatchNorm (Luo et al., 2025). Its BatchNorm running statistics remain client-local and are not included in FedAvg. For the graph comparison, all methods use the same split, client assignment, communication rounds, local updates, and evaluation protocol. FedSage, FedGCN (0-hop), and FedASTRA use only clientlocal structure. FedSage+ exchanges generated boundary features and reconstruction gradients without direct cross-client identifiers (Zhang et al., 2021). FedGCN (2-hop) relies on cross-client neighborhood information, using pre-aggregated neighbor features in the original protocol (Yao et al., 2023), while FedCog additionally exchanges intermediate representations through known cross-client node and edge correspondences (Lei et al., 2023). These different information-access settings are retained when interpreting the predictive results. For the FedASTRA configuration, Table 8 summarizes the settings used in the standard experiments and on Trivago. The order 𝑞 is used only for the identification analysis and is not a model hyperparameter. The corresponding evaluator queries do not affect model training or checkpoint selection. Table 8: Configurations of FedASTRA in the standard experiments and on Trivago. Standard experiments

Trivago

Hyperedge input Type-marginalized binary incidence, unit weights Online model Hidden dimension 64, dropout 0.35 Optimization Adam, learning rate 10 −2 , weight decay 5 × 10 −4 , gradient clip 5.0 Heat basis 𝑅 = 4, increment floor 10−4 , tail tolerance 10−6 Predictive path Two masks with probability 0.40, 𝜆pred = 1, EMA decay 0.99

Type-marginalized binary incidence, unit weights Hidden dimension 128, dropout 0.20 Adam, learning rate 3×10 −3 , weight decay 5×10 −4 , gradient clip 5.0 𝑅 = 8, increment floor 10−4 , tail tolerance 10−6 Two masks with probability 0.30, 𝜆pred = 1, EMA decay 0.996

Ablation settings. For the adaptive diffusion ablation, we evaluate 𝑅 ∈ {0, 1, 2, 4, 8} with 𝜆pred = 1 on CoraCA, DBLP4k, and Trivago at 𝐾 = 6. The 𝑅 = 0 control retains the feature encoder, classifier, masked predictor, and EMA target but removes diffusion. Three paired repetitions use the same node splits, client assignments, and training seeds across all five settings, giving 45 fitted models in total. Because increasing 𝑅 also increases the representation dimension and model size, we report the corresponding parameter count for each setting. The parameter count includes the feature encoder, learned time increments, classifier, and predictive head, while excluding the client-local EMA target. Let 𝑑 𝑥 be input-feature dimension, 𝑑 the hidden dimension, and 𝐶 the number of classes. For the single-layer linear classifier in our implementation, the number of online parameters is 𝑁 𝑅 = 𝑑 𝑥 𝑑 + 4𝑑 2 + (𝐶 + 12)𝑑 + 𝐶 + 𝑅𝑑 (4𝑑 + 𝐶 + 4). (118) The feature encoder contributes 𝑑 𝑥 𝑑 + 3𝑑, the time increments 𝑅𝑑, the classifier (𝑅 + 1)𝑑 (𝐶 + 2) + 𝐶, and the predictive head 4(𝑅 + 1)𝑑 2 + (𝑅 + 1)𝑑 + 6𝑑. This accounting provides the model-size context for the adaptive diffusion ablation. For the masked prediction ablation, we evaluate 𝑅 ∈ {1, 4} and 𝜆 pred ∈ {0, 1} on CoraCA and DBLP4k at 𝐾 = 6. To measure the computation cost of the adaptive diffusion ablation, each dataset is run on one NVIDIA RTX A6000 GPU, with repetitions and 𝑅 settings executed sequentially. Elapsed time is measured with CUDA synchronization and includes model initialization, all training rounds, validation-based checkpoint selection, checkpoint restoration, and final post-training measurements, while excluding dataset loading, split construction, and the final test evaluation. Figure 3 and Table 17 report predictive performance, parameter counts, and elapsed training time under this common measurement protocol. Communication accounting. Let 𝑏 𝜃 denote the size in bytes of the online model parameters and 𝐾𝑢 = |C𝑢 | be the number of participating clients in round 𝑢. FedASTRA transmits one model 39

download and one model upload per participating client, giving 𝑏 round,𝑢 = 𝐾𝑢 𝑏 𝜃 + 𝐾𝑢 𝑏 𝜃 = 2𝐾𝑢 𝑏 𝜃 ,

𝑏 auxiliary = 0.

(119)

Model communication is reported as the logical payload of these uploads and downloads. Serialization, encryption, packet headers, retransmission, and other transport overheads are excluded for all methods. For the federated graph baselines, auxiliary communication accounts for additional method-specific information required by the corresponding implementation, including generated features and reconstruction gradients for FedSage+, two-hop neighborhood information for FedGCN (2-hop), and routed intermediate representations for FedCog. Model communication is reported per round, while auxiliary communication is accumulated over the full run. Full-data ogbn-papers100M protocol without sampling. To support full-data training at this scale, ogbn-papers100M is processed with streaming minibatches. Each round traverses every training root once, and a 200,000-incidence budget controls batch size without truncating any rooted relation. Each minibatch performs one optimizer step. For FedASTRA, AdamW (Loshchilov & Hutter, 2019) uses a learning rate of 2 × 10−3 , weight decay 10−4 , dropout 0.2, and gradient-norm clipping at 2.0. The model uses hidden dimension 197, 𝑅 = 4, mask probability 0.40, 𝜆pred = 1, and EMA decay 0.99. The hidden dimension is selected to match the approximately one-million-parameter baseline budget. It gives 976,504 trainable parameters, while dimension 198 would give 985,420 and exceed the 984,442-parameter ceiling. In the minibatch implementation, each rooted example is represented independently. If a paper appears in multiple rooted relations, a separate copy is created for each relation, preventing message passing between different prediction examples. Each copied node therefore belongs to exactly one relation column, and different relation columns have disjoint support. This gives 𝐷 𝑣 = 𝐼 and 𝐵⊤ 𝐵 = 𝐷 𝑒 , so the occurrence-space operator 𝑃occ = 𝐵𝐷 𝑒−1 𝐵⊤ is an orthogonal projection: 2 𝑃occ = 𝐵𝐷 𝑒−1 (𝐵⊤ 𝐵)𝐷 𝑒−1 𝐵⊤ = 𝑃occ .

(120)

The heat kernel can therefore be evaluated exactly for every minibatch as Kocc (𝑡) = 𝑒 −𝑡 𝐼 + (1 − 𝑒 −𝑡 )𝑃occ .

(121)

Corollary 11 (Exact spectral form in the occurrence protocol). For every scalar multiplier 𝑓 on spec(𝑃occ ) ⊆ {0, 1}, 𝑓 (𝑃occ ) = 𝑓 (0)𝐼 + [ 𝑓 (1) − 𝑓 (0)]𝑃occ . (122) Consequently, for any 𝑡 > 0, span{𝐼, Kocc (𝑡)} = span{𝐼, 𝑃occ }. Therefore, the identity channel and any one positive-time heat channel span the space of all linear spectral filters of 𝑃occ . The corollary follows from the spectral projectors 𝐼 − 𝑃occ and 𝑃occ , together with 1 − 𝑒 −𝑡 > 0. Additional learned times provide separately parameterized feature channels before nonlinear normalization and prediction, although they do not enlarge the linear spectral space of 𝑃occ . The closed form in Equation (121) relies on the disjoint-copy minibatch construction. If node copies are shared across rooted relations, the resulting operator need not satisfy 𝑃2 = 𝑃. The general client-local transition in Equation (18) need not satisfy 𝑃2𝑘 = 𝑃 𝑘 and is therefore evaluated using the recurrence 2 −𝑃 in Appendix C.8. In float32, the scale implementation gives max |𝑃occ occ | = 0 and a maximum absolute difference of 1.91 × 10−6 between Equation (121) and a direct matrix exponential.

E

A DDITIONAL E XPERIMENTAL R ESULTS

This section provides additional experimental results by reporting extended performance evaluations, controlled analyses of the proposed mechanisms, and detailed scalability measurements under the corresponding experimental protocols. E.1

P ERFORMANCE ON NATIVE H YPERGRAPHS

Table 9 reports the complete native-hypergraph results for each client count 𝐾 ∈ {3, 6, 9}. On CoraCA, the performance gap between FedASTRA and Fed-HGNN increases as the number of clients grows from 3 to 9, from 4.83% to 7.75% accuracy and from 6.54% to 9.84% Macro-F1. 40

This trend is consistent with the increasing fragmentation of local observations under matched client inputs. Table 9: Complete native-hypergraph results under different number of clients. Method Acc. (%)

E.2

𝐾 =3 Macro-F1 (%)

Acc. (%)

𝐾 =6 Macro-F1 (%)

Acc. (%)

𝐾 =9 Macro-F1 (%)

CoraCA FedASTRA Fed-HGNN Fed-HNHN Fed-HyperGCN Fed-AllDeepSets Fed-AllSetTransformer Fed-UniGCNII Fed-ED-HNN

76.27 ± 0.54 71.44 ± 1.90 57.30 ± 0.82 67.38 ± 1.01 45.90 ± 3.43 30.22 ± 0.00 63.57 ± 1.89 61.90 ± 1.51

74.33 ± 0.72 67.79 ± 2.12 54.40 ± 1.21 63.08 ± 1.64 37.62 ± 4.62 6.63 ± 0.00 56.52 ± 5.53 57.27 ± 1.53

74.97 ± 0.63 67.97 ± 1.38 54.16 ± 2.46 63.84 ± 2.16 36.54 ± 2.11 30.22 ± 0.00 58.89 ± 1.52 59.28 ± 2.38

72.79 ± 0.93 63.57 ± 1.50 49.08 ± 3.29 57.65 ± 2.56 24.37 ± 2.86 6.63 ± 0.00 49.01 ± 3.67 52.11 ± 3.62

74.27 ± 0.73 66.52 ± 2.32 52.74 ± 1.13 60.85 ± 2.56 36.45 ± 1.45 30.22 ± 0.00 56.16 ± 2.07 57.69 ± 2.22

71.52 ± 0.97 61.68 ± 3.02 47.77 ± 2.57 53.47 ± 3.07 19.26 ± 6.62 6.63 ± 0.00 44.80 ± 3.52 50.46 ± 3.45

DBLP4k FedASTRA Fed-HGNN Fed-HNHN Fed-HyperGCN Fed-AllDeepSets Fed-AllSetTransformer Fed-UniGCNII Fed-ED-HNN

78.52 ± 1.26 77.62 ± 1.48 72.23 ± 2.64 74.74 ± 1.29 39.25 ± 0.68 30.87 ± 0.97 79.03 ± 2.12 71.92 ± 3.52

77.84 ± 1.04 76.98 ± 1.39 71.44 ± 2.66 73.43 ± 1.63 31.74 ± 1.79 22.50 ± 2.61 77.85 ± 2.47 71.19 ± 3.46

79.75 ± 0.82 77.73 ± 1.62 68.43 ± 2.55 72.29 ± 0.60 39.36 ± 0.72 30.82 ± 1.20 77.60 ± 2.49 72.30 ± 2.30

79.15 ± 0.75 77.00 ± 1.37 67.70 ± 2.67 70.88 ± 0.90 31.96 ± 2.36 21.30 ± 1.64 76.18 ± 2.98 71.59 ± 2.40

79.40 ± 1.35 77.55 ± 1.30 68.08 ± 1.23 71.04 ± 1.85 39.45 ± 1.18 31.28 ± 1.73 75.44 ± 3.10 72.09 ± 2.36

78.84 ± 1.24 76.96 ± 1.16 67.22 ± 0.97 70.06 ± 1.80 33.63 ± 1.75 21.62 ± 1.93 73.92 ± 3.27 71.30 ± 2.37

IMDB4k FedASTRA Fed-HGNN Fed-HNHN Fed-HyperGCN Fed-AllDeepSets Fed-AllSetTransformer Fed-UniGCNII Fed-ED-HNN

51.99 ± 1.85 50.14 ± 1.38 46.14 ± 0.62 47.36 ± 1.87 45.82 ± 1.87 37.04 ± 0.03 51.12 ± 2.34 48.93 ± 1.98

51.92 ± 1.53 50.10 ± 1.39 44.75 ± 0.57 46.33 ± 2.22 43.96 ± 4.83 18.04 ± 0.05 49.88 ± 3.45 48.61 ± 2.06

51.05 ± 1.53 48.36 ± 1.47 43.81 ± 2.13 43.26 ± 1.50 37.73 ± 1.67 37.06 ± 0.05 37.09 ± 0.87 40.75 ± 0.94

50.88 ± 1.34 48.25 ± 1.46 41.84 ± 2.95 41.35 ± 2.30 30.24 ± 1.83 18.06 ± 0.10 21.95 ± 5.33 30.57 ± 1.29

50.34 ± 0.92 48.05 ± 1.49 44.92 ± 1.93 41.81 ± 1.64 37.42 ± 1.35 37.03 ± 0.11 36.66 ± 0.87 40.71 ± 0.93

50.37 ± 0.85 47.41 ± 2.11 42.54 ± 1.81 34.90 ± 5.71 28.15 ± 3.67 18.21 ± 0.22 19.87 ± 3.96 30.58 ± 1.22

Trivago FedASTRA Fed-HGNN Fed-HNHN Fed-HyperGCN Fed-AllDeepSets Fed-AllSetTransformer Fed-UniGCNII Fed-ED-HNN

33.55 ± 1.60 22.99 ± 0.72 29.10 ± 1.36 9.40 ± 0.65 11.37 ± 0.11 8.99 ± 0.00 9.25 ± 0.23 9.54 ± 0.86

9.64 ± 0.35 5.00 ± 0.71 9.19 ± 0.19 0.15 ± 0.06 0.30 ± 0.01 0.10 ± 0.00 0.16 ± 0.05 0.16 ± 0.09

27.70 ± 1.14 22.08 ± 0.77 24.87 ± 1.06 9.00 ± 0.02 10.82 ± 0.15 8.99 ± 0.00 9.14 ± 0.09 9.05 ± 0.06

7.55 ± 0.32 4.05 ± 0.59 7.37 ± 0.35 0.11 ± 0.01 0.28 ± 0.03 0.10 ± 0.00 0.16 ± 0.01 0.13 ± 0.03

26.01 ± 1.29 20.48 ± 0.87 23.08 ± 0.70 9.10 ± 0.21 10.45 ± 0.22 8.99 ± 0.00 9.07 ± 0.10 8.99 ± 0.01

6.70 ± 0.15 3.75 ± 0.67 6.59 ± 0.24 0.13 ± 0.04 0.24 ± 0.01 0.10 ± 0.00 0.13 ± 0.03 0.10 ± 0.00

P ERFORMANCE AGAINST BASELINES WITH VARYING I NFORMATION ACCESS

Table 10 reports comparisons against federated graph learning baselines under different cross-client information-access settings, while Table 11 summarizes methods according to their available structural information and communication requirements. FedASTRA consistently outperforms identifier-free baselines across client counts and also surpasses FedSage+ despite the latter introducing additional exchanged information. In contrast, FedGCN (2-hop) and FedCog access explicit cross-client correspondence and therefore exploit a strictly richer observation setting. These results suggest that additional cross-client information is not universally beneficial: its value depends on whether the introduced information can be reliably exploited under the correspondence assumptions.

41

Table 10: Complete results under different cross-client information-access settings. Method Acc. (%)

𝐾 =3 Macro-F1 (%)

Acc. (%)

𝐾 =6 Macro-F1 (%)

Acc. (%)

𝐾 =9 Macro-F1 (%)

Cora FedSage FedGCN (0-hop) FedSage+ FedGCN (2-hop) FedCog FedASTRA

70.35 ± 1.96 74.07 ± 1.57 69.67 ± 0.71 84.05 ± 1.17 84.29 ± 1.50 77.54 ± 1.08

67.77 ± 1.67 71.24 ± 1.86 66.87 ± 0.30 83.01 ± 1.23 83.15 ± 1.64 76.06 ± 1.31

63.18 ± 0.97 65.90 ± 2.05 63.11 ± 1.66 84.05 ± 1.16 84.34 ± 1.06 74.45 ± 1.60

58.59 ± 0.87 61.96 ± 3.34 57.78 ± 1.63 83.12 ± 1.20 83.35 ± 1.00 72.13 ± 1.81

58.65 ± 1.85 62.07 ± 1.79 61.02 ± 1.40 84.12 ± 0.92 83.92 ± 0.78 73.33 ± 1.22

52.17 ± 2.81 57.44 ± 2.91 55.05 ± 3.65 82.92 ± 0.78 82.73 ± 0.66 71.83 ± 1.31

CiteSeer FedSage FedGCN (0-hop) FedSage+ FedGCN (2-hop) FedCog FedASTRA

65.08 ± 0.96 68.68 ± 1.50 63.16 ± 1.17 72.20 ± 1.44 72.21 ± 1.49 67.61 ± 2.32

59.56 ± 1.42 61.60 ± 1.32 57.75 ± 1.59 65.64 ± 2.26 65.84 ± 1.77 63.62 ± 1.61

63.73 ± 0.74 65.83 ± 0.56 62.53 ± 1.66 72.27 ± 1.53 72.38 ± 1.04 68.00 ± 1.86

57.00 ± 1.51 59.06 ± 0.52 56.48 ± 2.61 64.88 ± 1.44 65.09 ± 1.03 63.67 ± 2.07

62.93 ± 1.72 65.14 ± 1.80 62.95 ± 1.62 72.38 ± 1.50 72.51 ± 1.42 67.92 ± 1.88

55.67 ± 1.25 58.10 ± 1.68 57.69 ± 2.10 64.85 ± 2.07 65.11 ± 1.94 63.65 ± 2.13

Facebook FedSage FedGCN (0-hop) FedSage+ FedGCN (2-hop) FedCog FedASTRA

72.63 ± 0.73 75.14 ± 0.95 68.17 ± 0.33 83.21 ± 0.76 82.46 ± 0.69 76.88 ± 1.44

69.00 ± 1.08 72.62 ± 0.74 65.41 ± 0.64 82.02 ± 0.87 81.24 ± 0.73 75.58 ± 1.60

65.64 ± 1.81 67.87 ± 1.71 61.85 ± 0.95 82.84 ± 0.50 82.50 ± 0.84 75.57 ± 0.94

61.85 ± 2.39 64.39 ± 2.24 57.62 ± 1.32 81.58 ± 0.67 81.20 ± 1.09 73.71 ± 0.86

60.41 ± 1.61 64.30 ± 1.22 58.56 ± 1.33 82.73 ± 0.85 82.15 ± 0.94 75.12 ± 1.49

53.46 ± 4.16 59.44 ± 2.83 54.02 ± 1.99 81.51 ± 1.04 80.85 ± 1.13 73.30 ± 1.76

Table 11: Summarized results of federated graph baselines under different cross-client informationaccess settings. Results are aggregated across client counts 𝐾 ∈ {3, 6, 9}. Method

Exchanged or accessed information

Cora FedASTRA

Model parameters only, with no direct cross-client identifiers FedSage+ Locally generated boundary features and cross-client reconstruction gradients, with no direct identifiers FedGCN (2-hop) Cross-client node IDs, edges, and pre-aggregated neighbor features FedCog Cross-client node IDs, edges, and intermediate embeddings CiteSeer FedASTRA Model parameters only, with no direct cross-client identifiers FedSage+ Locally generated boundary features and cross-client reconstruction gradients, with no direct identifiers FedGCN (2-hop) Cross-client node IDs, edges, and pre-aggregated neighbor features FedCog Cross-client node IDs, edges, and intermediate embeddings Facebook FedASTRA Model parameters only, with no direct cross-client identifiers FedSage+ Locally generated boundary features and cross-client reconstruction gradients, with no direct identifiers FedGCN (2-hop) Cross-client node IDs, edges, and pre-aggregated neighbor features FedCog Cross-client node IDs, edges, and intermediate embeddings

E.3

Accuracy (%) Macro-F1 (%) 75.11 ± 0.99

73.34 ± 1.13

64.60 ± 1.11

59.90 ± 1.71

84.07 ± 1.03

83.02 ± 1.04

84.18 ± 1.04

83.08 ± 1.03

67.84 ± 1.66

63.64 ± 1.83

62.88 ± 1.02

57.31 ± 1.74

72.28 ± 1.46

65.12 ± 1.68

72.37 ± 1.26

65.35 ± 1.44

75.86 ± 1.02

74.20 ± 1.07

62.86 ± 0.71

59.02 ± 1.06

82.92 ± 0.61

81.70 ± 0.72

82.37 ± 0.73

81.10 ± 0.90

VALIDATION ON P ROPOSED A NALYSIS AND M ECHANISM

Table 12 isolates the contributions of the adaptive diffusion basis and the masked prediction objective. Removing masked prediction 𝜆pred = 0 consistently reduces both Accuracy and Macro-F1 on CoraCA and DBLP4k, indicating that the predictive alignment component provides complementary 42

representation learning signals. Increasing the heat basis width from 𝑅 = 1 to 𝑅 = 4 further improves performance when the predictive objective is enabled, while its effect is smaller without masked prediction. These results support the complementary roles of adaptive diffusion and masked representation alignment in FedASTRA. Table 12: Ablation study of adaptive diffusion and masked prediction at 𝐾 = 6. This study is separate from the heat-width sweep in Appendix D. Dataset

Reported condition

Parameters

Accuracy (%)

Macro-F1 (%)

CoraCA CoraCA CoraCA CoraCA DBLP4k DBLP4k DBLP4k DBLP4k

𝑅 = 1, 𝜆 pred = 0 𝑅 = 1, 𝜆 pred = 1 𝑅 = 4, 𝜆 pred = 0 𝑅 = 4, 𝜆 pred = 1 𝑅 = 1, 𝜆 pred = 0 𝑅 = 1, 𝜆 pred = 1 𝑅 = 4, 𝜆 pred = 0 𝑅 = 4, 𝜆 pred = 1

126,407 126,407 177,671 177,671 55,684 55,684 106,372 106,372

67.26 ± 1.48 74.27 ± 0.56 69.32 ± 0.69 74.97 ± 0.63 77.54 ± 0.70 79.58 ± 0.67 78.23 ± 0.51 79.75 ± 0.82

62.94 ± 1.75 71.96 ± 0.58 65.31 ± 1.15 72.79 ± 0.93 76.77 ± 0.78 78.99 ± 0.49 77.60 ± 0.56 79.15 ± 0.75

Table 13 reports the controlled-truncation results. The controlled partitions exhibit the expected ordering of retained higher-order co-membership mass. The observed pair/triple mass is 72.44/65.11%, 16.67/2.78%, and 9.68/1.10% for the low, reference, and high CoraCA partitions, respectively. The corresponding DBLP4k values are 27.21/9.24%, 16.67/2.78%, and 16.33/2.70%. These results confirm that the three partition conditions differ in structural truncation while preserving client loads and label histograms across paired comparisons. The ordering applies to co-membership mass only. Prediction performance also depends on feature and label alignment, so the truncation level alone does not determine Accuracy or Macro-F1. Table 13: Controlled-truncation results at 𝐾 = 6. Dataset

Reported condition

Accuracy (%)

Macro-F1 (%)

CoraCA CoraCA CoraCA DBLP4k DBLP4k DBLP4k

Low-truncation Reference High-truncation Low-truncation Reference High-truncation

77.99 ± 0.58 75.58 ± 1.33 73.97 ± 0.80 78.23 ± 1.76 79.46 ± 1.23 79.24 ± 1.49

76.40 ± 0.74 73.27 ± 1.07 71.34 ± 0.80 77.54 ± 1.59 78.85 ± 1.13 78.66 ± 1.49

Table 14 and Table 15 summarize the two-client structural identification audit. The audit uses five fixed 𝐾 = 2, 𝑐 = 1 diagnostic partitions per source, exact hyperedge types, and unit weights. Held-out
Í parent tokens mark cross-client rows and verify the oracle Φ𝑞 (H ) = 𝑒 |𝑒| 𝑞 after the partition is fixed. Sorting fragment sizes gives both attainable endpoints. Labels are used only by the partition constructor, and no learner is trained. These evaluator partitions are independent of the reported 𝐾 ∈ {3, 6, 9} training partitions. Across all evaluated cells, no higher-order co-membership target is point identified, and the median relative endpoint width increases from 36.37% at 𝑞 = 2 to 93.71% at 𝑞 = 5. These results empirically support the predicted ambiguity caused by latent hyperedge correspondence, especially for higher-order structural targets. Table 14: Two-client structural identification audit on four native datasets. For each order 𝑞, the audit contains 20 releases and 30 eligible strata. Relative endpoint width is (Φ+𝑞 − Φ𝑞− )/Φ+𝑞 . By Corollary 2, half of this normalized width gives the corresponding minimax lower bound for observable point estimation of the same order-𝑞 mass. 𝑞

Releases

Eligible strata

Point identified

Median relative width

𝑞 -mass floor

Oracle coverage

2 3 4 5

20 20 20 20

30 30 30 30

0/30 0/30 0/30 0/30

36.37% 70.56% 86.62% 93.71%

18.18% 35.28% 43.31% 46.85%

20/20 20/20 20/20 20/20

43

Table 15: Median absolute sharp-endpoint gaps over five two-client diagnostic partitions, measured in order-𝑞 tuple units. The values preserve the original dataset scale, complementing the normalized endpoint widths reported in Table 14. Dataset

𝑞=2

𝑞=3

𝑞=4

𝑞=5

CoraCA DBLP4k IMDB4k Trivago

6,714 3,752,114 18,587 410,593

69,204 983,644,998 205,338 3,263,206

469,120 2.1971×1011 1,581,947 23,744,190

2,631,843 4.2294×1013 10,490,694 209,428,691

To further verify the correspondence-invariant property of the learned representation, we conduct an evaluator-only permutation audit on the released relation columns. A separate CPU float32 audit permutes the 743 released relation columns of CoraCA client 0 at 𝐾 = 3 and protocol seed 0 a total of 32 times. The fixed instance has 892 nodes, 1,499 incidences, a 128-dimensional projected input, hidden width 16, and 𝑅 = 4. It uses neither labels nor training. The maximum differences in 𝑃 𝑘 , all heat-filtered features, and fixed-model logits are each zero, verifying the algebra used by Corollary 4 under this fixed implementation audit with shared numerical inputs. Table 16 reports evaluator-only audits under relaxed observation assumptions. Type coarsening removes a matching restriction while preserving the released row inventory, and the numeric containment check confirms that the coarsened endpoint hull contains the exact hull in all audited cells. In contrast, status removal and one-sided deletion alter the released inventory, so finite compatible classes require additional public bounds beyond the exact equal-count endpoint formula. Training and model selection are absent from all 120 audit outcomes in this evaluator-only audit. Table 16: Evaluator-only audit of relaxed observation assumptions on CoraCA and DBLP4k. The 40 cells consist of five fixed partitions and 𝑞 ∈ {2, 3, 4, 5} for each dataset. Release change

Cells

Numeric endpoint

Merge observed type strata

40

Available

Remove local/cross marks

40

Bound required

Delete 10% of one-side fragments

40

Bound required

Audited conclusion The coarsened endpoint hull contains the exact hull in 40/40 cells. Finite endpoints require a public cross-row count and support bound. Finite endpoints require public missing-row count, weight, and support bounds.

Figure 3 and Table 17 report the heat-width sweep over 𝑅 ∈ {0, 1, 2, 4, 8} on CoraCA, DBLP4k, and Trivago. CoraCA reaches 76.68% Accuracy and 74.35% Macro-F1 at 𝑅 = 2, compared with 70.67% and 67.85% at 𝑅 = 0. DBLP4k has closely grouped means over 𝑅 = 1, 2, 4, within 0.09 Accuracy points and 0.10 Macro-F1 points, followed by lower means at 𝑅 = 8. Trivago reaches its highest Accuracy of 27.66% at 𝑅 = 4 and its highest Macro-F1 of 7.32% at 𝑅 = 8. The latter change from 𝑅 = 4 adds 0.30 Macro-F1 points, with parameters increasing from 472,224 to 818,336 and fitting time from 235.3 to 417.9 seconds. The sweep identifies a dataset-dependent finite-capacity tradeoff. Moderate widths improve the attribute-only control, while additional channels increase parameters and runtime and can change the two classification metrics differently. Spectral density describes approximation by a growing family of heat filters, but finite-sample accuracy also depends on capacity and fitting; therefore, density alone does not impose a monotone ordering on these empirical curves. Each width’s runtime and parameter count follows the same measurement protocol described in Appendix D.4.

44

DBLP4k

CoraCA

Accuracy (%)

# Params (×103)

Macro-F1 (%)

Runtime (s) 500

80

78

250

76

74

200

300

72

70

150

200

68

66

100

81

80

80

79

79

78

78

77

77

76

32

8

28

7

24

6

400

100 0

200

500

150

400 300

100

200 50

100

0

0

Trivago

800

20

5 0

1

2

4

8

0

Heat channels R

1

2

4

400

600

300

400

200

200

100

8

0

0

Heat channels R

1

2

4

8

0

0

Heat channels R

1

2

4

8

Heat channels R

Figure 3: Predictive utility and cost of the heat-basis width. We fix 𝐾 = 6 and 𝜆pred = 1 on all three datasets. The 𝑅 = 0 control retains masked prediction and removes diffusion.

Table 17: Heat-basis width at 𝐾 = 6 and 𝜆pred = 1. Parameter counts include the online model and predictive head. Runtime uses the synchronized fitting boundary described in Appendix D.

E.4

Dataset

𝑅 Accuracy (%) Macro-F1 (%) Parameters Runtime (s)

CoraCA

0 1 2 4 8

70.67 ± 0.94 73.97 ± 1.16 76.68 ± 2.26 73.97 ± 0.87 73.91 ± 1.17

67.85 ± 1.64 71.44 ± 1.58 74.35 ± 1.96 71.43 ± 1.12 71.09 ± 1.24

109,319 126,407 143,495 177,671 246,023

55.0 ± 1.7 164.9 ± 0.3 199.8 ± 4.7 264.6 ± 1.8 451.5 ± 2.9

DBLP4k 0 1 2 4 8

78.66 ± 0.87 79.79 ± 0.95 79.79 ± 1.02 79.87 ± 1.41 77.70 ± 0.75

78.16 ± 0.87 79.23 ± 1.01 79.18 ± 0.98 79.27 ± 1.31 77.09 ± 0.82

38,788 55,684 72,580 106,372 173,956

54.8 ± 0.4 173.1 ± 2.1 208.7 ± 2.4 279.6 ± 0.3 478.9 ± 2.8

Trivago

21.80 ± 2.16 25.66 ± 1.97 26.93 ± 0.42 27.66 ± 0.91 26.59 ± 0.47

5.25 ± 0.29 6.35 ± 0.31 6.88 ± 0.48 7.01 ± 0.13 7.32 ± 0.18

126,112 212,640 299,168 472,224 818,336

15.2 ± 0.7 109.8 ± 0.1 150.8 ± 0.3 235.3 ± 0.6 417.9 ± 0.1

0 1 2 4 8

S CALABILITY ON L ARGE - SCALE DATA

Table 18 reports the full-scale evaluation on the complete graph assets and official splits. It contains one full-data execution rather than repeated runs. It records predictive quality, communication, wall-clock time, throughput, and peak device allocation with complete root and citation coverage for every compared method. FedASTRA achieves the highest predictive performance in this full-data setting while maintaining parameter-only communication.

45

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 GiB = 230 bytes. Communication counts bidirectional trainable-parameter traffic, excluding client-local BatchNorm buffers for all methods. Method

Parameters

Parameter traffic per round (MiB)

Wall-clock (s)

Roots/s

Peak GPU (GiB)

Fed-MLP Fed-SIGN Fed-HGNN Fed-HNHN Fed-HyperGCN Fed-GCN FedASTRA

983,380 984,442 982,672 34,672 984,442 983,380 976,504

60.02 60.09 59.98 2.12 60.09 60.02 59.60

47.2 47.6 54.6 312.5 406.6 61.8 1069.7

511,594 506,887 442,051 77,259 59,386 390,637 22,570

0.58 0.68 1.52 0.54 8.89 2.92 19.53

All requested neighborhoods are evaluated without truncation.

46

Related documents

• More Is Better? Exploring Latent Correspondence in Federated Hypergraph Learning#1490757
• Batch Before You Lift: Scalable Topological Deep Learning on Large Graphs#1249671
• Batch Before You Lift: Scalable Topological Deep Learning on Large Graphs#1242759
• From Coordinate Matching to Structural Alignment: Rethinking Prototype Alignment in Heterogeneous Federated Learning#168271
• Rethinking One-Shot Federated Graph Learning: Training-Free Statistical Estimation#973757