Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work considers geometric graphs having both non-uniform sampling density, as well varying neighborhood radius. Under this model, a GSO can be though of as a discretization of the latent continuous Laplacian. In order for this GSO to approximate the continuous laplacian, the adjacency matrix needs to be normalized according to the sampling density. The non-uniform geometric graph model considered here seems a plausible model for real-world graphs. Of course, though, the sampling density is not known in practice. For this reason, it estimates the sampling density using a NN in a self-supervised manner. Experiments on synthetic datasets, where the ground truth sampling density is known, show that indeed this NN approach can well approximate the true underlying sampling density. Finally, it concludes with a set of experiments that seem to validate the hypotheses stated earlier in this work. More precisely, performance is improved in classification tasks, while learning density values can be used as a way to assign importance scores to nodes.
strength_and_weaknesses: *  After the introduction of the non-uniform geometric graph model, the resulting GSO is properly derived with a bound on the convergence of it to the continuous laplacian.
* There is an admirable effort to justify the reasoning behind using the proposed geometric model through experiments where the decoder is restricted to be a geometric graph with hubs and with experiments that try to demonstrate the applicability of this work in practical tasks.
* However, as the work builds on the assumption of slowly changing density functions and piece-wise neighborhood radius, there should be a better discussion of it with other models, e.g. in statistical models there is a notion of popularity/expansiveness that differs for each node [1].
* From a clarity perspective, this work is, in my opinion, weakly motivated. For example, the relevant section starts with a discussion on ways to compare graphs for similarity. It is not clear how this is connected with this work. Moreover, while GSO are central to this work, the definition on them is not repeated in order to start a discussion on how they are used and why this approach can be better than other approaches. In general, reading this work leaves you with a question-mark on what the main target of it is.
* Moreover, in the experimental section regarding classification accuracy there is no comparison with works that learn a parameterized form of GSO (like the one of dasoulas et al. cited in this work). It is a question of whether we could have both pgso and this work combined.
* Finally, for the learned $1/\rho$, of the real-world networks, it would be interesting to see some plots and how they are different from let's say $1/\sqrt{deg}$.


[1] https://arxiv.org/pdf/0912.5410.pdf
clarity,_quality,_novelty_and_reproducibility: This work in general could be more clearly written, starting from motivating properly what this work is trying to do and why. For example, do we just want to derive a proper normalization of the adjacency matrix in a way that improves classification performance, or we want to explain in a theoretical grounded way why this normalization is necessary? Also, I think section 2 is quite verbose and each subsection does not seamlessly build on what is discussed in the previous one. E.g., section 2.2 starts by discussing again eq 1 with little reference to what was discussed right before (in deriving eq 2). 
In terms of quality more could be done in the experimental section with respect to comparing with other methods for learning parameterized graph shift operators, or a discussion with other latent models that try to learn graphs and assume different levels of popularity for each node.
In terms of originality of this work, it studies geometric graphs in a different context than it was done before. So far, geometric graphs were (mostly) assumed to be uniform as they were mostly studied as a theoretical model with concrete expressions on properties of them, e.g. degree distribution. Hence the uniformity assumption to derive such expression. From the GSO side, this work takes a rather different angle, rather than learning the parameters, it learns a way to normalize the adjacency matrix.
summary_of_the_review: I believe this work has some potential, though certain things need to be addressed. Mostly related to clarity, better motivating this work and focussing on the exact question/problem it tries to answer/solve. This will drive both the theoretical explanation and empirical evaluation in a more clear and concrete way.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper has considered non-uniformly sampled graphs from a metric-probability space and developed methods to estimate the unknown sampling density from those graphs. Also, the authors have experimentally tested the model and approach on synthetic and real-world graphs.
strength_and_weaknesses: Strength: The topic seems quite interesting and is of high practical value. 

Weakness: the presentation of the paper overall is not good. There are lots of typos and grammar issues that prevent me from understanding the paper well. Authors are suggested to overhaul the whole organization of the paper as well.

1) Subsection 1.1 on page 2, titled *Our Contributions* is poorly written. It actually states not *contributions* but more about *motivations*. Thus, I suggest integrating it into part of the introduction. 

2) Hard to appreciate the contributions in the paper. Suggestions: please state the primary approach to estimate the unknown sampling density, highlight the differences between the proposed method and existing ones, and identify challenges that arise from uniform sampling to non-uniform sampling. Especially please explain in detail the implications and significance of Proposition 1 on top of page 5 in the estimation of the sampling density. I was given the impression that the techniques presented in the paper are just simple generalizations of the existing ones (perhaps I am wrong). 
clarity,_quality,_novelty_and_reproducibility: The writing is not good.
summary_of_the_review: See the above.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper is interested in the study of geometric graphs, i.e. graphs sampled from an underlying metric space, such that the neighbourhoods are determined by the graph distance. In particular, it focuses on the case where the sampling measure $\nu$ differs from the intrisic measure $\mu$ of the underlying space (i.e. the one used to compute the classical Laplacian).

The authors develop a general form for a neighbourhood function and a geometric Laplacian, which can be understood as a Laplacian whose kernel $K(x, \cdot)$ is simply the indicator of a given ball around $x$. They also provide the corresponding definition for the discrete graph Laplacian, which depends on the sampling density $\rho = d\nu/d\mu$.

The next step is thus to estimate $\rho$; the authors introduce the concept of "Geometric graph with Hubs", which approximates real-worlds graphs decently well. In this model, $\rho$ is approximately proportional to the graph degree, and hence $\rho^{-1}$ can be learned by an equivariant neural network taking as input the node degrees.

Finally, they provide several numerical experiments showing how the density estimation step improves the performance of classical graph convolutional networks. They compare the performance when the Laplacian is corrected with $\rho$ and when it's not, as well as when the correction is only done in the last pooling layer.
strength_and_weaknesses: The problem of non-uniform sampling for geometric graphs is quite natural: it's normal to expect that the sampling measure does not exactly match the density of the graph. The methods developed are sound, and seem to be vindicated by the experiments, although it is interesting that adding density estimation mainly reduces the variance and does not affect too much the average/best performance.

On the other hand, the paper is a bit too technical in several aspects, which might hinder its readability for people that are not at the exact field intersection.
- on the theoretical side, it glosses quite quickly over definitions 3 and 4. In particular, the functions m^{(i)} are added without any explanation, except the one given in Appendix C; it might be more illuminating to move part of the appendix to the main text, so that readers used to classical graph theory can make the link between the usual Laplacians and the one in Equation 3. I also don't see the point of introducing the multiplication operator for Definition 3, as opposed to the more explicit forms used previously. It does make a nice parallelism between $\mathcal M$ and the diagonal matrices of Definition 4, but if that is the goal it should be made more explicit.
- the experiment section makes several references to the internals of laplacian-based networks, especially the pooling layers; it would be interesting to see how the density estimation exactly factors into that, even as an additional appendix.
clarity,_quality,_novelty_and_reproducibility: Minor remarks:
- why is the "related work" section at the very end of the paper ? it provides some nice context for the whole paper.
- above Definition 4, you do not use the introduced notation for $q(u)$.
- I haven't found the proof for Lemma 1 in the appendix
summary_of_the_review: This is a good paper, that could use some more work to broaden its appeal to non-expert readers.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper introduces a framework allowing to correct the matrix representation (or graph shift operator) of a non-uniform geometric graph according to how this graph is sampled from the underlying metric space, namely, according to a sampling density and a neighborhood radius that is assumed to vary across the graph. Further, it proposes a self-supervised method to estimate the sampling density when the underlying metric space is unknown, and empirically demonstrates that using these corrected graph shift operators improves performance in a number of learning tasks.
strength_and_weaknesses: Strengths:

- The problem addressed in this paper is important: indeed, commonly used graph shift operators do not provide precise information about sampling, e.g., it is not clear whether a high-degree node in an *unweighted* graph has high degree because the area surrounding it is densely sampled, or because the sampling radius is large.
- There is a strong motivation to "correct" the graph shift operator by encoding this sampling information: empirically, degree normalized graph shift operators tend to do better than their unnormalized counterparts, so normalizing by an even more accurate measure of sampling density should fare well.
- The numerical results are convincing (though limited).

Weaknesses:

- It is not clear if this framework only applies to unweighted or to both unweighted and weighted graphs. This is an important distinction because while in unweighted graphs it is not possible to discern whether high-degree nodes stem from high sampling density or large neighborhood radius, in weighted graphs the sampling density is more related to the number of edges incident to each node, and the neighborhood radius to their edge weights. Related to this, the paper does not include any numerical results on weighted graphs. 
- The "geometric graph with hubs" model is not motivated by real-world networks, but instead, by the ability to decouple the contribution of the sampling density and the neighborhood radius. While the model works well empirically on the synthetic/citation networks considered in the experiments, there is no discussion on whether its assumptions, in particular the slowly varying density assumption, are realistic. For example, it would be important to understand whether canonical graph models typically used to model real-world graphs---such as small-world, preferential attachment, household, etc.---can be modeled as geometric graphs with hubs.
- The numerical experiments are lacking: 
   - The link prediction experiments are arguably the most important experiments, as they demonstrate the validity of the model. However, they are only performed on synthetic graphs and on relatively simple (low rank) citation networks, which are embedded in $\mathbb{R}^2$. It would be interesting to see link prediction experiments on more complex networks (perhaps the AIDS dataset?), and with larger embedding dimension.
   - The assumption motivating the self-supervised learning approach---that the task depends mostly on the underlying continuous model---is not rigorously justified, and may be too strong, e.g., in heterophilous graphs. 
    - By definition, geometric graphs with hubs have more degrees of freedom than the correlation (inner product) and conventional geometric graphs with which they are compared in Fig. 2. If possible, the authors should include comparisons with other graph models with more degrees of freedom.
- The presentation is lacking and certain concepts are not well-defined, see below.



clarity,_quality,_novelty_and_reproducibility: - The $m$ functions in Defs. 3 and 4 are not defined.
- Related to the above, Def. 4 is hard to parse. What are the interpretations of the different terms composing the Laplacian?
- In Sec. 2.2, the authors claim that "the support of the kernel can be decoupled from the value it attains by defining a suitable neighborhoof model $\mathcal{N}(x)$ [...] and a suitable weighting function $W(x,y)$." However, the relationship between $K(x,y)$, and $\mathcal{N}(x)$ and $W(x,y)$ is not made explicit.
- Figure 5 is hard to read and not properly explained. It might be easier to order the chemical elements by some measure of how rare/discriminative they are.

Minor:

- In the beginning of Sec. 2, the authors claim that "the practitioner has the freedom to design a corresponding graph shift operator". Be careful with such statements---by definition, the graph shift operator should respect the graph structure, i.e., it has to be such that $S_{ij}\neq0$ iff either $(i,j)$ is an edge or $i=j$. Also, it seems like in (2) the GSO is restricted to be the Laplacian?
- Please number important equations.
- Sec. 1 and parts of Sec. 2 are somewhat verbose and repetitive. Some of the text can be cut down to add more experiments.
- Many important experimental details are left to appendices. Consider moving them to the main body of the paper.
- There are a number of typos here and there. Please proofread.
- A limitation of the model in Def. 2 is that it only encompasses graphs which are symmetric. This should be mentioned in the paper.
summary_of_the_review: The problem addressed in the paper is important and the proposed solution is well-motivated. However, the paper fails to consider weighted graphs; does not rigorously compare the proposed graph model with other models for real-world graphs; and has unclear definitions and limited numerical experiments.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Geometric graphs have long been studied: a natural random model is that the nodes are sampled from some distribution over a metric space, along with some neighborhood radius alpha(u) for each node u---nodes u and v are then considered adjacent iff the distance d(u,v) between u and v in the metric space is at most max{alpha(u), alpha(v)). Much of the literature focuses on uniformly-random sampling and constant alpha. However, social networks with communities and hubs (such as superspreaders) easily necessitate non-uniform sampling and varying neighborhood radius. Under this model, a graph shift operator (GSO) can be viewed as a discretization of the continuous Laplacian. In order for this GSO to approximate the continuous Laplacian, the adjacency matrix needs to be normalized according to the unknown sampling density: the sampling density is estimated using a neural network and self-supervised learning. 

The non-uniform model considered here seems reasonable for real-world graphs. Experiments on synthetic datasets suggest that this approach can indeed well-approximate the true sampling density. Additional experiments show improvement in classification tasks, while learning the density values can be used to assign importance scores to nodes. Fundamentally, several experiments here show how the density estimation improves the performance of classical graph-convolutional networks.

The authors are asked to incorporate the reviewer comments on writing.

justification_for_why_not_higher_score: The paper is quite technical with a good need for the appropriate technical background, and is not suitable for an oral or spotlight. 
justification_for_why_not_lower_score: A refreshing direction for ICLR, and good steps put forward toward the rigorous understanding of non-uniform geometric graphs with unknown sample density.
Decision: Accept: poster