acceptodds
Under review as a conference paper at ICLR 2027

Interaction-Aware Client Selection in Federated Learning via Learned Coalition Utility

Abstract

Client selection in federated learning is inherently combinatorial. The value of a training round depends on which clients train together, not on their individual contributions alone. Clients with overlapping data are redundant when combined, while those with complementary data reinforce one another, and which of these relationships matter shifts as the global model evolves. Methods that rank clients by individual importance, including Shapley-based selectors, and methods limited to pairwise correlations cannot capture this higher-order, evolving structure. We introduce , which learns a surrogate of coalition utility directly and selects client subsets by their predicted joint utility. A tree-based surrogate captures client interactions up to a controllable order and is refit each round to track the evolving learning dynamics. The same surrogate proposes the candidate pool and chooses the aggregation set, and we analyse the induced selection regret. Because the fitted surrogate decomposes additively into interaction effects, each selection step scores a candidate by its individual effect and its interactions with the clients already selected, making the policy interpretable. Across twelve settings on nine datasets, attains the highest trajectory-mean accuracy in every setting, by up to points over the strongest baseline.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
federated learning, client selection, coalition utility, cooperative game theory, Shapley interactions, interpretability, surrogate model

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_dxb7OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes NEXUSFL, a federated learning client selection method that models interactions among clients using a tree-based surrogate to capture complementarity and redundancy. Experiments across 9 datasets and 12 settings demonstrate strong performance, while theoretical analysis provides insights into selection regret.

Critical strengths
  1. Unlike methods that evaluate each client's contribution individually, NEXUSFL considers complementarity and redundancy among clients, enabling more effective client coalition selection. Both its motivation and methodology are well justified.

  2. The paper evaluates NEXUSFL on nine datasets across twelve experimental settings. It achieves the highest trajectory-mean accuracy in nearly all settings, demonstrating strong empirical performance.

  3. The paper is comprehensive, with a relatively complete theoretical analysis and extensive experimental evaluation.

Critical weaknesses
  1. Appendix B shows that coalition utility evaluation accounts for 46% of the total time per round for CNN / CIFAR-10 and 85% for DistilBERT / FinGPT, substantially exceeding the proportion spent on client model training. Although Figure 6(b) shows that reducing the sampling budget BB can lower computational costs, it may also degrade model performance. Therefore, adaptively selecting an appropriate BB to balance computational efficiency and model performance remains a direction worth further investigation.

  2. NEXUSFL relies on a surrogate tree model to predict the utility of different client combinations. However, Table 14 shows substantial variation in the surrogate’s cross-round predictive correlations across tasks. For FinGPT, the Spearman correlation coefficient is only 0.234. This suggests that the surrogate's predictive capability may depend on task characteristics, potentially affecting the effectiveness of client selection.

Questions for authors

See weaknesses.

1 comment
AuthorsOpenReview ↗

Response to Reviewer dxb7

We thank the reviewer for their constructive feedback and for appreciating our interaction-aware motivation, theoretical analysis, and empirical performance.


W1: Coalition Evaluation Cost and Adaptive Budget. We agree that coalition evaluation is the dominant cost of the pipeline and that adaptively adjusting BB is a valuable direction, which we also note in the Limitations and Future Work paragraph of Section 5. If the coalition utility game stabilized in later rounds, a natural way to reduce evaluation cost would be to decay BB as training progresses. In Appendix F.5 (Table 16), however, the mean Jaccard overlap between consecutive selected sets remains low even in the final quarter of training (Q4: 0.17–0.28), showing that the selection policy continues to shift across rounds. Reducing BB safely without degrading selection would therefore require reliable uncertainty estimates under drift (Kim & Choi, 2022) rather than a fixed decay schedule, and we leave this coupling to future work.


W2: Task Dependence of Cross-Round Surrogate Correlation.

We agree that cross-round correlation in Table 14 varies across tasks (0.234–0.809). Because next-round Spearman evaluates the previous round's surrogate on fresh current-round coalitions, it reflects both surrogate generalization and how rapidly coalition rankings shift after a global-model update.

However, lower cross-round correlation on tasks such as CIFAR-10 LT (0.442), Sent140 (0.339), and FinGPT (0.234) does not degrade selection performance. Across all six settings in Table 14, NEXUSFL beats every baseline in trajectory-mean accuracy (Tables 1 and 9, summarised below), and on FinGPT it avoids the sharp round-to-round accuracy drops seen in FedAvg, S-FedAvg, DivFL, and FilFL (Figure 8b).

TaskNext-round Spearman (Table 14)Reservoir R² (Figs. 11–12)NEXUSFL vs. Best Baseline, Mean (%)
CIFAR-10 D(0.1)0.8090.77048.0 vs. 45.6 (+2.4)
CIFAR-10 D(0.5)0.7610.71450.5 vs. 49.3 (+1.2)
SVHN D(0.1)0.6310.68549.9 vs. 37.6 (+12.3)
CIFAR-10 LT0.4420.60032.5 vs. 31.9 (+0.6)
Sent1400.3390.47181.1 vs. 78.8 (+2.3)
FinGPT D(0.1)0.2340.68487.4 vs. 85.3 (+2.1)

In NEXUSFL, final selection of the 10 aggregated clients within the pool always evaluates BB fresh coalitions on the current global model and refits the surrogate on the updated reservoir (reaching a mean Reservoir R² of 0.684 on FinGPT, as shown above). Final selection therefore adapts to the current round's global model even when cross-round rankings shift.


We thank the reviewer again for these constructive suggestions, which help clarify the trade-offs and diagnostic properties of our method.

Reviewer_FPiYOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes NEXUSFL, which shifts client selection from independent scoring to directly learning coalition utility and selects client sets based on the predicted joint utility. It uses a tree-based surrogate to capture client interactions up to a controllable order and refits the surrogate each round to track the evolving learning dynamics. The paper provides theoretical proofs and validates the performance of the proposed approach through experiments.

Critical strengths

The paper provides an exact decomposition of interaction effects, a decomposition and upper bound for cumulative selection regret, and an end-to-end convergence analysis under specific assumptions, giving it a solid theoretical foundation.

Critical weaknesses

Although the paper proves that tree depth limits the highest interaction order the surrogate can represent, increasing tree depth also increases model complexity. Therefore, Table 11 cannot directly verify that the performance gain comes from higher-order interactions. Further evidence or validation is needed.

Questions for authors

The paper involves a considerable number of hyperparameters. It is suggested that the authors further explain the rationale for choosing these hyperparameters and supplement relevant experiments or conduct a sensitivity analysis.

3 comments
AuthorsOpenReview ↗

Response to Reviewer FPiY [1/2]

We thank the reviewer for their constructive feedback and for recognising the theoretical foundation of the paper, including the interaction-effect decomposition, cumulative selection regret bound, and convergence analysis.


W1: Tree Depth Interaction Order vs. Model Complexity. We agree that increasing tree depth dd raises both the maximal interaction order and model capacity. To examine whether the gains in Table 11 reflect interaction structure rather than capacity alone, we look at two observations.

  1. Higher-order interactions are present in the coalition utility. Figure 2 directly decomposes the exact coalition utility UtU_t on CIFAR-10 without any surrogate. Under strong Dirichlet label skew (α=0.1\alpha = 0.1), pairwise and higher-order terms account for over half (~55%) of the variation in UtU_t. Genuine multi-client interaction structure therefore exists to be modeled, especially at smaller α\alpha.
  2. Test accuracy and out-of-sample generalization are not monotone in depth. We augment the test accuracies already reported in Table 11 with Reservoir R² (in-sample fit on the reservoir, Section 4.2) and Next round Pearson (out-of-sample correlation of the previous round's surrogate on fresh current-round coalitions).

Each cell reports Final accuracy (%) / Reservoir R² / Next-round Pearson:

  d     α = 0.1      α = 0.5      α = 1.0   
  1     54.6±0.4 / .564 / .737      57.1±0.8 / .483 / .683      58.3±0.4 / .458 / .664   
  2     54.9±0.9 / .678 / .775      59.3±0.2 / .604 / .724      60.2±0.4 / .570 / .703   
  4     56.6±1.0 / .765 / .776      59.8±0.9 / .710 / .751      60.9±0.3 / .673 / .721   
  8     55.7±0.8 / .824 / .740      59.1±1.3 / .789 / .748      61.1±0.4 / .754 / .721   

Although Reservoir R² increases steadily up to d=8d=8 across all α\alpha, test accuracy and Next round Pearson do not follow the same trend. Moving from d=4d=4 to d=8d=8 lowers test accuracy at α∈{0.1,0.5}\alpha \in \{0.1, 0.5\}, and Next round Pearson peaks at d=4d=4 in every setting before declining or plateauing at d=8d=8 (falling from 0.776 to 0.740 at α=0.1\alpha=0.1).

Taken together, while tree depth couples interaction order with model capacity, added capacity beyond d=4d=4 improves in-sample reservoir fit without helping out-of-sample generalization. We have added these diagnostics to Table 11 and the corresponding discussion to Appendix F.3 (Pool Size and Tree Depth).

AuthorsOpenReview ↗

Response to Reviewer FPiY [2/2]

Q1: Hyperparameter Sensitivity Analysis. We thank the reviewer for raising this concern. We would like to highlight that all 12 benchmark settings use one shared configuration of NEXUSFL (Appendix A.4), with no dataset-specific hyperparameter tuning. Below we describe what each key hyperparameter controls and the trade-offs governing its choice, point to the corresponding ablations in the paper, and describe the new sensitivity analyses we added.

1. Tree depth dd (Appendix F.3, Table 11). The depth dd sets the highest interaction order the surrogate can represent (Lemma 1). As discussed in our response to W1, the additive surrogate (d=1d=1) is the worst at every α\alpha, and depths beyond d=4d=4 improve in-sample fit without helping out-of-sample generalization. Because surrogate fitting is inexpensive relative to coalition evaluation, dd can be chosen by standard hyperparameter tuning.

2. Pool size pp (Appendix F.3, Table 10; Appendix D, Tables 6 and 8). The candidate set needs p>kp > k so the selector can choose among trained clients rather than reducing to direct client ranking at p=kp=k. Increasing pp expands the set of reachable coalitions and lowers the pool gap δt\delta_t (Equation 8). At a fixed BB, however, the same evaluations cover a smaller share of the in-pool coalitions, which raises the surrogate gap, and client training cost grows linearly in pp. Tables 6, 8 and 10 show that, at a fixed BB, a larger pool first improves selection and then stops helping. When tuning, pp should therefore be increased together with BB, within the available client training budget. We use p=2k=20p=2k=20, which gives the selector a choice inside the pool while limiting client training to twice the aggregation set.

3. Coalition budget BB (Section 4.3, Figure 6b; Appendix B). The coalition budget BB is the number of coalitions evaluated per round and controls the estimation term of the surrogate error (Equation 10). The cost of coalition evaluation is linear in BB (Appendix B). Figure 6b shows that accuracy keeps improving as BB grows, which makes BB a direct trade-off between selection quality and server-side evaluation time. As noted for pp, the two should be scaled together, since a larger pool contains more coalitions to cover. In the experiment with 1000 clients (Appendix F.2), for example, we raise both pp and BB.

4. Reservoir capacity ∣R∣max⁡|\mathcal{R}|_{\max} (Appendix F.8, Table 21). With BB new observations per round, the capacity sets how many past rounds the reservoir can hold and should be set relative to BB. Retaining more rounds gives the surrogate more client combinations and lowers the estimation term of Equation 10, while older entries raise the staleness term (Proposition 1). Table 21 shows that, at a fixed BB, trajectory-mean accuracy first improves with capacity and then declines once the reservoir holds many older rounds. We use ∣R∣max⁡=2500|\mathcal{R}|_{\max}=2500 (about 5 rounds at B=500B=500).

New Sensitivity Analyses (Added in Revision):

5. Softmax temperatures τsel\tau_{\mathrm{sel}} and τpool\tau_{\mathrm{pool}} (Section 3.1, Equation 7; Appendix F.13, Table 26). The same softmax policy is used twice per round, with τsel\tau_{\mathrm{sel}} governing selection of the aggregation set from the pool and τpool\tau_{\mathrm{pool}} governing proposal of the next pool from all clients. In both uses, the temperature trades off exploitation of the surrogate against keeping lower-scoring candidates reachable. We sweep each temperature on CIFAR-10 D(0.1)\mathrm{D}(0.1) with all other hyperparameters fixed. For both temperatures, trajectory-mean accuracy declines at larger values, where sampling is less concentrated on the surrogate's highest-scoring candidates and approaches uniform sampling.

6. Eviction decay κ\kappa (Appendix A.5; Appendix F.14, Table 27). When the reservoir is full, entries are evicted with probability proportional to exp⁡(κ⋅age)\exp(\kappa\cdot\mathrm{age}), with κ=0\kappa=0 giving uniform eviction. We sweep κ∈{0.0,0.1,0.5,1.0}\kappa \in \lbrace 0.0, 0.1, 0.5, 1.0 \rbrace on CIFAR-10 D(0.1)\mathrm{D}(0.1). Increasing κ\kappa lowers the reservoir's mean age, limiting how long stale entries persist as the global model evolves (Proposition 1). All three positive values improve Final accuracy over uniform eviction with little variation among them, while trajectory-mean accuracy remains comparable across all four settings.

We thank the reviewer for this helpful suggestion. We have added this discussion to Appendix A.4.

Thank you for the author response. After reviewing the feedback and the manuscript, my doubts have been resolved, and I will maintain my rating.

Reviewer_uJXwOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies client selection in federated learning. It points out the limitations of the popular Shapley value-based methods, which fail to identify complementary or redundant pairs. To address this issue, this paper proposes NEXUSFL, which uses a tree-based model as a surrogate model of the utility function. Such a design enables NEXUSFL to identify complementary clients during selection. Experimental results show that the method effectively improves trajectory-mean accuracy and final accuracy in multiple tasks.

Critical strengths
  • The paper is well written and easy to follow. The motivation is clear, and the solution effectively addresses the issue. Most design choices are well supported by both theory and empirical ablations. Though using a surrogate model to predict the utility function itself is not new, the proposed NEXUSFL adapts it well for the FL setup with design choices such as a recency-weighted reservoir, candidate pool, and tree-based surrogate. The choice of using a tree-based surrogate model also provides interesting interpretability regarding complementary and redundant pairs.
Critical weaknesses
  • While most baselines use the same compute budget, the reported performance of FedAvg is based on only half the compute. This seems to be unfair. I suggest reporting the one with the same budget, just as setting D in Table 12.
Questions for authors
  • I suggest the authors add a description for Figure 1b regarding the values of nodes and edges. It’s hard to understand without that context.
  • It seems that the description regarding the Long-tail setup is missing. Therefore, it’s hard to infer the property under such a setup.
2 comments
AuthorsOpenReview ↗

Response to Reviewer uJXw

We thank the reviewer for their constructive feedback and for highlighting the clarity of the presentation, our FL-specific design choices, and the interpretability of complementary and redundant client pairs.


W1: FedAvg Computational-Budget Parity. All methods in Tables 1 and 9 aggregate k=10k=10 clients per round. For FedAvg, training 20 random clients and aggregating 10 at random produces the exact same update distribution as training and aggregating 10 directly. Matching the 20-client training budget therefore requires aggregating all 20 trained clients (FedAvg-20, p=k=20p=k=20), which doubles the aggregation set size relative to all k=10k=10 methods in Tables 1 and 9.

To provide a direct training-compute-matched comparison without changing the k=10k=10 protocol of Tables 1 and 9, we clarified this distinction in Appendix A.3 and added Appendix F.12 (Table 25) comparing FedAvg (k=10k=10), FedAvg-20 (p=k=20p=k=20), and NEXUSFL across all 12 benchmark settings with 5 seeds (reproduced below):

Method (Final / Mean)CIFAR-10 D(0.1)SVHN D(0.1)DBpedia D(0.1)Covertype D(0.5)CelebA D(0.5)Sent140
FedAvg51.2±3.0 / 40.0±1.267.6±5.9 / 36.6±4.397.8±0.4 / 78.1±2.985.5±1.9 / 81.9±1.289.9±1.4 / 83.3±1.282.3±2.2 / 75.9±1.6
FedAvg-2055.0±2.7 / 45.0±1.173.1±2.4 / 42.5±3.798.1±0.1 / 80.9±2.685.6±4.4 / 83.3±1.190.1±1.8 / 84.4±1.081.7±2.9 / 76.8±1.9
NEXUSFL55.5±0.9 / 48.0±1.174.8±1.7 / 49.9±4.798.2±0.4 / 88.7±0.589.3±0.5 / 86.0±0.291.5±0.3 / 87.6±0.684.7±1.5 / 81.1±0.8
Method (Final / Mean)CIFAR-10 LTFinGPTYelp D(0.5)PathMNIST D(0.1)CIFAR-10 D(0.5)Yelp D(0.1)
FedAvg41.4±1.1 / 30.4±0.772.3±16.2 / 74.4±2.753.2±1.8 / 49.6±0.464.9±3.8 / 53.3±1.759.4±1.3 / 48.3±0.248.1±1.9 / 42.5±0.2
FedAvg-2041.4±1.0 / 30.5±0.786.6±7.4 / 79.1±2.357.0±0.8 / 52.0±0.269.2±1.7 / 57.3±2.060.8±0.9 / 50.1±0.149.4±2.3 / 44.9±0.5
NEXUSFL43.4±0.9 / 32.5±0.687.9±3.9 / 87.4±2.457.2±0.5 / 53.6±0.0571.6±2.6 / 60.6±2.260.1±1.5 / 50.5±0.752.1±1.8 / 48.4±0.5

NEXUSFL achieves higher trajectory-mean accuracy than both random baselines in all 12 settings and higher final accuracy in 11 of 12 while aggregating half as many clients as FedAvg-20. Although doubling the random aggregation set improves FedAvg across most tasks, averaging 20 random updates still mixes in redundant or conflicting clients, whereas selecting 10 complementary ones extracts faster progress.


Q1: Figure 1b Nodes and Edges. We updated Figure 1(b) to include an explicit legend (Nodes = main effects, Edges = interactions) and expanded the Figure 1 caption to clarify that panel (a) uses fixed Shapley scores, whereas panel (b) represents main effects as nodes and signed interactions as edges.


Q2: Long-Tail Partition Setup. Thank you for noting this omission; we have added this description to Appendix A.2. In the long-tail setup, each class c∈{0,…,C−1}c \in \{0, \ldots, C-1\} retains nc=⌊Nmax⁡⋅IR−c/(C−1)⌋n_c = \lfloor N_{\max} \cdot \mathrm{IR}^{-c/(C-1)} \rfloor training samples, where Nmax⁡N_{\max} is the balanced per-class sample count and IR=n0/nC−1≥1\mathrm{IR} = n_0 / n_{C-1} \ge 1 controls the exponential decay from head to tail (IR = 1 is balanced; with IR = 10, the rarest class keeps 1/10 of the samples of the largest). The retained samples are shuffled and partitioned uniformly into equal-sized shards across the nn clients.


We thank the reviewer for highlighting these points, which further strengthen our empirical evaluation and improve the clarity of the paper.

Thank you for the response, which has addressed my concerns and questions. The reason I brought up FedAvg-20 is that the most naive strategy is no selection at all, i.e., aggregating all trained clients, given that the compute has already been spent. Therefore, I think it should be a baseline in Table 1. That said, this is more a matter of presentation, and I am fine with the result being in the appendix. I would suggest adding a brief discussion of it in the main text. Overall, I think it is a good paper, and I will maintain my score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank the reviewers for the time and effort they put into their reviews. We appreciate the constructive feedback and found it valuable for strengthening both the experimental validation and the clarity of the manuscript. We have uploaded a revised PDF with all changes highlighted in blue\color{blue}{\text{blue}}, summarised below:

New Experiments and Diagnostics:

  • App. F.12 (Table 25): Added a 12-setting comparison against training-budget-matched FedAvg-20 (p=k=20p=k=20, 5 seeds). NEXUSFL beats FedAvg-20 in trajectory-mean accuracy in all 12 settings and in final accuracy in 11 of 12, aggregating half as many clients. [uJXw]
  • App. F.3 (Table 11): Added Reservoir R² and Next-round Pearson to the CIFAR-10 depth ablation (d∈{1,2,4,8}d \in \lbrace 1, 2, 4, 8 \rbrace, 3 seeds). Depths beyond d=4d=4 raise in-sample fit without improving out-of-sample generalisation. [FPiY]
  • App. F.13–F.14 (Tables 26–27): Added sensitivity sweeps on CIFAR-10 D(0.1) (3 seeds) for softmax temperatures (τsel,τpool\tau_{\mathrm{sel}}, \tau_{\mathrm{pool}}) and eviction decay (κ\kappa). [FPiY]

Presentation and Clarifications:

  • App. A.4: Added a Hyperparameter Rationale and Sensitivity summary covering tree depth (dd), pool size (pp), coalition budget (BB), reservoir capacity (∣R∣max⁡\lvert\mathcal{R}\rvert_{\max}), softmax temperatures (τsel,τpool\tau_{\mathrm{sel}}, \tau_{\mathrm{pool}}), and eviction decay (κ\kappa). [FPiY]
  • Figure 1(b) & Caption: Added an explicit legend (Nodes = main effects, Edges = interactions) and clarified that panel (a) uses fixed Shapley scores while panel (b) shows main effects and signed interactions. [uJXw]
  • App. A.2: Added the exact procedure for constructing the CIFAR-10 long-tail partition. [uJXw]
  • App. A.3: Clarified the compute-matched FedAvg-20 baseline protocol. [uJXw]

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.