HYGMA: Hypergraph Coordination Networks with Dynamic Grouping for Multi-Agent Reinforcement Learning
Authors: Chiqiang Liu
Dazi Li
Venue: ICML 2025 poster (2025)
Keywords: Multi-Agent Reinforcement Learning
Hypergraph Convolution
Dynamic Grouping
Multi-Agent Cooperation
Primary area: reinforcement_learning->multiagent
TL;DR: HYGMA integrates dynamic spectral clustering with hypergraph neural networks to enable adaptive agent grouping and efficient information processing in multi-agent reinforcement learning, outperforming state-of-the-art approaches in cooperative tasks.

Abstract: Cooperative multi-agent reinforcement learning faces significant challenges in effectively organizing agent relationships and facilitating information exchange, particularly when agents need to adapt their coordination patterns dynamically. This paper presents a novel framework that integrates dynamic spectral clustering with hypergraph neural networks to enable adaptive group formation and efficient information processing in multi-agent systems. The proposed framework dynamically constructs and updates hypergraph structures through spectral clustering on agents' state histories, enabling higher-order relationships to emerge naturally from agent interactions. The hypergraph structure is enhanced with attention mechanisms for selective information processing, providing an expressive and efficient way to model complex agent relationships. This architecture can be implemented in both value-based and policy-based paradigms through a unified objective combining task performance with structural regularization. Extensive experiments on challenging cooperative tasks demonstrate that our method significantly outperforms state-of-the-art approaches in both sample efficiency and final performance. The code is available at: https://github.com/mysteryelder/HYGMA.

HYGMA: Hypergraph Coordination Networks with Dynamic Grouping for Multi-Agent Reinforcement Learning
Chiqiang Liu Dazi Li
Abstract
efficient organization and coordination of agents to achieve system-widk objectives. This becomes particularly criti- cal when agent relationships need to dynamically evolve in response to changing task demands and environmental conditions.
Cooperative multi-agent reinforcement learning faces significant challenges in effectively orga- nizing agent relationships and facilitating infor- mation exchange, particularly when agents need to adapt their coordination patterns dynamically. This paper presents novel framework that in- tegrates dynamic spectral clustering with hyper- graph neural networks to enable adaptive group formation and efficient information processing in multi-agent systems. The proposed frame- work dynamically constructs and updates hyper- graph structures through spectral clustering on agents' state histories, enabling higher-order rela- tionships to emerge naturally from agent interac- tions. The hypergraph structure is enhanced with attention mechanisms for selective information processing, providing an expressive and efficient way to model complex agent relationships. This architecture can be implemented in both value- based and policy-based paradigms through uni- fied objective combining task performance with structural regularization. Extensive experiments on challenging cooperative tasks demonstrate that our method significantly outperforms state- of-the-art art approaches in both sample efficiency and final performance. The code is available at:
Despite significant advances in value decomposition meth- ods and policy optimization techniques (Huang et al., 2025; Li et al., 2021), existing MARL approaches face inherent limitations in modeling the dynamic nature of inter-agent relationships. Traditional methods either adopt a uniform treatment of all agents (Tan, 1993; Heess et al., 2017) or rely on static grouping structures (Zhang et al., 2020; Sukhbaatar et al., 2016). Such rigid frameworks often fail capture the evolving coordination requirements in complex multi- agent systems, leading to suboptimal performance and inef- ficient information exchange. Receante.Reecntt Recent work has highlighted the importance of adaptive coordination structures in MARL (Zang et al., 2024), yet the development of frameworks that can automatically identify and adapt agent relationships remains an open challenge (Niu et al., 2021).
To address these limitations, this paper proposes HYGMA (HY pergraph Grouping for Multi-Agent coordination), novel framework that leverages hypergraph networks to capture and adapt the complex relationships in multi-agent systems. Unlike traditional graph-based approaches that can only model pairwise interactions, hypergraph networks naturally represent higher-order relationships among multi- ple agents (Kim et al., 2024), enabling more expressive and efficient group coordination. The proposed framework dy- namically constructs hypergraph structures through spectral clustering on agents' state histories, allowing agent groups to form and evolve based on their actual coordination needs during task execution. The core of our approach is a two- level architecture that separates group formation from infor- mation processing. The first level employs dynamic spectral clustering to identify agent groups based on their state his- tories and interaction patterns. These grouping results are then used to construct hyperedges in the hypergraph net- work. The second level utilizes hypergraph convolution networks (HGCN) to process and propagate information among agents, enabling efficient feature extraction that re- spects the identified group structures. This architecture can
1. Introduction
Cooperative multi-agent reinforcement learning (MARL) has emerged as a promising paradigm for addressing com- plex real-world challenges that require coordinated decision- making among multiple agents (Charbonnier et al., 2025; Si et al., 2025). A fundamental challenge in MARL is the
'College of Information Science and Technology, Beijing Uni- versity of Chemical Technology, Beijing, China. Correspondence to: Dazi Li <lidz @ buc..ed.............
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Hypergraph Coordination with Dynamic Grouping for MARL
be effectively integrated into both value-based and policy- based multi-agent learning frameworks.
action graphs that cannot capture the higher-order relation- ships inherent in complex team coordination.
The main contributions of this work are summarized as follows:
Dynamic Grouping Mechanisms Prior work in agent or- ganization has explored three principal paradigms: prede- fined grouping (Lhaksmana et al., 2018; Macarthur et al., 2011; Russell & Zimdars, 2003), task-specific allocation (Iqbal et al., 2022: Lee et al., 2019; Shu & Tian, 2018), and role-based decomposition. While role-learning methods like ROMA (Wang et al., 2020b) and RODE (Wang et al., 2020c) enable context-dependent specialization, they typically re- quire manual specification of role numbers or action space partitions. VAST (Phan et al., 2021) demonstrates subgroup- aware value factorization but inherits the limitation of fixed group cardinality. These approaches remain constrained by either domain knowledge requirements or static structural assumptions, struggling to adapt when coordination patterns evolve dynamically during task execution. Recent advances attempt to automate group formation through learned simi- larity metrics (Zang et al., 2024). However, such methods often rely on heuristic similarity measures or black-box. relational modules that lack interpretable temporal analy- sis. Recent work has also explored coordination graphs for adaptive agent relationships (Yang al., 2022; Wang et al., 2021). Our spectral clustering approach fundamen- tally differs by establishing mathematically grounded group discovery through spectral analysis of agents' state trajec- tory manifolds, enabling principled adaptation to emerging coordination needs without prior group specifications.
A dynamic spectral clustering- bbsedd grouping mecha- nism that adaptively constructs coordination structures through temporal agent state representations, enabling automated group formation and evolution in response to dynamic coordination requirements in multi-agent systems.
A novel hypergraph neural architecture that extends tra- ditional graph-based information processing to capture higher-order agent relationships, substantially improv- ing the expressiveness and efficiency of multi-agen information exchange through learnable hypergraph convolution operations.
A unified learning framework that seamlessly incor- porates the proposed hypergraph-basedt coordination mechanism into both value-based and policy-based multi-agent learning paradigms, achieving signifi- cant empirical improvements over state-of-the-art ap- proaches in complex cooperative tasks.
2. Related Work
Multi-Agent Coordination Structures Centralized Train- ing with Decentralized Execution (CTDE) (Olichoek et al., 2008) has driven significant advances in value decomposi- tion methods. While single-agent settings have explored re- cursive least-squares approaches (Song et al., 2021), MARL methods like VDN (Sunehag et al., 2017) employed linear summation of local utilities, while QMIX (Rashid et al., 2020) introduced non-linear mixing networks constrained by monotonicity. Subsequent innovations like QTRAN (Son et al., 2019) relaxed these constraints through the Individual- Global-Max principle, with extensions enhancing explo- ration (Gupta et al., 2021; Mahajan et al., 2019) and mixing capacity (Wang et al., 2020a; Zang et al., 2023). However, these methods fundamentally assume fixed agent relation- ships through static decomposition structures (e.g., sum/max operations), limiting their ability to model dynamic coordi- nation patterns requiring adaptive group formation. In par- allel, actor-critic frameworks have extended CTDE through centralized crities, as seen MADDPG (Lowe et al., 2017) and COMA (Foerster et al., 2018) which address credit assignment via counterfactual baselines. While such ap- proaches enable decentralized execution, their information processing remains restricted to pairwise interactions. Re- cent communication-augui
Hy Hypergraph Representation Learning Graph neural net- works (GNNs) (Wang & Gombolay, 2020; Wu al., 2020) have demonstrated extensive applications in various do- mains (Jia et al., 2025). and have become prevalent in MARL for modeling agent interactions through graph struc- tures (Pesce & Montana, 2023). Approaches like DGN (Jiang et al., 2018) and MAGNet (Malysheva et al., 2018) employ attention mechanisms to capture pairwise relation- ships, while dynamic variants (Liu et al., 2020; Sheng et al., 2022) learn adaptive edges through differentiable attention. However, these graph-based methods fundamentally op- erate on dyadic connections, forcing higher-order group interactions to be approximated through chains of pairwise edges- an inefficient representation that loses natural multi- agent coordination semantics. Addressing coordination complexity, research has advanced along several dimen- sions: factorization approaches through coordination graphs (Böhmer et al., 2020), regularization techniques via nested optimization (Song et al., 2020), adaptive topological struc- tures (Li et al., 2020), and representational capacity analysis across varied multi-agent domains (Castellini et al., 2021). Policy-based frameworks have incorporated attention mech- anisms to enhance selective information processing (Iqbal & Sha, 2019), yet these innovations remain constrained by their underlying pairwise representational paradigm. Even
variants (Su et al., 2021; Wan et al., 2021) demonstrate performance gains from ex- plicit information exchange, yet still operate on fixed inter-
2

---

Hypergraph Coordination with Dynamic Grouping for MARL
hierarchical communication architectures (Liu al., 2023), while enhancing structured information flow, cannot inher- ently capture the n-ary relationships fundamental to complex team coordination. Hypergraph neural networks (Feng et al., 2019), demonstrating their expressiveness in social network modeling (Yu et al., 2021) and recommendation systems (Gao et al., 2023), offer a theoretical framework capable of natively representing higher-order interactions. To our knowledge, no prior work has combined spectral cluster- ing with hypergraph convolution to dynamically construct multi-agent hyperedges based on temporal state patterns, bypassing the heuristic hyperedge definitions common in other domains.
Figure 1.
The dynamic spectral clustering module periodically pro- cesses agents' state histories rather than every timestep, identifying natural groupings based on behavioral similari- ties. These grouping results construct a hypergraph topol- ogy where vertices represent agents and hyperedges capture intra-group relationships. Within each group, a multi- layer hypergraph convolution network with multi-head attention mechanism processes information, allowing agents selec- tively focus on relevant information rather than simple aver- aging. For each agent i, its local observation and action- observation history тÚ are encoded through a recurrent neu- ral network to generate individual embeddings, which are then enhanced through the attentive hypergraph convolution layers to produce group-aware representations h4.
3. Method
A cooperative multi-agent task can be modeled as Dec-POMDP (Olichoek et al., 2016) forming the tuple SN, P, R, O, n, 7), where N = [1....,n] n) denotes the finite set of n agents. 8 E represents the true state of the environment from which each agent draws an in- dividual observation O; E Ω according to the observation function (s,, i). At each timestep, each agent selects an action a; E A; based on its action-observatio history E T = (Ω x A)", forming a joint action a E .A". This results in a transition to the next state according to the transition function P(s'|s, a): S A + A(S) and shared reward> r = R(s, a) for the team, where R the reward function and 7 E [0, is the discount factor.
In the value- based implementation, each agent's 's individual Q-value is augmented with its group-aware representation to form (T, a, h₂). These enhanced Q-values are then combined through a monotonic mixing network to compute the joint action-value Qtor- Similarly, in the policy- implementation, each agent's policy network x; takes the concatenation of local observation history T; and group- aware representation h, as input to generate action probabil- ities, while the critic network uses the enhanced joint state representation for value estimation.
- IK is
Both implementations fully adhere to the CTDE paradigm while enhancing its coordination capabilities. During cen- tralized training, we leverage global information to discover dynamic group structures through spectral clustering. As proven in Theorem 3.2, these group structures converge and stabilize during training. At execution time, the core CTDE principle is preserved-agents operate without ac- cess to global state information. The key enhancement is that agents within established groups share local obser- vations with groupmates, enabling the HGCN to generate group-aware representations that capture coordinated be- haviors discovered during training. This approach respects CTDE's fundamental requirement of avoiding global state dependency during execution, while allowing more effective coordination through structured local information exchange within stable groups
The dynamic relationships between agents modeled through hypergraph structure (Zhang et al., 2018) G = (V, Y,E,E,, W.. The vertex set V = [uI,,.., 3n represents agents, while the hyperedge set E = fei, cm captures higher-order interactions among multiple agents, where each hyperedge Eg connects a subset of agents. W E mm is diagonal matrix containing hyperedge weights WaR that indicate the strength of these relationships. Unlike tradi- tional graphs limited to pairwise relationships, hypergraphs capture complex group interactions that naturally arise in multi-agent systems. The hypergraph structure updates dy- namically through spectral clustering based on agents' state histories, enabling adaptive grouping as the environment evolves.
3.1. Overview
3.2. Dynamic Spectral Clustering for Group Formation
The proposed HYGMA framework enhances multi-agent reinforcement learning through dynamic grouping and hypergraph-basee based information processing. The core com- ponents include a dynamic spectral clustering module for adaptive group formation, a hypergraph convolution net- work with multi-head attention for intra-group information processing. The method has been implemented in both value-based and pasecy-based learning paradigms. The over- all architecture of our proposed method is illustrated in
The group formation process takes agents' state histories as input to identify natural groupings that reflect coordination patterns. Given state history matrix H, E R for n agents, where b is batch size, is trajectory length, and d is state dimension, we formalize the grouping as normalized cut minimization problem:
Neut(G) = Σ cut V.)
(I)
vol(V,)
3

---

Hypergraph Coordination with Dynamic Grouping for MARL
(T.0)
Node features
Hypergruph convolution
Agents' features
Multi-heads
MLP
Linear
ReLu
(,))
attention
Agents
Periodic grouping
Group 1
Hypergraph structure
Figure 1. Overview of the proposed hypergraph-based dynamic grouping multi-agent rein- forcement learning framework with spectral clustering and attentive infor- mation processing.
stability threshold 5
Similarity Matrix W
Hyperedge
Generation
Group update? ?
Hypergraph
group number
Hyperedge Generation
mapping
Group
concat
Cooperative Task
a,,
Agent
(o),
Mixing Network
concat +
(F,
2, a,.
Agent
h
where cut(V;, Vi) measures the sum of edge weights be- tween group Vi and its complement, and (V;) is the sum of degrees of vertices in V,. To solve this NP-hard discrete optimization problem, we adopt spectral relaxation:
where a(i) represents the mean distance between agent i and all other agents within the same group, and b(i) denotes the minimum mean distance from agent any other group. This optimization inherently captures the trade-off between intra-group similarity and inter-group distinctiveness. The dynamic nature of multi-agent interactions necessitates a group update mechanism:
min LA( s.t. A AgRexA
where D is the normalized graph Laplacian, with D being the diagonal degree matrix and W representing the similarity matrix constructed using k-nearest neighbors based on Euclidean distances between agents' state history trajectories. Formally, Wij > 0 if agent) j is among the k-nearest neighbors of agent (or vice versa), and Wiy 0 otherwise. State histories are normalized across feature dimensions to ensure consistent scaling in different envi- ronments, enabling identification of coordination patterns regardless of specific state representations. The solution A contains the A eigenvectors corresponding to the & smallest eigenvalues of L, providing provably good approximation:
G. G-=SC(RD C(H.)) if ((,)),, GL-1 otherwise
(5)
where n( measures the normalized proportion of agents changing groups, and 5 is stability threshold. This mecha- nism guarantees both adaptivity and stability:
Theorem 3.2 (Convergence). Under the dynamic update rule with threshold 8, the sequence of groupings G. con- verges in finite time with probability 1. The expected number of updates before convergence is bounded by O(1/5) Appendix A.2 for proof)
Theorem 3.1 (Clustering Approximation). The spectral clustering solution G satisfies:
To ensure computational efficiency, we employ optimization strategies including history windowing, periodic updates, and termination.
(C) < O(log k) Neul(G")
(3)
where G* the optimal grouping structure. Further- more, this approximation ratio is tight in the sense that no polynomial-time algorithm can achieve asymptotically better approximation under standard complexity assump- tions. (See Appendix A. for proof)
The quality of grouping structure directly impacts the effec- tiveness of subsequent learning. For rigorous characteri- zation of this relationship, let V* G') denote the optimal value function under grouping structure G, we have:
Theorem 3.3 (Quality Preservation). For the obtained grouping structure G, and the optimal grouping G":
The determination of optimal group number k- requires balancing the expressiveness of grouping structure with its computational efficiency. We address this through optimiz- ing the silhouette score, which measures both the cohesion within groups and the separation between groups:
(s, Go) -
logo
(6)
where y is the discount factor and a is constant. Moreover, this bound is tight when the normalized cut difference between G, and G approaches O(log (See Appendix A.3 for proof)
b(1) - a(1)
k* = argmarie (iim R
(4)
max b(i)

---

Hypergraph Coordination with Dynamic Grouping for MARL
These theoretical guarantees establish the effectiveness of the dynamic spectral clustering mechanism in both com- putational efficiency and learning quality. The resulting group structure forms the foundation for hypergraph-buie based information processing descrihed in the subsequent section.
compared to fully-connected architectures, from O(n²) to (n? (k) where k is the number of groups (see Appendix
A.4 for theoretical analysis).
3.4. Learning Objectives
To optimize HYGMA architecture, design joint learn- ing objective that combines the main task performance with group consistency and attention regularization:
3.3. Hypergraph Attention Convolution Network
Based on the grouping structure obtained from dynamic spectral clustering, we construct a hypergraph G = (V, E, W) where vertices V represent agents and hyper- edges E capture the intra-group relationships. Specifically, for each group identified in Section 3.2, we create hyper- edge connecting all agents within that group, with the edge weight in W reflecting the group cohesion measured by the silhouette score. This dynamic hypergraph construc- tion allows us to model complex, higher-order relation- ships that naturally emerge from agent interactions. Within this dynamic hypergraph structure, we employ an attention- enhanced hypergraph convolution network generate per- sonalized information embeddings for each agent. For node i layer I, the feature update follows:
Lista
Lusk A1 Egnup X2Lan
(11)
The group consistency loss Lgroup ensures effective spec- tral clustering by minimizing intra-group distances while maximizing inter-group separation:
Egroup
Σ k=
Σ CJECk
d(hs. hz)
|C
(12)
- 9 min Lik
Σ sECo.JCC
d(hi
Cil
To encourage selective information processing through the attention mechanism while avoiding trivial solutions, we employ an entropy regularization term:
11+1) h4
Ose D D-2HWB--
H D 3 h ( p!)
Lan Σ ii=10 1N L
aie log(ase)
(13)
BEEi
where Ei represents the set of hyperedges containing node and matrices H, D. and B define the hypergraph structure. The attention coefficient aie is computed through:
The hyperparameters x1 and X2 balance the importance of these auxiliary objectives against the main task learning.
3.5. Implementation in Value-based and Policy-based Frameworks
( exp(LeakyRelIU(( [W,h," (W,h?"
Oie
Edees cop(LeakyRelUU(TTTW... " ())
HYGMA framework can effectively implemented in both value-based and policy-based learning paradigms while maintaining the CTDE principle. In both implementations, maintain the components: dynamic spectral cluster- ing for group formation, hypergraph construction based on group structure, and attention-enhancel HGCN for informa- tion processing within groups.
(8) This attention mechanism enables each agent to adaptively weight information from different groups belongs to, gen- erating personalized feature representations that capture both individual characteristics and group dynamics. The processed features enhance both value and policy networks:
Qi(Ti, ai ())) = fo((T,aailh
(9)
3.5.1. VALUE-BASED IMPLEMENTATION
T: TT(a, T,, h (1)) = fr ((m.1 (D)
(10)
In the QMIX framework. we enhance individual Q-values with awoup- representations:
This integration creates an end-to-end trainable architecture where dynamic group structures adaptively influence agents' decision making through ereetion-weighter information aggregation. By combining dynamic spectral clustering with attention-basee based hypergraph convolution, HYGMA enables flexible and efficient information exchange within groups while maintaining each agent's 's ability to selectively process relevant information.
Qi ai h4) = [e((Taaa()h))
(14)
These enhanced Q-values are then combined through a monotonic mixing network:
Qiot = fmär (Q1, (n.....Qni:. Qnis)
(15)
The TD loss serves the main task objective:
This hypergraph structure not only enhances representa- tion learning but also reduces communication complexity
Lunk (r + max a Quor (8', a,) Qioe)²
(16)
5

---

Hypergraph Coordination with Dynamic Grouping for MARL
The hypergraph structure particularly enhances the value- based implementation by providing contextual information that helps individual agents understand their role within different coordination patterns. This addresses a funda- mental limitation traditional value factorization methods:
Algorithm HYGMA: Hypergraph grouping for MARL
Require: Initial parameters 0 for networks, learning rates
ag. aq group update threshold 8
Ensure: Trained policy/value networks
I: Initialize replay buffer D, hypergraph G = (V, E, W)
while they can learn joint action-values, they struggle to identify dynamic coordination relationships. By integrating CecC-eextacttd features into the Q-function. agents learn to consider both individual utility and group-level coordina- tion simultaneously, leading to more effective collaborative strategies.
2: for each episode do
3: for each timestep do
Observe current states 8; and histories f
5:
// Update group structure if necessary if ((H)),,C(H.) ô then
6:
7:
Update groups via spectral clustering Construct new hypergraph G2 end if
8:
3.5.2. POLICY-BASED IMPLEMENTATION
9:
In the actor-critic framework, both the actor and critic net- works utilize the group-aware features. The policy network generates actions based on augmented observations:
10:
Generate group-aware representations Compute attention coefficients Oie Update node features hę
11:
12:
13:
I/ Action selection and execution for each agent do
Ti(a: Fi, h.) fx ([T)
(17)
14:
The critic estimates state values incorporating group infor- mation:
15:
if Value-based then
16:
Select action via c-greedy from Qi(T,, hha) else
V(s, h) = frr((sss))
(18)
17:
18:
Sample action from (T((|Ti, hs)
The task loss combines actor and critic objectives:
19:
end if
Lusk [log T. (a./n,, A.).A.]
20:
end for
(19)
21:
Execute joint action, observe reward vy and next
+ + 4') hi)
state 8t+1
22:
Store transition in D
In policy-based methods, the hypergraph structure enhances credit assignment by creating dynamic groupings where rewards can be more efficiently distributed within relevant
23:
end for
24:
Training phase
25:
Sample mini-batch from D>
agent subsets. The multi- head attention mechanism further
26:
Compute Lras according implementation type
refines this by allowing agents to focus on different aspects of group information simultaneously.
27:
Compute Cgroup and Cant
28:
Update networks using Listal = Luusk + Ai Egroup +
The complete training procedure for both implementations is summarized in Algorithm 1, integrating dynamic group formation (lines 6-8), attentive information processing (lines 11-12), and joint optimization (lines 26-28). This unified approach ensures coordination patterns emerge naturally while maintaining stable learning dynamics.
A Lat
29:
end for
Baselines. The SMAC experiments compare against state- of-the-art value factorization methods including Ft-QMIX (Hu al., 2023), QPLEX (Wang et al., 2020a), VAST (Phan et al., 2021), MAPPO (Yu et al., 20d2)and GoMARL (Zang et al., 2024). Ft-QMIX represents a finetuned version of QMIX with enhanced win rates over the vanilla implementa- tion. VAST incorporates sub-team value factorization based on predefined group numbers, while GoMARL presents an automatic grouping mechanism for efficient coopera- tion. The comparison also includes RITT (Hu al., 2023), which integrates effective modules from multiple methods for credit assignment. For -paicy-based scenarios, the base- line methods comprise communication-orientte approaches: MAGIC (Niu et al., 2021), CommNet (Sukhbaatar et al., 2016), GA-Comm (Liu et al., 2020), 13CNet (Singh et al., 2018) and TarMAC-IC3Net (Das al., 2019).
4. Experiments
The empirical evaluation consists of experiments on both value-based and policy-based implementations. The value- based implementation is tested on StarCraft Multi- Agent Challenge (SMAC) benchmark (Vinyals et al., 2019) with three representative maps: 3s_vs_________ vs_5z, 5m_vs. vs 6m and $s5z_vs_3$se 33_2. The policy-based implementation evalu- ated on Predator- Tredator-Prey (Singh et al., 2018), Traffic junetion (Sukhbaatar et al., 2016) and Google Research Football (GRF) (Kurach et al., 2020), which introduces additional complexity through sparse rewards, stochasticity and adver- sarial agents. A comprehensive description of each environ- ment can be found in the Appendix B.
6

---

Hypergraph Coordination with Dynamic Grouping for MARL
GoMARL
Pt. Quix
Oplox
VAST
35. Vs.
5m V5 Sm
3552 vs. 3o62
Tee Win Katr 69)
Test Wit Ratt
Ralt
Stepa (-100)
Skaps (-109
Stepa 10P)
Figure 2. The test won rate for the 3s_ $a_vv______ (Left), the 5m_ vs 6m (Middle) and the 3s52_ vs_ vs_3s6 (Right).
45
HYCRSA
40-
MArIC
35
30-
3ikers
20
i5
Epochs
Epodss
(a) moderate-scee (10x10 grid, 5 agents)
(b) large-scale (20x20 grid, 10 agents)
Figure 3. Average steps per episode in Predator-Prey, -reattor-Pre..
4.1. Performance on SMAC
ment in sample efficiency and final performance. The accel- erated convergence dynamics observed across all scenarios effectively offset the per-iteration computational increase, creating a favorable efficiency- trade-off (see Appendix C for detailed analysis of parameter efficiency, computational overhead, and performance trade-offs)
Figure 2 illustrates the performance of HYGMA across diverse SMAC benchmark scenarios, demonstrating consis- tent effectiveness where baseline approaches exhibit context- dependent limitations, In the balanced engagement scenario (5m_vs_6r vs_ vs_6m), which demands precise positioning and coor- dinated focus fire, HYGMA maintains stable high win rates while baseline methods demonstrate suboptimal coordina- tion efficiency. Analysis of the asymmetric combat scenario (3s_vs_5z)) reveals that despite GoMARL ultimately achiev- ing comparable asymptotic performance, HYGMA exhibits significantly accelerated convergence dynamics. This advan- tage becomes particularly pronounced in the heterogeneous scenario (3s5z_ vs 3s6z), where baseline approaches mani- fest substantial performance variance and limited win rates, contrasting with the stable and superior performance of HYGMA. The consistent effectiveness across these varying coordination challenges validates the dynamic hypergraph structure's capacity to facilitate diverse forms of agent co- operation. Notably, while HYGMA introduces additional parameters through the HGCN module, it maintains the same mixing network architecture Ft-QMIX, demonstrat- ing that performance improvements stem primarily from our novel hypergraph-based information processing rather than simply scaling up conventional network capacity. This architectural choice does introduce approximately 36% com- putational overhead in training time compared to baseline methods, but this cost is justified by the significant improve-
4.2. Performance on Predator-Prey
The Predator- Prey environment presents coordination chal- lenges at different scales through pursuit task with negative step penalties. The evaluation considers both moderate-scale coordination (5 predators, 10x10 grid) and large-scale co- ordination (10 predators, 20x20 grid). where agents must balance exploration and coordinated capture strategies.
Figure 3 reveal the scalability advantages of the dynamic hypergraph structure. In the moderate-scale scenario, the method demonstrates rapid policy convergence and stable performance, outperforming the state-of -hrtt--artttt baseline MAGIC in both convergence speed and final performance. The performance distinction becomes more pronounced in meth-
the large-scale scenario, where communication ods like CommNet and I3CNet exhibit substantial coordi- nation degradation. This contrast particularly highlights the limitations of fixed communication architectures in scaling to larger agent populations. The proposed method main- tains consistent coordination efficiency across both scenar- ios through adaptive group formation, enabling effective information flow while avoiding communication overhead.

---

Hypergraph Coordination with Dynamic Grouping for MARL
4.3. Performance on Traffic Junction
Table 2. Success rate and average steps taken in GRF
The Traffic Junction environment evaluates coordination mechanisms through traffic control scenarios of increasing complexity. The evaluation encompasses both a basic coor- dination setting with sparse traffic flow and a more challeng- ing scenario featuring higher traffic density and increased spatial complexity. The success criterion requires complete collision avoidance throughout episodes, demanding consis- tent coordination among all active agents.
METHOD
SUCCESS RATE
STEPS TAKEN
HYGMA
97.7. 0.7%
30.2611
0.24
MAGIC
98.2.1 1.0%
34.30.1 1.34
COMMNET
59.2 13.7%
39.321 2.35
IC3NET
70.0 9.8%
40,37 1.22
TARMAC-IC3NET
73.5 8.3%
41,53 2.80
GA-COME
88.8 3.9%
39.05 3.05
Table 1. Success rate and convergence steps in Traffic Junction.
IC3Net, TarMAC-IC3Net) show limited ability to develop sophisticated offensive strategies. The performance dispar- ity particularly manifests in the stability of learned policies, where the proposed approach maintains consistent behavior across evaluation episodes. This stability in the presence of environmental stochasticity suggests effective informa- tion aggregation through the dynamic hypergraph structure, enabling robust coordination in the face of uncertain state transitions and opponent behaviors.
x 7,
x 14.
METHOD
Nmax 5,
Nmax 10,
parrioe 0.3
parrioe 0.2
HYGMA
99.7 1. 0.1% (272 1 41)
99.2 1. 0.1% (569 34)
MAGIC
99,9 0.1% (440 + 64)
99.9 + 0.1% (819 + 85)
COMMNET
99.3 0.6% (585 + 73)
97.2 0.3% (3657 + 480)
IC3NET
97.8 1: 1.0% (611.1 101)
96.0 0.7% (1604 1: 109)
TARMAC-IC3NE ICNNET
84.8 + 4.5% (599 + 187)
95.5 + 1.3% (1706 + 104)
GA-COMM
95.9 + 0.1% (891 + 141)
97.1 + 0.7% (1573 = 253)
Table 1 reveals compelling trade-off between asymptotic performance and learning efficiency. Although MAGIC achieves marginally higher final success rates, HYGMA demonstrates substantially enhanced sample efficiency across both scenarios, with convergence (defined as first reaching 90% of final performance sustained for consecu- tive epochs) occurring significantly earlier. Rapid conver- gence characteristies of the hypergraph structure, which enables efficient discov- ery of critical coordination patterns. Notably, the method maintains high success rates comparable to stte-off-the-ar approaches while requiring only a fraction of the training samples, demonstrating the effectiveness of dynamic group coordination in accelerating policy learning.
O cup Erclution Tindine
0.44
6.2
be attributed to the adaptive nature
Numna leed Time Shoss (166 stote interva)
Node Coocoamence Nalte
Geooour Privad
100
36
38
4.4. Performance on Google Research Football
Nede I
The Google Research Football (GRF) environment intro- duces additional complexity through the combination of sparse rewards, high-dimensional action spaces, and ad- versarial elements. The evaluation scenario requires three attacking agents to coordinate against adaptive defensive opponents, presenting challenges in both strategic planning and tactical execution. The environment's 's inherent stochas- ticity and delayed reward signals pose particular challenges for consistent policy learning.
Figure 4, Group analysis in 5m_vs _m__._66..
Grouping with OCN
group
Pi-Qmix
Text Rate
Table 2 reveal key characteristics of different coordination approaches in complex domains. The proposed HYGMA and MAGIC establish comparable success rates at the up- per performance boundary, yet exhibit distinct operational characteristics. While communication-centio approaches like GA-Comm demonstrate moderate effectiveness, meth- ods relying on fixed communication structures (CommNet,
Steps (=109)
Figure 5. Ablation studies in 5m vs 6m.
8

---

Hypergraph Coordination with Dynamic Grouping for MARL
4.5. Analysis
totic performance compared state-of-the-art approaches. The emergence of interpretable group structures through spectral clustering provides insights into learned coordina- tion strategies. Theoretical analysis establishes guarantees on the grouping mechanism's 's quality and computational efficiency. Future work explore extensions to overlapping group structures through soft clustering techniques, further optimizations for very large agent populations, and deeper theoretical connections between spectral clustering and in- formation bottleneck principles in representation learning.
Analysis of the learned coordination patterns provides in- sights into the underlying mechanisms driving performance improvements. Taking the 5m_vs_ _on_vs__mm__ 6m scenario as repre- sentative case, Figure 4 reveals the emergence of structured coordination through temporal group evolution. The co- occurrence analysis indicates three distinct coordination pat- terns: a core tactical unit (Agents 0.1.2) maintaining high coordination frequency, a flexible support unit (Agent 3) adapting its grouping based on tactical situations, and a spe- cialized independent unit (Agent 4) operating with strategic autonomy. The convergence of this organizational struc- ture aligns with the stabilization of performance metrics, indicating the discovery of effective tactical roles.
A Acknowledgement
This work was substantially supported by the National Nat- ural Science Foundation of China under Grants 62273026.
Ablation studies presented in Figure 5 isolate three critical architectural components: our full method with dynamic hypergraph structure (HYGMA), variant replacing HGCN with standard GCN while maintaining dynamic grouping (Grouping with GCN), and fixed single-group variant (all- in-one group). The performance differentials demonstrate that improvements stem primarily from the hypergraph structure rather than merely increased information avail- ability. While the GCN variant outperforms the exed-group baseline, it exhibits significant performance degradation compared to proposed method, particularly in asymptotic performance. This confirms the superior representational capacity of hypergraphs for modeling higher-order agent relationships. Furthermore, the single-group variant's 's per- formance plateau illustrates how static information sharing structures, despite access to equivalent information, fun- damentally limit coordination complexity. These results validate that the dynamic hypergraph topology provides es- sential structural inductive bias for discovering sophisticated coordination strategies, serving as a key mechanism in bal- ancing the exploration-expllottaion trade-off in coordination learning.
Impact Statement
This work advances multi-agent reinforcement learning through more efficient coordination mechanisms. Beyond the general implications of advancing machine learning, our method's 's improved sample efficiency and interpretable group structures could benefit real-worle applications like traffic management and robotic coordination, potentially reducing computational resources and energy consumption. However, as with any advancement in multi-agent systems, considerations should be given to ensuring responsible de- ployment in sensitive applications. We release our imple- mentation to promote transparent and equitable access to this technology.
References
Böhmer, W., Kurin, V., and Whiteson, S. Deep coordina- tion graphs. In International Conference on Machine PMLR, 2020.
Learning, pp.
Castellini, J., Olichock, A., Savani, R., and Whiteson, S. Analysing factorizations of action-value networks for cooperative multi-agent reinforcement learning. Au- tonomous Agents and Multi-Agent Systems, 35(2):25, 2021.
5. Conclusion
This paper presents HYGMA, novel framework that inte- grates dynamic spectral clustering with hypergraph neural networks for addressing coordination challenges in multi- agent reinforcement learning. The framework makes three key technical contributions: First, an adaptive grouping mechanism leveraging spectral analysis discover coordi- nation patterns. Second, an attention-enhance hypergraph architecture capturing higher-ordes relationships while main- taining computational efficiency. Third, a unified objective combining task performance with structural regularization for both value-based and policy-basee learning paradigms.
Charbonnier, F., Peng, B.. Vienne, J., Stai, E.,, Morstyn, T., and McCulloch, M. Centralised rehearsal of decentralised cooperation: Multi-agent reinforcement learning for the scalable coordination of residential energy flexibility. Ap- plied Energy, 177:124406, 2025.
Das, A., Gervet, T., Romoff, J., Batra, D., Parikh, D., Rab- bat, M., and Pineau, J. Tarmac: Targeted multi-agent communication. In International Conference on machine learning. pp. 1538-15400 1546. PMLR, 2019.
Experimental results across diverse domains demonstrate significant improvements in sample efficiency and asymp-
Feng, Y., You, H., Zhang, Z., Ji, R., and Gao, Y. Hypergraph neural networks. In Proceedings of the AAAI confer-
9

---

Hypergraph Coordination with Dynamic Grouping for MARL
ence on artificial intelligence, volume 33, pp. 3558-3565, 2019.
Kurach, K., Raichuk, A., Stańczyk, P., Zajac, M., Bachem, O., Espeholt, L.,, Riquelme, C., Vincent, D., Michalski, M., Bousquet, O., et al. Google research football: A novel reinforcement learning enviromment. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 4501-4510, 2020.
Foerster, J., Farquhar, G., Afouras, T., Nardelli, N., and Whiteson, S. Counterfactual multi-agent policy gradi- ents. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Lee, Y., Yang, J., and Lim, J. Learning to coordinate ma- nipulation skills via skill behavior diversification. In In- ternational conference on learning representations, 2019.
Gao, C., Zheng, Y., L., N., Li, Y. Qin, Y., Piao. J., Quan, Y., Chang, J., Jin, D., He, X., al. A survey of graph neural networks for recommender systems: Challenges. meth- ods, and directions. ACM Transactions on Recommender Systems, 1(1):1-51, 2023.
Lhaksmana, K. M., Murakami, Y., and Ishida, T. Role-based modeling for designing agent behavior in self-organizing multi-agent systems. International Journal of Software Engineering and Knowledge Engineering, 28(01):79-995 2018.
Gupta, T., Mahajan, A., Peng, B., Böhmer, W., and White- son, S. Uneven: Universal value exploration for multi- agent reinforcement learning. In International Confer- on Machine Learning, pp. 1930-3941, PMLR, 2021.
Li, L.,, Li, D., Song, T., and Xu, X. Actor-critic learning control with regularization and feature selection in pol- icy gradient estimation. IEEE Transactions on Neural Networks and Learning Systems, 32(3):1217-12277, 2021.
Heess, N., Tb, D., Sriram, S., Lemmon, J., Merel, J., Wayne, G., Tassa, Y., Erez, T., Wang. Z., Eslami, S., et al. Emer- gence of locomotion behaviours in rich environments. arXiv preprint arXiv: 1707.0228000 2017.
Li, S., Gupta, J. K., Morales, P., Allen, R., and Kochenderfer, M. Deep implicit coordination graphs for multi-agent reinforcement learning, arXiv preprint arXiv:2006.1 11438, 2020.
Hu, J., Jiang, S., Harding, S. A., Wu, H., and wei Liao, S. Rethinking the implementation tricks and monotonic- ity constraint in cooperative multi-agent reinforcement learning, 2023.
Liu, Y., Wang, W., Hu, Y., Hao, J., Chen, X., and Gao, Y. Multi-agent game abstraction via graph attention neu- ral network. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 7211-7218, 2020.
Huang, A., Wang, Y., Liu, R., Zou, H., and Zhou, X. Qvf: Incorporating quantile value function factorization into cooperative multi-agent reinforcement learning. Pottern Recognition, pp. 111323, 2025.
Liu, Z., Wan, L., Sui, X., Chen, Z., Sun, K., and Lan, X. Deep hierarchical communication graph in multi-agent reinforcement learning. In IJCAI, pp. 208-216, 2023.
Iqbal, S. and Sha, F. reinforcement learning. In International conference machine learming, pp. 2961-2970. 20L.229......R.... 2019.
for multi-agent
Lowe, R., Wu, Y. I., Tamar, A., Harb, J., Pieter Abbeel, O., and Mordatch, I. Multi-agent actor-critic for mixed cooperative-comptttii environments. Advances in neu- ral information processing systems, 30, 2017.
Iqbal, S., Costales, R., and Sha, F. Alma: Hierarchical learning for composite multi-agent tasks. Advances in Neural Information Processing Systems, 35:7155-7166, 2022.
Macarthur, K., Stranders, R., Ramchurn, S., and Jennings, N. A distributed anytime algorithm for dynamic task allocation in multi-agent systems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 25, pp. 701-706, 2011.
Jia, M., Yao, Y., and Liu, Y. Review graph neural net- works for process soft sensor development, fault diagno- sis, and process monitoring. Industrial & Engineering Chemistry Research, (4(117)8543-855 -5644, 2025.
Mahajan, A., Rashid, T., Samvelyan, M., and Whiteson, S. Maven: Multi-agent variational exploration. Advances in neural information processing systems, 32, 2019.
Jiang, J., Dun, C., Huang, T., and Lu, Z. Graph convolutional reinforcement learning. arXiv preprint arXiv:1810.09200 2018
Malysheva, A., Sung, T. T.,, Sohn, C.-B., Kudenko, D., and Shpilman, A. Deep multi-agent reinforcement learning with relevance graphs. arXiv preprint 11Xiv:1811.12557, 2018.
Kim, S., Lee, S. Y., Gao, Y., Antelmi, A., Polato, M., and Shin, K. A survey on hypergraph neural networks: An in-depth and step-by-step guide. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp.
Niu, Y., Paleja, R. R., and Gombolay, M. C. Multi-agent graph-attention communication and teaming. In AAMAS, volume 21, pp. 20th, 2021.
2024.
10

---

Hypergraph Coordination with Dynamic Grouping for MARL
Oliehock, F. A., Spaan, M. T., and Vlassis, N. Optimal and approximate q-value functions for decentralized pomdps. Journal of Artificial Intelligence Research, 32:289-353, 2008.
Su, J., Adams, S., and Beling, P. -aloe-decomposittonn multi- agent actor-crities. In Proceedings of the AAAI conference artificial intelligence, volume 35, pp. 11352-11360, 2021.
Olichock, F. A., Amato, C., et al. A concise introduction to decentralized POMDPs, volume 1. Springer, 2016.
Sukhbaatar, S., Fergus, R., et al. Learning multiagent com- munication with backpropagation. Advances in neural information processing systems, 29, 2016.
Pesce, E. and Montana, G. Learning multi-agent coordi- nation through connectivity-driver communication. Ma- chine Learning, 1 112())483-554, 2023.
Sunehag, P., Lever, G., Gruslys, A., Czarnecki, W. M., Zam- baldi, V., Jaderberg, M., Lanctot, M., Sonnerat, N., Leibo, J. Z., Tuyls, K., et al. Value-decomposition networks for cooperative multi-agent learning. arXiv preprint arXiv:1706.05222 2017.
Phan, T., Ritz, F., Belzner, L.,, Altmann, P., Gabor, T., and Linnhoff-Popies Popien, C. Vast: Value function factorization with variable agent sub-teams. Advances in Neural Infor- mation Processing Systems, 01124418-240033 2021.
Tan, M. Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proceedings of the tenth inter- national conference machine learning, pp. 330-337, 1993.
Rashid, T., Samvelyan, M., De Witt, C. S., Farquhar, G., Foerster, J., and Whiteson, S. Monotonic value function factorisation for deep multi-agent reinforcement learning. Journal of Machine Learning Research, 21(178):1-51, 2020.
Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M.. Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. nature, 575 (7782):350-2 355-344, 2019.
Russell, S. J. and Zimdars, A. Q-decomposition for rein- forcement learning agents. In Proceedings of the 20th international conference on machine learning (ICML-03), pp. 656-663, 2003.
Sheng. J., Wang, X., Jin, B., Yan, J., Li, W., Chang, T.-H., Wang. J., and Zha, Learning structured communica- tion for multi-agent reinforcement learning. Autonomous Agents and Multi-Agent Systems, 36(2):50, (ys))5,,36(2):50, 2022.
Wan, L., Liu, Z., Chen, X., Wang. H., and Lan, X. Greedy- bbased value representation for optimal coordina- tion in multi- reinforcement learning. arXiv preprint arXiv:2 12.04444, 2021.
Shu, T. and Tian, Y. M'rl: Mind-aware multi-agent management reinforcement learning. arXiv preprint arXiv:1810.00147, 2018
Wang. J., Ren, Z., Liu, T., Yu, Y., and Zhang, C. Qplex: Duplex dueling multi-agent g-learning. arXiv preprint arXiv:2008.0100 01062, 2020a.
Si, X., Song, Y., Sun, X., Wang, W., and Qin, Z. Marlfuzz: industrial control protocols fuzzing based on multi-agent reinforcement learning. Computing, 107(2):1-26, 2025.
Wang, T., Dong, H., Lesser, V., and Zhang, C. Roma: Multi- agent reinforcement learning with emergent roles. arXiv preprint arXiv:2003.08033 2020b.
Singh, A., Jain, T., and Sukhbaatar, S. Learning when to communicate scale in multiagent cooperative and com- petitive tasks. arXiv preprint
Wang. I., Gupta, T., MaMajan,, A., Peng, B., Whiteson, S., and Zhang, C. Rode: Learning roles to decompose multi- agent tasks. arXiv preprint arXiv:2010.01522.
2018.
2020c. 2020c.
Son, K., Kim, D., Kang, W. J., Hostallero, D. E., and Yi,
Y. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In Inter- national conference on machine learning, pp. 5887-5896. PMLR, 2019.
Wang, T., Zeng, I.,, Dong, W., Yang, Q., Yu, Y., and Zhang, C. Context-aware sparse deep coordination graphs. arXiv preprint arXiv:2106.02880 2021.
Wang. Z. and Gombolay, M. Learning scheduling poli- cies for multi-robot coordination with graph attention networks. IEEE Robotics and Automation Letters, 5(3): 4509 2020.
Song. T., Li, D., Jin, Q., and Hirasawa, Sparse proximal reinforcement learning via nested optimization. IEEE Transactions on Systems, Man, and Cybernetics: Systems, (111))4420-43333 2020.
Song. T., Li, D., Yang, W., and Hirasawa, K. Recursive least gqastesquares temporal difference with gradient correc- tion. IEEE Transactions on Cybernetics, 51(8):2251- 4264, 2021.
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Philip, S. Y. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning sys- tems, 3241):4224, 2020.

---

Hypergraph Coordination with Dynamic Grouping for MARL
Yang, Q. Dong, W., Ren, Z., Wang, J., Wang. T., and Zhang, C. Self-organized polynomial-time coordination graphs. In International Conference Machine Learning, pp. 24963-24979, PMLR, 2022.
Yu, C., Velu, A., Vinitsky, E., Gao, J., Wang, Y., Bayen, A., and Wu, Y. The surprising effectiveness of ppo in cooper- ative multi-agent games. Advances in neural information processing systems, 35:24611 1-24224, 2022.
Yu, J., Yin, H., Li, Wang, Q., Hung, N. Q. V., and Zhang, X. Self-supervised multi-channel hypergraph convolutional network for social recommendation. In Proceedings of the Web Conference 2021, WWW '21, pp. 413-424, New York, NY, USA, 2021. Association for Computing Machinery.
Zang, Y., He, J., Li, K., Fu, H., Q., and Xing. J. Sequen- tial cooperative multi-agent reinforcement learning. In Proceedings of the 2023 International Conference on Au- tonomous Agents and Multiagent Systems, pp. 2023.
Zang, Y., J., Li, K., Fu, H., Fu, Q. Xing, J., and Cheng, J. Automatic grouping for efficient cooperative multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
Zhang, T., Xu, H., Wang, X., Wu, Y., Keutzer, K., Gon- zalez, J. E., and Tian, Y. Multi-agent collaboration via reward attribution decomposition. arXiv preprint arXiv:2010.08531, 2020.
Zhang, Z. Lin, H., Gao, Y., and BNRist, K. Dynamic hypergraph structure learning. In IJCAI, pp. 3162-3169, 2018.
12

---

Hypergraph Coordination with Dynamic Grouping for MARL
A. Theoretical Proofs
A.1. Proof of Clustering Approximation Theorem
Theorem A.1 (Clustering Approximation). The spectral clustering solution G obtained from the dynamic optimization satisfies:
Neut(G) O(log k) Neut((G))
(20)
where G is the optimal grouping structure.
The proof consists of three key steps:
Lemma A.2 Prlscrete-Continucd Relation).
The normalized cut minimization can be formulated as:
min Tr(X' s.t. x
(21)
where C DD-2/ is the normalized Laplacian.
Proof. For any k-way partition (Vi,.., Val:
cut(V, Vi) vol(Vi)
Neul(G)
(22)
i=1
xf Laz
(23)
x DIi
LX)
(24)
where x; is the indicator vector for partition V.
LI
Lemma A.3 (Spectral Relaxation Bound). The spectral relaxation provides bounded approximation:
x²(
(GG) S 22)((E)
(25)
2
where (L) is the second smallest eigenvalue of the normalized Laplacian.
Proof. By the Courant-Fischer theorem, the second eigenvalue of L satisfies:
A2(L) = min y" Ly 4ID'/11 y"
Applying the co-area formula and Cheeger's is rounding argument (Cheeger's Inequality), obtain the conductance bound:
(GG) (2)
The lower bound (2 < (GG) follows from the variational characterization of X2.
Lemma A.4 (Dynamic Grouping Bound). For our dynamic k-way clustering:
Neutx(G) < Ollo k)0² (G)
(V,)
(26)
5=1
where (G) (G) the optimal conductance.
13

---

Hypergraph Coordination with Dynamic Grouping for MARL
Proof. Through recursive analysis:
cut(V, Vi)
Neulg (G)
(27)
vol(V;)
Bog k1
2
2x(G;)
vol(V;)
(28)
j=1
$ 2 log k (G)
Σ vol(V))
(29)
/=1
where G; represents subgraphs at recursion level i.
Combining lemmas, we obtain:
GC) S Ollog k)d (G)
Σ col(V))
(30)
j=1
< O(log k). Neul(G")
(31)
This establishes our main approximation bound. The optimality of this ratio follows from reduction the Balanced Separator problem, details of which we omit as they are standard in the literature.
A.2. Proof of Convergence Theorem
Theorem A.5 (Convergence). Under the dynamic update rule with threshold 8, the sequence of groupings (Gi) converges in finite time with probability I. The expected number of updates before convergence is bounded by (11/8).
Lemma A.6 (Potential Function Properties). Define the potential function as:
V(G.) E
Σ gEG. f.j
8,113
(32)
This function satisfies:
1. Non-negativity; V(G.) 2 0
2. Boundedness: V(G)) & M n max,, ||s: s3l1?
Lemma A.7 (Potential Descent). For any timestep where G), C(H,)) > 8:
V(G+1)
Σ
||s 8311²
Σ
||8:
85113
(33)
iES. (E
(Ea
<oooV(G))
(34)
where Se is the set of agents that change groups, and 0 is constant determined by the clustering algorithm.
Proof. Consider the change in potential for each agent i Sp:
AV = Σ ||s 83 2
Σ
|18: - s,1
(35)
jEgc 1(8)
(Eg(())
< <-al|s | 21 2|?
(36)
where (o.(0) is the centroid of group (()... Summing over all changed agents and using |S,] 2 8n gives the result.
14

---

Hypergraph Coordination with Dynamic Grouping for MARL
The convergence then follows from the supermartingale convergence theorem:
Proof of Main Theorem. 1) The sequence (V(G.)) forms supermartingale:
(37)
2) Let 7 be the number of updates. For any / T:
- - a5E[NN]
(38)
where N₂ the number of updates up time
3) Therefore:
V(Go) O(1/8)
E[T S
(39)
ad
A.3. Proof of Quality Preservation Theorem
We establish that the quality of obtained grouping structures provides theoretical guarantees for the subsequent learning process, regardless of the specific learning framework used.
Lemma A.8 (Value Function Decomposition). For any grouping structure G, the value function can decomposed as:
V*(s Σ (s,) + +(G)
(40)
SEG
where Vi is the group-wise value function, and AG) represents the inter-group value term.
Proof. Consider the Bellman equation:
Gs, max{ t.B. (V' G)]}
(41)
max {
Ry($g, ag) + Rinter (s, a) (V G)]}
(42)
DEG
The inter-gron enter-group reward term Rinter (s, a) is bounded by the normalized cut:
Rinter (8, a)l S (Neul(G)
(43)
for some constant 3, as the normalized cut directly measures the strength of inter-group connections.
Lemma A.9 (Value Function Bound). For any grouping structures G1 and Gz:
G1 - G2)1 I-
7 A \(Ncut(Gs) Noul(
(44)
where X = 8(1 + 7).
15

---

Hypergraph Coordination with Dynamic Grouping for MARL
Proof. Let oī and uं be the optimal policies under G1 and G2 respectively. Then:
(* - (s, G2) = max E.
y (Re + R
(45)
max Exg
(Be + Renter, (G2)))
(46)
max E
Rinter, (Gi) Rinter, / (G2)
(47)
S 8 7 Ne)t(()) - Nout(G2)l
(48)
t=
8
Neul(Gi) Nc)l
(49)
The inequality follows from the triangle inequality and the bound on inter-group rewards.
Theorem A.10 (Quality Preservation). For the obtained grouping structure G2 and optimal grouping G*:
(s, - G.)l S 7/ log k
(50)
where 8
[I-7)T
Proof. From the Clustering Approximation Theorem:
[N.ut(G.) Neut(G S clog k
(51)
for some constant c. Combining with the Value Function Bound:
Y A|Ncut(Ge) - (Ct)
- V (s, G.)l
(52)
1-7
7/3
(1 7)3 clog k
(53)
aa log k
(54)
where a
Bc (1-9)=
Theorem A.11 (Tightness). The bound O(y log k) is right.
Proof. Consider an MDP with the following structure:
1. States directly correspond to group assignments
2. Rewards reflect the normalized cut values: r(s) = -
3. Transitions maintain group structure with probability
In this construction:
(*(xx = -NNcl( Σn
Netu(
(55)
1 1-
1=0
V*(s,G)) = (Ce)(GG)
(56)
Given that (G:) - GC Olog k) from the Clustering Approximation Theorem's tightness result, we have:
(v' (s, G.)l O log k)
(57)
16

---

Hypergraph Coordination with Dynamic Grouping for MARL
A.4. Communication Complexity Analysis
We analyze the communication efficiency of hypergraph structures in multi-agent systems, demonstrating that dynamic spectral clustering significantly reduces communication overhead compared to traditional fully-connected communication architectures.
Theorem A.12 (Communication Efficiency of Hypergraph Structures). For a system with n agents partitioned into l groups through dynamic spectral clustering, communicution complexity satisfies:
- n1²
Chyper (Gt) O O(n²)
(58)
h
where Chyper (Gt) represents the number of messages required for one complete information exchange in the hypergraph structure Gt-
Furthermore, this communication complexity is bounded by the normalized cut:
Ciyyper (G.) p Ncud(G.)) S O(log)) Neut(G*))
(59)
where p is problem-deepenent constant, and G is the optimal grouping structure.
Proof. In fully-connected communication architecture, each agent communicates with all other (n 1) agents, resulting in n(n - 1) = (n²)) total messages.
With hypergraph-baseee baase communication, assuming & groups with approximately n/k agents per group on average, each agent only communicates with other agents in the same group. This requires approximately Σgec, lgl ((g) - 1) - ( (n2 /k) total messages, where [g| represents the size of group g.
The relationship with normalized cut follows from analyzing the communication cost relative group structures. Let vol represent the volume of group g and cul(g, 9) represent the cut between group and its complement, By definition of normalized cut:
cut(g. 9) vol(g)
Ncut(G::= =
(60)
9EG,
For groups formed through spectral clustering, we can establish that:
cut(g.
lgl (1g1 1) < 2 . (1+
(61)
vol(g)
gEG,
gEG,
9EG,
The first inequality follows from [gl - lgl. and the second inequality reflects the relationship between grrra communication and the normalized cut, where better groupings (lower normalized cut) lead more efficient communication structures. Here, is problem-dependent constant that captures this relationship.
Therefore:
Chyper (hi) pp-n- 11+NNe Neul(G.))
(62)
Substituting the bound from Theorem which establishes Neut(G.) < Ollo N)) we obtain the final complexity bound:
Chyper (Gt) p.n. n- (1+ O k:) Ncut(G*))
(63)
This demonstrates that our hypergraph communication structure achieves significantly improved efficiency while maintaining the theoretical guarantees on grouping quality.
17

---

Hypergraph Coordination with Dynamic Grouping for MARL
B. Experimental Details and Environment Configurations
B.1. Detailed Information about SMAC Tasks
In each SMAC micromanagement problem, a group of units controlled by decentralized agents cooperates to defeat the enemy team controlled by built-in heuristics. Each agent's partial observation comprises the attributes (such as health, location unit unit_type) of all units shown up in its view range. The global state information includes all agents' positions and hea 1 th,, and allied units' last actions and cool down, which is only available to agents during centralized training.
The agents' discrete action space consists of attack [enemy_ id], move [direction], stop, and no-op for the dead agents only. A particular unit, Medivac, has no action attack [enemy_ide but has action heal [enemy_ie Agents can only attack enemies within their shooting range. Proper micromanagement requires agents to maximize the damage the enemies and take as little damage as possible in combat, so they need cooperate with each other or even sacrifice themselves.
Based on the performance of baseline algorithms, the tasks in SMAC are broadly grouped into three categories: Easy, Hard, and Super Hurd. The key to winning some Hard Super Hard battles is mastering specific micro techniques, such as focusing fire, kiting, avoiding overkill, et cetera. The battles can be symmetric or asymmetric, and the group of agents can be homogeneous or heterogeneous. Here we provide detailed characteristics of the scenarios used our experiments:
3s vs 5z is a Hard asymmetric battle between three Stalkers and five Zealots. The allied Stalkers must master the kiting technique and disperse in the area to kill the Zealots that chase them after another. This map faces the delayed reward problem; however, it is not very strict about micro-cooperation between agents because of agents' scattering.
5m vs 6m presents a Hard asymmetric engagement requiring precise tactical coordination. The allied agents must learn to focus fire without overkill and position themselves with considerable precision to overcome the enemy team's s numerical advantage. The relatively confined map space compared to 3s_vs__ s__vs__5o 5z increases the importance of proper
positioning and target selection.
3s57_vs _ represents Super Hard heterogeneous battle that requires breaking the bottleneck of exploration. Three Stalkers and five Zealots must battle against three enemy Stalkers and six enemy Zealots. The complexity arises from managing two unit types with distinet capabilities Stalkers excel at ranged combat while Zealots are melee specialists, This map requires sophisticated tactical coordination, where Zealots engage in close combat while Stalkers provide ranged support, making it one of the most challenging tasks in SMAC.
B.2. Detailed Information about Predator-Prey Environment
The Predator-Prey environment evaluates coordination capability through multi-agent pursuit tasks with different scales and complexity levels. At each time step, each predator receives local observation within its limited vision range and incurs a penalty of -0.05 until the prey is captured. This negative reward structure creates pressure for efficient coordination while the partial observability necessitates information sharing among agents.
Two configuration settings are examined to evaluate scalability and coordination effectiveness:
Moderate Scale (10x10 grid, 5 predators): A baseline setting testing fundamental coordination capabilities. Predators must balance between exploration and coordinated capture, as premature engagement without proper positioning often leads prey escape.
Large Scale (20x20 grid, 10 predators): A significantly more challenging setting that stresses both coordination and exploration efficiency. The enlarged state space and increased agent number create substantial challenges for conventional communication protocols, making it an effective test for scalable coordination mechanisms.
B.3. Detailed Information about Traffic Junction Environment
The Traffic Junction environment examines multi-agent coordination in dynamic traffic scenarios where cars must navigate through intersections without collisions. The environment features stochastic agent arrivals and requires consistent coordination among varying numbers of active agents. Two scenarios with increasing complexity are investigated:
18

---

Hypergraph Coordination with Dynamic Grouping for MARL
Basic Setting: A 7x7 grid environment accommodating up to cars (N_max 5) with arrival rate of 0.3 (p_arrive 0. Cars enter from designated points with random route assignments and must coordinate their movements to reach their destinations without collision. This setting tests fundamental coordination capabilities in controlled scale.
Complex Setting: A 14x14 grid environment supporting up to 10 simultaneous cars (N_max 10) with a reduced arrival rate of 0.2 (p_arrive = 2) The expanded space and increased agent number create more complex traffic patterns requiring sophisticated coordination strategies. The lower arrival rate maintains manageable density while extending average interaction durations.
Each car observes a 5x5 local region centered on its current position and must choose between gas and brake actions at each timestep. Episodes terminate upon collision or successful traversal of all spawned cars, with success measured by completing episodes without any collisions.
B.4. Detailed Information about Google Research Football
The Google Research Football (GRF) environment presents a challenging mixed cooperative-comppttiiee scenario featuring three attacking agents coordinating against built-in AI defenders. The environment is characterized by:
Action Space: Each agent selects from 19 discrete actions including directional movements (8 directions), ball control actions (e-g., dribbling, short pass, long pass, shot), and special actions (e.g., sliding, sprint). This rich action space enables diverse tactical possibilities while increasing coordination complexity.
Observation Space:
Agents receive local observations including relative positions and states of nearby players, ball position and velocity, and game mode indicators. The partial observability and dynamic state transitions create substantial uncertainty in decision -aaiiin.
Reward Structure: sparse reward signal (+1 for scoring) combined with potential early termination (ball out of bounds, possession change) creates challenging credit assignment problem. This structure necessitates effective exploration and coordination to discover successful offensive strategies.
The game engine's built-in AI provides adaptive defensive behaviors, requiring attacking agents to develop robust and coordinated strategies. The inherent stochasticity in both state transitions and opponent behavior creates a particularly challenging environment for multi-agent coordination mechanisms.
B.5. Hyperparameters and Implementation Details
To ensure reproducibility of our experimental results, we provide the hyperparameter settings used in our experiments different environments. Tables 3, and detail the key hyperparameters for SMAC, Predator-Prey, and Traffic Junction/GRF environments respectively.
Table 3. Hyperparameters for SMAC environments
Parameter
3s_vs_ _z_
5m vs_ 6m
3s5x_vs sstk_vs__33_ js_366
Batch size
128
128
128
Buffer size
5000
5000
5000
Double Q
True
True
True
Epsilon anneal time
100000
100000
100000
HGCN hidden dim
48
64
196
HGCN out dim
36
48
128
HGCN num layers
2
2
Min/Max clusters
2/4
2/3
2/3
Clustering interval
100000
100000
100000
Stability threshold
0.6
0.6
0.6
X
0.001
0.001
0.001
Aa
0.01
0.01
0.01
19

---

Hypergraph Coordination with Dynamic Grouping for MARL
Table Hyperparameters for Predator- environments
Parameter
Moderate-scale
Large-scale
Learning rate
0.001
0.0003
Batch size
500
500
Grid size
10x 10
20x20
Number of agents
5
10
Max steps
40
80
HGCN hidden dim
96
96
HGCN out dim
64
64
HGCN num layers
1
Min/Max clusters
2/4
2/5
Clustering interval
100
100
Stability threshold
0.8
0.8
Group consistency coeff
0.1
0.1
Attention reg coeff
0.01
0.01
Table 5. Hyperparameters for Traffic Junction and GRF environments
Parameter
TJ-7x7
TJ-14x14 14
GRF
Learning rate
0.001
0.001
0.001
Batch size
500
500
500
Number of agents
5
10
Max steps
20
40
80
HGCN hidden dim
96
128
128
HGCN out dim
64
96
96
HGCN num layers
2
Min/Max clusters
2/4
2/5
Clustering interval
100
100
100
Stability threshold
0.8
0.8
0.8
Group consistency coeff
0.1
0.1
0.1
Attention reg coeff
0.01
0.01
0.01
C. Parameter Size and Performance Analysis
C.1. Parameter Efficiency Analysis
Table 6 provides detailed comparison of parameter sizes across different mixing network architectures. We focus specifically on mixing network parameters as they represent the core architectural difference between QMIX-based methods and directly impact centralized training efficiency in MARL algorithms. While our method incorporates additional HGCN components (analyzed separately in Section C.2), the mixing network comparison highlights our architectural efficiency in the critical value decomposition component.
Our method demonstrates remarkable parameter efficiency while achieving superior performance:
In 3s vz_ with only 21.601K parameters (same as QMIX), our method achieves nearly 100% win rate and faster convergence compared to QPLEX (72.482K parameters) and RIIT (37.988 37.986K parameters). This showcases our method's ability to learn efficient representations without requiring additional parameters.
In 5m _s______nn_ 6m, maintaining the parameter efficiency (31.52) (3,522KK, our method consistently outperforms all baselines with a win rate around 95%. Notably, QPLEX uses more than three times the parameters (107.574K) but achieves lower performance.
20

---

Hypergraph Coordination with Dynamic Grouping for MARL
In the challenging 3s5z_vs vs_666 scenario, despite keeping the parameter count 63.105,, our method demonstrates significant performance advantages over baselines, reaching approximately 90% win rate while QPLEX (243.156K parameters) struggles to achieve 40%.
Table 6. Size comparison of all methods' mixing network(s)
Maps
(Ft-)QMIX
QPLEX
RITT
GoMARL
Ours
38_ 38_vs_5z
21.601K
72.482K
37.986K
26,530K
21.601K
5m_vs_6m
31,521K
107.574K
51.362K
31,554K
31.521K
3s57_vs, 1357_v8_3s66 3863
63.105K
243.156K
118.466K
61.028K
63.105K
C.2. HGCN Overhead Analysis
While our method maintains the parameter-efficien QMIX mixing network, it introduces additional computational elements through the hypergraph convolutional network (HGCN) component. Table 7 quantifies this overhead.
The HGCN module introduces additional parameters beyond the mixing network parameters reported in Table 6. The com- putational overhead, measured as the increase in wall-clock training time compared to the base (Ft-)QMIX inplementation, remains relatively consistent across scenarios at approximately 36%.
This additional computational cost is justified by the significant performance improvements our method achieves:
1. Enhanced Sample Efficiency: Despite increased computation per iteration, method requires fewer training iterations to achieve superior performance.
2. Adaptive Information Flow: The HGCN enables dynamic grouping and information sharing between agents, capturing coordination patterns that static architectures cannot represent.
Table 7. HGCN additional parameters and computational overhead
Scenario
HGCN Parameters Computation Overhead
3s_ 3$_v$_5
65,356
+36.47%
5m vs 6m
104,632
+35.33%
3s57_ vs_ 3366
391,336
+36.95%
C.3. Analysis of Elficiency-Perffrmmanc Trade-off
The superior rfffciency-eefformmnn trade-off of our method can be attributed to three key design choices:
1. Architectural Innovation: Our method introduces hypergraph structure for better representation learning while maintaining QMIX's s efficient architecture. This enables more expressive information processing without increasing parameter count.
2. Efficient Information Flow: The hypergraph structure facilitates more effective information exchange between agents, leading to faster convergence and better performance despite using fewer parameters than complex architectures like QPLEX and RIIT.
3. Smart Parameter Sharing: Our architecture achieves better performance through intelligent parameter sharing across components, demonstrating that architectural design can be more crucial than model capacity.
C.4. Scalability and Performance Analysis
The performance scaling with respect to scenario complexity shows interesting patterns:
Simple Scenarios (e.g., 3s vs_ vs_5 Our method achieves faster convergence and better final performance while maintaining minimal parameter count.
21

---

Hypergraph Coordination with Dynamic Grouping for MARL
Medium Complexity (e.g., 3m_vs_6m) (s_6m): The performance advantage becomes more pronounced, with sustained high win rates despite keeping parameter count low.
Complex Scenarios (c.g., 3s52_M vs__vs__________ ss_3sz)) Our method demonstrates remarkable scalability, maintaining high perfor- mance in challenging environments where other methods, even with substantially more parameters, struggle.
These results highlight critical finding: superior performance in multi-agent reinforcement learning be achieved through better architectural design rather than increased model capacity. Our method successfully improves upon QMIX's foundation by introducing more expressive information processing capabilities without sacrificing parameter efficiency, leading to better performance across various scenarios while maintaining minimal parameter requirements.
22


Reviews:
[{"review_id": "VYfR8NjYle", "reviewer": "Reviewer_4bMa", "summary": "This work considers the problem of coordination in multi-agent systems. It proposes to construct hypergraphs (i.e., graphs with n-ary rather than binary relations) based on agent histories and using a graph convolution technique over this structure. This is motivated by the fact that agents need to form groups for solving tasks and change between groups dynamically. For the hypergraph construction step, the authors propose an approximate spectral clustering technique and prove certain properties regarding its convergence and solution quality. The features obtained through the convolution are used as additional inputs for Q-networks and policy networks alongside histories / actions. The authors demonstrate that the approach generally obtains better performance than a suite of CTDE and communication-enhanced MARL techniques for a variety of benchmarks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your thoughtful feedback, which has helped us improve our manuscript significantly.\n\nM1: Similarity Matrix Construction and State/Observation Formats\n\nIn Section 3.2, we presented our dynamic grouping framework using the normalized cut problem. The similarity matrix $W$ is constructed using a $k$-nearest neighbors approach based on Euclidean distances between agents' state history trajectories. $W_{ij}$ is positive only when agent $j$ is among agent $i$'s $k$ nearest neighbors, and zero otherwise.\n\nFor consistent application across environments, state histories are normalized to ensure uniform scaling across feature dimensions before applying the $k$-nearest neighbors method. This enables identification of meaningful coordination patterns regardless of the specific state representation format. We have added these details in the manuscript and provided complete environment setup descriptions in Appendix B.\n\nM2: CTDE Compatibility\n\nThank you for this thoughtful question. Our approach follows and extends the CTDE framework:\nOur grouping mechanism exhibits convergence properties (Theorem 2, Figure 4), with group structures stabilizing during training and eventually ceasing to update. This convergence enables decentralized execution: once training completes and group structure stabilizes, each agent's decision process relies only on its local observations enhanced by pre-computed group-aware representations. The attention-enhanced HGCN enables agents to selectively process structured information within their established groups rather than providing centralized information.\n\nOur contribution enhances the representational capacity of the CTDE framework by discovering and leveraging higher-order dynamic relationships. We have clarified this point in Section 3.1 of the revised manuscript.\n\nM3: Computational Efficiency\n\nWe have implemented several strategies to optimize computational costs:\nLimited History Window: We only utilize the most recent state\\_history\\_length timesteps for clustering (5,000 steps for SMAC)\n\nIntermittent Updates: Clustering occurs at fixed intervals (100,000 steps for SMAC).\nConvergence-based Termination: As shown in Figure 4, group changes decrease substantially in mid-to-late training phases. We implement complete termination of the grouping mechanism after 1M steps.\n\nThese mechanisms balance computational efficiency with the advantages of dynamic grouping. Implementation details have been added to Section 3.2 of the revised manuscript.\n\nE1: Hypergraphs vs. Standard Graphs\n\nOur baseline comparisons include standard graph-based methods (MAGIC, GA-Comm). In Section 4.5, following your valuable suggestion, we have added a comparison between hypergraphs and standard graphs under identical grouping strategies in Figure 5, which demonstrates the advantages of hypergraph-based representations.\n\nE2: Hyperparameters\n\nWe have added comprehensive tables of hyperparameters to Appendix B.5, including settings for clustering parameters, network architectures, and training configurations. Key parameters includ (5m\\_vs\\_6m scenario for example) clustering\\_interval: $100000$, state\\_history\\_length: $5000$, stability_threshold: $0.6$, min\\_clusters: $2$, max\\_clusters: $3$, hgcn\\_out\\_dim: $48$, hgcn\\_hidden\\_dim: $64$, and hgcn\\_num\\_layers: $2$. \n\nE3: Computational Overhead\n\nOur clustering approach minimizes computational overhead through infrequent updates and an explicit termination mechanism, making the spectral clustering cost negligible in practice. Additionally, our HGCN implementation maximizes parameter reuse when group structures remain stable. In the 5m\\_vs\\_6m scenario, we add approximately 104,632 parameters while increasing computational time by only approximately 35\\% compared to baseline (Ft-)QMIX. We have included theoretical complexity analysis in Appendix A.4 and provided detailed parameter and runtime quantification for all SMAC environments in Appendix C.2, justifying this overhead.\n\nC1: Team Stability\n\nWe implemented a \"stability threshold\" mechanism to prevent excessive team changes. Groups update only when the proportion of agents changing membership exceeds this threshold, balancing adaptive behavior with structural stability. For Figure 4 data aggregation, we collected group information at regular intervals throughout training. The upper portion displays group structure evolution over normalized time steps (different colors represent distinct groups), while the lower matrix presents co-occurrence probabilities calculated by averaging group memberships across collected time points. This reveals stable coordination patterns—for instance, agents 0 and 1 exhibit high co-occurrence probability, indicating consistent collaboration.\n\nWe have addressed all your formatting and notation suggestions to improve our manuscript's clarity and precision, and we have introduced HYGMA (HYpergraph Grouping for Multi-Agent coordination) as name.", "claims_and_evidence": "The claims in the abstract and introduction are supported by appropriate evidence in the paper text.", "methods_and_evaluation_criteria": "M1. The way in which the similarity matrix $W$ is constructed from state histories (Section 3.2) should be specified. Furthermore, the format of the states and observations should be given for each environment.\n\nM2. The work is compared to a variety of CTDE methods, but it is not clear to me whether the proposed method is in fact CTDE itself. This is not discussed in detail in the paper. My understanding is that it is *not*, given that the method still needs to perform the clustering step over histories to obtain the graph structure and then features $h_i$, which requires knowing the histories of all the agents. I do not see how this can be done in a decentralised way at inference time.\n\nM3. Furthermore, given the spectral clustering requires knowledge of all the agent histories, the computational cost of this step will increase with longer episodes. This potential drawback should be discussed (and might be mitigated by, e.g., limiting the history to a time window at most X steps in the past).", "theoretical_claims": "I understand the statements of the theoretical claims but not the details of the proofs themselves.", "experimental_designs_or_analyses": "E1. The method is not compared with any other techniques that leverage graph structure. The need for using *hypergraphs* as opposed to standard (binary relation) graphs should be demonstrated in an ablation, as the claims around the need for hypergraphs are central to the narrative of the paper. \n\nE2. The work does not give any details about the hyperparameters that were used and how they were tuned. Given the work claims improvement over state-of-the-art methods, all algorithms should be given a comparable budget for hyperparameter tuning to make the comparison fair.\n\nE3. The overhead for performing the spectral clustering step and graph convolution steps should be quantified. While the method does seem to obtain an improvement in sample efficiency, in practice the wall clock time overhead may be significant.", "relation_to_broader_scientific_literature": "The work connects MARL and graphs in an interesting and novel way. I am not aware of similar works in MARL that use hypergraphs, and the reasoning for using n-ary relations is quite convincing.", "essential_references_not_discussed": "To the best of my knowledge, all essential references in this area are discussed.", "other_strengths_and_weaknesses": "The paper in general is fairly organised and well-written, with a novel idea and promising experiments.", "other_comments_or_suggestions": "C1. Regarding the experiment in 4.5: as far as I understand, there is no penalty for changing \"teams\". This may be unstable and could be problematic in more complex tasks. Could you specify how the information was aggregated for each point on the x-axis? \n\nC2. Consider giving your method a name so you can avoid \"Our Method\" etc. in tables and figures.\n\nC3. Running title (top of each page) still uses default template title.\n\nC4. Space is missing before the start of many citations, consider adding a space or \"~\" before `\\cite` commands\n\nC5. Subscripts in math notation use a mix of `\\text` and plain characters e.g. $\\mathcal{L}\\_{\\text{group}}$ and $\\mathcal{L}_{group}$. Consider being consistent (first one is preferable in my opinion).\n\nC6. Typos: \"Figure 3 reveal\", \"Table 1 reveal\", \"Table 2 illuminate\"\n\nC6. The way of combining task-specific and structural losses is quite standard, I would not view it as a contribution of the paper (as claimed in the conclusion).", "questions_for_authors": "Please address M1-M3, E1-E3, and C1 above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DzfHhlx42o", "reviewer": "Reviewer_KzYL", "summary": "This paper proposes a multi-agent reinforcement learning framework based on dynamic spectral clustering and hypergraph coordination network, aiming to address the challenges of dynamic relationship modeling and efficient information exchange in complex collaborative tasks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your thorough review and insightful questions. Your feedback has helped us identify important areas for clarification and improvement.\n\nQ1: Computational Overhead of Spectral Clustering\n\nWe appreciate your question regarding computational scalability. Our implementation addresses potential spectral clustering overhead through complementary optimizations:\n\nOur method executes clustering operations only at fixed intervals, combined with a stability threshold mechanism that triggers updates only when the proportion of agents changing groups exceeds the threshold ($\\delta$). This approach reduces computational demand as training progresses—clustering operations become increasingly infrequent as group structures stabilize, eventually being eliminated in later training phases.\n\nThese optimizations ensure the computational cost of spectral clustering becomes negligible in practice. While our measurements show the HGCN component introduces approximately 35\\% increase in total computational time, this trade-off is justified by the performance improvements across all test environments.\n\nWe acknowledge that scaling to larger agent populations would require additional considerations. We thank the reviewer for highlighting this important research direction, which we have addressed in our revised manuscript's discussion of future work.\n\nQ2: Grouping Update Threshold ($\\delta$)\n\nThank you for your thoughtful question about the grouping update threshold in formula (5).\n\nThe threshold $\\delta$ functions as a stability control mechanism determining when to trigger group restructuring. A group update occurs only when the proportion of agents that would change groups exceeds this threshold. This approach prevents computational overhead from frequent minor reorganizations while allowing adaptation when significant coordination pattern changes emerge.\n\nIn our implementation, we use $\\delta$=0.6, meaning group structures update only when at least 40\\% of agents would change their group assignment. This value balances computational efficiency with adaptivity.\n\nImportantly, this single threshold value performs effectively across all tested environments without requiring task-specific tuning. This robustness stems from:\n\n1.The complementary periodic evaluation (controlled by \\texttt{clustering\\_interval})\n\n2.Quality-based group selection using silhouette scores\n\n3.The self-correcting nature of the reinforcement learning process\n\nThis empirical stability aligns with our theoretical analysis in Theorem 2, which shows that $\\delta$ primarily affects the expected number of updates (O(1/$\\delta$)) rather than final convergence quality.\n\nQ3: Parameter Sensitivity\n\nThank you for raising this important question about parameter sensitivity.\nDynamic clustering parameters ($k_{\\min}$/$k_{\\max}$): These define search space bounds rather than fixed structural constraints. Our method employs silhouette score optimization to automatically select the optimal number of clusters within this range. We follow a consistent principle: $k_{\\min} = 2$ (allowing at minimum pair-wise coordination), while $k_{\\max}$ scales with agent count (approximately n/2). For SMAC environments with 5 agents, we use $k_{\\max} = 3$.\n\nThis silhouette-based selection significantly reduces sensitivity to the exact $k_{\\min}$/$k_{\\max}$ values, as the hypergraph structure naturally adapts to reflect discovered group dynamics.\n\nAttention mechanism: Our hypergraph convolution network uses a 4-head attention mechanism, balancing representational capacity with computational efficiency. This allows agents to selectively attend to different aspects of group information simultaneously.\n\nNetwork capacity parameters: Following standard practice, we adjust HGCN dimensions based on environment scale (e.g., from 96 dimensions in smaller environments to 128 in larger ones). This follows a simple principle: network capacity scales proportionally with environment complexity and agent count.\n\nLoss function weights: Regarding $\\lambda_1$ and $\\lambda_2$, we use $\\lambda_1 = 0.001$ for group consistency loss and $\\lambda_2 = 0.01$ for attention regularization. These values ensure auxiliary losses provide meaningful gradients without overshadowing the primary task objective. The same values work effectively across all environments.\n\nDespite capacity adjustments, our method's core algorithmic parameters remain consistent across environments. The dynamic nature of our approach—with spectral clustering, attention-based information processing, and stability thresholds—creates inherent adaptability that reduces the need for environment-specific tuning.\n\nWe have provided hyperparameter specifications in the appendix in revised manuscript to ensure full reproducibility. We appreciate the reviewer's comprehensive feedback and reference suggestions. We have incorporated into our manuscript to strengthen the literature review and better position our work within the field.", "claims_and_evidence": "The core propositions in the paper are backed by ample evidence, yet certain technical details and generalizability aspects merit further discussion.\n\nSeveral issues remain to be clarified: 1) The computational overhead of spectral clustering during each training phase remains unquantified, potentially impeding its widespread adoption. 2) Certain proofs depend on idealized assumptions (e.g., complete observation, deterministic transformation), necessitating a discussion on their robustness in real-world deviations.3) The sensitivity to the hyper-parameters is not been analyzed, potentially obscuring the true contributions of structural optimization.", "methods_and_evaluation_criteria": "The dynamic hypergraph coordination network and its evaluation criteria proposed in the paper have significant implications for addressing current collaboration challenges in MARL. For the first time, the integration of spectral clustering and hypergraph neural networks has addressed two critical challenges: dynamic grouping and high-order relationship modeling. Covering four types of differentiated benchmarks, the indicator design balances performance and interpretability, demonstrating the superiority of the method in complex collaborative tasks. Suitable for real-world scenarios that require flexible coordination, such as logistics and transportation, but further research is needed to optimize computations and adapt to physical constraints.", "theoretical_claims": "Yes, I have checked the proofs.", "experimental_designs_or_analyses": "The experimental design of the paper excels in scene coverage and baseline diversity, bolstering the assertion of the method's effectiveness in dynamic collaborative tasks. Nevertheless, deficiencies in communication overhead, hyperparameter influence, and ablation depth could potentially compromise the comprehensiveness and reproducibility of the conclusions. It is recommended to supplement the aforementioned analysis to bolster the persuasiveness of the experiment.", "relation_to_broader_scientific_literature": "The paper makes several contributions that build upon and interact with the broader scientific literature in multi-agent reinforcement learning.", "essential_references_not_discussed": "The paper covers the most relevant literature in the field of multi-agent reinforcement learning (MARL). However, some essential references can be considered:\n\n1. Yang, Q., Dong, W., Ren, Z., Wang, J., Wang, T. and Zhang, C., 2022, June. Self-organized polynomial-time coordination graphs. In International Conference on Machine Learning (pp. 24963-24979). PMLR.\n\n2. Wang, T., Zeng, L., Dong, W., Yang, Q., Yu, Y. and Zhang, C., 2021. Context-aware sparse deep coordination graphs. arXiv preprint arXiv:2106.02886.\n\n3. Liu, Z., Wan, L., Sui, X., Chen, Z., Sun, K. and Lan, X., 2023, August. Deep Hierarchical Communication Graph in Multi-Agent Reinforcement Learning. In IJCAI (pp. 208-216).", "other_strengths_and_weaknesses": "This article significantly enhances the flexibility and efficiency of multi-agent collaboration by innovatively combining dynamic spectral clustering with hypergraph neural networks. The theoretical analysis is solid, and the experimental verification is ample. Although there are shortcomings related to computational overhead and practical deployment verification, its strengths in algorithm design, theoretical contributions, and application potential position it as a significant advancement in the field of MARL.", "other_comments_or_suggestions": "The paper demonstrates outstanding innovation in methods and comprehensiveness in experiments but requires correction of detail errors and enhancement of reproducibility descriptions. It is recommended to prioritize addressing issues of terminology consistency and formula standardization, followed by supplementing experimental configuration details to enhance academic rigor.", "questions_for_authors": "Question 1: Dynamic spectral clustering requires calculating similarity matrices and performing feature decomposition in each round of training, which may result in significant computational overhead when the number of agents n is large (such as n>50). The paper did not mention any optimization measures for this, such as approximate spectral clustering methods.\n\nQuestion 2: How does the setting of the grouping update threshold δ in formula (5) affect performance? Is it necessary to manually adjust δ for different tasks?\n\nQuestion 3: How do dynamic clustering parameters (such as k_min/k_max) and attention heads affect performance? Do we need to readjust parameters for different tasks?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BvBhxtuszX", "reviewer": "Reviewer_WTGc", "summary": "The paper presents a novel framework that combines dynamic spectral clustering with hypergraph neural networks to address the multi-agent coordination problem in Multi-Agent Reinforcement Learning. The framework performs spectral clustering on agents’ state histories , dynamically constructing and updating the hypergraph structure. It enhances information processing through a hypergraph convolutional network and incorporates an attention mechanism to improve the selective processing of information. This architecture is also applicable to both value-based and policy-based paradigms.  The paper claims that this method outperforms state-of-the-art MARL approaches in sample efficiency and final performance across multiple tasks.\n\n\n## Update after Rebuttal\n\nI appreciate the authors’ response and their efforts to address the raised concerns. However, key issues related to the experimental section remain unresolved. The authors evaluate their method on only three scenarios from the SMAC benchmark. Given the limitation, I am maintaining my current score, which already reflects the highest assessment I can reasonably provide under the current circumstances.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your thoughtful feedback and constructive comments. Your insights have helped us identify areas for improvement in our manuscript.\n\nWeaknesses 1: Regarding Figure 1\n\nWe sincerely appreciate your thoughtful feedback and constructive comments, which have helped us identify areas for improvement in our manuscript.\nRegarding Figure 1\n\nThank you for your feedback regarding the confusing of Figure 1. We have made targeted improvements to better illustrate two key elements of our approach:\n\n1．The periodic nature of our grouping mechanism (rather than updating every timestep)\n\n2．The mapping from identified groups to hypergraph structure\n\nThe stability threshold ($\\delta$) was already included in the figure, and we've enhanced its visual prominence to emphasize this critical control mechanism that prevents excessive group fluctuations.\n\n\nWeaknesses 2: Value-based and Policy-based Framework Implementations\n\nThank you for highlighting this important area for improvement. We have enhanced Section 3.1 and 3.5 with:\n\n1.More comprehensive descriptions of our method's integration into both paradigms\n\n2.Explanation of how HGCN-extracted features enhance Q-function expressiveness in value-based frameworks, enabling more accurate modeling of intra-group coordination patterns\n\n3.Parallel analysis of how HGCN-extracted features improve policy networks in actor-critic frameworks by providing higher-order relationship information for more effective action selection\n\nTo address your concern about limited experimental comparison, we have added MAPPO as a policy-based baseline in the SMAC scenarios (achieving win rates of 0.93, 0.74, and 0.16 on 3s\\_vs\\_5z, 5m\\_vs\\_6m, and 3s5z\\_vs\\_3s6z respectively). This addition enables direct comparison between value-based and policy-based approaches in identical environments.\n\nThis expanded section better illustrates the versatility of our approach across different learning paradigms and strengthens this key contribution.\n\nOther comments: Scalability with Increasing Agent Numbers\n\nRegarding your question about agent scalability: The SMAC environment inherently addresses this through agent deaths during episodes, creating natural variation in agent counts within the same scenario. Our method successfully handles this dynamic aspect, as demonstrated in the performance results.\n\nOur dynamic grouping mechanism maintains efficiency with larger agent numbers through several design choices:\n\n1．Periodic pre-computation of groupings using collected state histories rather than real-time updates\n\n2．Strategic clustering intervals and stability thresholds that control update frequency\n\n3．Updates triggered only when specific conditions are met, preventing computational bottlenecks\n\nOur experiments demonstrate scalability across different agent populations:\n\n1．Predator-Prey environment: 5 agents (Fig. 3a) versus 10 agents (Fig. 3b)\n\n2．Traffic Junction: scenarios with up to 5 and 10 agents (Table 1)\n\n3．SMAC: varying numbers and types of agents across scenarios\n\nThe results consistently show our method's performance advantages becoming more pronounced as agent numbers increase, particularly in large-scale scenarios, validating its strong scalability characteristics.\n\nWe appreciate the opportunity to address these points and have incorporated these improvements in our revised manuscript.", "claims_and_evidence": "Yes. The paper derives the proposed claims through numerous formulas and proofs, and designs multiple experiments to validate the effectiveness of the method.", "methods_and_evaluation_criteria": "Yes. The method in this paper primarily focuses on improving multi-agent coordination. The selected baselines and experiments are commonly used scenarios in multi-agent systems.", "theoretical_claims": "Yes. This paper combines a large number of references and formula proofs to verify the correctness of its claims, especially in Section 3.2, where a large number of theorems are used to demonstrate the effectiveness of the dynamic spectral clustering mechanism in both computational efficiency and learning quality.", "experimental_designs_or_analyses": "Yes. This paper includes ablation studies and various coordination environments to test the effectiveness and scalability of the proposed method. Evaluation criteria such as convergence speed, sample efficiency, and final performance are applied to assess the effectiveness of the proposed method.", "relation_to_broader_scientific_literature": "1. Multi-agent group recognition using adaptive dynamic spectral clustering.\n2. Using Hypergraph to represent the relationships between multiple agents has become very common.\n3. Hypergraph attention convolutional neural network has powerful feature extraction ability, which can extract complex relationships between agents.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n\n1. The integration of dynamic spectral clustering with hypergraph convolution networks is novel and improve the limitations of modeling dynamic relationships between multiple agents.\n2. The formulas and theorems are introduced clearly and clearly, and are proved and derived.\n3. The paper is well-written and clear in its exposition of the methods and experiments.\n\n\n\nWeaknesses：\n\n1. The structure and annotations of Figure 1 are a bit confusing and difficult to understand.\n2. The introduction and experiment of Implementation in Value-based and Policy-based Frameworks are still a bit simple. As a major innovation point, it should be discussed and compared.", "other_comments_or_suggestions": "Will dynamic grouping affect efficiency and performance when the number of agents increases? Is it possible to add an experiment with different numbers of agents in the same scenario for further discussion?", "questions_for_authors": "See weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EtjeZcCzsV", "reviewer": "Reviewer_6Jxm", "summary": "The paper proposes a new method to learn higher-order coordination patterns between agents, based on a spectral clustering algorithm and a hyper-graph convolutional network. Agents are coherently grouped together, with such groups changing only when a certain threshold is hit, with the HGCN then combining their information to provide an additional learning signal that can be used in both value-based and policy-based algorithms. Experimental results show improved performances and better sample efficiency against SOTA baselines on a diverse set of cooperative problems.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed feedback. We sincerely appreciate your thoughtful questions that will improve our manuscript.\n\nQ1: CTDE Compliance and Execution Requirements \n\nOur method strictly adheres to CTDE without requiring centralized execution:\n\n1.During execution, agents' decisions depend only on local observation history ($\\tau_i$) and group-derived features ($h_i$), not global state.\n\n2.Group structure converges during training (Theorem 2), after which agents operate with stable group membership, exchanging information only within established groups.\n\n3.HGCN functions as a structured information processor during training, creating enhanced local representations without execution-time centralization. This approach is similar to other CTDE methods that enrich agent representations while maintaining decentralized execution. Importantly, once training is complete, the learned group structure remains fixed during deployment, ensuring true decentralized execution with only local observation exchange within established groups.\n\nQ2: Agent Group Membership Limitations \n\nYour observation about overlapping groups is astute. We considered allowing agents to belong to multiple groups, which better captures multidimensional coordination relationships. Implementation complexity, computational overhead, and convergence stability led us to adopt hard partitioning as a first implementation. We agree that real-world coordination is often overlapping. This limitation opens directions for future research: (1) soft/fuzzy clustering, (2) hypergraph structures with overlapping hyperedges, and (3) multi-membership representation learning. We've added a discussion of this limitation in our revision manuscript.\n\nQ3: Role of $k$ in Equation (4) \n\nIn Equation (4), $k$ directly influences optimization as the primary variable. For each $k \\in [k_{\\min}, k_{\\max}]$, spectral clustering partitions agents into k groups, determining how $a(i)$ and $b(i)$ are calculated:\n\n1．$a(i)$: mean distance between agent $i$ and others in its group\n\n2．$b(i)$: minimum mean distance from agent $i$ to any other group Selecting $k$ that maximizes silhouette coefficient balances intra-group cohesion and inter-group separation.\n\n\nQ4: Fairness of Experimental Comparisons \n\nOur experimental comparisons remain fair because:\n\n1.Our method maintains CTDE compliance as explained in Q1, operating under the same paradigm constraints as baselines.\n\n2.Figure 5's ablation studies show improvements derive from structured information processing rather than increased information access. The \"Single Group\" variant provides same information but underperforms without adaptive grouping.\n\n3.We've enhanced ablation studies (Figure 5) with experiments comparing our approach against standard graph structures. These new results isolate the specific benefits of dynamic hypergraph structure versus static information sharing.\n\n4.Experiments already include CommNet as a baseline, which implements structured communication within CTCE. We've expanded discussion of these comparative results to highlight our method's specific contributions.\n\nQ5: Communication Efficiency Claims \n\nYou correctly identified our imprecise statement. \"Avoiding communication overhead\" should be \"providing more efficient communication structure.\" Traditional methods require $O(n^2)$ communication complexity, while our hypergraph structure reduces this to $O(n^2/k)$ through dynamic grouping, explaining superior performance in large-scale environments. Runtime comparisons and efficiency analysis are added in the appendix.\n\nQ6: Convergence Definition in Traffic Junction \n\nIn Traffic Junction experiments, convergence is defined when an algorithm first reaches 90\\% of final performance and maintains this for 5 consecutive evaluation epochs, capturing stable convergence rather than temporary spikes.\n\nQ7: Parameter Analysis Completeness \n\nOur focus on mixing network parameters was a deliberate choice to isolate the core architectural components that directly influence value factorization. We've expanded Appendix C with comprehensive parameter analysis including HGCN components. In 5m\\_vs\\_6m, though HGCN adds 104,632 parameters, it increases computational time by only approximately 35\\% due to efficient parameter reuse during group reorganizations. Our ablation studies demonstrate that performance gains stem primarily from the dynamic hypergraph structure's efficient information processing capabilities rather than simply increased model capacity, highlighting the importance of architectural design over raw parameter count in multi-agent coordination.\n\nMissing References \\& Notation corrections: \n\nThank you for highlighting relevant prior work and notation inconsistencies. We've incorporated discussions of the suggested references in our revision and corrected all notation issues.", "claims_and_evidence": "The paper supports its claim with a quite extensive theoretical grounding, and provides results that bound the achievement of convergence of the learned hyper-graph representation, as well as the error from the optimum. Some aspects of the algorithmic outcome are not sufficiently made clear in my opinion (such as the centralized execution requirement), please see the Questions below for more details.", "methods_and_evaluation_criteria": "I have some concern on the effective assessment of the proposed empirical results and their analysis. While it is clear that the proposed algorithm achieves better performances on a wide set of problems, I think that the analysis lacks clarity in assessing the actual merits of the underlying methodology, and is sloppy in some aspects. Please see the Questions below for a more detailed breakdown of this aspect.", "theoretical_claims": "I have checked the detailed proof of the main theoretical claims in some details, and these seem to be correct and sound.", "experimental_designs_or_analyses": "I have not empirically checked the validity of the proposed experimental analyses.", "relation_to_broader_scientific_literature": "The relevant connections with existing scientific literature are already appropriately discussed in the paper.", "essential_references_not_discussed": "Applications of (fixed) hype-rgraph structures in improving learning performance have already been investigated in MARL literature (e.g., see [[Castellini et al., 2021]](https://link.springer.com/article/10.1007/s10458-021-09506-w), [[Boehmer et al., 2020]](https://proceedings.mlr.press/v119/boehmer20a.html) and [[Li et al., 2021]](https://dl.acm.org/doi/10.5555/3463952.3464044)), but this track of works is not mentioned nor discussed. Also, attention mechanisms to focus agents solely on salient information of the others have been proposed for policy-based methods as well (e.g., [[Iqbal et Sha, 2019]](https://proceedings.mlr.press/v97/iqbal19a.html)).", "other_strengths_and_weaknesses": "None", "other_comments_or_suggestions": "- Equation (7): $\\alpha ie\\rightarrow\\alpha_{ie}$ (also at the end of the following text block and in Equation (13))\n\n- Equation (13): $\\mathcal{L}att\\rightarrow\\mathcal{L}_{att}$\n\n- Equation (13): $\\mathcal{L}task\\rightarrow\\mathcal{L}_{task}$", "questions_for_authors": "**Q1:** I think as aspect that is not highlighted is that the proposed overall framework is not amenable to decentralized execution: both value-based and policy-based instantiation of it require the agents to feed on the group-aware representations $h_i$, which requires the centralized module for spectral clustering and the hyper-graph network (and the consequent centralized collection of agents' histories and actions) in order to be computed. I think that this aspect should be clearly stated and discussed, as to avoid confusion in the reader and wrong positioning in the existing MARL landscape.\n\n**Q2:** You method, although learning higher-order decompositions, still produces partitions of the agents (indeed, produced by a spectral clustering algorithm), and thus limit the impact of one agent to only a single subset of the others. In higher-order factorizations, however, it is common to have agents that are comprised into different overlapping factors with diverse subsets of other agents in each of them. I think the potential effects of this, and some general reflections on this aspect, should be discussed in the paper, as these help is assessing potential use-cases and general limitations of the proposed algorithm.\n\n**Q3:** In Equation (4), the impact of $k$ is not apparent? Where does it influence the optimization problem? How are $a(i)$ and $b(i)$ using it (if they are)?\n\n**Q4:** If my understanding of all the SMAC baselines is correct (I'm not very familiar with VAST and GoMARL), you are comparing only against CTDE algorithms, that thus retain a completely decentralized execution scheme. This does not look like an entirely fair comparison, as your proposed method instead uses centralized information to feed the agents' $Q$-functions. Although I appreciate that these are some popular and strong baselines, and comparing to them is useful in assessing the increased performance of your algorithm, I think that also comparing against some centralized-execution method would have been helpful in clearly assessing up to what extent these improvements stem from the hyper-graph approach you are actually proposing, and what is instead due to simply having more information at execution time. On this point, Figure 5 is a step forward, but definitely not sufficiently discussed or interpreted.\n\n**Q5:** \"The proposed method maintains consistent coordination efficiency across both scenarios through adaptive group formation, enabling effective information flow while avoiding communication overhead.\" Isn't your proposed method using a form of communication after all? In the compared baselines, the communication happens between agents directly, while in your communication is between agents and the centralized components. Given that there is an information exchange in your method as well, how is it avoiding communication overheads?\n\n**Q6:** In the Traffic Junction problem, how is the convergence step measure assessed? When is an algorithm considered to be converged? This aspect needs more explanation to be able to properly appreciate the results.\n\n**Q7:** In Appendix C.1, it seems a bit obvious that the parameters you are using for the mixing network are the same as QMIX, as the mixer network structure you use is indeed that of QMIX. However, you do not seem to keep account of the additional parameters of the attention HGCN, which probably would change the following comparison and discussion on your low parameter count. Perhaps I am not understanding the way in which you count the mixing parameter here, and the hyper-graph network's one are included there?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces an interesting approach to improving multi-agent coordination by using a hypergraph and spectral clustering to learn higher-order relationships between agents. The method shows promising results in terms of both performance and sample efficiency, especially compared to existing baselines. However, a few points could be cleared up to make the paper stronger from reviewers.
- there’s some confusion about whether the method is truly decentralized. The approach relies on agents sharing a lot of information, which seems more centralized than decentralized in execution. This should probably be explained more clearly, as it could confuse readers who expect a purely decentralized setup.
- The experimental section could use more depth. While the method outperforms some baselines, there isn’t a detailed breakdown of the results, and it feels like some of the analysis is a bit rushed. More comparisons, especially with methods that also use centralized execution, could help show how much of the improvement is due to the proposed hypergraph method versus just having more information overall.
- Also, some of the assumptions around communication need clarification. While the paper claims to reduce communication overhead, it seems like the agents are still relying on some form of communication with a central module, which could be seen as a form of overhead itself. This part of the discussion feels a little unclear.
- the computational cost of using spectral clustering and hypergraph networks isn’t discussed much, but these elements are likely adding significant overhead. The authors should be upfront about the time and resources required for training and also make it clear how the parameters stack up against other methods.

Overall, the paper presents an interesting idea, but there’s some need for more clarity in both the theoretical and experimental sections to make it more digestible and transparent for readers.
Decision: Accept (poster)