Feature Driven Graph Coarsening for Scaling Graph Representation Learning
Graph Coarsening;Graph Neural Networks
Yes
No ethics review needed.
Although the runtime for each experiment is very fast, this method depends heavily on extensive hyperparameter tuning. Do the authors have any suggestions for how to select the hyper-parameters?
1. The method relies solely on node features and labels, achieving impressive performance even without an initial graph structure. This approach shows potential for unifying graph data with other data formats.

2. This method stands out for its efficiency and resilience against structural attacks.

3. Bridging the sparsity of PY with the homophily of coarsening introduces an innovative and promising concept.
This paper studies the scalability and structural limitations of existing graph coarsening techniques. It proposes a new framework, Coarsened Graph Learning (CGL), to directly learn a reduced graph from attribute data alone, eliminating the need for a pre-existing graph. By learning the graph from features, CGL enables scalable GNN training, is resilient against adversarial attacks, and incorporates semi-supervised learning with label information for enhanced downstream task performance. Experimental comparisons show that CGL outperforms state-of-the-art methods in node classification accuracy and computational efficiency across various datasets, proving its potential in large-scale, real-world applications.
1. Since validation and test labels should remain hidden during training, it would be helpful to clarify how they are masked, perhaps by introducing a specific notation or symbol for this purpose.

2. Some baseline results are not fully reproduced. For instance, GCond typically produces results close to those of the full dataset, suggesting that the authors may not have adjusted the dataset split to 80%/10%/10% when replicating GCond’s performance.

3. Testing this method on large heterophilous graphs, such as Penn94, would add valuable insights into its scalability and effectiveness in diverse graph structures.

4. This method shares similarities with FGC [1] in objective design and learning approach. However, a more in-depth methodological comparison between the two would be beneficial for understanding their differences and relative strengths. Adding a dedicated section on related works to systematically compare various graph coarsening and condensation methods [2] would further enhance the paper.


### References
[1] Featured graph coarsening with similarity guarantees. ICML 2023

[2] A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation. IJCAI 2024
Yes
No ethics review needed.
Could the authors provide more details on the rationale for addressing structureless graphs and the specific real-world applications this approach is intended to serve?

Why were other coarsening methods not included as baseline comparisons, given the abundance of related work?

BSUM may face scalability issues, especially with high-dimensional data or large block sizes. Did the authors encounter efficiency or convergence challenges on large datasets, and if so, how were these managed?

About the different optimization strategies used, could the authors illustrate why choose these methods and compare with other advantages od doing so?
The optimization approach focuses on deriving a coarsened graph directly from node features, combining graph structure learning with coarsening. By removing dependency on initial graph structures, CGL could mitigate issues caused by adversarial and noisy edges. The writing is clear and accessible, with well-defined concepts that facilitate understanding of complex ideas.
The paper introduces the optimization-based framework Coarsened Graph Learning (CGL), which directly learns a coarsened graph from feature data alone. This framework addresses the challenges of scalability and the reliance on initial graph structures. The authors highlight that while graph neural networks (GNNs) are good at modeling graphs, they are vulnerable to adversarial edges that can degrade performance by contaminating node neighborhoods. CGL aims to improve robustness against these adversarial attacks by learning a coarsened graph independently of the original graph structure. CGL formulates the problem as a multi-block, non-convex optimization problem, solved using the Block Successive Upper-bound Minimization (BSUM) technique. The authors compare CGL and its semi-supervised variant (SCGL) against GCOND, SCAL and FGC methods on both homophilic and heterophilic datasets, measuring both classification performance and computational efficiency. Additionally, the incorporation of label information into the objective function significantly enhances downstream task performance.
The motivation for learning from structureless graphs is limited, making it unclear why this direction is essential or where it’s practically relevant. 

CGL is the combination of graph structure learning and graph coarsening, the comparison and discussion of related works are not sufficient. In experiment settings, the baseline of graph coarsening methods are also limited. 

While choosing the BSUM methods for non-convex optimization, for large-scale problems, BSUM can be computationally expensive and may converge slowly. As the number of variables and the size of each block are large in some large-scale graph datasets, this might reduce efficiency in practical applications.

The motivation of each optimization procedure is not clear. For example, CGL adapts the idea of paper “A unified framework for structured graph learning via spectral constraints” to optimize the structure of coarsened graph directly, lacking motivation and details for the arguments.
Yes
No ethics review needed.
1. In the introduction, emphasis has been given on the adversarial robustness of the proposed approach. However, under experiments, the result and most of the discussion have been deferred to the appendix. Wondering if it may be useful to include a part of the results in the main text for consistency.
2. In table 10, it is interesting to observe that the performance for perturbed data at certain rates is higher compared to unperturbed data. Do you have any comments on this phenomenon?
1. Tackles the highly relevant problem of graph coarsening, which is especially useful for large graphs.
2. Eliminates dependence on graph structure, achieving much lower computational complexity compared to baselines.
3. Demonstrates adversarial robustness
The paper proposes a graph coarsening approach that only depends on the node attributes (feature matrix and optionally labels) of the larger graph. Each node is allocated to a super-node (or a node in the coarsened graph), which is learned by solving a multiblock nonconvex optimization problem. This optimization also learns the coarsened graph’s feature matrix and adjacency matrix. The results indicate superior performance across different datasets, improved computational complexity, and robustness against adversarial attack. The latter is due to the elimination of dependence on graph structure in their approach.
While the underlying problem is topical and interesting, I have below concerns:

1. Lack of clarity and structure: I believe the presentation can be significantly improved. For example, in the introduction, the authors discuss scalability issues for large graphs, critique existing graph coarsening methods (especially their reliance on graph structure), and need for adversarial robustness. However, the discussion feels scattered and difficult to follow.
2. The method itself is simple and intuitive to follow. However, the design choices are not well-motivated. For example, the approach assigns each node to a super-node. This seems to assume an inherent clustering of nodes. This is further reinforced by using node labels and adding the constraint that similar labeled nodes should be assigned to the same super-node. Wonder why hard assignments should be used instead of soft assignments? Is it to aid optimization? An analysis of the relationship between original nodes and supernodes would have been helpful. Moreover, it seems that the coarsened graph may not improve performance when the node labels and downstream tasks are not correlated.
3. The reported performance on the complete dataset doesn’t match the values from previous work [1, 2] for Cora, Citeseer, and Flickr. This raises concerns regarding fairness of comparison. The exact experimental settings and how they differ from referenced work have not been covered even in the appendix.



[1] Zheng X, Zhang M, Chen C, Nguyen QV, Zhu X, Pan S. Structure-free graph condensation: From large-scale graphs to condensed graph-free data. Advances in Neural Information Processing Systems. 2024 Feb 13;36.

[2] Jin W, Zhao L, Zhang S, Liu Y, Tang J, Shah N. Graph condensation for graph neural networks. arXiv preprint arXiv:2110.07580. 2021 Oct 14.
Yes
No ethics review needed.
See the above weaknesses.
Pros:
1.  Coarsened Graph Learning is important for the downstream task. 
2. The paper proposes two settings for the downstream tasks, such as coarsened graph learning CGL and semi-supervised coarsened graph learning SCGL.
This paper proposes a graph-coarsening framework that directly learns a coarsened graph from attribute information. The framework also includes a semi-supervised learning pipeline for GNNs that incorporates label information.  The paper proposes two settings: coarsened graph learning CGL and semi-supervised coarsened graph learning SCGL,  and shows the improved performance on downstream tasks.
Cons:
1. Why use the coarsened graph for node classification learning to get better node classification performance? It is better to highlight the motivation and prove it with theoretical support.
2. It is better to show the performance of the graph-coarsening framework on other graph-level tasks, such as graph classification and compare it with related baselines.
3. The motivation of the paper needs to be better highlighted. Why only using data features is effective? In fact, the graph structure, even though the noisy/incomplete graph structure is important for the graph coarsing .
4. Some of the notations need to be better illustrated in the paper, such as Wh.Data, L.Data.
5. It is suggested to give some coarsened graph cases to demonstrate the effectiveness of the proposed framework compared with baselines.
@inproceedings{
anonymous2024feature,
title={Feature Driven Graph Coarsening for Scaling Graph Representation Learning},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=6VuTXirQIv},
note={under review}
}
Graphical modelling for structured data analysis has gained prominence across numerous domains. A significant computational challenge lies in efficiently capturing complex relationships within large-scale graph structures. Graph coarsening, which reduces graph size by merging nodes and edges into supernodes and superedges, enhances scalability and is crucial for graph neural networks (GNNs). However, current methods either construct graphs from large-scale attribute data or assume a pre-existing graph before coarsening, limiting their applicability, especially in domains like healthcare and finance where graph structure is often unavailable. In this paper, we present a novel framework that directly learns a coarsened graph from attribute information, reducing computational complexity and enhancing robustness against adversarial attacks, which commonly target vulnerabilities in graph structures. By integrating label information, our framework also enables semi-supervised learning, leading to improved performance on downstream tasks. Extensive experiments show that our method outperforms state-of-the-art coarsening techniques in both accuracy and computational efficiency.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Graph Coarsening Graph Neural Networks
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/4c5519281aeab6c31f65784f9635052f522cb926.pdf
learning on graphs and other geometries & topologies
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/cdda917fee051cfba8100207e7a1c847f48592a4.zip
Feature Driven Graph Coarsening for Scaling Graph Representation Learning
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission