Complete-Tree Space Favors Data-Efficient Link Prediction
Authors: Chi Gao
Lukai Li
Yancheng Zhou
Shangqi Guo
Venue: ICML 2025 poster (2025)
Keywords: Complete-Tree Space
Network Embedding
Data-Efficient Learning
Link Prediction
Primary area: general_machine_learning->representation_learning
TL;DR: We develop the complete-tree space that favors data-efficient link prediction on real-world networks due to its intrinsic hierarchical permutation symmetries.

Abstract: Link prediction is a fundamental problem for network-structured data. However, the prevalent research paradigm tends to assume abundant observed links, overlooking more challenging scenarios with a scarcity of observed links, which results in insufficient sample sizes. In real-world networks, hierarchical modularity, characterized by structured and nested connections, remains robust even with sparsely observed links. To address the challenge of limited link samples, we propose leveraging hierarchical modularity as a prior structure. We introduce complete-tree (CT) space, a discrete metric space with latent complete-tree structures, to formalize hierarchical modularity with an emphasis on its hierarchical permutation symmetry. Utilizing the group theory to quantize and compare permutation symmetries of different spaces, we prove that the CT space provides a significantly lower bound on sample complexity than the commonly used Euclidean space. We develop leaf matching, a data-efficient network embedding that maps nodes onto the CT space and conducts discrete optimization by reducing it to decentralized search. Experiments verify the data efficiency of CT space over other spaces. Moreover, leaf matching outperforms the state-of-the-art graph transformer in data-scarce scenarios while exhibiting excellent scalability. The code is available at: **https://github.com/KevinGao7/LeafMatching**.

Complete- Tree Space Favors Data-Efficient Link Prediction
Chi Gao Lukai Li'
Yancheng Zhou?
Shangqi Guo
Abstract
Its goal infer missing links in a network based on the observed ones, real-world networks are often incomplete. Despite its significance, there exists substantial gap be- tween prevalent research settings and real-world demands: most models operate under the assumption that less than 15% of existing links are unobserved (Cen et al., 2023; Xiong et al., 2024), yet numerous such as biological, informational. and social networks, the proportion of unobserved links exceed by far that of observed links (Amaral, 2008; Olesen et al., 2011; Wei et al., 2016; Hohwald et al., 2009; Adafre & de Rijke, 2005). For instance, it is estimated that around 89% 98% human binary protein interactomes are still not verified (Dunham & Ganapathiraju, 2021). Our work aims to this gap by investigating data-scarce regimes and tackling the challenge of insufficient sample sizes.
Link prediction is fundamental problem for network-structure data. However, the prevalent research paradigm tends to assume abundant ob- served links, overlooking more challenging sce- narios with scarcity of observed links, which results insufficient sample sizes. In real-world networks, hierarchical modularity, characterized by structured and nested connections, remains robust even with sparsely observed links. To address the challenge of limited link samples, we propose leveraging hierarchical modularity as prior structure. We introduce complete-tree (CT) space, a discrete metric space with latent complete-tres tree structures, to formalize hierarchical modularity with an emphasis on its hierarchical permutation symmetry. Utilizing the group the- ory quantize and compare permutation sym- metries of different spaces, prove that the CT space provides a significantly lower bound on sample complexity than the commonly used Euclidean space. We develop leaf matching, a data-efficient network embedding that maps nodes onto the CT space and conducts discrete opti- mization by reducing it decentralized search. Experiments verify the data efficiency of CT space over other spaces. Moreover, leaf match- ing outperforms the state-of-the-an graph trans- former in data-scarce scenarios while exhibiting excellent scalability. The code available at: httpa/////eeeieeiaa///////aaaaaa
networks,
Sparsify
matrix of shortest path distance
2
2
1. Introduction
module
Link prediction is long-standing and crucial problem in both graph representation learning and network science (Lihen-Nowell & Kleinberg, 2003; Kumar et al., 2020).
Figure I. Hierarchical modularity exists regardless of link observ- ability: the distance matrices with different link observability both indicate that and b, as well as e and d, cach form a module, while two formed modules together constitute a larger module.
'Center for Brain-Inspired Computing Research, Department of Precision Instrument, Tsinghua University. Beijing, China "Weixia College, Tsinghua University, Beijing, China. Correspon- dence to: Shangqi Guo <shangqi_guo mailllulluu@iiiiieieeeaaaa wwinalll.iigggguuuuuuuuu
Insufficient sample sizes call for strong priors, leading us to focus on hierarchical modularity, a general property in many important real-world networks, including but not lim-
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Complete- Tree Space Favors
Link Prediction
ited social, scientific collaboration, gene interaction, and brain networks (Chen & Li, 2015; Radicchi al., 2004; Ryan et al., 2012; Meunier et al., 2010). In these networks, permuting nodes within modules of each layer preserves the overall distance matrix. Our key insight is that the hierar- chically modular structure can still be detected even with low link observability, as shown in Figure 1. This prop- erty allows hierarchical modularity to serve as an effective structural prior, narrowing the hypothesis space of joint link distributions and reducing the sample complexity.
significantly lower bound on sample complexity than the Eu- clidean space while maintaining expressivity for networks with an arbitrary latent tree structure.
2. Algorithm. We develop Ieaf matching, data-efficient network embedding that maps nodes onto the discrete CT space, and construct its optimization algorithm.
3. Experiment. We verify the data efficiency of the CT space over Euclidean, hyperbolic, and Hilbert space and demonstrate the practicality and scalability of leaf matching,
Hierarchical modularity inherently suggests hierarchical permutation symmetries in a network's 's latent space. For example, permuting nodes as (a. + (b, a). dc + (d, c). (a, b, c,d) - (c, d, a, b) and their compositions does not alter the distance matrices in Figure 1. To formalize this, introduce complete-tres (CT) space, discrete metric space with latent complete-tree structures. In this space, the leaf nodes form the point set and the minimum height of common ancestor root nodes defines distances. The CT space fully captures the hierarchical permutation symmetry of hierarchical modularity in real-world networks, allowing to intrinsically embed this prior and address the challenge of limited sample sizes. The upcoming challenge lies in the inherent discreteness of the CT space, which restricts the use of conventional mathematical tools commonly applied to continuous manifolds.
2. Related Work
Despite the abundance of existing work on link prediction, both our problem focus and method innovations are unique.
2.1. Inta-Efficient Graph Learning
Few-shot link prediction (Bose et al., 2019) aims to predict missing edges across multiple graphs using a small sample of known edges. This task targets applications where multi- ple graphs from single domain are available. In contrast, our work focuses on more challenging scenario where only one graph is known to the models. One-shot relation learning for knowledge graphs (Xiong et al., 2018) empha- sizes leveraging the semantic knowledge extracted by the embedding models for relation generalization, while our method utilizes the general topological structure for data- efficient link prediction on complex networks. The work of (Kitsak et al., 2023) deals with the similar setting of large, substantially incomplete networks but targets at the shortest path node finding problem rather than link prediction.
We solve this challenge by utilizing group theory. We define the submetry group by making an analogy with the classical concept of the isometry group, which captures the local per- mutation symmetries in metric space. This group enables us to quantitatively calculate the hypothesize space size of joint link distributions. We can then derive a lower bound on the sample complexity for link prediction in any finite metric space of node representations. We prove that the CT space offers a significantly lower sample complexity than the commonly used Euclidean space while maintaining ex- pressivity for networks with an arbitrary latent tree structure. Building on this, we develop leaf matching, a data-efficient network embedding that directly maps nodes onto the CT space. We further solve the discrete optimization challenge of leaf matching by converting it to an averaged version of greedy navigation over generated computation graph that ensures scalable decentralized search.
2.2. Metrie Space for Network Embeddings
The work of (Menand & Seshadhri, 2024) proves that low- dimensional vectors in Euclidean space cannot effectively capture the sparse ground truth of link distributions. In contrast, embeddings hyperbolic space (Nickel & Kiela, 2017) demonstrate competitive performance regarding rep- resentation capacity and generalization ability for link pre- diction. Mcanwhile, node2ket (Xiong et al., 2024), which operates in quantum Hilbert space, also exhibits excellent performance in both generalization capability and represen- tation efficiency. Our CT space is comparable to hyperbolic space in terms of the exponentially expanded neighbors but differs due to its unique hierarchical permutation symme- tries that theoretically ensures low sample complexity.
Experiments among network embeddings verify the sample- efficiency of CT space compared to Euclidean, hyperbolic, and Hilbert space. Meanwhile, leaf matching outperforms the state-of-the-art graph transformer in data-scarce scenar- ios on real-world networks, while maintaining scalability. The contributions are listed below:
2.3. Tree-based Link Prediction
HBDM (Nakis et al., 2023) is hierarchical block distance model that combines the clustered tree structure with Eu- clidean space vectors. The work of (Clauset et al., 2008) also employs the leaves of tree ensembles to represent each
1. Theory. We provide a sample complexity lower bound for link prediction with nodes represented in arbitrary finite metric space. We prove that the CT space offers
2

---

Complete- Tree Space Favors Data-Efficient Link Prediction
node for link prediction. A fundamental difference between leaf matching and these existing works is that the complete- tree structure is pre-determined instead of data-driven in leaf matching. Therefore, no search is needed in selecting the optimal tree, and the hypothesis space size is greatly reduced to enable data-efficient link prediction.
neural network is used for deriving node representations.
3.3. PAC learning for Link Prediction
Since link prediction can be formalized as supervised learning problem, the probably approximately correct (PAC) learning theory can be applied to calculate the sample com- plexity lower bound. Here we give the main result of PAC learning on which our theory is built (Shalev-Shwarr & Ben-David, 2014):
3. Preliminaries
In this section, we will first formalize the link prediction problem in a supervised learning context and second de- scribe the node representation framework on which our theory is built. We will then introduce the probably approx- imately correct (PAC) learning theory, which clarifies the main focus of our theory.
Lemma 3.1. Suppose the hypothesis space H is finite, the range of the loss function I E 10, and that the training links S are sampled i.i.d. from an arbitrary D, for any e. E (0, 1), the sample complexity satisfies that if 2 108(2)H1/8) then with probability of at least 1 - 6, the generalization gap (h)) - LD(h)]
|= S for all h E H.
3.1. Link Prediction as Supervised Learning
By Lemma 3.1, smaller hypothesis space size leads to lower sample complexity for given generalization gap. Therefore, the key is to effectively reduce the size of the hypothesis space to constrain the sample error while main- taining expressiveness to ensure low approximation error.
Consider a graph G = (V, E), with node set V (1,....)) o} and edge set E C V V. Formulating link prediction in supervised learning context, we can see that the input set comprises node pairs X = V x V, and the target set Y = [0, 1] provides continual quantification of link existence. Therefore, link prediction is exactly a regression problem. We restrict this study to undirected graphs.
4. Theoretical Bounds for the Complete-Tree Space and Others
The hypothesis space is then h : X + Y. Let I. be loss function, the generalization error of h is thus (h) = Ex.gr>((X,y)) (((()))))))))))))))))))))))))()) v)]. where D(X, Y) is un- known. The empirical error (h) = ((h,)((( 9:), where S = ((I,, j=) the training set for link predic- tion, comprising positive samples of observable links and generated negative samples.
In Section 4.1, we will first define the concept of the sub- metry group and, secondly, introduce the general sample complexity bound for an arbitrary finite metric space. In Section 4.2, we will formalize hierarchical modularity by complete-tree-basee metric space before calculating its sample complexity bound and comparing it with that of the Euclidean space. These two subsections focus on the sample error. In Section 4.3, we will discuss terms related to the approximation error by proving that the complete- -rreee---reeeee space is sufficient to represent networks whose latent space has an arbitrary tree structure. All the proofs are in Appendix A.
3.2. Link Prediction in the Finite Metric Space
Consider finite metric space (M, d), with point set M = (1,..., m of finite elements and the corresponding metric d: M x M + R. Suppose the metric space has dimension n. In that case, we denote that an n dimensional coordinate can represent each point in the point set, and that m = mf, where m, m. respectively correspond to the number of points in the n, dimensional metric space.
4.1. Bound for Finite Metric Space
By Lemma 3.1, the key for estimating the sample complexity bound lies in calculating the size of the hypothesis space H. We can see from Figure 2 that the symmetry of the metric space directly constrains the hypothesis space size: the more symmetric the metric space is, the larger number of node placements will correspond to the same joint connection probabilities, and therefore the smaller hypothesize space size. Therefore, the challenge lies in giving a countable description of the symmetry of the metric space, which we solve by utilizing concepts in group theory, as shown below.
Our theory is built upon the node representation framework, where each node of a graph is represented by point in the metric space (e.g.. coordinate vector in the Euclidean space), denoted by the mapping function ʃ V - M. The link probability of each two nodes is negatively correlated with the distance of two node representations, denoted by the probability function g : R - [0, 1]. strictly decreasing function with additional parameters related to the two nodes. Therefore, we can denote h X + Y as a composition function: h = g o d o (f x f). This formulation is general for link prediction, regardless of whether an embedding or
Since the nodes in V will generally occupy only a subset of the whole point set M instead of the whole set, the local symmetric properties of the metric space will more precisely constrain the hypothesis space size than the global ones.
3

---

Complete- Tree Space Favors Data-Efficient Link Prediction
arbitrary finite metric space as below.
Theorem 4.2. Suppose the v nodes of a graph are repre- sented by points non-overlapping in each dimension of an n dimensional finite metric space with m points, where m = mm. Suppose the link probability of each two nodes can be expressed by strictly decreasing function with the distance of Iwo node representations. Suppose the loss func- tion E [0, 11, and the training links S are sampled iidd from an arbitrary D. For any c. 8 E (0, 1), the sample complexity of link prediction satisfies that if
Nodes Graph
Peter Set of the Metric Synce M
Biizance
Node Placements
Distnnce of the Two Nudex
Connection Prolushility
oato the Mutric Space
distance C-O with probubilitt
Madalgu MI
213,2)
struntinss
situations
log 2 [A(m))")) MinSub(v,M 18)
distance probability
8 2
(2)
2e
then with probability of at least 1 6, the generalization
gap (hs(h) Ln(h)] | S for all h E H. Here we denote su as the sample complexity lower bound, and A(m1, v) as
Figure Since the distances of three points in metric space form isosceles triangle, the metric space constrains the size of the hypothesis space: the size reduced to despite the six situations of node placements.
that the local symmetry of
the permutation number: choosing ordered elements from
my distinct elements.
4.2. Bounds for the Complete- T and Euclidean Space
However, no concepts in the mathematical literature, as far we know, can directly deseribe such local symmetries. Therefore, before introducing the main theory, we will first define the submetry group by making an analogy with the existing concept of isometry group.
From Theorem 4.2, can see that the sample complexity lower bound for link prediction is directly constrained by the MinSub (v, M) of the metric space from which to represent the nodes. We will start from the property of hierarchical modularity and see if it could lead to a metric space with large order of the submetry group, and therefore constraining the sample complexity.
Definition 4.1. Submetry Group.
The submetry group is defined to measure the local permutation symmetries finite metric space. Specifically, consider a subset of points M, C M in a metric space (M, d) with n dimensions, where M, satisfies that the coordinates of each point M, maps from M2 to M, we define submetry group as the set of a that maintains all pair- wair distances:
A module means that the nodes inside the module have more significant connection probability than those outside. Therefore, module implies the symmetry of an arbitrary permutation of nodes inside the module. Hierarchical modu- larity thus implics that the latent metric space of the network has hierarchical permutation symmetry, which naturally satisfied by a tree. Accordingly, we formally define the complete-tree space below, visualized by Figure 3.
do not overlap in each dimension. Denoting
Sub(M,, M) A {ald(i.j) = (lo(i), M.). (1)
Definition 4.3. Complete-Tres Tree (CT) Space. Consider a complete b-ary tree with k layers. We define the distance be- tween any two leaf nodes i. as k- where ica(i.)) de- notes the height of the lowest common ancestor node of i, Note that Ica(i, 2) = O. Now consider the n--dimensional case: the point set be the concatenation of leaf nodes:
We denote the isometry group of M as [M). Note that submetry group is a natural extension of the isometry group: when M, A1 and is restricted to bijection, the subme- try group becomes exactly the isometry group.
lca(t.))
Different M, may have different orders of submetry groups, but we focus on boundary situations where the order of the submetry group is relevant only to the number of ele- ments in the subset Mg. Thus, we define MinSub(l, .M) = min ((Sub(M,, M)l) to represent the minimal local sym- |M, metry of a metric space.
McT (1 (4,, L2, ..., (n)) and metric dCT(((a), ((0)
niK-Ij E._i Ica(!!") (())) for arbitrary f(a),110 E M. We can easily verify that det McT x McT - IR is metric and deT E [0, 1]. A CT space is exactly (Mer, der) with parameters b, k,
Given the definition of CT space, can prove:
With the definitions above, we can now provide an exact es- timation of the hypothesis size H in the most general sense. Taking such an estimation into Lemma 3.1 of PAC learning, we can derive the sample complexity lower bound for an
Theorem 4.4. For CT space with parameters b, k, n. suppose 1 S b-1 mR, then MinSuber (1, Mcr) > 1-1
m 11-

---

Complete- Tree Space Favors Data-Efficient Link Prediction
Comparing Theorem 4.4 with Theorem 4.5, and being aware that the number of nodes is generally much higher than the dimension of the metric space, we can see that
3
b
c
d
e
f
g
h
a
a
0
1
2
2
3
3
3
3
Proposition 4.6. The Complete- Tree Space is more sample- efficient than the Euclidean Space for node presenlation in link prediction.
b
0
2
2
3
3
3
3
C
2
2
0
1
3
3
3
3
d
2
2
1
0
3
3
3
3
To understand intuitively why Proposition 4.6 holds, we can refer to the visual representation in Figure 4.
c
3
3
3
3
0
1
2
2
f
f
3
3
3
3
1
0
2
2
4.3. Expressivity of the Complete-Tres Tree Space
3
3
3
3
2
2
0
1
While the previous subsections focus on the sample error, this subsection emphasizes the approximation error. Con- sider real-world networks with an arbitrary latent tree struc- ture. Their latent space can be formalized by the arbitrary- tree space, which resembles the complete-tree space but allows for varying bifurcation numbers. In Theorem 4.7, will demonstrate that a subspace within the complete-tree space can effectively approximate the arbitrary-tres space, as illustrated in Figure 5.
h h
3
3
3
3
2
2
1
0
Figure 3. The complete-tree space has hierarchical permutation symmetries implied by the property of hierarchical modularity. For example, the permutation of (a, b) > (b, a). b, d) (c,d, d, a, (a, b, d, e, f.g,h) h) + (c, J.g. g. h, a, b, c, d) or their compositions does not change the distance matrix.
Now move on to the case of the Euclidean space, which default choice in graph representations. Consider an dimensional Euclidean space with the commonly used cosine similarity the metric. The point set in this space can be restricted to n dimensional sphere. When considering a discrete version of this space, reasonable due to the finite precision of real numbers in computers, such as float 64, there exist finite and countable points on the sphere. is straightforward to prove that
node the intent tree structure
the wrbitrary space
Theorem 4.5. For discrete Euclidean space with cosine similarity as the distance, MinSubgu (1, MBu) = 2m "# where n the dimension of the sphere and m is the number of points in the metric space.
aM MAr Mer
Figure 5. Subspace approximation: by increasing number layers, there exists mapping оı MMA Mcr from points in the arbitrary tree space to the complete-tre trope space so that (1) the distance order is preserved; (2) the distance gap is constrained.
Theorem 4.7. Subspace approximation. Consider arbitrary-tree space with dimension n, with the tree struc- ture in each dimension including ka layers. The bifurca- tion number the ith layer ranges from 1(2)
rotations
(6) where
by
hierarchical permutations
max( logg 6
reflections
= 0,
kn 2, and denote r min! log, 6
ri = max( log, 1/(2 Then there exists map OM MAT - McT from the arbitrary-tree space to a complete- tree space with dimension n., bifurcation number and k layers, where ke the distance order is loosely preserved; (2) the distance gup is constrained:
CT space
Euclidean space
Ek--2 log, b
!socr| 2
128
[sog.l 8 2 16
that (1)
derlam(a))osr()) satisfies that darla.)]
Figure 4. This figure shows that the CT space has much larger order of isometry group than the Euclidean space in the one- dimensional case. The comparison of submetry groups in multi- dimensional cases is more complex, but maintains the conclusion.
E [min(], 1,, +),r). rl. Loose order preservation: for an arbitrary three points a, b, c in the arbitrary-tree space, if the distances in the arbitrar-ttree space satisfies that
5

---

Complete- Tree Space Favors Data-Efficient Link Prediction
(a, dAr (a,c), c) then in the complete-tree space, we have dct (a ( < (c), (c))
Theorem 4.7 establishes that the complete-tree space is suf- ficient to represent network with latent space of arbi- trary tree structures. This ensures that the approximation eπror will be low. Note that this conclusion is general for real-world complex networks because hierarchy is a central organizing principle complex networks as demonstrated in (Clauset et al., 2008).
0
1
2
2
3
3
3
3
3
5. Leaf Matching
2
2
0
3
3
3
3
3
Leaf matching is an embedding that maps the nodes in graph
3
3
3
3
0
2
G to points in the CT space as defined in 4.3 with parameters (b, k. n). denoted as f - McT. We generally set = 2
3
3
3
3
1
2
and & for 1 approach the number of nodes in G.
3
2
0
3
3
3
3
2
1
5.1. Loss Function
The loss function of each node in graph G is defined below:
Figure 6. Leaf matching. The left side represents the latent tree structure and the distance matrix of the CT space. The right side shows the generated computation graph and the discrete optimiza- tion process. Specifically, the computation graph is derived from the CT space, and optimization occurs by moving to neighbor node (arrowed) on the computation graph that has the lowest loss.
loss(i) Σ log(p(i,
Σ log(1 p(i, A)) KEN
(3)
where P includes all the other endpoints of observable links that are connected to an endpoint of i. The negative nodes E N are randomly selected deg(i) times from V to serve as negative samples; À balances positive and negative losses. The probability p(i;j) that each nodes i,j in graph G has link in the CT space is computed below:
Consequently, we shift our focus to decentralized search techniques, which operate effectively in discrete domains and rely solely on local information.
Jon Kleinberg (2001; 2006) demonstrates that a specific sub- set of small-world networks can guarantce polylogarithmic time complexity for navigation between arbitrary pairs of nodes using a greedy strategy. This phenomenon suggests that the neighboring nodes in such networks can naturally define the neighborhoods within the discrete CT Space, fa- cilitating scalable convergence. Building on this insight, the optimization algorithm for leaf matching is developed, reducing the network embedding optimization problem to an averaged version of greedy navigation.
p(..ja,n))
(4)
(CT(f(FFG) T log (d) deg()))
a
where deg(i) denotes the degree of the i th node, and (()) denotes the distance of the two points in the CT space that represent nodes j. This formula is mod- ified from (Krioukov et al., 2009; Jankowski et al., 2023), with an additional log term to match the exponentially grow- ing neighborhood size of points in the CT space. Here ? 1, implies the clustering coefficient inverse of temperature, which is unique to each type of complex net- work. a > 0 is simply selected so that the loss is balanced between positive and negative samples, analytically calcula- ble (Allard et al., 2024) when the network is scale-free.
Specifically, for each dimension of the complete- tree space, computation graph Ge is generated where the points (leaves) in the 1-dimensional CT space form the node set of G.. Each node has constant degree ka c clog (mz), where πy = bベー1 denotes the number of nodes in G, (se- lected to approach [V] in G), and e is a constant. The probability that arbitrary two nodes x, y are connected in Ge given by the following expression
5.2. Optimization Method
Pe(x, v) x (der(zzg))
(5)
Since the CT Space is discrete, defining neighborhoods and gradients poses challenges. This limitation prevents the application of standard optimization methods used in continuous manifolds, such stochastic gradient descent.
The optimization procedure is shown in Algorithm 1:
Scalability. The three loops Algorithm can all be
6

---

Complete- Tree Space Favors Data-Efficient Link Prediction
Algorithm 1 Grredd-Naviggation-ban Optimization
6.1. Settings
Input: an graph to be embedded G (V, E) with v nodes and my edges; d computation graphs Ge Ec),
6.1.1. DATASETS
Initiate: Randomly map each node i in G to a node in each computation graphs Gei the output is f1) with d dimensions. repeat
We experiment on six datasets, including the classic Cora, Pubmed, Citeseer (Yang et al., 2016; Li et al., 2024), the large-scale ogbl-collab, ogbl-ppa (Hu et al., 2020), and the temporal ICEWS18 (Liu et al., 2022). These six typical benchmark datasets, which vary in size, include real-world citation, collaboration, political event, and protein interac- tion networks. Detailed data statistics are in Appendix B.
Add randomness. If the current epoch is below given ratio r, of the maximum epoch, randomly adjust all edges of a node to connect to a single random edge in the graph G' with a given probability. for = 1 to e do
6.1.2. EVALUATIONS
for j 1 to ka do
For Cora, Pubmed, Citeseer, and ICEWS18 utilize ROC- AUC, PR-AUC, and FI score as the evaluation metrics. For the large-scale ogbl-collab and opb,, we adopt the de- fault evaluation metries of Hits@ 100 and Hits@ 50. We define link observability as the ratio μ between observ- able (training) edges and ground truth (total) edges. In the space comparison experiment, we vary μ from 0.9 to 0.1. In the practicality experiment, practical scenarios. For data splitting and the negative ratio in testing, we adhere to the settings established by CogDL. (Cen et al., 2023). Note that certain nodes from the test set are excluded if they lack links in the filtered training set.
for k = 1 to d do
Loss calculation. Compute loss(1) with the representation of i in the kith computation graph now changed to be the jth neighbor node in Ge- end for
Greedy navigation. Map the representation of in the ktth computation graph the neighbor node (including the current node) with the lowest loss. end for end for
set μ 0.02 simulate
until The training epoch reaches a given value.
6.1.3. MODELS
parallelized through vector computations, resulting in a par- allelizable time complexity of Om. logğ (m))d), where d is the dimension of the CT space. It's important to note that we use here instead of n to prevent any misunderstandings in the representation of time complexity; in other places of this paper, n corresponds to the dimension.
There are twelve baselines. Three are representative net- work embeddings: node2vec (Grover & Leskovee, 2016), Poincaré (Nickel & Kiela, 2017), and node2ket (Xiong et al., 2024), respectively applying the Eaclidean, hyperbolic, and quantum Hilbert space. Three are representative neural networks, including the -fate-of-the-art (SOTA) LPformer (Shomer et al., 2024) and two GNN baselines: SEAL (Zhang & Chen, 2018) and GAE (Kipf & Welling, 2016). The re- maining six are heuristic algorithms: Adamic Adar (AA) (Adamic & Adar, 2003), Common Neighbors (CN) (New- man, 2001), Jaccard's Coefficient (JC) (Jaccard, 1901), Katz Index (KI) (Katz, 1953). Resource Allocation (RA) (Zhou et al., 2009), and Preferential Attachment (PA) (Barabási et al., 1999). All parameter settings are in Appendix B.
Since integers can represent the leaf nodes, each point in the d dimensional CT space can be represented by integer vector. We generally choose b- = 2 for leaf matching, so that both distance computations and edge samplings for the com- putation graphs can be accelerated through bit operations.
Since the greedy navigation for decentralized search has guaranteed time complexity ([log,(m))) (Kleinberg, 2001), the number of convergence epochs for leaf matching is also O (nt)). which is demonstrated in the scalability experiment 6.3.2. Consequently, the total time complexity for leaf matching becomes (m, logá dd). Note that n4 is set to approach the number of nodes in G. Therefore, the discrete optimization algorithm is fast and scalable.
6.2. Data Efficiency of the Complete-Tree Space
In this experiment, we compare leaf matching using the complete-tree (CT) space with classic network embeddings from other spaces. Since all the models being compared are network embeddings, we anticipate that this experiment will effectively reveal the sample complexity of different spaces for node representation in link prediction. For fair comparisons, we set the dimension size to 16.
6. Experiment
We will outline experimental settings in Section 6.1, com- pare network embeddings across metric spaces to demon- strate the data efficiency of the CT space in Section 6.2, showcase the practicality and scalability of leaf matching in Section 6.3, and present ablation results in Section 6.4.
As shown in Figure 7, leaf matching generally outperforms all baselines across various link observability levels on repre- sentative datasets. Notably, as link observability l decreases,
7

---

Complete- Tree Space Favors Data-Efficient Link Prediction
PUBMED
ICEWS18
OGBL COLLAB OGBLACOLLAB
50-
ROC-AUC (N6)
85
ROC-AUC (%6)
Hitslg500 (%6)
80-
20-
redelvee (bocildear)
(lkhher)
75-
60-
puizeare (Hsperlulie)
16-
Complete- Trua)
70-
0.9
0.8
07
0.
0.5
04
033
62
0.1
0.9
0.8
0.7
0.6
0.4
0.3
0.2
0.1
0.
0.3
0.7
0.6
0.5
0.4
0.3
02
6.7
Observability
Observahility
Observahility
Figure 7. The performance of the four network embeddings across three representative datasets is presented, with link observability decreasing from 0.9 to 0.1. Experiments were repeated times. curves show mean values, the shaded areas represent standard deviation. The full results (such as Cora, Citeseer and PR-AUC, Fl Score) can be found in Appendix B.
the advantage of leaf matching over node2vec increases, confirming the sample efficiency of the CT space compared to the Euclidean space, established in Proposition 4.6.
lar structures are generally detected and preserved by the CT space. At low link observability (μ 0.2), the structures are even sharpened, qualitatively demonstrating how and why the CT space is data-efficient.
Furthermore, the strong performance of leaf matching even at high link observability highlights the effectiveness of the CT space in representing complex networks, as demon- strated in Theorem 4.7. is worth noting that the Poincaré embedding in hyperbolic space exhibits relatively low per- formance. We attribute this phenomenon to the fact that the Poincaré space has only one central point with exponen- tially expanded neighbors, which limits its effectiveness to tree-structured data. contrast, the CT space allows every point to have exponentially expanded neighbors, enabling it to effectively represent real-world complex networks.
6.3. Practicality and Scalability of Leaf Matching
6.3.1. 1. PRACTICALITY
Table 1. The link observability set to = 0.02 for simulating extremely difficult setting with practical meanings, around -9%- human binary protein interactomes are still not verified (Dunham & Ganapathiraju, 2021). Hit@50 and Hit@ 100 reported, respectively, for the ogbl-collab and ogbl-ppa datasets.
MODEL
FEATURE
COLLAB(%)
PPA(%)
Shortest- path distance (normalized)
CT space distance (degree corrected)
LPFORMER
15.55 1.63
0.27 0.03
LPFORMER
X
8.43 = 3.05
0.19 + 0.07
SEAL
V
5.26 = 1.46
OOM
SEAL
1.03 0.38
00M
GAE
0.04 0.00
0.00
" 0.2
GAE
X
0.21 = 0.10
0.00 + 0.00
AA
X
3.52
0.12
CN
3.52
0.08
JC
3.52
0.02
6.76
0,03
RA
3.52
0.11
PA
2.02
0.06
/ 0.8
OURS
15.60 = 0.24
0.55 + 0.04
Table shows that leaf matching outperforms all baselines, including the SOTA neural network (LPformer) even with the additional information node features. Leaf matching is thus practical for link prediction in real-world low-data scenarios. Here we highlight some key applications where sparse link prediction is crucial: (1) scientific collaboration recommendation (Guo & Chen, 2013; Barabåsi et al., 2002):
Figure 8. Distance matrices of Citeseer are presented for nodes with the maximal degree. Additional visualization results be found in Appendix B.
We can also see from Figure 8 that the hierarchically modu-
8

---

Complete- Tree Space Favors Data-Efffcient Link Prediction
(2) prediction of human protein interactomes (Dunham & Ganapathiraju, 2021); and (3) other important real-world networks such as mutualistic (Olesen et al., 2011), large so- cial (Hohwald et al., 2009), and Wikipedia networks (Adafre & de Rijke, 2005), which have also demonstrated a higher prevalence of unobserved links compared to observed ones.
A complementary experiment comparing the detailed run- time per epoch is also conducted shown in Figure 10, demonstrating the time efficiency of leaf matching, We at- tribute such a good property to the fact that each point in the n dimensional CT space can be represented by an integer vector: we generally choose = 2 for leaf matching, so that bit operations can implemented to accelerate both distance computations the CT space and edge samplings for the computation graphs.
6.3.2. SCALARILITY
We conduct scaling tests using both synthetic (Erdös-Rényl random networks) and real-worke (ogbl-collab) networks to verify the scalability of leaf matching.
6.4. Ablation Studies
The ablation experiments are conducted on Cora, Pubmed, and Citeseer, regarding and with μ 0.1. It can be from Figure 17 in Appendix B that leaf matching remains robust with varying hyperparameters.
Random Networks (Synthetic)
140
Ogbl-Collab (Real)
number of epachs
120
7. Conclusion and Discussion
100
We systematically investigate data-efficient link prediction in metric spaces. We develop sample complexity theories from the perspective of permutation symmetry, introduce the data-efficient complete-tree space, construct network embedding lcaf matching with a scalable optimization algo- rithm, and validate our findings experimentally.
80
60
10
10
number of nodes
Figure 9.
The convergence epoch is shown regarding the number
nodes in the networks.
Table 2. Efficiency comparison between metric spaces. Specifi- cally, data efficiency depends on the size of the hypothesis space, time efficiency depends whether there exists sub-quadratic op- timization algorithm, and space efficiency depends on the typical vector dimension.
Figure shows that the convergence epoch of leaf matching linearly (or even sub-linearly) related the logarithm of the number of nodes in the graph, representing excellent scalability. This is because leaf matching is optimized specific computation graph guaranteeing polylogarithmic time complexity for navigation between arbitrary pairs of nodes using greedy strategy, as described in Section 5.2.
Efficiency Type
Data
Time
Space
Complete-Tree Tree Space Hilbert Space
Hyperbolic Space
Fuclidean Space
Runtime per epoch with fixed batch size (512)
curs
0OM
We highlight above an efficiency comparison between com- monly used metric spaces. It can be seen that the CT space is generally efficient. Furthermore, its ability efficiently express arbitrary hierarchical structures suggests broader datatype extensions to enable data-efficient natural language processing (Tifrea et al., 2018), visual modeling (Zhuang et al., 2019), and hierarchical planning (LeCun, 2022).
GAAB
SEAL
(slepoch)
10
35. 76
26.42
16.35
10'
In terms of insights for neuroscience, the CT space may also facilitate the functional understanding of hierarchically arranged grid cells in the entorhinal cortex (Zhang et al., 2023; Shpektor et al., 2024). Additionally, the proposed optimization method on the multi-dimensions CT space may reveal what the natural gradient in the brain is for, particularly in contexts where brain networks are greedily navigable (Seguin et al., 2018: Heszberger al., 2021).
1.43
10"
cobl-collab
ogbl-ppa
Figure 10. Runtime comparison between leaf matching and neural
network baselines.

---

Complete- Tree Space Favors Data-Efficient Link Prediction
Acknowledgements
Chen, F. and Li, K. Detecting hierarchical structure of community members in social networks. Knowledge- based systems, 87:3-15, 2015.
We sincerely thank Luping Shi, Rong Zhao, Dahu Feng, Yihan Lin, Hao Zheng, Likai Tang. Sen Song, Huan Luo, Songhai Shi, and Ila Fiete for their valuable comments and encouragements. This work supported by the National Natural Science Foundation of China (Grant 62206151) and China National Postdoctoral Program for Innovative Talents (Grant BX20220167).
Clauset, A., Moore, C., and Newman, M. Hierarchical structure and the prediction of missing links networks. Nature, 453((191):98-1)5 2008.
Dunham, B. and Ganapathiraju, M. K. Benchmark evalua- tion of Molecules, 27(1):41, 2021.
interaction prediction algorithms.
Impact Statement
This paper aims to advance the field of Representation Learn- ing. with the positive social impact of facilitating deeper understanding of critical networks, such as human protein interactomes, mammalian brain connectomes, and genetic interactions, even in the face of technological or funding constraints. However, there is a potential negative social impact when these techniques are applied to social networks, particularly regarding privacy concerns. It is essential to balance the benefits of enhanced understanding with the ethical implications of data usage in sensitive contexts.
Grover, A. and Leskovec, J. node2vee: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discov- ery and data mining, pp. 855- 864, 2016.
Guo, Y. and Chen, X. Cross-domain scientific collaborations prediction using citation. In 2013 IEEF/ACM interna- tional conference on advances in social networks analysis and mining (ASONAM 2013), pp. 765-770. IEEE, 2013.
Heszberger, Z.,, Majdán, A., Biró, A., Gulyás, A., Balázs, I.., Németh, V., and Bíró, J. Greedy navigational cores in the human brain. In Advances in Parallel & Distributed Pro- cessing, and Applications: Proceedings from PDPTA '20, CSC'20, MSV'20, and GCC'20, pp. 337-346. Springer, 2021.
References
Adafre, S. F. and de Rijke, M. Discovering missing links in wikipedia. In Proceedings of the 3rd international workshop on Link discovery, pp. 90-97, 2005.
Adamic, L. A. and Adar, E. Friends and neighbors on the web. Social networks, 25(3):211-244 2003.
Hohwald, H., Cebrián, M., Canales, A., Lara, R., and Oliver, N. Inferring unobservable inter-community links in large social networks. In 2009 International Conference on Computational Science and Engineering, volume 4, pp. 375-380. IEEE, 2009.
Allard, A., Serrano, M. Á., and Boguñá, M. Geometric description of clustering in directed networks. Nature Physics, 20(1):150-155) 2024.
Amaral, L. A. N. A truer measure of ignorance. Pro- ceedings of the National Academy of Sciences, 105(19); 6795-6796, 2008
Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118-22133 2020.
Barabási, A.-I.,, Albert, R., Jeong, H. Mean-field theory for scale-free random networks. Physica A: Statistical Mechanics and its Applications,
1999.
Jaccard, P. Étude comparative de la distribution florale dans une portion des alpes et des jura. Bull Soc Vaudoise Sci Nat, 37:547-579, 1901.
Barabãsi, A.- Jeong, H., Néda, Z., Ravasz, F.,, Schubert, A., and Vicsek, T. Evolution of the social network of scientific collaborations. Physica A: Statistical mechanics and its applications, 311(3-4):590-614 2002.
Jankowski, R., Allard, A., Boguñá, M., and Serrano, M. Á. The d-mercator method for the multidimensional hyper- bolic embedding of real networks. Nature Communica- tions, 14(1):7585, 2023.
Bose, A. J., Jain, A., Molino, P., and Hamilton, W. L. Meta- graph: Few shot link prediction via meta learning. arXiv preprint arXiv: 992.0982... 2019.
Cen, Y., Hou, Z., Wang. Y., Chen, Q. Luo, Y., Yu, Z.,, Zhang, H., Yao, X., Zeng, A., Guo, S., et al. Cogdl: A comprehensive library for graph deep learning. In Proceedings of the ACM Web Conference 2023, pp. 747-
Katz, L. A new status index derived from sociometric anal- ysis. Psychometrika, 18(1):39-43, 1953.
Kipf, T. N. and Welling, M. Variational graph auto-encoders. arXiv preprint 161 2016.
758, 2023.
10

---

Complete- Tree Space Favors Data-Efficient Link Prediction
Kitsak, M., Ganin, A., Elmokashfi, A., Cui, H., Eisenberg, D. A., Alderson, D. L.,, Korkin, D., and Linkov, I. Find- ing shortest and nearly shortest path nodes in large sub- stantially incomplete networks by hyperbolic mapping. Nature Communications, 14(1):186, 2023.
Meunier, D., Lambiotte, R., and Bullmore, E. T. Modu- lar and hierarchically modular organization of brain net- works. Frontiers in neuroscience, 4:200, 2010.
Nakis, N., Çelikkanat, A., Lehmann, S., and Mørup, M. A hierarchical block distance model for ultra low- dimensional graph representations. IEEE Transactions Knowledge and Data Engineering, 2023.
Kleinberg, J. Small-world phenomena and the dynamics of information. Advances in neural information processing systems, 14, 2001.
Newman, M. E. Clustering and preferential attachment in growing networks. Physical review E, 64(2):025102, 2001.
Kleinberg, J. Complex networks and decentralized search al- gorithms. In Proceedings of the International Congress of Mathematicians (ICM), volume 3, pp. 1049.1044. Cite- seer, 2006.
Nickel, M. and Kiela, D. Poincaré embeddings for learning hierarchical representations. Advances in neural informa- tion processing systems, 30, 2017.
Krioukov, D., Papadopoulos, F., Vahdat, A., and Boguná, M. Curvature and temperature of complex networks. Phys- ical Review E Statistiicll, Nonlinear, and Soft Matter Physics, 80(3):33101, 2009.
Olesen, J. M., Bascompte, J., Dupont, Y. L., Elberling, H., Rasmussen, C., and Jordano, P. Missing and for- bidden links in mutualistic networks. Proceedings of the Royal Society B: Biological Sciences, 278(1706):725- 732, 2011.
Kumar, A., Singh, S. S., Singh, K., and Biswas, B. Link prediction techniques, applications, and performance: A survey. Physica A: Statistical Mechanics and its Applica- tions, 553:124289, 2020.
Quessard, R., Barrett, T., and Clements, W. Learning disen- tangled representations and group structure of dynamical environments. Advances in Neurul Information Process- ing Systems, 33:19727-19737, 2020.
LeCun, Y. A path towards autonomous machine intelligence version 0.9. 2, 2022-06-27. Open Review, 62.1) 2022.
Radicchi, F., Castellano, C., Cecconi. F., Loreto, V., and Parisi, D. Defining and identifying communities in net- works. Proceedings of the national academy of sciences, 101(9):2658 01-266666666,,, 2004.
Li, J., Shomer, H., Mao, H., Zeng, S., Ma, Y., Shah, N., Tang, J., and Yin, D. Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking. Advances in Neural Information Processing Systems, 36: 3853-3866, 2023.
Ryan, C. J., Roguev, A., Patrick, K., Xu, J., Jahari, H., Tong, 7.,, Beltrao, P., Shales, M., Qu, H., Collins, S. R., et al. Hierarchical modularity and the evolution of genetic interactomes across species. Molecular cell, 46(5):691- 704, 2012.
Li, J.. Shomer, H., Mao, H., Zeng, S., Ma, Y., Shah, N., Tang, J., and Yin, D. Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking. Advances in Neural Information Processing Systems, 36, 2024.
Seguin, C., Van Den Heuvel, M. P., and Zalesky, A. Nav- igation of brain networks. Proceedings of the National Academy of Sciences, 115(24):6297-3300 2018
Liben-Nowell, D. and Kleinberg, J. The link prediction problem for social networks. Proceedings of the twelfih international conference on Information and knowledge management, pp. 556-559, 2003.
Shalev-Shwartz S. and Ben-David, S. Understanding ma- chine learning: From theory to algorithms. Cambridge university press, 2014.
Shomer, H., Ma, Y., Mao, Li, J., Wu, B., and Tang, J. Lpformer: An adaptive graph transformer for link prediction. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2686 2024.
Liu, Y., Ma, Y., Hildebrandt, M., Joblin, M., and Tresp. V. Tlogic: Temporal logical rules for explainable link fore- casting on temporal knowledge graphs. In Proceedings of the AAAI conference on artificial intelligence, volume 36, pp. 4120-4127, 2022.
Shpektor, A., Bakermans, J. J., Baram, A. B., Sarnthein, J., Ledergerber, D., Imbach, L., Müller-Seydlizz, E., Barron, H. C., and Behrens, T. E. A hierarchical coordinate system for sequence memory in human entorhinal cortex. bioRxiv, pp. 2024 2024.
Menand, N. and Seshadhri, C. Link prediction using low- dimensional node embeddings: The measurement prob- lem. Proceedings of the National Academy of Sciences, 121())e2312227121 2024.

---

Complete- Tree Space Favors Data-Efficient Link Prediction
Tifrea, A., Bécigneul, G., and Ganea, O.-E. Poincaré glove: Hyperbolic word embeddings. arXiv preprint arXiv: 18X100880000556, 2018.
Wei, X., Cao, B., Shao, W., Lu, C.-T., and Philip, S. Y. Community detection with partially observable links and node attributes. In 2016 IEFE International Conference on Big Data (Big Data), pp. 773-782. IEEE, 2016.
Xiong, H., Tang, Y., He, Y., Tan, W., and Yan, J. Node2ket: Efficient -ihhdiimensonaal network embedding in quan- tum hilbert space. In The Twelfth International Confer- on Learning Representations, 2024.
Xiong, W., Yu, M., Chang, S., Guo, X., and Wang, W. Y. One-shot relational learning for knowledge graphs. arXiv preprint arXiv:I800 0000000000 2018.
Yang, Z., Cohen, W., and Salakhudinov, R. Revisiting semi-supervised learning with graph embeddings. International conference on machine learning, pp. 40-48.
PMLR, 2016.
Zhang. H., Rich, P. D., Lee, A. K., and Sharpee, T. O. Hippocampal spatial representations exhibit a hyperbolic geometry that expands with experience. Nature Neuro- science, 26(1): 1311):131113) 2023.
Zhang, M. and Chen, Y. Link prediction based on graph neu- ral networks. Advances neural information processing systems, 31, 2018
Zhou, T., Lü, L., and Zhang, Y.C. Predicting missing links via local information. The European Physical Journal B, 71:623-631 630. 2009.
Zhuang, C., Zhai, A. L., and Yamins, D. Local aggregation for unsupervised learning of visual embeddings. In Pro- ceedings of the IEEE/CVF international conference on computer vision, pp. 2002-6012, 2019.
12

---

Complete- Tree Space Favors Data-Efficient Link Prediction
A. Theoretical Proofs
A.1. Theorem 4.2
Since M is a finite metric space, and that graph G has finite nodes, we can see that the hypothesis space is finite. Therefore, the requirements of lemma 3.1 satisfied and the sample complexity lower bound is determined by the size of the hypothesis space |
Since the probability function 9 R + [0, is strictly decreasing, [ equals the total number of the joint pair- pair-wise distance distributions of the nodes in the metric space, which we denote as | = [J], and j E J denotes joint distance distribution.
By the assumption of non-overlapping mappings from V to M, we know that there are totally [A(m1, e)]" situations of node placements F = {.}. We can easily see from Figure 2 that there exists a mapping K F that is many-to-one surjective function.
For each f E F, there is Mf)(), and therefore (f), By the definition of submetry group, know that {or Slo E (J)(M. M)} is set of node placements that belongs to the same joint distance distribution. We denote this set as Set(f). Meanwhile, for an arbitrary f. we have [Set(f) 2 MinSub(v, MC). Therefore, an arbitrary distance distribution j has at least MinSub(u, M) node placements.
Since K: F - J is many-to-on surjective function, can derive that [|] theorem 4.2 by lemma 3.1.
|||
1. and therefore MiSub(e,
A.2. Theorem 4.4
Before bounding the MinSub(l, for the general dimensional CT space, we will first give the result of the more basic one-dimensional case.
For CT space with parameters b, k, 1, suppose v S k-1 and denote the order of the isometry group of one-dimensional CT Space as T(b, k). Since [(bb 1) and T(b, k + 1) T(b, k) for k 1,2,3, ..., we can derive T(b, k)) b! -
When it comes to the submetry group, its reduction of order from the isometry group happens when some leaves in certain subtree are not fully occupied (permutations within these non-occupied leaves will not add to the order of submetry). Therefore, MinSuber(1, Mcr; 1) occurs when the leaves are occupied most intensively.
Accordingly, we can derive MinSubeT(4 (1, McT; 1) > I(b, + [log(())))
Now can we give the lower bound of MinSuber (1, McT) for the more general n-dimensional case.
From the one-dimensional case, we know that MinSub(I, Meri l)er > 1(b, + [log((0]] where [lb, k:) = 1--1 for the 1 dimensional case. Therefore, MinSub(l, Mcrsn) > I(b, 1 + [logs (1))) (bb) [+1ttoa(1)) -1 (bl) 1
(bl)
m 17 [(b 1)!] = m 116
A.3. Theorem 4.5
The cosine similarity suggests that the m points in the point set can be regarded as evenly distributed over n dimensional unit sphere, where the isometry group is composed of rotations and reflections.
By (Quessard et al., 2020), we know that rotations in the n + 1 dimensional space can be parameterized by the product of (1+1)m unit rotations. Aware that there exists one-to-one mapping between each rotation and each reflection (with a deter- 2
minant of and - respectively, in matrix representations), we can therefore derive that [[sor ( (MEw) = 2m fm
2m + Meanwhile, since the Euclidean space only has global symmetries and that the points M, by definition can by covered by an n 1 dimensional sphere, we can see that MinSubga (1, Mcr) = [Iso = 2m nサ1
13

---

Complete- Tree Space Favors Data-Efficient Link Prediction
A.4. Proposition 4.6
From Theory 4.2, we know that the sample complexity lower bound is negatively correlated with MinSub(e, M). For the Euclidean Space with dimension (here refers the dimension of the corresponding sphere), MinSub (v, Mr.)
(Mgg) 2m _ For the CT space, MinSuber Mcr) > m m Since the number of nodes in graph generally much larger than the dimension used, we can see that MinSuber(r, (Mr))) > m ((-1X--1 > MinSubbu(r, MEx) 2m 2. Therefore, the CT Space is theoretically more sample-efficient than the Euclidean space for node representation in link prediction.
A.5. Theorem 4.7
We first give the proof of the dneedimeniionll case.
Denote the coordinate of point in the arbitrary-tree space as a number of the corresponding node in the bifurcation to the ith layer. For example, the point in the most left side of a tree has coordinate of (0, O, .O...........,,. Similarly, denote the coordinate of a point in the complete-tree space as y (yo. "/,.......,,........ -2)
Tk.- where denotes the serial
Construct the map оM MAT MeT such that y - a (x) == (xri)t. where (aa),b denotes the reversed code of x; in the b-nary code with complementary zeros.
Consider two different points b in the arbitrary-tree space, and denote as the location of the last different element of (0() and (b), We can see that AT b)
Re I where E [0, hip 2]. Meanwhile, we can derive that
s+1
if 0
dct (c)(
logs bh he-1
(6)
if 8 > 0
where E [1, Tog, ] denotes the height of the lowest common ancestor node the sth coordinate of point a,b, respectively, in complete tree with bifurcation number b.
If (a, < dar(a, c), the location s(a, b) < s(a,c), c). Therefore, (CT(aM((4) < dCT(oM (a) the loose order preservation is proved.
Meanwhile, since K. = + Σn log, ((0)] we can derive that
if 0
[h. rr
(s
if > 0
Therefore, derive that the distance ratio der(asr dcr(ow((a). satisfies that g [min( [),r) darla.))
For the dimensional case, simply give the inequalities and gaps of distance components in each dimension, and since the average operation preserves the inequalities, the dimensional case proved.
B. Experimental Details
We first report some common settings of leaf matching in all experiments. Specifically, the bifurcation number of the complete tree selected as 2. The epoch ratio to stop adding randomness is 0.8. The probability edge change the randomness-adden adding process is 0.2. Meanwhile, all the experiment results with variance are tested five times.
B.I. Data Efficiency of the CT space
I. PARAMETERS
We utilize the official implementation of node2vec, node2ket, and poincare to test their performance. Here's 's the hyperpa- rameter settings for these algorithms five datasets:
14

---

Complete- Tree Space Favors Data-Efficient Link Prediction
In general, perform grid search to systematically adjust the parameters of all models. The embedding dimensions set 16 for all models for fair comparison (For node2ket, it is the dimension of sub-embeddings that is set to 16). Other hyperparameters are set as default in their original official implementations except for the following adjustments for performance improvement:
For node2ket in Cora, Citeseer, Pubmed, and ICEWS18,, we increase the number of sub-embeddiing C' for each node from 8 to 16, the learning rate p from 0.1 to 1.25 and decrease the number of iterations from 100M to 50M, For ogbl-collab, C' increased 32, p is increased to 1.6 and the number of iterations is decreased to 50M.
For poincare in Cora, Citeseer, Pubmed, and ICEWS18, increase the batch size from 64 and the learning rate from 0.001 to 0.01. For ogbl-collab, the batch size is further increased to 256 but the learning rate is set back to 0.001 for convergence of the loss.
For node2vec, no adjustments were made to the original parameters.
For leaf matching, in Cora, Citeseer and Pubmed, we set / = =, 1, 1, = 0.8, training it with batch size 256 on 50 epochs. For ICEWS18, we set size 32 on 50 epochs. For ogbl-collab, we set h 16, 7 3, 57, 3, 1.re 0.8, training it with batch size 256 on 50 epochs.
3, 33 1, 1, 0.8, training it with batch
1.1.2. DATASETS
We utilize the link prediction data wrapper from CogDL. (Cen et al., 2023) to split the training and testing data. Here we show how the dataset statistics changes with the link observability μ for cora, pubmed, citeseer, ogbl-collab, and icews 88:
CORA
PUBMED
CITESTUR
20000
X-60-
St ldgg
Ammberol IMgr
6060-
Toii Fat
Trai
Tinin
Text
Text
4060
40000
Text
3000
Twen Neg
2000-
2660
2000
1060
Obaraiity
1000
2000
17500
1060
1510
2500
Nurthe
COLLAD
JCDWS118
Thale Sa
"Taae
Text
2.6
Suntee
1.0
-35
3.0
100.00
120000
190900
19000
190000
200300
231006
240913
106e0
1250)
1500
1739)
23900
22500
Numbar
Nodks
Figure f.. It is shown that the number of test edges has unimodal distribution when link observability changes. This phenomenon is caused by fact that some nodes are removed from test set they have no links in the filtered training set.
1.3. EXTRA RESULTS
Reults on other metrics (ROC-AUC, PR-AUC, FI) for Cora, Citeseer, Pubmed and ICEWS18 are shown below in Figure 12, 13, 14, 15. The full visualization results are shown Figure 16.
15

---

Complete- Tree Space Favors Data-Efficient Link Prediction
CORA
ROC-AUC (90)
60-
PR. (54)
65
40-
401
redeSvee (Brclldonn)
60-
(1ilhert)
55
porzcare (Pypertolic)
50-
Complete-Tan
20
20
0.9
0.3
6.2
0.1
0.9
0.7
0.2
0.1
0.8
6.7
0.
0.1
Link Oiservability
Link Observ ahiiery
Link Observability
Figure 12. ROC-AUC, PR-AUC and F1 score of the network embeddings on Cora presented, with link observability μ decreasing from 0.9 0.1. Experiments are run times.
CITESEER
85
ROC-AUC (96)
(%6)
60
75-
60
30-
50-
50-
vedeives (Euolideaa)
40-
(lilber))
pertzano (1(perhulic)
(Complete Tree)
0.9
0.8
0.7
de
05
0.4
0.3
0.3
0.1
0.9
0.8
0.7
0.5 Link Observability
0.6
0..4
0.3
0.2
9.1
0.9
0.8
0.7
06
0.3
0.4
0.5
03
61
Link Observability
Link Observability
Figure 13. ROC-AUC, PR-AUC and score of the network embeddings on Citeseer are presented, with link observability decreasing from 0.9 0.1. Experiments are times.
PUBMED
90-
80
PR. (%))
60-
ROC-AUC
60-
75
50-
F1
70-
(Boxildea))
modelket (1Ebhet)
(boptooli
30-
ouss CCmplete Treo)
20
0'a
02
Link Observability
Link Observability
Link Observabiility
Figure 14. ROC-AUC, PR-AUC and F1 of the network emheddings on Pubmed are presented, with link observability j decreasing from 0.9 to 0.1. Experiments are run 5 times.
16

---

Complete- Tree Space Favors Data-Efficient Link Prediction
ICEWS18
100
95
95-
85-
ROC-AUC (90)
99-
PR-AUC (%)
85
85-
80-
modelvee (Euch)lcan)
modelber (Hiibbr
paincce (ltyazhulie)
65
our Complau--ree)
60
09
08
0.5
0.2
6.
Link Observability
Link Observability
Link Observability
Figure ROC-AUC, PR-AUC and F1 score of network embeddings on ICEWS18 are presented, with link observability f decreasing from 0.9 0.1. Experiments are run 3 times.
Cora
Citeseer
Pubmed
Shortest path distance (normalized)
CT space distance (degree corrected)
Shortest path distance (normalized)
CT space distance (degree corrected)
Shortest-path distance (normalized)
CT space distance (degree corrected)
Jl = 0.2
11 0.4
# = 0.6
11 0.8
Figure 16. Distance matrices of Cora, Citeseer, and Pubmed are presented of nodes with the maximal degree, with link observability decreasing from 0.8
17

---

Complete- Tree Space Favors Data-Efficient Link Prediction
B.2. Practicality
B.2.1. MODELS
We utilize the official implementations LPFormer (Shomer et al., 2024), GAE (Kipf & Welling, 2016), and SEAL (Zhang & Chen, 2018) provided in HeaRT (Li et al., 2023) to evaluate performance on the ogbl-ppa and ogbl-collab datasets. The parameter settings for LPFormer are not changed. For SEAL, in addition to the original parameter settings, we set the number of training epochs to 100 and the evaluation step to 1. For GAE, since there are official scripts for ogbl-collab and ogbl-ppa, we adopt the settings used for the PubMed dataset as default. Similarly, we set the number of epochs to 100 and the evaluation step to 1.
16, e 3, = 3: Te = 0.9 in oghl-collab. In ogbl-ppa, we set 7 7 a 85, n 32, c = 1,> 1,re 1.0. Both of them are trained with batch size of 512, using 100 epochs for ogbl-collab and 20 epochs for ogbl-ppa.
For leaf matching, we set h 16, = 2.,
Because there's s no validation set in the setting of CogDI. (Cen et al., 2023), we use the following policy to judge whether neural network is converged. After applying Gaussian smoothing to the loss curve, we define the convergence point as the moment when the current loss Leur first satisfies:
(L10% - Leur) > Leur Leuin
(8)
10
In other words, consider the neural network to have converged when the relative improvement in loss since the 10th percentile epoch exceeds ten times the gap between the current loss and the minimum loss.
Table 3. Heuristic methods for link prediction. (x) denotes the set of neighbors of node For the Katz index, P(x, y, represents the set of all possible paths between nodes æ and y of length
Method
Scoring Function
Common Neighbors
(N(()) n (v)
Preferential Attachment
[N(x]] ((=))-\N[>))
Jaccard's Coefficient
N(r)N(()
M
Adamic Adar
EzEN(E)NN())) log M+)
Resource Allocation
ELEN(UYN(()) [Nl
Katz index
Bt (P(x,
Heuristic methods predict missing links by first applying scoring functions S(x, y) to pairs of nodes, and then comparing the scores of different links to make judgment. As illustrated in Table 3, the six heuristic methods used in this study can be categorized based on the type of neighbor information they utilize.
First-Order Method: Common Neighbors (Newman, 2001), Preferential Attachment (Barabási et al., 1999), and Jaccard's Coefficient (Jaccard, 1901) rely solely on first-order neighbor information. These methods evaluate the immediate neighbors of nodes x and y.
2. Second-Order Method:
The Adamic Adar (Adamic & Adar, 2003) and Resource Allocation (Zhou al., 2009) employ second-order neighbor information, calculating weighted sum based on the properties of their common neighbors.
3. Global Structure Method: The Katz Index (Katz, 1953) calculates a weighted sum of all possible paths between two nodes, which can be exponentially numerous. To manage this complexity, we approximate the Katz Index by limiting the path length to (essentially making it a 'third-order' method), represented as Σ/= 8e. P y, E)}. where we set 0.005 and 3, consistent with the approach used HeaRT (Li al., 2023).
18

---

Complete- Tree Space Favors Data-Efficient Link Prediction
B.2.2. DATASETS
For the two datasets ogbl-collab and ogbl-ppa, we utilize the link prediction data wrapper from CogDL (Cen et al., 2023) to split the training and test data. Besides the default setting, we link observability μ 0.02. Note that certain nodes from the test set are excluded if they lack links in the filtered training set. Here's the information about the two datasets used in our setting:
Table 4. Dataset statistics for oph and ogbl-collab where the link observability = 0.02 over the whole dataset. The numher of negative edges is times the positive edges in the testing as default setting in CogDL.
Statistic
ogbl-ppa
ogbl-collab
Original Nodes Edges
576,289 30,326,273
235,868
1,285,465
Training Nodes & Edges
160 & 424,639
31,107 & 19,353
Testing Pos. Edges
14,753,580
117,541
Testing Neg. Edges
73,767,900
587,705
Training Edges/ Testing Edges
0.03
0.16
B.3. Scalability
For synthetic data, the ER network is generated randomly with link probability p= [V7 where |V] here denotes the number
5
of nodes. We use the default setting of leaf matching, and adjust & in each experiment to make n; = 2 equals [V. The convergence criterion is set to when the training loss is below 0.89. Such setting reasonable because 0.89 is generally the converging point of leaf matching over the ER networks of varying sizes. We repeatedly run the experiments five times and report the average converging epoch.
For real-world data, we partition the training edges in ogbl-collab into subsets containing 1, 1/1/2.... 1/64 64 of the total edges. For each subset, we conduct five training runs, calculate the mean loss and smoothen the loss curve by the Gaussian Kernel. Convergence is determined when the relative decrease in loss for all subsequent epochs is no greater than 0.05% compared to the current epoch. Additionally, the randomness technique used in neighbor selection is always kept (or Te = 1.0) to consistently assess convergence. The fitting curve is log-log curve formulated by y = a log (3 (3log (7æ + c) + b) + a, where 3, represent the number of nodes and the convergence epoch. Specifically, 20.97, 3 22.07, 7 7.02 10-1,c- -5.54, b 10, a 62.04.
B.4. Run-time Comparison
We evaluate the per-epoch training time of our algorithm and other neural network models on the ogbl-collab and ogbl-ppa datasets where μ 0.02, with the batch size fixed at 512. For SEAL ogbl-collab, the reported runtime excludes the time required for subgraph dataset construction. On ogbl-ppa, SEAL encounters an oft-of-memory (OOM) error, constructing the subgraph dataset requires excessive memory (on the order of terabytes).
GAF is typically infeasible for training on the ogbl series datasets due to the need to reconstruct the entire adjacency matrix, which is prohibitive given the large number nodes (over hundreds of thousands). To address this, we employ a block-wise reconstruction strategy for the adjacency matrix, enabling training without affecting the loss. However, this approach results in increased training time. The block size is set 2048, meaning that each step, we reconstruct adjacency matrix of size (N, 2048) where N is the number of nodes.
B.5. Ablation Studies
It can be seen from Figure 17 that (1) leaf matching remains robust on the three datasets with varying hyperparameters: (2) space dimension has significant influence on the performance of leaf matching, as long it is not too small (above 8); (3) leaf matching achieves its best performance when the leaf number (b* approximates the number of nodes in the graph.
19

---

Completc- Tree Space Favors Data-EMficiett Link Prediction
ROC-AUC Tree Layer
ROC-AUC Dimension
cora
Ctartor
76
Pubmed
74
74
ROCAUC (%)
72
72
ROC-AUC
68
60
66
66
9
13
17
21
25
4
12
16
20
24
Layer
ROC-AUC Alpha
ROC-AUC Gamma
75
74
74
ROC-AUC (%)
RDC AUC (%)
72
70
70
68
12
16 Alpha
32
Figure 17. The ROC-AUC score with varying parameters the three datasets.
20


Reviews:
[{"review_id": "BW6Vva0sqK", "reviewer": "Reviewer_cq4E", "summary": "This paper explores the challenge of link prediction in data-scarce networks by introducing the CT space, a discrete metric space that formalizes hierarchical modularity in networks. The authors leverage group theory to prove that the CT space provides a lower bound on sample complexity compared to Euclidean space. Subsequently, they propose Leaf Matching, a network embedding approach optimized for CT space, which outperforms existing models like graph transformers in data-scarce scenarios. Experiments validate the superiority of CT space over Euclidean, hyperbolic, and Hilbert spaces.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer for spending valuable time reviewing our manuscript and providing insightful comments. We have improved our paper accordingly and our responses are as below.\n\nQ1: **Scalability** ‘…does not provide detailed runtime comparison baselines; explanations and analyses of scalability’\n\nA1: We have added a **detailed runtime comparison experiment** between leaf matching and neural network baselines, as shown in https://anonymous.4open.science/r/Figures-58B7/Runtime.jpg. It can be seen that leaf matching is time-efficient. Analyses: each point in the $n$ dimensional CT space can be represented by an **integer vector**; we generally choose $b=2$ for leaf matching, so that **bit operations** can be implemented to accelerate both distance computations in the complete-tree space and edge samplings for the computation graphs.\n\nWe have also added an **epoch convergence experiment** on the real-world ogbl-collab dataset as shown in https://anonymous.4open.science/r/Figures-58B7/Scalability.png, representing even better scaling than on synthesized graphs. Analyses: this is because leaf matching is optimized on a specific computation graph guaranteeing **polylogarithmic time complexity** for navigation between arbitrary pairs of nodes using a **greedy strategy** [1-2].\n\nQ2: **Consistency** ‘…the authors should apply a consistent setting across these datasets’\n\nA2: We have **added ogbl-collab and ICEWS18** (a temporally growing graph selected following the suggestion of Reviewer yGLm) to the space comparison experiment, which is shown in https://anonymous.4open.science/r/Figures-58B7/Ogbl-collab.jpg and https://anonymous.4open.science/r/Figures-58B7/Temporal%20Graph.png. It can be seen that the complete-tree space maintains more data-efficient than other spaces on both datasets. We conduct the practicality experiment only on the ogbl datasets because $\\mu=0.02$ will lead to graph collapse on the three smaller datasets.\n\nQ3: **Ablation** ‘…A high link observability $\\mu=0.9$ is chosen, which seems unreasonable; …the results are reported only on the Cora, which is insufficient; explanations and analyses of ablation studies’\n\nA3: As suggested, we have altered $\\mu$ from $0.9$ to $0.1$ and added experiments on the Citeseer and PubMed datasets; we have also added experiments regarding hyperparameters of $\\alpha$ and $\\gamma$. The added ablation studies are shown in https://anonymous.4open.science/r/Figures-58B7/Ablation.jpg. The added analysis: it can be seen that (1) leaf matching remains robust on the three datasets with varying hyperparameters; (2) space dimension has no significant influence on the performance of leaf matching, as long as it is not too small (above 8); (3) leaf matching achieves its best performance when the leaf number ($b^{k-1}$) approximates the number of nodes in the graph. \n\nQ4:**Interpretability** ‘Referring to Figures 7, 10, and 11, the proposed method performs worse than the baselines at higher link observability. Can you provide more explanation?’\n\nA4: The false prediction cases of leaf matching are mainly caused by its **structural prior that sharpens the hierarchical modularity structures**, as shown in the **added visualization experiment**: https://anonymous.4open.science/r/Figures-58B7/Hierarchical%20Modularity.jpg.\n\nQ5: **Space Comparison** ‘Consider adding a summary table comparing CT space with alternative metric spaces to highlight its advantages concisely’\n\nA5: We greatly appreciate the reviewer for such an outstanding suggestion! The added table is as below:\n\n| Efficiency of Metric Spaces | Data | Time | Space |\n|----------------------------|------|------|-------|\n| **Complete-Tree Space**     | ✓    | ✓    | ✓     |\n| **Hilbert Space**           |      | ✓    | ✓     |\n| **Hyperbolic Space**        |      |      | ✓     |\n| **Euclidean Space**         |      | ✓    |       |\n\n*Table: While data efficiency depends on the size of the hypothesis space, time efficiency depends on whether there exists an optimization algorithm with time complexity sub-quadratic to the number of nodes, and space efficiency depends on whether the typical vector dimension is around tens instead of hundreds.*\n\nQ6: **Clerical Errors** ‘→ The CT space fully captures; → choosing $v$ ordered elements from $m_1$ distinct elements.’\n\nA6: Thanks for the kind reminder. We have corrected these two clerical errors accordingly.\n\nOnce again, we would like to express our gratitude to the reviewer for the valuable feedback, which has helped us further improve our manuscript.\n\nReference\n\n[1] Kleinberg, Jon. \"Small-world phenomena and the dynamics of information.\" Advances in neural information processing systems 14 (2001).\n\n[2] Kleinberg, Jon. \"Complex networks and decentralized search algorithms.\" Proceedings of the International Congress of Mathematicians (ICM). Vol. 3. European Mathematical Society, Zurich, Switzerland, 2006.", "claims_and_evidence": "Yes. For the link prediction problem in data-scarce environments, the paper introduces a novel metric space (CT space) and its optimization method (Leaf Matching) to address the limitations of existing approaches, including poor generalization under insufficient samples, high computational costs, and difficulty in handling hierarchical modular networks.", "methods_and_evaluation_criteria": "Yes. The proposed methods make sense for the problem of link prediction in data-scarce environments.", "theoretical_claims": "Yes. The CT space provides a theoretically grounded metric space that captures hierarchical modularity.", "experimental_designs_or_analyses": "Further experiments are needed to demonstrate the effectiveness of the method:\n- The paper claims that Leaf Matching scales as O(log n) but does not provide detailed runtime comparison baselines.\n- Why does the experiment on link observability u decreasing from 0.9 to 0.1 only use the citation networks Cora, Citeseer, and PubMed, while the experiment at u = 0.02 is conducted on OGBL-COLLAB and OGBL-PPA? To demonstrate the generalization of the model, the authors should apply a consistent setting across these datasets.\n- The ablation study seems more like a hyperparameter experiment. A high link observability u = 0.9 is chosen, which seems unreasonable because the authors claim the effectiveness of the proposed method in low link observability settings. Additionally, the results are reported only on the Cora, which is insufficient to demonstrate the method’s effectiveness on other domain datasets.\n- The experimental section lacks explanations and analyses of scalability and ablation studies, only reporting the results.\n- Referring to Figures 7, 10, and 11, the proposed method performs worse than the baselines at higher link observability. Can you provide more explanation?", "relation_to_broader_scientific_literature": "The contributions of this paper are related to prior work in metric space embeddings for graphs, low-data link prediction, and hierarchical modularity in networks.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Although the proposed method has theoretical support, which is welcomed, the experimental section should be further improved. For specific weaknesses, please refer to Experimental Designs or Analyses.", "other_comments_or_suggestions": "- Consider adding a summary table comparing CT space with alternative metric spaces to highlight its advantages concisely.\n- “The CT space fully capture” → “The CT space fully captures”\n- “choosing v ordered elements from m1 distinct elements..” → ”choosing v ordered elements from m1 distinct elements.”", "questions_for_authors": "Please see the weaknesses.", "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": "VHj5IIwanb", "reviewer": "Reviewer_fkGt", "summary": "This paper proposes a Complete-Tree based approach to explore the hierarchical structure of graphs such that the sample complexity for link prediction can be improved. The key idea is to develop a (hierarchical) complete tree to model the node distance in graphs, and utilize leaf matching to embed nodes into the tree, based on which the link probability can be computed. Experiments demonstrate the effectiveness and scalability.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer’s time and insightful comments. Our justifications and improvements are as below.\n\nW1: **Hierarchical Evidence**: **Numerous existing studies have empirically verified** hierarchical modularity in many important real-world networks: metabolic [1], customer purchasing [2], genetic regulatory or interaction [3-4], social [5], scientific collaboration [6], anatomical or functional brain networks [7], the Internet [8], etc. We have also added a **visualization experiment** to demonstrate the hierarchical modularity in three real-world datasets (see https://anonymous.4open.science/r/Figures-58B7/Hierarchical%20Modularity.jpg).\n\nW2: **Real-World Performance/Scalability**: Leaf matching has **excellent performance over real-world networks**. This is theoretically validated in Theory 4.7 and empirically verified in Sec 6.2-6.3. Briefly speaking, a subspace in the **complete-tree space** can well approximate the **arbitrary-tree space** and therefore guarantees good generalization. For further demonstration, we have added **ogbl-collab and ICEWS18** (a temporally growing graph selected following the suggestion of Reviewer yGLm) to the space comparison experiments (see https://anonymous.4open.science/r/Figures-58B7/Ogbl-collab.jpg and https://anonymous.4open.science/r/Figures-58B7/Temporal%20Graph.png). It is shown that the complete-tree space remains more data-efficient than other spaces on the million-scale real-world datasets. We have also conducted a **new scaling experiment** on the real-world ogbl-collab dataset using the $\\log{10}$ scale, as shown in https://anonymous.4open.science/r/Figures-58B7/Scalability.png, representing even better scaling than on synthesized graphs. \n\nW3: **Heterophilic/Inductive/Features**: Our main focus is demonstrating **complete-tree space superiority over other spaces** for data-efficient link prediction, which we have verified theoretically, algorithmically, and experimentally. For these extended capabilities, the Euclidean-space adaptations [9-11] suggest promising directions for future complete-tree-space extensions, such as developing graph neural networks in the complete-tree space. \n\nW4: **GNN Comparisons**: We have added 4 GNN (suggested by Reviewer yGLm) and 6 heuristic baselines (suggested by Reviewer RBEo, yGLm) to the practicality experiment (see https://anonymous.4open.science/r/Figures-58B7/Practicality.png). Leaf matching remains competitive. \n\nQ1: **Symmetry Measure**: We define the **submetry group** in Definition 4.1 as the set of maps that maintains all pair-wise distances in a finite metric space, where these maps originate from a **subset** of points and extend to the entire set of points in the metric space. Notably, the larger the order of the submetry group, the more locally symmetric the metric space is.\n\nQ2: **Directed Graphs**: Probably yes in that (1) successful embeddings have been developed in the ‘symmetric’ Euclidean space [12-13] by modifying the loss function; (2) The exact formulas suggesting our loss function modifications have already been introduced by physicists in the field of complex networks in [14]. We leave such an extension to future work.\n\nQ3: **Tree Determination**: **No search is needed in selecting the optimal tree**. Instead, we empirically find that simply choosing the bifurcation number to be $b=2$ and the tree layer $k$ to enable $b^{k-1}=v$ is enough for leaf matching to perform well on real-world networks. \n\nQ4: **Cluster Comparison**: Key difference: **the complete-tree structure is pre-determined instead of data-driven**, so that the hypothesis space size is greatly reduced to enable data-efficient link prediction (clarified in Related Work).\n\nQ5: **l(a), l(b)**: Both imply a point in the $n$ dimensional complete-tree space, representable by an $n$ dimensional integer vector, with distances calculated through bit operations ($b=2$ default). \n\nQ6: **Eq.4 Justification**: Modified from [15-16], with a log term to match the exponentially growing neighborhood size of points in the complete-tree space. Optimal as loss nears zero in practice. Gamma implies the clustering coefficient [16] or inverse of temperature [15], which is unique to each type of complex network [16]. Alpha is simply selected so that the loss is balanced between positive and negative samples, analytically calculable [14] when the network is scale-free.\n\nQ7: **Ablation**: We have added experiments regarding $\\alpha$ and $\\gamma$ with $\\mu=0.1$, as well as on the Citeseer and PubMed datasets besides Cora (see https://anonymous.4open.science/r/Figures-58B7/Ablation.jpg). It can be seen that leaf matching remains robust with varying hyperparameters.\n\nQ8: **Template**: We apologize for this oversight.\n\nOnce again, we would like to express our gratitude to the reviewer for the valuable feedback.\n\nReference: https://anonymous.4open.science/r/Figures-58B7/Reference2.png", "claims_and_evidence": "Yes, claims are clearly stated with proofs given.", "methods_and_evaluation_criteria": "Yes, the method explores the hierarchical structure in graphs to improve the scalability, and the evaluation criteria makes sense.", "theoretical_claims": "I checked the theorems in the paper but didn’t not review the details of the proofs.", "experimental_designs_or_analyses": "Yes. The method is tested on benchmark ogb datasets and the analyses are valid. However, more baseline methods (e.g., GNN-based methods) should be included, and more datasets (e.g., heterophilic graphs) should be considerd.", "relation_to_broader_scientific_literature": "Yes", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "(1)\tThe method is based on two assumptions: First, graphs exhibit hierarchical structures, and second, link probability is negatively related to the node representation distance. However, (First) though hierarchical structure clearly exhibit in synthetic graphs like CSBM, it is not clear how such ideal hierarchical structure exhibit in real-world graphs; (Second)the assumption on the relationship between link probability and node representation may not be applicable to heterophilic graphs.\n(2)\tThe link prediction results are largely determined by the pre-defined features, e.g., CT, degree, node distances, etc. The proposed method may only be applicable to transductive settings but may not be applicable to inductive settings?\n(3)\tThe proposed method can not incorporate node features into consideration.\n(4)\tExperiments: comparison with **more recent** GNN-based models should be included.", "other_comments_or_suggestions": "See questions", "questions_for_authors": "(1)\tPage 2 “Our key insight is that the hierarchically modular structure can still be detected even with low link observability, as shown in Figure 1”: Is there any empirical evidence to show the hierarchical structure exhibits in real-world graphs? Besides, the tree of real-world graphs may not be so ideal/balanced compared to synthetic graphs, will this affect the performance/scalability?\n(2)\tSection 4.1 Line 4-8: How do you measure the symmetry of the metric space? Can the proposed analysis generalizes to metric spaces that are not symmetric, e.g., directed graphs?\n(3)\tDef. 4.3: Is the complete tree spae determined once the graph is given? If a unique CT is not determineed, how to find the optimal tree? In general, the CT tree is somehow related to hierarchical graph clustering where graph clsuters (close nodes) at different levels are discovered. How do you compare the CT-based approach to other graph cluster approach? What are $l^{(a)}, l^{(b)}$ here?\n(4)\tEq.(4): What’s the intuition? How to justify such formulation is (sub)optimal? How to choose alpha and gamma?\n(5)\tExperiments: more ablation/parameter studies should be included, e.g., effect of alpha, gamma; more baselines; more datasets.\n(6)\tFig. 8: Maybe better to have x-axis as log10(number of nodes)\n(7)\tThe template for this submission seems to be incorrect, as there’s no line number to refer to.", "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": "JhjM9weuz4", "reviewer": "Reviewer_RBEo", "summary": "This paper addresses the understudied problem of link prediction when only sparse links are available. It proposes studying the complete tree space (CT), which offers a significantly lower bound on sample complexity compared to the commonly used Euclidean space. Building on this, the authors introduce leaf matching, a data-efficient network embedding that maps nodes onto the CT space and conducts discrete optimization by reducing it to decentralized search.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer for spending valuable time reviewing our manuscript and providing insightful comments. We have improved our paper accordingly and our responses are as below.\n\nQ1: **Practical Use Case**: ‘it would be beneficial to include practical use cases illustrating scenarios where sparse links are common’\n\nA1: Key applications where sparse link prediction is crucial: (1) **scientific collaboration recommendation** [1-2]; (2) prediction of human protein interactomes ($89 \\\\%-98 \\\\%$ unverified [3]); (3) other important real-world networks such as mutualistic networks [4], large social networks [5], and Wikipedia networks [6] have also demonstrated a higher prevalence of unobserved links compared to observed ones. We have integrated this discussion to the Practicality Experiment section. \n\nQ2: **Dataset Consistency**: ‘the authors conduct CT space experiments on the first three datasets and leaf matching experiments on the last two, which seems like cherry-picking. It would be helpful if the authors could provide justification for this approach’\n\nA2: We appreciate this important observation and have **added ogbl-collab and ICEWS18** (a temporally growing graph selected following the suggestion of Reviewer yGLm) to the space comparison experiment, which is shown in https://anonymous.4open.science/r/Figures-58B7/Ogbl-collab.jpg and https://anonymous.4open.science/r/Figures-58B7/Temporal%20Graph.png. It can be seen that the complete-tree space maintains more data-efficent than other spaces on both datasets. We conduct the practicality experiment only on the ogbl datasets because $\\mu=0.02$ will lead to graph collapse on the three smaller datasets.\n\nQ3: **Traditional Baseline**: ‘It would be beneficial to compare the proposed methods with traditional link prediction algorithms like AA, Common Neighbors, and Jaccard Similarity to justify their effectiveness’\n\nA3: As suggested, we have added **6 heuristic and 4 GNN baselines** to the practicality experiment, as shown in https://anonymous.4open.science/r/Figures-58B7/Practicality.png. Leaf matching remains competitive. \n\nOnce again, we would like to express our gratitude to the reviewer for the valuable feedback, which has helped us further improve our manuscript.\n\nReference\n\n[1] Guo, Ying, and Xi Chen. \"Cross-domain scientific collaborations prediction using citation.\" 2013 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM 2013). IEEE, 2013.\n\n[2] Barabâsi, Albert-Laszlo, et al. \"Evolution of the social network of scientific collaborations.\" Physica A: Statistical mechanics and its applications 311.3-4 (2002): 590-614.\n\n[3] Dunham, Brandan, and Madhavi K. Ganapathiraju. \"Benchmark evaluation of protein–protein interaction prediction algorithms.\" Molecules 27.1 (2021): 41.\n\n[4] Olesen, Jens M., et al. \"Missing and forbidden links in mutualistic networks.\" Proceedings of the Royal Society B: Biological Sciences 278.1706 (2011): 725-732.\n\n[5] Hohwald, Heath, et al. \"Inferring unobservable inter-community links in large social networks.\" 2009 International Conference on Computational Science and Engineering. Vol. 4. IEEE, 2009.\n\n[6] Adafre, Sisay Fissaha, and Maarten de Rijke. \"Discovering missing links in Wikipedia.\" Proceedings of the 3rd international workshop on Link discovery. 2005.", "claims_and_evidence": "The claim that existing link prediction methods primarily focus on densely observed links and overlook cases with few links is valid. However, it would be beneficial to include practical use cases illustrating scenarios where sparse links are common.", "methods_and_evaluation_criteria": "The proposed method involves CT space, which loosens the bound on sample complexity compared to commonly used metrics. The leaf matching algorithm effectively maps node embeddings to the CT space.", "theoretical_claims": "I reviewed the proofs roughly and found them to be generally acceptable.", "experimental_designs_or_analyses": "The experiments appear valid, but there is room for improvement:\n1. The authors conduct CT space experiments on the first three datasets and leaf matching experiments on the last two, which seems like cherry-picking. It would be helpful if the authors could provide justification for this approach.\n2. It would be beneficial to compare the proposed methods with traditional link prediction algorithms like AA, Common Neighbors, and Jaccard Similarity to justify their effectiveness.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper is well written and easy to read.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "It is necessary to justify the effectiveness of the proposed CT and leaf matching algorithms by comparing them with traditional link prediction algorithms. Many GNN-based link prediction works have been found to perform worse than traditional algorithms in link prediction. A comparison would strengthen the paper's claims.", "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": "n7yKyPqLvd", "reviewer": "Reviewer_yGLm", "summary": "This paper studies the link prediction task under the scarce data scenario. In the real-world application, the observed links in the network are far fewer compared to the unobserved ones. However, current LP methods usually focus on scenarios where observed links are abundant. To solve the problem, this study applies the hierarchically modular structure as the prior of the underlying graph structure through a \"complete-tree\" metrics space. A leaf matching method is proposed to map the nodes onto the complete-tree space. The experiments compared to other network embedding methods show that leaf matching in complete-tree space can achieve significant results when link observability levels are low.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer for spending valuable time reviewing our manuscript and providing insightful comments. We have improved our paper accordingly and our responses are as below.\n\nQ1: **Hierarchical Modularity Detectability**: ‘the claim that \"hierarchically modular structure can still be detected even with low link observability\" in Introduction is not empirically validated…especially comparing the modular structure with different link observability $\\mu$’\n\nA1: We thank the reviewer for highlighting this point and have clarified our claim in the revised paper. Theoretically, low link observability preserves hierarchical modularity because subsampling a stable distribution retains its statistical properties. To empirically validate this, we have added a **visualization experiment** for Cora, Citeseer, and Pubmed, as shown in https://anonymous.4open.science/r/Figures-58B7/Hierarchical%20Modularity.jpg. We can see that (1) hierarchical modularity persists even at low link observability; (2) leaf matching in the complete-tree space can well recover or even sharpen such a structure across the three datasets.\n\nQ2: **Temporally Growing Graph**: ‘Authors can consider benchmarking the proposed leaf matching on graphs with temporal information on graph edges to better select the \"observed\" vs \"unobserved\" edges’\n\nA2: This is a great suggestion. Since benchmark datasets for link prediction generally do not include elaborate temporal information, we have conducted **new experiments on the ICEWS18 dataset** from the domain of temporal knowledge graph, treating entities as nodes and relationships as edges. Results in https://anonymous.4open.science/r/Figures-58B7/Temporal%20Graph.png show that the complete-tree space significantly outperforms other spaces on this graph.\n\nQ3: ** Baselines**: ‘More baselines should be considered in the region of low link observability’\n\nA3: As suggested, we have added **6 heuristic and 4 GNN baselines** to the practicality experiment (see https://anonymous.4open.science/r/Figures-58B7/Practicality.png). Leaf matching remains competitive. \n\nQ4: **Link Observability Settings**: ‘In experiments, why choose$\\mu=0.9$ to $0.1$ for Cora, Citeseer, Pubmed, but go aggressively on Collab and PPA with only $\\mu=0.02$?’\n\nA4: We regard $\\mu=0.02$ as an **extremely difficult setting with practical meanings**, as around $89 \\\\% - 98 \\\\%$ human binary protein interactomes are still not verified [1]. Higher $\\mu$ naturally favors data-hungry neural networks over embedding methods. We emphasize that this work lays the foundation for future complete-tree-space neural networks, by theoretically, algorithmically, and experimentally demonstrating the data-efficiency of complete-tree space over other spaces.\n\nQ5: **OGBL for Space Comparison**: ‘Can authors show a similar results for OGB datasets like Figure 7 when varying $\\mu$?’\n\nA5: We have **added ogbl-collab** to the space comparison experiments (see https://anonymous.4open.science/r/Figures-58B7/Ogbl-collab.jpg). We can see that the complete-tree space consistently excels. \n\nOnce again, we would like to express our gratitude to the reviewer for the valuable feedback, which has helped us further improve our manuscript.\n\nReference\n\n[1] Dunham, Brandan, and Madhavi K. Ganapathiraju. \"Benchmark evaluation of protein–protein interaction prediction algorithms.\" Molecules 27.1 (2021): 41.", "claims_and_evidence": "- The claims made in the paper are mostly well supported by the theoretical analysis.\n- However, the claim that \"hierarchically modular structure can still be detected even with low link observability\" in Introduction is not empirically validated. It will be more convincing if authors can empirically investigate how much of a hierarchically modular structure can be preserved in graph datasets from the experiment section, especially comparing the modular structure with different link observability $\\mu$.", "methods_and_evaluation_criteria": "- The method is well motivated to solve the problem at hand.\n- However, the selection of benchmark datasets can be improved. When changing the link observability rate, the edges to drop are random, which does not reflect the growing trajectory of the graph. Authors can consider benchmarking the proposed leaf matching on graphs with temporal information on graph edges to better select the \"observed\" vs \"unobserved\" edges.\n- More baselines should be considered in the region of low link observability. For example, heuristics link predictors like Common Neighbors, Resource Allocation, AdmicAdar Index, Katz Index, and Preferential Attachment should be included due to their strong baseline performance. GNN methods like GAE[1], SEAL[2] should also be discussed due to their wide adoption for LP tasks.\n\n[1] Variational Graph Auto-Encoders\n[2] Link Prediction Based on Graph Neural Networks", "theoretical_claims": "Theoretical Claims is solid.", "experimental_designs_or_analyses": "See \"Claims And Evidence\" part.", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "See above.", "other_comments_or_suggestions": "NA", "questions_for_authors": "- In experiments, why choose $\\mu=$0.9 to 0.1 for Cora, Citeseer, Pubmed, but go aggressively on Collab and PPA with only $\\mu=0.02$? Can authors show a similar results for OGB datasets like Figure 7 when varying $\\mu$?", "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": {"ethical_review_concerns": "NA"}}]

Author rebuttal:

Meta-review: The reviewers find that the approach provides a novel CT metric space as well as an associated Leaf Matching optimization procedure  providing a solid contribution with improved generalization that is theoretically justified. The reviewers generally also finds that claims are clearly stated with proofs given and substantiated by results. However, the reviewers also find that the experimentations could be improved in particular by including further baselines, datasets, and ablations.

The authors very carefully and meticulously in their rebuttals addressed the reviewers concerns also adding additional experimentations addressing concerns and providing further empirical evidence. The reviewers acknowledged the authors rebuttals and found the manuscript  suitable for publication at ICML.

The authors are strongly encouraged to include the additional experimentations and clarifications provided in their rebuttals in the final manuscript.
Decision: Accept (poster)