Graph Coarsening using Game Theoretic Approach
Authors: Sonali Raj
Manoj Kumar
Sumit Kumar
Ruchir Gupta
Amit Kumar Jaiswal
Venue: Accepted by TMLR ()

Abstract: Graph coarsening is a method for reducing the size of an original graph while preserving its structural and feature-related properties. In graph machine learning, it is often employed as a preprocessing step to improve efficiency and scalability when handling large graph
datasets. In this study, we address the challenge of coarsening an original graph into a coarsened graph that retains these characteristics. We propose a Cooperative-Based Graph Coarsening (CGC) algorithm, which leverages cooperative game theory as a framework
for combinatorial optimization, aiming to minimize the total Dirichlet energy of the graph through localized optimizations. We prove that the proposed coarsening game is a potential game that guarantees convergence to a stable coarsened graph. Tests on real-world datasets
demonstrate that CGC algorithm surpasses prior state-of-the-art techniques in terms of coarsened graph accuracy and achieves reduced time complexity. These results highlight the potential of game-theoretic approaches in the advancement of graph coarsening techniques.

Published in Transactions on Machine Learning Research (02/2026)
Graph Coarsening using Game Theoretic Approach
Sonali Raj
sonalimj. rs. www.inn..r..cce2giiiib.....o.
Department of Computer Science and Engineering
Indian Institute of Technology (BHU) Varanasi, India
Manoj Kumar
manojkr
Department of Electronics Engineering
Indian Instätute of Technology (Indian School of Mines) Dhanbad, India
Sumit Kumar
kumars @nitj. oc.
Deportment of Computer Science ond Engineering Dr B R Ambedker National Institute of Technology, Jalandhar, India
Ruchir Gupta
rguptaa.se@@ithhuu.c...
Department of Computer Science and Engineering Indian Institute of Technology (BHU) Varanasi, India
Amit Kumar Jaiswal
amit.chr@ittbluu ac
Jay Chaudhry Software Innovation Centre
Indian Institute of Technology (BHU) Varamasi, India
Reviewed on OpenReview: https: // openreview. net/ net/ forum? id= BuLB)QJJIn
Abstract
Graph coarsening is a method for reducing the size of an original graph while preserving its structural and feature-related properties. In graph machine learning, it is often employed as preprocessing step to improve efficiency and scalability when handling large graph datasets. In this study, we address the challenge of coarsening an original graph into a coarsened graph that retains these characteristics. We propose a Cooperative-Based Graph Coarsening (CGC) algorithm, which leverages cooperative game theory as a framework for combinatorial optimization, aiming minimize the total Dirichlet energy of the graph through localized optimizations. We prove that the proposed coarsening game is potential game that guarantees convergence to stable coarsened graph. Tests real-world datasets demonstrate that CGC algorithm surpasses prior stale-of-the-arl techniques in terms of coarsened graph accuracy and achieves reduced time complexity. These results highlight the potential of game-theoretic approaches in the advancement of graph coarsening tochniques.
1 INTRODUCTION
Graphs are powerful data structures used represent complex relationships and interactions among entities. Graphs offer natural and flexible way to model real-world systems, which widely employed across varied domains such as social networks, biological systems, transportation infrastructures, and communication
networks (Fan et al. 2019 Li et al. 2021 Rahmani et al. 2023 Wu et al. 2022 Shi & Weninger 2017 Tn these representations, entities are modeled as nodes, while the relationships or interactions among them are captured through edges. This framework enables systematic analysis of both local and global connectivity patterns, as well as the structural characteristics of complex systems (Neville Jensen Gutierrez, 2008).
2007
Angles
With the growing need to extract knowledge from graph-structured data, Graph Neural Networks (GNNs) have emerged as class of deep learning models specifically designed for learning on graphs. By leveraging

---

Published in Transactions on Machine Learning Research (02/2026)
both the feature information of nodes and the structure of their neighborhoods, GNNs propagate informa- tion through the graph via message passing and aggregation mechanisms. This allows GNNs to capture rich relational patterns and contextual dependencics, making them highly effective for tasks such as node classification, link prediction, and graph classification (Corso et al. 2024).
However, as real-world data becomes increasingly voluminous and interconnected, large-scale graphs have become more common, driven by advances in scientific rescarch, online platforms, and the proliferation of connected devices in the Internet of Things. The application of GNNs to such massive graphs introduces sig- nificant computational and memory bottlenecks. The recursive neighborhood expansion in message passing leads to rapidly growing computation, while deep GNN architoctures suffer from over-smoothing, wherein node representations become indistinct. Additionally, training GNNs often requires extensive hyperparam- eter tuning, further increasing time and resource demands. These challenges highlight. the need for efficient preprocessing strategies to reduce graph size without compromising structural and semantic integrity. There
are various techniques for graph reduction, including graph sparsification (Fung et al., 2011 Bravo Herms-
dorlf& & Gunderson
2019
Li al.
2022). graph coarsening (Dickens el al. 2024 Kumar et al. 2023 Loukas
2019
Huang et al. 2021 Loukas & Vandergheynst, 2018 Wang et al. 2019) and graph condensation (Jin
et al.
2021 Xiao et. al. 2024 Gao et al. 2025).
Graph sparsification reduces the number of edges while preserving key structural properties such as cuts, pairwise distances, or spectral signatures. However, it retains the full set of nodes, limiting its potential for computational speedup in node-centric operations. Moreover, many sparsification algorithms depend on costly spectral computations (e.g., effective resistance or eigenvalue approximations) and do not always align with downstream task objectives, such those in GNN-based learning (Li et al. 2022).
Graph condensation, in contrast, synthesizes a small, learnable graph from scratch such that a GNN trained on this synthetic graph approximates the performance of one trained on the original graph. While effective at reducing memory usage during GNN training, condensation methods rely on nested or bi-level optimization (e.g.. gradient or distribution matching), which incurs substantial preprocessing cost and memory over- head. Furthermore, they often require label information and offer limited interpretability, which hampers generalization across models and datasets.
Graph coarsening offers balanced alternative by reducing both nodes and edges through the aggregation of structurally or feature-similar nodes into supernodes, while maintaining the overall topology and semantics of the graph (Chen et al. 2022). This approach retains a clear mapping between the original and reducod graph, allowing interpret ability and compatibility with a variety of downstream GNN tasks. As a result, coarsening enables more scalable and efficient graph learning without sacrificing representational fidelity.
ceiiiizattio-bbseed and deep learning-based. Heuristic coarsening methods [Loukas 2019 Huang et al. 2021 Loukas & Van- dergheynst 2018 typically rely only on structural information such as adjacency patterns or spectral ap- proximations, and ignore node features. As a result, coarsened graphs can be less informative and degrade downstream performance (c.g.. node classification). Deep learning- baseen methods (Ying et al. 2018 Jin
Recent graph coarsening approaches fall into three main categories: heuristic-based,
et al. 2021 Zhao et al. 2020 ZZheng et al.] 2023 Dickens et al. (024) leverage graph neural networks (GNNs) to learn coarsening operations as part of graph representation learning. These methods are com- putationally intensive and do not suit generalized GNNs,
GNN trained particular model does
not perform well on other models. Optimization--ased coarsening methods (Kumar et al. 2023 2024 do incorporate structure and features but introduce many hyperparameters and require repeated tuning across datasets and coarsening ratios. This leads to significant computational overhead and undermines the basic purpose of coarsening, i.e., to reduce cost rather than add complexity. In these approaches, the search space becomes increasingly large and multidimensional as the graph size grows. Therefore, these approaches gencrally fail to produce the desired results when the problem size is large and suffer from scalability issucs. Additionally, game-theoretic formulations have been explored mainly for graph clustering (Mandala et al., 2014 Bu et al. 2018 Zhao et al.) 2024 Kumar & Guptal 2021 Li et al., (024).. These game- gaee-theoretic clustering methods often rely solely on structural connectivity and ignore node attributes, or they depend on nontrivial hyperparameters that require clustering-specifie expertise to tune.
2

---

Published in Transactions on Machine Learning Research (02/2026)
These limitations demonstrate the need for coarsening technique that is both computationally efficient and feature-aware, while preserving the structural properties of the original graph. Our work aims to develop a fast method without hyperparameter tuning that uses both graph topology and node attributes to produce high-quality coarsened graphs for the improvement of downstream task performance and hence, we introduce cooperative game-theoretic framework for coarsening.
We utilize cooperative game theory for four key reasons. First, cooperative games allow us to incorporate both structural connectivily and feature similarily in unified manner. The marginal contribution based cost reflects how much node benefits the coalition in terms of both graph structure and feature smoothness. Sccond, the game theory allows us the construction of cxact potential game, which guarantces that every time a node updates its coalition choice, the global Dirichlet energy decreases. This alignment ensures that local best responses naturally guide the system toward a stable coarsened representation without the need for tuning. Third, the potential game formulation ensures convergence a pure Nash equilibrium, which corresponds to stable coalition structure. Fourth, the existence of at least one Nash equilibrium ensures a stable and high-quality solution. This property makes the method more scalable than heuristic or conventional optimization techniques.
In our game-theorelic formulation, each node acts as a player that strategically forms coalitions with other nodes in the graph. This insight motivates our distributed formulation of the graph coarsening problem, where each player minimizes its cost. In our formulation, coalitions correspond to supernodes, and the cost of each player defined through its marginal contribution to the Dirichlet energy, which measures frat signal smoothness the graph, minimizing it preserves both connectivity and attribute consistency under coarsening. This creates direct connection between local node-level decisions and the global objective of minimizing energy distortion in the coarsened graph. This gives theoretical guarantee of stability and explains the robust, tuning-free performance of CGC across diverse dalasets and coarsening ratios. This gives a theoretical guarantee of stability and explains the robust, tuning-free free performance CGC across diverse datasets and coarscning ratios.
The main contributions of this paper are summarized as follows:
Introduces a novel graph coarsening framework using game theory.
rntroueess a cost function that utilizes marginal contributions to Dirichlet energy, ensuring structural preservation.
Empirically validates the approach on real-world datasets, demonstrating its effectiveness in node classification tasks.
Presentes a theoretical proof demonstrating that the proposed game satisfies the conditions of potential game.
The remaining paper is structured as follows. Section presents the necessary background on graphs and graph coarsening, followed by the proposed problem formulation and the game-theoretic framework. Section introduces the algorithm along with its convergence guarantee. Section 4 provides experimental results on real-world datasets for node classification, structural property preservation, and comparisons state-of-ie of-te-of-the- art methods.
2 BACKGROUND
This section presents the fundamental concepts of graphs and graph coarsening, including a toy example, followed by the formulation of the proposed problem and its game-theoretic formulation.
2.1 Graph
A simple undirocted graph with features and labels, denoted as G G EV, is defined by a node set V = (V1, Ve...., ....,,,, V/}} and an edge set C [V]2. The topology of the graph is represented using a weighted adjacency matrix W Rox,, where each entry Way 2 indicates the strength of the connection between the nodes V; and Vj, and p = [V] indicates the total count of nodes. The matrix X Ixxa encodes node features, with each row 2; representing
n-dimensional attribute vector corresponding to V, node, and the label is denoted as Y e p assigns each node one-hot encoded categorical label, representing its
3

---

Published in Transactions on Machine Learning Research (02/2026)
membership in a predefined set of classes. To analyze structural properties such as connectivity or spectral characteristics the graph, we employ the combinatorial Laplacian matrix = D - W, where is the degree matrix. The Laplacian is symmotric, positive semidefinite, and has zero row sums, making it useful for computational tasks such as graph compression, embedding, manifold learning and spectral preservation. It satisfies by -W for + J. while diagonal elements represent node degrees. The set of all feasible combinatorial graph Laplacians L is defined
f = 10 E RPx θ = ,i, 50 for i
Σos) J#1
(1)
However, directly analyzing large-scale graphs computationally expensive, which requires reducing their size while retaining structural properties. In the next subsection, we discuss graph coarsening in detail.
2.2 Graph Coarsening
Graph coarsening aims to construct a smaller and tractable graph G. = Wex with k nodes from a larger graph G = (V, F, W, x, Y) with p nodes, while preserving structural and featural properties of the original graph, where < p. Each node in Ge referred to as a supernode, represents a merging of nodes from G grouped based on shared attributes or structural similarities. The coarsening process aims construct a mapping matrix C e 12a*k, where Ciy signifies that the i-th node of the original graph G is mapped to the j-th supernode of the coarsened graph Ge- This mapping adheres to many-to-one relationship, each node in G is assigned to exactly one supernode in Ge while preserving an orthogonal structure among the supernodes. The matrix C' lies in the following set S.:
S. = (C=(CERP" RRE
- 0Vj 4 (C = dj. |1 2 1, Cj E ER; || 1, [C E ER
(2) Here, Cy.Cr) denotes the standard inner product the vectors Cj and Cj., |Cy]lo denotes the number of non-zero entries of a vector (the fo-norm), Cj and Cj, denote the j-th and j'-th columns, and [ represents the j-th row of of the loading matrix C. The orthogonality condition (C,,Cy) that the columns of C are mutually orthogonal. This condition leads (C,, C3) d, captures the aggregated contribution of the nodes assigned to the j-th supernode; second, the constraint lell 1 enforces that each row of C contains exactly one non-zero entry, mcaning that cach node in the original graph is associated with a single supernode in the coarsened graph, thereby implementing a hard assignment.
ensures constraints: first, the identity
Let P E R denote the coarsening matrix, which serves as the Jinverse of the loading matrix C. That is, we define P = Ct, where Cf is the Moore-Penree Penrose pseudoinverse C. This matrix enables the reconstruction (or projection) of coarse-level representations back to the original graph domain. The Laplacian matrix of the original graph O, the Laplacian matrix of the coarsened graph +,, the feature matrix of the original graph X and the feature matrix of the coarsened graph Xe, logether satisfy the following relations such as:
+, CTOC, PX, C=Pi,
Y. arg PongmaxPPP
6.7
6.30
0.20
Graph Coarsening
8,2
wyF 5
10
62
0:1
0.53
0.26
2.5
0.36
0.25
Figure 1: Illustration of the graph coarsening process on small example.

---

Published in Transactions on Machine Learning Research (02/2026)
We demonstrates how node grouping of simple graph G with six nodes V = (V1, V2, V3, V4, V3. Va through the assignment matrix θ E IR366 leads to reducedddimmnssonal graph G. with nodes V. = (V1, V2, V3} and where each node is assigned a two-dimensional feature vector. The coarsening matrix P is defined below and its pseudoinverse calculated using = Pt. The feature matrii E RR and its coarsened feature matrix X _ax² calculated using X PX,, as shown in equation (I). Now the original and coarsened Laplacian matrices θ E R6x6 and O E R 3x3 computed as O CC:
9
-3
-5
0
0
-1
3
-2
0
0
0
-5
P
θ
3
2
0
-4
0
and θ, = CTOC===
-4 14
-10
(4)
15
-4
-10 15
0
0
-4
-4
15
-7
0
0
-6
-7
13
To ensure meaningful coarsening, modern methods optimize the mapping matrix C' under constraints such as sparsity, orthogonality, and balance among supernodes. These techniques incorporate the characteristic matrix X, and in some cases, both X and the label information Y, together with the adjacency matrix, to gencrate coarser graphs more informative. The resulting graph facilitates downstream tasks while maintain- ing the structural and spectral fidelity of the original graph.
2.3 Proposed Problem Formulation
Given weighted adjacency matrix W Rex and feature matrix X E R corresponding to the node set V (Vi V2,..., 1/}} of the original graph, model the graph coarsening problem as cooperative game. In this formulation, graph nodes are treated as players, and the edges associated with each node define the possible actions available to that player. The game aims to study how groups of players (nodes) form coalitions (supernodes) to achieve a common goal and fairly distribute outcomes among the players. Throughout this paper, we use the lerms player and node interchangeabll. The goal of each coalition this cooperative game is minimize the cost of each player. The objective is to determine a set of coalitions S S2..., S,), where cach coalition S; V, that collectively minimizes the overall Dirichlet energy of the coarsened graph and is formulated as
k
min SEST
Σ w
s.t. ST
S SIUs, 1=1
V, -
(5a)
S,S i<j
Wij
Wuys
34
Tei
Vi Vi, Vu, E S path(u, v) S
(5b)
S.
PES,
V
where each S. S denotes a subset of nodes mapped to a corresponding supernode V, and here represents the ith supernode. The term Wij refers to the (i,j)-th entry of the original graph weight matrix W, while wiy denotes the (i,j)-th entry of the coarsened weight matrix W., representing the weight of the edge between supernodes VÚ and Vj. Similarly, æ; denotes the i-th row of the original feature matrix X, and & denotes the i-th row of the coarsened feature matrix Xe, representing the feature vector of the supernode Ve The term || - 12 quantifies the local variation in the feature signal between the supernodes, and the summation aggregates this variation between all pairs of connected supernodes. Here, the summation over < j ensures that each coarsened edge is counted exactly once in the global dirichlet energy. The constraint Sf defines the coalition structure, ensuring a complete and disjoint partition of the node set V into h subsets. [S,] is the cardinality (size) of the nodes in set S. The path(u, v) defines the length of the shortest path between two nodes and within the same subset S, and constraint by most two in the original graph. This constraint ensures that each coalition forms a connected subgraph with mutual reachability. By minimizing the objective function defined in cquation (5a), the resulting supernodes exhibit smooth variations and preserve the structure the original graph while ensuring energy-efficient coarsening. Minimizing this problem is NP-hard, as it generalizes diameter-constrained graph partitioning as described in (Zhang al.).. We formulate the graph coarsening task as a cooperative game such that set of coalitions S (S1, S2..... S by incorporating structural constraints. This new interpretation enables game-theoretis reasoning over graph structures. The formal definition of this game is presented in the next subsection.
5

---

Published in Transactions on Machine Learning Research (02/2026)
2.4 Game setup
In this work, apply cooperative game theory to address the problem of graph coarsening. Cooperative game theory, as defined by (v Neumann & Morgenstern, 1953), is mathematical framework in which group of players interacts to achieve a common goal by forming coalitions based on binding agreements. We adopt this framework to model graph coarsening as game, defined as CGame = (N, v), where N = 21.2...... denotes the set of players (graph nodes), and v is the characteristic function that assigns a transferable total cost. value each leasible coalition. Each player E has a feature veclor xy and a neighborhood set AG, consisting of all nodes connected to i. The members of the set A, will be the potential collaborators of player for coalition formation, from which a feasible subset can be selected based on cost and structural constraints. To model coalition dynamics and cost distribution in the CGame framework, characteristic function, and player cost. The mapping profile is defined as a tuple m = (m1, 122, :.)). where each m, indicates the coalition S E S to which node is assigned based on the merging decision. This mapping induces a set of supernodes V. - (V, V2...., VeJ, where is the number of distinct coalitions formed. The profile m thus specifies the complete node-to-supen sod--to-uuperode assignment. For a particular node i, the mapping can be expressed as (m,, m-:), where m-s represents the mapping decisions of all nodes except i. The of nodes assigned to coalition S; under mapping m is denoted by R3; and the coalition S; excluding node j under mapping m is represented by Rg, (j)- The characteristic function of Rg is defined as:
define the mapping profile,
DE R
if RSS
e (RS))
(6)
EjERY, C3 (1)
if Rg >
where, DE Rm
ue 1&x B.11?
cS (J) = DE((EE(L) R DE(RS) \ f/)
(7)
2
(u,
Where, (E(R)) represents the contribution of Dirichlet energy of the th supernode coalition S, formed under the mapping profile m and cg, (j) denotes the cost of node E Rgg, defined as the marginal increase in Dirichlet energy due to its presence in coaliton S. Ess, denotes the set of edges connected to the ith supernode corresponding to coalition S; on the coarsened graph. Since each edge is incident to exactly two supernodes, the factor 1/2 guarantees that each edge contributes exactly once to the global energy.
Given the characteristic function e and the individual player cost c(j) in terms of cost, we now analyze the strategic behavior of players to reach the convergence state the game, or a stable coalition structure. A coalition structure is considered stable if it satisfies two conditions: internal stability and external stability.
Refinement-
Refinement
Node RRelinement
10
1! Leader
2nd Leader
kth Leader
K- Hop Coarsened Graph
Original Graph
Potential Coalitions
1- Hop Coarsened Graph
Figure The figure illustrates the step-by-step process of cooperative game-based graph coarsening, It depicts coalition formation based on degree (as leaders), followed by refinement using the cost of each node within coalition to achieve stability. The input to the CGC algorithm is the original graph G(V, F, X, Y)Y). where some nodes may not have label information.

---

Published in Transactions on Machine Learning Research (02/2026)
A coalition is internally stable if no subset of its members can decrease their total allocated cost by deviating to form a new coalition, as expressed in equation (8)
Easo(T), VC
(8)
IE
A coalition is externally stable if no player has an incentive to deviate from their current coalition to join another feasible coalition. Let Т; represent the set feasible coalitions available to the player i, that is, coalitions for which the player's inclusion does not increase their cost or violate coalition constraints. Then, the optimal strategy for the player i, denoted by m defined as the best response that minimizes their individual cost, as shown in equation 9
m arg min (m,, m-i) m,eT
(9)
where 6; denotes the cost allocated player i, which can be expressed as a function c(mm, m-x) representing the cost when player seleets the mapping m, while others choose fixed profile m--;- Here, u(T) is the
value of subset T given by the characteristic function. In the next. subsection, we present the CGC algorithm that ensures convergence to this equilibrium state.
3 ALGORITHM DEVELOPMENT
In CGame, each player joins a coalition to minimize individual cost with respect to the current coalition structure. The contribution of each player within coalition then computed. Players follow best-response decisions, leading the system to converge toward stable coalition structure where no player has an incentive to deviate. To implement this process, we introduce the cooperative game- based graph coarsening (CGC) algorithm.
Given graph G X.) with weighted ad- jacency matrix W E R and node features X E RIV x CGC algorithm employs an iteralive procedure to minimize the cost of each player and converge to a stable coalition structure (i.c., a par- tition of the node set V into disjoint coalitions) as described in algorithm 1 The algorithm begins by initializing each node as a singleton coalition, where its Dirichlet-cnergy cost DE is computed according to equation 7 (line 2). The set S_coalition is ini- tialized as empty to track nodes already assigned to multi-node coalitions, preventing them from being reconsidered as leaders. The set leaderSet stores the nodes selected coalition leaders during the first itcration and is subsequently reused in later it- erations. The array c_cost stores the initial DE values for each singleton node, while c s_update holds the updated player costs during the evaluation of candidate coalitions S,-
A Algorithm 1 Cooperative game-based graph coars- ening (CGC) using one- hop neighbor exploration
1: Inpuu: Graph G(V, E, X)
2: Initialize: Ccost < {i DE[i, vi E V., Cupdate
Cenet, S (fi), vi E V), Scoalition + 0, leaderSet
3: Sort V by degree in descending order
4: repeat
Sprev
if leaderSet 0 then V leaderSet for each node i do if i & Scoalition and has edges then S. (x) neighbors(()
10:
Compute each node cost cs, (j) for all j c St (equation 0 and
11:
set coalition cost v(S.) = Eyes, 6s, (7) (equa-
tion
12:
e(S.) < <Eee,, Ccost()) then for each node E S do
13:
14:
if es, (1) Cupdate (J) then Remove from
15:
end for else S, +
16:
In the coalition formation step, we begin by form- ing a local coalition with a node and its neighbors. To check the stability of this coalition, we evalu- ate whether any individual node or group of nodes
17:
end
18:
then IcaderSet < leader Set U (3), Scoalition <- Scoalition U S, update S, Cupdate
|Sa
19:
end
20:
end for
within the coalition has an incentive to deviate and form a separate coalition that would reduce their cost as defined in equation 7
21:
until S = Sprev
22: Output: Loading matrix C (constructed based on S)
This requires checking whether any subset of the current coalition deviate as best response to obtain lower cost. However, exhaustively evaluating all subsets is computationally expensive for large coalitions.

---

Published in Transactions on Machine Learning Research (02/2026)
Leager
(a) All Possible Deviating Subcoalitions the 1-Hop Neighborhoods of Nodes 1, 5, and 6 (Without Leader-
(b) All Possible Deviating Subcoalitions in the 1-Hop Neighborhoods of Nodes 1, 5, and 6 Baased For- mation)
Based Formation)
Figure 3: Comparison of possible internal deviations in coalitions formed using leaderless and beader-based methods. Circles indicate all possible subgroups that can break the coalition, while dotted circles highlight nodes that may deviate into alternate coalitions.
To improve convergence speed and emphasize structurally important nodes, we incorporate a leader-based coalition formation strategy. In this strategy, a coalition is only valid if it inchudes a designated leader; otherwise, it is discarded. The nodes with the highest degree of centrality are prioritized as leaders, ensuring that highly connected nodes initiate the formation of coalitions.
The formation process commences by sorting the nodes in descending order of degree (line 3), since high- degree nodes are more influential in the network, and their early consideration ensures that major connectivity hubs are prioritized during coalition formation. Then each node is sequentially evaluated as a potential leader. A potential leader attempts to form a preliminary coalition by selecting its immediate one-hop neighbors St. The feasibility of potential coalition S is evaluated by checking whether v(S,) < Exes, e((i)), i.e. its total cost is less than or equal to the sum of the costs of its members when acting individually. If S is not feasible, the potential leader is retained as a singleton coalition, and the algorithm proceeds to the next leader. Otherwise, if S feasible, the tentative coalition undergoes a refinement phase (lines 17 17-21), where each node's individual cost is compared against its previous configuration, whether as singleton or part of another coalition. Only nodes whose cost is reduced by joining the coalition are retained. If the refined coalition contains more than one member, it is accepted, and the init node is confirmed as the coalition leader (lines 17). The next leader is selected from the remaining nodes in the sorted list, skipping those already assigned to an existing multinode coalition (line 8).
In con-leader-based coalition refinement, the problem involves exploring all possible subsets of a coalition to check for deviations. We consider the Stable Coalition problem, which asks whether there exists a coalition satisfying the internal stability condition, as defined in equation this problem is NP-complete. To illustrate the efficiency of our approach, consider the example shown in Figure 3a In the leader-based coalition refinement, we adopt heuristic approach to assess the Stable Coalition condition. Checking the stability of single coalition requires 0(A) comparisons (one for each neighboring node). Checking all & coalitions requires O(k A) total comparisons, where A is the average degree and & is the number of coalitions. This improvement is illustrated in Figure 3b with further details provided in Appendix A.2 The performance in leader-based coalition formation will not be affected. Once the coalition cost is distributed among players, cach player can unilatcrally deviate under best-response dynamics whenever it is beneficial. Moreover, each such deviation decreases the overall syster cost, as demonstrated in the next subsection, where we prove that this game potential game.
We prove in Theorem [ that
Theorem 1. The Stable Coalition prohlem is NP-complete.
Proof. The proof of Theorem has been given in Appendix A.1
The cost allocated to an individual node j within a candidate coalition S., denoted by cs. (f), is computed using the Dirichlet energy based marginal contribution defined in equation 7 which measures the incremen- tal impact of node j on the total value of the coalition (line 10). After computing the costs, each node finds its best mapping decision according its previous configuratinn, it is removed from the coalition. This ensures that participation is beneficial and rational for all members of the final coalition structure. Finally, during the update of the coalition structure
equation (8). If its cost within the coalition exceeds the cost from
8

---

Published in Transactions on Machine Learning Research (02/2026)
S, all nodes in St are removed from the existing coalition set S, and the refined coalition S; is inserted back into S as a new coalition and c s_update stores the updated player costs inside the candidate coalition Si- As per algorithm 1 the entire process is repeated iteratively until the coalition structure 5 reaches oquilibrium, where no further beneficial changes in the mapping decision are possible, with Sprev denoting the coalition structure from the previous iteration used to check convergence. At this point, the configuration considered stable node has incentive to switch coalitions, leave, form new coalitions.
The proposed method dynamically determines the final size of the coarsened graph based on the number of coalitions formed at the stable state. To enable deeper reductions while preserving structural locality, extend approach via recursive multi-level strategy. In this setting, the coarsened graph from one iteration of the CGC algorithm | becomes the input for the next. In this setting, the coarsened graph from one iteration of the CGC algorithm | becomes the input for the next. The features of the coarsened graph at each level calculated using X. PX. Although each level performs only one-hop neighborhood exploration, the overall effect of such itcrations achieves an effective k-hop coarsening of the original graph. The algorithm for multi-level coarsening is provided in Appendix A.4
Table 1: Performance comparison across different GNN mod- cls (GCN, GAT, APPNP) datasets including Cora, DBLP, CoCS, Pubmed, Co-Physics, Genius, and OGBN-Arxiv, un- der various coarsening ratios using the proposed CGC algo- rithm. Each value represents the mcan accuracy + standard deviation over 10 runs.
4 ANALYSIS OF THE ALGORITHM
4.1 Theoretical Analysis
This section analyzes the convergence of the CGC algorithm an equilibrium state (where no coalition reduce the cost by unilateral deviation) within CGame. To as- sess the existence of an equilibrium, it is es- sential to examine the convergence behav- for of the CGC algorithm. This can be achieved by demoustrating that the CGC algorithm of CGame constitutes a potential game. Before presenting the proof, we first introduce the concept of a potential game and define the potential function used in our analysis.
Dataset
r=k/p
GCN
GAT
APPNP
Cora
0.21
87.96 + 0.05
86.71
0.02
89.07 + 0.03
0.07
82,00
0.23
81.75 = 0.12
$1.00
0.06
84.97 + 0.08
DBLP
0.05
80.74 + 0.06
0.05 83.20
83.43 + 0.04
0.01
76.77 = 0.08
80.24
0.05
0.14
92.53 4 0.09
89.36 0.07
93.47 +: 0.05
CoCS
0.03
91.13 = 0.03
88.34
0.04
91.15 0.02
0.01
85.66 + 0.05
$3.82 0.06
88.27 + 0.03
0.235
86.84 + 0.04
78.63
0.05
85.22 + 0.06
Pubmed
1.
76.20
0.02
83.41 + 0.09
0.07 78.31
83.99 + 0.05
0.09
94.79 1 0.11
92.11
0.10
95.85
0.08
Co-Physirs
0.01
95. 1 0.02
93.51
95.14 0.01
0.005
92.43 + 0.07
0.05 92.03
93.94 + 0.04
80.00 1 0.03
79.84
79.78
Genius
0.02
79.97 + 0.08
79.98
0.04
79.96 + 0.09
0.009
79.91 1 0.14
0.00 80.00
79.15
1.34
0.007
78.63 + 0.03
80.00
79.60
0.73
0.15
53.83 1 0.23
0.13 51.14
51.07
1 0.20
52.81 + 0.33
49.87
49.92
OGBN-Arxiv
0.01
50.91 - 0.42
48.06
0.28
47.93 + 0.58
0.004
46.86
1 0.50
45.21 0.28
45.13 4 0.58
0.001
42.01
0.56
40.44
0.58
39.25 1.29
Definition 1. Potential Game A cooperative game can be vegorded a polential game if there exists global scalor function 2, called the potential function, that captures the alignment of individual cost changes with a collective objective. Formally, for any player i E N, and any two mapping decisions m,, m² E Ai, with a fixed mapping configuration of other players m_ E II Aj, the following implication holds:
ea ca(ml, m..) ca m- 5O
@(m4, m-:) $ $0
(10)
where, G represents the cost incurred by node i. This condition ensures that a reduction in an individ- ual node's 's cost. corresponds to a non-increasing global potential, thereby aligning local choices with a global optimization goal.
The total potential of the CGame can be evaluated by aggregating the individual potentials of each coalition. When node is mapped to a coalition, it incurs cost c, which contributes the coalition's potential. Accordingly, we compute the potential of each coalition. The potential of coalition St under mapping profile m, denoted by ((Hg)) is defined as follows:
9

---

Published in Transactions on Machine Learning Research (02/2026)
Detaset
DRLP
PubMedd
17.5
Orgini3--p 9--3)
15.0
(rik)1))
12.5
FGC (w022))
009
10.0
LAGC (nd
120
FH000
9-62X
100
9-2000
20-
2.5
0.0
30
20
25
10
20
Ogenwilae EdRI. Scralier
(a) Cora
(b) DBLP
(c) Pubmed
Physis
120
203
(30
153
60
111
103
93-
(d) CoCS
(e) Co-Physics
(f) e-similarity
Figure 4: This figure plots the top 40 eigenvalues of the Laplacian matrix for both the original and coarsened
graphs across various datasets: (a) Cora, (b) DBLP, (c) PubMed, (d) CoCS, and (e) Co-Physics, under different coarsening ratios. Figure (f) shows the corresponding e-similarity values for the same datasets. The values of c, which range from 0 1, shows the similarity between the original graph G and the coarse graph Ge generated by the proposed CGC algorithm, with lower values implying higher structural similarity.
Calculation of Coalition-Level Potential: Given a coalition S under a specific mapping profile m, its potential contribution o( defined as:
( DE(R))
Σ
Wevl 1 Tz
(11)
where Es, denotes the set of edges connected to the ith supernode (coalition S:) on the coarsened graph, Wuv is the weight on edge (u, v), and Fa, Fo are feature vector of supernodes u and under m.
Global Potential 2(m): Let S (S), , S represent the set of all coalitions. This global potential aggregates the contributions of all coalitions, providing holistic measure of the graph reduction configu- ration. coincides with the Dirichlet energy objective given in equation (5). Since each coarsened edge is incident to exactly two supernodes, the factor 1 ensures correct edge accounting when coalition-level potentials are aggregated. The total potential of CGame under mapping profile m is given by:
2
((m) =
of R
Σ S,ES
Σ (u,o)EEs,
Tuv 11 - 11113
Σ S, i<3
wis 1 2,
(12)
2
S
where, ((R3)) is the Coalition-Level Potential as defined in equation
11
Theorem 2. The function (mm) satisfies the conditions of potential function. Therefore, CGame con- stitutes a potential game.
Proof. The proof of Theorem has been given in Appendix A.7
Theorem 3. At least one Pure Nash Equilibrium. (PNE) is ensured in the proposed CGame framework when operating under the CGC algorithm.
Proof. The proof of Theorem has been given in Appendix A.7
10

---

Published in Transactions on Machine Learning Research (02/2026)
Table 2: Node classification accuracy on various real-world datasets using the proposed CGC algorithm, compared against slate-of-the-arl methods SCAL, FGC, and LAGC. Experiments conducted under different coarsening ratios (r k/p). Each value represents the mean accuracy + standard deviation computed over 10 runs. The results demonstrate that CGC consistently achieves superior performance across wide range of datasets and coarsening levels. OOM indicates cases where execution exceeded memory.
k/p
SCAL
LAGC
CGC
Whole
CORA
0.21
80.05
1.U2
83.33
= 0.02
84.01
1 0.13
S7.96 = 0.32
89.50
0.05
54.07
0.94
67.98 + 1.77
71.73
0.13
80.57 :: 0.21
0.23
75.09
81.47 0.13
81.31 0.75
81.75 0.51
DELP
0.05
76.38 + 1.83
74.75 + 0.10
75.53 0.65
80.74 + 0.43
85.35 + 0.86
0.01
68.70
4.50
69.28 = 0.06
69:90 0.69
76.77 = 0.12
0.14
81.41 3.15
91.37 + 0.00
90.01 0.82
92.53 + 0.67
CO-CS
0.03
50.46 5.43
78.74 + 0.04
84.71 0.25
91.13 = 0.31
93.32 # 0.62
25.20 7.32
77.29
0.235
78.02 0.48
81.71 1 0.09
83.21 0.71
86.84 = 0.11
PUBMED
0.07
73.73 0.90
89.37 + 0.06
77.24 0.81
86.02 0.28
88.89 d: 0.57
0.02
64.71 4.08
71.10
76.37 0.05
83.41 0.72
0.09
90.68 1: 1.03
87.25 1 0.40
87.11 0.03
94.79 1 0.19
CO-PHYSICS
0.01
31.08 + 10.02
91.38
0.12
91.11 0.19
96.22 0.74
0.005
24.92 2.97
88.01 + 0.29
89.26 0.03
92.43 = 0.58
0.06
79.99 = 0.11
OOM
OOM
80.00 = 0.03
OOM
Genius
0.009
79.98 0.09
OOM
OOM
79.91 + 0.14
86.71 4: 0.12
0.007
79.99
OOM
78.63
0.15
27.50 1.41
0OM 16.05 + 0.06
OOM
53.83 0.23
0.04
7.55 + 0.25
29.79 0.09
52.81 - 0.33
OGBN-Arxiv
0.01
5.86 0.00
31.00
32.37 0.22
50.91
56.24 0.22
0.004
5.86 + 0.00
22.19 + 0.29
30.45 + 0.88
46.86 + 0.50
0.001
5.86 + 0.00
19.34 = 0.01
25.71 0.68
42.01 0.56
4.2 Numerical Analysis
In this section, we first describe the experimental setup, a detailed overview of the datasets, followed by ana- lyzing the proposed algorithm's experimental results on real graph data sets which evaluate its performance across various graph neural network models, and then compare it with state-of-the-art methods to showcase the effectiveness of the CGC algorithm.
Experimental Setup: Experiments were conducted on a system running Ubuntu 18. 04.04.6 LTS (x86 64) with dual Intel Xeon E5-2630 v4 CPUs (40 logical cores, 2.20 GHz) and 247 GB RAM. Dataset: We have evaluated our method on real-world datasets, including Cora, DBLP, CoCS, PubMed, Co-Physics, OGBN-Arxin and Genius. Detailed data set statistics are provided in Table A.5 in the appendix.
Baseline models: We evaluate the performance of the CGC algorithm (proposed) by its output as a coarsened graph the input for the GNN model for node classification task. To ensure consistency, we adopt GNN architectures similar to those in the baseline study, including GCN (Kipf & Welling 2016), GAT (Veličković et al., 2017), and APPNP (Gasteiger et al., 2018). We compare the performance of the proposed CGC algorithm with statc-of-the-art methods, including SCAL (Huang et al. 2021), FGC (Kumar et al. 2023), and LAGC (Kumar et al.) 2024), in terms of node classification accuracy. Experiments conducted on real-world datasets demonstrate that our model surpasses existing classification accuracy and computational efficiency.
methods both node
Node Classifccation: For the node classification lask, we first apply the proposed CGC algorithm to the original graph G() to obtain a coarsened graph G,(O,, without using any node labels. After obtaining Ge we split the node labels on the original graph into 80% training labels(Yrrain) and 20% testing (obls(((est).. The test labels Yiest completely masked and excluded during label projection. Concretely, construct Ytrain by zeroing out the one-hot label rows of all test. nodes, so Ytrain contains labels only for training nodes. We infer coarse labels via Y. = arg max (Ytrain) (Huang et al.) 2021 Kumar et al.) 2024 2023), where P C++ cnsuring that Y, depends exclusively on training labels with zero contribution from Y Ytest- We then train the Graph Neural Network (GNN) on Ge(O,, ((.9,.Xa, Xe, Yc) and evaluate performance on the 20% test nodes in the original graph, whose labels Yiest were completely excluded during coarsening and are used only for final evaluation. Furthermore, we perform node classification on the original graph and compare the results with those obtained from the coarsened graph. To ensure equitable comparison, we use the same data split, allocating 80% of the node labels for training and the remaining 20% for testing.
11

---

Published in Transactions on Machine Learning Research (02/2026)
It is evident from Table I that the node classification performance remains consistent across different GNN models (GCN, GAT, APPNP) on datasets including Cora, DBLP, CoCS, PubMed, Co-Physics, Genius, and OGBN-Arxiv under various coarsening ratios, demonstrating the robustncss and effectiveness of the proposed CGC algorithm. Furthermore, we compare the node classification performance of the GCN model using our proposed CGC method against state-of- oo-ttf--t-artt approaches including SCAL, FGC, and LAGC. The results, summarized in Table 2 demonstrate that CGC consistently outperforms these bascline methods across various datasets and coarsening ratios. We present robustness studies that complement the results reported in the main paper. These include additional baseline comparison, sensitivity analysis to leader selection, evaluation on heterophilous graphs, comparison with a random node-masking baseline, experiments under reduced label supervision, ablation studies on leader variants, and results on the ogbn-arxiv datasct using the official OGB splits. Overall, CGC shows stable performance across all settings with comprehensive results are in Appendix A.6
To assess the struc- tural preservation of the coarsened graph, we evaluate spectral and smoothness properties using the Relative Eigenvalue Error (REE) and e-similarity metrics. REE is defined q
Structural Properties:
Runtime comparison of the proposed CGC algo- rithm with baseline algorithms SCAL., FGC, and LAGC across various real-world datasets and coarsening ratios (r= k/p). Time(in seconds) includes only the graph coars- ening step. The results demonstrate that CGC is compu- tationally efficient and scales well across different datasets.
Table 3:
as 1 -.:, | measures the spectral de- viation between the original and coarsened Laplacian matrices @ and O₂ over the small- est eigenvalues, where A and \, denote the i-th cigenvalues of θ and θe, respec- tively. Lower REE indicates better spee- tral preservation. It is evident from Fig- ure | that the plots of the top 40 eigen- values of the Laplacian matrix for both the original and coarsened graphs across various datasets (a) Cora, (b) DBLP, (c) PubMed, (d) CoCS, and (e) Co-Physics un- der different coarsening ratios, closely ap- proximate the original spectra and demon- strate improved aligument compared to state- of- the-art algorithms. For smoothness, we adopt a feature-dependent e-similarity no- tion: given the node-feature matrix X, require (r) < tr(X O) < (I + e) tr ex), where TXX) and tr(8T denote the Dirichlet energy of
A.
Dataset
r
SCAL
FGC
LAGC
CGC
0.21
2.28
18.90
9
0.35
Cora
0.05
6.58
7.50
9
0.35
0.23
85.02
2818.14
1980
14
DBLP
0.05
65.96
581.31
309
15
0.01
64.27
169.28
84
15
0.14
23.13
3398.42
1758
13
CoCS
0.03
27.38
704.16
357
15
0.01
45.33
261.51
126
15
0.235
53.37
2609.87
4380
23
Pubmed
0.07
59.75
640.52
569
24
0.02
61.34
167.48
202
24
0.09
58.98
66477.98
10078
58
Co-Physics
0.01
110.38
914.43
585
67
0.005
155.63
634.21
422
67
0.06
17707
7019
0.02
22732
9011 1
Genius
0.009
24251
9613
0.007
24521
9720
0.15
3792
1503
0.04
6506
84388
61262
2579
OGBN-Arxiv
0.01
7258
49139
58341
2877
0.004
7946
15284
14172
2912
0.001
7376
9677
8957
2924
this specific feature signal on the original and coarsened graphs, respectively. This definition measures how well the coarsened graph preserves the energy of the task-relevant feature matrix X, consistent with feature-dependent smoothness evaluation used in recent graph coarsening research Kumar et al. (2023). A smaller c therefore indicates better preservation of the smoothness of X under coarsening. It is evident from Figure (() that the e-similarity values for the DBLP, CoCS, PubMed, and Co-Physics datasets across different coarsening ratios r remain within the valid range [o, 1], indicating reliable smoothness preservation.
Time complexity:
Given a graph with p nodes and an average degree A, the time complexity of the proposed coarsening algorithm is O(p- A k)) where & denotes the number of nodes of the coarsened graph. The per-iteration cost and the convergence bound are provided in Appendix [A.3] This computational efficiency arises from the fact that each node interacts only with its neighbors and that the coarsening process significantly reduces the size of the problem. As demonstrated in Table 3 the proposed CGC algorithm achieves faster execution limes (in seconds) compared to the baseline methods such as SCAL,
12

---

Published in Transactions on Machine Learning Research (02/2026)
FGC, and LAGC in most coarsening ratios. Entries marked "_" indicate baseline runs that failed due to out-of-memory (OOM).
5 CONCLUSION
This paper introduced the CGC algorithm, a cooperative game-theoretic approach to graph coarsening that utilizes node features and the weighted adjacency matrix. We defined the coalition cost using the Dirichlet energy. We measured each player's cost as its marginal contribution, which the change in energy that results from including or excluding the player from the coalition. We formally proved that the CGC algorithm operates within the CGame framework Since the potential function is defined as the sum of Dirichlet energies of all coalitions, the final stable state corresponds to a minimum total energy configuration. Empirical results on node classification tasks show that our method achieves superior accuracy and significantly lower coarsening time than mtate-of-the-all baselines. Overall, the CGC algorithm provides a computationally efficient and effective solution for graph coarsening, demonstrating both theoretical soundness and practical advantages.
potential game, guaranteeing convergence to stable solution.
References
Renzo Angles and Claudio Gutierrez. Survey of graph database models. ACM compuling surveys (CSUR), 40(1):1-39, 2008.
Walid Ben-Ameur, Ali Ridha Mahjoub, and José Neto. The maximum cut problem. Paradigms of Combi- natorial Oplimization: Problems and New Approaches, pp. 131 172, 2014.
Gecia Bravo Hermsdorff and Lee Gunderson. A unifying framework for cation and coarsening. Advances in Neural Information Processing Systems, 32, 2019.
graph sparsifi-
Zhan Bu, Jie Cao, Hui-Jia Li, Guangliang Gao, and Haicheng Tao. Gleam: A graph clustering framework based on potential game optimization for large-scale social networks. Knowledge and Information Systems, 55(3):741-777, 2018.
Jie Chen, Yousef Saad, and Zechen Zhang, Graph coarsening: from scientific computing to machine learning. SeMA Journal, 79(1):187 223, 2022.
Gabriele Corso, Hannes Stark, Stefanie Jegelka, Tommi Jaakkola, and Regina Barzilay. Graph neural networks. Nature Reviews Methods Primers, 4(1):17, 2024.
Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis. Weighted graph cuts without cigenvectors a multilevel approach. IEEE transactions on pattern analysis and machine intelligence, 29111) 2007.
Charles Dickens, Fdward Huang, Aishwarya Reganti, Jiong Zhu, Karthik Subbian, and Danai Koutra. Graph coarsening via convolution matching for scalable graph neural network training. In Companion Proceedings of the ACM on Web Conference 2024, pp. 1502-1510, 2024.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural nerwsrks for social recommendation. In The world wide web conference, pp. 417-426, 2019.
Wai Shing Fung, Ramesh Hariharan, Nicholas JA Harvey, and Debmalya Panigrahi. A general framework for graph sparsification. In Proceedings of the forly-thrrd annuaal ACM symposium on Theory of compuling, pp. 71-80, 2011.
Xinyi Gao, Junliang Yu, Tong Chen, Guanhua Ye, Wentao Zhang, and Hongzhi Yin. Graph condensation: A survey. IEEE Trunsactions Knowledge and Data Engineering, 2025.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. orXiv preprint arXiv:1810.0580 2018.
13

---

Published in Transactions on Machine Learning Research (02/2026)
Zengfeng Huang, Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou. Scaling up graph neural networks via graph coarsening. In Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, pp. 684, 2021.
Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph condensation for graph neural networks. arXiv preprint arxiv:21 10.010...0. 07580, 2021.
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing, 2011)335--9,, 1998a.
George Karypis and Vipin Kumar. A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. University of Minnesota, Department of Computer Science and Engineering, Army HPC Research Center, Minneupolis, MN, 38:7-1, 1998b.
Thomas N Kipl and Max Welling. Semi-supervised classification with graph convolutional networks. arviv preprint Xix::1609 02907, 2016.
Manoj Kumar, Anurag Sharma, and Sandeep Kumar. unified framework for oplimization-based graph coarsening, Journal of Machine Learning Research, 24(118):1-50, 2023.
Manoj Kumar, Subhanu Halder, Archit Kane, Ruchir Gupta, and Sandeep Kumar. Optimization framework for semi-supervised attributed graph coarsening. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024.
Mayank Kumar and Ruchir Gupta. Overlapping attributed graph clustering using mixed strategy games. Applied Intelligence, 51(5):5299 5313, 2021.
Hui-Jia Li, Yuhao Feng, Chengyi Xia, and Jie Cao. Overlapping graph clustering in attributed networks via generalized cluster potential game. ACM Transactions on Knowledge Discovery from Data, 18(1):1-26, 2024.
Jiayu Li, Tianyun Zhang, Hao Tian, Shengmin Jin, Makan Fardad, and Reza Zafarani. Graph sparsification with graph convolutional networks. International journal of data science and analytics, pp. 1-14, 2022.
Rui Li, Xin Yuan, Mohsen Radfar, Peter Marendy, Wei Ni, Terrence J O'Brien, and Pablo M Casillas- Espinosa. Graph signal processing, graph neural network and graph learning on biological data: sys- tematic review. IEEE Reviews in Biomedical Engincering, 16:109-135, 2021.
Andreas Loukas. Graph reduction with spectral and cut guarantees. Journal of Machine Learning Research, 201116):1-42, 2019.
Andreas Loukas and Pierre Vandergheynst. Spectrally approximating large graphs with smaller graphs. In International conference on machine learning, pp. 3237 3246. PMLR, 2018.
Supreet Mandala, Soundar Kumara, and Kalyan Chatterjee. A game-theoretic approach to graph clustering. INFORMS Journal on Compuling, 26(3):629 643, 2014.
Dov Monderer and Lloyd S Shapley. Potential games. Games and economic behavior, 14(1):124 143, 1996.
Jennifer Neville and David Jensen. Relational dependency networks. Journal of Machine Learning Research, 8(3), 2007.
Saced Rahmani, Asiye Baghbani, Nizar Bouguila, and Zachary Patterson. Graph neural networks for intelli- gent transportation systems: A survey. IEEE Transactions on Intelligent Transportation Systems, 24(8): 8846 8885, 2023.
Baoxu Shi and Tim Weninger. Proje: Embedding projection for knowledge graph completion. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
Johann v Neumann and Oskar Morgenstern. Theory of games and economic behavior. Princeton University Press, 1953.
14

---

Published in Transactions on Machine Learning Research (02/2026)
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arxiv preprint arXiv:1710. 10903, 2017.
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. Hcterogeneous graph attention network. In The world wide web conference, pp. 2022-200000 2019.
Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recommender systems: a survey. ACM Computing Surveys, 55(5):1-37, 2022.
Shuyin Xia, Xinjun Ma, Zhiyuan Liu, Cheng Liu, Sen Zhao, and Guoyin Wang. Graph coarsening via supervised gramular-ball for scalable graph neural network training. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 12872 12880, 2025.
Zhenbang Xiao, Yu Wang, Shunyu Liu, Huiqiong Wang, Mingli Song, and Tongya Zheng, Simple graph condensation. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 53 71. Springer, 2024.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchi- cal graph representation learning with differentiable pooling, Advances in neural information processing systems, 31, 2018.
Jack Zhang, Lucas Silveira, Hamidreza Validi, Logan Smith, Austin Buchanan, and Illaa Hicks. Partition- ing graph into low-diameter clusters.
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. arXiv preprint trXiv:2006.052 05929, 2020.
Chao Zhao, Ali Al-Bashabsheh, and Chung Chan. Game theoretic clustering for finding strong communities. Entropy, 26(3):268, 2024.
Xin Zheng, Miao Zhang, Chunyang Chen, Quoc Viet Hung Nguyen, Xingquan Zhu, and Shirui Pan. Structure-free graph condensation: From large-scale graphs to condensed graph-free data. Advances in Newral Information Processing Systems, 36:6026 6047, 2023.
A Appendix
A.1 NP-Completeness of Coalition Instability Detection in Laa-Ledder--Bsee Refinement
Recall that internal stability (Eq. equation
requires that for a given coalition
Σa S v(T), VTCS, iET
(13)
where a denotes the cost allocated to player i in the current coalition S, and o(T)) is the cost that subset T would incur deviates and forms a standalone coalition.
If there exists some non-emply subset T C S such that
Σ N
a v(),,
then the members of T collectively overpaying relative to their stand-alone worth and have an incentive to deviate; in this case, the coalition S is internally unstable.
15

---

Published in Transactions on Machine Learning Research (02/2026)
Coalition Instability Detection (decision version). Given finite set of players S with allocated
costs {cilies and a characteristic function v(.), does there exist a non-emply subset C S such that the internal-stabiltty inequality equation 13 is violated, i.e.,
Σ < u(T) ET
If such subset ezists, the members Tf have incentive deviate and form their own coalition, making the original coalition S unstable.
We now show that this decision problem is NP-complete.
Proof of Theorem 7 To prove that the Coalition Instability Detection decision problem Q' NP- complete, we must show things: (1) Q' NP and (2) known NP-complete problem can be reduced to Q' in polynomial time.
Step 1: Coalition Instability Detection is in NP. A decision problem is in NP if, for every instance of the problem, a proposed solution (certificate) can be verified in polynomial time. For the Coalition Instability Detection decision problem, certificate is a non-empty subset T C S that is claimed to violate internal stability. To verify this certificate, we need to compute (i) the total cost Σier Cs and (ii) the sub-coalition cost vT)), and then check whether the inequality
Σ ET
> vTT)
holds.
our CGC formulation, the per-player costs and the characteristic function are defined via the Dirichlet energy DE( of a coalition on the coarsened graph ( (qquatonn 0 and equation 7 Let G E) be the underlying fine graph with node features {ouJuev and edge weights {Wue) (x. Each coalition C V induces supernode the coarsened graph, and denote by (S) the set of edges incident to this
supernode on the coarsened graph.
The Dirichlet energy contribution associated with coalition S is then
DE(S) 2
Σ
Dav 1| 10
(s)))
Each term || - 1 can be computed in ((n) time, where n is the feature dimension, and each edge in (S) processed once. Hence, DE(S) can be computed in (S) n) time.
The cost allocated to player j in a coalition given by
cs(i) DE(S) DE(S (i}).
where DE(S) and DE(S \ (f)) are both defined using the corresponding incident-edge sets (S) and E. (S (j)) on the coarsened graph. Thus, computing cs()) requires two Dirichlct-cnorgy ovaluations and is therefore O(E,, n) for each player's cost. Given a fixed coalition S, the total cost of any subset. C S is
Ees(1,
iET
which can be obtained in O(T')) time once the costs (cs(i))ies are available.
The charactoristic function u(-) used in our CGC game is defined in Eqs. equation and equation 7 spe-
cializing those definitions to an arbitrary subset T (corresponding to some coalition supernode), we have
DE(T), Σ JET
TT = 1, it it > 1,
x(T)
cT(),,
16

---

Published in Transactions on Machine Learning Research (02/2026)
where
(r (T(T) DE (i)):
and each DE(() is evaluated using the corresponding incident-edge set (T) on the coarsened graph. As above, cach Dirichlet energy term can be computed in O(IE, n) time, all er()) for T can be obtained in O(IT) (Tx( n) time, and hence v(T) is computable in polynomial time.
Therefore, for any proposed subset T S, both Eier cs (with c; cs(i)) and u(T) (as defined above) be evaluated in time polynomial in the size of the input. The final comparison Σier G > v(T) is constant time. Hence, the Coalition Instability Detection decision problem Q' admits polynomial-tine verification procedure and belongs to the class NP.
Step NP-hardness via reduction from known NP-complete problem. Let Q denote the MAX- CUT decision problem and let Q' denote the COALITION INSTABILITY DETECTION decision problem defined above. We reduce from Q, which is No-complete (Ben- Ameur et al. 2014), and give a polynomial- -imm many-one reduction Q Sp Q'
FV Max-Cut (decision version). Given undirected graph G (V, F) with nonnegative integer edge weights (u,eee) and threshold K N, the MAX-CUT decision problem asks whether there exists a subset U S V such that
(Ut
Σ
Wav 2 K.
(u.r)E weU, UEU
Reduction (Q Sp Q). Given an instance (G, K) of Q, we construct an instance of Q' as follows. Let W E (E,))E Wae denole the total edge weight.
Player set. Define S V U [p], where p dummy player.
Characteristic function. For any coalition T S S, let = TTV and define
T()) = W - cula (U, V VU).
Since the Dirichlet energy of the indicator function fo satisfies {(fv cuto V VV)), this can be written as v(T) = W - {ffu), i.c., an affine transformation of the cut-basod Dirichlet energy.
3. Costs. For all i V, set = 0, and for the dummy player set
C
W K K+
This construction clearly computable in polynomial time |V| + [F].
Equivalence. We now show that the MAX-CUP CUT instance (G,K) is a "yes" instance if and only if the constructed COALITION INSTABILITY DETECTION instance admits violating coalition.
(+) Suppose there exists U C with CU* V U*) 2 K. Consider the coalition U (p). Then
Σ - W K 2
iET
(TT) W cuto(U", V U²) S K-
Нence Eiero W - K+ > W K v(T), T violates internal stability.
17

---

Published in Transactions on Machine Learning Research (02/2026)
(=) Suppose there exists a coalition T S S such that ΣiEr 4 > x(T). p T, then Σier 0, while v(T) = W c (T, V\T) 2 0, so the inequality Σier 4j > v(T) cannot hold. Thus any violating coalition must contain p.
Let T UU for some U - V. Then Eier = Cp = W-K+ v(T) = W - V\U). The violation condition becomes W - > W cututu(U, V\U,, which simplifies to cuta(U, (() > K K- Since cut values are integers, this equivalent to cu, V (U) 2 K, so U a feasible solution to the original MAX-CUT instance.
Conclusion. Since the COALITION INSTABILITY DETECTION problem Q' in NP (Step 1), and known NP-complete problem MAX-CUT Q reduces to polynomial time (Step 2), it follows that Q' is NP- complete.
A.2 Illustrative Example of Coalition Stability
As illustrated in Figure g consider a graph in which three coalitions C1, C2, C3 are formed based on the 1-hop neighborhoods of nodes 1, 5, and 6, respectively. Specifically, for node 1, its local neighborhood includes nodes 2, 3, and 4, resulting the coalition C₁ = 2,, 4). To analyze the stability of these coalitions, we consider two approaches: first, the case without Seader-basee refinement, and then the case with leader- based refinement.
In Non-Leader-Based Coalition Refinement, the stability of coalition is evaluated by checking whether any individual node group of nodes has incentive to deviate. Evaluating stability in this way requires examining all possible non-empty subsets of the coalition. For C1, which contains four nodes, the maximum number of non-empty subsets to consider is 24 1 = 15. However, as shown in Figure 3a only 11 subsets are obscrved to deviate since C2 not a fully connected clique. When the nodes a coalition are fully con- nected, the deviation ceeiation-checking process corresponds to the Stable Coalition problem, which is NP-complete, as established Theorem
In the leader-based coalition refinement, nodes 1,5, 6 are selected as leaders, as shown in Figure 3b and form coalitions with all their neighbors. In the refinement step, each neighbor a, is individually checked to decide whether it should (i) remain in the leader's coalition, (fi) leave to join another coalition led by different leader, (iii) remain unassigned if no better option is available. This requires only 6 checks, one per neighbor, resulting in linear time complexity. This localized refinement procedure generalizes efficiently across the entire graph. Let & denote the number of leaders (at most k), and d, the number of neighbors of leader i. The total number of comparisons to chock stability across all leader- coalitions is O 1= d:). Since Em di k. A, where A the average degree of the graph, the overall comparison cost O A).
A.3 Complexity and Convergence Analysis
Per-iteration complexity. One ileration corresponds to a full sweep over all leaders, that is, al most k leader updates. Each leader considers at most A one-hop neighbors. Evaluating all marginal costs inside a candidate coalition requires O(A²) computation, and checking membership or updating assignments adds O(pA), The per-iteration cost is therefore (k{A2² + +A)). Since p > A, the dominant term OOkp A).
Convergence bound. CGC induces a finite exact potential game: every accepted coalition update pro- duces the same decrease in the global potential in the individual player's cost, and the potential is non-negative Dirichlet-energy quantity. Hence the potential cannot decrease indefinitely, and only finitely
18

---

Published in Transactions on Machine Learning Research (02/2026)
many improving deviations are possible, so the repeat repeat-until loop converges to pure Nash equilibrium (PNE) in finitely many steps.
More concretely, after the first full sweep over the nodes, the leader set stabilizes and contains exactly k leaders. In the subsequent dynamics, only the remaining p - & follower nodes may change their coalition, and each such move strictly decreases the Dirichlet-ence energy potential. Since each follower can choose among at most & leaders, a follower can switch coalitions at most (k- 1) times. Hence, the total number of accepted coalition updates is bounded by (p- (o-k)(k: 1) O(pk). Under our update schedule, each iteration processes at most & leaders, the number of iterations until convergence is most O(pk/k) O(p), while the total number of nove-level updates is O(pk), which in the worst case (k S p) is at most quadratic, O(p"), in the number of nodes.
A.4 Multi-Level CGC Algorithm
Algorithm 2 Multi-Level CGC Algortihm based Graph Coarsening
Require: Original graph G (V, E,),, number of coarsening levels k Ensure: Coarsened graph (kk)
1: (()) <- G
2: for i= to k do
3: Apply CGC algorithm ! on (i-
4: Obtain coarsened graph G(
end for
return (k))
A.5 Additional Dataset Details
Dataset
number of nodes
features
levels
Cora
2,704
1,433
DBLP
17,716
1,639
CoCS
18,333
2,000
Pubmed
19,717
500
3
Co-Physics
34,493
8,415
6
OGBN-Arxiv
169343
128
40
Genius
421961
12
Table 4: Details of the real datasets, including the number of nodes p, features n, and levels I,
A.6 Experiments
This section presents supplementary robustness studies that complement the results reported the main paper. These include additional baseline comparison, sensitivity analysis leader selection, evaluation on heterophilous graphs, comparison with a random node-masking baseline, experiments under reduced label supervision, ablation studies on leader variants, and results on the ogbn-arxiv dataset using the official OGB splits.
A.6.1 Additional Baseline Comparison
To ensure fairness and completeness in our empirical evaluation, we additionally compare CGC against several recent and widely used graph coarsening baselines. Specifically, we include the recently proposed structure- guided SGBGC method (Xia et al.) 2025). along with the scalable non- lea-nnnnn approaches HEM (Kryypis &
19

---

Published in Transactions on Machine Learning Research (02/2026)
Table 5: Node classification accuracy of CGC compared with the recent supervisod coarscning method SGBGC and scalable non-learning baselines HEM, Graclus, and METIS across multiple real-world dalasets and coarsening ratios (r k/p). Each value reports the mean accuracy = standard deviation over 10 runs.
Dataset
r= k/p
SGBGC
HEM
Graclus
METIS
CGC
0.21
84.62
0.34
79.88
1.42
81.32 + 0.31
83.31
0.30
87.96 0.32
Cora
0.05
82.67
0.44
30.21
+ 0.00
63.32 _ 2.21
30.21 _ 0.00
80.57 1 0.21
0.23
84.21 + 0.50
75.29 + 2.10
82.30 + 0.16
83.31 + 0.24
84.75 + 0.54
DBLP
0.05
78.72
0.26
66.77
= 2.57
64.65 E 0.41
53.18 = 4.75
80.74 = 0.43
0.01
73.86
0.25
44.71
0.00
44.71 - 0.00
44.71 0.00
76.77 0.12
0.14
92.11 + 0.44
85.76
+ 0.90
90.52 + 0.64
90.94
- 0.48
92.53 - 0.67
CoCS
0.03
91.38 + 0.28
22.56 +: 0.00
60.75 + 2.61
23.77 + 3.30
91.13 + 0.31
0.01
91.25
0.17
22.56 1 0.00
22.56 1 0.00
22.56 + 0.00
85.66 + 0.45
0.235
85.46
0.20
82.04
+ 0.46
84.37 + 0.42
82.97
- 0.27
86.84 - 0.11
PubMed
0.07
83. + 0.15
57.50 + 0.13
81.29 - 0.22
57.30
- 0.38
86.02 = 0.28
0.02
82.45 + 0.31
39.27 +: 0.01
39.27 1 0.01
39.17
1 0.05
83.41 + 0.72
0.09
94.78
0.43
81.57
1.37
16.67 + 0.00
16.67 0.00
94.79
0.19
Co-Physics
0.01
92.56
0.14
50.52
= 0.00
50.52 - 0.00
50.52
= 0.00
94.15
= 0.37
0.005
89.54
+ 0.22
50.52 + 0.00
50.52 - 0.00
50.52 - 0.00
92.43
- 0.58
Kumar 1998a), Graclus [Dhillon et al. 2007 and METIS (Karypis & Kumar 1998b). All baseline models
are exccuted using their publicly available implementations with recommended hyperparameter configura- tions. T node classilaasiiicatoon accuracy under varying coarsening ratios across multiple benchmark datasets. As shown Table 5 CGC consistently outperforms all compared methods across datasets and coarsening levels, with particularly notable gains under stronger compression (smaller k/p).
A.6.2 Sensitivity Analysis of CGC to Leader Selection
We evaluate the sensitivity of CGC to random leader selection on four benchmark datasets (Cora, DBLP, CoCS, and Pubmed) by running CGC multiple times with independently sampled leader sets, while keeping all other settings fixed. For each datasct, we perform multiple independent runs (150 for Cora, 50 for CoCS, and 35 for DBLP and Pubmed) and record the resulting node-classification accuracies. As sunmarized by the histograms in Figure 5a
5b 5c and [d CGC exhibits strong stability under random leader selection across all four datasets. On Cora, 150 runs yicld accuracies ranging from 85.19% to 37.33, with a narrow spread of (range: 0.69%). CoCS shows similar robustness, with 50 runs distributed between 91. 91.80% and 92.77% (range: 0.97%), while Pubmed displays the highest stability, with 35 runs concentrated in the interval 87.13% 87.50% (range: 0.37%). The empirical distributions Figure 5 reveal that the vast majority of runs cluster tightly around the mean accuracy, with very few outliers. This narrow concentration indicates that CGC's performance is highly robust and not strongly dependent the theoretical convergence guarantees apply only to local equilibria, these empirical results demonstrate that different leader selections consistently lead to similar high-quality solutions, suggesting that the local equilibria reached by CGC are of comparable quality across different starting configurations.
2.34 percentage points. On DBLP, 35 runs fall within an even tighter band of 84.36%-85.00
the specific random choice of initial leaders. Although
A.6.3 Evaluation Heterophilous Graphs
CGC is primarily designed for homophilic graph settings where neighboring nodes tend to share similar features and labels, consistent with the Dirichlet-energy objective that encourages merging structurally and semantically aligned nodes. Since the datasets used in our main experiments (e.g., Cora, Citeseer, PubMed, DBLP, Co-CS, Co-Physics, OGBN-Arxiv, Genins) are prodominantly homophilic, we additionally evaluate CGC on two heterophilous benchmarks (Cornell and Texas) to assess robustness beyond this regime. We compare CGC against the classical coarsening baselines HEM, Graclus, and METIS under multiple coarsening ratios (r = k/p), reporting mean accuracy + standard deviation over 10 runs. As shown in Table CGC substantially outperforms all baselines across all coarsening levels, with the performance gap widening under stronger compression (smaller r), where traditional methods degrade to near-random accuracy (>
20

---

Published in Transactions on Machine Learning Research (02/2026)
12
Mean 86.60%
Mean 84.75%
=0.49
Std +0.18
Frequency (#ns))
10
Frequency (#Runs)
4
85.5
86.5 Accuracy (%)
84.6
84.7
84.9
Accuracy (%)
(a) Cora
(b) DBLP
14
Mean 92.35%
5
Mean
Frequency (#Runs)
12
+0.21
Frequency (#Runs)
4
10
Accuracy (%)
Accuracy (%)
(c) CoCS
(d) Pubmed
Figure 5: Distributions of node-llassiffcation accuracy across multiple runs of CGC under random leader selection, based on 150 runs for Cora, 50 for CoCS, and 35 for DBLP and Pubmed. Each histogram reports the sample mean (Hs) and standard deviation (a), highlighting the tight concentration of accuracy values and the robustness of CGC leader selection.
44-56%) while CGC maintains significantly higher accuracy (71-84)). These results demonstrate that CGC remains effective in heterophilous settings and preserves discriminative structural information even under aggressive graph reduction.
Table 6: Node classification accuracy on heterophilous graph datasets (Cornell and Texas), comparing the proposed CGC algorithm against classical graph coarsening baselines HEM, Graclus, and METIS under different coarsening ratios (r k/p). Each value reports the mean accuracy + standard deviation over 10 runs.
Dataset
r k/p 0.23
HEM
Graclus
METIS
CGC
Original
54.10 + 4.25
52.46 + 3.67
53.88 2.38
84.53 t 0.91
Cornell
0.06
44.81 + 0.00
43.61 + 4.25
44.81 + 0.00
79.21 + 1.20
86.90 + 0.56
0.02
44.81 + 0.00
44.81 + 0.00
44.81 + 0.00
71.25 + 2.07
0.23
56.39 + 5.32
61.31 + 2.96
57.05 1.27
84.53 + 0.91
Texas
0.06
55.19 + 0.00
40.11 = 12.08
55.19 0.00
79.21 + 1.20
87.31 + 1.38
0.02
55.19 + 0.00
47.76 + 14.86
55.19 0.00
71.25 + 2.07
21

---

Published in Transactions on Machine Learning Research (02/2026)
A.6.4 Random Mode-Maskinng Baseline
To determine whether the performance gains of CGC arise solely from graph size reduction from the quality of the coarsening mechanism, we implement a random mode-masking baseline that removes nodes uniformly at random to match the coarsened graph size produced by CGC. We run this process 10 times with different random seeds and report mean accuracy standard deviation. As shown Table 7 CGC consistently outperforms random masking across all coarsening ratios, confirming the value of the coalition- based merging strategy over naive downsampling.
Table 7: Node classification comparison of CGC with random node-masking baseline under different coarsening ratios (r k/p). Each value reports the mean accuracy + standard deviation over 10 runs.
Dataset
= k/p
Node Masking Baseline Accuracy
CGC
0.21
44.63 = 6.10
87.96 0.32
Cora
0.05
22.84 + 9.67
80.57 0.21
0.23
77.92 1.33
84.75 0.54
DBLP
0.05
70.16 3.61
80.74 0.43
55.10 16.99
76.77 0.12
0.14
89.08 1.65
92.53 0.67
Co-CS
0.03
83.84 = 3.05
91.13 0.31
0.01
81.42 = 9.92
85.66 0.45
0.235
56.01 = 7.60
86.84 0.11
Pubmed
0.07
36.92 1 14.14
86.02 + 0.28
0.02
31.12 1 17.03
83.41 0.72
0.09
92.01 1.72
94.79 0.19
Co-Physics
0.01
90.36 3.44
94.15 0.37
0.005
79.13 7.25
92.43 0.58
A.6.5 Robustness to Limited Labeled Data
To study the robustness of CGC under reduced label availability, we perform additional experiments using smaller training subsets (30%, 40%, 60%, and 70% of labeled nodes), following the same settings as the main evaluation. The results, presented in Table g show that CGC maintains strong performance across reducod supervision levels, demonstrating that CGC remains effective even with significantly fewer labeled nodes.
A.6.6 Ablation Studies on Leader Variants
To assess the impact key design choices in CGC, we perform ablation studies on two variants: (i) Random- leader initialization and (ii) Random-neighbor merge under restricted hop sizes. In the Random-leades variant, coalition leaders are selected uniformly at random across 10 independent runs, and report the mean node-classification accuracy with the corresponding standard deviation. The value in parentheses indicates the average coarsening ratio = k/p achieved across the 10 runs. In the Random-neighbor merge ablation, each node selects a random neighbor within a limited hop neighborhood for merging, instead of using Dinichlet-cnery--aate marginal contribution, thereby isolating the effect informed coalition formation.
As shown in Table g both variants result in substantial accuracy degradation and increased variance relative to the proposed CGC method, demonstrating the critical role of energy-guided coalition formation and structured leader selection.
A.6.7 Official OGB Splits
We additionally report the performance of CGC on the ogbn-arxiv benchmark using the official data splits provided by the Open Graph Benchmark (OGB). Table [0 summarizes the node-classificatin accuracy of CGC across range of coarsening ratios k/p. The results indicate that CGC retains competitive performance even under aggressive coarsening, with accuracy decreasing gracefully as the ratio is reduced.
22

---

Published in Transactions on Machine Learning Research (02/2026)
Table 8 Node classification accuracy of CGC under different training label ratios (70%, 60%, 40%, and 30%). Each value represents the mean accuracy standard deviation over 10 runs.
Dataset
k/p
70% labels
60% labels
40% labels
30% labels
85.16 = 0.51
85.59
0.48
86.53 0.58
86.99 0.64
Cora
0.2338
82.15
78.67
1.50
67.25
3.12
56.76 3.17
0.0406
77.49 = 1.48
75.76
2.58
73.70
2.49
65.63
3.03
85.73 + 82.49 - 0.29
85.31
0.28
84.91 + 0.13
84.39
0.19
0.23
80.06
0.40
72.98 + 0.53
66.47
0.93
DRLP
0.05
79.54 + 0.50
78.39
0.74
76.65
1 0.81
72.97
0.98
0.01
76.44 1 0.89
76.13
1.64
74.90
1 1.46
72.60
2.29
93.97
1 0.09
93.73
0.24
91.56
1. 0.20
88.32
0.20
CoCS
0.14
90.46 1 0.47
89.26
0.68
82.07 1 2.83
76.87
2.88
0.03
89.77 + 0.42
89.46 1 0.70
87.29 1 0.65
85.63 = 1.74
0.01
84.63 + 0.98
84.20
1.90
83.78 + 1.60
83.06
1.60
87.87 + 0.39
87.76
0.27
86.48 + 0.10
85.34
0.16
0.235
83.20
0.62
77.16
1.44
57.09
1.84
30.27
0.97
PubMed
81.47
78.09
1.43
62.50
49.08
2.62
79.53
77.17
1.85
70.15
1.94
65.48
96.56 + 0.05
96.44
0.08
96.30 + 0.08
96.11 = 0.07
Co-Physics
0.09
93.47
1: 0.40
92.21 1 0.60
87.01 1: 2.32
82.01 : 2.41
0.01
93.50 = 0.37
92.88 + 0.62
90.32 + 1.74
58,00 = 2.46
0.005
91.24 = 1.84
91.36 + 1.55
90.80 + 1.98
90.48 = 1.78
79.97 + 1.05
80.00
0.01
78.97 + 3.05
72.74 4.20
Genius
0.06
78.82 + 12.26
78.29
4.81
77.26 + 5.12
67.15 + 23.
0.02
59.39 + 21.09
48.73
26.56
48.73 + 26.56
45.86
26.97
55.30
53.30
0.17
53.03 1.17
45.31
0.42
OGBN-Arxiv
51.31 + 0.41
48.43
0.56
40.89 + 0.73
22.66
86.99 -
86.53
0.58
85.59 + 0.48
85.16
0.23
82.76 + 1.27
82.76
1.27
67.35 + 2.20
57.49
2.96
Cornell
0.06
78.99
1 1.21
78.55
1.54
74.75 1 2.33
68.46
2.05
0.02
71.31
1.96
70.32
2.82
69.28 1 3.60
67.11
2.60
86.91
+ 0.90
86.72 # 0.71
85.75 + 0.59
85.22 = 0.57
0.23
82.76
1 1:27
79.21
1,26
67.35 1 2.20
57.49 2.96
Texas
0.06
78.99
+ 1.21
78,55
1.54
74.75 + 2.33
68, = 2.05
0.02
71.31
+ 1.96
70.32
2.82
69.28
+ 3.60
67.11 = 2.60
40.25
+ 3.51
31.18
2.50
23.95
0.83
21.35
0.44
0.16
29.33
= 0.71
28.42
0.92
27.71
0.90
26.03 0.85
Squirrel
0.01
30.17
=
28.81
2.13
28.24
1.63
29.33
1.39
0.004
22.95
1
22.07 1.42
22.34
1.32
23.08
Table 9: Ablation study random-leader and random-neighhor variants. Values show mean accuracy and + standard deviation over runs; parentheses denote the average coarsening ratio r = k/p.
Dataset
= k/p
Random-leade (r)
Random-neighbor merge
CGC (Desc) 87.96 = 0.32
Whole Data
0.21
86.90 + 0.92 (0.27)
83.03 = 0.12
Cora
89.50 4 1.20
0.05
79.09 1 1.33 (0.09)
62.35 1 3.23
80.57 1 0.21
0.23
83.45 + 0.33 (0.26)
82.45 = 0.16
84.75 + 0.54
DBLP
0.05
80.24 1 0.16 (0.06)
78.44 1 2.71
80.74 1 0.43
85.35 1 0.86
78.87 + 0.75 (0.02)
68.65 +
76.77 0.12
0.14
92.11 + 0.73 (0.14)
89.68 = 0.38
92.53 = 0.67
CoCS
0.03
90.94 0.44 (0.03)
63.49 = 3.57
91.13 = 0.31
93.32 + 0.62
0.01
88.25 1: 0.83 (0.01)
35.37 +: 1.56
85.66 1 0.45
0.235
86.53 + 0.18 (0.16)
82.40 + 0.32
86.84 = 0.11
PubMed
0.07
85.77 1: 0.39 (0.04)
41.11 + 0.31
86.02 0.28
88.89 1 0.57
0.02
82.93 1 0.67 (0.01)
81.13 + 0.22
83.41 1 0.72
0.09
94.42 + 0.24 (0.09)
88.98 + 0.23
94.79 + 0.19
Co-Physics
0.01
93.88 + 0.49 (0.02)
67.79 = 1.37
94.15 + 0.37
96.22 + 0.74
0.005
92.12 + 0.63 (0.008)
67.20 + 0.30
92.43 + 0.58
23

---

Published in Transactions on Machine Learning Research (02/2026)
Table 10: Node-clasiiiiation accuracy on ogbn- using official OGB splits
Dataset
k/p
CGC Accuracy
ogbn-arxiv
1.0
53.44 = 0.34
ogbn-arxiv
0.15
47.23 = 0.35
ogbn-arxiv
0.04
46.28 0.36
ogbn-arxiv
0.01
44.17 + 0.46
ogbn-arxiv
0.004
41.85 = 0.59
ogbn-arxiv
0.001
38.75 = 0.59
A.7 Theoretical Convergence Guarantee
Proof of Theorem 2 Recall that for each coalition S,, the coalition-level potential (RR)) is defined in equation [1 The global potential is then given by ((m) Sses di (eg)
If the potential function & meets the cost-alignment condition defined in equation 10 then CGame confirms the properties of potential game, where local cost improvements support the minimization of global po- tential. Under CGC algorithm, node i updates its mapping decision from a coalition S; to S at a mapping profile m = (m, m-;), only its cost decreases. Suppose Rgg and Rg are the nodes in coalitions S, and Sy, respectively, before changing the mapping decision. The change in node i's cost due to the transition from coalition S; to S is calculated as:
Ac (m,,,, m-)) (m,, m.) DE(RS; (()) DE(R3) (DE(RS)) DE(RS, \ (t))
(14)
where Aq < O. This inequality holds because a node deviales to Sy only when such a move strictly reduces cost. Formally,
(m m-i) < Ca(m;, m-.) Aq = camm m-;) - Ga (m,, m..) < O.
(15)
Therefore, the update rule ensures that node's cost always decrcases after deviation.
Now, when node updates ils mapping, the value of the potential function changes as follows:
Ao Oine Odec
(16)
where iine represents the increase in Φ and @dec represents the decrease in Φ.
Specifically, when node remapped from coalition Sy, the potential value é of coalition S increases, while the potential value of coalition S, decreases. These changes in & are caleulated follows:
The increase in for the coalition S is:
Óin (RR (i)) (
DE(NS U (ii) D = =m(m,, m.:)
(by equation
11
(by equation
(17)
The decrease in o for the original coalition St is:
daee- ((Rg)) ((R3; (i)) D DE(RY, (i))
(by equation
11
cc(m,,
(by equation
(18)
24

---

Published in Transactions on Machine Learning Research (02/2026)
If the condition Ac; < 0 is satisfied, then from equations 17 and (18). the change in the global potential Åó is equal to the change in the individual cost Δq.- Consequently, A < O, which shows that every locally improving move strictly decreases the global potential. This proves that CGame an exact potential game. Moreover, this equality holds because a unilateral move of node i affects only the coalition it leaves and the coalition it joins, and the global potential is defined as the sum of the corresponding coalition-level Dirichlet energies. As result, the value of Aø decreases monotonically nodes update their mapping decisions according to the CGC algorithm.
Proof of Theorem 3
The presence of PNI is justified using the arguments outlined below.
1. In the proposed CGame, the potential function 6(m) is defined over the set of all possible mapping profiles, where each node selects coalition from its neighbors. Since both the number of nodes and their neighbor sets are finite, the number of mapping profiles and thus the range of @(m) is finite.
2. The game progresses through updates these profiles, with nodes updating their choices based on the CGC algorithm. As shown in Theorem X and above point that this game is finite-ootential game where each update results in a strictly decreasing value of @(m), preventing the game from revisiting previous states and ensuring convergence. Once the potential function reaches its minimum value, any unilateral deviation by a player would increase their own cost and thus increase Φ(m). Therefore, a player will not unilaterally deviate, confirming that the converged state corresponds to a Pure Nash Equilibrium?
IIn OGame, PNE represents mapping profile where player further reduce its cost by unilaterally changing its mapping choice.
Everry finite potential game admits a puro-strategy equilibrium, as proved [Monderer & Shapley 1996
25


Reviews:
[{"review_id": "xtYoUZ9Lig", "reviewer": "Reviewer_Rts6", "summary": "", "questions": "", "limitations": "", "rating": null, "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": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a cooperative-game-theoretic algorithm for graph coarsening that seeks coalitions (supernodes) by minimizing a Dirichlet-energy–based objective. Nodes are treated as players; each coalition’s worth is the energy and each node’s cost is its marginal contribution to that energy. A leader-base} heuristic restricts candidate coalitions to 1-hop neighborhoods of high-degree nodes to avoid an NP-complete subset search; then iterative best-response updates are used until no node wants to deviate. The authors claim (i) the game is a \\textbf{potential game}, hence convergence to a PNE; (ii) the approach is fast; and (iii) the coarsened graphs preserve structure and yield good node-classification accuracy across several datasets (Cora, DBLP, Coauthor CS/Physics, Pubmed, OGBN-Arxiv, Genius). Results tables/figures include Algorithm 1 (p.7), Tables 1–3 (pp.9–12), Figure 2 (workflow), Figure 3 (leader vs. non-leader refinement), and spectral/$\\varepsilon$-similarity plots (Figure 4).", "claims_and_evidence_yn": "No", "claims_explanation": "Below are my major concerns with the paper:\n\n(A) Inconsistencies/Ambiguities in Energy and Potential-Game Definitions\n\n\\begin{itemize}\n \n\\item Notation in general is a mess. For example, The manuscript uses the symbol $m$ to represent multiple distinct quantities across different sections, which may cause confusion for readers. For instance, in Section~2.1, $m$ denotes the number of classes in the label matrix $L \\in \\mathbb{R}^{p \\times m}$, while in Section~2.4, it represents the mapping profile $(m_1, m_2, \\ldots, m_p)$ in the game-theoretic formulation. Later, $m$ also appears as the number of coalitions in the complexity analysis (e.g., $O(m \\cdot \\Delta)$) and as the Laplacian dimension in Equation~(1). Reusing the same symbol for unrelated concepts (labels, mapping profiles, coalitions, and matrix dimensions) detracts from the clarity of the presentation.\n\n\\item \\textbf{Which edges define the coalition energy?} Eq.~(5a) minimizes $\\sum_{i<j}\\tilde w_{ij}|\\tilde x_i-\\tilde x_j|^2$, i.e., \\textbf{between-supernode} variation (a cut-like energy). In Eq.~(7), $DE(R^m_{S_i})$ is defined using $E_x$, “the set of edges connected to the $i$-th supernode on the coarsened graph,” while Eq.~(11) defines the coalition potential with $E_{S_i}$, “the edges connected to the $i$-th supernode.” These are boundary edges, not purely internal edges, and a single cross-coalition edge contributes to the energy of \\textbf{multiple coalitions}. Then, the global potential in Eq.~(12) is the sum of coalition energies. Without a careful accounting (e.g., a factor $1/2$ or an edge partition), this \\textbf{double-counts} inter-coalition terms. It is unclear that a unilateral node move changes the global potential exactly by that node’s marginal cost as claimed in Appendix A.5 (Eqs. (16–18)). Please redefine coalition potentials over disjoint edge sets or redo the potential-game argument with explicit handling of cross-coalition terms.\n  \n  \\item \\textbf{Objective mismatch}: The coarsening objective is Eq.~(5a), but the node cost (Eq.~(7)) is defined via differences of $DE(\\cdot)$ on coalitions computed over $E_x$ or $E_{S_i}$. The relationship between the sum of marginal costs and the global objective in (5a) is not proven. Currently, the potential function $\\Phi(m)=\\sum_i DE(R^m_{S_i})$ is not obviously equivalent to (5a). Please formalize the equivalence.\n\\end{itemize}\n\n(B) Label Leakage in the Evaluation Protocol (maybe critical)\n\nIn \\textbf{Node Classification}, the paper states: ``we infer [the coarsened graph’s] node labels using $Y_c = \\arg\\max(PY)$'' (Section 4.2), \\emph{then} train GNNs on $G_c(\\Theta_c,X_c,Y_c)$ and evaluate on the remaining 20\\% of nodes (same section). Unless $Y$ contains only \\textbf{training labels}, $PY$ averages \\textbf{all} original labels inside each supernode—including test labels—which leaks test information into training via $Y_c$. Nothing in the text specifies masking test labels when forming $Y$ for the $PY$ step; in fact, the phrasing “excluding their labels during the coarsening process” explicitly refers to coarsening, not to the label-aggregation step used to create the training labels on the coarsened graph. This can inflate accuracy substantially, especially when coalitions mix train and test nodes. Please clarify and, if needed, re-run with $Y$ restricted to the training subset (and a principled way to handle unlabeled nodes when aggregating).\n\n\n(C) NP-Completeness Argument Seems Detached from the Actual Problem\n\nTheorem 1 (Appendix A.1) proves NP-completeness of a stylized “Stable Coalition decision problem” defined over arbitrary real numbers and an arbitrary function $f$, then reduces from a special knapsack instance. This construction is not tied to the graph-based Dirichlet energy used in the paper. The result thus shows that \\emph{some} stability problem is NP-complete, not that the \\emph{graph-coarsening stability check} with the specific cost function in Eq.~(7) is NP-hard. A formal reduction aligned with Eqs.~(6–7) and the energy semantics is needed.\n\n(D) Algorithmic Clarity and Complexity\n\n\\begin{itemize}\n\n  \\item \\textbf{Notation drift}: The paper alternates between $W$ and $A$ for adjacency; labels are denoted by $L$ and later by $Y$; Algorithm 1 initializes \\texttt{ccost ← \\{i : Dn[i]\\}} without defining \\texttt{Dn}. Please unify symbols.\n\n  \\item \\textbf{Complexity claims vary}: Section 3 states $O(\\Delta)$ per coalition, while Section 4.2 cites $O(p\\cdot \\Delta \\cdot k)$. Moreover, computing all marginal costs $c_{S_i}(j)=DE(S_i)-DE(S_i\\setminus\\{j\\})$ naively is $O(|S_i|)$ energy evaluations, potentially $O(\\Delta^2)$ per leader. Provide a precise per-iteration complexity and iteration bound.\n\n  \\item \\textbf{Heuristic vs. theory}: The PNE proof assumes arbitrary feasible coalitions, but Algorithm 1 restricts to leader-containing 1-hop subsets. Does the potential-game guarantee still hold under this restriction?\n\n\\end{itemize}\n\n(E) Experimental Methodology and Reporting\n\n\\begin{itemize}\n\n  \\item Use official OGBN-Arxiv splits in addition to custom 80/20.\n\n  \\item Include scalable non-learning baselines (HEM/Graclus/METIS) and memory-optimized FGC/LAGC.\n\n  \\item Add ablations: label aggregation (training-only), leader vs. non-leader, hop-size, and leader-selection metrics.\n\n  \\item Clarify $\\varepsilon$-similarity: The definition $(1-\\varepsilon)\\operatorname{tr}(X^\\top \\Theta X)\\le \\operatorname{tr}(\\tilde X^\\top \\Theta_c \\tilde X)\\le (1+\\varepsilon)\\operatorname{tr}(X^\\top \\Theta X))$ is feature-dependent, unlike standard Rayleigh quotient bounds.\n\n\\end{itemize}\n\nMinor Issues / Clarity / Presentation\n\n\\begin{itemize}\n\n  \\item Explicitly relate $P=C^\\dagger$ in Eq.~(3) to averaging in Eq.~(5b).\n\n  \\item Clarify all Algorithm 1 variables (\\texttt{Dn}, \\texttt{Scoalition}, \\texttt{ccost}).\n\n  \\item Unify label notation ($L$ vs. $Y$).\n\n  \\item Fix missing bibliographic details and grammar issues (e.g., ``descibed'' → ``described'').\n\n\\end{itemize}\n\nQuestions to the Authors:\n\n\\begin{enumerate}\n\n  \\item Is $Y$ restricted to training labels in $Y_c=\\arg\\max(PY)$?\n\n  \\item Provide a formal statement aligning Eq.~(5a) with Eqs.~(11–12).\n\n  \\item Do Theorems 2–3 hold under leader-restricted 1-hop coalitions?\n\n  \\item What is the formal per-iteration complexity and convergence bound?\n\n  \\item Include OGBN-Arxiv results with official splits.\n\n  \\item Provide ablations: leader variants, hop sizes, smoothing, alternative costs.\n\n  \\item Add scalable non-learning baselines.\n\n\\end{enumerate}", "audience_yn": "Yes", "audience_explanation": "This paper would interest a TMLR audience because it presents a new perspective on improving the scalability of graph-based learning methods if the claimed results are correct - currently not verifiable due to notation inconsistencies and presentation issues. The authors propose a Cooperative-Based Graph Coarsening (CGC) algorithm that applies ideas from game theory to reduce large graphs while preserving key structural and feature properties. By framing coarsening as a potential game that minimizes Dirichlet energy, the method provides a principled way to form stable node groupings without extensive hyperparameter tuning. The approach may complement existing graph learning techniques by offering a computationally efficient preprocessing step that can benefit Graph Neural Networks (GNNs) when dealing with large datasets.", "requested_changes": "Below are my major concerns with the paper:\n\n(A) Inconsistencies/Ambiguities in Energy and Potential-Game Definitions\n\n\\begin{itemize}\n \n\\item Notation in general is a mess. For example, The manuscript uses the symbol $m$ to represent multiple distinct quantities across different sections, which may cause confusion for readers. For instance, in Section~2.1, $m$ denotes the number of classes in the label matrix $L \\in \\mathbb{R}^{p \\times m}$, while in Section~2.4, it represents the mapping profile $(m_1, m_2, \\ldots, m_p)$ in the game-theoretic formulation. Later, $m$ also appears as the number of coalitions in the complexity analysis (e.g., $O(m \\cdot \\Delta)$) and as the Laplacian dimension in Equation~(1). Reusing the same symbol for unrelated concepts (labels, mapping profiles, coalitions, and matrix dimensions) detracts from the clarity of the presentation.\n\n\\item \\textbf{Which edges define the coalition energy?} Eq.~(5a) minimizes $\\sum_{i<j}\\tilde w_{ij}|\\tilde x_i-\\tilde x_j|^2$, i.e., \\textbf{between-supernode} variation (a cut-like energy). In Eq.~(7), $DE(R^m_{S_i})$ is defined using $E_x$, “the set of edges connected to the $i$-th supernode on the coarsened graph,” while Eq.~(11) defines the coalition potential with $E_{S_i}$, “the edges connected to the $i$-th supernode.” These are boundary edges, not purely internal edges, and a single cross-coalition edge contributes to the energy of \\textbf{multiple coalitions}. Then, the global potential in Eq.~(12) is the sum of coalition energies. Without a careful accounting (e.g., a factor $1/2$ or an edge partition), this \\textbf{double-counts} inter-coalition terms. It is unclear that a unilateral node move changes the global potential exactly by that node’s marginal cost as claimed in Appendix A.5 (Eqs. (16–18)). Please redefine coalition potentials over disjoint edge sets or redo the potential-game argument with explicit handling of cross-coalition terms.\n  \n  \\item \\textbf{Objective mismatch}: The coarsening objective is Eq.~(5a), but the node cost (Eq.~(7)) is defined via differences of $DE(\\cdot)$ on coalitions computed over $E_x$ or $E_{S_i}$. The relationship between the sum of marginal costs and the global objective in (5a) is not proven. Currently, the potential function $\\Phi(m)=\\sum_i DE(R^m_{S_i})$ is not obviously equivalent to (5a). Please formalize the equivalence.\n\\end{itemize}\n\n(B) Label Leakage in the Evaluation Protocol (maybe critical)\n\nIn \\textbf{Node Classification}, the paper states: ``we infer [the coarsened graph’s] node labels using $Y_c = \\arg\\max(PY)$'' (Section 4.2), \\emph{then} train GNNs on $G_c(\\Theta_c,X_c,Y_c)$ and evaluate on the remaining 20\\% of nodes (same section). Unless $Y$ contains only \\textbf{training labels}, $PY$ averages \\textbf{all} original labels inside each supernode—including test labels—which leaks test information into training via $Y_c$. Nothing in the text specifies masking test labels when forming $Y$ for the $PY$ step; in fact, the phrasing “excluding their labels during the coarsening process” explicitly refers to coarsening, not to the label-aggregation step used to create the training labels on the coarsened graph. This can inflate accuracy substantially, especially when coalitions mix train and test nodes. Please clarify and, if needed, re-run with $Y$ restricted to the training subset (and a principled way to handle unlabeled nodes when aggregating).\n\n\n(C) NP-Completeness Argument Seems Detached from the Actual Problem\n\nTheorem 1 (Appendix A.1) proves NP-completeness of a stylized “Stable Coalition decision problem” defined over arbitrary real numbers and an arbitrary function $f$, then reduces from a special knapsack instance. This construction is not tied to the graph-based Dirichlet energy used in the paper. The result thus shows that \\emph{some} stability problem is NP-complete, not that the \\emph{graph-coarsening stability check} with the specific cost function in Eq.~(7) is NP-hard. A formal reduction aligned with Eqs.~(6–7) and the energy semantics is needed.\n\n(D) Algorithmic Clarity and Complexity\n\n\\begin{itemize}\n\n  \\item \\textbf{Notation drift}: The paper alternates between $W$ and $A$ for adjacency; labels are denoted by $L$ and later by $Y$; Algorithm 1 initializes \\texttt{ccost ← \\{i : Dn[i]\\}} without defining \\texttt{Dn}. Please unify symbols.\n\n  \\item \\textbf{Complexity claims vary}: Section 3 states $O(\\Delta)$ per coalition, while Section 4.2 cites $O(p\\cdot \\Delta \\cdot k)$. Moreover, computing all marginal costs $c_{S_i}(j)=DE(S_i)-DE(S_i\\setminus\\{j\\})$ naively is $O(|S_i|)$ energy evaluations, potentially $O(\\Delta^2)$ per leader. Provide a precise per-iteration complexity and iteration bound.\n\n  \\item \\textbf{Heuristic vs. theory}: The PNE proof assumes arbitrary feasible coalitions, but Algorithm 1 restricts to leader-containing 1-hop subsets. Does the potential-game guarantee still hold under this restriction?\n\n\\end{itemize}\n\n(E) Experimental Methodology and Reporting\n\n\\begin{itemize}\n\n  \\item Use official OGBN-Arxiv splits in addition to custom 80/20.\n\n  \\item Include scalable non-learning baselines (HEM/Graclus/METIS) and memory-optimized FGC/LAGC.\n\n  \\item Add ablations: label aggregation (training-only), leader vs. non-leader, hop-size, and leader-selection metrics.\n\n  \\item Clarify $\\varepsilon$-similarity: The definition $(1-\\varepsilon)\\operatorname{tr}(X^\\top \\Theta X)\\le \\operatorname{tr}(\\tilde X^\\top \\Theta_c \\tilde X)\\le (1+\\varepsilon)\\operatorname{tr}(X^\\top \\Theta X))$ is feature-dependent, unlike standard Rayleigh quotient bounds.\n\n\\end{itemize}\n\nMinor Issues / Clarity / Presentation\n\n\\begin{itemize}\n\n  \\item Explicitly relate $P=C^\\dagger$ in Eq.~(3) to averaging in Eq.~(5b).\n\n  \\item Clarify all Algorithm 1 variables (\\texttt{Dn}, \\texttt{Scoalition}, \\texttt{ccost}).\n\n  \\item Unify label notation ($L$ vs. $Y$).\n\n  \\item Fix missing bibliographic details and grammar issues (e.g., ``descibed'' → ``described'').\n\n\\end{itemize}\n\nQuestions to the Authors:\n\n\\begin{enumerate}\n\n  \\item Is $Y$ restricted to training labels in $Y_c=\\arg\\max(PY)$?\n\n  \\item Provide a formal statement aligning Eq.~(5a) with Eqs.~(11–12).\n\n  \\item Do Theorems 2–3 hold under leader-restricted 1-hop coalitions?\n\n  \\item What is the formal per-iteration complexity and convergence bound?\n\n  \\item Include OGBN-Arxiv results with official splits.\n\n  \\item Provide ablations: leader variants, hop sizes, smoothing, alternative costs.\n\n  \\item Add scalable non-learning baselines.\n\n\\end{enumerate}", "broader_impact_concerns": "None that I know of.", "additional_comments": "None.", "extra_scores": {}, "extra_text": {}}, {"review_id": "N5alusDf1x", "reviewer": "Reviewer_Edju", "summary": "", "questions": "", "limitations": "", "rating": null, "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": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces a Cooperative Game-based Graph Coarsening (CGC) method that models graph coarsening as a cooperative game among nodes. Each node acts as a player forming coalitions (supernodes) to minimize its Dirichlet energy cost, leading to a stable, energy-efficient coarsened graph. The authors prove that the game is a potential game, guaranteeing convergence to equilibrium, and demonstrate that CGC achieves better accuracy and lower runtime than prior coarsening methods across multiple datasets.\n\nStrengths\n\nS1) The application of game theory to the graph coarsening problem is interesting. Treating each node as an individual agent and viewing the node-merging process as coalition formation is both novel and intuitive.\n\nS2) The paper is clearly written and well-organized. The main ideas are presented logically, supported by sound theoretical analysis and solid mathematical grounding.\n\nS3) The proposed approach exhibits strong empirical performance, demonstrating both effectiveness (in preserving downstream accuracy) and efficiency (in computational cost) across diverse datasets.\n\nWeaknesses / Questions\n\nW1) The evaluation protocol for node classification requires clarification. If the primary goal of coarsening is to accelerate training while preserving performance, then inference should ideally be conducted on the original graph, not the coarsened one, for a fair comparison with existing methods. The paper should explicitly describe this procedure.\n\nW2) It would be helpful to discuss whether CGC is applicable to heterophilous graphs, where connected nodes often have dissimilar labels. Such settings can pose challenges for methods that assume homophily.\n\nW3) A simple node-masking baseline—where a subset of nodes is randomly masked to match the coarsened graph’s size—could serve as a valuable reference point, highlighting how much of the performance gain comes from the coarsening mechanism itself.\n\nW4) The choice of using 80% of nodes for training seems unusually high. Many graph learning benchmarks use smaller labeled subsets (e.g., 30% or less). Including experiments with more limited supervision would provide deeper insights into the robustness of CGC.\n\nW5) The paper should also clarify how labels for merged (super)nodes are assigned—whether via majority voting, weighted aggregation, or soft-labeling strategies. This detail is essential for reproducibility and understanding how supervision propagates through the coarsened graph.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Overall, the claims made in this paper are well supported by both theoretical analysis and empirical evidence.", "audience_yn": "Yes", "audience_explanation": "Graph coarsening is a highly practical problem with potentially broad applications across various domains.", "requested_changes": "Please address or clarify the above-mentioned weaknesses and questions in the revision.", "broader_impact_concerns": "N/A", "additional_comments": "N/A", "extra_scores": {}, "extra_text": {}}, {"review_id": "rznMvBgb6j", "reviewer": "Reviewer_c8vT", "summary": "", "questions": "", "limitations": "", "rating": null, "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": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the lack of a unified and interpretable principle for node merging in existing graph coarsening methods, which mostly rely on heuristic or topology-based rules. To overcome these issues, the authors propose CGC, a cooperative-game-based coarsening framework that models node merging as a game where each node’s marginal contribution to the Dirichlet energy determines coalition formation, ensuring interpretable and convergent coarsening with better preservation of structural and feature information. Experimental results show that, compared with existing graph coarsening methods, CGC achieves higher accuracy and faster runtime in most cases.\n\nStrengths:\n\n1) Modeling graph coarsening as a cooperative game introduces a principled and interpretable decision mechanism for node merging. This formulation not only explains why specific nodes are merged but also links the coarsening process to a clear optimization principle, providing stronger interpretability and consistency than heuristic merging rules.\n2) The formulation as a potential game ensures convergence to a pure-strategy Nash equilibrium, which offers stronger theoretical justification than many heuristic coarsening methods.\n\nWeaknesses:\n\n1) The proposed method does not demonstrate clear novelty. The overall approach is conceptually similar to previous game-theoretic graph clustering works and fails to introduce new techniques to address existing challenges.\n2) The convergence guarantee of potential games applies only to local equilibria. The method may be sensitive to initialization or leader selection, but this is not analyzed.\n3) The paper does not clarify whether the pseudo-inverse label projection uses only training labels; if test labels are included, this could cause data leakage and artificially inflate classification performance.\n4) The experimental evaluation is incomplete and potentially unfair: many baselines are reported as OOM without explanation or mitigation, and the paper does not compare against the latest graph coarsening methods.", "claims_and_evidence_yn": "No", "claims_explanation": "The theoretical proposition of the paper, that the game is a potential game and there exists a PNE, has been rigorously proven to be credible. The convergence conclusion has clear logic and sufficient mathematical derivation. However, the empirical claims are currently not fully substantiated: Several baselines in the tables report “OOM” or missing values, preventing a fair comparison; The numerical stability of pseudoinverse label inference and the separation of training/testing data are not clarified, potentially affecting result reliability; No ablation studies are provided to verify that the performance gains stem from the game-theoretic mechanism rather than specific hyperparameters or feature choices.", "audience_yn": "Yes", "audience_explanation": "The paper presents a potential-function framework linking graph coarsening with cooperative game theory, which holds some significance for researchers studying graph compression, spectral approximation, and GNN stability.", "requested_changes": "1) Could the authors clarify whether only the training set labels are used when computing the projected labels for the coarsened nodes? If test set labels are included, might this lead to data leakage and overestimated accuracy?\n2) Could the authors clarify or provide mitigation strategies for cases where baseline methods report ‘OOM’ or missing results, to ensure experimental completeness and fairness?\n3) Could the authors analyze the sensitivity of CGC to initialization and leader selection, given that the convergence guarantees only apply to local equilibria?\n4) Could the authors include more recent and relevant baseline methods for a fairer comparison?\n5) Inconsistency in notation and dimensions: On page 3 (Background section), you first define 𝑝 as the number of nodes, but later describe the Laplacian matrix as having dimensions 𝑚×𝑚. Please unify the notation and correct all matrix dimension annotations accordingly.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)