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
Venue: ICLR 2025 Poster (2025)
Keywords: Exact network embedding
latent distance model
logistic PCA
large scale network modeling
Primary area: learning on graphs and other geometries & topologies
TL;DR: The paper develops a metric procedure for exact large-scale network embedding providing substantially lower dimensional exact network embeddings than previously reported

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.

Published as a conference paper at ICLR 2025
How Low CAN YOU GO? SEARCHING FOR THE IN- TRINSIC DIMENSIONALITY OF COMPLEX NETWORKS USING METRIC NODE EMBEDDINGS
Nikolaos Nakis!* Niels Raunkjær Holm Andreas Lyhne Fiehn Morten Mørup²
I Yale University Technical University of Denmark
nicolaos. nakis n com, nielsrauna jaieisaanajaeeeggaaaa com, andrease a dk, mmor@dtu.dd
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 dimen- sions remain unclear. We presently prove that lower dimensional embeddings are possible when using Euclidean metric embeddings as opposed vector- baseed Lo- gistic 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, demonstrate that even large-scale networks can be effectively embedded in very oow-dimensional spaces, and provide exam- ples of scalable, exact reconstruction for graphs with up 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.
Code available at: http::/ghhha..comm//neeee//////t
INTRODUCTION
Graphs are used in plethora of settings to model various complex systems including social networks, the Internet, citation links between research publications, neural networks, protein- prottin interactions, food webs, and metabolic networks (Newman) 2003). to mention but few. From machine learning perspective graph representation learning (GRL) aiming to embed graph structure using low-dimensional vector spaces that provide compressed representations of network structure has in recent years garnered substantial attention (Hamilton et al. 2017a b). Some of the challenges in GRL include preserving structure from the discrete graph space in the learned embedding space. This means that the connectedness and similarity of nodes in the graph should carry over into the embedding space (Zhang et al.) 2020). Both local connectivity and global community structures are crucial to the characteristics of the system modeled by the graph. The concept of homophily (Mcpherson al., (200)) should thus be preserved, such that links between nodes are signified in their corresponding embeddings. Intuitively, the node representations should be close in proximity to each other in some measure relevant to the embedding space. Further, this notion of proximity should apply to next-step neighbors, next-next-step, and so on (Zhang et al. 2017). In the literature,
"Shared first authorship.

---

Published as a conference paper at ICLR 2025
various so-called shallow embedding methods, which essentially refer to mapping nodes one-to-one to embedding vectors have been proposed. These methods each aim to capture different parts of the graph structure, e.g. DeepWall Walk (Perozzi et al. 2014), LINE (Tang et al. 2015), node2vec (Grover & Leskovec 2016), GraRep (Cao et al. 2015). TADW (Serrano et al. 2007). and many more (Zhang aall||22200 Recently, it has been demonstrated that latent space network representation approaches
such as the latent distance model (Hoff et al., 2002) perform favorably using ultra-low dimensional
(i.e., D = 2 and D 3) embedding representations (Nakis al. 2022).
In Seshadhri et al. (2020) the goal of embedding graphs was formulated as capturing as much structure as possible from the graph in low-rank representation. They also pose the question of how well we can embed graphs. They conclude that graphs created from low-dimensional embeddings cannot have many triangles involving vertices of low-degree. This was later discussed in Chanpuriya et al. (2020) where it was demonstrated that with a relaxed version of the factorization model, finding exact low-rank embeddings for bounded degree graphs, i.e. graphs with at most degree kimaz= is indeed feasible. For this task, they used method for learning an embedding model based on logistic principal component analysis (LPCA). However, the work only provided rough estimates of the required embedding dimensions and the approach was restricted to the analysis of small networks (i.e., less than 20.000 nodes).
In this paper, investigate the limits required to achieve exact network embeddings. Specifically, propose an algorithm to efficiently search for an upper bound for the exact embedding dimension ( (D") of graphs. We further theoretically and empirically demonstrate that lower embedding dimensions can be achieved considering metric embeddings using the latent distance model (LDM) (Hoff et al. 2002). Importantly, through the properties of distance functions, metric spaces have natural and intuitive notions of proximity and by extension also node homophily and interconnectedness on both local and global scale. Inspired by the Hierachical Block Distance Model (HBDM), as introduced by Nakis et al. (2022), we exploit that the metric properties are especially useful for embedding very large graphs. As the reconstruction check itself becomes intractable for large sets of nodes, we further exploit how hierarchical representations of data with metric properties allow linearithmic runtime complexity. As such, we implement a KD-tree- bareed nearest neighbor reconstruction check method.
1.1 RELATED WORK
The interest in embedding networks using low dimensional representations has been substantially explored in the inexact reconstruction setting in which latent space modeling approaches including the latent eigenmodel and latent distance model have been explored (Hoff et al. 2002, Hofi 2007).
Recently, it has been observed that the latent distance model using ultra-low dimensional representa- tion provides strong generalization in graph representation learning tasks such node classification and link prediction (Nakis et al., 2022). The first attempt to quantify the intrinsic dimensionality of exact network reconstruction was considered in Chanpuriya al. (020)) based on a Logistic PCA (LPCA) model. For a network of N nodes, the LPCA model consists of two rank D E Z embedding matrices X, Y E NND. It assumes that the probability of link between node and j, expressed
in the adjacency matrix A E {0, N as aijj 1, is a o{XY )i.s) where (xx) = (1 (1+c -----=- is the iigmoid-function
Using the shifted adjacency matrix āzjj = 2az - 1, the log-likelihood can be compactly written as (ā,()( X Ik,)). )). Maximizing the likelihoods of links between all node
indices i and j is then equivalent to the following optimization task: (aus
N
min C(RLPCA Y)) min X
log
XYT] 133
(I)
Notably, this objective is closely related to identifying the sign-rank of matrix in which the product
āi.j XYT
> 0 Vi,j. It has been shown that the sign-rank is lower bounded by N/amaz (Ā)
where mmaz (A) denotes the largest singular value, i.c. spectral norm, of A Foorster 2002). This
bound has been refined in the context of learning theory and communication complexity in (Razborov
& Sherstov| 2010) whereas the existing known lower bounds for sign-rank have recently been surveyed
in (Hatami et al. 2022) and found to have limitations. To minimize [(RLPCA(X. (X, Y)) Chanpuriya ct al. (2020) initialize X and Y uniformly at random in [-1, 1] and use the SciPy implementation of the L-BFGS scheme with default parameters and maximum of 2000 iterations to optimize the
2

---

Published as a conference paper at ICLR 2025
D' dimensional Space
( X.9)
2 E
Network imput
go
R, rullal
YO
network reconstractio
Figure 1: Model Overview: The input network is embedded into low-dimensional space using matrices X and Y, defining an upper bound D on intrinsic dimensionality for seuucture-preserving reconstruction via the 8-radius. Connected nodes fall within each other's 3-radius, ensuring exact reconstruction.
expression. A check for full reconstruction made by comparing A to o ). In practice, XY is clipped to [0, 1] (i.e. applying the map clip R + [0, 1] defined as clip(z) max(0, min x))) and the Frobenius norm of the difference between the clipped reconstruction and A is calculated, ||elip(XY )- All When this measure evaluates 0, all predicted indices match the actual adjacency matrix and the found embedding thus allows for perfect reconstruction. They carried out this optimization process using coarse analysis of varying embedding dimensionalities in multiples of 16, and reported the dimensionality of the lowest exact embedding dimension found, e.g., they obtained factorizations of rank 16 on the well-known datasets Cora and Citeseer (Yang et al. 2016 and 32 on ca-HepPh (Leskovec et al. 2005) (see Table
In Gu et al. (2021) the exact embedding dimension was evaluated at the point in which the latent dimension was as large as the number of nodes arguing that this would be the upper bound of required dimensions and the optimal dimensionality defined as the lower dimensional representation concurring within a small margin of such exact embedding. In Bonato et al., (2012); [Bonato] (2017) the Logarithmic Dimension Hypothesis was proposed arguing for dimensionality of the embedding space of networks scaling as (log N) when considering the MGEO-P model (Bonato et al. 2012)
relying on embeddings based on the L -nom in a Blau space in which distance in latent position of nodes used to characterize their relations (McPherson) 2004) akin to the latent distance model (Hoff et al. 2002). Similarly, in [Braakoo et al. (202T it was proven that any directed acyclic graph (DAG) can be perfectly embedded using the probabilistic box embedding in which the probability of observing a link is given by the node-specific box overlap using a Ollog N) embedding dimension. It was further empirically observed that, for oww-dimesiionll embeddings, metric embedding approaches provided higher capacity embeddings compared to those relying on 202T Finally, in Chanpuriiya et al, (2023) LPCA was generalized to undirected graphs by use of difference formulation between two symmetric non-negan negative decompositions bridging the exact network embedding to community detection methodologies. In Chanpuriya et al. (2020) it was proven that for bounded degree (i.e., kimx) graphs exact embeddings can be achieved using = 24max + dimensions. This result was further refined in Chanpuriya et al. (2023) proving that for sparse networks the arboricity i.c., largest subgraph density-weighe by the number of nodes in the subgraph, bounds the embedding dimensions by 4[o2]2 + (Chanpuriya et al. 2023).
LPCA (Boratko
1.2 CONTRIBUTIONS
From these related works several important open questions remain. Specifically, Q1: Can metric model formulations provably provide lower dimensional representations than LPCA? We presently prove that metric embeddings can uniformly provide least as low dimensional embeddings as LPCA and highlight empirically that lower dimensional representations of networks exhibiting homophily can be achieved yet the same embedding dimension for networks exhibiting heterophily. Q2: How can network's exact low-dimensional embedding efficiently be quantified? Whereas there exist bounds on the embedding dimensions based on logarithmic scaling wrt. number of nodes (Boratko et al.) 2021) in the network, maximum degree (Chanpuriya et al.) 2020), and arboricity (Chanpuriya et al. 2023) is unclear how the lowest possible actual exact embedding dimension of a given network can be identified and Chanpuriya et al. (022)) provided only
3

---

Published as a conference paper at ICLR 2025
Adsoancy
embedinng
embeddinng
Adjoannc
Riszx embroding
Ambbddinngg
(a) Graph with homophilous community block struc-(b) Graph with heterophilous block structure. Green ture. Green lines indicate the La radius 3.
circles indicate the L2 radius B.
Figure 2: Example graphs with a community and an anticommunity structure, respectively, and their corresponding RLPCA and embedddnngg (Lines/Circles denote link thresholds for R22).
very coarse assessment of embedding dimensionality. We presently derive efficient logarithmic search strategy reliably identifying an upper bound on the intrinsic dimensionality of exact network embeddings. Q3: How can exact network embeddings be linearithmically O(N log N) quantified in large graphs? Existing network embedding assessments rely on the explicit evaluation of all links and non- non-links in the objective function optimized well as reconstruction check scaling for N nodes as ((N2) which is not feasible for large graphs. We presently, explore how metric embeddings enable efficient linearithmic neighborhood queries through the use of KD-trees to scalably assess perfect network reconstruction, and for the first time achieve such a reconstruction for networks with up to a million nodes. We further provide a linearithmic approximation of the full likelihood of metric embeddings providing efficient learning framework that we demonstrate can be refined using zero-margin hinge-loss optimization over the few approximation-indin induucd missclassified dyads to achieve exact embeddings of large-scale networks.
METHODS
In the following w, will denote the 7th row of the matrix W and || denotes the conventional Fuclidean norm. diag(b) will denote diagonal matrix with the elements of b along the diagonal and sbg the conventional sign function that is -1 b < and b > O. Let denote the adjacency matrix of a graph such that a,, if there is a link between node i and and a,j 0 otherwise. Finally let ūj = 2a,,; - the shifted adjacency matrix such that links and absence of links respectively given by 1 and -1
Q1: Both the local and global structure of a given graph carry information about the role of each specific node, and this contributes the complexity of embedding nodes. Modeling the optimization objective such that the resulting embedding space has the capacity to capture these connectivity- related attributes is crucial for encoding the information into oiw-dimensional node representations. We note two main components in the approach of Chhnnuriyaa et al. (2020), namely a parametrized reconstruction model and a loss measure between the true graph and its reconstruction. We can thus decompose the objective function in Equation into the reconstruction model and loss function respectively given by
(X
(2)
C(R) A Σ - log o (ān.)
(3)
1.j
where A == [ is the shifted adjacency matrix and R = [ra.s] is the reconstruction of the adjacency matrix, i.e., given by Eqquation 2 Considering L(.), in which the underlying modeling assumption is a Bernoulli likelihood, we can express the reconstruction at index i, as applying thresholding on the link probability, i.c. p(A.j 1) 2 3. or equivalently, م.ا 2
Analyzing RIPCA we see that it consists of an outer product between the two embedding matrices. The expressiveness of this reconstruction model thus lies in the pairwise inner products between each row vector in the two matrices. This method is known to have a lot of representational capacity akin to PCA, as the inner product provides a natural similarity measure between vectors, proportional the angles between them. Notably, the IPCA model formulated above can be considered a generalization to row and column specific embeddings of the latent eigenmodel proposed Hoff (2007). The
eigenmodel also includes bias term B, i.e. REIG Y, 8) e 3 XY As result, expressing
4

---

Published as a conference paper at ICLR 2025
this formulation of the latent eigenmodel by LPCA would require additional dimension, i... [81 [ Y) provided that 3 is non-zero and XY does not exactly span the constant matrix (a low-probability event), Consequently, the latent eigenmodel formulation can in theory reduce the dimensionality by one when compared to LPCA, i.e. Dī.PCA 1 S DĀIG S Di.PAA- Similarly, standard PCA requires an extra dimension if the data is not centered, i.e., when applying SVD directly to an uncentered data matrix. Importantly, we are only arguing for the dimensionality of
the solution and not that the solution must be exactly [81 [ Y) since the model reconstructions RLPCA, REIG- and RL, for LPCA, LEIG, and LDM non-unique and can all be modified by an orthogonal matrix Q such that X- XQ and Y Y YQ-+ provide identical reconstructions.
To further improve the expressiveness of the node embedding optimization objective, we consider the Euclidean latent distance model (LDM) (Hoff' et al. 2002 Hoff 2007) that provides metric specification of the reconstruction model according to
R1 (X, Y, 3) B |0, y 11112]
The LDM is a metric model, i.e., it yields an embedding vector space endowed with a distance function, which has useful properties we will elaborate on later. Importantly, in Theorem 2.1 we establish that the recconssstrrtt model can provide more favorable embedding dimensions using up to two embedding dimensions less than REPCA- A model overview is given in Figurr I Theorem 2.1. Let PC and Di,, denote the lowest exact embedding dimension for a graph embedding obtainable by optimization w.r.t. the -LLoc--rcoosttruction and reo-ssscostituiionn respectively. We then have the relationship
DLPCA-22 - 2--2. S DLPCA-
For proof of the above theorem see section A.2 in the supplementary material.
Importantly, metric models are especially efficient when modeling homophily in networks. i.e., a friend of a friend is also friend, which is naturally entailed by the triangular inequality using metric embeddings (Hoff et al. 2002). On the other hand, heterophilous networks (Chanpuriya et al.) 2023) also defined in terms of stochastic equivalence (Hoff) 2007) in which dissimilar nodes can be grouped is well accounted for by LPCA and can according to the above theorem at least with similar embedding dimensions be accounted for by the LDM. This is illustrated in Figure 2 where we compare the RLPCA and RL, considering a homophilous community structured and heterophilous network. We here observe that the R2 formulation can account for communities using an embedding dimension of D- = whereas R.PCA and RIE (not shown) requires D = 2 whereas all approaches can perfectly reconstruct the heterophilous network using D = 2. In Figure 3 we further highlight an example empirically verifying the bounds of Theorem 2.1 RLPCA requires three dimensions since more than three communities (as in Figure 2} need angles greater than 90 degrees in 2D for perfect reconstruction, which is not possible for the 10 communities in Figure 3 As result, an additional dimension needed to mimic the bias term included in RLEIG that can reconstruct the network using two dimensions exploiting that the bias term can threshold on angles less than 90 degrees for perfect reconstruction. Importantly, RI,, can trivially embed this network using only one dimension due to its metric properties.
Q2: To find an upper bound for the dow-dimensional exact embedding, we propose Algorithm which utilizes binary search (also called logarithmic search due to its logarithmic scaling) to search through an interval [bb, ub), 16 < ub E z of embedding space ranks with linearithmic time complexity (Knuth) 1998). We initialize the first iteration of embeddings a relatively high dimension Do ub. yielding the embedding matrices X, Y E R Nx Do When the LDM optimization yields embedding
matrices that perfectly reconstruct the graph, they concatenated Z = X Y E 12Nx Do As the LDM is translation invariant, we center the concatenated matrix as Z. Z 1uz, where uz is a vector containing the rowwise mean of Z. We then proceed to the next iteration of embeddings X', Y RN where the new rank D is chosen according to binary search. We initialize the new embeddings using the low-rank SVD with /) dimensions, given as Z, ~ UD V to project the previous embedding matrices onto the reduced space as X' = (X- - 14 Y (Y lu I VD E RNDD This is repeated by updating D in accordance with the binary search. In Figure of the supplementary material the benefits of truncated SVD initialization from higher embedding dimension as opposed to randomly initializing the new embedding at the given embedding dimension illustrated.
5

---

Published as a conference paper at ICLR 2025
Algorithm 1 Progressive search for solution with lowest
Q3: A metric space is defined set M endowed with a distance func- tion di M x M + R satisfying the metric properties for points I, y, E
EED
Require: ib, ub E 2 and ib < ub.
1: Initialize search interval as [tb, ub]
2: D +- Nome
Optimal found. Initial candidate EED. b For
M, i.e. (I) d(xr, x) = 0, (I) for I & y: d(x, y) > O, (III) d(z, y) = a(y,a)) and (IV) [the triangle inequal- ityl: d(r, 2) I d(z, y) + d(y, 2). Since the RL, reconstrruuti based on the Euclidean distance between the latent coordinates of the nodes, the set of nodes jointly embedded during training will therefore satisfy these metric properties.
3:
Do +- ub
4:
0o + R8xx x N.ooxxVXx44 RNV.oo,eee ,0,,,, ~ (0,,
C2.
80 Unif((,
5: Initialize Mx with Ou
> Mx: model w. reconstruction R. 6: +- Train until convergence or full reconstruction. otherwise stop search.
7: while 1b S ub do
8:
D thtuh
9:
[t, V. SVD(Conent[X, YJ) For C2. center embedding space after
concar.
10:
XX')") W.x.V.YY Initialize Mr with (X',
11:
0' + Train Mr until convergence or exact embodding
13:
exact embeclding achieved then
Optimizing the objective function
14:
D
15:
wh < D- @ 8'
with the R1,-recome reconstrtuuiinn
in
16:
Equation 4, we obtain a set of pa- rameters 0- (X', Y "8,). As-
17:
Stop search if D = ib.
18:
else
19:
Stop search if D ub.
suming 0' corresponds to a per-
20:
1b + D
feet reconstruction and noting that (ā [R1, (l))) > 0, we ob- serve that sign Rr, (O*))) (.,)) is +1
21:
end
22:
end while
for links and -1 for nonlinks, and thus B can be viewed as the radius of the hypersphere, cen- tered in at. which encapsulates all y for which the node index pair i.j constitute a link in the embedded graph. This corresponds to unit disk graph (Clark et al. 1990) defined across two embed- dings X, Y instead of a single embedding X. Examining the full reconstruction R = R1, (X, Y, B), we see that the æ; and y, node embeddings encode the source and target nodes, respectively, in the pairwise relations between nodes in the graph.
Checking for perfect reconstruction: To check if exact embedding has been found, we have to check if the reconstrueted adjacency matrix Å from the embeddings is the same as the original A. This is done by calculating the Frobenius error between them À A-AlIe/|Al le which poses issues with both runtime and memory usage when working with large graphs as it requires the dense adjacency matrix. For this reason, we propose a different approach to check if an exact embedding has been found exploring that the metric properties allow us to employ different similarity searching techniques (Zezula et al.) 2006; Yianilos 1993). In particular, we use the fixed-radius nearest neighbors search based on KD-trees which can be constructed in linearithmic time (Knuth) 1998 Friedman et al.. 1977, Bentley 1975). If we find all the nearest neighbors within the distance / in the embedding space, we can compare the found neighbors with the sparsely represented edge index lists. The worst case runtime for making the comparison would be O(N²), which happens in the case that everything in the graph is connected. As large graphs are mostly very sparse (Barabási & Pósfai 2016) with edges typically scaling tab-linearithmically the effective runtime will be much lower Nakis et al. 2022).
Scalable inference: When working with very large graphs a lot of memory will be required to store the full dense adjacency matrices, which is necessary for the reconstruction check using Frobenius error. The reconstruction check can be done with only the sparse representation of the proposed nearest neighbors full reconstruction check, but we still need address the issue of memory when calculating the loss and learning the representation. Two sampling methods that try to get around the issue of memory on very large graphs are random node sampling (Leskovec & Faloutsos 2006) and negative sampling/case-conto inference (Hamilton) 2020, Raftery et al. 2012).
Random Node (RN) sampling: In random node (RN) sampling (eeskovec & Faloutsos, 2006 a random set of nodes is sampled uniformly amongst the original N nodes. We let b denote the set of sampled node indices. the optimization objective in [Equation 3 can be reformulated as:
CRN CRY(R) - - Ejes log (ār,) This is equivalent to inducing subgraph from the nodes in and performing optimization step this subgraph as if was the original adjacency matrix. When using RN sampling where each node has an equal probability of being in the induced sample, might end up not preserving the structural properties of the graph. In Stumpf et al. (2005) they show that RN sampling does not retain the power law degree distribution for scale-free networks.

---

Published as a conference paper at ICLR 2025
Case-control (CC) sampling: Case control (Raftery al. 2012) in Mikolov et al. (2013); Goldberg et al. (2014) and also explained in Hamilton (2020) considers all
negative sampling formulated
nodes in the graph which we denote V. For each of the node indices i' all the links collected 7
and for & E z sample k (40) non-links uniformly, denoted by f((") In practice, we set k 5.
Defining I = Urev[l and to -Urev((')) ) the loss from Equation 3 can be redefined as:
(c)(R) = En Eneei (- log (rg)) + Er (-w3 log (r;))
Where 1 and lo corresponds to the sets of links and non-links in 1 and la, e.g. RLg. Wj is a node specific recalibration weight based on the amount of links and non-links.
N-14" P.l
Hierarchical Block Distance Model approximation and hinge loss active set optimization: Sam- pling methods visit only a very small fraction of the network during training which can especially become an issue for exact reconstruction of large-scale networks potentially creating problems with convergence of the model, as well as convergence speed. We therefore propose a Uwo-stage opti- mization approach based on the linearithmically scaling (O log( hierarchical block distance model (HB DM) originally proposed in the context of the Poisson likelihood (Nakis et al.) 2022). To achieve perfect reconstruction from an HBDM initialized solution we further exploit that the hinge loss reduces the loss function to only consider missclassified dyads but with same stationary points for exact network reconstruction as Equation 3) Specifically, we start by optimizing the HBDM based on the following augmentation of the method to the Bernoulli log- lieliiklihood:
Kr
CHBDM R))
Σ
β - ||x - -5512a
Σ
Σ CJECNz
log(1 + exp(B - |x: - -x5llz))
i
Ry ml
16.
K2
log(1 exp(( - 11 (2112))
1=1 k *
in which a hierarchical structure akin to a KD-tree is used to reduce the softplus contribution from the likelihood based approximating this part of the likelihood using an optimally learned hicrarchical structure based on the current learned embedding space thereby providing an accurate approximation of the full likelihood (Nakis et al. 2022). By optimizing the embedding space using HBDM only a relatively small number of dyads will remain misclassified as a result of the block approximation. The Hierarchical Block Distance Model (HBDM) uniquely characterizes the entire likelihood of large-scale graphs without sampling, achieving linearithmic space and time complexity through a hierarchical approximation of the total likelihood via metric clustering under Euclidean distance. The sums over terms 1, k. L, K refer to the K clusters and L layers used by HBDM, while YNXN = (JA.)) E 0, N represents the adjacency matrix of the graph, where yi.j = 1 if the pair (i,j) E F, otherwise it is 0 for all 1 < i, < N. Our model uses HBDM for initializing its latent space to provide a "hot" start.
In the second stage, we explore that for perfect reconstruction the stationary points of the Bernoulli likelihood and hinge loss are the same. This enables to use a zero-margin hinge loss optimization procedure that operates only over the active set of misclassified dyads (identified using the linearithmic reconstruction check) as opposed to all dyads in the logistic loss Equation to efficiently achieve perfect reconstruction:
Lm (R)) A Σ max max -ūrrtes)),
(8)
(i.))ES
where S is the active set. The active set S is then updated after each iteration via the KD-tree-basse based perfect reconstruction check until perfect reconstruction achieved. This HBDM initialization allows our model to misclassify very few pairs, denoted M, with M < N2 (observed empirically) for large graphs. The model then iterates only over these misclassified pairs, identified using KD-trees and the metric properties of the LDM. These pairs casily accounted for by the proposed analytical hinge loss optimization without computational constraints. Consequently, our model can achieve perfect reconstruction of large-scale graphs efficiently. To our knowledge, are the first to achieve
7

---

Published as a conference paper at ICLR 2025
Table I: Graphs used in the experiments along with some statistics. Comp. Arboricity denotes the max- imal arboricity obtained considering as subgraphs only the connected components of the graph as the actual arboricity requires infeasible exhaustive evaluation of all combinations of subsets of nodes thus providing lower bound on the arboricity.
Adacancy mails
Vean EED stasnatiee standad dedation
Figure 3: Visualization of the training statistics
Diracc
Natza
1y
Ang.
Nan Digine/
Tral
over 100 test runs the synthetic block graph seen in the left figure. The bar is the mean exact embedding dimension (EED) and the error bars correspond to the standard deviation of the mea- surements. An extended version of this figure can be seen in the supplementary A.6
Cle
2706
sedimsted
3.83
108/5.25
103
Reate
21.5
1911
100003
3.3
$1/713
10876
3.55
390
4611
27g
1971
4.50
17114.5
1980
saSocted
5.5
540/5.51
18804
3.9
9240
386
63153
26
CC
(a) 1=1
(b) 1=3
(c) 1=6
Erick
Cyech
Figure 4: Reordered udjacency matrices Figure 5: Comparison of case-control (CC), random node of the com-amazon network different sampling (RN), HBDM, and full likelihood inference on hierarchy levels learned by HBDM.
the Cora network.
this and provide such an efficient optimization procedure. The HBDM has linearithmic complexity. and we have empirically observed that after very few HBDM iterations, the number of misclassified pairs in the linearithmic scale. This results in an overall linearithmic complexity for our proposed method, making it highly scalable method, much more efficient than competing basclines.
3 RESULTS AND DISCUSSION
The methods introduced are tested on commonly used graph datasets: Cora, Citeseer, Pubmed (Yang et al.] 2016), ca-HepPh (Leskovec et al.] |005||Gehrke Gehrke et al. 2003), and ca-GrQe (Leskovec
al. (007) which are all different publication and citation networks, Facebook (Yang et a 2020)) which is subset of the Facebook network, wiki-Vote (Leskovec et al.] 2010b a) consisting of
voting on Wikipedia, the peer to peer network p2p-Gnutella04 (Leskovec et al. 2007 RRipeanu et al.,
2002), the Amazon network (Yang & Leskovec 2012). and Roadnet-PA PA which of Pennsyllvnnaa (Leskovec et al. (008). Many of the graphs are retrieved from the SNAP Datasets collection (Leskovec & Krevl 2014)) or Py PyTorch Geometric (Fey & Lenssen 2019). The datasets all preprocessed by ignoring edge weights, i.e., each entry in the adjacency graph is either 0 or 1. We list graph statistics for the datasets in Table as well as note the edge type, i.e., directed/uuddreetted. Optimization is performed using the ADAM optimizer (Kingma & Ba. 2014)) with the learning rate halved after k steps of no improvement. The initial learning rate and k vary by loss function and dataset, assessed qualitatively. Experiments run for up to 30,000 epochs, with rank intervals adjusted per dataset and prior results (Chanpuriya et al.) 2020). See the supplementary material for details.
road network
Searching for the optimal embedding dimension D": 5 searches have been carried out for each of the datasets and the minimum exact embedding dimension (D") has been reported along with the mean and standard deviation across the analyses of each network. These results are presented in Table aloog with the exact embedding dimensions reported by [Chanpuriya et al. (2020). Notably, in Chanpuriya et al. (2020) all networks were analyzed as undirected whereas we presently preserve the directed structure of the directed networks to highlight that the directionality of links can naturally be accounted for by the exact embedding. As result, the results can only be directly compared for the five undirected networks. In Chhnpuriyy et al. (2020) self-links were further included the modeling, but we presently do not model self-links ignoring these in the loss function. However,
8

---

Published as a conference paper at ICLR 2025
Table 2: Lowest exact embedding dimensions (D*) found for each Table 3: dataset across 5 searches along with the mean and standard deviations bedding dimensions (D") across the searches. We have marked directed networks with "*" as found for the two large-scale these will not be comparable with Chanpuriya et al. (2020) as they networks, com-amazon and converted all networks to undirected networks.
Lowest exact em-
roadNet-PA.
(hgt
(Eigassdd
D' do Margreafo
Chasparipctt..
PeddNet-P
Cora
Chesse
16.2 (445)
( (443
0445
(14 1853)
(01 045)
15
D2 (12)
13
16
(U52)
(8
16
(005 045)
10
(104 0.55)
8
(8 01
Wik-Naee
41
(42.33 1.00)
45
(658 043)
45
(464 1.34)
42
(42. 0445
Ca-laphh
(16mm))
19
(194-11355)
(1687 (.53)
Polernt
14
37
(474
17
(134
1n
(1
48
in the supplementary A.3 we include the modeling of self-links for direct comparison and find that this has little influence on the extracted embedding dimensionality D', From the results we see that using the proposed efficient search scheme, we identify the existence of solutions with substantially lower optimal embedding dimension D than previously reported and substantially lower than the bounds in terms of maximal degree
2kmaxx + 1 (Chanpuriya et al.) 2020) and arboricity 4[a] +1 1 (Chanpuriya et al. 2023) as presently evaluated only across each component of the graphs. Additionally, these results align with the theoretical result from Theorem 2.1 i.e., D' for the R1,, -ebbedddd is at least as good as the st.rc--embedding For Cora, the RLPCA solution has a 1r that is three dimensions larger than the R2 eemeeddingg This is likely due to the optimization being increasingly difficult for lower dimensions, causing the training process to get stuck in local minima rather than finding the expected (or approximate) optimal solutions, as we according to Theorem 2 can analytically extract an embedding of dimension DLPCA = Di2 + directly from the R, solution.
Instability of training procedure: As with many other machine learning algorithms, optimizing for the embeddings is dependent on initialization and hyperparameter settings, i.e., number of epochs, learning rate, etc. As result there are guarantees that the lowest possible D is identified. The optimization procedure is initialized with random embedding matrices, and this can lead to the model getting stuck in local minima. We showcase this behavior using synthetic data in Figuuee 3] We run the training procedure for each of the RL,-, REIG- and RLPCA modelss, where we start by testing if we can embed it in 1 dimension, moving up to dimensions if not possible, and so on, until convergence. We do this 100 times for each model. We observe that R.L.,, and R reliably extract their respective lowest embedding dimensions of D = and D = whereas the RLPCA-model is less reliable and only in few of the runs correctly identifies the D = 3 solution.
RLPcc-models,
Statistics of the reconstructed graph for embedding dimensions below the optimal D*: In Figure 6 we present graph statistics for the Cora network, to illustrate the impact of additional compression on the reconstructed graph as < D*. Notably, the statisties for D* represent the ground truth, reflecting perfect graph reconstruction. Figure iallstusss how the average degree of the reconstructed network evolves as the network is compressed into power-dimensionss spaces than the lowest exact dimension. Figure 6b) demonstrates that the average shortest path length of the reconstructed graph decreases with increasing compression, reflecting the network's 's structural simplification. The graph density, as provided Figure 6c is consistent with the observed increase in average degree, also rises as the network becomes more compressed. Finally, Figure 6d highlighss the increasing percentage of misclassified dyads as the model is further compressed, emphasizing its diminishing ability to accurately reconstruct the original network. (See also supplementary A.
embedding
Scalable exact network embeddings: In Figure 5| we compare case-control (CC) inference, random node (RN) sampling, and the HBDM inference to inference using the full likelihood considering the Cora network. We observe that the HBDM outperforms the alternative similar linearithmic O N log N) specified CC and RN sampling procedures providing scalable inference while achieving convergence relatively close to the convergence using the full likelihood. In Table 3 the achieved exact embedding dimension of the two large networks are given. This demonstrates that the two- phase procedure is scalable, but due to computational costs, we leave the search for tighter bound on their embedding dimension for future work. In Figure 4 we visualize the Amazon network organized according to the exact embedding using the corresponding HBDM induced hierarchical approximation structure of this embedding. The exact emhedding effectively captures the underlying
9

---

Published as a conference paper at ICLR 2025
Dia
LitenDmanion
(a) Average Degree
(b) Average Shortest Path
(c) Graph Density
(d) Miss-classified Dyads
Figure 6: Graph statistics for the reconstructed graph as the latent dimension decreases from the exact embedding dimension (D*) to (D= = 1) for Cora. ( (D*) ensures perfect reconstruction.
community structure with high within-block densities, while progressively revealing more detailed network structures as we traverse the hierarchy.
4 CONCLUSION, LIMITATIONS AND BROADER IMPACT
Our work explores the intrinsic dimensionality of graphs by posing the question of just how few dimensions are needed to represent a graph in way that allows for perfect reconstruction. Through metric models, we demonstrate both theoretically and empirically that we can construct more expressive embedding spaces than LPCA (Chanpuriya et al. 2020) and the same time exploit metric properties to linearithmically, ON log N), scale the inference of exact network embeddings to large graphs. Using our framework we achieve substantially lower embedding dimensions than previously reported. Surprisingly, we also observe from our large-scale network analysis that even large networks can be modeled exactly using very low-dimensional representations. We anticipate efficient exact network embeddings can have wide applications within network science from the visualization and extraction of communitics as presently highlighted to graph representation learning tasks including node classification and link prediction in which the LDM based on Euclidean distance has demonstrated strong performance using oiw-dimensional representations (Nakis et al.. 2022). Furthermore, we anticipate that exact embeddings efficent network motif discovery (Milo et al. 2002)] Vespignani 2003) to the characterization of network resilience and path properties based on the extracted topology induced by the exact network embedding. The approach can also be used to identify the interpolation threshold which has previously been used define comparatively suitable network representations (Gu al. (02I).
have important applications within
Our approach does not necessarily identify the lowest possible network embedding dimension but an upper bound D* and can be prone to issues of local minima, see also section 3 We presently considered metric embedding by the L2-norm as originally proposed for the latent distance model (Hoff al., (202)) which enabled us to establish a direct relationship to the embedding dimensions of LPCA. However, we note that other metric embedding approaches for instance as proposed relying on the Loe norm (Bonato et al. 2012: Bonato, 2017: Boratko et al., 202T) or hyperbolic
geometry (Krioukov et al. |009|] Boguñá al. 2010 Papadopoulos et al. 2012 Thomas et al. 2016 Muscoloni et al., [017]] Nickel & Kicla| 20176 2018) may enable lower dimensional representations
than the ones presently achieved. In the supplementary material A. we contrast the performance of the Euclidean embeddings to embeddings based on the Poincaré disk model, finding that the two embedding approaches perform very similar in terms of the estimated exact embedding dimensionality, Notably, our scalable inference procedure directly generalizes to other metric embedding approaches and future work should further investigate properties of other choices of geometry on the extracted dimensionality D
Whereas we expect exact embeddings to be useful for a variety of graph representation learning tasks care has to be taken in the context of link prediction as exact embeddings will imply learning explicitly to also characterize links set to zero as zero. As such, the approach may only provide meaningful predictions when treating links as missing from the loss function (using the hold-out method) if used for link fink-prrdittion (Miller et al., 2009) as opposed to the traditional approach setting links to zero and predicting that they were changed (Liben-Nowell & Kleinberg 2003). Low-dimensional exact embeddings can be directly used for network visualization and div-dimeniional representation as presently highlighted. This however can also be used for surveillance purposes in which the compact representations induced by the embeddings provide owwddimensional node-specific fingerprints which can be used for profiling and identification purposes.
10

---

Published as a conference paper at ICLR 2025
ETHICS STATEMENT
The authors declare no conflicts of interest.
REPRODUCIBILITY STATEMENT
All code for reproducing the experiments available at: https//github..oo/AAneeee F/ooo LowCan experimentation are publicly available.
Furthermore, all data sets used in the
REFERENCES
Albert-LászIó Barabási and Márton Pósfai. Network Science. Cambridge University Press, 2016.
ISBN 9781107076266. doi: 10.1007/978- 1-4614-6744-1.
Gary Becigneul and Octavian Eugen Ganea. Riemannian adaptive optimization methods. In Inter- national Conference on Learning Representations, 2019. URL https::/ net/
Forum?id=rleiquh
Jon Louis Bently. Multidimensional binary search trees used for associative searching, Communica- tions of the ACM, 18(9):509-517, 9 1975. ISSN 15577317. doi: 10. 10.1145/2310002361000,, URL
https: d1. acm wwt.///////oo/oooooooo 1tt.://1..1111111111000
Marián Boguñá, Fragkiskos Papadopoulos, and Dmitri Krioukov. Sustaining the internet with
hyperbolic mapping. Nature Communications, 1(1), September 2010. ISSN 2041-1723. doi:
00.10388ncomms1063 http: doi wwtp://ooooooo/o/../ooooo// 1038/ comms 063
Anthony Bonato. The geometry of social networks. Notes Can. Math. Soc, 48:12-13, 2017.
Anthony Bonato, Jeannette Janssen, and Pawel Pralat. Geometric protean graphs. Internet Mathemat- ics, 8(1-2)22-28, 2012.
Michael Boratko, Dongxu Zhang, Nicholas Monath, Luke Vilnis, Kenneth L Clarkson, and Andrew McCallum. Capacity and bias of learned geometric embeddings for directed graphs. Advances in Neural Information Processing Systems, 34: 14::16423-164333 2021.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. GraRep: Learning graph representations with global structural information. International Conference on Information and Knowledge Management, Proceedings,
10 2015. doi: 10.1145/2004416280655
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.
Sudhanshu Chanpuriya, Ryan Rossi, Anup B. Rao, Tung Mai, Nedim Lipka, Zhao Song, and Cameron Musco. Exact representation of sparse networks with symmetrie nonnegative em- beddings. 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 Asso- ciates, Inc., 2023. U.Litppss/ppppeeeiigg..rr..oooop ccppeper.rppppppeeeeeeeeee Sacaaper_fllesseee files/paper/ 2223/file/428car 222222111/22233r2222222222222212 Pape Coseerr-oooeeeencecce
Brent N Clark, Charles Colbourn, and David S Johnson. Unit disk graphs. Discrete mathematics, 86(1-3):165-177, 1990.
Matthias Fey and Jan Eric Lenssen. Fast Graph Representation Learning with PyTorch Geometric. 2019. URL htt.:httss//aaaee wwtp:/wwwwrgg/aabbaob 903. 3. 02428v222
Jürgen Forster. A linear lower bound on the unbounded error probabilistic communication complexity. Journal of Computer and System Sciences, 65(4)=612-625, 2002.
11

---

Published as a conference paper at ICLR 2025
Jerome H. Friedman, Jon Louis Bentley, and Raphael Ari Finkel. An Algorithm for Finding
Best Matches in Logarithmic Expected Time. ACM Transactions on Mathematical Software
3(3):09999 226. 9 1977. ISSN 15577295. doi: 10.1 10.11455555744435555. URL https:
f findit cvt. /tkk//oo/100/ 1tt.:/10.111113151 45/355744 355745
Johannes Gehrke, Paul Ginsparg, and Jon Kleinberg. Overview of the 2003 KDD Cup. SIGKDD Explor, 5(2):1191111 12 2003. ISSN 1931-0145. doi: 10. 10.114459809722.989999
Yoav Goldberg, Omer Levy, Tomas Mikolov, lly Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. word2vec Explained: deriving Mikolov et al.s negative-sampling word-embedding method. 2014. /ttps:tss///aiii wwwpeiivi.rgg//aa abs///b//////
Aditya Grover and Jure Leskovec. node2vec: Scalable Feature Learning for Networks. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 13- 17-Nugust-2016:855 864, 7 2016. ISSN 2154-817X. doi: 10. 10.114552939972229995544 URL
https://arxiv..or abs 00653v1
Weiwei Gu, Aditya Tandon, Yong- Yeol Ahn, and Filippo Radicchi. Principled approach to the selection of the embedding dimension of networks. Nature Communications, 12(1):3772, 2021.
William L. Hamilton. Graph Representation Learning. 2020. doi: 10.1007/978-3-001-015588
William I. Hamilton, Rex Ying, and Jure Leskovee. Inductive Representation Learning on Large Graphs, Advances in Neural Information Processing Systems 30 (NeurIPS), pp. 1024-1034, 2017a.
William L Hamilton, Rex Ying, and Jure Leskovec. Representation Learning on Graphs: Methods and Applications. 2017b.
Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, and Rosie Zhao Lower bound methods for sign-rank and their limitations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Schloss-Dagstuh--Leibbizz Zentrum für Informatik, 2022.
Peter D Hoff. Modeling homophily and stochastic equivalence in symmetric relational data. Advances in neural information processing systems, 20, 2007.
Peter D Hoff, Adrian E Raftery, and Mark S Handcock. Latent Space Approaches to Social Network Analysis. Journal of the American Statistical Association, ([14660):090-1000 12 2002. ISSN 0162-1459, doi: 10.1
8906.
Diederik P. Kingma and Jimmy Lei Ba. Adam: Method for Stochastic Optimization. 3rd International Conference on Learning Representations, ICLR 2015 Conference Track Proceedings, 12 2014.
6980v9
Donald E. Knuth. The Art of Computer Programming: Sorting and searching, volume 3. Addison Wesley Longman, second edition, 1998.
Max Kochurov, Rasul Karimov, and Serge Kozlukov. Geoopt: Riemannian optimization in pytorch, 2020.
Dmitri Krioukov, Fragkiskos Papadopoulos, Amin Vahdat, and Marián Boguñá. Curvature and temperature of complex networks. Physical Review E, 80(3), September 2009. ISSN 1550-2376. doi: 10.1 10.1103/phyareee33003313
URL /t_.atppp//x......cr/////ooo//
035101
Jure Leskovec and Christos Faloutsos. Sampling from Large Graphs. 2006.
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford Large Network Dataset Collection, 2014. URL htttlhtt::///smtt stan www.ddd.dddddaaaaaae
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations. 2005.
12

---

Published as a conference paper at ICLR 2025
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution. ACM Transactions Knowledge Discovery from Data (TKDD), 1(1), 3 2007. ISSN 15564681. doi: 10.1145/1217299
1217301. URL https: /tt.://dl.ccm acm. org/ /oii/0 1ww.//111119........ 1217331
Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, and Michael W. Mahoney. Community Structure in
Large Networks: Natural Cluster Sizes and the Absence Large Well-Defined Clusters. Internet 2.009991....000009999.
Mathematics, 6(1):29-123, 10 2008. ISSN 15427951. doi:
URL wtt.htttss:/eeee /ttp//rxxxv http://wwwvvvog..eaa///// abs/ www.///ss..........//.. 1355v1
Jure Leskovee, Daniel Huttenlocher, and Jon Kleinberg. Predicting positive and negative links in online social networks. Proceedings of the 19th International Conference on World Wide Web, WWW '0, pp. 641 650, 2010a. doi: 10. 00.1144/7729990177777555 URL https: /tte://cllaae
D
Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. Signed networks in social media. In- ternational Conference on Human Factors in Computing Systems, 2: 2:1361-1370, 2010b. doi: 10.1145/1153322.175555 1753533.
David Liben-Nowell and Jon Kleinberg. The link prediction problem for social networks. In Proceedings of the twelfth international conference on Information and knowledge management, pp. 556-559, 2003.
Miller McPherson. A blau space primer: prolegomenon to an ecology of affiliation. Industrial and Corporate Change, 13(1):263-280 2004.
Miller Mcpherson, Smith-Lovis Lynn, and James M Cook. Birds of a Feather: Homophily in Social Networks. Source: Annual Review of Sociology, 27:415 2001.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. Distributed Representa- tions of Words and Phrases and their Compositionality, Advances Neural Information Processing Systems, 10 2013. ISSN 10495258. htthttps:: /ttp://aaxivvvv org. abs 4446v1
Kurt Miller, Michael Jordan, and Thomas Griffiths. Nonparametric latent feature models for link prediction. Advances in neural information processing systems, 22, 2009.
R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. Network motifs: Simple building blocks of complex networks. Science, 298(5594):824-88 10 2002. ISSN 00368075, doi: 10.1
URL
www. htt.op////.aa.ccaaaacceeeore/o/a
22w.mnccee....... 5594. 824
Alessandro Muscoloni, Josephine Thomas, Sara Ciucci, Ginestra Bianconi, and Carlo Cannistraci. Machine learning meets complex networks via coalescent embedding in the hyperbolic space. Nature Communications, 8, 11 2017. doi: 10.1008/44166-0017-000
Nikolaos Nakis, Abdulkadir Celikkanat, Sune Lehmann, and Morten Morup. A Hierarchical Block Distance Model for Ultra Low-Dimensional Graph Representations. IEEE Transactions on Knowledge and Data Engineering, 36(4):399 4 2022. ISSN 15582191. doi: 10.1109)
T0333.003,3304344 URL URI.mtppss://esvvvoorr////. httpD///SAS.A.tlttpt////////////
2204. 258555555.2222
M EE Newman. The strueture and function of complex networks. SIAM Review, 45:167-256. 2003. ISSN 00361445. doi: 10. 00.113377700061145444444800 cond mat mat/33035161
Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical represen- tations. In Guyon, U. Von Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran
Associates, Inc., 2017a. URL http:/tst//ppcceeeiinnggeo//e/ee https//ppprroceennnnnnnirrr.... neurips wwtpwppp...ppppprrrr....
Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representations. Advances in neural information processing systems, 30, 20178 7b.
13

---

Published as a conference paper at ICLR 2025
Maximillian Nickel and Douwe Kicla. Learning continuous hierarchies in the lorentz model of hyperbolic geometry. In International conference on machine learning, pp. 3779-3788. PMLR, 2018.
Fragkiskos Papadopoulos, Constantinos Psomas, and Dmitri V. Krioukov. Network mapping by replaying hyperbolic growth. IEEE/ACM Transactions on Networking, 23:198-211, 2012 URL
https: semaneisssaacttccccsesss
52858447
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. DeepWalk: Online Learning of Social Represen- tations. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 701-710, -00, 2014. doi: 00001444/26233302222227777 ot/p./o...../....111///1///
h
orq/abs/140a 1403. w6526t552333
Adrian Raftery, Xiaoyue NIu, Peter Hoff, and Ka Yee Yeung. Fast inference for the latent space network model using case-control approximate likelihood. Journal of computational and graphical statistics, 21(4):901-19,, 2012.
Alexander Razborov and Alexander Sherstov. The sign-rank of ac "0. SIAM Journal on Computing, 1833)188381885 2010.
M. Ripeanu, Ian T Foster, and Adriana lamnitchi. Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design. arXiv.org, 2002.
M. Angeles Serrano, Dmitri Krioukov, and Marian Boguna. Self-similarity of complex net-
works and hidden metric spaces. Physical Review Letters, 100(7). 10 2007. doi: 10.1 103/ PhysRevLett. 100.07870111000 URL http: /aaxiiv org/ http:/711..0022ttppp/o
doi
100.0787000000000 C78701
C. Seshaddrri, Aneesh Sharma, Andrew Stolman, and Ashish Goel. The impossibility of low-rank representations for triangle-rich complex networks. Proceedings of the National Academy of Sci- ences of the United States of America, 117(111:55311-563,, 3 2020. ISSN 10916490, doi: 10.1073/ MMAS.19113300 URL www. pras. pttpp//....gg///////////..... /0t1://///////111/////a....o 19111301111111111111
Michael P.H. Stumpf, Carsten Wiuf, and Robert M. May. Subnets of scale-free networks
not scale-free: Sampling properties of networks. Proceedings of the National Academy of Sci- ences of the United States of America, 102(12):4221-45) 122244, 2005. ISSN 00278424. doi:
10. 10.1073/PNAS.00 0050 FFL
URL https: www
pnas. org doi aww.aass...... 1073 pnas 0501179102
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang. Jun Yan, and Qiaozhu Mei. LINE: Large-scale In- formation Network Embedding. WWW 2015 Proceedings of the 24th International Conference on World Wide Web. pp. 1067-1077, 2015. doi: 114114452736227724410993 http://wxxdddooooooooo http:////.......a..ooo...//////. 27727773362777779933
Ittp::t:
org/ 503. 0357
Josephine Thomas, Alessandro Muscoloni, Sara Ciucci, Ginestra Bianconi, and Carlo Cannistraci. Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space. 02 2016. doi: 10.48550/arXiv.1600 160.206622.22.
Alessandro Vespignani. Evolution thinks modular. Nature Genetics 2003 35:2, 3582):118-119, 10 2003. ISSN 1546-1718, doi: 10.1038/ng 1003-118. 1003-/11 URL www. naturettuuee.e.. com/ art Articles/ngl003-
Jaewon Yang and Jure Leskovec. Defining and Evaluating Network Communities based on Ground- truth. Knowledge and Information Systems, 1211)118 5 2012. ISSN 021931 16. doi:
10.10077510111--01--06553 URL httphhtpp:///aatttt wwwp///ggggaaaaaa......a.. aass///ss 6233v3
Renchi Yang, Jieming Shi, Xiaokui Xiao, Yin Yang, Sourav S. Bhowmick. and Juncheng Liu. PANE:
scalable and effective attributed network embedding. VLDB Journal, 1236 -2622226772222 9 2020. doi: 100110077.000788802--00009944444 //dx.66o..cg/11.110001
023 00790-4 00077700------00-------
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting Semi-Supervised Learning with Graph Embeddings. 33rd International Conference on Machine Learning, ICML 2016,
86-94, 3 2016. URL htt.///tts::/axii...rrr//////// http:///wwxvv.oorrras/ss///s/eee
08861v2 v
14

---

Published as a conference paper at ICLR 2025
P. Yianilos. Data structures and algorithms for nearest neighbor search in general metric spaces. ACM-SIAM Symposium on Discrete Algorithms, 1993.
Pavel Zezula, Giuseppe Amato, Vlastislav Dohnal, and Michal Batko. Similarity Search The Metric
Space Approach. 32, 2006. doi: 10. 10.100770-338--9155-2 URL http:://k//k springerpnnng
Com/ 10.10770000000 01177000377775--7
Daokun Zhang, Jie Yin, Xingquan Zhu, and Chengqi Zhang. Homophily, Structure, and Content
Augmented Network Representation Learning. pp. 609-618, 2017. doi: 10. 1011.
0072.
Daokun Zhang. Jie Yin, Xingquan Zhu, and Chenggi Zhang. Network Representation Learning: A Survey. JEEE Transactions on Big Data, 6(1):3-28, 3 2020. ISSN 23327790. doi: 10.1109/ TBDAATA.201.2255001...
15

---

Published as a conference paper at ICLR 2025
A APPENDIX
A.1 EXPERIMENTS WITH HYPERBOLIC DISTANCE MODEL
To verify that our method extends to other metric spaces than the Euclidean, run the EED search procedure using a hyperbolic distance model, based on the Poincaré ball model as seen in (Nickel Kiela 2017a)). as this model formulation is well-suited for gradient-based optimization. Concretely. we optimize using the Riemannian ADAM implementation from the geoopt library Kochurov et al. 2020 which is based on (Becigneul & Ganea 2019).
Table 4: Extended version of Figure 2
Lowest exact embedding dimensions (D*) found for each dataset across 5 searches along with the mean and standard deviations across the searches, including the Hyperbolic distance model. See Figure for graph statistics for each of the graphs. Results using hinge loss are obtained with margin of 0. "Crrrently only 3 searches have been performed for the Hyperbolic model on Pubmed.
Dastsset
D" (122
12" (UPCA)
13" (Figenmodel)
D" (1ag) Hiuge
D Chanpuriya
D' (Hyperholic) loss
Coru
( 0.45)
9
(3455
(..5)
(7 ar ()
16
a
Cheseer
(6.7 e 0.55)
9
(9.3 0.45)
9
(445
(7
16
(7.8 0.40)
Faechook
(20.67
(22.6
20
(2016
a
(103 0.45)
(104
Wiks Vone*
41
(42.33 a 1.97)
(458 0.45)
45
(464 1.34)
42
(42.2 c 0.45)
48
45
(46.0 1.55)
14
(14 ())
17
(17. 0.45)
17
(.710.7)
16
(16 m
32
17
(176 0.49)
co-HopPh
16
(16
(1988 0.84)
19
(19.4 0.55)
16
(16.67 0.52)
32
18
(1866 080)
Pubmed
(14
(17.3
(1744
16
0.42)*
A.2 PROOF OF THEOREM
In this section we provide the proof of Theorem 2.1
Theorem A.1. Let DLPCA and Di, denote the lowest possible exact embedding dimension for graph embedding obtained by optimization w.r.. the recostriconttttcttonn and LL2 recosssccntiiiiiinnn respectively. Then:
PLCA 2SD, S DEPCA
Proof. Recall that the probability of a link at index pair (i,j) in LPCA is given by p(Ai.) =
XY [X_]_ and recall that this implies that a link exists if and only if X >0
We note that the signs of X and Y are invariant to scaling by positive scalars, and define y == [7], and a = [al,- where Yi, Oj IR. We can now write:
sign
XY
sign (diag (7) XYT diag (a) sign
XY
From this expression, we can ensure row-wise normalization of the factorization matrices, i.e.
frow)
1. by setting = frww and a, = V
frow)
Considering the metric embeddings. the distance || 3 |1, is always non non-negatie non-negative and therefore / also has be non-negative as is used to separate links (i.e., B > | أزااا from non-links (i.c.. B < | أ 2l) Since both these terms are positive, we can express exact metric embedding equivalently in squared terms:
sigu (B | 55 siign [8
||
5)1(2) sign (32 (32-11+1
- --..ū
Setting 3 2 simplifies to sign (2 { and since multiplying by 2 does not change the sign, confirm that the metric embedding can represent the same information as the L.CA--emeddinng i.c.
sign (3 a. Ú)ا12) sign (ir.ū,]
16

---

Published as a conference paper at ICLR 2025
As write the metric model through an LPCA model augmented with two extra dimensions:
c l1
8² (1122 13 2x.y,
[-1
xx]
2y
this demonstrates that the LPCA-embedding needs at least two more dimensions to capture the same information the metric embedding.
A.3 EXPERIMENTS INCLUDING SELF-LINKS
The experiments in Chanpuriya et al. 2020 were based self-loops and for direct comparison we therefore here also include the corresponding experiments in which we set the diagonal of all networks one (i.e., include self-loops), 10 experiments were and the results reported in Table The hyperparameters for the experiment are reported in Table
Table Lowest exact embedding dimensions (D*) found for each dataset across 10 searches along with the mean and standard deviations across the searches. Self-loops considered. Note that in Chanpuriya et al. (2020) all their graphs were converted to undirected graphs and the rank comparison therefore not directly comparable for the directed networks. See Figure [orr graph statistics for each of the graphs.
Dataset
D (L2)
1 (LPCA)
D
Chanpuriya al.
2020
Cora
(6.1 0.3162)
(9 a 0)
Citeseer
(7 a 0)
9
(9.556
0.526)
16
Facebook
20
(20 a 0)
21
(22.3 ar 1.16)
ca-GrQe
(8 (8)
9
(10.2 0.7888)
16
Wiki-Vote
42
(42.8 a 0.4216)
42
(44.1 a 1.449)
48
22p-nnutella04
16
(1
17
(17.7 0.483)
32
ca-HepPh
17
(17.1 a 0.3162)
19
(18.7 0.483)
32
Pubmed
15
(15
16
(17.4 a 0.6992)
48
Table 6: Hyperparameters for exact embedding search. 10 experiments were carried out for both the LPCA and the La model.
Dataset
# epochs
Initial learning rate
LR-scheduler patience (k)
Search range
Cora
30, 000
1.0
500
[1, 50]
Citeseer
30, 000
1.0
500
[1 50
Facebook
30, 000
1.0
500
[1550]
ca-GrQe
30,000
1.0
500
[,550
Miki-Vote
30, 000
1.0
500
1,500
D2p-Cinueella04
20, 000
0.1
500
1,50
ca-HepPh
20, 000
1.0
500
1,50
Pubmed
20,000 000
1.0
500
[,55
A.4 HYPERPARAMETERS USED FOR RESULTS WITHOUT SELF-LINKS
The hyperparameters used for the experiments not considering self-links (Figure 2) are presented in Table 7
A.5 THE ADVANTAGE OF INITIALIZING THE EMBEDDING SPACE BY SVD
We used low-rank SVD of higher-rank embedding space initialize the search of the embedding space at the next rank in the Algorithm] In Figure 7 we demonstrate the difference between this "hot start" approach and randomly initialized embedding space i.e. "cold start".
17

---

Published as a conference paper at ICLR 2025
Table 7: Hyperparameters for exact embedding search not considering self-links (see results in
Figure 2). 5 experiments were carried out for both the LPCA and the L2 model.
Dataset
# epochs
Initial learning rate
LR-scheduler patience (k)
Search range
Cora
30, 000
1.0
200
[1, 64
Citeseer
30, 000
1.0
200
1, 64
Facebook
30, 000
1.0
200
1,96
ca-GrQc
30, 000
1.0
200
[1,80]
Wiki-Vote
30, 000
1.0
200
1,50
P2p-Gnutella04
30, 000
0.1
200
1,80
ca-HepPh
30,000 000
1.0
200
1,
Pubmed
30, 300
1.0
200
[1.80]
Rank 40
Rank 20
Rank
Hot Start
SWB Stant
Cold Start
Cole Start
Cold Start
Froberiaa Srror
Frobertus Error
0.-
Pribentu
02-
02
0.0
0.-
52
1000
150
200
100
1060
1566
2010
2000
1060 3506
5203
16666
35666
20060
25000 20000
Epoch
Epoch
Epoch
Rank 15
Rank
13
Rank 14
1.0
Coldd Start
Cold Start
Cold Start
Frubenka Erior
Frotonks Enfr
Fobertis
0.
0.4
02.
02
30
2020
1000
5000
8200
20000
32000
5202
10000
25000 20000 25000
50000
5007 20000
15000
20000
25000
20000
Epoch
Epoch
Epoch
Figure 7: SVD and random initialization (cold start) for some search steps for the dataset PubMed. The search was initialized at rank 80 (randomly initialized) and then low-rank SVD-initialization was used for the proceeding search steps. Additionally, we have initialized training with random initialization for each search step. The legend marked with if an exact embedding was achieved.
18

---

Published as a conference paper at ICLR 2025
A.6 VISUALIZATION OF TRAINING STATISTICS ON SYNTHETIC GRAPHS
3kloda
20
10
30
Lobke
Figure 8: Visualization of the training statistics over 100 test runs on the synthetic graphs seen in the left figure. The bar the mean exact embedding dimension (EED) and the error bars correspond to the standard deviation of the measurements. All runs are performed using hinge loss.
Mean EED on a synthetic graph with 120 nodes and different number of blocks
Model
17.
(LatemEiggn)
Min (typarbblkc)
12
LatontE gon
12.5
Hyperbar bopebblllc
Mean EED
10.0
0.0
10
30
50
90
Number of blocks in synthelik graph
Figure 9: EED for different models and different block sizes synthetic networks with different amounts of blocks similar to those in Figure 8
A.7 THE HIERARCHICAL BLOCK DISTANCE MODEL
Given Bernoulli log- likelihoeood over latent distance model, where YNXN (yi,)) 0, NNN represents the adjacency matrix of the network, where Yi. = 1 if the pair (2,j) E E, otherwise is for all 1 < i s N. The total network log- likelihood is defined as:
log P(YIA)= = Σ (ummi - log(1 - exp (nw)))
Σ
Thi
Σ ig
log(1 + exp (n:)),
(10)
i
where My are the log-odds, Mly || y 1121 Scaling the optimization of such expression not feasible as the second term requires the computation of all node pairs scaling as O(N2). In
19

---

Published as a conference paper at ICLR 2025
contrast, the first term scale with the number of edges, i... O log N) Nakis et al. (0022) making its computation scalable for large networks.
To scale the LDM to large-scale networks, the HBDM procedure approximates Σ ووية log(1 exp(11s)) by enforcing hierarchical block structure similar to stochastic block models. Specifically, HBDM employs a hierarchical divisive clustering procedure. is worth noting that the original work by Nakis al. [2022] focused on a Poisson likelihood and undirected networks. In this study, we extend their approach to a Bernoulli likelihood, adapting it for directed networks.
We define the total representation matrix [ YJ, which combines the source and target node embeddings through concatenation. The matrix Z is then structured into a hierarchy using a tree-based divisive clustering approach, resulting cluster dendrogram.
The tree's 's root represents a single cluster encompassing the entire set of the concatenated latent variable embeddings. Z. each level of the tree, the cluster recursively partitioned until the leaf nodes contain more than the desired number of nodes, Neaf. The number of leaf nodes, Meat is chosen based on the HBDMs' linearithmic complexity upper bound and thus set to Neat = log N. This results in approximately K / log((N) total clusters. At each tree level, the tree-nodes represent clusters corresponding to that level's height. When partitioning a non-leaf node, the split is performed only the set of data points assigned the parent tree-node (cluster). For each tree level, the pairwise distances between data points different tree-nodes are used to define the distances between the corresponding cluster centroids. These distances then used to compute the likelihood contribution of the blocks. Binary splits are applied iteratively to the non-leaf tree-nodes, progressing down the tree. When all tree nodes are treated becomes leaves (contain maximum log N points), the HBDM analytically computes the pairwise distances within each cluster to determine the likelihood contribution of the corresponding analytical blocks. This computation incurs linearithmic cost of O(K leaf) = ON log N). Moreover, this approach preserves the homophily and transitivity properties the model, as explicitly shown in the paper.
The total HBDM expression for our approach is defined as:
K2 Σ
CHBDM(I) - Σ
33-11a -||| - - -
B
Σ
log(1 + exp(3 ||x - -Yalle))
iデj
k
i.ECCE
y =1
L K. K2
ΣΣΣ
log(1 exp(B - 11
p 12 (121)))
(11)
I=1
k=
where E L...., L denotes the (-th level of the dendrogram, k is the cluster index at each tree level, (!) and pi represents the corresponding centroid.
A.7.1 THE EUCLIDEAN CLUSTERING OF HBDM, RESPECTING METRIC PROPERTIES
Finally, in order for the clustering preserve the metric properties of the Euclidean space, the HBDM defines a Euclidean version K-means clustering. The divisive clustering procedure relies on the following Euclidean norm objective:
J(r p)
Tsk Iz px12
(12)
where A denotes the cluster index, zi is the i-th data point, rik is the cluster responsibility or assignment, and μą is the cluster centroid. Since the loss function for K-means with the Euclidean norm does not provide closed-form updates, the proposed method introduces the following auxiliary
loss function:
Equation 12 as:
N
K
||z
J J+
Σ
Tik
+
(13)
2
i=1
k=l
20

---

Published as a conference paper at ICLR 2025
where Φ the auxiliary variables, while in Nakis al. (2022) they show how this auxiliary functions accounts for optimizing Equation 12
A.8 HBDM SEARCH
The active set used in the hinge loss optimization is reduced significantly by using the solution obtained from the HBDM framework as described in Nakis et al. (2022) and adapted to binary graphs. This reduced active set is then optimized by the hinge loss with margin of A KDTree is used to query neighbors within the radius of B and this is used to update the active set and thus determine which nodes are reconstructed correctly. From Figure 10 we observe empirically that the HBDM has reduced the active set enough to optimize using the hinge loss and we further observe that the next search step hot started with the low-rank SVD the previous full reconstruction also starts at a sufficiently small active set size.
A.9 COMPUTE RESOURCES USED
The experiments on the smaller graphs, i.c., all the graphs except com-amazon and roadNetPA can all be run on consumer-grade hardware. More specifically used 2023 Macbook Pro with M3 Pro chip. For the larger datasets we used high- teth-rrrformece compute cluster equipped with an Nvidia A100 GPU and multiple Intel Xeon Gold CPUs with either 16 24 cores.
A.10 ADDITIONAL STATISTICS OF THE RECONSTRUCTED GRAPH FOR EMBEDDING DIMENSIONS BELOW THE OPTIMAL D":
We provide pairwise comparisons between the optimal dimension (D*) and lower dimensions for (i) Degree Distribution, (ii) Clustering Coefficient Distribution, and (iii) Shortest Path Length Distribution. Figure Figure 1T shows results for the Cora dataset while Figure[Figure 12 the results for the Facebook dataset, highlighting increasing deviations in distributions as dimensions move further below (D*).
A.11 PERFECTLY RECONSTRUCTING RANDOM NETWORKS:
We investigate whether our proposed approach can perfectly reconstruct random networks with a ground-truth latent dimension, for both Euclidean and Hyperbolic geometries. To generate random graphs, we sample D-dimensional random vectors uniformly within a ball of radius R (with R = 1 for the Poincaré disk model) and assign scalar bias ensure realistic network sparsity. Links then generated via Bernoulli sampling. Our findings indicate that stochastic network generation prevents the recovery of exact embedding dimensions (EED), even in high-dimensional settings. However, by making network generation deterministic - linking nodes when dij S 3 - perfect reconstruction achieved. We set the number of nodes for networks as N 1000, and D 3, The results are summarized in Table 8
Table 8: Comparison between EED found by the hyperbolic model and the Euclidean model for synthetic networks generated according to 3- and 8-dimensional hyperbolic and Euclidean geometric structures, respectively.
Synthetic Dataset
D* (Hyperbolic Model)
D* (Euclidean Model)
Hyperbolic
3D
5
Hyperbolic
8D
9
9
Euclidean
3D
3
Buclidean
BD
8
8
21

---

Published as a conference paper at ICLR 2025
Searth steo-1
Search 2
Search step
Search step
Search step 5
10.09 free
"ingg Los Fhoae
0.6-
0.6-
0.--
0.6-
0.6
Miglerfed
2.4-
0.1-
130
2.0 Eaach
300
0.0
110
200
300
200
403
500
5300
10000
1000
2002
Epech
Qpoth
Couch
Spach
(a) Cora
Search stop
Search
Search
Search
Search
0.20
(Sant 15)
(Barit 11)
0.22
[Hank 8)
0.20
(Hurkk 5)
0.23
[Rank 7)
IBON Phess
Maclenfed Synde
0.25
0.15
0.15
0.15
0.10-
0.25
0.55
0.25
0.05
293
5000
(b) Citeseer
Search
Scarch [Blnk 211
[Rank
(Sani 241
Ufteric 14)
(Hark 20)
IB:2M Fhass
idage Lien Waite
1.0
1.0
1.4
65
4.5
0.5
200
400
503
230
508
150
2000
2000
5000
10000
5208
50700
(c) Facebook
Search shen
Search crep. (Saikk
sten
Search etep
[Sank
[Rwnk:
HEOW Pheie
0.2
tawhh
Fyack
Search
Search
(Pank 15)
(P2 122)
[Rank
(Panc
0.2
02
3.0
1090
1053
2000
40.0 Epoch
4b.0
2053 Opcch
Zooth
(d) Pubmed
Search step
Search stop 2 |Rank 21)
Search stop
Search stap 4
Search step 5
(Rank 30)
(Rank 161
|Rane 18)
(Rank: 19)
0.1
Macberfed Cysds
0-3-
0-3
0-2
0.2
02
0.1
3.8
0.0
Tpoch
Eooch
Qpach
Cooch
Spach
(c) D2p-Gnutella04
Figure 10: Percentage of misclassified dyads for different steps of the search algorithm using HBDM. The run is marked by if exact embedding was achieved.
22

---

Published as a conference paper at ICLR 2025
028
77
D7
D
D-
D
923
5
2.12
2.13
0.00
0.00
0.00
720
122
179
0.2
25
10.0
125
15.0
Deggres
Cllsteing Covel cart
Path Langh
(a) Dogree Distribution Comparison
(b) Clustering Coefficient Distribu- (c) Shortest Path Length Compari- tion Comparison D"
D 7 VS D
6
vs D 6
D
7 vs D =6 6
D-
D
0.2
0.13
0.00
0.0
Degins
Clustring Conficari
Path Leigh
(d) Degree Distribution Comparison
Clustering Coefficient Distribu- (f) Shortest Path Length Compari- tion Comparison D
D
VS
5
vs 5
son D
7 D 5
=
D²=7
D7 D
D-4
D=4
Precko Nodaay
0.19
Dorik
0:0
0.5
28
100
150
200
0.
0.2
244
3.6
0.8
1.0
0.0
00
25
50
150
135
150
17.5
206
Clirwiing
gg) Degree Distribution Comparison (h) Clustering Coefficient Distribu- (i) Shortest Path Length Compari-
D 7 vs D 4
tion Comparison D = 7 vs D = 4 son D 7 vs D =
0.20
D
7
D
033
of
4.5--
Dunddy
000
03
8:00
Dagree
Clazaring Confioint
Puth Lengh
i Degree Distribution Comparison
(k) Clustering Coefficient Distribu- (l) Shortest Path Length Compari- tion Comparison D 7 D D) 7 D =3 3
D
-
D
D
Node
2.52
085
200
203
1.0 00
58
75
10.8
150
Clusteingg Confecett
(m) Degree Distribution Compari- (n) Clustering Coefficient Distribu- (0) Shortest Path Length Compari-
son D = 7 vs D = 2
tion Comparison 7 vs 2 son D* = 7 vs D =
Figure 11: Additional pairwise graph statistics comparison for the reconstructed graph the latent dimension decreases from the exact embedding dimension (D*) for the Cora network. (D*) ensures perfect reconstruction.
23

---

Published as a conference paper at ICLR 2025
D 20
2.00
17
17 20
D
D-15 15
D-
3.023
2.8
8.155
12
1.0
075
3.09
0.2
0:5
000
0.88
0.0
200
420
250
0.5
3.5
Degrae PM
Cludkring Conficantt
Pwth Langh
(a) Dogree Distribution Comparison
(b) Clustering Coeff. Distribution
(c) Shortest Path Length Compari- D 20 vs D = 15
D 20 D 15
Comparison D 20 vs D = 15
2.0
Dr
175
Poedoon Noxkes
0.003
1.0
0.655
1:00
075
8.65
0.0
02
92h
800
Dog om
Glusering Comfidde11
Pat Lengh
(d) Degree Distribution Comparison
(e) Clustering Caeff. Distribution
(f) Shortest Path Length Compari-
D
20% VS
Comparison D 20 vs D 10
son D
20 vs
10
0.230
20
= D
D 20
0125
D-8
D
Paggsn Nodea
0.00
1.50
0.6
0015
122
8
0070
0.06
6:5
0.00
200
400
000
600
1000
000
0.
0.2
3.4
0.5
6.
10
00
2
g Degree Distribution Comparison (h) Clustoring Coeff. Distribution
(i) Shortest Path Length Compari-
20 VS D = 8
Comparison D 20 vs D = 8
son D 20 vs D = 8
0.030
01 20
2.00
20
- 20
0.225
Fraden Nodes
1.00
0010
0//
0.58
02
0.00
0.
601
03
Degiee
Ckalarin Confidiatt
Pach Langh
i Degree Distribution Comparison (k) Clustering Coeff. Distribution
(l) Shortest Path Length Compari-
D
20 D 5
Comparison D" 20 D
D" 20 vs
0.00
= 20 D-2
20
D-2
D-2
175
8.44
155
8.8
035
301
033
835
0.6
88
Glastring
Langh
(m) Degree Distribution Compari-
(n) Clustering Coeff. Distribution Comparison D = 20 vs D = 2
(o) Shortest Path Length Compari- son D* 20 vs
son D' 20 vs
Figure 12: Additional pairwise graph statistics comparison for the reconstructed graph as the latent dimension decreases from the exact embedding dimension (D*) for the Facebook network. (D*) ensures perfect reconstruction.
24


Reviews:
[{"review_id": "1N4UizddOT", "reviewer": "Reviewer_odRC", "summary": "The paper is discussing a relevant problem in network geometry, which is about searching for the intrinsic dimensionality of complex networks.\nThe 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\nbe used to provide linearithmic scaling.", "questions": "Can the authors offer results and tests using for benchmarks artificial networks generated in a geometric space of a given dimension?\nFor instance, see this article in case of hyperbolic geometry:\nGeneralised popularity-similarity optimisation model for growing hyperbolic networks beyond two dimensions\nB Kovács, SG Balogh, G Palla\nScientific Reports 12 (1), 968\n\nCan the author expand their method also to network with hyperbolic geometry?\nCan 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? \n\nHow this study related to this other study that is missing in their related works part:\nDetecting the ultra low dimensionality of real networks\nP Almagro, M Boguñá, MÁ Serrano\nNature communications 13 (1), 6096\n\nWhen the Authors mention in the limitation section the to embedding using hyperbolic geometry, they refer to (Nickel & Kiela, 2017; 2018). \n\nIt is not clear to me why they do not refer to:\n+ the first model-based algorithms proposed in:\n1. Curvature and temperature of complex networks\nD Krioukov, F Papadopoulos, A Vahdat, M Boguná\nPhysical Review E, 2009\n2. Sustaining the internet with hyperbolic mapping\nM Boguná, F Papadopoulos, D Krioukov\nNature communications 1 (1), 62, 2010\n3. Network mapping by replaying hyperbolic growth\nF Papadopoulos, C Psomas, D Krioukov\nIEEE/ACM Transactions on Networking 23 (1), 198-211, 2015\n \n+ the first model-free and topological machine learning algorithm proposed in:\n1. Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space\nJosephine Maria Thomas, Alessandro Muscoloni, Sara Ciucci, Ginestra Bianconi, Carlo Vittorio Cannistraci\nhttps://arxiv.org/abs/1602.06522, 2016\n2. Machine learning meets complex networks via coalescent embedding in the hyperbolic space\nA Muscoloni, JM Thomas, S Ciucci, G Bianconi, CV Cannistraci\nNature Communications 8 (1), 1, 2017", "limitations": "", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "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. \nThe study does not use as benchmark any complex network model that generates networks in a geometric space of a given dimensionality. \nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YDBlJo6yqV", "reviewer": "Reviewer_GFnZ", "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.\n\na) Theoretical Contribution:\n- They proved that metric embeddings can provide lower dimensional representations compared to Logistic PCA.\n- They showed that metric embeddings can achieve dimensions up to two dimensions less than LPCA while maintaining perfect reconstruction.\n\nb) Methodological Contributions:\n- They developed an efficient search algorithm to find the minimal embedding dimension with O(N log N) complexity.\n- For large networks, they Proposed a scalable O(N log N) approach using KD-trees.\n- They Introduced a two-phase optimization approach combining the Hierarchical Block Distance Model (HBDM) with hinge-loss optimization\n\nc) Empirical Contributions:\n- Using their method, they found lower embedding dimensions than previously reported.\n- They showed successful embedding of large-scale networks (up to 1 million nodes).\n- They provided extensive experiments on various real-world networks\n\nOverall, 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.", "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?\n\nMinor comments and suggestions.\n- line 045: \"...preserving structure from* the discrete graph...\" -> \"preserving structure *of the discrete graph\"\n- line 068: 20.000 nodes -> 20,000 nodes. Use a comma instead of period\n- line 076: \"...we exploit* that the metric properties...\". Use of a better verb is recommended.\n- line 078: \"...exploit* how hierarchical...\". Use of a better verb is recommended.\n- line 140: \"wrt.\" -> \"w.r.t.\" Use periods.\n- 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$.\n- line 300: \"Everything in the graph is connected\"? Do you meant a \"fully connected graph\"?\n- line 303: \"Scalable inference:\" Are you missing a colon?\n- 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].\n- 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].", "limitations": "", "rating": 8, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "Strengths:\n- Strong theoretical foundation with proven bounds\n- Novel scalable approach for large networks\n- Comprehensive empirical validation\n- Clear practical implications for network analysis\n- Reproducible research with code provided\n- Well-written and structured presentation\n\nStrengths with experimentations:\n- Diverse dataset selection (10 different networks of varying sizes and types)\n- Multiple experimental validations (5 searches per dataset)\n- Comprehensive comparisons with baseline methods\n- Clear ablation studies showing the benefits of different components\n- Scalability demonstrated on large networks\n- Reproducibility ensured with detailed hyperparameter settings", "weaknesses": "Weaknesses:\n- The approach may not find the absolute lowest possible embedding dimension\n- Optimization can be sensitive to initialization and hyperparameters\n- Limited exploration of alternative metric spaces (e.g., hyperbolic geometry)\n- The method might not be directly applicable for link prediction tasks\n- Some privacy concerns regarding potential surveillance applications\n- 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. \n\nSome additional experiments could strengthen the paper:\n- Comparison with other metric embedding approaches (e.g., hyperbolic embeddings)\n- More extensive analysis of the impact of network properties on embedding dimension. Features such as connectivity, number of connected components, etc.\n- More detailed runtime analysis for different network sizes", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AjMfDz5gOd", "reviewer": "Reviewer_qGwB", "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.\n\n[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.\n\n[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.),\nAdvances in Neural Information Processing Systems, volume 36, pp. 21023–21038. Curran Associates, Inc., 2023", "questions": "See the weakness above.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "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.\n\n2. 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].\n\n2. 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?\n\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GJneMudRrW", "reviewer": "Reviewer_N48b", "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.", "questions": "There are a few things that remained unclear to me, specifically\n1. 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?\n2. 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.\n3. 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.\n4. Does the proposed Theorem 2.1 always hold in practice? Are there some assumptions that are made?\n5. 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)?\n6. L. 357 states that a \"relatively small number of dyads will remain misclassified\". Can you say more precisely what \"relatively small\" means?\n7. 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?\n8. 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?\n9. 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?\n\nMinor points\n- I believe there should be a comma instead of a period in l. 68 (20.000 nodes --> 20,000 nodes)\n- I believe it should be \"coarse\" instead of \"course\" in l. 142/143\n- I think it should be \"obtainable\" instead of \"obtain able\" in Theorem 2.1.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "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.\n2. Their proposed $O(n \\log n)$ time algorithm for computing exact embeddings in is well-described and easy enough to follow.\n3. 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.\n2. 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.\n3. Some claims appear to be left somewhat vague (see my questions below).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7EMDMPTonh", "reviewer": "Reviewer_bMSk", "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.", "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?\n- 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.\n- 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?\n\n### Typos\n- Line 136 \" yet the same embedding dimension for networks exhibiting heterophily.\"\n- Line 153 \"missclassified\"\n- Line 902 \"miss-classify\"\n- In equation 2, $\\mathcal{R}$ is a matrix, but in equation 4, it is a scalar.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "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.\n- The discussion of motivation and presentation of results is generally clear.\n- 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.\n- 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.\n- 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.\n- 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.\n---\nRazborov, Alexander A., and Alexander A. Sherstov. \"The sign-rank of AC ^0.\" SIAM Journal on Computing 39.5 (2010): 1833-1855.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)