PHLP: Sole Persistent Homology for Link Prediction -- Interpretable Feature Extraction
Junwon You Eunwoo Heo Jae-Hun Jung






PHLP: Sole Persistent Homology for Link Prediction - Interpretable Feature Extraction
    
Junwon You, 
Eunwoo Heo,
Jae-Hun Jung
Junwon You and Eunwoo Heo are co-first authors.

Junwon You, Eunwoo Heo, and J.-H. Jung are with the Department of Mathematics, Pohang University of Science and Technology (POSTECH), Pohang, South Korea. 
J.-H. Jung is also with the Graduate School of Artificial Intelligence, POSTECH, Pohang, South Korea.

Preprint. Under review.
    
======================================================================================================================================================================================================================================================================================================================================================================================


Link prediction (LP), inferring the connectivity between nodes, is a significant research area in graph data, where a link represents essential information on relationships between nodes. 
Although graph neural network (GNN)-based models have achieved high performance in LP, understanding why they perform well is challenging because most comprise complex neural networks. 
We employ persistent homology (PH), a topological data analysis method that helps analyze the topological information of graphs, to explain the reasons for the high performance. 
We propose a novel method that employs PH for LP (PHLP) focusing on how the presence or absence of target links influences the overall topology. 
The PHLP utilizes the angle hop subgraph and new node labeling called degree double radius node labeling (Degree DRNL), distinguishing the information of graphs better than DRNL. Using only a classifier, PHLP performs similarly to state-of-the-art (SOTA) models on most benchmark datasets. 
Incorporating the outputs calculated using PHLP into the existing GNN-based SOTA models improves performance across all benchmark datasets. 
To the best of our knowledge, PHLP is the first method of applying PH to LP without GNNs. 
The proposed approach, employing PH while not relying on neural networks, enables the identification of crucial factors for improving performance.



Graph analysis, link prediction, persistent homology, topological data analysis.



§ INTRODUCTION


Graph data
pervade numerous domains such as social networks, biological systems, recommendation engines, and e-commerce networks <cit.>.
The graph is well-suited for modeling complex real-world relationships.

Predicting missing or potential connections within a graph is essential for many applications, unlocking valuable insight and facilitating intelligent decision-making. 
The ability to predict future network interactions can be applied to diverse domains, including friend recommendations on social networks <cit.>, knowledge graph completion <cit.>, identification of potential drug-protein interactions in bioinformatics <cit.>, prediction protein interactions <cit.>, and optimization of supply chain logistics <cit.>.

The link prediction (LP) problem has been categorized into three major paradigms: heuristic methods, embedding methods, and graph neural network (GNN)-based methods, which are explored in detail in Section <ref>.
Recently, compared to heuristic <cit.> and embedding methods <cit.>, GNN-based models have achieved significant score improvements in capturing intricate relationships within graphs <cit.>. 

However, GNN-based methods are comprised of neural networks, making it challenging to understand the reasons for their performance.
To explore these reasons, we employ persistent homology (PH), a mathematical tool in topological data analysis (TDA) that enables the inference of topological information regarding the manifold approximating the data <cit.> by quantifying the persistence of topological features across multiple scales.
Various research has had successful outcomes in applying PH to graph classification and node classification tasks <cit.>.
In contrast, relatively few studies have explored using PH for LP.
The topological loop-counting (TLC) GNN <cit.> is a notable example that uses PH.
The TLC-GNN injects topological information into a GNN, and experiments were conducted on benchmark data where node attributes are available.






In this context, as illustrated in Fig. <ref>, we present a novel approach to LP, called PHLP, which calculates the topological information of a graph.
To use the topological information of subgraphs for LP, we measure how the topological information changes depending on the existence of the target link, as illustrated in Fig. <ref>.
To extract topological information from various perspectives, we utilize angle hop subgraphs for each target node. 
Additionally, we propose new node labeling called degree double radius node labeling (Degree DRNL), which incorporates degree information for each node, using DRNL <cit.>.

The contributions are summarized as follows:

    
  * We develop an explainable LP method, PHLP, that employs the topological information for LP through PH without relying on neural networks, as illustrated in Fig. <ref>.
    
  * We demonstrate that the proposed method, even with a simple classifier such as a multilayer perceptron (MLP), can achieve LP performance close to that of state-of-the-art (SOTA) models.
    This method surpassed the SOTA performance for the Power dataset.
    
  * We reveal that merely incorporating vectors computed by PHLP into existing LP models, including SOTA models, can improve their performance.
    
  * To the best of our knowledge, the proposed method using PH without a GNN is the first to achieve performance close to that of SOTA models.



§ RELATED WORK




 §.§ Link Prediction


Heuristic Methods.
Heuristic-based approaches to LP compute the predefined structural features within the observed nodes and edges of the graph. 
Classic methods, such as common neighbors <cit.>, Adamic-Adar <cit.>, Jaccard coefficient <cit.>, and preferential attachment <cit.>, rely on simple heuristics that capture certain aspects of node relationships. 
Zhou et al. <cit.> proposed a local random walk method, whereas Jeh and Widom <cit.> developed SimRank to quantify similarity based on the structural context. 
Although heuristic methods provide a preliminary understanding of LP, they are limited by their inability to capture complex relationships within graphs.
Furthermore, heuristic methods are effective only when the defined heuristics align with the graph structure; therefore, applying heuristic methods across all graph datasets can be challenging.


Embedding Methods.
Embedding methods map nodes from the graph into a low-dimensional vector space where geometric relationships mirror the graph structure. 
Koren et al. <cit.> demonstrated the power of matrix factorization for collaborative filtering. 
Perozzi et al. <cit.> introduced DeepWalk, using random walks to generate node sequences and employing the skip-gram model to produce embeddings. 
Tang et al. <cit.> developed large-scale information network embedding (LINE), which preserves local and global structures. 
Grover and Leskovec <cit.> further advanced this approach with Node2Vec (N2V), proposing a flexible notion of the neighborhood to capture diverse node relationships.

Embedding methods are advantageous due to their applicability regardless of the data characteristics using optimization. Node representations capture global properties and long-range effects through the learning process. However, these methods often require significantly large dimensions to express basic heuristics, resulting in lower performance than heuristic methods <cit.>.
Moreover, in embedding methods, Ribeiro et al. <cit.> explained that two nodes with similar neighborhood structures may have vastly different embedded vectors, especially when they are far apart in the graph, leading to incorrect predictions.

GNN-Based Methods.
The GNN has become a pivotal approach to LP due to its ability to grasp graph-structured data. 
By effectively incorporating local and global information through message passing and graph aggregation layers, GNNs enhance LP performance.
The model by Zhang et el. <cit.> uses subgraphs as the primary structural units to learn and predict connections, resulting in significant improvement. 
This paradigm shift led to research focusing on refining and advancing subgraph methods in the context of GNNs <cit.>. 
Following this trend, Pan et al. <cit.> proposed WalkPool (WP), a new pooling mechanism that uses attention to jointly encode node representations and graph topology into learned topological features.
However, despite their superior performance, GNN-based methods pose a challenge in comprehending the underlying mechanisms driving their predictions.
Within this context,
we develop the PHLP, based on PH, with performance comparable to GNN-based models.



 §.§ Persistent Homology on Graph Data

In recent years, PH, a method of analyzing the topological features of data, has been widely used to analyze graph data. 
It has demonstrated its effectiveness in graph classification tasks by analyzing the topology of graphs <cit.> and has been applied to node classification tasks <cit.>. 
However, its suitability for LP tasks has been limited, and research on applying PH for LP has progressed slowly.
Yan et al. <cit.> proposed an intriguing approach by integrating PH with GNNs. 
While their model demonstrates the potential of PH for capturing topological features of graph data, it relies on GNN structures.
Additionally, the TLC-GNN requires further research on datasets without node attributes.

Although PH has demonstrated success in graph and node classification tasks, its filtration technique, tailored to analyzing the entire graph structure, might not be optimal for LP as the role of each node in LP differs from that in graph or node classification tasks. 
To address this challenge and advance research in LP, we develop a filtration method tailored explicitly to LP tasks.


§ METHOD



 §.§ Outline of the Proposed Methods



We propose (a) PHLP and (b) multiangle PHLP (MA-PHLP) as described in Fig. <ref>. 
The PHLP method analyzes the topological structure of the graph, focusing on target links.
First, PHLP samples a (k,l)-angle hop subgraph for the given target nodes (Section <ref>). 
Then, PHLP computes persistence images (PIs; Section <ref>) for cases with and without the target link. 
To calculate PIs, we introduce the node labeling and define the edge-weight function (Section <ref>).
Through PHLP, each target node is transformed into a vector comprising PIs.
In addition, LP is performed using the calculated vectors
with a classifier (Section <ref>). 
To reflect diverse topological information, we also propose MA-PHLP, which analyzes data from various angles (Section <ref>).




 §.§ Extracting Angle Hop Subgraph



Given a graph G = (V, E) and two nodes u,v ∈ V, a k-hop enclosing subgraph for (u,v) is defined as 𝒩^k_u,v = (V', E') such that 

    V'    = { z ∈ V | d(u, z) ≤ k  or  d(z, v) ≤ k}, 
    
        E'    = { (z, w) ∈ E | z ∈ V'  and  w ∈ V' },

where d(z, w) is the minimum number of edges in any path from z to w in G.
We define a (k,l)-angle hop enclosing subgraph, where the term “angle” signifies viewing the subgraph from multiple perspectives. 
The (k,l)-angle hop subgraph is a generalization of the k-hop subgraph. 
Given a graph G = (V, E) and two nodes u, v ∈ V, a (k,l)-angle hop enclosing subgraph for (u, v) is defined as 𝒩^(k,l)_u,v = (V', E') such that 

    V'    = { z ∈ V | d(u, z) ≤ k  or  d(z, v) ≤ l }, 
    
        E'    = { (z, w) ∈ E | z ∈ V'  and  w ∈ V' }.

Thus, the angle hop can generate subgraphs in various forms, providing flexibility to adapt to various graph characteristics.



 §.§ Filtration of the Subgraph



For a given subgraph, the Rips filtration <cit.> is employed to calculate the topology using PH. 
To apply the Rips filtration, we define an edge-weight function using node labeling that reflects the topology of the given graph. 





Degree DRNL.
Zhang et al. <cit.> introduced DRNL, which computes the distance from any node to two fixed nodes.
For any subgraph 𝒩=(V',E') of G and two nodes a,b ∈ V', the DRNL f^(a,b)_drnl: V' →ℕ based on (a,b) of G for any vertex w in V', is defined as

    f^(a,b)_drnl(w) = 1 + min(d(w,a), d(w,b)) + q_w(q_w + r_w - 1),

where q_w ∈ℤ and r_w ∈{ 0, 1} are integers representing the quotient and remainder, respectively, such that d(w,a)+d(w,b) = 2q_w + r_w. 
We call these two nodes, a and b, center nodes.
These center nodes do not need to be the target nodes used when extracting the subgraph.

However, DRNL encounters limitations when the graph is transformed into node-label information.
As depicted in Fig. <ref>, DRNL assigns the same node labels to different graphs, resulting in identical zero-dimensional PIs (Fig. <ref>, Section <ref>).
To incorporate the local topology of each node with the effects of DRNL, we introduced Degree DRNL. 
For a given subgraph 𝒩 = (V', E') of G and center nodes a,b ∈ V', the Degree DRNL f^(a,b)_degdrnl : V' →ℝ  based on (a,b), for all vertex w in V', is defined as

    f^(a,b)_degdrnl(w) = f^(a,b)_drnl(w) + M - (w)/M,

where M denotes the maximum degree of nodes in 𝒩.
The (M-(w))/M term above assigns larger values for lower degrees of w. When M = (w), the value of Degree DRNL matches the original DRNL, ensuring that the edges connected to nodes with higher degrees are assigned smaller values, promoting their earlier emergence in the filtration.
Fig. <ref> demonstrates various node labels obtained using Degree DRNL, resulting in PIs that can be distinguished from each other (Fig. <ref>). 


Edge-weight function. 
For a given subgraph 𝒩 = (V', E'), f : V' →ℕ denotes any node labeling function.
The edge-weight function W:E' →ℝ, for any edge (w, z) in E', is defined as 

    W(w,z) =max(f(w),f(z)) + min(f(w),f(z))/max(f(w),f(z)).

The min/max term in the definition of W refines values further, enhancing the discriminative power by reducing the occurrence of identical edge weights.




 §.§ Persistent Homology



Given an edge-weighted subgraph 𝒩 = (V', E', W), we construct a Rips filtration and compute its PH.
First, we create a sequence of subgraphs {𝒩_ϵ}_ϵ∈ℝ, where each 𝒩_ϵ = (V', E'_ϵ) and E'_ϵ= { e ∈ E | W(e) ≤ϵ}. 
Second, we convert each subgraph 𝒩_ϵ into the Rips complex 
K_ϵ = {τ∈𝕏| (w,z) ∈ E'_ϵ for any two vertices  w,z ∈τ}, where 𝕏 is the power set of V'. 
In K_ϵ, a simplex τ is formed when the vertices in τ are pairwise connected by edges in 𝒩_ϵ.
Then, the Rips filtration is obtained as  
K_ϵ_1↪ K_ϵ_2↪⋯↪ K_ϵ_m = 𝕏
for ϵ_1 ≤ϵ_2 ≤⋯≤ϵ_m.
Third, we compute the p-dimensional homology group H_p(K_ϵ) for each complex K_ϵ and track how these groups change as ϵ increases. 
The persistence diagram D <cit.> comprises
persistence pairs (b,d) representing the ϵ values at which a homological feature appears b and disappears d, respectively, in the filtration.



 §.§ Persistence Image



We convert the persistence diagram into a PI <cit.>. 
For a given persistence diagram D,
consider a linear transform L: ℝ^2 →ℝ^2 defined by L(x, y) = (x, y-x). 
The image set of D under this transformation is denoted as L(D). 
For each point (b,d') in L(D), a weight function ϕ_(b,d'): ℝ^2 →ℝ is defined that assigns a weight to each point in the persistence diagram. 
A common choice for ϕ_(b,d') is the Gaussian function centered at (b,d').
The nonnegative function is defined as h:ℝ^2 →ℝ, as h(x,y)=1/log(1+ | y |).
The function h is zero along the horizontal x-axis, and is continuous and piecewise differentiable, satisfying the conditions presented in <cit.>.
The persistence surface ρ_D:ℝ^2 →ℝ is defined as

    ρ_D(z) = ∑_(b,d') ∈ L(D) h(b,d')ϕ_(b,d')(z).


The continuous surface ρ_D is discretized into a finite-dimensional representation over a predefined grid. 
This grid consists of n cells, each corresponding to a specific region in the plane. 
The PI is defined as an array of values I(ρ_D)_p for each cell p. 
Each I(ρ_D)_p in this array is computed by integrating the persistence surface ρ_D over the area of cell p:

    I(ρ_D)_p  = ∬_pρ_D   dy   dx.




 §.§ Predicting the Existence of the Target Link


For the given target nodes (u,v), we sample the (k,l)-angle hop subgraph 𝒩^(k,l)_u,v, denoted as 𝒩^- (Section <ref>), assuming that the target link does not exist during this process. 
On this subgraph, we extract topological features by calculating PH and its vectorization (i.e., the PI, as described in Sections <ref> and <ref>). The vectorization is calculated for each dimension and concatenated. If k ≠ l, for symmetry, we repeat the same process with the (l,k)-angle hop subgraph once and consider the average of the two vectors, denoting this vector as x^-. 
To observe the difference in topological features, we consider a subgraph 𝒩+ obtained by connecting the target link to 𝒩^-.
For this graph, x^+ denotes the vector obtained using this method.

To predict the existence of the target link with the vectors x^- and x^+, we employ an MLP classifier Φ: ℝ^2(d+1)n^2→ℝ where n represents the resolution of the PI, and d denotes the maximal dimension of PH. 
The model predicts the existence of a link between two target nodes with the following probability: 

    z_uv = σ(Φ(x)),

where x is the concatenation of x^- and x^+, and σ is the activation function.
For the training dataset 𝒳⊆ V × V, comprising positive and negative links corresponding to the elements of E and (V× V)∖ E, respectively, we define the loss function as follows:

    ∑_(u,v) ∈𝒳 BCE(z_uv, y_uv),

where BCE(·,·) represents the binary cross-entropy loss and y_uv denotes the label of the target link (u,v), which is 0 for negative links or 1 for positive links.



 §.§ Multiangle PHLP


The MA-PHLP maximizes the advantages of PHLP by examining data from various angles through the extraction of subgraphs based on a hyperparameter, the maximum hop (max hop, denoted as H).
The types of angles are elements of all combinations of k and l within the set {(k,l) ∈ℤ^2 | 0 ≤ l ≤ k ≤ H, k > 0}.
If we define the prediction probability of a PHLP for each type of angle hop as z_i for i=1, 2, ..., N, then MA-PHLP predicts the likelihood of the link existence with the following probability: 

    p = ∑_i=1^N α_iz_i ,

where α = (α_1,...,α_N) ∈ℝ^N is a trainable parameter.
We apply the softmax function to the parameter α to ensure that the sum of all elements equals 1. 
Moreover, MA-PHLP is trained using the binary cross-entropy loss.



 §.§ Hybrid Method


The proposed approach easily integrates with existing subgraph methods. Subgraph methods treat the LP task as a binary classification problem comprising two components: a feature extractor F and classifier P. Vectors with PH information calculated using the proposed methods are incorporated through concatenation before the classifier.
The detailed process of the hybrid method is outlined as follows: 

    
  * Subgraph Extraction: For the given graph G and target nodes (u,v), k-hop subgraph 𝒩^k_u,v is extracted. 
    
  * Feature Extraction: Existing methods extract features Z = F(𝒩^k_u,v) from the subgraph.
    
  * Persistent Image Calculation: The methods described in Sections <ref>, <ref>, and <ref> are applied to 𝒩^k_u,v, where I denotes the PI vector. An MLP Φ:ℝ^m →ℝ^n transforms the PI into a format similar to Z. 
    For the hybrid method of MA-PHLP, 𝒩^k_u,v is replaced with multiangle subgraphs, concatenating their PI vectors.
    
  * Classification: Next, α_1 Z and α_2 Φ(I) are concatenated, where α_1 and α_2 are trainable parameters. The softmax function is applied to the parameter α=(α_1,α_2), ensuring that the sum of elements equals 1, denoted by J.
    This concatenated vector is classified using the existing method's classifier, P(J).



§ EXPERIMENTS

This section evaluates the performance of MA-PHLP. 
The experiments were also conducted using only zero-dimensional homology (MA-PHLP (dim0)).
We used the area under the curve (AUC) <cit.> as an evaluation metric. We repeated all experiments 10 times and reported the mean and standard deviation of the AUC values. 



 §.§ Experimental Settings


Baselines. To evaluate the effectiveness of PHLP, we compared the proposed model with five heuristic methods, four embedding-based methods, and two GNN-based models. The heuristic methods include the Adamic-Adar (AA) <cit.>, Katz index (Katz) <cit.>, PageRank (PR) <cit.>, Weisfeiler-Lehman graph kernel (WLK) <cit.>, and Weisfeiler-Lehman neural machine (WLNM) <cit.>. 
For the embedding-based methods, we applied N2V <cit.>, spectral clustering (SPC) <cit.>, matrix factorization (MF) <cit.>, and LINE <cit.>. Moreover, SEAL <cit.> and WP <cit.> represent the GNN-based methods. 

Datasets.

In line with previous studies <cit.> and <cit.>, we evaluate the performance of our MA-PHLP on the eight datasets in Table <ref> without node attributes: USAir <cit.>, NS <cit.>, PB <cit.>, Yeast <cit.>, C. elegans (C. ele) <cit.>, Power <cit.>, Router <cit.>, and E. coli <cit.>. 
The detailed statistics for each dataset are summarized in Table <ref>.

Implementation Details. 
All edges in the datasets were split into training, validation, and testing datasets with proportions of 0.85, 0.05, and 0.1, respectively, ensuring a fair comparison with previous studies.
The max hop M was set to 3 for most datasets (Table <ref>). 
However, for the E. coli dataset, it was reduced to 2 when employing one-dimensional homology due to memory constraints. 
Conversely, for the Power dataset, the max hop was set to 7 because it does not demand heavy memory and computation time.
The sigmoid function was employed for the activation function of the PHLP classifier.
Tables <ref> and <ref> present the results of the hybrid methods using SEAL <cit.> and WP <cit.>, respectively.
For these experiments, a two-layer MLP was used for the MLP Φ in Step 3 of Section <ref>. 
We set the k-hops following the original methods, SEAL and WP, and the max hops M of MA-PHLP were set as the k, except for the Power dataset.
For the Power dataset, we set the k-hop to 1-hop and max hop M to 7, respectively, which is discussed in detail in Section <ref>.





 §.§ Results

Results of MA-PHLP.
Table <ref> presents the AUC scores for each model on the benchmark datasets. 
Bold marks the best results, and underline indicates the second-best results.
The results of AA, Katz, WLK, WLNM, N2V, SPC, MF, LINE, and SEAL are copied from SEAL <cit.> for comparison. 
The MA-PHLP demonstrates high performance across most datasets, achieving competitive scores.
The proposed model outperforms several baselines, falling between the SEAL and WP models in terms of the AUC score. 
Notably, for the Power dataset, MA-PHLP achieves the highest AUC score, indicating its effectiveness in capturing link patterns.

Results of Hybrid Methods.

Simply concatenating the PI vector calculated using PHLP with the final output of the SEAL model increases AUC scores for all datasets, as listed in Table <ref>. This outcome suggests that when the SEAL model lacks topological information for inference, 
the vectors calculated using PHLP can serve as additional inputs.


Similarly, we attempted to hybridize PHLP with the current SOTA model, WP. 
As presented in Table <ref>, a slight increase in AUC scores is observed for all datasets. The Power dataset demonstrates significant improvement.




 §.§ Ablation Study

Effects of Degree DRNL. To assess the proposed Degree DRNL regarding the influence of incorporating degree information on model performance, we conducted experiments using DRNL and Degree DRNL and compared the results. 

We used MA-PHLP (dim0) for the experiments.
Table <ref> presents the AUC scores of MA-PHLP (dim0) with DRNL and Degree DRNL.
Across all datasets, MA-PHLP (dim0) yields higher AUC scores when used with Degree DRNL than with DRNL.
The substantial improvement observed in the Power dataset is noteworthy, where Degree DRNL yields an increase of over 4 points in the AUC score.
These experiments demonstrate the importance of incorporating degree information into node labeling, revealing its efficacy in enhancing the performance of MA-PHLP. 




Angles of PHLP. Table <ref> presents the performance of PHLP (dim 0) concerning various (k,l)-angle hop subgraphs.
Section <ref> proposed angle hop subgraphs as an alternative to traditional k-hop subgraphs to capture information from various perspectives. 
Moreover, MA-PHLP is proposed to aggregate information from multiple angles. 
To investigate performance when extracting information from specific angles, we conducted experiments using PHLP at different angles.
We used only zero-dimensional PIs for the experiments.
Overall, the results demonstrate that the performance is favorable for cases corresponding to the k-hop subgraph (where k and l are the same). 
However, some datasets perform better when k and l differ, highlighting the importance of varying angles to achieve the best performance. Therefore, using MA-PHLP is recommended to maximize performance consistently across datasets.


Comparison with TLC-GNN.
To demonstrate that the proposed method extracts superior topological information compared to the conventional TLC-GNN approach, we conducted the same experiments. 
The TLC-GNN was constructed by augmenting the graph convolutional network (GCN) model with PI information. 
We replaced the PI component of the TLC-GNN model with the PI vector produced by MA-PHLP, resulting in the MA-PHLP-GNN. 
The zero-dimensional PH was employed in this study for fair comparison because TLC-GNN used only zero-dimensional PH.
Additionally, we conducted experiments where the PH vectors were replaced with zero vectors, denoted as GCN. 
Table <ref> presents the experimental results.


The TLC-GNN is employed when the given data includes node attributes.
Hence, we conducted experiments using the following widely used benchmark datasets with node attributes: Cora <cit.>, CiteSeer <cit.>, and PubMed <cit.>. 
The MA-PHLP-GNN outperformed the TLC-GNN significantly on the CiteSeer and PubMed datasets while achieving similar performance on the Cora dataset. 
The TLC-GNN does not exhibit performance improvement for the PubMed dataset despite adding topological information. 
However, the proposed MA-PHLP-GNN demonstrates substantial performance enhancement.
Although the proposed model is developed for datasets without node attributes, it exhibits effective performance on datasets with node attributes through hybridization with the existing methods: SEAL+PHLP, WP+PHLP, and MA-PHLP-GNN. 
These experiments verify the versatility and effectiveness of this approach across diverse datasets.



 §.§ The hops and max hops of the hybrid methods





Determining the hyperparameters such as “hop" and “max hop" is crucial for the performance of the hybrid method. We conducted experiments to explore the effects of different combinations of these parameters. 
Given that the hybrid methods (e.g., MA-PHLP + SEAL and MA-PHLP + WP) exhibited the highest performance improvement on the Power dataset, 
we conducted experiments on the Power dataset.
Table <ref> presents the AUC scores for varying hop (SEAL or WP) and max hop (MA-PHLP).
For each target node, while the SEAL and WP extract a k-hop subgraph, the MA-PHLP calculates the PIs based on a subgraph with max hop M.
When the parameter M is 1 or 2, the AUC scores are not robust to k, showing large variations; however, when M is 3, although MA-PHLP + SEAL still exhibits variations up to 2, MA-PHLP + WP shows only minor variations.
As M exceeds 3, the AUC scores of MA-PHLP + SEAL and MA-PHLP + WP are robust to k, exhibiting little sensitivity (maximum 0.84) to variations.
This suggests that setting both the hop and the max hop to identical values may be permissible without further searching for optimal hyperparameters.







§ ANALYSIS




 §.§ Analysis of the PHLP


Figs. <ref> and <ref> visualize concatenated PIs to illustrate how MA-PHLP (dim0) extracts topological features for LP. 
We let 𝒵⊆ℝ^2 × k × r^2 be a set of vectors calculated by MA-PHLP, where k is the number of angles, and r denotes the PI resolution. 
For (z_1, z_2) ∈𝒵, z_1 ∈ℝ^k × r^2 is the concatenation of PIs for all angles with a target link, and z_2 ∈ℝ^k × r^2 is the concatenation for cases without a target link.
We consider a function h:ℝ^k × r^2→ℝ defined as 
h(v⃗_1, ..., v⃗_k) = 1/k∑_i=1^k ‖v⃗_i ‖_1, where v⃗_i ∈ℝ^r^2 are PIs, and ‖·‖_1 denotes the L_1-norm.
For visualization, we transform 𝒵 into points in ℝ^2 using the function G, defined as G(z_1,z_2) = (h(z_1),h(z_2)) for each (z_1, z_2) ∈𝒵. 

We plot distributions of points separately for positive and negative links, considering both DRNL and Degree DRNL.
The distributions of the NS and Yeast datasets between positive and negative links display significant differences, supporting the highest performance in Table <ref>.
In contrast, the distributions for the C. ele and Power datasets are the most similar when using Degree DRNL, correlating with the lowest scores in Table <ref>.



 §.§ Analysis of the Power Dataset

In most LP models, including the SOTA models SEAL and WP, the Power dataset tends to have the lowest AUC scores among the datasets. 
In Table <ref>, the Power dataset is at the bottom in terms of scores across models (e.g., WLK, WLNM, MF, LINE, SEAL, and WP).
However, the proposed model achieves the highest AUC scores on the Power dataset among baseline models, prompting an analysis of the reasons for this performance.

In Fig. <ref>, for DRNL, the Power dataset exhibits horizontal lines, indicating that the values h(z_2) have a limited range of outcomes for vectors z_2 in cases without the target link; thus, the set of values h(z_2) with the same value should be spread out.
This observation implies that, for numerous subgraphs the calculation of PIs yields similar outcomes despite the differences in their topological structures, posing a challenge in distinguishing between them.

To address this problem, we applied Degree DRNL, which incorporates degree information. 
The points in Fig. <ref> are distributed without horizontal lines, leading to the highest score increase, as listed in Table <ref>.

The performance of heuristic methods, such as AA, Katz, and PR, tend to be similar to random guessing on datasets with low density, particularly in the cases of the Power and Router datasets. 
Embedding methods also display low performance. 
In contrast, the GNN-based methods demonstrate improved performance using subgraphs and the network learning ability.
However, the performance for the Power dataset is significantly lower than that for the Router dataset. 



To bridge this gap, we analyzed subgraphs with node labeling. 
The number of nodes within the selected subgraphs between positive and negative links was significantly different on the Router dataset but not the Power dataset (Table <ref>). 
This difference is attributed to the presence of the hub nodes in the Router dataset, which are connected to numerous nodes. 
Thus, the subgraphs corresponding to positive links tend to have more nodes than those corresponding to negative links. 


OOM denotes “out of GPU memory”.

However, the Power dataset does not have hub nodes, and the number of nodes in the subgraph of positive links remains small. 
We randomly changed the center nodes (a,b) for node labeling f^(a,b)_degdrnl increasing the performance, as listed in Table <ref>. 
This outcome highlights that setting target nodes as the center nodes may not effectively analyze the topological structure in the case of small graphs. 
Furthermore, the performance for the Power dataset continues to increase with increasing hops (Table <ref>), achieving an AUC score of 95.87, which is significantly better than that of 92.11 for WP. 



§ CONCLUSION

This paper proposes PHLP, an explainable method that applies PH to analyze the topological structure of graphs to overcome the limitations of GNN-based methods for LP.
By employing the proposed methods, such as angle hop subgraphs and Degree DRNL, PHLP improves the analysis of the topological structure of graphs.
The experimental results demonstrate that the proposed PHLP method achieves competitive performance across benchmark datasets, even SOTA performance, especially on the Power dataset. 
Additionally, when integrated with existing GNN-based methods, PHLP improves performance across all datasets.
By analyzing the topological information of the given graphs, PHLP addresses the limitations of GNN-based methods and enhances overall performance. 
As demonstrated, PHLP provides explainable algorithms without relying on complex deep learning techniques, providing insight into the factors that significantly influence performance for the LP problem of graph data. 

IEEEtran



