Solving Normalized Cut Problem with Constrained Action Space

Questions part

Training settings for NeuroCUT and ClusterNet

Yes, all learning based methods used the same training datasets and test datasets while maintaining the same number of training steps. It is important to note that these two algorithms are designed for unweighted graphs and do not directly support weighted graphs. Therefore, we made the following modifications:

• For ClusterNet, we replaced the values of the 0-1 adjacency matrix with edge weights. Additionally, we adjusted its loss calculation formula to align with weighted Normalized Cut.

• For NeuroCUT, we also added the support of weighted edges. Specifically, we adjusted the reward function to match the weighted Normalized Cut and incorporated edge weight information into the node embeddings, including the weights of adjacent edges and embeddings obtained through random walks. Furthermore, NeuroCUT requires an initial partition, and its built-in initial partition method has poor performance; thus, we replaced it with the results from METIS.

Contribution of Cheeger bounds

The Cheeger bound presented in this work is not a specific result of a more general case. Note that, in our work the Cheeger constant corresponds to the minimum normalized cut. For classical Cheeger bounds, the Cheeger constant is found by minimizing the normalized cut over all possible partitions. In our case, we don't consider the class of all possible partitions, but only on the restricted class of ring+wedge partitions. So, the minimum "constrained" normalized cut is be greater or equal than the classical Cheeger constant(=minimum normalized cut). In principle it is not know how large this quantity is and if it still makes sense to minimize the normalized cut on this smaller space of partitions. In our work we prove that actually also the $k$-th "constrained" normalized cut is still bounded from above by $\mathcal{O}(\sqrt{\lambda_k})$, following a behavior similar to the classical case. This shows that constraining the minimization to this class of partitions leads to good quality normalized cuts. Proving this result in full generality is very difficult, but showing this already for spider-web graphs provides a good justification of using ring+wedge partitions. Thank you for your question, we will clarify this point in the final version of the paper.

Metrics of Table 1 and 2

The metrics of Table 1 and 2 are Normalized Cut of partitions provided by different methods, which is mentioned in the caption of the Tables. A lower value indicates better performance.

Generalization results for compared methods

NeuroCUT and ClusterNet does not support generalization directly based on their codes. We are working on modifying them to support generalization, and give their generalization results in the revised version.

Training curves of RL

Although the reward seems converge early, there is still slight optimization for the final performance. When wedge partition is not fixed, there is rapid initial convergence, but continued training leads to a decline in the reward before reaching the best solution, resulting in the selection of the best checkpoint being from the early stages. In contrast, fixing wedge partition allows for ongoing exploration around a favorable position, yielding better results.

We have also added reward curves during the testing in Figure 6 in the Appendix B.4, from the curves we can find the performance is increasing steadily with fixed wedge partition, and when wedge partition is not fixed, it cannot have further performance increase after initial converge.

Regarding the number of training steps, this is a useful suggestion. Indeed, the optimization achieved in the later stages of our current training strategy is significantly smaller compared to the beginning. We will explore better training strategies to accelerate the convergence process during this phase.

We truly appreciate the points you raised in your review, as they help us improve and refine our work. Below, we’ve outlined our responses to address the issues:

Weakness Part

Including more baselines

Thank you for the suggestion. From the results of NeuroCUT and ClusterNet, they outperform baselines in all experiments, so we chose them as the comparism methods and omit the weaker competitors.

Introducing Ringness and Wedgeness in compared methods

Our ultimate goal in this problem is to provide a superior parition with smaller Normalized Cut, and without extra constraints. Baselines cannot incorporate the Ringness and Wedgeness constraint in their structure, because they directly do partition based on nodes, or from a existing partition (e.g. the partition result given by METIS). Without the constraint, they should have a larger action space compared with WRT; however, they actually cannot perform better results. On the other hand, although our method restricts the action space, we finally find partition with smaller Normalized Cut. This further demonstrates that introducing the domain knowledge by constraining the action space represents a more effective approach.

Graphs are relatively small

Thank you for your question. During training, we need to randomly sample a sub-graph during every iteration and perform checks such as connectivity and map coverage on that graph. Currently, this sampling process is inefficient, and as the node number increases, the overhead rises significantly. This has temporarily prevented us from conducting larger-scale training. We are also working on improving processing efficiency so that the model can be applied to maps with a larger number of points.

Performance of Transformers in large graphs

In this paper, our primary contribution lies in presenting a novel approach to incorporating domain knowledge by constraining the action space. Specifically, we restrict the action space to ring and wedge, providing better results with Transformers. Although Transformers is able to perform good results when scaling to larger graphs, the quadratic time complexity of Transformers indeed poses challenges. To address this issue, we can employ acceleration techniques such as Flash Attention or Linear Attention to alleviate the problem.

We truly appreciate the points you raised in your review, as they help us improve and refine our work. Below, we’ve outlined our responses to address the issues:

More ablation studies

Thank you for pointing out the problem. We are working on implementing ablation studies you mentioned, and will add them in the revised version of the paper later.

Running time of our method

We give the inference time of our method and other competitors on City Fraffic graphs with 4 partitions in the table above. From the table, We can observe that METIS and ClusterNet have relatively low and stable running time; Spectral Clustering, while also having a shorter running time in the experiments, exhibits a rapid increase based on node number. NeuroCUT, takes a longer time and shows a significant growth as the number of points increases. Our method WRT takes relatively longer than METIS and ClusterNet, but is significantly faster than NeuroCUT.

Comparison between GNNs and Transformers

In this work, we choose Transformers instead of GNNs due to their superior scalability for larger graphs. In Transformer, each token can attend to all other tokens, enabling information exchange to occur in parallel. Conversely, GNNs are limited to observing only neighboring nodes and typically require a significantly greater number of layers to capture global information.

The Normalized Cut, particularly when applied with ring and wedge, necessitates a holistic view of the global graph. Since GNNs inherently lack access to this global information, this limitation represents a significant bottleneck for their ability to learn effective strategies for Normalized Cut.

Graphs are relatively small

Thank you for your question. During training, we need to randomly sample a sub-graph during every iteration and perform checks such as connectivity and map coverage on that graph. Currently, this sampling process is inefficient, and as the node number increases, the overhead rises significantly. This has temporarily prevented us from conducting larger-scale training. We are also working on improving processing efficiency so that the model can be applied to maps with a larger number of points.

Metrics of Table 1 and 2

The metrics of Table 1 and 2 are Normalized Cut of partitions provided by different methods, which is mentioned in the caption of the Tables. A lower value indicates better performance.

Performance on other types of datasets

Our core idea is to constrain the action space based on domain knowledge, thereby training a better model. In this paper, Our method focuses on the road network graph and proposes the ring-wedge partition method. However, for knowledge graphs, since the nodes are not positioned on a plane, directly applying ring and wedge shape may be challenging. One idea could be proposing a mapping algorithm to project the nodes onto a plane for analysis. Alternatively, we could explore new methods to simplify the action space based on the features of the knowledge graphs.

We truly appreciate the points you raised in your review, as they help us improve and refine our work. Below, we’ve outlined our responses to address the issues:

Method is ad-hoc and specific

The graph transformations are not purely manually designed; the transformations we propose are based on the application scenario of planar road networks. We are inspired by real-world road network designs. Theoretical analysis also supported the notion that ring and wedge partition form a robust constrained action space. We believe that this approach can be applied to various road network-related problems.

Comparison between Dynamic Programming and Reinforcement Learning

Dynamic programming is a part of our method. Once the radius and the number of rings are determined, we can use dynamic programming to find the optimal solution for the ring partition; meanwhile, RL is employed to seek the optimal partition for the wedge part. Combining both parts completes the ring-wedge partition and their performance cannot be directly compared.

Graphs are relatively small

Thank you for your question. During training, we need to randomly sample a sub-graph during every iteration and perform checks such as connectivity and map coverage on that graph. Currently, this sampling process is inefficient, and as the node number increases, the overhead rises significantly. This has temporarily prevented us from conducting larger-scale training. We are also working on improving processing efficiency so that the model can be applied to maps with a larger number of points.

Can this approach be automated by classifying the graphs to automatically find which transformations should be applied as a preprocessing step?

Thank you for the suggestion. Our method focuses on the road network graph and proposes the ring-wedge partition method based on the characteristics of the road network graph, which enhances the performance of reinforcement learning (RL) by constraining the action space. For other graphs, we can also design similar constraints on action space based on the inherent properties of the graph, thereby training better RL models. We believe that constraint design is closely related to specific problems and requires a solid theoretical foundation, thus necessitating tailored one-on-one designs. Automatically determining the appropriate transformations as a pre-processing step is currently out of scope. In fact that is a completely different research problem.

Thank you authors for your response. Perhaps an "apples to apples" comparison with other methods and on larger instances would improve the work. The current approach is very specific and ad-hoc and demonstrated on relatively small instances. I will keep my review score unchanged.

We truly appreciate the points you raised in your review, as they help us improve and refine our work. Below, we’ve outlined our responses to address the issues:

Weakness Part

Generalizability of our method

Our method is applicable to a broad subset of planar graphs, particularly those modeling transportation and road networks, like traffic simulation, map representation learning, and traffic prediction. This makes our method suitable for a broad subclass within spatio-temporal application domains. Furthermore our method provides a principled ways of incorporating prior knowledge into partitioning using transformer-based reinforcement learning.

Modeling in ring-wedge style

Many city road networks naturally exhibit a ring-wedge structure, where traffic flows from outer suburban or remote areas (wedge-shaped regions) into the city center, which is often organized into multiple concentric rings. For instance:

1. Beijing's Five Ring includes a large circular expressway encircling the city, acting as the outermost "ring" within the urban area, while traffic flows from various surrounding suburban areas converge toward the city center.
2. Shanghai's urban expressway system consists of three ring roadways and two major cross roads in the central urban area, with traffic streams from the outer districts feeding into these rings.
3. Qatar's infrastructure also features multiple ring roads, designed to handle traffic coming from different directions and converging toward central hubs.

Also, at the end of large events, people tend to expand outward from the center of the stadium, exhibiting a radial dispersion through the main avenues.

This ring-wedge traffic pattern is prevalent in many urban networks, especially for large cities, making our method broadly applicable. By explicitly constraining the shape of network components to reflect these patterns, we address practical challenges and provide a principled approach to fine-grained, shape-controlled graph partitioning.

On the theoretical front we provide new Cheeger inequalities that connect the spectral properties of a graph with algebraic properties that capture the shape of the partitions.

Transformers with Graphs

Thank you for pointing out the issue that our expression in the paper was not sufficiently precise. We intend to clarify that sequential input helps to simplify the input space, making it more suitable for Transformers' learning. We are currently revising the relevant content and will update the expression in the revised version.

For the use of positional encoding, we are also implementing comparative experiments by not performing ring or wedge transformations, but directly use the coordinates as positional encoding and treat the edge weights as attention masks. We will update the results of the comparative experiments later.

Writing improvements in Section 5.2

Thanks for your kind suggestion. We are improving our writings on Section 5.2.1 and 5.2.2 to simplify the explanation according to your advice and will prepare the revised version.

Optimal Partitioning of Circles in line 322

Thanks for your advice. We have added the pseudo-code of finding Optimal Partitioning of Circles in the appendix G. The algorithm uses dynamic programming, which have time complexity $O(n^2k)$.

Current Partition, Binary Mask and colored Square matrix in Sec. 5.4

The Current Partition represents the indices of points on the selected wedge and indicates where we are splitting between wedge$_i$ and wedge$_{i+1}$ . It is a binary mask. Suppose there are $k$ wedges for the Current Partition. If we decide to split between $j$th wedge and $j+1$th wedge, it will only be related to the existing partitions that cover $j$. Therefore, in the attention mask, we mask out the portions associated with other partitions. We are working on providing more detailed and intuitive explanations in the appendix.

Applying on different datasets and relationship to graph cut methods

We appreciate your suggestion and have conducted a thorough review of the relevant literature. The methods employed in the referenced articles [1] apply to the min-cut problem. Min-cut and max-flow are dual problems. For general graphs, the time complexity of algorithms solving max-flow such as Dinic is $O(V^2E)$, while it can be reduced to $O(E \log E)$ for planar graphs. However, Normalized Cut differs from these approaches, as it requires simultaneous consideration of both the size of the cut and the weights of internal edges, making it unsuitable for resolution through min-cut methods. To the best of our knowledge, there is currently no polynomial-time solution or verification method available for Normalized Cut, even on planar graphs.

[1] SCHMIDT, Frank R.; TOPPE, Eno; CREMERS, Daniel. Efficient planar graph cuts with applications in computer vision. In: 2009 IEEE conference on computer vision and pattern recognition. IEEE, 2009. p. 351-356.

Questions Part

Is it still a NP-Hard problem

Thank you very much for bring up this point which we should have mentioned in the paper. The problem of finding the Normalized Cut (normalized min-cut) on planar graphs is classified as NP-Complete and may also be NP-Hard. As referenced in the appendix of [2], it has been established that determining the Normalized Cut on regular grids is at least NP-Complete due to a reduction from the PARTITION problem.

[2] Shi, J., & Malik, J. (2000). Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8), 888-905.

Definition of Normalized Cut and line 214

We followed the standard definition of Normalized Cut without introducing a new definition for it. When minimizing Normalized Cut, the partition can consist of arbitrary point sets. However, we found that the model struggles to learn a good partitioning strategy in an unconstrained setting. Based on prior knowledge of the traffic environment, we constrain the action space to ring and wedge, enabling the model to propose better strategies within a constrained action space. In Line 214, we consider a special case of planar graphs, known as spider web graphs. Under this specific case, we prove that ring and wedge partitions achieve the same bound as the classical case. This theoretically demonstrates the feasibility of restricting the action space to ring and wedge.

Node order in line 283

Thank you for pointing out the error in our expression. In fact, the first transformation, which maps the points to the x-axis, does not involve the node order. The node order only comes into play during the second step when adjusting the positions of the points on the coordinate axis. In the second transformation, we can move the points on the x-axis to positions $(X, 0)$ without changing their relative order, where $X$ is the radius order of the node among all nodes. Clearly, for any ring partition on the transformed graph, we can find an equivalent ring partition on the original graph.

Definition of the graph center

Thanks for pointing out the question. Currently, we directly use the average of all coordinates as the graph center. In practical applications, we can also select appropriate centers based on real-world situations, such as designating high-traffic locations like stadiums and concert venues as centers.

We have added an ablation study in appendix B.5 to explore the the impact of selecting different centroids. We offset the centroid by a distance of up to 5% and recalculated the results of Normalized Cut. A normalized value closer to zero indicates better performance. We observe that any offset from the centroid results in a worse performance, and with greater offsets correlating to a more significant decline. We also find that in nearly half of the cases where offsets were applied, the resulting errors remained within 5%. Thus, in this paper, we opted to use the centroid as the center of the graph.

Histogram also shows that in approximately 15% of cases, offsetting the centroid yielded improvements of over 10%. In the future, we can propose a more effective strategy for centroid selection to enhance the algorithm's performance.