GPEN: Global Position Encoding Network for Enhanced Subgraph Representation Learning
Authors: Nannan Wu
Yuming Huang
Yiming Zhao
Jie Chen
Wenjun Wang
Venue: ICML 2025 poster (2025)
Keywords: Subgraph Representation Learning
Primary area: deep_learning->graph_neural_networks

Abstract: Subgraph representation learning has attracted growing interest due to its wide applications in various domains. However, existing methods primarily focus on local neighborhood structures while overlooking the significant impact of global structural information, in particular the influence of multi-hop neighbors beyond immediate neighborhoods. This presents two key challenges: how to effectively capture the structural relationships between distant nodes, and how to prevent excessive aggregation of global structural information from weakening the discriminative ability of subgraph representations.
To address these challenges, we propose GPEN (Global Position Encoding Network). GPEN leverages a hierarchical tree structure to encode each node's global position based on its path distance to the root node, enabling a systematic way to capture relationships between distant nodes. Furthermore, we introduce a boundary-aware convolution module that selectively integrates global structural information while maintaining the unique structural patterns of each subgraph. Extensive experiments on eight public datasets identify that GPEN significantly outperforms state-of-the-art methods in subgraph representation learning.

GPEN: Global Position Encoding Network for Enhanced Subgraph Representation Learning
Nannan Wu Yuming Huang"
Yiming Zhao
Jie Chen
Wenjun Wang 13
Abstract
hops
Subgraph representation learning has attracted growing interest due to its wide applications in various domains. However, existing methods pri- marily focus on local neighborhood structures while overlooking the significant impact of global structural information, in particular the influence of multi-hop neighbors beyond immediate neigh- borhoods. This presents two key challenges: how to effectively capture the structural relationships between distant nodes, and how to prevent ex- cessive aggregation global structural informa- tion from weakening the discriminative ability of subgraph representations. To address these challenges, we propose GPEN (Global Position Encoding Network). GPEN leverages hierar- chical tree structure to encode each node's global position based on its path distance to the root node, enabling a systematic way to capture rela- tionships between distant nodes. Furthermore, we introduce boundary-aware convolution module that selectively integrates global structural infor- mation while maintaining the unique structural patterns of each subgraph. Extensive experiments eight public datasets identify that GPEN sig- nificantly outperforms state-of-the-art methods in subgraph representation learning.
Suspicious
Legit Business X
hops
Suspicious
Intermediate
Hub A
Subgraph A
Legit Business
2 hops
Legit Business
Intermediate
Hub
Subgraph
Figure I. Illustration of the challenge. While fraudulent (Subgraph A) and legitimate (Subgraph B) transaction schemes exhibit similar local structures centered around hub nodes and regular transac- tion patterns, Subgraph receives funds from suspicious sources through multiple hops of intermediate accounts, highlighting the importance global structural information beyond neighborhoods.
have achieved remarkable success in graph-related tasks, including node classification (Chen et al., 2020; Xiao et al., 2022), link prediction (Lei al., 2019; Long al., 2022), and graph classification (Zhang et al., 2018; Xie et al., 2022; Wei et al., 2023).
Subgraph representation learning, which focuses on captur- ing meaningful representations of subgraphs within a larger graph, has attracted growing interest. It has shown strong potential in various applications, such as predicting cellu- lar functions in protein-protedd interaction networks and diagnosing rare discases in phenotype knowledge graphs (Sharan et al., 2007; Alsentzer et al., 2020b).
1. Introduction
Graphs are widely used to model relational data, such as transportation networks (Jiang & Luo, 2022), biological systems (Fout et al., 2017), and social networks (Chen et al., 2018). In recent years, Graph Neural Networks (GNNs)
However, existing methods focus mainly on local neighbor- hood structures while overlooking the significant impact of global structural information (Alsentzer et al., 2020b; Wang & Zhang, 2022; Jacob et al., 2023; Kim & Oh, 2024). in particular the influence of multi-hop neighbors beyond immediate neighborhoods. As illustrated in Figure 1, in financial transactions, money laundering schemes often de- liberately mimic legitimate transaction patterns to avoid detection. Both fraudulent (Subgraph A) and legitimate (Subgraph B) schemes appear similar when only examining
'Equal contribution 'College of Intelligence and Computing, Tianjin University. Tianjin, China "College of Management and Economics. Tianjin University. Tianjin, China YYazhou Bay Inno- vation Institute, Hainan Tropical Ocean University, China. Corre- spondence to: Nannan Wu nannan. wu sranman.vu@ju..cdu.....
Proceedings of the nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

GPEN: Global Position Encoding Network for Enhanced Subgraph Representation Learning
their direct transaction behaviors, as they both contain a cen- tral hub node that processes multiple regular transactions with surrounding accounts. This structural similarity arises because fraudsters intentionally construct their schemes to resemble normal business operations. The key distinction is the global structural information: fraudulent schemes (Sub- graph A) receive funds from suspicious sources through multiple hops of intermediate accounts, deliberately creat- ing distance between the suspicious source and the final hub node. This indicates that capturing only local neighbor- hood structures is inadequate for learning effective subgraph representations.
between nodes to control information flow during convolu- tion, allowing the model selectively integrate global struc- tural information while maintaining the unique structural patterns of each subgraph. It helps maintain the subgraph's s inherent structural characteristics while incorporating useful information from the global structural information.
We conclude the contributions of GPEN as follows:
We propose a novel tree-based global position encod- ing that provides a unified way to capture multi-hop relationships for all nodes in the graph, effectively ad- dressing the challenge of modeling global structure.
Modeling the global structural information presents two major challenges. First, effectively capturing the structural relationships between distant nodes is challenging. Current methods, such as random walk sampling, may overlook important distant nodes and struggle to encode sampled sequences into meaningful global features. This requires capturing global structural information from a more unified perspective rather than relying on fragmented local views. Moreover, simply aggregating global structural information can weaken the discriminative ability of subgraph repre- sentations. According to the homophily principle, nodes connected by edges are more likely to share similar proper- ties. Excessive aggregation of global structural information may introduce distant nodes that are irrelevant to the sub- graph, weakening the learning of its intrinsic structure. This highlights the need for a module that can selectively in- tegrate global structural information while preserving the inherent structural characteristics of the subgraph.
We design a boundary-awand aware convolution module that selectively integrates global structural information while preserving intrinsic subgraph structures, prevent- ing the dilution of structural characteristics.
Extensive experiments on eight public datasets iden- tify that GPEN outperforms state-of-the-ar methods, achieving superior performance in subgraph represen- tation learning.
2. Preliminaries
Notations. Let G = (V, E) denote a undirected graph with node set V and edge set E C V V. = {S1, S2, .... } is set of subgraph of G. For each subgraph S. = (V, F.a) has a label yı where V S V and Es S E. Furthermore, the subgraphs may share nodes and/or edges and consist of multiple components.
To address these challenges, we propose GPEN (Global Po- sition Encoding Network), which effectively captures global structural information while preserving inherent subgraph structures. GPEN leverages a hierarchical tree structure to encode global position information and control information aggregation through boundary-ane aawrre convolution. Specifi- cally, GPEN first transforms the graph into tree structure to utilize its natural hierarchical organization for position encoding. Using this tree structure, we encode each node's 's global position based on its path distance to the root node, enabling a structured way to capture relationships between distant nodes. This tree-based position encoding effectively captures multi-hop relationships and addresses the challenge of modeling global structural information systematically, rather than relying fragmentary local views from sam- pling. Furthermore, as an optional enhancement, we explore additional benefits of the tree structure and discover a tree perturbation trick that utilizes the tree's hierarchical nature to generate consistently perturbed samples, which helps sta- bilize model training. To prevent excessive aggregation of global structural information that could obscure intrinsic subgraph structures, we introduce a boundary- con- volution module. This module computes difference vectors
Problem Definition. Given a set of subgraphs S [S1. S2..., S in a graph G = E), GPEN generates a representation Zs, for each subgraph to predict its label y/-
Spatial GCN. Graph convolution for Spatial GCN is based the aggregation of node neighbourhood features. Nodes update their features by passing and receiving messages (features). The formulation is:
h 10 = M (n! AGGIN ;uE :uEN(()) (I)
where h represents the feature vector of node v at layer 1. N (v) denotes the neighbours of v. AGG and M denotes aggregation and update operations, respectively.
Tree. Trees are widely used in computer science and math- ematics for hierarchical data organization, traversal, and dynamic programming. A tree is a connected acyelic graph commonly represented as T = (Vr, ET), where Vr is the set of nodes (vertices) and ET C Vr x VT is the set of edges. In a tree, any two nodes are connected by exactly one simple path, and there are no cycles. A tree with n nodes has exactly n edges.
2

---

GPEN: Global Position Encoding Network for Enhanced Subgraph Representation Learning
Boundary. Convolution
Subgraph Dataset
Global
offiree seterr
Serge Mecie
Reedout & MLP
run
Position Encoding
Zs
Vanilla Graph Convolution
Subgraph
Graph
950
Subgraph Prediction
MLP
Position Encoding
tright
Construction
Optional
Zs'
Tree
Tree Perturbation
root
Subgraph
Max compasent 5
Figure 2. Framework of GPEN, (1) Left Side (Global Position Encoding): The input consists of the entire graph and a subgraph S= +C, D, E}. GPEN utilizes tree structure to encode each node's global position, enabling it to capture relationships between distant nodes. Optionally, the largest connected component the tree can be used for perturbation. (2) Middle (Boundary-aware Convolution): After vanilla message-passinne node representations h, in the subgraph are refined using difference vectors di between nodes to selectively integrate global structural information while preserving the subgraph's inherent characteristics.
(3) Right Side (Subgraph Representation & Prediction): The node representations are aggregated to obtain the subgraph representation {?s, Z }. which is then fod into an ML.P to predict the subgraph labels.
3. Methodology
this, GPEN leverages tree structure to encode each node's global position, enabling a systematic way to capture rela- tionships between distant nodes. Specifically, GPEN first estimates node importance through degrec-based random walks, and then utilizes this information to construct a tree for position encoding. Finally, GPEN encodes each node's global position based its path distance to the root node.
In this section, describe GPEN in detail. GPEN con- tains two key modules: (1) Global Position Encoding and (2) Boundary-aware Convolution. Global position encod- ing leverages the natural hierarchical organization of tree structure to encode each node's global position, enabling a systematic way to capture relationships between distant nodes. Boundary-aware convolution computes difference vectors between nodes to control information flow during convolution, allowing the model to selectively integrate global structural information while maintaining the unique structural patterns of each subgraph.
Definition 3.2. Global Position Encoding: Given a tree T with root and depth tmaxx the global position encoding of node is a vector P. E {0, 1mxx+ defined as:
{1
ifi=ta to otherwise
pol.
Vi (0,
mmax }
Definition 3.1. Global structural information: For a node e in graph G, its global structural information characterized by its hierarchical position in a tree T constructed from G. Formally, let t, (T, r) denote the shortest path distance from v to the root node in T. The global structural information of is encoded through f., which reflects its structural influence relative to the most central node (root) in the hierarchical organization of T.
where t, = (v, r) is the shortest path distance from v to T.
We will explain the process tree construction and global position encoding.
3.1.1. TREE CONSTRUCTION
Inspired by PageRank (Page et al., 1999), we leverage node degrees to measure node importance, as degrees naturally reflect how well-connected and influential nodes are in the graph (Borgatti, 2005; Lü et al., 2016; Tan et al., 2023). . The importance of each node v is calculated through iteration based on degrees:
3.1. Global Position Encoding
The global structural information in the entire graph can affect the labels of subgraphs. To acquire global structural information for subgraphs, we introduce the global position of nodes, which takes into account all nodes. To achieve
3

---

GPEN: Global Position Encoding Network for Enhanced Subgraph Representation Learning
to enhance model robustness. The insufficient number of subgraphs can affect the model's stability. For example, as shown in Table 2, the em-user dataset has 57,333 nodes and 4,573,417 edges, but only 324 subgraphs. This substantial disparity can result in large variations in outcomes under different seeds.
R(L +1 1) (1-a) + op
(3)
where R(() is the importance vector at iteration 6, M is the degree-normalized adjacency matrix where My 1. if d; there is an edge between nodes i and j (and dj is the degree of node j). a is the probability of random jumps, and p is the initial probability vector with each element equal to [V] where [ is the number of nodes in the graph.
This trick utilizes the tree structure to generate additional samples through consistent perturbation. As shown in the Left Side of Figure 2, for each subgraph S, we extract its largest connected component in the tree as a new sample:
To utilize the importance values for tree construction, we assign edge weights based on the importance of connected nodes:
s I) y"
Waj-
R
RDj (1,5) F
(4)
if Vos
(8)
The node with the highest importance value is selected as the root node r:
where S' and yf are the generated subgraph and its label, Vs the node set of S, and fc denotes the function that se- lects the largest connected component of Vs within T' The threshold ensures that only sufficiently large components are used as new samples.
== arg max R(v) EV
(5)
Using the edge weights, we construct a weighted graph G' (V, E, W). where Wi is the set of weights for the edges. The weighted graph G' and root allow the use of different algorithms to construct the tree:
This trick is effective because the tree is constructed by considering the weights of all nodes and edges in the entire graph, preserving much of the original graph's 's structural information. Moreover, since all perturbations are derived from the same tree structure, they follow a consistent pattern, ensuring the quality and coherence of the generated samples.
T = ALGORITHM('',,
(6)
where T' is the tree, ALGORITHM denotes algorithms for tree construction. For example, using the maximum span- ning tree algorithm, the tree is constructed by connecting all nodes using the edges with the highest weights.
Importantly, this simple trick introduces no additional pa- rameters that need careful tuning, as it utilizes the already constructed tree structure. Our experiments show that this optional step can help reduce the variance of results across different random seeds.
3.1.2. GLOBAL POSITION ENCODING
The shortest path from every node to the root naturally divides the tree into different levels. This hierarchical struc- ture facilitates the efficient encoding of all nodes. The global positional encoding of node v can be defined as one-hot vector representing its shortest path distance P. from the root node:
3.2. Boundary-aware Convolution
Excessive aggregation of global structural information may weaken the discriminative ability of subgraph representa- tions by introducing irrelevant distant nodes.
To address this challenge, we propose boundary- convolution that computes difference vectors between nodes to control information flow during convolution. Specifi- cally, for a node in the subgraph, the module first derives the node feature vectors through vanilla message-passing, then computes the difference vectors between the nodes and their neighbors, and finally aggregates the node feature vectors and the difference vectors to obtain the final node representation. Formally,
P. I[t,, = 0), I[t,, = =1),.., (mma)) )1 R fman
(7) where f. is the shortest path distance from the root node, is the identity function and bmaz is the maximum possible value of t equal to the depth of the tree. For the function I, I(4)) = 1 when the condition q = true, otherwise O.
Importantly, the global position encoding is computed of- fline. The final feature 2;; for 02 E V can be obtained by concatenating origin feature x; zerigin and P. together, which will be utilized in subsequent steps of the model.
z (1) AGG (n!)) (dr u E (V(1))
(9)
3.1.3. OPTIONAL TREE PERTURBATION
where 2 is the final representation of node at layer 1, (I) represents the feature vector of u as computed by equation 1, d denotes the difference vectors in the dimensional space
Beyond using the tree structure for global position encoding, we further explore its potential and discover a simple trick
4

---

GPEN: Global Position Encoding Network for Enhanced Subgraph Representation Learning
between and its neighbour u, and AGG is the aggregation operation, such summation.
crepancy between them is bounded by:
7 ZGNNN
S C1
Σ 1
1
The difference vectors d" are formulated as:
NEV
+ C2D(DDUGGEN HOON
d h h u (())
(10)
+ C3D( .
(14)
These difference vectors emphasize the internal structure of subgraphs by capturing the relative differences between neighboring nodes, helping maintain the subgraph's 's unique structural patterns.
where C1 C22 C3 are constants dependent model depth L and Lipschitz continuity of aggregation functions. XGPEN = XX [ P] and X = - are the imput
features for GPEN and standard GNN respectivve,, where P = {polev.
To achieve the convolution, we introduce diagonal matrix M, which acts as a binary selector for nodes within sub- graphs, with M.,, if node is part of the subgraph, and O otherwise. The representations of graph are denoted as,
The proof provided in the Appendix A.1. This controlla- bility result ensures that GPEN's representations maintain meaningful connections standard GNN representations while incorporating additional structural information. The bound demonstrates that our extensions provide enhanced expressiveness within controlled limits.
-1- H) +M,D (1)
(11)
where b is a balance factor controlling the integration of global structural information, ( is the representation ma- trix of nodes, (0) is the result of vanilla graph convolution and ( is the difference matrix. H and D are formu- lated as:
Building on the controllability result, we next analyze whether our global position encoding can effectively distin- guish nodes based on their structural roles:
Theorem 4.2 (Global Position Encoding Distinctness). Let G G (V,E) E) be a connected graph, and be the tree con- structed using edge weights Wsj R(i) + R(j). where R(v)) is the PageRank score of node v. For any nodes u. E V with deg(u) & deg(v), their global position en- codings satisfy pa. + Po-
H ( = (AH (1-1) w(-!))
(12)
and
T
D = Σ EmENtON) d EveNo..)
d=
(13)
Full proof is in the Appendix A.2. This theorem confirms that our tree-based global position encoding successfully captures structural differences between nodes, particularly distinguishing nodes with different connectivity patterns.
where (0) X. X is the node feature matrix after global position encoding, allowing GPEN to preserve subgraph structures while selectively incorporating global structural information.
Having established the effectiveness of position encoding, we analyze the stability of our boundary-award convolution mechanism:
4. Theoretical Analysis
Theorem 4.3 (Noise Robustness). Let h, ho + cu be
To theoretically validate GPEN, we provide a comprehen- sive analysis of its key properties. We first demonstrate that GPEN provides controllable representation learning through bounded representation discrepancy. Then we show how the global position encoding effectively captures struc- tural information. Further analysis proves the stability of boundary-awand convolution against noise propagation, and finally establishes generalization guarantees for the tree per- turbation technique.
noisy node features with e, NO o²1). The covariance of boundary- convolution outputs satisfies:
Cov(z.A) - (1 +3W((0) +
while standard GNN aggregation yields Cov(=GNN) [W Furthermore, boundary-aware convolution achieves higher signal-to-noise ratio (SNR).
The detailed proof is included in Appendix A.6. This sta- bility analysis reveals that our boundary- convolution effectively suppresses noise propagation compared to stan- dard GNN aggregation. The difference vectors used in boundary-aware convolution help maintain structural dis- tinctness while reducing noise amplification, which is essen- tial for robust subgraph representation learning.
We begin by showing that GPEN maintains controllable representation learning, with bounded discrepancy between its representations and those of standard GNNs:
Theorem 4.1 (Bounded Representation Discrepancy). Let GGPEN and GNN denote subgraph representations gener-
ated by GPEN and standard GNN, respectively. The dis-
5

---

GPEN: Global Position Encoding Network for Enhanced Subgraph Representation Learning
Model
ppi-hp
hpo-metab
hpo-neuro
em-user
MLP
0.445 + 0.009
0.386 0.035
0.404 0.019
0.524 0.060
GBDT
0.446 + 0.000
0.404 + 0.000
0.513 + 0.000
0.694 0.000
Sob2Voc
0.388 + 0.003
0,472 + 0.032
0.618 + 0.009
0.779 + 0.041
GNN-seg
0.361 + 0.025
0.542 + 0.028
0.647 + 0.003
0.725 = 0.010
SubGNN
0.599 0.025
0.537 + 0.025
0.644 0.019
0.816 0.041
GLASS
0.619 + 0.022
0.614 +: 0.016
0.685 0.016
0.888 0.019
SSNP
0.636 + 0.022
0.587 + 0.032
0.682 + 0.013
0.888 0.016
S2N
0.643 + 0.041
0.639 + 0.072
0.686 + 0.019
0.890 + 0.035
GPEN
0.644 + 0.009
0.639 + 0.009
0.691 + 0.006
0.912 + 0.013
Table 1. The mean micro-Fl scores (average of 10 runs) with standard deviations on four real-world datascts.
Finally, we analyze how our optional tree perturbation tech- nique enhances model generalization:
nodes
edges
Subgraphs
# Classes
ppi-bp
17,080
316,951
1,591
Theorem 4.4 (Generalization Bound). Let 3(k) v /Es ||SS measure perturbation effects. With prob- ability - 6, the expected risk Lhh is bounded by:
hpo-metab
14,587
3,238,174
2,400
hpo-ncuro
14,587
3,238,174
4,000
10
em-user
57,333
4,573,417
324
2
density
5,000
29,521
250
3
cut-ratio
5,000
83,969
250
L(h) < (h) 2dyc (n(e//)
In(1/6) 2m
coreness
5,000
118,785 43,701
221
+ 3(K),
component
19,555
250
where dvc is the VC dimension and m, & are the numbers of original and perturbed subgraphs.
Table 2. Statistics of all datascts.
The full proof can be found in Theorem A.7 in the Ap- pendix.Thie This generalization bound demonstrates that tree perturbation improves model generalization by generating structurally consistent augmented samples. The bound quan- tifies how the additional samples from tree perturbation help reduce overfitting.
5.1.2. BASELINES
We compare GPEN with GNN-seg, MLP, GBDT, Sub2 Vec (Adhikari et al., 2018), SubGNN (Alsentzer et al., 2020b), GLASS (Wang & Zhang, 2022), SSNP (Jacob et al., 2023), and S2N (Kim & Oh, 2024) as our baselines. For detailed baseline introductions and experimental settings, please re- fer Appendix A.2.
The theoretical analysis above establishes four key prop- erties of GPEN: (1) controllable representation learning with bounded discrepancy, (2) effective structural distinc- tion through global position encoding, (3) robust feature learning via boundary-aware convolution, and (4) enhanced generalization through tree perturbation. Together, these properties validate our approach to subgraph representation learning and demonstrate how GPEN addresses the chal- lenges outlined in the introduction.
5.2. Experimental Results
5.2.1. REAL-WORLD DATASETS.
GPEN outperforms all existing models on four real-world datasets. The results are summarized in Table which re- ports the average micro-FI scores and standard deviations for each model and dataset (averaged over 10 runs with different seeds). The em-user dataset which contains denser connections and higher average node degree. GPEN easily outperforms other basclines on the em-user datasets, likely because the larger graph sizes result in deeper trees, making the tree structure more impactful. This result highlights GPEN's superiority in capturing node interaction patterns in a larger graph setting, validating the great performance of GPEN. Notably, simpler baselines like MLP and GBDT that only consider node features perform poorly (0.524 and 0.694 on em-user), while methods that partially capture global structure (GLASS, SSNP) show better results but still fall short of GPEN's comprehensive approach. This empirically validates our theoretical analysis that effective
5. Experimental Evaluation
5.1. Experimental Settings
5.1.1. DATASETS.
We use the same four real-world datasets and four synthetic datasets (Alsentzer et al., 2020b; Wang & Zhang, 2022: Kim & Oh, 2024). Detailed information about these datasets is presented in Table 2 and Appendix A.2. The datasets are divided according to the split ratios outlined in the baselines (Alsentzer et al., 2020b; Wang & Zhang, 2022; Jacob et al., 2023; Kim Oh, 2024).
6

---

GPEN: Global Position Encoding Network for Enhanced Subgraph Representation Learning
Method
density
cut ratio
coreness
component
Sub2Vec
0.459 0.038
0.354 + 0.044
0.360 0.060
0,657 + 0.054
GNN-seg
0.952 + 0.019
0.346 = 0.035
0.593 0.038
1.000 + 0.000
SubGNN
0.919 + 0.019
0.629 = 0.041
0.639 + 0.098
0.958 + 0.101
GLASS
0.930 = 0.028
0.935 = 0.019
0.840 + 0.028
1.000 = 0.000
S2N
0.963 0.057
0.892 1 0.044
0.726 0.114
1.000 1 0.000
GPEN
0.956 0.016
0.936 = 0.016
0.876 + 0.019
1.000 0.000
Table The mean micro-Fl scores (average of runs) with standard deviations on four synthetic datasets.
No.
GPE BWC OTP
ppi-bp
emuser
0.90
op-1p
1
0.644 = 0.009 0.912 + 0.013
0.85
Micro-F1 Score
2
0.633 = 0.019 0.898 + 0.032
0.80
3
V
0.590 0.016 0.796 = 0.050
0.75
4
0.631 = 0.013 0.864 + 0.028
5
0.632 = 0.013 0.857 + 0.033
0.70
6
0.585 = 0.028 0.796 + 0.054
0.65
7
0.584 = 0.019 0.796 + 0.032
8
0.588 = 0.022 0.850 = 0.076
0.60
4
Tree-Based Data Auamentation Threshold c
Table 4. The mean micro-Fi Fl scores and their standard deviations. averaged over runs, the ablation studies.
Figure 3. Hyperparametric Analysis
subgraph representation requires both global position in- formation and selective feature integration. Finally, GPEN achieves lower standard deviations while maintaining higher accuracy, validating the theoretical stability of our modules.
datasets (e.g., #0.016 cut-ratio compared to +0.044 for S2N) demonstrate the stability benefits of our tree-based po- sition encoding and boundary-awar feature integration ap- proach, aligning with our theoretical analysis of the model's representational properties.
5.2.2. SYNTHETIC DATASETS.
The synthetic datasets provide controlled experiments to validate specific components of GPEN. As shown in Table GPEN achieves sate-offthheaart performance three out of four datasets, with particularly strong results tasks requiring global structural understanding.
5.2.3. ABLATION STUDY
To validate the power of the modules, conducted ab- lation studies by removing each corresponding module from GPEN. For convenience, we use abbreviations for the three modules: Global Position Encoding (GPE), Boundary- aware Convolution (BWC), and Optional Tree Perturbation (OTP). The results the ablation experiments are shown in Table 4. Each module acting individually cannot improve performance and may even worsen it the emuser dataset. However, when the two modules work together, the results improve, and the best performance is achieved when all three modules are used together. This indicates that the three modules are interdependent. When they work together, they can better utilize both global and local structural infor- mation of the subgraphs. achieving optimal performance. can be observed that removing GPE module leads to sig- nificant performance drop. highlighting the important role of global position encoding in subgraph representation. Ad- ditionally, when the OTP module is introduced, GPEN not only shows improved results but also experiences a reduc- tion in standard deviation, demonstrating the effectiveness of the OTP module.
On the cut-ratio dataset, which tests boundary structure recognition, GPEN achieves 0.936 accuracy with # deviation, outperforming other methods and demonstrating the effectiveness of our boundary-ave ule. The strong performance coreness (0.876), which evaluates both boundary and positional information, further validates GPEN's ability to capture multi-hop relationships through global position encoding.
convolution mod-
While simpler models like GNN-seg perform well on den- sity and component tasks that primarily test local struc- ture recognition, they struggle with tasks requiring global context (0.346 cut-ratio). In contrast, GPEN maintains competitive performance on local structure tasks (0.956 density) while excelling at tasks requiring global informa- tion, empirically validating its design goal of balancing local and global structural information.
The consistently lower standard deviations across

---

GPEN: Global Position Encoding Network for Enhanced Subgraph Representation Learning
0.95
1.00
0.85
0.95
0.95
0.80
MicroFFi Score
0.90
0.90
0.75
0.70
0.80
0.80
0.60
0.75
0.75
0.70
0.70
0.45
0.65
0.65
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.6
0.8
1.0
10
20
25
30
Number of Hyperparameter b
Number of Hyperparameter b
Number of batch size
(a) The results of four real-world datasets
(b) The results of four synthetic datasets
(c) The results of different batch sizes
Figure Hyperparametric Analysis
Tree
ppi-bp
hpo-metab
hpo-neuro
em-user
Breadth-Fing Search Tree
0.560 = 0.054
0.515 = 0.031
0.606 + 0.037
0.857 = 0.047
Depth- First Search Tree
0.579 0.047
0.494 + 0.030
0.605 0.034
0.846 + 0.035
Minimum Spanning Tree/Steiner Tree
0.570 = 0.030
0.587 = 0.026
0.683 0.019
0.833 = 0.022
Maximum Spanning Tree
0.644 + 0.009
0.638 + 0.009 0.691 0.006
0.912 + 0.013
Table 5, Different constructing tree algorithms for the tree
5.2.4. TREE ANALYSIS
construction in GPEN.
We evaluated four tree construction algorithms determine their impact on GPEN's performance: Breadth-First Search Tree (BFS), Depth-First Search Tree (DFS), Minimum Span- ning Tree (MST), and Maximum Spanning Tree (MaxST).
5.2.5. HYPERPARAMETRIC ANALYSIS
We conducted comprehensive experiments to understand the impact of three key hyperparameters in GPEN: the bal- ance factor the tree-based data augmentation threshold c, and the batch size. Our analysis reveals distinct patterns that provide insights into the model's behavior and design principles.
Table 5 shows that the maximum spanning tree algorithm achieved the best results. This is likely because we use edge weights construct the tree, and the maximum span- ning tree algorithm focuses retaining high-weight edges, preserving the more informative structures of the graph.
Tree-based Data Augmentation Threshold c. The thresh- old parameter e determines the minimum size of connected components used for generating augmented samples. Our experiments reveal an interesting trade-off, as shown in Figure 3. Lower thresholds tend to generate numerous but potentially noisy augmented samples, as smaller connected components may not preserve meaningful structural prop- erties of the original subgraphs. Higher thresholds, while ensuring quality, restrict the quantity of augmented data, limiting the regularization benefits. The optimal perfor- mance typically occurs at moderate threshold values, where the augmentation process achieves a sweet spot between sample quality and quantity. This pattern is particularly pronounced in datasets with larger average subgraph sizes, where the tree structure provides more opportunities for meaningful augmentation.
Specifically, the effectiveness of MaxST stems from its ability to preserve critical structural information by priori- tizing connections between high-importance nodes through edge weights way = R|i] + Rlj). where R[i] represents the PageRank-derived importance score. This approach cap- tures the graph's 's hierarchical backbone more effectively than traversal-based methods (BFS/DFS) or minimum- weight approaches (MST).
MaxST demonstrates significant performance improve- ments, particularly in dense graphs such as hpo-metab and hpo-neuro, substantially outperforming BFS and DFS meth- ods. Additionally, MaxST exhibits superior stability with consistently lower standard deviations.
While MaxST has higher computational complexity (O(E) log (VD) compared to BES/DFS (O(V) + [E)), the significant performance gains justify this cost. The en- hanced quality of global position encodings and improved model robustness make MaxST the optimal choice for tree
Balance Factor b. The balance factor controls the integra- tion of local structural features and global position infor- mation during boundary-aware convolution. As illustrated in Figure 4(a), we observe a consistent pattern across all
8

---

GPEN: Global Position Encoding Network for Enhanced Subgraph Representation Learning
datasets: optimal performance emerges when b falls within moderate range, typically between 0.6 and 0.8. This finding validates our theoretical framework that effective subgraph representation requires careful balance between local and global information. When b is too low, the model fails to leverage crucial local structural patterns that define sub- graph boundaries. Conversely, excessively high values lead to over-emphasis on local structures, causing the model to lose sight of important global contextual information. The consistency of this optimal range across diverse datasets sug- gests that this balance is fundamental requirement rather than dataset-specific phenomenon.
powerful tools for processing graph-structured data. Var- ious architectures have emerged, including GCN (Kipf & Welling, 2016), GAT (Velickovic et al., 2017), and Graph- Sage (Hamilton et al., 2017), each offering unique ap- proaches to graph learning.
6.2. Subgraph Representation Learning.
The field of subgraph analysis has experienced significant growth (Alsentzer et al., 2020a), with applications ranging from predicting graph evolution (Meng et al., 2018) to en- hancing graph classification (Wang et al., 2021). However, the specific challenge of learning subgraph representations remained largely unexplored until recently. A breakthrough came with SubGNN (Alsentzer et al., 2020b), which estab- lished the foundations of subgraph representation learning and prediction. The model innovates through its anchor- based information sampling mechanism, which bridges lo- cal subgraph structures with global graph context through carefully designed information channels. Building on this foundation, GLASS (Wang & Zhang, 2022) introduced novel perspective by developing mask-based approach to distinguish subgraph boundaries. Following these works, researchers have proposed some approaches to balance rep- resentational power with computational efficiency. Recent advances include SSNP (Jacob et al., 2023), which improves efficiency through stochastic neighborhood sampling during the readout phase, and S2N (Kim & Oh, 2024), which trans- forms the subgraph learning problem through an innovative graph coarsening approach that balances computational effi- ciency with comprehensive structural preservation. The field has also benefited from adapting existing methodologies. For instance, Sub2Vec (Adhikari et al., 2018), originally de- signed for community detection, demonstrates how random walk sampling and language modeling techniques (Le & Mikolov, 2014) can capture subgraph characteristics.
Batch Size Effects. The impact of batch size on model performance, depicted in Figure 4(c), reveals the interplay between optimization dynamics and model convergence. Smaller batch sizes generally lead to better performance, which can be attributed to more frequent parameter updates and increased stochasticity in the optimization process. This stochasticity helps the model escape local minima and ex- plore the parameter space more effectively. As batch size increases, we observe performance degradation, particularly notable in tasks requiring fine-grained structural discrimi- nation. This degradation stems from two factors: reduced gradient update frequency per epoch and the averaging effect of larger batches, which can smooth out important learning signals from individual subgraphs with unique structural patterns.
Dataset-Specific Sensitivity. Different datasets exhibit varying degrees of sensitivity to hyperparameter changes, as evidenced in Figure 4(b). Datasets with clear structural boundaries (such as component-based tasks) demonstrate remarkable robustness to hyperparameter variations, main- taining stable performance across wide parameter ranges. In contrast, tasks requiring nuanced integration of multi- scale information (such as coreness prediction) show higher sensitivity. This disparity underscores the importance of our dual-module design: while some tasks primarily benefit from either global position encoding or boundary-aware convolution, complex tasks require precise coordination be- tween both modules, making them more sensitive to the balance factor and other hyperparameters.
7. Conclusion
In this paper, we present GPEN, a novel method for sub- graph representation learning that addresses two key chal- lenges: capturing structural relationships between distant nodes and preventing excessive aggregation of global struc- tural information. Through hierarchical tree-based position encoding, GPEN systematically captures multi-hop relation- ships between nodes, overcoming the limitations of existing local neighborhood approaches. The boundary- convolution module selectively integrates global structural information while preserving the intrinsic characteristics of each subgraph, thus effectively balancing the trade-off between global and local structural information. Extensive experiments on eight public datasets validate GPEN's supe- rior performance compared to state-of state-of-the-ant the-art methods
6. Related Work
6.1. Graph Neural Networks.
While traditional deep learning approaches (Schuster & Pali- wal, 1997; Krizhevsky et al., 2012) have achieved remark- able success with Euclidean data like images (Cheng et al., 2020) and text (Zheng & Zheng, 2019), numerous real- world applications require modeling data in non-Euclidean graph structures. This necessity led to the development of Graph Neural Networks (GNNs), which have become
9

---

GPEN: Global Position Encoding Network for Enhanced Subgraph Representation Learning
Acknowledgements
In 6th International Conference on Learning Represen- tations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenRe- view.net, 2018. URL https: wwwppppweeeiwnneeeeeeeeeeeeeeeee forum? serrm?id=rytstxxii
This work was supported by the National Key R&D Pro- gram of China (No.31400), NSFC (U2468204), Key R&D and Transformation Plan of Qinghai Province (No.2022- QY-218), Science and Technology Plan of Shenzhen 1CCXF22021102012255524
the Key R&D project in Hainan province, China .N0.ZDYF2024SHF2005) and the Major Science and Technology Program of Yazhou Bay Innovation Institute of Hainan Tropical Ocean Uni-
Chen, M., Wei, Z.., Huang, Z., Ding, B., and Li, Y. Simple and deep graph convolutional networks. In International conference on machine learning, pp. 2020.
PMLR,
vensixy2023CXYZD0011.
Cheng, Z., Lu, R., Wang. Z.., Zhang. H., Chen, B., Meng, Z., and Yuan, X. Birnat: Bidirectional recurrent neu- ral networks with adversarial training for video snapshot compressive imaging. In European Conference on Com- puter Vision, pp. 258-275. Springer, 2020.
Impact Statement
This paper introduces GPEN (Global Position Encoding Network), a framework for enhanced subgraph represen- tation learning. The advancement primarily contributes to the efficiency and effectiveness of graph neural networks, with broad applicability in domains such as fraud detection, biomedical research, and social network analysis. We antic- ipate that this work will not introduce any negative ethical or social impacts.
Fout, A., Byrd, J., Shariat, B., and Ben-Hur, A. Protein interface prediction using graph convolutional networks. Advances in neural information processing systems, 30, 2017.
Hamilton, W., Ying. Z., and Leskovec, J. Inductive repre- sentation learning on large graphs. Advances in neural information processing systems, 30, 2017.
References
Adhikari, B., Zhang, Y., Ramakrishnan, N., and Prakash, B. A. Sub2vec: Feature learning for subgraphs. In Ad- vances in Knowledge Discovery and Data Mining: 22nd Pacific-Asia Conference, PAKDD 2018, Melbourne, VIC, Australia, June 3-6, 2018, Proceedings, Part 22, pp. 170-182. Springer. 2018
Jacob, S. A., Louis, P., and Salehi-Abari, A. Stochastic sub- graph neighborhood pooling for subgraph classification. In Proceedings of the 32nd ACM international conference on information and knowledge management, pp. 3963- 3967, 2023.
Jiang, W. and Luo, J. Graph neural network for traffic forecasting: A survey, Expert systems with applications, 207:1 17921, 2022.
Alsentzer, E., Finlayson, S., Li, M., and Zitnik, M. Sub- graph neural networks. Advances in Neural Information Processing Systems, 33:8017-8029, 2020a.
Kim, D. and Oh, A. Translating subgraphs to nodes makes simple gnns strong and efficient for subgraph representa- tion learning. In Forty-first International Conference on Machine Learning, 2024.
Alsentzer, E., Finlayson, S., Li, M., and Zitnik, M. Sub- graph neural networks. Advances in Neural Information Processing Systems, 33:8017-8029, 2020b.
Borgatti, Centrality and network flow. Social networks, 27(1):55-71, 2005.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. arXiv preprint arXiv: 1609.02077 2016.
Boucheron, S., Lugosi, G., and Bousquet, O. Concentration inequalities. In Summer school on machine learning. pp. 208-240. Springer, 2003.
Krizhevsky, A., Sutskever, I., and Hinton, G. E. Imagenet classification with deep convolutional neural networks. Advances neural information processing systems, 25, 2012.
Bousquet, O., Boucheron, S., and Lugosi, G. Introduction to statistical learning theory. In Summer school on machine learning, pp. 169-207. Springer, 2003.
Langley, P. Crafting papers on machine learning. In Langley, P. (ed.), Proceedings of the 17th International Conference on Machine Learning (ICML.200)), pp. 1207-1216, Stan- ford, CA, 2000. Morgan Kaufmann.
Catoni, O. Pac-bayesian supervised classification: the thermodynamies of statistical learning. arXiv preprint arXiv:0712.02248, 2007.
Le, Q. and Mikolov, T. Distributed representations of sen- tences and documents. In International conference on machine learning, pp. 1 1188-18 1196. PMLR, 2014.
Chen, J., Ma, T., and Xiao, C. Fastgen: Fast learning with graph convolutional networks via importance sampling.
10

---

GPEN: Global Position Encoding Network for Enhanced Subgraph Representation Learning
Lei, K., Qin, M., Bai, B., Zhang, G., and Yang. M. Gen- gan: A non-linear temporal link prediction model for weighted dynamic networks. In IEEE INFOCOM 2019- IEEE conference on computer communicatiions, pp- 388- 396. IEEE, 2019.
Xiao, S., Wang, S., Dai, Y., and Guo, W. Graph neural networks in node classification: survey and evaluation.
Machine Vision and Applications, 33(1):4, 2022.
Xie, Y., Liang, Y., Gong, M., Qin, K., Ong, Y.-S., and He, T. Semisupervised graph neural networks for graph classification. IEEE Transactions Cybernetics, 53(10): 6222 6235, 2022.
Long, Y., Wu, M., Liu, Y., Fang, Y., Kwoh, C. K., Chen, J.,
Luo, J., and Li. X. Pre-training graph neural networks for link prediction in biomedical networks. Bioinformatics, 38(8):2254 2262, 2022.
Zhang, M., Cui, Z.., Neumann, M., and Chen, An end-to- end deep learning architecture for graph classification. In Proceedings of the AAAI conference on artificial intelli- gence, volume 32, 2018.
Lü, L., Chen, D., Ren, X.-L., Zhang, Q.-.,, Zhang, Y.- C.. and Zhou, T. Vital nodes identification in complex networks. Physics reports, 650:1-63, 2016.
Zheng, J. and Zheng, L. hybrid bidirectional recurrent convolutional neural network attention- based model for text classification. IEEE Access, 7:106673-106683 2019.
Meng, C., Mouli, S. C., Ribeiro, B., and Neville, J. Sub- graph pattern neural networks for high-order graph evolu- tion prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Page, L., Brin, S., Motwani, R., and Winograd, The pagerank citation ranking: Bringing order to the web. Technical report, Stanford infolab, 1999.
Schuster, and Paliwal, K. K. Bidirectional recurrent neural networks. IEEE transactions on Signal Processing, 45(11):2673-2681 1997.
Sharan, R., Ulitsky, I,, and Shamir, R. Network-band prediction protein function. Molecular systems biology, 3(1):88, 2007.
Tan, Y., Liu, Y., Long, G., Jiang. J., Lu, Q., and Zhang, C. Federated learning on non-iid graphs via structural knowl- edge sharing. In Proceedings of the AAAI conference artificial intelligence, volume 37, pp. 9953-9961, 2023.
Vapnik, V. N. and Chervonenkis, Y. On the uniform convergence of relative frequencies of events their probabilities. In Measures of complexity: festschrift for alexey chervonenkis, pp. 11-30. Springer, 2015.
Velickovie, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., Bengio, Y., et al. Graph attention networks. stat, 1050 (20): 2017.
Wang, J. Chen, P., Xie, Y., Shan, Y., Xuan, Q. and Chen, G. Broad learning based on subgraph networks for graph classification. Graph Data Mining: Algorithm, Security and Application, pp. 49-71, 2021.
Wang, X. and Zhang, M. Glass: Gnn with labeling tricks for subgraph representation learning. In International Confer- ence on Learning Representationss, 2022. URL http //openrevies eew net iet..eeee//orrmmmoddoo.tt
Wei, L., Zhao, H., He, Z., and Yao, Q. Neural architecture search for gun-based graph classification. ACM Transac- tions on Information Systems, 42(1):1-29, 2023.

---

GPEN: Global Position Encoding Network for Enhanced Subgraph Representation Learning
A. Appendix
A.I. Theoretical Analysis
Theorem A.1 (Controllability of Representation Discrepancy). Let S = (V, E, be a subgraph with [V|= nu, and let 7 and 7 denote the subgraph representations generated by GPEN and a standard GNN, respectively, Assume the following:
& is the tree construction, functionn
f IR IR + Rd is Lipschitz continuous function with Lip(f) = -I[' 70, where 70 the spectral norm bound of the parameter matrix W() at layer I.
The pesssgg-passing functions (Boundary-awe) aware Convolution) and m (standard GNN) are Lipschitz continuous with constants Lip(g) and Lip(m), respectively.
All parameter matrices {W()} satisfy || S Y for some 7 > O.
Then, the discrepancy between representations is bounded by:
||,GEN 7GNN
S C1
Σ
h hg
GNNN
C2D(DU)GPEN, HONN + C2D(X x
(15)
BEV
where:
ho =b,, G) is the global position encoding of node
D(U)PPEN {dl" lu V) the multiset of local representations from the 1-th Boundary-aware Convolution,
X [ PI and XGNN ooriiin are the input features for GPEN and standard GNN respectively, where
P = {p..vvv.
D(A, B) = inf ||a (a)aa is the optimal matching metric,
Constants C₁ L Lip(f), C2 L d Lip(f), and Cs -Li((f) Lip(m) depend the model depth L and hidden dimension d.
Proof. We decompose the discrepancy via triangle inequality:
|| 12PEN
|NNN|| s
| (E hv. Σ
d
Σ
h
GNN
Σ d!
Tern
+ f Σ
GNN
Σ
Σ
GNNN
(16)
Bounding Term 1: By Lipschitz continuity of ff and the norm inequality:
(|E(hh 1:GNN)) || ||Σ de0
Term Lip(f)
< Lip(f) Σ |l, A.GNN| || Σ ||a!"1))
(by triangle inequality)
Lip(()) Σ ||,,, - 1.NNN + m max, lc(21)).
(17)
Using the optimal matching metric D,,,),, we have:
max [dd || 5 ((D(O)GENN HNN)..
(18)
12

---

GPEN:
Global Position Encoding Network for Enhanced Subgraph Representation Learning
Bounding Term 2: By Lipschitz continuity of a'nnd m:
Term 2 x Lip(f)
[ [ do00 - -5 mm aewTt))
Lip(f) -ii(f))Lippmm) D(X .GGNN..
(19)
Combining bounds:
| -ZONN - Lip(f) Σ I|, N Lip(f) n D(D(U)GENN HGNN)
Lip((f) Lip(m) ,
= = Σ 1/, -00---1, 11 C2 HCNN) + C3D(X X
(20)
where C1 I. Lip(f), C2 L d Lip(f), and C3 Lip(f) Lip(m), incorporating the model depth L and hidden dimension d.
Theorem A.2 (Global Position Encoding Distinctness with Tree Construction Constraints). Let G (V, be a connected graph and E V with deg(u) A deg(v). Let T be constructed via using maximum spanning tree (MST) with edge
weights Wij- = R(i) + R(j), where R(v) is the PageRank score of node v. Assuming node importance R(v) is strictly increasing with degree (i.e., deg(u) > deg(v) = R(u)= > R(v)), then their global position encodings satisfy Pu # Po-
Proof. We first establish two lemmas:
Lemma A.3 (Monotonicity of PageRank). Under the iteration in (3) with a E (0, for connected graphs, deg(u) > deg(v)
R(u) > R(v).
Proof. From the PageRank equation = (1-a)MM. ap, where My 1/ deg(i). For node u with higher degree:
R()
R(u) = a1)
deg(j)
[V
JEN(u)
By the Ferron-Frobenius theorem, stationary distribution components satisfy R(u)/ deg(w) > deg(v) when deg(u)= deg(v). Hence R(u)= R(v).
Lemma A.4 (MST Path Property). In T with edge weights way R(i) + R(j). the path from any node v to root monotonically increasing in R(-) values.
Proof. Suppose there exists decreasing edge (x on the path with R(x) > R(y). Then replacing it with edge (y, 2)
where R(2)= R(y) would increase the total weight, contradicting MST maximality.
Now consider u. with deg(u) deg((). By Lemma A.3, R(u) R(v). Let = R(v). There are cases:
Case 1: lies on the path from to r in T. By Lemma A.4, disty(u, r) = disty( r) + disty v) > (v. r).
Case 2: and v belong to different subtrees. Let w be the lowest common ancestor. Then:
distr (u, r) disty(u, (u, w) (w, r) * distr(u, w) + disty (w, (v,
since and cannot have identical distances to while maintaining MST maximality under weight ordering.
Thus Pa * Pe in all cases.
Corollary A.5 (Degree-Induced Structural Distinetness). Let
I(u) = t, denote the global structural information of node defined as its depth in T. For any E V with deg(u) & deg(v), their structural information satisfies I(u) # I(v). The converse does not hold: I(u) + I(v) may occur even when deg(u)) deg(v).
Proof. The first statement follows directly from Theorem A.2. For the converse, consider a graph with two 3-degree nodes u and v where u connects to leaf nodes while e connects to hub nodes. Their MST depths may differ despite equal degrees.
13

---

GPEN: Global Position Encoding Network for Enhanced Subgraph Representation Learning
Theorem A.6 (Stability of Boundary-aware Convolution). Let hi by + by be the observed node features with additive noise co (0, I),, where feeveev mutually independent. Given subgraph S E G. define the following two
aggregation operators:
Standard GNN aggregation: GANN = EueN(t) he
Boundary-aware aggregation: _A Nr + EuEN(o - hm)
Then the covariance matrices satisfy:
Cov(=+*) = (1 33 (((1) ( and Cov(ze = [W(u))o21
Furthermore, the signal-to-noise ratio (SNR) satisfies:
B
B||l GNN
2
Tr(Cov(2#1))
where d is the feature dinension.
Proof.
We first analyze the boundary-award aggregation. Let d" = hy hu (hy - hw) + (Ev - Ev). The aggregation
becomes:
2x
h +
Σ
(he +c Σ (cv - Cu)
wEN(()
uEN(v)
signal term
noise term
The noise covariance is:
cu) = -ov ((WWN -Ea 6. + E(5 <c+
Cov(2BA) = Cov
u
a
Using independence of {
(1 + ( W
= = (1++
For standard GNN aggregation:
Cov(=ONN)
Σ Cov(c.)=[W())
mEN(m)
The SNR comparison follows from:
E BilIBBAI BA Tr(Cov(=BAA)
E B 12 (1 + 3w)()) + (Ww)))
E C.INGNN11 |13 W Wwv)lo2d
where the first inequality uses Jensen's inequality and the second follows from ||[ = ||, + Ehe - h
|| Σ h,, 112 [|E|2,NN]]] by triangle inequality and the fact that (1 + + (b) Z [N(v) for (N( 2
Theorem A.7 (Generalization Bound with Tree Perturbation). Let H be the hypothesis class with VC dimension dyc (Vapnik Chervonenkis, 2015), trained on m original subgraphs Si,..., Sm and perturbed subgraphs Si...., St. generated tree perturbation. Let Cemp (h) and L(h) denote the empirical and expected risks respectively. With probability least 1 8 over the sample generation, for any h H:
L(h) S (h) + 2dvc In(em/k)
In(1/8)
+V
+ ((k)
2m
where 3(k) - Ber || and perturbed subgraphs.
measures the perturbation effect, and |ASS is the symmetric difference between original
14

---

GPEN: Global Position Encoding Network for Enhanced Subgraph Representation Learning
Proof. We proceed through three key steps:
Lemma A.8 (Rademacher Complexity with Augmentation). Let Rm (H) be the Rademacher complexity (Bousquet et al., 2003) H on original samples. The augmented complexity satisfies:
Rm à (H) S
m Fm (H)
+
k
(x( +
B SAS
+
2k
Proof. Using the contraction property of Rademacher complexity:
k o.h(S))) +
R I
E
sup m
k j==
Decompose into original and perturbed terms, then apply Talagrand's concentration inequality on the perturbation term (Boucheron al., 2003).
Lemma A.9 (VC Dimension Preservation). The tree perturbation process preserves the VC dimension:
dyc(Hl) I 2dyc(H)
where H' is the augmented hypothesis space.
Proof. Each perturbation can be viewed as restriction operator fe acting the original space. By the Sauer-Shelah lemma, the growth function of the composed space satisfies 11 (n) - (n).
Lemma A.10 (Stability of Perturbation). The expected symmetric difference satisfies:
B[[SAAS1]] s Bi[Vsl (]S
where e is the size threshold in (8.
Proof. By the perturbation definition S' = Ja(Vs, T), the difference comes from nodes outside the largest connected component, Apply linearity of expectation over the node selection process.
Combining these results via PAC-Bayes framework (Catoni, 2007):
In(1/8)
((h) S Cemp + 2Pmmx(()) +
2(m + k)
Substitute Lemma A.8 and bound Rg (H) using Lemma A.9 through Dudley entropy integral:
dvc (veln(ek/dvc)
(H)) S CV
k
Finally apply Lemma A.10 bound the perturbation term B(k).
A.2. Experimental Details
1.2.1. DATASETS
(1) real-world datasets. The ppi-bp dataset is molecular biology dataset for predicting cellular functions of protein groups involved in common biological processes. The hpo-metab and hpo-neuro datasets are clinical diagnostic datasets for predicting the type of rare metabolic neurological disorder based phenotype and genotype data from a knowledge graph. The em-user dataset is a user profiling dataset for predicting user characteristics, such as gender, based on their workout history within social fitness network.
(2) synthetic datasets. These four synthetic datasets are constructed by generating specific structured subgraphs on base graphs. The labels for each dataset are determined by binning the subgraph specific structure (Alsentzer et al., 2020b). Detailed information about these datasets presented in Table 6.
15

---

GPEN: Global Position Encoding Network for Enhanced Subgraph Representation Learning
Dataset
Nodes
Edges
Subgraphs
Average Nodes per Subgraph
Density
5,000
29.521
250
20.0 + 0.0
Cut Ratio
5,000
83,969
250
20.0 + 0.0
Coreness
5,000
118,785
221
20.0 0.0
Component
19,555
43,701
250
74.2 = 52.8
PPI-BP
17,080
316,951
1,591
10.2 = 10.5
HPO-METAB
14,587
3,238,174
1,400
14.4 + 6.2
HPO-NEURO
14,587
3,238,174
4,000
14.8 + 6.5
EM-USER
57,333
4,573,417
324
155.4 100.2
Table 6. Subgraph Properties in Synthetic and Real-World Datasets
A.2.2. BASELINES
To prove model validity, compare GPEN with the following baselines:
(I) SubGNN (Alsentzer al., 2020b) utilizes subgraph-level message passing with artificial channels;
(2) GLASS (Wang & Zhang, 2022) employs label trick with a mask matrix to differentiate between subgraph internal and external regions;
(3) SSNP (Jacob al., 2023) introduces a Stochastic Subgraph Neighborhood Pooling strategy, sampling neighboring nodes during subgraph readout:
(4) S2N (Kim & Oh, 2024) translates subgraphs nodes using graph coarsening methods, while capturing both local and global structures of the subgraph.
(5) Sub2Vec (Adhikari et al., 2018) generates subgraph embeddings by sampling random walks and using Paragraph2
(6) GNN-seg a standard MPNN that performs graph classification by treating each subgraph as an independent graph, ignoring its external connections; and (7) ML.P and (8) GBDT aggregate node embeddings for subgraph classification, disregarding the overall graph structure.
A.2.3. IMPLEMENTATION DETAILS
we set the number of iterations ř for PageRank 100, with the damping factor set to 0.85. Similar GLASS and SubGNN, our model pre-trains nodes to generate node features for real-world datasets. Additionally, global position encoding is added as the initial feature for all datasets. We calculate the vector differences node representations using a COO-formatted sparse adjacency matrix A, which significantly reduces memory usage. use classic loss functions for classification tasks: BCE loss for binary classification and cross-entropy loss for multi-class classification.
Algorithm 1 Global Position Encoding
Input: Graph G = (V, E)
Output: Global Position Encodings {p.lvev
1: R < (3)
2: Wij t R + (i,,j) E E
3: < arg max R(Co
4: G' + V.E.WW), W = {wi}}
5: T (6) do
6: for all
7: In distr
8: P, + hot(t.)
9: end for(p,loev
16


Reviews:
[{"review_id": "ut3HZ1sZS9", "reviewer": "Reviewer_FTVY", "summary": "The paper introduces a method called GPEN for Subgraph Representation Learning. It proposes the construction of a hierarchical tree to compute the Global Position Encoding (GPE) and introduces Boundary-aware Convolution (BWC) and tree-based Optional Tree Perturbation (OTP). These strategies aim to address two major challenges in graph representation learning: capturing structural relationships between distant nodes and preventing excessive aggregation of global structural information.", "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 your positive feedback and constructive remarks on our paper. Below, we provide a detailed response to your questions and comments.\n\n**[W1 and W3]**\n\nWe thank the reviewer for pointing out these notation issues throughout the paper. To clarify:\n- $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.\n- $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.\n- $\\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.\n- $\\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$.\n- $\\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$.\n\nWe will correct these notations in the revised manuscript and use more distinctive symbols to avoid confusion.\n\n**[W2]**\n\nOur 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.\n\nWe 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.\n\n**[W4]**\n\nWe thank the reviewer for the detailed statistical analysis. However, we respectfully argue that a holistic evaluation reveals significant advantages for GPEN.\n\nCrucially, 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.\n\nWhile 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).\n\n**[S1]**\n\nThank 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:\n\nFirst, 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.\n\nWe 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.", "claims_and_evidence": "The paper provides detailed theoretical analysis and validation for the GPE, BWC, and OTP in GPEN.", "methods_and_evaluation_criteria": "Experiments show that GPEN has better average performance and lower standard deviation. However, the experimental results are not significant, as detailed in [W4].", "theoretical_claims": "The paper proposes several theorems as theoretical support for the effectiveness of the modules in GPEN, and provides comprehensive proofs in the appendix.", "experimental_designs_or_analyses": "The paper demonstrates through experiments that the standard deviation of GPEN is significantly lower than other methods, indicating better robustness. However, several conclusions from the experiments are not significant, as detailed in comment W4.", "relation_to_broader_scientific_literature": "The paper identifies two major challenges in existing Subgraph Representation Learning methods: capturing structural relationships between distant nodes and preventing excessive aggregation of global structural information. It proposes to construct a hierarchical tree and designs the GPE, BWC, and OTP modules to address these challenges.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n\nThe paper provides detailed theoretical analysis and validation for each module.\n\nWeaknesses:\n\n[W1] In section 3.1.1, as the transition matrix of PageRank, why $M$ is $\\mathbf M_{ij}=\\frac{1}{d_i}$ instead of $\\frac{1}{d_j}$? Also, what is the initial value of $R$ in equation 3?\n\n[W2] Section 3.1.3 mentions that \"The insufficient number of subgraphs can affect the model’s stability.\" However, the tree perturbation module generates at most one new sample for each subgraph. Therefore, the total number of subgraphs is at most twice the original number. Is this sufficient to address the issue of insufficient subgraphs?\n\n[W3] In section 3.2, the notion in equation 12 is unclear:\n* What is $\\mathbf A$? It seems to be undefined in the paper.\n* What does the subscript $n$ in $\\mathbf H_n^{(l-1)}$ stand for? Is it a different matrix from $\\mathbf H^{(l-1)}$?\n* Is $\\mathbf W^{(l-1)}$ the edge weight of the weighted graph in section 3.1.1? If so, what does the superscript $(l-1)$ represent? The edge weight in section 3.1.1 seems to be a constant independent of the layer.\n\n[W4] In Table 1, the $p$-values comparing GPEN with S2N on all datasets are greater than 0.05, indicating non-significant differences. The same applies to the experiments in Table 3 and the ablation study in Table 4. The advantage of GPEN seems to lie only in its more stable performance and smaller variance.", "other_comments_or_suggestions": "In section 3.1.2, the global positional encoding groups nodes according to their depth in the tree, then encodes them directly into a 01 vector. It loses the information of its value. Especially considering that the edge weights and trees here are artificially calculated and constructed, the shortest path length on the tree may not represent real and accurate global information. Would it be better to use an encoding that retains the depth value of the nodes, such as the sin/cos function encoding designed for sequences in the classic \"Attention is all you need\"?", "questions_for_authors": "See above.", "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": "Zqc395CzOV", "reviewer": "Reviewer_2fVD", "summary": "This paper presents GPEN (Global Position Encoding Network), a novel approach for subgraph representation learning that addresses the limitation of existing methods which primarily focus on local neighborhood structures while overlooking global structural information. GPEN implements two key modules: (1) global position encoding, which leverages hierarchical tree structure to encode each node's global position, enabling the capture of structural relationships between distant nodes; and (2) boundary-aware convolution, which computes difference vectors between nodes to control information flow, selectively integrating global structural information while maintaining the unique structural patterns of each subgraph. Experiments show that GPEN achieves competitive or superior performance compared to state-of-the-art methods on eight public datasets.", "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 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:\n\n\n**Weakness 1 & Other Comments/Suggestions: Improving Figure Clarity**\n\n\nThank you for your suggestion regarding the color coding in the captions of tables. For the revised manuscript, we will:\n- Enhance the clarity of y-axis labels and line colors in Figure 4.\n- Add grid lines to facilitate easier interpretation of results in Figure 4.\n\nThese visual improvements will make our results more accessible and interpretable for readers.\n\n\n\n**Weakness 2: Methods for Automatic Threshold Determination**\n\n\nWe 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.\n\n\nIn 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:\n\n\n| Threshold c value | 2 | 4 | 6 | 8 |\n|---------|---------|---------|---------|---------|\n| ppi_bp | 0.611 | 0.622 | 0.644 | 0.633 |\n| hpo_metab | 0.638 | 0.610 | 0.603 | 0.598 |\n| hpo_neuro | 0.671 | 0.691 | 0.681 | 0.681 |\n| em_user | 0.876 | 0.903 | 0.912 | 0.902 |\n\n\nThis 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.\n\n**Question: Maximum Spanning Tree Performance Across Graph Types**\n\n\nThank you for this insightful question about the consistency of Maximum Spanning Tree (MaxST) performance across different graph structures.\nIn 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.\n\nThe 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.\"\n\nThe 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.", "claims_and_evidence": "The main claims of the paper are well-supported by theoretical analysis and experimental results. The authors claim that GPEN can effectively capture global structural information while preserving the unique features of subgraphs, which is supported by multiple theoretical analyses and relatively comprehensive experimental validation. Theoretically, the authors provide four theorems with proofs that analyze the bounded representation discrepancy, global position encoding distinctness, noise robustness of boundary-aware convolution, and generalization guarantees for tree perturbation. Experimentally, results on four real-world datasets and four synthetic datasets show that GPEN performs well on subgraph representation learning tasks. The ablation study (Table 4) demonstrates the contribution of each component, validating the complementary nature of the three modules: Global Position Encoding (GPE), Boundary-Aware Convolution (BWC), and Optional Tree Perturbation (OTP).", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate for the research problem. The authors use the same datasets and data splits as previous work, ensuring comparability of results. The evaluation uses micro-F1 scores as metrics, which is a common measure for subgraph classification tasks. Experiments are conducted on various datasets with different characteristics, including molecular biology, clinical diagnostics, and user profiling datasets from real-world scenarios, as well as synthetic datasets designed to test the ability to recognize different structural features. Notably, the authors explore the impact of different tree construction algorithms (Table 6), demonstrating the superiority of the Maximum Spanning Tree algorithm, which enhances the credibility of their method selection.", "theoretical_claims": "The theoretical claims in the paper are supported by sound mathematical proofs. Section 4 provides four core theorems: Theorem 4.1 proves that the discrepancy between GPEN representations and standard GNN representations is bounded; Theorem 4.2 establishes that global position encoding effectively distinguishes nodes with different connectivity patterns; Theorem 4.3 analyzes the noise robustness of boundary-aware convolution, proving it achieves higher signal-to-noise ratio compared to standard GNN aggregation; and Theorem 4.4 provides generalization bounds for the tree perturbation technique. The proofs are elaborated in Appendix A.1 with rigorous derivations using appropriate mathematical tools such as Lipschitz continuity, Perron-Frobenius theorem, and PAC-Bayes framework.", "experimental_designs_or_analyses": "The experimental design is reasonably sound. The authors adopt the same datasets and data splits as the baselines, facilitating fair comparison. The experiments cover multiple aspects: performance comparison on real-world datasets (Table 1), controlled experiments on synthetic datasets (Table 3), ablation studies (Table 4), and hyperparameter analysis. The authors explore the impact of different tree construction algorithms (Table 6), comparing Breadth-First Search Tree, Depth-First Search Tree, Minimum Spanning Tree, and Maximum Spanning Tree algorithms.", "relation_to_broader_scientific_literature": "The paper has connections to the scientific literature. In Section 6, the authors review related work, including the development of Graph Neural Networks and advances in subgraph representation learning. The paper discusses existing methods such as SubGNN, GLASS, SSNP, and S2N, and explains how GPEN attempts to address some of the challenges faced by these methods from the perspectives of global structural information and selective information integration. This literature connection helps to understand the research background and contributions of GPEN.", "essential_references_not_discussed": "The paper discusses most of the relevant important references. The authors' review of related work covers the progression from fundamental work on Graph Neural Networks to advances in subgraph representation learning methods.", "other_strengths_and_weaknesses": "Strengths:\n1. The global position encoding proposed in GPEN is a novel approach that systematically captures multi-hop relationships between nodes in a graph.\n2. The paper provides comprehensive and rigorous theoretical analysis, proving the effectiveness and stability of the method.\n3. Experiments are conducted on multiple datasets, validating various aspects of the method through ablation studies and hyperparameter analysis.\n4. The paper mentions using COO-formatted sparse adjacency matrices to calculate difference vectors of node representations, demonstrating consideration for memory efficiency.\n\nWeaknesses:\n1. Some figures' labels and color choices could be clearer, particularly the visualizations in Figure 4.\n2. The paper discusses the impact of threshold c but lacks methods for automatically determining the optimal threshold.", "other_comments_or_suggestions": "Some figures in the paper could be improved, such as the y-axis labels and line colors in Figure 4. Consider adding grid lines or using different line types to distinguish different data series, which would help readers better interpret the results.", "questions_for_authors": "Among the different tree construction algorithms, the Maximum Spanning Tree performs relatively well. Is this advantage consistent across all types of graph structures, or is it more significant for certain types of graphs (such as sparse or dense graphs)?", "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": "YS9hcrSfQA", "reviewer": "Reviewer_jSEe", "summary": "This paper presents GPEN, a novel method for subgraph representation learning that addresses two key challenges: capturing structural relationships between distant nodes and preventing excessive aggregation of global structural information.", "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 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:\n\n**W1: Concerns about tree-based encoding and complex graph topologies**\n\nWe 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:\n\n| Dataset | Nodes | Edges | Avg. Degree | Subgraphs | Avg. Nodes per Subgraph |\n|---------|-------|-------|-------------|-----------|-------------------------|\n| Density | 5,000 | 29,521 | 5.90 | 250 | 20.0 ± 0.0 |\n| Cut Ratio | 5,000 | 83,969 | 16.79 | 250 | 20.0 ± 0.0 |\n| Coreness | 5,000 | 118,785 | 23.76 | 221 | 20.0 ± 0.0 |\n| Component | 19,555 | 43,701 | 2.23 | 250 | 74.2 ± 52.8 |\n| PPI-BP | 17,080 | 316,951 | 18.56 | 1,591 | 10.2 ± 10.5 |\n| HPO-METAB | 14,587 | 3,238,174 | 222.0 | 1,400 | 14.4 ± 6.2 |\n| HPO-NEURO | 14,587 | 3,238,174 | 222.0 | 4,000 | 14.8 ± 6.5 |\n| EM-USER | 57,333 | 4,573,417 | 79.77 | 324 | 155.4 ± 100.2 |\n\nNotably, 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.\n\nThis 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.\"\n\n[1] Alsentzer et al., \"Subgraph Neural Networks\", NeurIPS 2020\n\n[2] Wang & Zhang, \"Glass: GNN with labeling tricks for subgraph representation learning\", ICLR 2022\n\n[3] Jacob et al., \"Stochastic subgraph neighborhood pooling for subgraph classification\", CIKM 2023\n\n[4] Kim & Oh, \"Translating subgraphs to nodes makes simple GNNs strong and efficient for subgraph representation learning\", ICML 2024\n\n**W2: Request for concise theoretical summaries in main text**\n\n\nWe appreciate this constructive suggestion. Our theoretical analysis establishes four key properties: \n1. Theorem 4.1 proves the controllability of GPEN's representations\n2. Theorem 4.2 proves the distinctiveness of global position encoding\n3. Theorem 4.3 proves that the boundary aware convolution module can suppress noise propagation\n4. Theorem 4.4 proves that the empirical distribution covers a wider range after perturbation.\n\nIn 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.\n\n**W3: Discussion of potential underperformance scenarios**\n\nWe 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.\n\nOur 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.\n\n\n**Typo correction**\n\nThank you for pointing out the typo on line 804. We will correct \"real-work datasets\" to \"real-world datasets\" in the revised manuscript.", "claims_and_evidence": "yes, the submission is supported by clear and convincing evidence", "methods_and_evaluation_criteria": "yes, the proposed method makes sense for the graph learning challenges.", "theoretical_claims": "yes, the theoretical proof of the paper seems correct.", "experimental_designs_or_analyses": "yes, the experiment section is well-designed.", "relation_to_broader_scientific_literature": "This paper addresses existing challenges in a more novel way", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "**Strengths:**\n\nS1. The paper provides rigorous theoretical analysis (Theorems 4.1–4.4) to validate its claims, such as bounded representation discrepancy and noise robustness, which adds intellectual depth to the innovation.\n\nS2. The introduction provides a clear overview of the limitations inherent in existing methods, which highlights the key challenges capturing distant relationships, avoiding over-aggregation. Figure 1 enhances this by visually contrasting fraudulent and legitimate subgraphs, making the motivation intuitive.\n\n\n**Weaknesses:**\n\n\nW1. Although the tree-based encoding approach introduces an innovative perspective, its fundamental assumption may limit its applicability, such as a tree structure can sufficiently capture the intricacies of complex graph topologies. Specifically, in graphs characterized by high cyclicity or dense interconnectivity, the hierarchical simplification imposed by tree-based representations could lead to an oversimplification of relational patterns, potentially compromising the model's ability to generalize effectively.\n\nW2. While it is appropriate to provide the detailed theoretical proofs in appendix, it would be beneficial to provide a concise summary of the key insights in the main text, such as the mechanism by which boundary-aware convolution enhances the signal-to-noise ratio. This approach would significantly improve the accessibility and clarity of the work for readers. \n\nW3. There is little discussion of scenarios where it might underperform (e.g., sparse graphs, small subgraphs). This could highlight limitations and guide future work.\n\nTypo: Line 804 'real-work datasets' -> 'real-world datasets'", "other_comments_or_suggestions": "Please answer W1-W3", "questions_for_authors": "Please answer W1-W3", "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": "vY6NQtWlss", "reviewer": "Reviewer_QQCz", "summary": "The paper introduces GPEN (Global Position Encoding Network), a novel algorithm for subgraph representation learning. The algorithm addresses the task of predicting labels for subgraphs within a large input graph, given a set of labeled subgraphs. GPEN innovates by moving beyond the limitations of existing methods that primarily focus on local neighborhood structures. It achieves this by incorporating global structural information through a novel tree-based global position encoding for each node. This encoding is combined with a boundary-aware convolution module and an optional tree perturbation technique. The authors support their approach with both empirical evaluations demonstrating effectiveness and theoretical analyses to justify the method.", "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 deeply appreciate your thoughtful review and positive assessment of our work. Below we will respond to the raised questions.\n\n## W1 and S2: Visualization of Learned Embeddings\n\nWe 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.\n\n## S1: Hyperparameter Analysis Summary\n\nThank 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:\n\n- 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.\n\n- 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.\n\n- 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.\n\n- GPEN demonstrates reasonable robustness to hyperparameter changes within these ranges, with different datasets exhibiting varying sensitivities based on their inherent structural properties.\n\n## Q1: Applicability to Directed Graphs\n\nGPEN can be naturally extended to directed graphs. Below we elaborate on how each module can be adapted:\n\nOur 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.\n\nFor 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.\nOnce 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.\nFor 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.\n\nThese 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.", "claims_and_evidence": "The paper's main claims are well supported by convincing evidence. Experimental results show that GPEN outperforms existing methods across various datasets, while theoretical analysis validates the method's soundness from multiple angles. In particular, Figure 1 clearly demonstrates the limitations of relying solely on local structural information and how GPEN addresses this issue by capturing global structural information.", "methods_and_evaluation_criteria": "The proposed methods are innovative and well-justified. GPEN cleverly utilizes tree structures to encode global position information, while the boundary-aware convolution module effectively balances local and global information. The experimental evaluation employs widely recognized datasets and baseline methods in the field, with a well-designed and comprehensive evaluation protocol.", "theoretical_claims": "I carefully checked the correctness of the theoretical claims, including the theorems and proofs related to bounded representation discrepancy, global position encoding distinctness, noise robustness, and the generalization bound. They are robust and clearly presented, providing a strong theoretical foundation for the GPEN algorithm. The inclusion of these formal analyses significantly strengthens the paper.", "experimental_designs_or_analyses": "The experimental design is sound and effective. Extensive experiments on eight public datasets, with results averaged over 10 different random seeds, provide reliable statistical significance. The hyperparameter analysis and ablation studies effectively validate the contribution of each module.", "relation_to_broader_scientific_literature": "The work is well-connected with existing research. The paper clearly identifies limitations in existing methods and proposes effective solutions. GPEN's main innovations - global position encoding and boundary-aware convolution - represent significant improvements and additions to prior work.", "essential_references_not_discussed": "I did not find any essential references that were missing or overlooked in the paper's discussion of related work.", "other_strengths_and_weaknesses": "Strengths：\n\nThe core idea of tree-based global position encoding is novel and effective.\nRobust theoretical analysis strengthens the paper.\nThe paper is well-structured and easy to follow.\n\nWeaknesses:\n\nVisualizations of learned embeddings could further illustrate the effectiveness of GPEN.", "other_comments_or_suggestions": "1. Although the paper includes hyperparameter analysis, a sentence or two summarizing the general robustness or sensitivity of the key hyperparameters within the main body (perhaps in the experimental section) would be helpful for readers. This would provide a concise summary without requiring a deep dive into the appendix.\n\n2. Adding visualizations of the final learned embeddings could highlight the effectiveness of the approach to a reader.", "questions_for_authors": "The current work primarily addresses subgraph representation learning on undirected graphs. Could the authors discuss the applicability of GPEN to directed graphs (e.g., follow relationships in social networks, citation links in academic networks)? Specifically, we are interested in how edge directionality would be handled in the tree construction phase and what modifications to the maximum spanning tree algorithm would be necessary to accommodate directed scenarios. The answer would help understand GPEN's potential for broader applications in directed graph domains.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces GPEN (Global Position Encoding Network), a novel method aimed at enhancing subgraph representation learning (learning the representation of a subgraph in a graph) by effectively capturing global structural information through hierarchical tree-based position encoding and a boundary-aware convolution module. The reviewers generally appreciate the clear motivation, rigorous theoretical analysis, and thorough empirical validation across diverse datasets. Two reviewers recommended acceptance (score 4), while two give weak accept (score 3). Given the important problem of subgraph representation learning, high-quality theoretical contributions, comprehensive empirical validation, clarity of writing, and thorough responses addressing reviewer concerns, the consensus is to recommend acceptance of the paper, subject to the inclusion of the promised clarifications and improvements in the final manuscript.
Decision: Accept (poster)