Learning Graph Representations in Normed Spaces

1. I do not see the novelty of the paper. Embedding in the normed space is not a new topic. Indeed, the authors themselves refer to many relevant papers in Section 3. Although the authors did not refer to papers in the machine learning community, the embedding in the normed space has been discussed even in the machine learning community e.g., [A]. Hence, the authors need to clarify the novelty of the paper.

2. While the motivation for using norm spaces is somewhat clear if we read Section 3, it is frustrating if we need to wait for it. It would be preferable to clarify what types of graphs are your paper's target in the Introduction section. In other words, it should be clarified in the introduction section for which graphs each of $l^1$ and $l^\infty$ is better than existing Riemannian manifold methods.

3. What is the benefit of the normed space embedding in applications? My concern is that although the normed space is simple in its formulation, it is not intuitive when we visualize the results even compared to those in hyperbolic space. The $l^1$ distance case might be acceptable since we could imagine Manhattan-like road structure to see the distance between two points when we see the visualization. However, I do not know how we visually understand them in the $l^\infty$, although we know that a ball is given as a hypercube there.

4. Similar concerns related to the applications. I am concerned that it is not obvious whether we can connect the embedding results to another machine learning method since I do not know any machine learning methods that the input is the normed space, although we can forcibly input it as a vector. Graph reconstruction is a good benchmark but usually not an ultimate goal. Or if the graph reconstruction is an ultimate goal, we do not need to stick to embedding.

5. The objective function (1) is unfair. It gives strong advantages to the normed space. The objective function forces the ratio between the graph distance and the distance in the embedding space to be 1:1. In practice, it can be 1:c since we usually only care the relative distance. The norm space does not care about this difference since it is linear and we can scale any shape by any factor. Specifically, for a normed space $Y$ and for any embedding function $f: \\mathcal{V} \to Y$, we always have another embedding function $f\_c$ that scales the distances among the points $(f(v))\_{v \in \\mathcal{V}}$ with the factor $c$, i.e., the embedding function $f\_{c}$ such that $d\_{Y}(f\_{c}(u),f\_{c}(v)) = c d\_{Y}(f(u),f(v))$ for all $u,v \in \\mathcal{V}$. In general metric space, it does not hold. Rather, lacking this property gives some metric spaces attractive characteristics. The objective function (1) kills those attractive characteristics. This technical issue is the strongest concern to me.

[A] Atsushi Suzuki, Atsushi Nitanda, Taiji Suzuki, Jing Wang, Feng Tian, and Kenji Yamanishi. "Tight and fast generalization error bound of graph embedding in metric space." In Proceedings of the 40th International Conference on Machine Learning, 2023

My main concern is that the algorithms for using these embeddings are tailored to each of the applications, and doesn't seem to lead to a general purpose graph embedding algorithm. The algorithms also seem to assume that distances are the natural values to bound distortions against: I had trouble seeing why would the downstream tasks using the embeddings `pick up' the fact that the distances are encoded in 1-norm.

I disagree with some of the stated contributions. Quoting directly from the abstract "we propose normed spaces as a more flexible and computationally efficient [...]". I agree that the paper directly compares against popular Riemannian manifolds as a way to show the advantages of normed spaces, but they are not introduced here or are a new concept per se. I see the contributions are purely empirical, which, in my opinion, does not necessarily mean a negative point.

With this in mind, given that the main contributions of the paper are empirical, it would make the paper more of a "keep this in mind" when considering graph embedding problems. I have also listed this as a question, but considering the link prediction experiments: if the embeddings are learned and then used by the model, how does this compare to letting the model learn the embeddings itself in a way that best solves the task? I think it is crucial here to consider how the experimental setup is done to ensure the soundness of the claim that normed spaces are a better choice for link prediction using GNNs.

Further, in low-dimensional embeddings (e.g., t-SNE) where the goal is visualisation, the asymmetry pointed out in the paper for Eq. (1) is considered a problem, as the 2D Euclidean space is not adequate for handling it. Why is that? Appendix B was not clear in explaining this. I think one way to explore it could include distortion as computed over the "local neighborhoods" (e.g., 2-hop) and distortion globally (where the number of distance comparisons could dominate the average as they are much more numerous in cases where $E << N^2$, where $E$ is number of edges and $N$ is the number of nodes. As a side note, I believe exploring why this is not an issue is a theoretical result that is of interest to the wider ICLR community.

The greatest weakness of this paper is in the scale of the empirical evidence. Most of the graphs are <= 1000 nodes, and it is well-known by machine learning practitioners that results which hold at such small scales do not necessarily scale-up in a reasonable way, particularly those methods based on gradient-descent. For a specific example, the limited performance of methods in the small-data setting in of the experiments of Figure 2 are likely explained by training issues which are problematic for such small graphs but do not present issues for larger graphs. It is particularly surprising to me that the authors have focused on such small-scale data, as one of the intended selling points of their work is the computational efficiency of the induced distance metrics.

An additional weakness is the lack of theoretical statements related to the proposed metrics. The absence of such theoretical claims is not a deal-breaker for the paper, but this makes the limited scale of the empirical evidence all the more problematic, as theoretical results which might suggest (for example) greater representational capacity of the proposed metrics at larger scales are not available.

As a final weakness, there is limited understanding presented in the work - for example, intuition as to why these particular choices of norm work better than alternative approaches. The authors do present some motivation in Section 3 - "Theoretical Inspiration" - however the collection of facts here do not suggest to me any particular reason to favor $\ell^1$ or $\ell^\infty$ over $\ell^2$. For a more specific critique, the authors do not present any particularly compelling reason why $\ell^\infty$ works best for shallow embeddings, while $\ell^1$ works best when using a GNN.