GPEN: Global Position Encoding Network for Enhanced Subgraph Representation Learning

We deeply appreciate your thoughtful review and positive assessment of our work. Below we will respond to the raised questions.

W1 and S2: Visualization of Learned Embeddings

We appreciate your suggestion about visualization. We agree that adding visualizations of the learned embeddings would enhance the interpretability of our approach. In the revised manuscript, we will add t-SNE visualizations of subgraph representations learned by GPEN compared with baseline methods on selected datasets. These visualizations will help readers intuitively understand how our method better separates subgraphs of different classes in the embedding space.

S1: Hyperparameter Analysis Summary

Thank you for this valuable suggestion. We will add a concise summary of our hyperparameter analysis in Section 5.2.5 of the main experimental section. The key findings include:

• The balance factor b (controlling the trade-off between local and global structural information) shows optimal performance in the range of 0.6-0.8 across all datasets, indicating that moderately emphasizing local structural information while maintaining global context leads to better subgraph representations.

• The tree-based data augmentation threshold c achieves optimal results with moderate values (4-6), suggesting that this range provides an effective balance between generating sufficient augmented samples and maintaining structural integrity.

• Batch size exhibits relatively stable performance for values between 5 and 15, with gradual decline for larger values (>20), likely due to reduced gradient update frequency and less effective early stopping with larger batches.

• GPEN demonstrates reasonable robustness to hyperparameter changes within these ranges, with different datasets exhibiting varying sensitivities based on their inherent structural properties.

Q1: Applicability to Directed Graphs

GPEN can be naturally extended to directed graphs. Below we elaborate on how each module can be adapted:

Our importance calculation already accommodates directed graphs, as the transition matrix $M$ inherently represents directional flow where $M_{ij}$ is defined based on the out-degree of nodes. This formulation naturally captures the directional influence of nodes in the graph without requiring fundamental changes.

For tree construction, we would maintain the same edge weight assignment while selecting an appropriate spanning arborescence algorithm (directed version of spanning tree) such as Edmonds' algorithm to construct the tree structure from the weighted directed graph. The root node selection would remain based on the highest PageRank score, preserving our hierarchical encoding approach. Once the directed tree (arborescence) is constructed, the global position encoding process remains identical to the undirected case. We would still compute each node's position based on its path distance to the root node, enabling the same systematic way to capture relationships between distant nodes in directed scenarios. For boundary-aware convolution, the primary change would be in the adjacency matrix representation, which would need to reflect the directionality of edges. This modification preserves our boundary-aware convolution's ability to control information flow during the process.

These adaptations would enable GPEN to effectively capture hierarchical relationships in directed network scenarios such as citation networks, social influence networks, and information flow systems, while preserving the theoretical guarantees established in our paper.

We deeply appreciate your kind words regarding the clarity of our presentation. Thank you for acknowledging the thoroughness of our theoretical and experimental sections. Below, we have responded to the weaknesses raised by the reviewer:

W1: Concerns about tree-based encoding and complex graph topologies

We appreciate this thoughtful observation. Our extensive experiments were conducted on eight public benchmark datasets that have been widely used in previous subgraph representation learning studies [1-4]. We evaluated GPEN on eight public datasets comprising various graph structures, including dense networks and small subgraphs. For clearer perspective, here's a summary of these datasets:

Notably, GPEN achieves superior performance (0.912 micro-F1) on EM-USER, which contains over 4.5 million edges, demonstrating that our approach effectively captures complex structural information in densely connected graphs.

This effectiveness primarily stems from the Maximum Spanning Tree (MaxST) methodology, which preserves critical structural information during tree construction by leveraging node importance scores derived from PageRank. The weighting scheme ensures connections between high-importance nodes are prioritized in the resulting tree structure, effectively capturing the backbone of the graph's hierarchical organization. Our tree analysis (Table 6) shows MaxST consistently outperforms other tree construction methods across all datasets, confirming its ability to capture essential graph topology even when simplifying complex structures. As other reviewers noted, our approach "effectively clarifies the practical significance of utilizing a hierarchical tree in the study."

[1] Alsentzer et al., "Subgraph Neural Networks", NeurIPS 2020

[2] Wang & Zhang, "Glass: GNN with labeling tricks for subgraph representation learning", ICLR 2022

[3] Jacob et al., "Stochastic subgraph neighborhood pooling for subgraph classification", CIKM 2023

[4] Kim & Oh, "Translating subgraphs to nodes makes simple GNNs strong and efficient for subgraph representation learning", ICML 2024

W2: Request for concise theoretical summaries in main text

We appreciate this constructive suggestion. Our theoretical analysis establishes four key properties:

1. Theorem 4.1 proves the controllability of GPEN's representations
2. Theorem 4.2 proves the distinctiveness of global position encoding
3. Theorem 4.3 proves that the boundary aware convolution module can suppress noise propagation
4. Theorem 4.4 proves that the empirical distribution covers a wider range after perturbation.

In our revised manuscript, we will add concise summaries after each theorem in Section 4, highlighting key insights in accessible language and demonstrating how these theoretical properties address the challenges outlined in our introduction.

W3: Discussion of potential underperformance scenarios

We thank the reviewer for this valuable suggestion. Regarding synthetic datasets with small subgraphs (Table 3), these were specifically designed to test different capabilities. For density and component tasks, where GNNs already perform well, our model complements these strengths. As shown in Figure 2, our position encoding supplements original features rather than replacing them, while our boundary-aware convolution prevents excessive aggregation. For cut-ratio and coreness datasets, which require more sophisticated structural understanding, our approach effectively captures the necessary information.

Our experiments do reveal some insights about potential limitations. In the Component dataset (Table 3), which has the lowest average degree (2.23) among all datasets, multiple methods including GPEN achieve perfect scores, suggesting that for very sparse graphs with clear component structures, simpler methods may be equally effective. Additionally, our hyperparameter analysis (Figure 4) shows varying sensitivities across datasets, with Coreness exhibiting more pronounced performance fluctuations with changes in the balance factor b, indicating that optimal parameter tuning may be more critical for certain graph structures.

Typo correction

Thank you for pointing out the typo on line 804. We will correct "real-work datasets" to "real-world datasets" in the revised manuscript.

We thank the reviewer for their detailed comments. We appreciate that they found our "theoretical claims in the paper are supported by sound mathematical proofs" and acknowledged that our "experimental design is reasonably sound." Below, we have responded to the weaknesses raised by the reviewer:

Weakness 1 & Other Comments/Suggestions: Improving Figure Clarity

Thank you for your suggestion regarding the color coding in the captions of tables. For the revised manuscript, we will:

• Enhance the clarity of y-axis labels and line colors in Figure 4.
• Add grid lines to facilitate easier interpretation of results in Figure 4.

These visual improvements will make our results more accessible and interpretable for readers.

Weakness 2: Methods for Automatic Threshold Determination

We agree with the reviewer that such methods can be very insightful. However, we would like to note that since the tree perturbation module is optional (as not all datasets suffer from insufficient samples), and as reviewer FTVY13 noted, we don't generate too many samples, making manual parameter tuning sufficient for most applications.

In Figure 3 of our manuscript, we presented a comprehensive analysis of how different threshold values $c$ affect model performance. For enhanced clarity, we have reformatted these experimental results in tabular form below:

This table reveals that while threshold selection influences performance, the variation is generally moderate. GPEN demonstrates relatively stable performance across a reasonable range of threshold values (c=4 to c=8), suggesting it is not overly sensitive to the exact choice of c. This stability reduces the need for precise automatic tuning. For the hpo_neuro dataset, we observe identical performance at thresholds 6 and 8 because there are no remaining connected components larger than these thresholds, which inherently limits the number of samples our method generates. This natural upper bound on generated samples further reduces the necessity for complex automatic threshold determination methods. In addition, the tree perturbation module is optional and primarily benefits datasets with insufficient samples. For datasets with abundant samples, this module may not be necessary.

Question: Maximum Spanning Tree Performance Across Graph Types

Thank you for this insightful question about the consistency of Maximum Spanning Tree (MaxST) performance across different graph structures. In Appendix A.2.4, we conducted a comprehensive analysis of different tree construction algorithms and their impact on GPEN's performance. As shown in Table 6 of our appendix, we evaluated four representative tree construction methods: Breadth-First Search Tree (BFS), Depth-First Search Tree (DFS), Minimum Spanning Tree (MST), and Maximum Spanning Tree (MaxST). Our analysis shows that while MaxST consistently outperforms other tree construction algorithms across all datasets, its advantage is indeed more pronounced in certain graph types.

The experimental results show that the Maximum Spanning Tree algorithm consistently achieves superior performance across all datasets. This is primarily because MaxST effectively preserves critical structural information during the tree construction process by utilizing node importance scores derived from PageRank. The weighting scheme ensures that connections between high-importance nodes are prioritized in the resulting tree structure, effectively capturing the backbone of the graph's hierarchical organization. As reviewer FTVY13 noted, this "effectively clarifies the practical significance of utilizing a hierarchical tree in the study."

The advantage of Maximum Spanning Tree is particularly pronounced in dense graphs with higher average node degrees. For instance, in dense networks such as hpo-metab and hpo-neuro, MaxST achieves significantly better results (0.638 ± 0.009 and 0.691 ± 0.006 respectively) compared to BFS (0.515 ± 0.031 and 0.606 ± 0.037) and DFS (0.494 ± 0.030 and 0.605 ± 0.034). This performance advantage stems from MaxST's ability to identify and preserve important pathways in complex network topologies, resulting in more meaningful global position encodings that better capture the structural relationships between distant nodes.

We sincerely appreciate your positive feedback and constructive remarks on our paper. Below, we provide a detailed response to your questions and comments.

[W1 and W3]

We thank the reviewer for pointing out these notation issues throughout the paper. To clarify:

• $M_{ij}$ : Thank you for bringing this to our attention. You are correct; $M_{ij} = \frac{1}{d_j}$ if there is an edge between nodes $i$ and $j$, where $d_j$ is the out-degree of node $j$. The incorrect notation in the paper was a typographical error.
• $R$: The initial value of $R$ in equation 3 is a uniform distribution where each element equals $\frac{1}{|V|}$, with $|V|$ being the number of nodes in the graph.
• $\mathbf{A}$: This represents the adjacency matrix of the graph, where $A_{ij} = 1$ if there is an edge between nodes $i$ and $j$, and $A_{ij} = 0$ otherwise.
• $\mathbf{H}_n^{(l-1)}$: The subscript $n$ was a typographical error. It should be $\mathbf{H}^{(l-1)}$, representing the node embeddings from layer $l-1$.
• $\mathbf{W}^{(l-1)}$: This refers to the trainable parameter matrix in the graph convolution operation, not the edge weights $w_{ij}$ mentioned in section 3.1.1. The superscript $(l-1)$ indicates that this parameter matrix is associated with the transformation from layer $l-1$ to layer $l$.

We will correct these notations in the revised manuscript and use more distinctive symbols to avoid confusion.

[W2]

Our experimental results show that tree perturbation is effective with modest sample increases, though excessive samples may introduce noise. As shown in Figure 3 in our paper, we conducted detailed experiments on the impact of different threshold values c on model performance. Due to space limitations, we present the numerical results in our response to Reviewer 2fVD under "Weakness 2: Methods for Automatic Threshold Determination." These results clearly identify that even a relatively small number of additional samples can significantly improve the model's performance, while excessive samples may actually harm performance.

We agree that this is an important consideration. However, our primary goal is to explore the potential of tree structures in subgraph representation learning. While our results show promising improvements, we do not claim this approach "completely solves the issue of insufficient subgraphs" in our paper. We recognize that developing high-quality data augmentation methods requires consideration of many factors, which is beyond the scope of our current work.

[W4]

We thank the reviewer for the detailed statistical analysis. However, we respectfully argue that a holistic evaluation reveals significant advantages for GPEN.

Crucially, GPEN shows superior performance over S2N on most datasets, particularly on synthetic datasets specifically designed to evaluate distinct structural learning capabilities. On these challenging tasks, GPEN outperforms all baseline methods, showcasing its robust structural understanding. In stark contrast, S2N not only fails to match GPEN but actually exhibits performance degradation compared to other established baselines. For example, on cut-ratio, S2N scores 0.892 vs. GLASS's 0.935 vs. GPEN's 0.936, and on coreness, S2N scores 0.726 vs. GLASS's 0.840 vs. GPEN's 0.876.

While S2N achieves comparable mean results on a few datasets, it does so with markedly high standard deviations compared to other baselines (averaging a 43.2% increase over SubGNN and a 127.7% increase over GLASS). GPEN, conversely, achieves its strong performance with significantly lower standard deviations across the board (averaging a 59.8% reduction compared to SubGNN and 37.5% compared to GLASS).

[S1]

Thank you for this insightful suggestion regarding alternative encoding methods for the global positional information. Our choice of one-hot encoding for tree depths was based on several practical considerations:

First, the inherent message-passing mechanisms in GNNs enable the model to naturally learn relationships between different depth levels during convolution operations, making explicit continuous encoding less critical in this context. Second, node depth primarily functions as a categorical feature that distinguishes nodes. The one-hot representation provides clear separation between these structural groups. Third, unlike transformer models that should generalize across unseen positions, our model operates on specific graph structures where the positional relationships are fixed, reducing the need for the interpolation capabilities that make sin/cos function encodings valuable in sequence modeling.

We conducted additional experiments comparing one-hot encoding with sin/cos function encodings, but due to space limitations, we apologize that we couldn't present these results. Consistent with our reasoning, these experiments showed no significant performance improvements, as both encoding methods capture the same fundamental structural information.