acceptodds
Under review as a conference paper at ICLR 2027

Graph Homomorphism Distortion: A structural (pseudo)-metric for attributed graphs

Abstract

A large driver of the complexity of graph learning is the interplay between structure and features.When analyzing the expressivity of graph neural networks, however, existing approaches ignore features in favor of structure, making it nigh-impossible to assess to what extent two graphs with close features should be considered similar.We address this by developing a new (pseudo-)metric based on graph homomorphisms.Inspired by concepts from metric geometry, our graph homomorphism distortion measures the minimal worst-case distortion that node features of one graph are subjected to when mapping one graph to another. We demonstrate the utility of our novel measure by showing that: 1) it can be efficiently approximated under some additional assumptions, 2) it provides a granular approach to graph distinction and 3) it serves as a structural encodings, extending the concept of homomorphism counts to atrributed graphs, which improve the predictive capabilities of graph neural networks.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, geometric deep learning, graph learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_7oDvOpenReview ↗
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 G′⊆GG' \subseteq G, dis(G,G′)=0\mathrm{dis}(G,G')=0. However, the proof in Appendix C (p. 20, lines 1063–1072) uses the inclusion homomorphism φ′:G′→G\varphi':G'\to G, which establishes the reverse direction, namely dis(G′,G)=0\mathrm{dis}(G',G)=0. 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 dHD(G,G′)=0d_{\mathrm{HD}}(G,G')=0, 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:

  1. Proposition 2 (p. 5, lines 222–224): Although dHDd_{\mathrm{HD}} is defined as a distance between graphs, the expression dHD(ρ(V(G)),ρ′(V(H)))d_{\mathrm{HD}}(\rho(V(G)),\rho'(V(H))) takes vertex sets rather than graphs as its arguments.

  2. Section 4 (p. 6, lines 313–320): The color histogram h(G)h(G) is defined as a multiset, but the paper states Im⁡fG=h(G)\operatorname{Im} f_G=h(G). 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)

  1. Proposition 3 (p. 5, lines 250–257; p. 20, lines 1063–1072): The proposition states that dis⁡(G,G′)=0\operatorname{dis}(G,G')=0, whereas the proof uses the inclusion homomorphism ϕ′:G′→G\phi':G'\to G. According to Definition 1, this establishes dis⁡(G′,G)=0\operatorname{dis}(G',G)=0, so the direction of the distortion is inconsistent with the statement.

  2. Definition 1 and Section 3.3 (pp. 3, 5): Since the authors define inf⁡∅=∞\inf\varnothing=\infty, the distance dHDd_{\mathrm{HD}} can take infinite values. However, the graph encoding is defined as Γ(G)F∈R∣F∣\Gamma(G)_{\mathcal F}\in\mathbb R^{|\mathcal F|}, 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
AuthorsOpenReview ↗

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 CnC_n for even n. If it is not bipartite, then it will have a homomorphism to CnC_n with nn 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 dHDd_{HD} 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.

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.

AuthorsOpenReview ↗

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 dHDd_{HD} 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 C3C_3 and P3P_3, 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 GG and HH with order n:=∣G∣n := |G| and m:=∣H∣m:= |H|, 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 G=K1,nG = K_{1,n} and H=K1,mH = K_{1,m} with node degree as attribute functions. The dHDd_{HD} will be ∣n−m∣|n - m|, 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 G:=P4G := P_4 with H:=K1,3H := K_{1,3}. 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 dHDd_{HD} to the [0,1][0,1] as dHD/(1+dHD)d_{HD}/(1+d_{HD}), where we set 1 if dHD/(1+dHD)d_{HD}/(1+d_{HD}) is NaN, i.e., dHDd_{HD} 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 dHDd_{HD} 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 GG and CnC_n the cycle graph, with odd nn, there is a homomorphism from CnC_n to GG iff there is an odd cycle with at most size nn in GG.

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.

Reviewer_bXgdOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces graph homomorphism distortion (GHD), a continuous dissimilarity for vertex-attributed graphs obtained by minimizing worst-case attribute distortion over graph homomorphisms in both directions. The authors study metric-like and discriminative properties of this quantity, relate it to Hausdorff distance and 1-WL, and construct a graph encoding by measuring distortion to a reference family. Because exact homomorphism computation is expensive, the practical method replaces graphs by bounded-treewidth subgraphs (treewidth 1 or 2) before computing the distance.

The paper evaluates discrimination on BREC and downstream graph learning on ZINC-12K, NCI1, and ogbg-molhiv. The core idea is interesting and the paper contains substantial theory, but I have concerns about the correctness/scope of a central WL comparison and, more importantly, about whether the practical bounded-treewidth proxy preserves the invariance and meaning of the exact construction. Under a slightly strict ICLR bar I am just below acceptance.

Critical strengths
  1. The proposed object is conceptually distinctive: it combines homomorphism-constrained structural matching with continuous attribute distortion, providing a graded notion of graph similarity rather than only binary isomorphism/WL distinction. The paper develops this idea through several theoretical properties rather than presenting only an encoding heuristic.

  2. The empirical validation spans both structural discrimination and downstream prediction. The BREC results show that the choice of structural attribute function matters, and the ZINC/NCI1/ogbg-molhiv experiments provide evidence that the distortion encoding can be useful alone or complementary to homomorphism/subgraph counts. This breadth makes the contribution more compelling than a purely formal metric proposal.

Critical weaknesses
  1. The scope of the WL comparison and the transition from the theoretical distance to the practical encoding need clarification. Theorem 2 does not require the two graphs to have the same order, although its proof invokes Lemma 3, which assumes this. A direct counterexample is given by C_4 and C_6: under standard 1-WL with uniform initialization and a shared color encoding, they have the same colors but different multiplicities, and they admit homomorphisms in both directions. Consequently,

    d_WL(C_4, C_6) = 1, whereas d_H(C_4, C_6) = d_HD(C_4, C_6) = 0.

    This contradicts the general statement of Theorem 2. The issue may be repairable by restricting the result to connected graphs of the same order, but the scope of the related discriminative and topological claims also needs to be made explicit.

    Beyond the terminology of an extended pseudometric, I am concerned about how infinite distances enter the practical encoding. Under Definitions 1–2 and the original cycle reference family in Table 2, no input graph can have finite symmetric distances to both C_3 and C_4: the former requires the input graph to contain a triangle, whereas the latter requires it to be bipartite. Thus, as defined, every input encoding has at least one infinite coordinate, yet the manuscript represents this encoding as a real-valued vector and feeds it into an MLP.

  2. The claimed non-overestimation guarantee for the bounded-treewidth approximation does not hold, and invariance of the implemented reduction is not adequately supported. Following Proposition 5, Section 3.4 claims that choosing induced subgraphs yields d_HD(G, H) >= d_HD(G', H'). However, with inherited attributes, the inclusion map only guarantees the directional distortion dis(G', G) = 0; it does not justify removing the symmetric error terms in Proposition 5. A direct counterexample uses the same constant attribute for all vertices: let G = H = K_4 and choose induced subgraphs G' = K_3 and H' = K_2. Then

    d_HD(G, H) = 0, whereas d_HD(G', H') = infinity,

    because no homomorphism exists from K_3 to K_2. Thus, this is not merely a lack of approximation-quality experiments: a stated guarantee used to justify the approximation is false.

    The implementation also uses a minimum spanning tree or greedy edge additions to construct low-treewidth graphs. These operations generally do not implement the induced-subgraph construction invoked above, and their outcomes may depend on vertex labels, edge iteration order, or tie-breaking. The manuscript needs to explain how the resulting distance/encoding remains isomorphism-invariant and support this with vertex-relabeling tests and exact-versus-approximate comparisons on small graphs. Otherwise, the distinctions reported on BREC may partly reflect artifacts of the reduction rather than valid discrimination of the original graph structures.

Questions for authors

Clarification that could change my assessment:

  1. Does Theorem 2 assume |V(G)|=|V(H)| (or another condition that makes Lemma 3 applicable)? If not, please explain how d_WL <= d_H handles equal color supports with different color multiplicities.
  2. Because inf(empty)=infinity, on what domain is d_HD intended to be a finite pseudometric? Should the global object be described as an extended pseudometric, and do the topology statements require adjustment?

Evidence that could change my assessment: 3. Is the implemented treewidth-1/treewidth-2 reduction invariant to vertex relabeling and edge ordering? If yes, please specify/prove the canonical construction; if not, please report a relabeling test and explain how the resulting quantity can serve as a graph invariant. 4. On graphs small enough for exact computation, how closely does the bounded-treewidth proxy track exact d_HD (error, rank correlation, or pairwise ordering), and how sensitive are downstream results to the reduction/reference family?

2 comments
AuthorsOpenReview ↗

Response 1

We thank the reviewer for the careful evaluation of the manuscript and the detailed feedback. We address each of the reviewers' concerns separately below. In the interest of clarity we keep our responses brief though we are happy to clarify any points that remain open.

CW1 and Q1. This observation is correct, Theorem 2 (along with Propositions 6 and 7) assumes ∣V(G)∣=∣V(H)∣|V(G)| = |V(H)|. We did not state this assumption explicitly in the section: since graphs with different numbers of vertices are trivially distinguished by the WL isomorphism test, we had implicitly restricted our analysis to graphs of equal cardinality. The updated manuscript (changes highlighted in blue) clarifies this assumption for the entire section and states it explicitly in the affected theorems and propositions. Thank you for pointing this out.

CW2. We have updated Proposition 5 and corrected it to Corollary 2 to point out that accounting for the infinity results in a similar but not identical inequality. Additionally, we have added a new Proposition 5, which is the real bound we use for calculating the approximations empirically. We believe that this reformatting improves clarity.

Q2. We agree that the measurement name should be an extended pseudo-metric and that the case specified in the CW2 is a consequence of infinity being present. We have corrected this in the manuscript. Please note that the results and conclusions of the work do not change by this adjustment. We refer the reviewer to our previous response and the general response containing more details.

Q3. We agree that the reduction is not invariant to vertex relabeling and edge ordering. It could be made for the case of TW1 by assigning edge-weights given by some combination of features of vertices and then picking edges sorted by this value for the MST algorithm. However, highly symmetric graphs as BREC would inevitably include similar values which would result in random tie breaking. Nevertheless, any choice of subgraph still works since both procedures, TW1 and TW2 reductions, only delete edges. Since we keep the rooted-invariants from the original graph, the set of homomorphisms only grows, since restrictions decrease, resulting in the bound diminishing. In that sense, the process results in an invariant, i.e., for isomorphic graphs, it will evaluate to 0 but depending on the choice for some non-isomorphic graphs it could also evaluate to 0. This comment provides an interesting venue for improving our method, for example by trying over different seeds or using canonicalization techniques! We will consider this in future work.

Q4. We have run preliminary experiments on how close the reductions track the dHDd_{HD} on ER graphs. Appendix E in Table S.7 and Table S.8 show the results for both the computation of the extended pseudometric and the computation of the encodings for learning tasks. Note that tw1 has a greater error than tw2, according to our previous experiments. This strengthens our claims, as the degree of decomposition is a tunable parameter that changes efficiency for accuracy.

We thank the reviewer for the constructive feedback. We welcome any further questions and are available for immediate discussion. If our responses have resolved the concerns raised, we would appreciate a reassessment of the score to reflect these improvements.

We want to thank again the reviewer for the comments and thorough feedback. As the rebuttal period draws to a close, we would like to know whether our comments have fully addressed the reviewers concerns. If that is the case would appreciate it if the reviewers would consider our comments favorably when it comes to updating the scores, otherwise we remain available for further discussion.

Reviewer_jMCUOpenReview ↗
Rating
4(+1)
Confidence
4(+1)
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Graph Homomorphism Distortion (GHD), a continuous measure of graph dissimilarity that incorporates both graph structure and node attributes. The authors analyze its mathematical properties and expressive power, develop a computational approximation, and evaluate its effectiveness on graph expressivity benchmarks and molecular property prediction tasks.

Critical strengths
  1. The paper presents a relatively comprehensive theoretical framework, covering the mathematical definition of GHD, its properties, and its expressive power.

  2. The experimental evaluation is relatively comprehensive, including expressivity assessment on BREC and predictive performance on molecular property prediction tasks.

  3. Rather than relying solely on traditional graph isomorphism tests to measure expressive power, the paper introduces a continuous measure of graph dissimilarity. This provides a more fine-grained perspective on comparing attributed graphs.

Critical weaknesses
  1. The theoretical comparison of expressive power requires further justification. Traditional WL distinguishability is a discrete property, whereas the numerical value of GHD depends on the distance metric and scale of the node attributes. Therefore, directly comparing their numerical values may not provide a sufficiently rigorous characterization of their relative expressive power.

  2. The authors define the distortion as infinity when no homomorphism exists between two graphs. However, how is this infinite distance handled in practice when there is no homomorphism between a reference graph and an input graph?

  3. The paper does not sufficiently isolate the contributions of the node attribute encoding Ψ\Psi, the homomorphism constraints, and the choice of reference graphs. Additional ablation experiments are needed to clarify whether the performance improvements primarily come from the node encodings or the proposed distance measure.

Questions for authors

See the weakness.

7 comments

We thank the reviewer for their constructive feedback and for highlighting the theoretical and empirical strengths of our paper. We clarify the raised concerns below.

CW1: We agree that WL distinguishability is a discrete property, while the numerical value of dHDd_{HD} depends on the metric and scale of the node attributes. Our comparison of distinguishing capabilities is established by Proposition 6: when WL colorings are used as vertex attributes, any pair of graphs distinguished by WL has strictly positive dHDd_{HD}. So the comparison is between zero versus nonzero distance, rather than numerical magnitudes, and is unaffected by positive rescaling of the color encoding. Furthermore, the numerical ordering in Theorem 2 is a separate statement under the specified integer encoding of WL colors, which allows for direct comparison since distinct colors are separated by a distance of at least one. We have revised the manuscript (changes highlighted in blue) to make this distinction and the role of the chosen encoding more explicit.

CW2. Presence of infinity in dHDd_{HD} (Practice): To represent infinite distances, we set a marker value that is greater than any attainable distance under the used encodings. Given the sizes of the graphs in BREC, ZINC, NCI1 and ogbg-molhiv, it suffices to use 100 for ER, RWPE and SP. In the case of BREC, graphs with a non-zero distortion to another have 100 which is above the threshold of machine precision. For TW1 reduction (MST-based), BREC graphs have no infinite values. For the case of TW2, 9 out of 400 pairs have infinite distance. In the case of ZINC, NCI1 and ogbg-molhiv, the value for infinite distance in the encoding is generally chosen to be 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. Since this would imply that some values are “over infinity” we rerun the learning experiments for a placeholder of 1000 and results are within a standard deviation. We conclude by this that this 2% was not extremely relevant empirically. We will include this in the ablations of the final manuscript.

CW3. We performed an additional set of experiments to disambiguate the impact of the choice of rooted-invariant and our extended pseudo-metric, where we only add the rooted-invariant as a PE. They are shown under the PEs column in the revised manuscript in Table 1 and Table 2.

We sincerely thank the reviewer for positive evaluation and constructive feedback. We remain available for further questions; we believe to have addressed your concerns and we would hope that this would be reflected in your score.

We want to thank again the reviewer for the comments and thorough feedback. As the rebuttal period draws to a close, we would like to know whether our comments have fully addressed the reviewers concerns. If that is the case would appreciate it if the reviewers would consider our comments favorably when it comes to updating the scores, otherwise we remain available for further discussion.

Thanks for the rebuttal. My concerns have been addressed. I have increased my score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response 1

We thank the reviewers for their constructive feedback and for highlighting the theoretical and empirical strengths of our paper. We have updated our manuscript highlighting in blue the changes made during the rebuttal. In the following general response, we resolve concerns and corrections that were common to different reviewers. It is important to note that none of our conclusions are affected by these changes—they merely increase clarity and rigor:

Theorem 2 Statement: (along with Propositions 6 and 7) assumes ∣V(G)∣=∣V(H)∣|V(G)| = |V(H)|. We did not explicitly state this assumption in the section: since graphs with different numbers of vertices are trivially distinguished by the WL isomorphism test, we had implicitly restricted our analysis to graphs of equal cardinality. The updated manuscript clarifies this assumption for the entire section and states it explicitly in the relevant theorems and propositions.

Proposition 3: Since we are using the inclusion homomorphism, the correct direction of 0 distortion through it is dis(G’,G)dis(G’, G). The statement had a typo on the apostrophe. We have corrected this in the manuscript.

Presence of infinity in dHDd_{HD} (Theory): The observations from the reviewers are correct and the correct terminology for this pseudo-metric is an “extended pseudo-metric”. We have updated the manuscript to reflect this. All of the theoretical results hold under this setting. We have updated Proposition 5 to the real bound we use in practice and updated the previous bound to be correct and left it as Corollary 2. We believe that this improves clarity.

Presence of infinity in dHDd_{HD} (Practice): To represent infinite distances we set a marker value that is greater than any attainable distance under the used encodings. Given the sizes of the graphs in BREC, ZINC, NCI1 and ogbg-molhiv, it suffices to use 100 for ER, RWPE and SP. In the case of BREC, graphs with a non-zero distortion to another have 100 which is above the threshold of machine precision. For TW1 (MST-based reduction), reduction BREC graphs have no infinite values. For the case of TW2, 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. We have clarified this in the revised manuscript. Since this would imply that some values are “over infinity” we rerun the learning experiments for a placeholder of 1000 and results are within a standard deviation. We conclude by this that this 2% was not extremely relevant empirically. We will include this in the ablations of the final manuscript.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.