- Rating
- 2
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes Graph Homomorphism Distortion (GHD), a new graph distance that considers both graph structure and node features. Specifically, GHD measures the minimum worst-case distortion of node features under graph homomorphisms, which preserve the adjacency relationships between nodes.
To make the computation tractable, the authors employ tree decomposition and dynamic programming, together with an approximation strategy that reduces the treewidth of the input graphs.
The authors evaluate the discriminative power of GHD on BREC and further use GHD-based graph encodings as additional features for GNNs. Experiments on ZINC, NCI1, and ogbg-molhiv demonstrate improvements in predictive performance.
Critical strengths
The main strength of this paper is the idea of defining a graph distance based on node feature distortion under structural constraints imposed by graph homomorphisms. This provides a different perspective from traditional homomorphism counts and is an interesting direction for measuring graph similarity.
Another positive aspect is that the authors go beyond the theoretical formulation and investigate the use of GHD as a graph encoding for GNNs. In particular, the combination of GHD with existing subgraph counts improves predictive performance, suggesting that GHD may capture complementary information.
Critical weaknesses
1. About motivation, related work, and experimental validation
I found some statements in the Introduction potentially inaccurate or misleading. For example, the authors state:
"since WL is a combinatorial measure, it only captures graph structure while ignoring any features." (lines 35 and 36)
However, WL can incorporate initial node features, and message-passing GNNs also aggregate information from both node features and graph structure. I believe the authors' intended argument is that standard WL-based distinguishability tests do not directly quantify continuous differences between graphs, rather than that WL cannot incorporate node features. This distinction should be made clearer.
I also found the discussion of related work somewhat incomplete. Several existing studies combine the Weisfeiler–Lehman framework with optimal transport to measure fine-grained differences between graphs, including Wasserstein Weisfeiler–Lehman Graph Kernels (Togninalli et al., 2019), Weisfeiler–Lehman Meets Gromov–Wasserstein (Chen et al., 2022), and Wasserstein Graph Distance Based on L1-Approximated Tree Edit Distance between Weisfeiler–Lehman Subtrees (Fang et al., 2023). These studies are closely related to the motivation of this paper, and I would encourage the authors to discuss them and clarify the differences from GHD.
Regarding the experiments, since the main contribution is a new graph distance, I believe comparisons with existing graph distance methods are important. The current evaluation mainly focuses on comparisons with count-based structural encodings. It would be useful to construct graph encodings using existing distances, such as Fused Gromov–Wasserstein or Wasserstein WL, and evaluate them under the same GNN framework. This would help determine whether the improvements come from the specific properties of GHD or simply from incorporating additional graph-distance information.
Furthermore, I think the paper would benefit from experiments that separately evaluate the ability of GHD to capture fine-grained differences in node features and graph structure. For example, one could fix the graph structure while gradually perturbing node features, and separately fix the node features while modifying the graph edges. The current experiments on BREC and downstream prediction tasks do not directly establish whether GHD captures these two types of differences in the fine-grained manner emphasized in the motivation.
2. About theoretical properties of GHD and approximation guarantees
One concern is that GHD becomes infinite when a graph homomorphism does not exist in either direction. While this is not mathematically incorrect, it raises a question about the motivation of capturing fine-grained differences between graphs.
For example, a path with three nodes and a triangle differ by only one edge. However, there is no graph homomorphism from the triangle to the path, so their GHD is infinite. In such cases, it is unclear whether GHD provides a meaningful characterization of the magnitude of structural differences. Since the paper explicitly identifies the sensitivity of graph isomorphism to small structural changes as a limitation of existing approaches, I believe this issue deserves further discussion.
I am also concerned about how infinite distances are handled when GHD is used as a graph encoding. Since the authors use cycle graphs as reference graphs, cases where no homomorphism exists may arise in practice. However, I could not find a clear explanation of how such values are handled before being passed to the MLP.
There also appears to be an issue with Proposition 3. The proposition states that for a subgraph , . However, the proof in Appendix C (p. 20, lines 1063–1072) uses the inclusion homomorphism , which establishes the reverse direction, namely . This distinction seems important for the approximation argument in Section 3.4 (p. 6, lines 292–301), particularly the claim that the subgraph-based approximation does not overestimate the original distance. Since zero distortion in one direction does not imply , the claimed lower-bound guarantee does not appear to follow from the presented proof. (Could the authors please verify this point?)
Finally, although the authors report computational speedups and graph distinguishability results for different treewidth settings, the approximation error with respect to the original GHD is not directly evaluated. I believe such an evaluation is necessary to better understand the accuracy and limitations of the proposed approximation.
3. About notations
I have not exhaustively checked all the notation throughout the paper, but I noticed several instances of inconsistent or mathematically imprecise notation. I encourage the authors to carefully review the notation throughout the main text and appendices to ensure consistency and mathematical rigor.
Below are a few examples of apparent issues:
-
Proposition 2 (p. 5, lines 222–224): Although is defined as a distance between graphs, the expression takes vertex sets rather than graphs as its arguments.
-
Section 4 (p. 6, lines 313–320): The color histogram is defined as a multiset, but the paper states . The left-hand side is a set, whereas the right-hand side is a multiset, so they are not generally equal.
(The following two issues have already been raised in section 2)
-
Proposition 3 (p. 5, lines 250–257; p. 20, lines 1063–1072): The proposition states that , whereas the proof uses the inclusion homomorphism . According to Definition 1, this establishes , so the direction of the distortion is inconsistent with the statement.
-
Definition 1 and Section 3.3 (pp. 3, 5): Since the authors define , the distance can take infinite values. However, the graph encoding is defined as , which appears inconsistent with the possible range of the distance.
These are only a few examples, and similar issues may exist elsewhere in the paper. Some of them go beyond notational inconsistencies and may affect the correctness of the mathematical statements or proofs. I therefore recommend that the authors carefully review and clarify the notation throughout the paper.
Questions for authors
1. Handling infinite distances
How are infinite GHD values handled when constructing graph encodings, particularly before passing them to the MLP? Could the authors also report how frequently infinite distances occur in the evaluated datasets?
2. Theoretical justification of the approximation
In Proposition 3, the direction of the distortion appears to be reversed between the statement and the proof. Could the authors clarify this point? In particular, does the claim in Section 3.4 that the subgraph-based approximation does not overestimate the original distance still hold?
3. Validation of fine-grained graph similarity
Could the authors provide experiments that separately evaluate the sensitivity of GHD to changes in node features and graph structure? For instance, it would be informative to examine how GHD changes under gradual feature perturbations and small edge modifications.
Additionally, comparing GHD-based graph encodings with encodings constructed from existing graph distances under the same experimental setup would help clarify the specific advantages of the proposed distance.
3 comments
Several concerns remain unresolved.
First, the comparisons with FGW and WWL are still only promised, so it remains unclear whether the improvements come from GHD itself or simply from adding graph-distance information.
Second, the authors now state that GHD captures attribute distances under structural constraints rather than fine-grained structural differences. This conflicts with the Introduction, which motivates the method by the sensitivity of isomorphism-based approaches to small structural changes. GHD shows the same issue in a more extreme form: a path on three vertices and a triangle differ by only one edge, yet their distance is infinite. The claim that GHD is more structurally sensitive than WL is also unsupported.
Third, about 60% of the distances are infinite on ZINC, ogbg-molhiv, and NCI1. The encoding therefore largely acts as a binary flag for whether a homomorphism to each cycle exists, rather than as a continuous distance. Since this information is determined by simple properties such as bipartiteness and odd girth, an ablation against such binary indicators is needed. In addition, the placeholder value of 100 is smaller than some finite values, which breaks the ordering of distances, and the stated characterization of homomorphisms to odd cycles is incorrect.
I therefore maintain my score.
Response 2
Thank you for the additional queries for clarity. We address all remaining concerns below and clarify some of the claims in the response to our rebuttal.
First, we have added Table S.9. with a comparison on ZINC of using WWL and FGW. We don’t think our method's validity should rely on just being better than any other method as that might give an incorrect characterization of its usefulness. However, we see that WWL and FGW are not as good as either or homomorphism counts.
Second, we think both of these interpretations are valid, complementary lenses through which to view our method. Our claim in the Introduction is that WL cannot account for small differences, our proposed method aims to address this particular shortcoming. In some cases, like and , the absence of an edge leads to an infinite distance. Our claims on measure sensitivity refer to the cases where the distance is finite. In Definition 1 and what follows of Section 3 we clearly state that a continuous distance can only be achieved when homomorphisms exist both ways. If there are not, GHD degenerates to a binary flag, as the reviewer correctly points out.
In the most general sense, for two graphs and with order and , WL trivially deems them to be non-isomorphic if they have a different order, i.e, .$ n \neq m$, whereas our method assigns a continuous distance between them. This can be infinity, yes, but it’s not always the case. As a concrete example, take and with node degree as attribute functions. The will be , thus accounting for subtle differences of nodes and connectivity in the claw graphs, whereas WL always just deems non-isomorphic. A similar example of the usefulness of our method can be derived for graphs of the same order by comparing with . We have added a clarification in the introduction and in the limitations (Line 055 and Line 493, in blue in the updated manuscript) underlining that our method gives a quantifiable distance only in case homomorphisms exist, while it is as informative as a binary flag outside of this range.
These corner cases do not undermine the property of GHD of providing more fine grained discrimination with respect to WL, which merely partitions pairs of graphs between isomorphic and non isomorphic. Empirical validation further supports the usefulness of our proposal, especially in the case of BREC graphs, undistinguishable by WL.
Third, to demonstrate the commitment to our work, we have run a set of additional ablations on ZINC incorporating the concerning cases raised by the reviewer. For the binary flag ablation we set the entries of the encoding vector to 0 and and change it to 1 if distances are infinite, representing a binary flag of bipartiteness, odd-girth and other properties derived from absence of homomorphisms. In addition, we also add an ablation to account for values larger than the naive cap of 100. We normalize the output of the to the as , where we set 1 if is NaN, i.e., is infinity in the case where no homomorphisms exist both ways. Table S.8 shows these results. In summary, the binary flag case (Binary) is barely better than baseline and worse than and the normalized range (Capped) is equivalent to our results in Table 2 and within standard deviation.
As a clarifying statement, It’s true the odd cycle claim is only partially correct. For a graph and the cycle graph, with odd , there is a homomorphism from to iff there is an odd cycle with at most size in .
We thank the reviewer for the additional requests for clarification and ablations, which have strengthened the soundness of our claims against various caveats and comparison partners. We would appreciate a rise in the score if no further doubts arise and all doubts have been resolved. Otherwise, we remain available if any further requests for clarifications arise.
Response 1
We thank the reviewer for their careful reading of the manuscript and detailed feedback. We address each concern in turn below. In the interest of clarity we keep our responses brief though we are happy any points that remain open.
CW1, CW3. In the revised manuscript (changes highlighted in blue), we have addressed the concerns regarding the motivation, related work. We agree that it would be of interest to have a comparison with FGW and WWL. We will work on producing these results during the discussion period to have them included in the final version of the manuscript.
CW2. It is true that for fine-grained distances the existence of a homomorphism is required. Moreover, we do not posit that we capture structural fine-grained differences but rather that we capture distances in the attributes restricted by the structure. That is, we include the structure as a restriction. Since defining what accounts for a slight change to a graph is removal of an edge, a vertex, a connected component, we aim to use the graph as a constraint on the attribute function. We believe that in this sense, we are more structurally sensitive than WL.
Q1 To represent infinite distances we used a marker value for infinity at 100. In the case of BREC, graphs with a non-zero are always deemed different, irrespective of the difference. In the TW1 (MST-based reduction) reduction case there are no infinite values. In the TW2 case, 9 out of 400 pairs have infinite distance.
In the case of ZINC, NCI1 and ogbg-molhiv, the value present at the position of infinite distance to the proxy family will have the placeholder 100. In the case of RWPE this is far larger than any value while in the case of SP and ER there are 2% of values that are bigger.
In terms of the prevalence of infinite distances we have found that on ZINC, ogbg-molhiv and NCI1 it is around 60%. It may disencouraging, however it makes complete sense. As pointed out previously, only bipartite graphs will have homomorphism into Cn for even n. If it is not bipartite, then it will have a homomorphism to Cn with n odd only if it contains a ring of that size. Thus this acts like a binary flag in certain signature positions, while in others it's a continuous distance.
Q2. Regarding Proposition 3, as you pointed out, we mistakenly reversed the direction of the distortion. We have corrected this in the revised manuscript, and we thank you for pointing out this notational issue. We have updated Proposition 5 to Corollary 2 and added a new Proposition 5, which is what actually corresponds to our experimental setting. We believe this results in a clearer picture. The previous requirement for induced subgraphs is not anymore a requirement in this case, we just required subgraphs.
Q3. We ran experiments comparing dHD under structural perturbations and attribute perturbations. They are shown in Appendix E in Table S.6 The structural perturbations introduce changes in the graph structure while the attribute perturbation swap values of attributes between pairs of vertices in the graph. We are also running experiments evaluating the distances as encodings in graph learning tasks and will make sure to include and discuss them in the final version of the manuscript.
We sincerely thank the reviewer for their constructive feedback and helpful suggestions. We remain available for further questions, and we kindly ask that you consider raising your score if our responses have resolved your concerns.