How Low Can You Go? Searching for the Intrinsic Dimensionality of Complex Networks using Metric Node Embeddings

Authors: Nikolaos Nakis, Niels Raunkjær Holm, Andreas Lyhne Fiehn, Morten Mørup
Primary area: learning on graphs and other geometries & topologies
Keywords: Exact network embedding, latent distance model, logistic PCA, large scale network modeling

Abstract:
Low-dimensional embeddings are essential for machine learning tasks involving graphs, such as node classification, link prediction, community detection, network visualization, and network compression. Although recent studies have identified exact low-dimensional embeddings, the limits of the required embedding dimensions remain unclear. We presently prove that lower dimensional embeddings are possible when using Euclidean metric embeddings as opposed to vector-based Logistic PCA (LPCA) embeddings. In particular, we provide an efficient logarithmic search procedure for identifying the exact embedding dimension and demonstrate how metric embeddings enable inference of the exact embedding dimensions of large-scale networks by exploiting that the metric properties can be used to provide linearithmic scaling. Empirically, we show that our approach extracts substantially lower dimensional representations of networks than previously reported for small-sized networks. For the first time, we demonstrate that even large-scale networks can be effectively embedded in very low-dimensional spaces, and provide examples of scalable, exact reconstruction for graphs with up to a million nodes. Our approach highlights that the intrinsic dimensionality of networks is substantially lower than previously reported and provides a computationally efficient assessment of the exact embedding dimension also of large-scale networks. The surprisingly low dimensional representations achieved demonstrate that networks in general can be losslessly represented using very low dimensional feature spaces, which can be used to guide existing network analysis tasks from community detection and node classification to structure revealing exact network visualizations.

Decision: accept (poster)
Reviewer scores: 6, 8, 5, 6, 6

Reviews and discussion:
<thread>
creation date:
1729993839510

thread_type:
official_review

<thread_object>
creator: reviewer_bmsk

<content>
summary:
This paper advances prior work in the field about finding exact representations of networks using low-dimensional vector embeddings in a latent space. It does so by proposing a few algorithms that scale the work to larger networks. First, the paper uses a distance-based model for network representation, which is slightly different from the bilinear model used in other works. The results show that the the former is at least as effective as the latter, and it can also accommodate scalable checking that the representation is exact. Second, the paper finds tighter upper bounds for the dimensionality needed for exact representation than prior work, proposing binary search and warm starts to speed up the procedure. Third, the paper explores using sampling and hierarchical models to facilitate scaling up the search for exact embeddings to large networks, and it claims to find exact representations for a 1M-node network.

strengths:
- The paper advances understanding of the capacity of dense vector representations of a network's nodes. Such representations are ubiquitous across graph machine learning, but this area is still not well understood, so advancements can be significant.
- The discussion of motivation and presentation of results is generally clear.
- The core advancement of using a distance-based model, KD-trees, and sampling and/or hierarchical models to scale up exact embedding search to large graphs seems logical and yields results on significantly larger graphs than prior work.
- Finding tighter upper bounds for exact embedding dimensionality using binary search and warm starts is a smaller but still nice advancement.

weaknesses:
- The adaptation of HBDM is the best instance of this paper's main advancement, which is scaling exact representation search to larger networks. Given this, HBDM is insufficiently described in the main paper. In particular, it is the reviewer's opinion that the discussion of Equation 6 should be significantly expanded with full description of the notation and more intuition about the terms of the loss.
- On the other hand, there is a lot of description of relatively minor differences, e.g., the single dimension of difference between LPCA and the latent eigenmodel, which could be moved to the appendix.
- There could be some more discussion of older but still relevant theory work, such as work on sign rank of a matrix (e.g., Razborov and Sherstov, 2010), since this line of work is essentially about the sign ranks of networks' adjacency matrices.
---
Razborov, Alexander A., and Alexander A. Sherstov. "The sign-rank of AC ^0." SIAM Journal on Computing 39.5 (2010): 1833-1855.

questions:
- Related to the main weakness listed above, how would you intuitively describe Equation 6 and the adaptation of HBDM to exact representation search here?
- Is the KD-tree-based check that the representation is exact used only for the distance-based model (L2), or can is it also applied to LPCA and Eigenmodel? It is not clear to me how it can be applied to the latter two.
- It seems that CC sampling would be overall stronger than RN sampling, but based on Figure 3 it seems to take longer to produce an exact representation. Why is this the case?

### Typos
- Line 136 " yet the same embedding dimension for networks exhibiting heterophily."
- Line 153 "missclassified"
- Line 902 "miss-classify"
- In equation 2, $\mathcal{R}$ is a matrix, but in equation 4, it is a scalar.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730388540819

thread_type:
official_review

<thread_object>
creator: reviewer_n48b

<content>
summary:
The authors investigate how many embedding dimensions are required to losslessly embed complex networks in metric spaces. As a motivation for their work, they mention the importance of low-dimensional embeddings for tasks "such as node classification, link prediction, community detection, network visualization, and network compression". Specifically, they ask whether lower-dimensional embeddings than previously achieved based on the so-called Logistic PCA model are feasible. They develop an efficient algorithm to compute the exact embedding dimension of large complex networks which is based on the hierarchical block distance model. Using kd-trees to efficiently search for nodes' neighbours during optimisation, they avoid $O(n^2)$ complexity, enabling computing lossless embeddings in time $O(n \log n)$. Finally, they show empirically that their approach requires fewer dimensions to embed networks than previous approaches.

strengths:
1. The authors consider a relevant research question and improve upon the state-of-the-art, achieving network embeddings in lower-dimensional metric spaces than previous works.
2. Their proposed $O(n \log n)$ time algorithm for computing exact embeddings in is well-described and easy enough to follow.
3. The empirical evaluation supports their theoretical claims.

weaknesses:
1. The authors highlight their work's relevance by referring to several downstream tasks which are expected to benefit from lower-dimensional embeddings. However, they merely show that they can achieve lower-dimensional embeddings than previous work, but do not show how or whether the performance on downstream tasks is affected.
2. The last paragraph of the abstract mentions that their work can be used to "guide existing network analysis tasks", however, they do not pick up this point later in the paper to explain _how_ this can be done.
3. Some claims appear to be left somewhat vague (see my questions below).

questions:
There are a few things that remained unclear to me, specifically
1. The present analysis is limited to unweighted networks and only considers the presence or absence of links. Would it be possible to extend the proposed approach to weighted networks or is there a fundamental limitation that prevents this?
2. At the points when Fig. 1 is mentioned in the text (l.237), it was not clear to me how to interpret what is shown in the figure. I assume that the key is what is mentioned in l.285-286, is that right? I would recommend providing an explanation of how to read the figure earlier on.
3. I am also wondering whether you have explored how your method behaves on "difficult" networks with less clear structure than those shown in Fig. 1? I am not sure what exactly "difficult structure" is, but would assume that, for example, Erdős–Rényi random graphs may be difficult to embed since they do not exhibit significant structure.
4. Does the proposed Theorem 2.1 always hold in practice? Are there some assumptions that are made?
5. Why is Algorithm 1 efficient? This is not really clear to me. And what does "efficient" mean here (i.e., what is the algorithm's time complexity)?
6. L. 357 states that a "relatively small number of dyads will remain misclassified". Can you say more precisely what "relatively small" means?
7. L. 368-269 states that "The active set $\mathcal{S}$ is then updated [...] until perfect reconstruction is achieved". I assume here that Eqs. (6) and (7) are optimised in turn, is that correct? And if so, how do we know that the procedure will terminate?
8. I was a bit surprised to see that the Roadnet-PA network requires 16 dimensions for lossless embedding. Given that road networks are essentially embedded in 2D in the real world, should it not be possible to embed it in fewer than 16 dimensions?
9. The network shown in Fig. 2 seems like it should be embeddable in 1D, just as the network shown in Fig. 1a. However, it seems somewhat difficult for the optimisation to find this solution, given that the mean EED is higher than 1. What happens as one increases the number of blocks in the networks? Does the mean EED grow?

Minor points
- I believe there should be a comma instead of a period in l. 68 (20.000 nodes --> 20,000 nodes)
- I believe it should be "coarse" instead of "course" in l. 142/143
- I think it should be "obtainable" instead of "obtain able" in Theorem 2.1.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730457102962

thread_type:
official_review

<thread_object>
creator: reviewer_qgwb

<content>
summary:
Built on a series of works by Chanpuriya et al. (see [1] and [2]]), this paper uses metric embedding to study the low intrinsic dimension of network embedding. First of all, the authors provide an improved upper bound of existing intrinsic dimensions and an efficient searching algorithm for finding such an upper bound. Experiments were conducted on real-world graphs to demonstrate by considering metric embeddings using the latent distance model. These findings could help to have a better understanding of network embeddings and potentially can be applicable to large-scale graphs.

[1] Sudhanshu Chanpuriya, Cameron Musco, Konstantinos Sotiropoulos, and Charalampos E. Tsourakakis. Node Embeddings and Exact Low-Rank Representations of Complex Networks. Neural Information Processing Systems, 2020.

[2] Sudhanshu Chanpuriya, Ryan Rossi, Anup B. Rao, Tung Mai, Nedim Lipka, Zhao Song, and Cameron Musco. Exact representation of sparse networks with symmetric nonnegative embeddings. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.),
Advances in Neural Information Processing Systems, volume 36, pp. 21023–21038. Curran Associates, Inc., 2023

strengths:
1. This paper studies interesting theoretical problems concerning the intrinsic dimension of network embeddings. The authors proposes to use a new loss function to quantify the upper bound of intrinis dimension.

2. An efficient searching algorithm is proposed to quantify the provided upper bound. Experimental results also show the effectiveness of the proposed method.

weaknesses:
1. I am not quite sure how significant such a new upper bound is compared with the existing work presented in Theorem 2.1. It seems that the authors use a new objective defined in Equ. (4) to obtain the upper bound $D_{L2}$ which could be $D_{LPCA}$, $D_{LPCA} -1 $, or $D_{LPCA}-2$. How significant is this result? Please make a short discussion on how significant difference between current work and [1,2].

2. It is a concern that the efficient logarithmic search method presented is not effectively justified.  The authors claimed that they derived an efficient logarithmic search strategy that reliably identified an upper bound on the intrinsic dimensionality of exact network embeddings. I did not see the runtime complexity analysis and justification of correctness. How can we make sure the returned embeddings are exactly correct? How can the lower bound and upper bound parameters lb, ub be set?

3. How practically useful of these quantified embeddings compared with DeepWalk and node2vec? Although this is not a very serious concern as the paper mainly focuses on the theoretical perspective of network embedding. How could usefulness be compared with popular node embedding algorithms such as DeepWalk, node2vec, and LINE etc. From my understanding, these real-world embeddings perform better in terms of node classification when the dimensionality increases. It would be helpful if authors can elaborate on this.

questions:
See the weakness above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730599805492

thread_type:
official_review

<thread_object>
creator: reviewer_gfnz

<content>
summary:
This paper explores the intrinsic dimensionality of complex networks using metric node embeddings and argues that metric embeddings are superior to vector-based inner product embeddings in this domain. The premise of this paper is dimension reduction, but it is not mentioned at what cost it is acheived. This paper has theoretical, methodological, and empirical contributions as the following.

a) Theoretical Contribution:
- They proved that metric embeddings can provide lower dimensional representations compared to Logistic PCA.
- They showed that metric embeddings can achieve dimensions up to two dimensions less than LPCA while maintaining perfect reconstruction.

b) Methodological Contributions:
- They developed an efficient search algorithm to find the minimal embedding dimension with O(N log N) complexity.
- For large networks, they Proposed a scalable O(N log N) approach using KD-trees.
- They Introduced a two-phase optimization approach combining the Hierarchical Block Distance Model (HBDM) with hinge-loss optimization

c) Empirical Contributions:
- Using their method, they found lower embedding dimensions than previously reported.
- They showed successful embedding of large-scale networks (up to 1 million nodes).
- They provided extensive experiments on various real-world networks

Overall, this has strong theoretical and practical contributions to network embedding research. The experiments are generally sufficient, although it lacks some runtime reports. The paper's main strengths lie in its theoretical foundations and scalable approach for large networks, while its limitations are mainly related to optimization challenges and the scope of experimental validation.

strengths:
Strengths:
- Strong theoretical foundation with proven bounds
- Novel scalable approach for large networks
- Comprehensive empirical validation
- Clear practical implications for network analysis
- Reproducible research with code provided
- Well-written and structured presentation

Strengths with experimentations:
- Diverse dataset selection (10 different networks of varying sizes and types)
- Multiple experimental validations (5 searches per dataset)
- Comprehensive comparisons with baseline methods
- Clear ablation studies showing the benefits of different components
- Scalability demonstrated on large networks
- Reproducibility ensured with detailed hyperparameter settings

weaknesses:
Weaknesses:
- The approach may not find the absolute lowest possible embedding dimension
- Optimization can be sensitive to initialization and hyperparameters
- Limited exploration of alternative metric spaces (e.g., hyperbolic geometry)
- The method might not be directly applicable for link prediction tasks
- Some privacy concerns regarding potential surveillance applications
- While suggested method has low computational complexity, the proposed implementation for preserving the A matrix in the memory is not efficient. In this work they resort to sampling methods for maintaining large A matrices in the memory. 

Some additional experiments could strengthen the paper:
- Comparison with other metric embedding approaches (e.g., hyperbolic embeddings)
- More extensive analysis of the impact of network properties on embedding dimension. Features such as connectivity, number of connected components, etc.
- More detailed runtime analysis for different network sizes

questions:
The optimization is sensitive to initialization and hyperparameters. For a given set of hyperparameters, what is the probability of converging to (1) the global minimum answer, (2) a minimum answer, and (3) not converging? Using a Monte Carlo scheme, what would be average value for D for a given set of hyperparams?

Minor comments and suggestions.
- line 045: "...preserving structure from* the discrete graph..." -> "preserving structure *of the discrete graph"
- line 068: 20.000 nodes -> 20,000 nodes. Use a comma instead of period
- line 076: "...we exploit* that the metric properties...". Use of a better verb is recommended.
- line 078: "...exploit* how hierarchical...". Use of a better verb is recommended.
- line 140: "wrt." -> "w.r.t." Use periods.
- line 263: $\mathbb{R}^{2N×D_0}$ -> $\mathbb{R}^{N×2D_0}$. Since you are defining $\mathbf{Z}=[\mathbf{X} \mathbf{Y}]^T$, it seems the dimensions should be $N×2D_0$  rather than $2N×D_0$.
- line 300: "Everything in the graph is connected"? Do you meant a "fully connected graph"?
- line 303: "Scalable inference:" Are you missing a colon?
- line 446: In Figure 3, not all Y-axis ranges are equal. Is there a reason? The Y-axis range for "Rank 16" is [0, 2.0], while for the others is [0, 1.0].
- line 865: In Figure 5, not all Y-axis ranges are equal. In "Rank 10" the range is [0.3, 1.0], in "Rank 13" the range is [0.2, 1.0], while in the rest it is [0.0, 1.0].
</content>
</thread_object>

</thread>
<thread>
creation date:
1731256787833

thread_type:
official_review

<thread_object>
creator: reviewer_odrc

<content>
summary:
The paper is discussing a relevant problem in network geometry, which is about searching for the intrinsic dimensionality of complex networks.
The Authors provide an efficient logarithmic search procedure for identifying the exact embedding dimension. Specifically, they propose an algorithm to efficiently search for an upper bound for the exact embedding dimension (D∗) of graphs. The Authors claim to demonstrate how metric embeddings enable inference of the exact embedding dimensions of large-scale networks by exploiting that the metric properties can
be used to provide linearithmic scaling.

strengths:
The idea proposed is original and the question of the study is of significance.

weaknesses:
The study does not refer to certain relevant literature in complex networks. 
The study does not use as benchmark any complex network model that generates networks in a geometric space of a given dimensionality. 
The results are of difficult to interpret is the study does not provide tests on artificial network models generated in a geometric space with a certain dimensionality.

questions:
Can the authors offer results and tests using for benchmarks artificial networks generated in a geometric space of a given dimension?
For instance, see this article in case of hyperbolic geometry:
Generalised popularity-similarity optimisation model for growing hyperbolic networks beyond two dimensions
B Kovács, SG Balogh, G Palla
Scientific Reports 12 (1), 968

Can the author expand their method also to network with hyperbolic geometry?
Can the authors comments why and how their method applies to many real networks that have intrinsic hyperbolic geometry considering that their method seems based on an Euclidean embedding? 

How this study related to this other study that is missing in their related works part:
Detecting the ultra low dimensionality of real networks
P Almagro, M Boguñá, MÁ Serrano
Nature communications 13 (1), 6096

When the Authors mention in the limitation section the to embedding using hyperbolic geometry, they refer to (Nickel & Kiela, 2017; 2018). 

It is not clear to me why they do not refer to:
+ the first model-based algorithms proposed in:
1. Curvature and temperature of complex networks
D Krioukov, F Papadopoulos, A Vahdat, M Boguná
Physical Review E, 2009
2. Sustaining the internet with hyperbolic mapping
M Boguná, F Papadopoulos, D Krioukov
Nature communications 1 (1), 62, 2010
3. Network mapping by replaying hyperbolic growth
F Papadopoulos, C Psomas, D Krioukov
IEEE/ACM Transactions on Networking 23 (1), 198-211, 2015
 
+ the first model-free and topological machine learning algorithm proposed in:
1. Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space
Josephine Maria Thomas, Alessandro Muscoloni, Sara Ciucci, Ginestra Bianconi, Carlo Vittorio Cannistraci
https://arxiv.org/abs/1602.06522, 2016
2. Machine learning meets complex networks via coalescent embedding in the hyperbolic space
A Muscoloni, JM Thomas, S Ciucci, G Bianconi, CV Cannistraci
Nature Communications 8 (1), 1, 2017
</content>
</thread_object>

</thread>
<thread>
creation date:
1732285989636

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Updated paper and rebuttal response by authors

comment:
We thank the reviewers for their time and thoughtful feedback, which have greatly helped us improve the clarity and experimental setup of our manuscript. In the revised version, all changes and updates are highlighted in blue for easy reference. We are happy to address any further questions or provide additional clarifications.
</content>
</thread_object>

</thread>


Metareview:
metareview:
Most reviewers were weakly positive on this paper and thus I am recommending acceptance. The paper gives a more scalable approach for finding exact low-dimensional embeddings of large networks, focusing on Euclidean embeddings. Using this approach they show that some real-world networks have surprisingly low exact embedding dimensions, extending and strengthening previous findings of Chanpuriya et al. A major weakness is that it's not clear what the upshot is -- the finding certainly seems interesting but what should we do with it? What implications does this have on graph ML methods or practice? In any case, reviewers found the paper sufficiently interesting as is to warrant acceptance.

I will note that some of the theoretical results in the paper seem weak/misrepresented. In particular, the claim in the abstract/intro that the paper affirmatively answers "Can metric model formulations provably provide lower dimensional representations that LPCA?" is confusing. It is clear that inner product and Euclidean norm embeddings are roughly the same due to the fact that ||x-y||^2 = ||x||^2 + ||y||^2 + 2<x,y>. In fact, this is confirmed by the paper's own theory: in Theorem 2.1 the authors prove that the two embedding approaches differ by at most an additive factor 2 in the embedding dimension (due to the rank-2 difference between a Gram matrix and a squared distance matrix. This is not a significant factor, and I would argue that it has essentially no relevance to our theoretical understanding of exact embeddability of real-world graphs. It does not deserve mention the abstract in my opinion or being highlighted as one of the main contributions of the paper.

The main takeaway from the paper should be that exact Euclidean embeddings are easier to find in practice on large networks, not that they have better representation capacity. This should be clarified.