Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this work, the authors investigate the Local Intrinsic Dimensionality (LID), especially the feature (FLID), structure LID (SLID), and Representation LID (RLID) of a graph. Through experimental analysis, the authors demonstrate that the FLID and SLID are well correlated with the graph complexity, and real-world graphs have a much lower intrinsic dimensionality. In addition, authors also interpret the over-smoothing problem associated with GNN models from the perspective of the SLID's convergence.
main_review: Strength
1. This work investigates the LID of graphs, and interpreted the GNN models from the perspective of FLID, SLID, and RLID, which is interesting.
2. Authors demonstrate that FLID and SLID are good indicators of graph complexity according to node features and graph structures, respectively.
3. Experiments indicate that GNN models learn to map the raw features with high extrinsic dimensionality to low intrinsic dimensionality, and further identify the over-smoothing problem of GNNs as the collapse of the graph structure to a complete graph with $SLID=0.5$.


Weakness
The major concern is how to understand and utilize these LID metrics in graph learning. Although the investigation of FLID, SLID, and RLID is interesting, it seems that the authors do not provide any intuitive explanation of these LIDs in the paper, and these LIDs are only used to understand some operations and problems associated with GNNs. It would be great if the authors could give some more intuitive explanation of these LID metrics, and discuss how these LIDs can be leveraged in graph learning. For example, from the reviewer's perspective, one potential usage of these LIDs is to design graph adversarial attacks and more robust GNN models, as we can downgrade the performance of GNNs by perturbing graph structure or node features to change these LIDs. In addition, authors have utilized SLID to interpret the over-smoothing problem associated with GNNs, but they have not discussed how to leverage SLID to design a GNN model which overcomes the over-smoothing issue. I wonder if the authors could provide a more detailed discussion about issues related to graph learning, like the above two mentioned examples?
summary_of_the_review: In this work, the authors introduce the concept of FLID, SLID, and RLID, and investigate these metrics in graph learning. The investigation is interesting, and these LIDs are helpful in determining the graph complexity, understanding the issues associated with GNN models (e.g., over-smoothing problem). However, it seems that these LIDs are not intuitive to be explained, and this paper also does not discuss how to leverage these LIDs in graph learning. Therefore, it would be great if the authors could provide a more detailed discussion about the reviewer's two concerns mentioned above.
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: This paper study the local intrinsic dimension of graphs in terms of feature, structure, and representation.
main_review: Strengths:  
1. This is an interesting topic and can help us understand many graph learning techniques.   
2. The organization and presentation are good and easy to follow.  


Weakness:   
1. The SLID takes the distribution function as $G(y)=a^y$. However, the graphs in the real world are scale-free and directly taking the average degree for distribution definition is not reasonable.  
2. Graph representation learning is a fusion of both feature information and structure information. However, I didn’t see the relationship between these three LIDs in terms of definition and experimental analysis.  
3. The conclusion of Section 4.2 is wrong. The authors state that the SLID estimated on synthetic graphs goes up as the latent space dimensionality d increase in all settings. However, in some settings, the SLID first decrease and then increase as shown in Figure 4 (b). These experimental results directly disproved the conclusion.   
4. The first conclusion in Section 5 is incorrect. The authors take the number of nodes and edges as the extrinsic dimensionality. As for image data, we take the number of pixels as the extrinsic dimensionality rather than the number of image samples. Similarly, this definition is correct for graph-level tasks, but for node-level tasks, extrinsic dimensions should be the dimension of features and local structures.
5. The second conclusion in Section 5 is not rigorous. The authors stated that the datasets within the same category have similar S/FLIDs and those across categories exhibit a large discrepancy. However, the FLID of Cornell is more similar to Cora rather than Winsconsin. 
6. The conclusion in Section 6.1 is wrong. First, the numbers of dataset classes are not equal, and the numbers of samples belonging to different classes are not equal. It is not reasonable to compare the difficulty of classification directly according to numerical values under different task difficulties. For example, CiteSeer is with 6 classes and 75.08% accuracy while PubMed is with 3 classes and 87.6% accuracy. Apparently, CiteSeer is easier to learn, but the authors give the opposite conclusion. Second, the authors force predefined conclusions to interpret results, regardless of the real numerical relationships of the results. For example, the difference in the accuracy of Cora and PubMed is around 2%, so is the difference between Cornell and Wisconsin. But the authors state that PubMed < Cora and Cornell$\approx$Wisconsin.   
7. The authors state that graphs with lower SLIDs are easier to learn in the abstract but I didn’t find the support by theory or empirical results.  
8. According to the results, the SLID had no relationship with accuracy, that is to say, the structure complexity had no relationship with graph representation learning, which was inconsistent with our experience of graph representation learning.  


Minors:  
1. In the first line of Page 5: “a node-set E”->“an edge-set E”
summary_of_the_review: Interesting research problem, but some definitions are unreasonable and most of the claims are incorrect.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper characterizes the intrinsic dimensionality of node features, graph structures, and representations learned by GNNs via the so-called Local Intrinsic Dimensionality (LID) measure, intending that it can benefit the community in understanding the difficulty of an underlying graph learning task. In addition, estimators for Feature LID (FLID), Structure LID (SLID), and Representation LID (RLID) were introduced. This work showed that real-world graphs have much lower intrinsic dimensionality when compared to their extrinsic dimensionality. 

main_review: Strengths
=======

The paper applies different LID measures such as FLID, SLID, and RLID in order to quantify the difficulty/complexity in learning a particular graph.  This feat is important for understanding the limitations of graph neural networks.

Weaknesses
==========

I fail to realize the innovation and practical impact of the LID measures in real-world scenarios.  In particular, I would like to have seen a proposed graph learning technique that leverages the discoveries and the importance of the analysis carried out using the LID measures discussed. Such contribution would substantially increase the relevance of this paper.  At least some preliminaries results on that direction would hugely increase the innovation of the paper.
summary_of_the_review: I recommend the paper as marginally below the acceptance threshold due to the weaknesses mentioned above.
review_title: null

Meta-review: The paper investigates the interesting problem of the local intrinsic dimension (LID) of graphs, and interpreted the GNN learning from Feature LID (FLID), Structure LID (SLID), and Representation LID (RLID). The concepts are novel but the paper needs better insights on how LID can improve graph learning and stronger empirical evidence to support their claims.
Decision: Reject