Adjacency Search Embeddings
Authors: Meher Chaitanya
Kshitijaa Jaglan
Ulrik Brandes
Venue: Accepted by TMLR ()

Abstract: In this study, we propose two novel Adjacency Search Embeddings that are inspired by the theory of identifying s-t minimum cuts: Maximum Adjacency Search (MAS) and Threshold-based Adjacency Search (TAS), which leverage both the node and a subset of its neighborhood to discern a set of nodes well-integrated into higher-order network structures. This serves as context for generating higher-order representations. Our approaches, when used in conjunction with the skip-gram model, exhibit superior effectiveness in comparison to other shallow embedding techniques in tasks such as link prediction and node classification. By incorporating our mechanisms as a preprocessing technique, we show substantial improvements in node classification performance across GNNs like GCN, GraphSage, and Gatv2 on both attributed and non-attributed networks. Furthermore, we substantiate the applicability of our approaches, shedding light on their aptness for specific graph scenarios.

Published in Transactions on Machine Learning Research (12/2024)
Adjacency Search Embeddings
Mcher Chaitanya
mypindiirohu@Behha.cck
ETH Zürich
Kshitijaa Jaglan University of Zürich
kjaglan@ifi.cm uzh. ch
Ulrik Brandes ETH Zürich
wbrandes@clka.ck
Reviewed on OpenReview: https: // openreview. net/ forum? id= CDN5cFTNaa.
Abstract
In this study, we propose two novel Adjacency Search Embeddings that are inspired by the theory of identifying s-t minimum cuts: Maximum Adjacency Search (MAS) and Threshold- based Adjacency Search (TAS), which leverage both the node and subset of its neighborhood to discern a set of nodes well-integrated into higher-order network structures. This serves as context for gencrating higher-order representations. Our approaches, when used con- junction with the skip-gram model, exhibit superior effectiveness in comparison to other shallow embedding tochniques in tasks such as link prediction and node classification. By incorporating our mechanisms as preprocessing technique, we show substantial improve- ments in node classification performance across GNNs like GCN, GraphSage, and Gatv2 on both attributed and non-attributed networks. Furthermore, we substantiate the applicability of our approaches, shedding light on their aptness for specific graph scenarios.
1 Introduction
Node embeddings are concise numerical representations of individual nodes in a network, capturing their structural and relational significance. These embeddings condense complex structural information into compact vectors for facilitating efficient downstream tasks such as node classification, link prediction, and other machine-learning applications. These embeddings place nodes in a continuous vector space, allowing us to extract meaningful features for lasks like node classification and link prediction in machine learning. Inspired by Natural Language Processing (NLP) techniques, node embedding methods like 9kipGram-Word2V Word2 Mikolov et al. 2013b al use algorithms to capture intricate patterns and relationships within graph structures.
These NLP algorithms excel in generating embeddings that capture semantic relationships and contextual muances within textual data. The SkipGram model focuses on predicting context words those expected to appear in close proximity given a specified target word. Shallow embedding techniques for graphs generate sequences of nodes using methodologies like random walks Perozzi et al. (2014;; Grover Leskoved (0066 or auto-encoding adjacency vectors Wang et al. (2016) and employ the SkipGram model to generate vector representations. The resulting embeddings aim encode each node in graph into a low-dimensional vector, where the geometric proximity of vectors reflects the similarity relatedness of the corresponding nodes in the network. By capturing both local and global graph structures, node embeddings prove instrumental in enhancing the efficiency and effectiveness of downstream machine lcarning tasks Xu 22021) These shallow embedding techniques, though computationally efficient, sulfer from the drawback of lacking parameter sharing during training. Each node has a unique embedding vector that is learned independently. This lack of parameter sharing can lead to overfitting, especially when dcaling with sparse graphs or limited training data Hamilton et al. (2017b). Recently, Graph Neural Networks (GNNs) have shown great promise in learning representation ions by sharing parameters across node neighborhoods for graph-structured data for

---

Published in Transactions on Machine Learning Research (12/2024)
better generalization. However, training GNNs on large graphs can be computationally challenging due to the exponential growth of node neighborhoods with increasing network depth Hamilton et al. (2017a).
Neighbor sampling approaches have emerged as a key technique to address this issue by approximating the node neighborhoods during training. They enable scalable GNN training on large-scale graphs that would otherwise be intractable due to memory constraints. Early works like GraphSAGE Hamilton et al. (2017a) introduced neighborhood sampling as a way to make GNN training feasible on large graphs. Subsequent rescarch has explored various sampling strategies, including layer-wise sampling, importance sampling, and variance reduction techniques Chen & Zhao 20188: Zou et al. (201)). Recent advancements like GraphSAINT Zeng et al.] (2019) and ClusterGCN [Chiang et al. (2019) have further demonstrated the effectiveness of neighbor sampling in achieving state-of-the-arl performance on large-scale graph benchmarks. The continued development and adoption of neighbor sampling methods are crucial for unlocking the full potential of GNNs in real-world applications with massive graphs.
Present work in a nutshell: In this research, we introduce two methods, Maximum Adjaceney Search (MAS) and Thrresooldbased Adjacency Search (TAS), aimed at capluring sequences of well-conmected nodes from a given set of nodes. The TAS approach employs an extended version of the well-known Breadth First Search (BFS) Algorithm, called Delayed-BFS. This algorithm takes a set of vertices, S, and a threshold as input to generate a sequence of nodes that are structurally well-connected, potentially within a higher-order network topology, to S. These sequences can be fed to the SkipGram- -Wrrddeee model or can be used as a preprocessing or sampling mechanism in existing GNNs to identify structurally influential local neighborhoods for feature aggregation around node to generate node embeddings. The MAS approach is a dynamic variant of TAS. Our goal in this paper is not to explicitly identify specific structures like motifs, graphlets, or simplicial complexes Vishwanathan et al. (2010): ; Rossi et al. (2018): Piaggesi et al. (0022) but rather generate sequences of tightly connected nodes in cohesive sub-structures of the network.
Main Contributions:
Novel sampling Approaches: We propose two variants of Adjacency search-based methods, Maximum Adjacency Scarch(MAS) and Threshold-based Adjacency search (TAS) embeddings, which are efficient,, effective, and highly scalable algorithms for feature learning on graphs. These approaches involve constructing sequences as neighborhood contexts, capturing nodes within the cohesive sub-structures in the network topology.
Non-random walk techniques: Our approach involves executing Breadth-First Search (BFS) not from a single node but rather from a subsct of nodes simultancously based on certain threshold criteria to determine when a node can be marked as visited. This unique methodology enables the generation of node sequences that inherently capture complex topological patterns such as triads, quads, simplicial complexes, and motifs. Our path-based approaches differ from the random walk approaches and can be considered as specific instances of k-th order random walks for any k N
Empirical Performance: Our proposed algorithms significantly enhance link prediction accuracy when integrated with the SkipGram model, out outperforming the best results of other shallow embedding techniques by an average of 6.97%. Furthermore, our approach serves as an effective local neighborhood sampling tochnique for message aggregation GNNs, loading to improved performance across various architectures, including GCN, GraphSage, and GATv2, for both attributed and att-ibtrb graphs Notably, in non-attributed networks, our sampling mechanism demonstrates up to 12. 1 % efficiency improvement compared to trainable node embeddings in GNNs, highlighting its effectiveness in identifying structurally influential neighborhoods for aggregation.
AA higher-order random walk typically retains some memory of previous steps, opposed to first-order Markov process. While our approaches not directly mesery-bused walk in the strictest sense, its choice of nodes (bused maximum adjacency threshold) implicitly reflects past choices. This makes them behave similarly to higher-order random walk, where past decisions influence the current selection
?trainabee node embeddings refer to the node embeddings which can be initialized with any randomly initialiiiinnonnnnon methods https://ppytttchoorg/
2

---

Published in Transactions on Machine Learning Research (12/2024)
Applicability; We discuss the applicability of our approach and identify scenarios where it may not be well-suited for downstream tasks in Appendix D
Preliminarics Here, we present a brief overview of Maximum Adjacency Search (MAS), an effective method for determining s-t minimum cuts. MAS Stoer & Wagner (1997) is a widely used algorithm in graph theory, particularly for identifying minimum cuts and analyzing flow networks. In the context of an s-t minimum cut, the goal is to partition the graph into two disjoint sets: one containing the source vertex s, and the other containing the target vertex t. The objective is to minimize the total weight of the edges that connect these two sets. MAS works by selecting vertíces based on their adjacency to already-selected vertices. Specifically, in cach iteration, a vertex with the highest adjacency among the unselected vertices is added to the current set. This iterative process continues greedily, including the vertex with the most adjacent neighbors already in the set and ensuring that critical vertices and edges are efficiently identified for the partition. This houristic not only facilitates efficient identification of the minimum cut but also tends to form tightly connected communities around the seed set S. The likelihood of selecting a cut-edge is minimized each iteration by choosing highly connected vertex, which helps avoid cutting through critical edges prematurely and promotes the formation of cohesive vertex groupings.
Motivation Our approaches are motivated by Maximum Adjaceney Search, which is a well-known s-l minimum cut approach. They are built on the assumption that the probability of future connections between two different nodes is higher in well-connected structures. Thus our methods are based on the assumption that the likelihood of future connections between two distinct nodes is higher within well-connected substructures. Unlike random walks, which sample sequences across the entire graph, our approaches leverage MAS and its generalized variants to generate targeted sequences that capture well-conmected local neighborhoods around each node. This approach reduces training time, fewer sequences are generated compared to random bask- methods. Furthermore, in contrast to existing higher-order techniques, our methods efficiently identify these well-connected regions without explicitly searching for combinatorial structures, such as cliques.
2 Related Work
Over the years, various algorithms and techniques have been proposed for generating node embeddings, each with its strengths and applications. These can be broadly classified into three major categories: Matrix Factorization Approaches, Random Walk Approaches, and Graph Neural Networks (GNNs). This section briefly overviews various embedding approaches specifically tailored for non-attributed graphs
Matrix Factorization Approaches: Early techniques for learning representations through matrix factor- izations draw significant inspiration from dimensionality reduction methods Belkin & Niyogi (2001): Kruskal (1944). Methods falling within this category construct a high-order proximity matrix using transition proba- bilities and subsequently engage in factorization processes to derive node embeddings. Notable approaches, such as Laplacian Eigen Maps Belkin & Niyogi (2001) and Locally Linear Embeddings (LLE) Rowes] (2000), operate based on this foundational principle. HOPE (High-Order Proximity preserved Embedding) Ou et al. (2016) strives to maintain higher-order proximity information within the learned embeddings. It achieves this objective by performing a matrix factorization strategy to capture higher-order proximities in the form of a similarity matrix. By decomposing this matrix, HOPE generates embeddings that preserve first and higher-order relationships within the graph. The HOPE algorithm supports general similarity measures, distinguishing it from other approaches. For instance, the Graph Factorization algorithm Ahmed et al. (2013) considers the first-order neighborhood as similarity measure, while GraRep Cao et al. (205)) operates with higher-order similarity, such as k-th length shortest paths between two nodes (A*). It's important to note that these approaches may not be suitable for large graphs because their loss functions rely on the entire adjacency matrix Xu (021))
Random Walk Approaches: A significant number of recent successful methodologies utilize random walk statistics to learn node emboddings. The underlying concept is to ensure similar embeddings for nodes that co-occur during random walks Goyal & Ferraral (2018). The DeepWalk algorithm |erozzi et al. (2014), for instance, utilizes random walks to explore the graph and subsequently applies skip-gram continuous
3

---

Published in Transactions on Machine Learning Research (12/2024)
bag-of-words models for generating embeddings. Node2Vee Grover & Leskovec (0166) extends DeepWalk by incorporating second-order random walks. Notably, Node2Vec introduces flexible parameters, the "return parameter' and the"in-out parameter, allowing for a trade-off between exploration and exploitation during the generation of sentences of nodes through random walks. Finc-tuning these paramcters enables Nodc2Vec to produce embeddings that emphasize either local neighborhood structures (homogeneous neighborhoods) or more extensive structural information (heterogeneous neighborhoods). Various extensions to these shallow embedding methods have been proposed in the literature Chen al. (2018a); Perozzi et al. (2017) Chamberlain et al. (2017). LINE Tang et al. (2015) is another approach often compared with the performance of DeepWall and Node2Vec. LINE aims to discover d-dimensional representation for each node by considering first and second-order graph proximities. It is similar to Deep Walk when the size of the vertices context is set to one Qiu et al. 2018). Recently, Pimentel et al. (2019) proposed neighborrhood-based node embeddings (NBNE) that used ego-centric representations of nodes instead of random walks for learning node representations. Their approach attains superior performance compared to Node2Vec and SDNE Wang al. (2016) on prediction and classification tasks. The approaches Node2Vec, Walk,alk, and NBNE can be considered neighborhood search- based embedding approaches for node.
Further related work pertinent to GNNs tailored for non-attributed networks is provided in Section 5.1
3 Adjacency Search Based Embeddings
Within graphs, approximating a node's context often involves constructing or sampling sequences. For example, Node2Vee employs sccond-order biased random walks Grover & Leskovec (2016). while DeepWalk utilizes uniform random walks Perozzi al. (2014) for generating these sequences. In this section, we introduce two novel mechanisms for generating sequences to serve contexts for nodes. Before delving into approaches,
present the relevant notation used in this paper. We represent the graph by G(V, E) where V and E are the sets of vertices and edges, respectively. For case of notation, let n and m represent the cardinality of the vertex and edge sets, respectively. The open and closed neighborhoods of a verlex v are denoted by N(v) and N(u]. We denote the set of positive integers by Z+. We use node and vertex interchangeably in this paper.
3.1 Maximum Adjacency Search EMbee-iimsddiigg
This approach draws inspiration from the Maximum Adjacency Dejjacency/Cardinallnn Cardinality search technique, which is employed for identifying an s-t minimum cut in a graph Stoer & Wagner (1977) ; Cai & Matula (1993). It is a recursive algorithm where, at each iteration, the objective is to identify a tightly connected vertex to the set of well-connected vertices and perform a merge operation to identify the s-l minimum cut. Incorporating the vertex with the highest degree of connectivity into the existing set of vertices reduces the likelihood of encountering an edge belonging to the minimum cut.
approach provided in Algorithm works similarly by constructing sequences of well-connected and cohesive nodes for every vertex v, together with a subset of its neighborhood, S e N(o)- This is attained by iteratively adding vertex u E V that is tightly connected (maxinally connected) to the sequence set S (line 11 in Algorithm D This process is repeated until the desired Walk Length is attained. The MAS-Embeddiing approach relies on the following parameters (all the parameters are in Z+):
Our
Number of Neighbors (k): l denotes the cardinality of the seleeted neighborhood of v E V.
Number of Permulations (p): This parameter assists in capturing diversified imumddiate neighborhoods of a vertex v, which in turn facilitates the identification of a cohesive subset of nodes.
Walk Length (I): This parameter refers to the sequence length that is generated for every vertex in the graph.
Window Size (w): This refers to the context window size used by the SkipGram model.
Dimensions (d): This parameter represents the dimension of feature representations.
4

---

Published in Transactions on Machine Learning Research (12/2024)
Algorithm 1 MAS-Embeddings
1: Input: Graph G, Walk Length I, Window size w, Dimension d,
# #Neighbors k, #Permutations
2: for all in graph.nodes() do
3: repeat times
4: neighbors + len(neighbors)/
B random permutation of the neighbors vertex
num hum__sqqennces
-...nuummsseeuueee for i l....num sequences do
S
8:
S.inser((v)
S.inser((neighborss) k... (k 1)])
> insert k neighbors of node v into the set S
10:
repeat
11:
find the maximally adjacent u to S S.insert(u) until (Jen(S) 1) sequences.ineerte
12:
13:
14:
15: end
16: f = train (w, d, sequences)
b train the sequences using skip-gram model
17: return f
3.2 Threshold-basee Adjacency Search (TAS)-Embeddiing
Here, we present the TAS embeddings, a generalized variant of the MAS embeddings approach. Let 0 E R" be a vector of thresholds, where each element 0, denotes the threshold for vertex v E V, and 0g E Z The transition state of a vertex v from non-visited visited occurs when at least O, of its neighbors are already visited. A sequence for node is the set of vertices visited by together with subset of its neighbors S C M(). For the rest of the paper, consider 0 to be a constant, Le., all vertices have uniform thresholds.
3.2.1 Generation of Sequences
The Delayed-BF's approach, outlined in Algorithm takes a vertex v, a subset of neighborhood 5 N and threshold 0 as the imput to produce sequence of nodes that are cohesive and well-connected to S. The thresholds of all u E V S are set to the minimum of their degree and f. This is because the maximum be visited is 6, degree(u). The threshold parameter ensures that the vertex
threshold at which u visit is delayed till it acquires sufficient reinforcement from its neighbors. When f = 1, (FF(S) behaves similarly to traditional BFS(S), encompassing immediate neighbors and their subsequent neighbors in the sequence. The distinction from traditional BFS becomes apparent when 0 2 2. For 0 = 2, every vertex noods reinforcement from least 2 visited neighbors for to be visited. To illustrate the operation of Algorithm 3. consider Figure [ where for 0 = Delayed- 2, does not visit any nodes. In contrast, Belayed-BFS(2,PF) 4, 6) will visit. (5,3, 7). Similarly, Delayed-BFS(1.3) with 0 = 2 will visit the set of vertices {2, 4, 5, 6, 7, 8, 9}. The set of sequences of nodes generated for different thresholds adheres to the following hierarchy:
sequenceg=1 2 sequenceg=2 2 sequencee=3""
Thus, the generated sequences constrained to visit specific cohesive structures (including higher-order structures such motifs, etc) with increase in thresholds 0. Notice that the MAS Embeddings approach (Algorithm M can be interpreted as dynamic threshold-based adjacency scarch embedding where the threshold of the node u that is being added to the sequence S is equal to the cardinality of the set of edges between u and S, i.e. [E(u, S)). ()). As illustrated, TAS- Embeddins (Algorithm 2 produces distinct sequences by employing the Delayed-BFS approach for various subsets of node and its neighborhood. Apart from the set of parameters mentioned in Section 3.1 the Algorithm relies on the threshold parameter, which is a constant in our experiments.
5

---

Published in Transactions on Machine Learning Research (12/2024)
Figure 1: An example network to demonstrate the functioning of Delayed-BFF approach (3
A
Algorithm TAS-Embeddings
Input: Graph G, Threshold 0, Walk Length I, Window size w, Dimension d, #Neighbors k, #Permutations p
for all in graph.nodes() do for threshold <- 1...0 do
4: repeat times
5: neighbors + cermuto(u.ncighbors]]
b. random permutation of the neighbors a vertex
num sequences +- len len (neighhorss)/
for i 1...num sequencee do S+Ø
S.insert(v)
10:
S.insert(neigghooss) k... (k 1)]) sequence + (E S, 0,
insert & neighbors of node into the set S D generate the threshold based sequences
11:
12:
13:
end
14: f= train (w, d, sequences)
train the sequences using skip-gram model
15: return f
Algorithm Delayed-BFS
1: Input: Graph G, sequence S, threshold 8, Walk Length
2: Initialization: Queue I; Vu $ S T[u] = min(degree(u)).)) Tlu E S] =0
enque
repeat
vertex i dequeue(I) sequennce.nserrtf
7: for all u E N[i] do if & then decrement T[u] if T[u]== == 0 then enqueue(I,
8:
10:
11:
12: until (I is empty) or (len(sequence) = I)
13: return sequence
3.3 Shallow Embedding Learning Framework
Let f V gd be the function that maps nodes to d-dimensional feature representations that we intend learn for downstream tasks. Let denote the of sequences generated by Algorithm g We adopt the standard feature learning framework where the representations are trained by maximizing the log probability of predicting node occurrence in sequence S conditional on another node and its representation

---

Published in Transactions on Machine Learning Research (12/2024)
Hamilton et al. 2017b). This is expressed as:
max log Pr(s(f(c))
(1)
ΦEV
where Pr the probability measure. under the standard assumptions of conditional independence to ensure tractability, we get
Pr(s)f(u)) P(((
Modeling the conditional likelihood as softmax parametrized by feature vectors:
e110,11))
Pr(i E s)f(u)) Eu e(f()..00))))
where f(v)) represents the dot product between the feature representation of nodes and v. By optimizing the log probability equation [ the algorithm maximizes the predictability of a node in the generaled sequence given another node j, thereby creating node embeddings in which nodes co-occurring in sequences have similar representations. This optimization is accomplished using stochastic gradient descent. with negative sampling Mikolov et al. (0013b).
3.4 Time Complexity
In this section, we assess the time complexity of our proposed embedding approaches. Consider graph G with n and m representing the cardinalities of the vertex and edge sets. Let F(()) denote the cardinality of the set of odges associated with the vertex v. The maximum degrce in the graph is denoted by A. Let S be the set comprising of the node and a subset of its neighborhood for which a sequence is generated (Algorithm [ We create A buckets where vertices are distributed in these buckets according to the count of their adjacencies with N[S]. Notice that, under this construction, adding vertex to set S necossitates at most E(u) updates (moving a vertex from one bucket to another) and identifying the next maximum adjacent vertex to [[S] involves constant look-up (from the highest bucket). The time complexity for generating (nn) sequences using Algorithm is given by:
deufe)
I-1s]
E(S) +
E(ug)
a=l
j=1
where Uj is the 5th vertex added to the set S (sequence). The equation evaluates to O(n + m) (since (1.p.k] k) E O())). The time complexity of SkipGram-Word2Wee logarithmic on the size of vocabulary (i.c., on the vertex set [V] Mikolov et al. (2013a): Pimentel et al. (2018). Thus, the overall time complexity of the Maximum Adjacency Search embeddings (Algorithm) [ is bounded by O(nn m) log n). A similar analysis applies Threshold-based Adjacency Search Embeddings (see Algorithm 2. In practice, MAS outperforms TAS in computational efficiency due to its significantly smaller set of hyperparameters, which results in reduced number of generated sequences. Since walk lengths are bounded by constant, the space complexity is linear in the number of vertices. Further details on the scalability of MAS and TAS approaches are provided in the Appendix A
is linear on the number of sentences and
4 Empirical Evaluation with other Shallow Embedding Techniques
We assess the feature representations derived from MAS and TAS embeddings in the context of standard supervised learning tasks: link prediction and node classification. We utilize datasets to evaluato the performance of our approaches against other shallow embedding methods. The statistics of these six graph datasets employed for evaluation outlined in the Appendix B Table

---

Published in Transactions on Machine Learning Research (12/2024)
We assess the efficacy of our proposed approaches in comparison to shallow embedding approaches like Node2Vec, DeepWalk, and NBNE (Results regarding the comparison with GNNs are detailed in Section As outlined below, these methods are executed with a varied range of hyperparameters (with Dimensions, d, uniformly set to 128 for all approaches). The best-performing bascline is used for comparison.
Baselines:
Hyperparameter tuning systematically explores parameter values within a designated grid. Specifically, the parameters and undergo optimization on the validation set through an exhaustive grid search, considering values from the set [0.1, 0.2....... ,,22....,1.. 1, 4]. The window size, denoted as I, is selected from the set of values {5, 10, 15, 20). The walk lengths are chosen from the range [10, 80] in increments of 10, and the number of random walks per node is set to 10.
Vec Grover & Leskoved 2016):
Deep Walk Perozzi et al. 2014): The sampling strategy can be seen as a special case of node2vec with p = q =. The rest of the parameter configurations are similar to Node2Vec.
NBNE Pimentel et al. 2019): NENE uses a permutation parameter (ø) to capture diversified immediate neighborhoods. we vary & from to 20, and the window size is set to the subset of the neighborhood (varied from 3 to 10) that is chosen for representation (as suggested in the paper).
Parameters for MAS and TAS: The parameters for MAS and TAS described in the Algorithms and are initialized the following values.
Number of Neighbors (k): In our experiments, we vary k from 1 to 10. For graphs having higher average degrees (such as Facebook and email), we vary the range of number of neighbors (k) parameter from 1 to 20.
Number of Permutations (p): In our experiments, p is small constant, and vary it from 1 to 8.
Walk: Length (I): In our experiments, we vary this paramcter from 10 40 steps of 5.
Window Size (w): This chosen from the set of values {5, 10, 15, 20).
Dimensions (d): For experimental purposes, we set d = 128.
Threshold (f): For our empirical analysis, the threshold parameter, 0 Z+, is varied in the range of 0 E [1.8).
Link Prediction Task: In the context of a network, link prediction tasks involve predicting the likelihood of the existence of a link (edges) between pairs of nodes based on the observed network topology and associated features Lü & Zhou (011). Node embeddings are exlended to edge embeddings using the operators Hadamard (0), 12, /1, and Average. Further description of these operators is provided in the Appendix, Table Subsoquently, a logistic classifier is trained these edge embeddings to identify the potential presence of edge in the network. For training both Maximum Adjacency Search (MAS) and pirrshold-based Adjacency Search (TAS) embeddings, we initially obtain sub-graph with 80% randomly selected edges from each dataset and generate node embeddings by training MAS and TAS on these sub-graphs. A subset of the training edges (10%) are used for validation to select the best operator. The best logistic regression classifier obtained in this process is further used for testing on the remaining 20% data. We use an equal-sized sample of negative edges as positive edges for training. The accuracy for link prediction tasks is evaluated using the AUC (area under the ROC curve) score with a 5-fold cros-validatiin Baeza- Yates (1999).
Table delineates the performance of Maximum Adjacency Search (MAS) embeddings and Threshold- Adjacency Search (TAS) embeddings in link prediction tasks. On average, MAS and TAS approaches demonstrate an improvement in accuracy of 6.075% and 6.76%, respectively, surpassing the best accuracy achieved by other methods. Notably, the Hadamard operator (denoted by O in Table [], when used with MAS and TAS embedding approaches, exhibits good stability and consistently yields the best performance across all networks. We provide the percentage gain attained by MAS and TAS over other approaches in Table 1
8

---

Published in Transactions on Machine Learning Research (12/2024)
Table AUC of Maximum Adjacency Search (MAS) Embeddings, Threshold-basee Adjacency (TAS) embeddings, Node2vce, Deepwalk, and NBBE on Link Prediction task. On all the datasets, the @ operator achieved the best performance. The best overall performance is highlighted in bold, while the best-performing baseline is shaded in gray.
DATA SET
MAS EMBEDDINGS
TAS EMBEDDINGS
NODE2VEC
DEEPWALK
NENE
GAIN
FACEBOOK
0.985
0.988
0.933
0.927
0.921
5.89%
ARXIV
0.983
0.985
0.923
0.911
0.927
6.25%
EMAIL
0.941
0.932
0.857
0.829
0.843
9.80%
CORA
0.868
0.881
0.838
0.749
0.842
4.6%
PUBMED
0.885
0.913
0.801
0.783
0.838
8.95%
CITESEER 0.871
0.869
0.761
0.729
0.819
6.35%
Node Classification: Node classification is the task of assigning predefined labels categorics nodes within network. Each node is associated with one or more classes, and machine learning models utilize node features, network topology, our study, we utilize node embeddings generated through Maximum Adjacency Search (MAS) and Threshold- based Adjacency Search (TAS) approaches across the entire network. The process involves training logistic classifiers with 80% of the labeled nodes for training, including subset for validation, while the remaining 20% serves as a test set. This procedure is iterated with 5 random seed initializations ensure the robustness and reliability of the evaluation process. Table shows the Miero-F1 scores for the node classification task datasets Email, Cora, Pubmed, and Citeseer. As can be observed, both MAS and TAS embedding approaches considerably outperform the existing shallow embedding methodologics by an average improvement of 15. 15.95% and 19.6 19.67%, respectively. All datasets are used for multi-class classification except for the Blog datasel, which uses multilabel classification.
combination of both to predict these labels Goyal & Ferrara (2018). J. In
Table 2: Micro-Fl score MAS embeddings, TAS embeddings, Node2vec, Deepwalk and NBNE on node classification task. The best overall performance highlightod bold, while the best cest-performing bascline is shaded in gray.
DATA SET
MAS EMBEDDINGS
TAS EMBEDDINGS
NODE2VEC
DEEPWALK
NBNE
GAIN
EMAIL
0.1162
0.1263
0.0912
0.0733
0.0872
38.4 %
CORA
0.8271
0.8192
0.7530
0.7427
0.7701
7.4 %
PUBMED
0.7931
0.8282
0.7181
0.7007
0.6914
15.33%
CITESEER
0.6294
0.6296
0.5013
0.5071
0.5309
18.59%
BLOG 0.2103
0.2097
0.1731
0.1514
0.1901
10.62%
5 Neighborhood Sampling in GNNs
Neighborhood sampling in Graph Neural Networks a technique designed to manage computational complexity and memory usage by selectively sampling subset of node's neighbors during training. Traditional GNNs, like Graph Convolutional Networks (GCNs) Kipf & Welling (016a)), aggregate information from all neighboring nodes, which can be computationally prohibitive for large-scale graphs. To address this, methods such GraphSAGE (Graph Sample and AggregatE) Hamilton et al. (2017a) and FastGCN (Fast Graph Convolutional Networks) Chen et. al.) (2018b) employ neighborhood sampling to limit the number of neighbors considered at each layer. GraphSAGE samples fixed number of neighbors for each node to create a computationally feasible and efficient aggregation process, enabling the model to handle large graphs without significant loss performance. FastGCN, on the other hand, samples neighbors in a way that approximates the full distribution of the graph, thereby maintaining the quality of the learned representations while reducing

---

Published in Transactions on Machine Learning Research (12/2024)
the computational load. Other notable approaches include importance sampling, where neighbors are selected based on their relevance, adaptive sampling techniques that adjust the sampling strategy during training and training on smaller sub-graphs or clusters Chen & Zhao (2018); Zou et al. (2019); Huang et al. (2018); Chiang ct al. (019)); Zong et al. (2019). These sampling strategies are critical for scaling GNNs to industrial-sized graphs used in real-world applications such as social networks, recommender systems, and biological norwsrks.
5.1 Literature Review
Graph Neural Networks (GNNs) employ edge-based aggregation of node features into low-dimensional
representations, demonstrating effectiveness in various downstream machine learning tasks Izadi et al.] (2020); ;
Kan et al. (2021); Kipf & Welling (016bb); Zhang & Chen (0018) Zhang et al. (2018). Nevertheless, the
application of many existing GNNs is limited to graphs with node features features/attributes aitruitess.. A considerable number
of real-world graphs do not include node attributes Chen et al. [020); Duong et al. (019)). In such scenarios, the direct application of Graph Neural Networks (GNNs) becomes challenging due to the absence of node features Cai & Wang 2018); Errica et al. (2019). Various intuitive methods have been commonly employed to address this issue by selecting artificial node features for GNNs based on degree, random, positional, and distance-related characteristics HHmmllon et al. 20017ap; Saat et al. (2021): ; Chen et al. (2017); You al. (2019): ; Li et al. (2020). Recently, Cui et al. (0022) provided comprehensive understanding of artificial node features for positional node classification tasks. The authors categorize commonly used artificial node features into positional and structural node features based on the type of information they can assist GNNs in capturing. Empirical results indicate that positional node features are particularly effective for positional node classification, while structural node features prove more beneficial for tasks related to structural node classification and graph classification. The authors observe that using DeopWalk emboddings as positional node features for GNNs yields the highest accuracy in node classification tasks compared to other feature alternatives such as random initialization (trainable node embeddings), degree, PageRank, etc.
Many structural encoding techniques have been proposed to address the limitations of GNNs to capture the underlying structure. In Bouritsas et al. (0022). the authors introduce a novel topologicaly--awann message passing scheme that leverages substructure encoding. The central concept involves counting specific substructures, such as cycles, cliques, and triangles, and embedding this substructure count information into the pesssgo-passingg process of the neural network. Experimental results demonstrate that this method outperforms existing approaches. However, a significant limitation of such structure-encoding methods is the high time complexity (O(n*) for size kt substructure) associated with counting substructures. In Yan et al. (2024), the authors propose technique for precomputing structural embeddings that encode distance information within simple subgraphs or substructures surrounding each node or an edge. This method enhances standard Graph Neural Networks (GNNs) by integrating precomputed topological information, which climinates the need for the model to learn representations over all possible subgraphs dynamically during training. While the primary goal of these frameworks is to enhance the expressiveness of graph neural networks by explicitly counting these substructures, the Maximum Adjacency Search (MAS) and Topological Adjacency Scarch (TAS) frameworks proposed in Algorithms 1 2 offer efficient algorithmic procedure to implicitly capture well-connected substructures without the need to explicitly identify count them, thus avoiding the computational bottleneck typically seen in substructure counting. This implicit approach enables faster and more scalable graph learning, while still improving the model's expressivity.
Fath-based Graph Neural Networks inherently aims to capture the substructures by sampling random or shortest paths that extends beyond the simple neighborhood of the node. In Abboud et al. (2022), the authors introduces a novel massagg-pasingg mechanism for Graph Neural Networks (GNNs) that incorporates the shortest-path distance between nodes to address the issue of over-squashing. Traditional GNNs only allow nodes to communicate with their direct neighbors, which can limit the flow of information across the graph. To mitigate this, the proposed approach extends message passing beyond immediate neighbors by also considering k-hop nodes (nodes that are kt steps away) and their respective distances. This allows nodes to directly exchange information even if they are not adjacent, thereby breaking the information bottleneck. PathGCN Eliasof et al. (2022) employs simple random walks as paths over which the weights for the spatial operator are learned. These random walks define the paths across which information is propagated. After learning the weights associated with these paths, a convolution operation is performed using linear operator.
10

---

Published in Transactions on Machine Learning Research (12/2024)
Path Neural Networks (PathNNs) Michel al. (2023) are novel graph neural network architecture that enhances the expressive power of GNNs by aggregating information along paths emanating from each node. PathNNs aggregate paths of varying lengths, such as shortest paths or simple paths up to certain length K, to update node representations. Unlike random walks Eliasof et al. (2022) or shortest paths Abboud et al. (2022]] Michel et al. (0023) which sample connected sequences from each node, our MAS and TAS approaches generate targeted sequences that capture well-connected local paths around each node. These paths can be seen instances of higher-order random walks and represent & distinet form of complex shortest paths, facilitated by the Delayed-BFS algorithm outlined in Algorithm 3 This approach not only reduces training time by generating fewer sequences compared to random walks but also enhances the model's expressivity by capturing more intricate structures within the graph
5.2 Threshold Adjacency Search (TAS) neighborhood Sampler
In this section, we introduce TAS-sampler, novel sampling technique designed to identify structurally significant local neighborhoods surrounding nodes within Graph Neural Networks for aggregation and message passing. This technique can be seamlessly integrated with any existing GNN architecture. To showcase the effectiveness of TAS-samper, we incorporate it into three prominent GNN architectures for non-attributed graphs: GCN Kipf & Welling (2016a), GraphSage- Hamilton al. (201aa), and GATv2 Brody al. 2021).
Algorithm outlines the TAS-Sampler procedure. First, the optimal parameters for the threshold, the number of neighbors, and the number of permutations are determined using Algorithm 2 Then, sequences representing the node's neighborhood context are generated, and an auxiliary graph, G', constructed using this new context. While MAS could be used for sequence sampling, we opted for TAS sequences due to their strong performance node classification tasks (Table 2
Algorithm TAS-Sampling
Input: Graph G
{0, p. TAS (
get the optimal parameters for TAS
for all in graph.nodes() do
4: for threshold <- 1...0 do
5: repeat p times
6:
neighbors +
random permutation of the neighbors of a vertex v
7:
num seruunceeeeccsseeee + len for 1...num 1._..uum_sseeuuenees do
5+@
10:
S.insert(v)
11:
Sinsert(neeighbors]] k... (k 1)]) sequence + Delayed-BFS(G,S,. S,0,1)
insert k neighbors of node into the set S
12:
13:
sequences. waa.encces.ineerssqqueeeee
14:
end
15:
TAS Adjacency_LLstteee
most frequent vertices from sequences(v).
Construct an auxiliary graph G' with TAS Adjacency List
16:
17:
return G'
During each message passing iteration, the hidden embedding ! corresponding, node V(G') is updated according to the information aggregated from u's neighborhood Nu)) G', This is expressed follows (For consistency, we use the similar notation from Hamilton 20200):
h ( (UDATEE()) (I! (A."DAAT""""".CCCCCC AGGREGATE Vo N(G (()((w))))) - -UDDATE (n Mi ()))
where UPDATE and AGGREGATE are arbitary differentiable functions (neural networks), V(G') are the set of vertices in the auxiliary graph G' (step 17 of Algorithm 4 N (u)) is the neighborhood of in G and
11

---

Published in Transactions on Machine Learning Research (12/2024)
(G (w)) is the aggregated message from the neighborhood of u in G'. Observe that not all neighbors of in the original graph G are retained as neighbors in the auxiliary graph G', effectively creating skip-connections. Moreover, nodes well-connected to u but at a multi-hop distance in G can become direct neighbors in G'.
6 Empirical Evaluation on GNNs with Artificial Node Features
Here we compare the performance of TAS-sampler incorporated in GNNs against complete neighborhood, random sampling, and PageBank sampling techniques [Hamillon et al. (2017a) with artificial node features for node classification tasks. We employ similar setup of experiments for node classification tasks as done in the paper Cui et al. (2022). We used the GraphSAGE, GCN, and GATv2 models, trained and tested them using the same data splits as in previous studies Kipf & Welling) (2016a); Brody et al. (2021); p; Cui let al. (2022), namely 20 randomly selected samples for each class during training with a validation set of 500 samples. Trainable node embeddings R and the embeddings produced from DeepWalk are provided as artificial node features for GNN. In the case of trainable node embeddings, The performance is measured for mean, sum, and max aggregation in each GNN layer, and the best classification accuracy is reported in Table 3 For GCN and GATv2, we consider the complete neighborhoods of the original graph G and sAS-slmpled auxiliary graph G' (step 16 of algorithm 4 for aggregation, and for GraphSage, we show the best performance attained by using random sampling and sampling using random walks with restarts (PageRank). For our experimental purposes, we initialized H = 10 (step 16 of Algorithm g The experiment is repeated for 5 random soed initializations for reliability. We also provide the accuracics obtained on Cora, Pubmed, and Cileseer datasets using GNNs with real node features. As can be observed from Tables TAS-Sammpl when incorporated in existing architectures, achieve an improvement up to 12.1% over other GNN architecturos these benchmark datasets showcasing its capability to identify influential neighbors for aggregations compared to existing mechanisms.
Table 3: Fl-micro Accuracies on Cora Dataset for different initializations of features vectors for the node classification task. The highest overall performance is highlighted in bold, while the best-performing baseline is shaded in gray.
GNN-ARCHITECTURE
TRAINABLE NODE
DEEP WALK EMBEDDINGS
REAL FEATURES
EABEDDINGS
GCN
59.7 + 1.1
68.3 + 1.2
76.4 + 1.3
GRAPHSAGE-POOL
63.8 + 1.7
72.6 + 1.5
77.7 + 1.1
GATv2
61.7 = 3.2
71.7 + 1.3
78.3 + 2.1
GCN-TAS
71.8 + 2.1
73.7 + 1.5
77.3 1.7
GRAPUSACCE-POLL-TAA TAS
70.2 + 2.1
74.2 + 1.9
78.2 + 0.9
GATv2-TAS TAS
68.1 + 1.4
73.1
+ 0.6
79.4 + 1.6
Integrating the TAS-Sampler into existing GNN architectures yielded a substantial performance boost in non-attributed networks, both for trainable node embeddings and deep walk features. reasonable performance increase was also observed for real node features, except for the Citeseer dataset, which has an average degree of 1.42 and an average clustering cocfficient of 0.14. Due to the scarcity of higher-order structures in Citeseer, the TAS-Sumpler, which samples nodes from cohesive regions, provides only marginal improvement this dataset for real-world features. This behavior aligns with discussion in Section D many nodes in extremely sparse graphs tend to have high betweenness centralities due to the lack of cohesiveness.
Subgraph Sampling to find the optimal TAS parameter set (step 2 of Algorithm 4) For all the experiments listed above, the optimal parameter set, (0, k. p) is found by rumning TAS on the entire network G. Here, we study the perturbation of the node classification accuracies using GCN Kipf & Welling
trainable node embeddings refer to the node embeddings which can be initialized with any aandomly-nittilllaatt methods httnps///yytorrh.on///doc.
12

---

Published in Transactions on Machine Learning Research (12/2024)
Table 4: Fl-micro Accuracies on CiteSeer Dataset for different initializations of features vectors for the node classification task. The best overall performance highlightod in bold, while the best- cest-performing bascline is shaded in gray (except for GATv2 using real features, which perform better than the proposed approaches for the CiteSoer dataset).
GNN-ARCHITECTTURE
TRAINABLE NODE
DEEP WALK EMBEDDINGS
REAL FEATURES
EMBEDDINGS
GCN
35.4 1.3
45.6 =
66.3 1.4
GRAPHSAGE-POOL
39.7 + 2.9
42.1 1 2.1
64.4 + 3.1
GATv2
2.5
44.4 1 1.9
67.4 2.3
GCN-TAI
43.6 + 1.3
47.8 = 1.9
66.7 + 0.6
GRAPHSAGE-POOK TAS
46.8 + 211
44.6 + 2.2
65.3 + 1.5
GATv2-TAS
48.4 + 3.4
46.1 + 0.8
66.7 2.1
Table 5: Fl-miero Accuracies on PubMed Dataset for different initializations of features vectors for the node classification task. The best overall performance is highlighted in bold, while the best-performing baseline is shaded in gray.
GNN-ARCHTE
TRAINABLE NODE
DEEP WALK EMBEDDINGS
REAL PEATURES
FMBEDDINGS
GCN
50.7 + 1.9
70.5 + 1.3
78.1 0.6
GRAPOSAGE-POOL
43.2 + 1.5
70.6 + 2.5
77.1 + 1.5
GATv2
46.7 0.8
69.4 + 1.4
78.4 1.2
GCN-TAS
62.3 = 1.2
74.7 + 1.0
79.6 - 1.3
GRAPHSAGE-POOL--AA
2.3
76.2 1
79.2 0.8
GATv2-TAS
54.1 1 3.9
71.7 1 2.2
78.2 + 3.1
2016a and GraphSage Hamilton et al. (2017a) different sampled subgraphs the CORA Sen al. 2008) and OGBN-PRODUCTS Hu et al. datasssss respectively, for understanding purposes. We sample connected induced subgraphs for experimental purposes with 3000 vertices each. We ran the Step of Algorithm 4 to find the optimal sets of parameters for each of these 5 subgraphs. We ran the GCN on Cora on a similar train-test setup as described in Section + and used the standard train-test splits on ogbn-products. As can seen from Table 7 the accuracies attained for real features and trainable node embeddings are similar the observed accuracies from Table The slight improvement in GCN performance be attributed to better generalization of TAS- porameters by using the subgraphs rather than the entire graph.
Table 6: Fl-micro Accuracies for node classification lask on Cora Datasel using GCN with TAS sampling. The TAS parameters for Algorithm 4 Step 2 were determined for five randomly sampled induced subgraphs of 3000 nodes (SU BSURAAHHH-, [0,4), and TAS-Sampling for GCN is performed on the entire graph G using the optimal parameter set found each of these sub-graphs.
TAS OPTIMAL SET
TRAINABLE NODE
REAL FEATURES
EMBEDDINGS
SURGRAPH-0
72.7 + 1.0
77.3
+ 1.1
SURGRAPH-1
70.6 + 1.4
78.2 + 0.9
SUBGRAPH-2
71.1 + 0.9
77.7 1 2.8
SUBGRAPH-3
71.1 + 2.1
77.4 + 0.4
SUBGRAPIL-
70.8 + 1.8
77.4 + 2.1
13

---

Published in Transactions on Machine Learning Research (12/2024)
Table Fl-micro Accuracies for node classification task on ogbn-products dataset using GraphSage with TAS sampling. The TAS parameters for Algorithm [ Step were determined for five randomly sampled inducod subgraphs of 10000 nodes -G- then performed the full graph G using the TAS optimal parameter set found each of these sub-graphs.
[0, 4]). PAS-Sampii for GraphSage (for 1000 epochs) was
TAS OPTIMAL SET
TRAINABLE NODE
REAL FEATURES
REAL FEATURES
EMBEDDINGS
WITH TAS SAMPLING
WITH SAGE SAMPLING
SUBGRAPH-O
63.1 1.7
79.2 1.6
77.1 + 2.3
SUBGRAPI-1
64.9 1 1.3
78.9 + 1.1
78.1 1 0.9
SUBGRAPH-2
62.4 1.5
80.7 0.8
77.9
SUBGRAPH-3
63.7 + 0.8
81.4 + 1.7
79.9
+ 1.1
SUBGRAPH-4
64.5 + 1.0
82.1 1.9
80.2 + 0.6
7
Conclusion
This paper introduces two novel techniques for generating node embeddings in non-attributed graphs: Maximum Adjacency Search (MAS) and Threshold-based Adjacency Search (TAS), which are inspired by the theory of s minimum cuts. Both algorithms proved to be effective in downstream tasks. In link prediction tasks, observed average improvement of 6.97% over existing shallow embedding techniques. Additionally, when incorporated as neighborhood sampling mechanisms, our approaches exhibit an improvement up to 12.1% in node classification tasks compared to Graph Neural Networks equipped with artificial node features, highlighting the effectiveness our sampler in identifying structurally influential vertices (that can at multi-hop distance) around every node.
Limitations Our approaches are better suited for networks where attributes and links are predominantly based on homophily. We empirically demonstrated in Appendix, Section D where our methods struggle identify broker edges bridging ties that typically form between different well-connected structures. Future research should be aimed at the node features and the connectivity structure of graph while simultaneously adapting for both homophily and heterophily in graphs. Given that the proposed approaches require multiple runs to evaluate the optimal paree-parrmeter values, future research should focus on designing models with fewer
Impact Statement This paper presents work whose goal to advance the field of graph-based Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
8 Acknowledgments
This work was supported by the Swiss National Science Foundation (SNSF Grant number 209488).
References
Ralph Abboud, Radoslav Dimitrov, and Ismail Ilkan Ceylan. Shortest path networks for graph property prediction. In Learning on Graphs Conference, pp. 5-1. PMLR, 2022.
Amr Ahmed, Nino Shervashidze, Shravan Narayanamurthy, Vanja Josifovski, and Alexander Smola. Distributed large-scale natural graph factorization. In Proceedings of the 22nd international conference World Wide Web, pp. 37-48, 2013.
R Baeza-Yales Modern information retrieval. Addison Wesley google scholo, 2:127-111 136, 1999.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering.
A duances in neural information processing systems, 14, 2001.
14

---

Published in Transactions on Machine Learning Research (12/2024)
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pallera Analysis and Machine Intelligence, 45(1):657 668, 2022.
Ulrik Brandes. A faster algorithm for betweenness centrality, Journal of mathematical sociology, 25(2): 163-177, 2001.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? ar preprint arXiv:2105.1443 14491, 2021.
Chen Cai and Yusu Wang. A simple yet effective baseline for non-attributed graph classification. ar preprint Xix::18111 1.0508, 2018.
Weiqing Cai and David W Matula. Partitioning by maximum adjacency search of graphs. Parlitioning Dala Sets, 19, 1993.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. In Proceedings of the 24th ACM international on conference on information and knowledge management, pp. 891 900, 2015.
Benjamin Paul Chamberlain, James Clough, and Mare Peter Deisenroth. Neural embeddings of graphs in hyperbolic space. XrXiv preprint arXiv: 705. 10359, 2017.
Haochen Chen, Bryan Perozzi, Yifan Hu, and Steven Skiena. Harp: Hierarchical representation learning for networks. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018a.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018b.
Shi Chen and Qi Zhao. Shallowing deep networks: Layer-wise pruming based feature representations. IEEE transactions on pattern analysis and machine intelligence, 41(12):3048 3056, 2018.
Xu Chen, Siheng Chen, Jiangchao Yao, Huangjie Zheng, Ya Zhang, and Ivor W Tsang. Learning on allribute-missing graphs. IEEE transactions on patlern analysis and machine intelligence, 44(2):740 -57, 2020.
Zhengdao Chen, Xiang Li, and Joan Bruna. Supervised community detection with line graph neural networks. arXiv preprint arXiv: 170::1700000 770.008415 2017.
Wei-Tin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient. algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 257-266, 2019.
Hejie Cui, Zijic Lu, Pan Li, and Carl Yang. On positional and structural node features for graph neural networks on non-attributed graphs. In Proceedings of the 31st ACM International Conference on Information E Knowledge Management, pp. 3898-3902 2022.
Chi Thang Duong, Thanh Dat Hoang, Ha The Hien Dang, Quoc Viet Hung Nguyen, and Karl Aberer. On node features for graph neural networks. arxiv preprint 1rXiv:1911.0877 2019.
Moshe Eliasof, Eldad Haber, and Eran Treister. pathgen: Learning general graph spatial operators from paths. In International conference on machine learning, pp. 5878-5891. PMLR, 2022.
Federico Errica, Marco Podda, Davide Bacciu, and Alcssio Micheli. A fair comparison of graph neural networks for graph classification, arXiv preprint orXiv:1912.09880 2019.
Martin G Everett and Thomas W Valente. Bridging, brokerage and betweenness. Social networks, 44:202-220 2016.
Linton C Freeman. A set of measures of centrality based betweenness. Sociometry, pp. 35 41, 1977.
15

---

Published in Transactions on Machine Learning Research (12/2024)
Palash Goyal and Emilio Ferrara. Graph embedding techniques, applications, and performance: A survey. Knowledde--aase Based Systems, 151:78-90 94, 2018.
Adilya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data måning, pp. 855 855-864, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017a.
William L Hamilton. Graph representation learning. Morgan & Claypool Publishers, 2020.
William L. Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. TEEE Data Eng. Bull, 40(3):52-74 74, 2017b.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in newral information processing systems, 33:22118 22133, 2020.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. Advances in neural information processing systems, 31, 2018.
Mohammad Rasool Izadi, Yihao Fang, Robert Stevenson, and Lizhen Lin. Optimization of graph neural networks with natural gradient descent. In 2020 IEEE international conference big data (big data), pp. 171-179. IEEE, 2020.
Xuan Kan, Hejie Cui, and Carl Yang. Zero-shot scene graph relation prediction through commonsense knowledge integration. In Machine Learning and Knowledge Discovery in Databases. Research Track: European Conference, ECML PKDD 2021, Bilbao, Spain, September 13-17, 2021, Proceedings, Part II 21, pp. 466-482. Springer, 2021.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint Xrx:::1609 02907, 2016a.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07300 2016b.
Joseph B Kruskal. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika, 29(1): 27, 1964.
Jure Leskovec and Julian Mcauley. Learning to discover social circles in ego networks. Advances in neural information processing systems, 25, 2012.
Jure Leskovee, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters.
ACM transactions on Knowledge Discovery from Data (TKDD), 1(1):2 es, 2007.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning, Advances in Neural Information Processing Systems, 33:4465 4478, 2020.
Linyuan Lü and Tao Zhou. Link prediction in complex networks: A survey. Physica A: statistical mechanics and ils applications, 39006):1150-117)) 2011.
Gaspard Michel, Giannis Nikolentzos, Johannes F Lutzeyer, and Michalis Vazirgiannis. Path neural networks: Expressive and accurate graph neural networks. In International Conference Machine Learning, pp- 24737 24755. PMLR, 2023.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. arXiv preprint arXim:1301.378.. 2013a.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. Advances in neural information processing systems, 26, 2013b.
16

---

Published in Transactions on Machine Learning Research (12/2024)
Galileo Namata, Ben London, Lise Getoor, Bert Huang, and U Edu. Query-driven active surveying for collective classificatton. In 10th international workshop on mining and learning with graphs, volume 8, pp. 1, 2012.
Mark EJ Newman. Mixing patterns in networks. Physical review E, 67(2):026126, 2003.
Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity preserving graph embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1105-1114, 2016.
Hogun Park and Jennifer Neville. Generating post-hoc explanations for skip-gram- based node embeddings by identifying important nodes with bridgeness. Neural Networks, 164:5466561, 2023.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Bryan Perozzi, Vivek Kulkarni, Haochen Chen, and Steven Skiena. Don't walk, skipl: Online learning of multi-scale network embeddings. In Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017, Sydney, Australia, July 31 August 03, 2017, pp- 258 258-265, 2017.
Simone Piaggesi, André Panisson, and Giovanni Petri. Effective higher-order link prediction and reconon from simplicial complex embeddings. In Learning on Graphs Conference, pp. 55-1. PMLR, 2022.
Tiago Pimentel, Adriano Veloso, and Nivio Ziviani. Fast node embeddings: Learning ego-centric representa- tions, 2018.
Tiago Pimentel, Rafael Castro, Adriano Veloso, and Nivio Ziviani. Efficient estimation of node representations in large graphs using lincar contexts. In 2019 International joint conference on neural networks (IJCNN), pp. 1-8. IEEE, 2019.
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the eleventh ACM international conference on web search and data mining, pp. 459-467, 2018.
Ryan A Rossi, Nesreen K Ahmed, and Eunyee Koh. Highor-order network representation learning. In Compunion Proceedings of the The Web Conference 2018, pp. 4, 2018.
Sam T Rowes. Nonlinear dimensionality reduction by locally linear embedding. Science, 290:232, 2000.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM international conference on data mining (SDM), pp. 333-341 STAM, 2021.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collective classification in network data. AI magazine, 29(3):93-9)) 0003-93,-4 2008.
Mechthild Stoer and Frank Wagner. A simple min-cut algorithm. Journal of the ACM (JACM), 44(4): 585 591, 1997.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In Proceedings of the 24th international conference on world wide web, pp. 1067-1077 1077, 2015.
S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. Journal of Machine Learning Research, 11:1201-1242, 2010.
Daixin Wang. Peng Cui, and Wenwu Zhu. Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD international conference Knowledge discovery and data mining, pp. 1225 1225-1234, 2016.
17

---

Published in Transactions on Machine Learning Research (12/2024)
Mengjia Xu. Understanding graph embedding methods and their applications. SIAM Revicw, 63(4):825 853, 2021.
Zuoyu Yan, Junru Zhou, Liangeai Gao, Zhi Tang, and Muhan Zhang. An efficient subgraph gun with provable substructure counting power. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 3702-3713, 2024.
Hao Yin, Austin R. Benson, Jure Leskovec, and David F Gleich. Local higher-order graph clustering. Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 555 564, 2017.
Jiaxuan You, Rex Ying, and Jure Leskovec. Posilion-aware graph neural networks. In Internalional conference on machine learning, pp. 7134-7143, PMLR, 2019.
Reza Zalarani and Huan Liu. Social computing data repository at asu, 2009.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. arXiv preprint arXiv:1907 04931, 2019.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in newral information processing systems, 31, 2018.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Layer-dependent importance sampling for training deep and large graph convolutional networks. Advances in neural information processing systems, 32, 2019.
18

---

Published in Transactions on Machine Learning Research (12/2024)
Appendix: Adjacency Search Embeddings
A Scalability of MAS and TAS approaches
Why is MAS scalable large networks: For each node and a subset of its neighborhood (where the subset is chosen in step 9 of Algorithm D], MAS generates a sequence of nodes of constant length. This is done by iteratively adding vertex that maximally connected to the existing sequence. This process can be performed for all vertices in the graph in overall linear time, explained in the time complexity Section 3.4 of the paper. The data fed into the common SkipGram Word2vec model has size of O(n x walk length). Since the walk length is constant, the space complexity is linear in the number of nodes. The size of the generated embeddings is (n x d), where d represents the dimension size.
Why is TAS scalable to large networks: In TAS, each node is assigned a threshold, denoted 0 [L. 8). When / = 1, TAS generates sequences of constant length by conducting a BFS the subset of nodes chosen in line 10 of Algorithm 2. When 0 = 2, node outside the selected subset of nodes (line 10 of Algorithm 2 will be activated or added to the sequence of existing nodes if it has at least two edges incident to the current. set of nodes, Similarly, for 0 = i, a node is added to the existing sequence of nodes if it is incident to at least nodes that are part of the existing sequence. This operation can be executed by slightly modifying the standard Breadth First. Search, as depicted in Algorithm 3 This demonstraates that TAS is as scalable as the standard BFS, enabling it handle extremely large-scale networks. The complexity analysis of TAS is akin to MAS, with a slightly higher constant factor, as sequences are generated for every node and subset of its neighbors from 8 ==1 to 8.
B Statistics of Datasets Used
1. Facebook Leskovec & Mcauley (0012 This dataset captures a snapshot of users' ego networks, where nodes represent users, and edges depict their relationships.
2. Arxiv Leskovec et al. (2007): : A collaboration network of researchers who submitted articles to
the Astrophysics category in ArXiv. Here, nodes represent the researchers, and edges indicate collaborations on papers.
Email Yin et al. (2017): Constructed from email data from a European research institution, this network has an edge (u,u) if person u sent at least one email to person v. The labels represent
department IDs.
Cora Sen et al. 20088 A citation network of publications classified into 7 classes based on their
subject areas.
5. Pubmed Namata et al. labels denoting the type of diabetes discussed in each publication.
2012): A citation network of scientific publications related to diabetes, with
Citeseer Sen et al. 22008: A cilation dataset of scientific publications where the research articles are classified into 6 subject categories.
7. Blog Zafarani & Liu (2009): A friendship network in which nodes represent bloggers and edges represent friendships between them. The labels represent. blogger interests inferred through the metadata provided by the bloggers.
Assortativity, or homophily, refers the inclination of nodes to connect with others that are similar in some aspect. Table presents the degree and label assortativity, computed according to Newman (2003) on the datascts used in this paper. Email, Cora, and Pubmed exhibit negative degree assortativity, indicating that nodes in these graphs are more likely to connect lo nodes with different degrees. Conversely, the graphs Facebook, Arxiv, and Citeseer demonstrate positive degree homophily, suggesting that nodes in these graphs tend to connect with others that have similar dogrocs. The Email dataset presents negative label assortativity, i.c., connected nodes have different labels, while others present positive homophily. Thus, the datasets chosen cover a broader spectrum of homophily properties.
19

---

Published in Transactions on Machine Learning Research (12/2024)
Table 8: Statistics of Datasets Used
DATASET
NODES
EDGES
AvG. DEGREE
# LABELS
DEGREE HOMOPHILY
LABEL HOMOPHILY
FACEBoOK
4,039
88,234
21.84
NA
0.0635
NA
ARXIV
18,772
198,110
10.55
NA
0.2052
NA
EMAIL
1,005
25,571
25.44
42
-0.0137
-0.0029
CORA
2,708
5,429
2.004
-0.0599
0.7711
PURMED
19.717
88,651
4.49
3
-0.433
0.686
CITESEER
3,312
4,732
1.42
0.0493
0.6778
BLOG
10,312
333,983
32.38
39
0.2541
0.0515
C
Operators for Link Prediction Tasks
Table 9 provides the list operators used for link prediction tasks against other shallow embodding approaches.
Table 9: Choice of operator for link prediction tasks
OPERATOR
DEFINTTION
SYMBOL
HADAMARD
f.(v) * f(()) [f(()) f((m)
L2
12
L1
[f(()) - -f(()) [f(()) f((U)
11
AVERAGE
1
D Applicability of MAS and TAS approaches
This section delves into the operational aspects of our proposed embedding approaches. Specifically, we will showcase the network characteristics that warrant consideration before applying MAS and TAS approaches.
Analysis on Facebook and CORA Networks: In the context link prediction, we analyze the challenging nature predicting certain network edges using MAS and TAS embeddings. We hypothesize that the misclassified edges are often connected nodes that act as brokers or bridges between two different portions of the sub-graphs and have higher betweenness centrality Park & Neville (2023): Everctt & Valente (2016); categorize nodes based on their betweenness
Freeman 1977; Brandes (2001). To test this hypothesis, centralities and assign each misclassified edge to the bucket containing the higher betweenness centrality of its two endpoints. Figures aa and b) depict the distribution of misclassified edges within each bucket. for the Facebook and Cora networks. The 0-10 percentile group corresponds to the lowest 10 percentile of betweenness centralities, while the 90-100 percentile group represents the top percentile.
Our observation reveals skewed distribution towards the 90-100 percentile bucket for both networks, implying that misclassifted edges frequently associated with these broker nodes with higher betweenness values of its endpoints. These broker nodes act as bottlenecks for both MAS and TAS approaches, as the sequences can only percolate through these vertices, typically for very low values of threshold or adjacencics. Consequently, this results in a limiled set of sequences surrounding the broker node for learning the context. of the node. This observation further illustrated for test edges with vertices of degree or 2 as the sequences can only percolate with thresholds or with a maximum adjacency of Similar challenges arise for vertices with star-shaped topologies or for vertices connected in long chains. We observed similar trends for misclassified node labels in node classification tasks.
20

---

Published in Transactions on Machine Learning Research (12/2024)
175
150-
400
125
Miclessfiedd
1.00
300
75
50
100
25
10
20
30
10
Ranges of Betweenness centrality
Ranges of Betweenness centrality
(a) Incorrectly predicted edges Facebook.
(b) Incorrectly predicted edges on CORA.
Figure 2: Betweenness Centralities of the end points of misclassified edges with MAS
Parameter Sensitivity: In assessing the impact of minor perturbations in parameters on the performance of MAS and TAS embedding approaches for prediction and classification, we first determine the optimal parameter configuration that maximizes performance. We then systematically vary each selected parameter by #l and observe the resulting changes in performance. For MAS, we perform experiments to assess sensitivity by perturbing the number of permutations (p) and the number of neighbors (k). For TAS, the sensitivity analysis is performed by varying the threshold.
Sensitivity w.r.t to number of permutations For Maximum Adjacency Search embeddings, slight perturbation in the number of permutations parameter yields an average variation of 1.87% and 2.03% for link prediction and node classification, respectively for Cora, Citescer and Pubmed networks. We notice similar results when perturbing the neighbors parameler, k. Overall, we observe an enhancement in performance with the increase of E [1,8] and & E [0]; this expected as the sequences are generated for diversified neighborhoods of each vertex with increase in the value of k. In the case of Threshold-basee Adjacency Search, minor perturbation in by +1 results in an average variation of 1.5% and 3.21% for link prediction and node classífication tasks. As described in Section increasing the value of 0 restricts the spread of Delayed- BFS (Algorithm
3 to specific higher-order structures.
Sensitivity w.r.t walk-length For MAS, varying the walk-lengthh parameter (1 E {5, 10, 15, 20, 25, 30, 35,40)) 40}) results in an average performance variation of 2.9% for link prediction and 1.51% for node classification on the Cora, Citesoer, and Pubmed networks. Generally, performance improves as the walk length increases, which is expected since longer walks capture substruct multi-hop neighborhoods more effectively. Similar trends performance variation have been observed for TAS.
Sensitivity w.r.t dimensions To illustrate the impact of the dimension parameter on both link prediction and node classification tasks for the MAS approach (Algorithm [ As depicted in Figure 3 a) and Figure B(b,, the accuracy demonstrates an upward trend with an increase in dimension. Notably, in the case of Cora's link prediction, there is a significant accuracy improvement of 3.2% when varying d from 128 to 512. A parallel trend is evident the Citeseer dataset for node classification, showcasing a Micro-F1 score increase of 2.41%. The behavior of TAS-embeddings with the change in dimension similar to that the MAS approach.
E Structural Encodings
In graph neural networks (GNNs), structural encodings are often concatenated with real node or edge features enhance the model's ability capture both local topology and node-specific attributes. These structural encodings typically represent graph properties, such as node degrees, centrality measures, or subgraph patterns, and used to provide additional context about node's position and importance within the
21

---

Published in Transactions on Machine Learning Research (12/2024)
Cara Citeseer
Pubmed
0.9
AUC Score
0.8
0.75
Dimensions
(a) Change in AUC scores for link prediction task on the Cora, Citeseer, and Pubmed datasets with the change in dimensions.
Cara
Citeseer
Pubmed
0.8
Micro-F1
0.5
0.4
Dimensions
(b) Change in Micro-FI scores for node classification tasks on the Cora, Citeseer, and Pubmed datascts with the change in dimensions.
Figure 3: Sensitivity of dimension parameter on MAS-embeddings
graph. When these encodings are concatenated with real features, the model benefits in enhanced expressivity Michel et al. (2023), capturing multi-hop information and better generalization by leveraging node's intrinsic features and their structural context.
In Table 10 we present the results of concatenating TAS embeddings, generatod from Algorithm 2 with intrinsic node features for GraphSage using random sampling (similar trends were observed for GCN and GATv2). We found that TAS proves to be more efficient. when used sampler in message passing for GNNs
22

---

Published in Transactions on Machine Learning Research (12/2024)
(i.e., implicit structural encoding) compared to the explicit approach, where structural encodings are concatenated with node features. This suggests that leveraging TAS within the message-passing framework leads to better performance than directly concatenating embeddings.
Table 10: F1-micro Accuracies Cora, Citeseer and PubMed Datasets using structural encodings for node classification task. Features vectors are concatenated with TAS embeddings and node's intrinsic features and passed it to GraphSage with random sampling at every layer.
GRAPH
REAL FEATURES
FEATURES
+
TAS EMBEDDINGS
CORA
77.9 0.8
77.7 +
CITESEER
63.1 = 2.7
64.4 + 3.1
PUBMED
77.5 + 0.8
77.1 + 1.5
F Training Time for TAS approach
Table 11 provides the training time (in minutes(m) and seconds(s)) for the TAS, and other random walk based methods Veo and Deepwalk) across various parameters on node classification tasks. Training times were obtained using 16 core processor, running TAS on 12 threads, and all algorithms were implemented using gensim.
Table 11: Training times across networks
GRAPH
TAS
NODE2VEC
DEEPWALK
EMAIL
11m333
18m41s
13m55s
CORA
49m09s
61m13s
24m31s
CITESRER
33m47s
43m00s
27m16
PUBMED
121m02s
187m25s
39m08s
23


Reviews:
[{"review_id": "4TJKj0kIqi", "reviewer": "Reviewer_scgH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.New Node Embedding Techniques. MAS dynamically selects maximally connected nodes, while TAS uses a threshold-based approach to find cohesive substructures. These methods are used to pre-process graph data and can be integrated with models like the Skip-Gram to enhance tasks such as link prediction and node classification.\n2.Performance Improvement. MAS and TAS embeddings outperform traditional shallow embeddings like Node2Vec and DeepWalk in link prediction and node classification tasks.\n3.Applications in GNNs. When used as a pre-processing technique for GNNs, MAS and TAS improve the performance by better identifying influential local neighborhoods for message passing.\n\nWeaknesses:\n1.Several Limitations. One major concern arises from several limitations in the proposed approaches. (1) The primary strategy employed, Maximum Adjacency Search (MAS), tends to prioritize tightly connected neighbors, which can lead to the exclusion of sparsely connected nodes that might carry important information. This approach assumes that the most informative nodes are the ones densely connected to the current sequence. However, in certain data structures, especially in scenarios with heterogeneous or long-range connections, less connected nodes could be pivotal for capturing the broader graph structure or important latent relationships. A possible limitation of the proposed node embedding approach is its bias toward locally dense subgraphs, which can result in an incomplete or biased representation of the global graph structure. This limitation could affect tasks that require capturing weak but semantically meaningful connections, such as in social networks or knowledge graphs, where weaker links might represent important relationships. (2) The large number of parameters involved in both MAS and TAS increases the risk of overfitting, which can degrade generalization performance and limit their effectiveness in real-world applications. This over-parameterization can also lead to increased computational costs and make model tuning more challenging. (3) The computational complexity presented in this paper is inaccurate, as it assumes the graph is sparse, representing a best-case scenario. This assumption is unrealistic, as real-world graphs are more likely to be dense. When analyzing computational complexity, it is essential to consider the worst-case scenario, where the graph is dense. Moreover, the computational complexity of the proposed approaches depends on both the number of nodes and edges, which could significantly limit their scalability and applicability in real-world scenarios involving large and dense graphs.\n\n2.Unclear Motivation and Methodological Advantages. Another major concern is the unclear motivation and advantages behind the proposed approaches. The specific research problems this paper aims to address, as well as the advantages of the proposed methods over existing ones, are not clearly defined. Consequently, it is difficult to determine whether the observed performance improvements in the experiments are due to the proposed design or simply the result of careful parameter tuning. To strengthen the paper, a clearer articulation of the research problems compared to existing methods is needed, along with concrete examples demonstrating how the proposed approaches outperform existing techniques, including node embedding methods, neighborhood sampling strategies in GNNs, and methods for extracting higher-order relationships.\n\n3.Incomplete Literature Review. While the section on Related Work categorizes the literature into three main areas—matrix factorization, random walks, and GNNs—it remains incomplete and lacks specificity. Given that the proposed approaches focus on mining high-order relationships and performing neighborhood sampling for node embedding learning, the paper should provide a more comprehensive review of relevant studies. This should particularly include an in-depth examination of node embedding methods, neighborhood sampling techniques in GNNs, and the exploration of higher-order relationships, such as those found in hypergraphs and subgraph mining.\n\n4.Unconvincing Experimental Evaluation. Although various experiments were conducted across different tasks, such as link prediction and node classification, the experimental evaluation falls short in convincingly demonstrating the effectiveness of the proposed approaches. First, the comparison methods are outdated and not representative of the current state-of-the-art. Second, the datasets used for different tasks lack consistency. Third, each task is evaluated using only a single metric, limiting the comprehensiveness of the assessment. Fourth, as previously mentioned, the numerous parameters involved in the proposed approaches raise questions about whether the performance improvements stem from the proposed design or merely from careful parameter tuning. Finally, the running time for all methods should be reported to ensure that the computational complexity of the proposed approaches remains within reasonable bounds.\n\n5.Chaotic Organization. The paper suffers from several organizational issues, with explanations of parameters and algorithms scattered throughout. To improve readability, these sections should be rearranged. For instance, the parameter settings on page 4 should be moved to the experimental section. On page 6, Section 3.3, titled “Shallow Embedding Learning Framework” should be positioned closer to Section 3.1, as Algorithm 1 in Section 3.1 outlines the steps of embedding learning related to the Skip-gram model discussed in Section 3.3. Additionally, the discussion on neighborhood sampling found on page 9 should be incorporated into Section 2, titled “Related Work.” Moreover, an independent section should be added to define the notations used in this paper in detail. Importantly, including a separate “Preliminaries” section to introduce the techniques employed—such as Maximum Adjacency Search (MAS) and s-t minimum cut—would provide valuable context for readers.\n\n6.Unclear Descriptions. The presentation of algorithms in this paper is difficult to understand and lacks sufficient explanation regarding the steps involved in the proposed algorithms. For example, in Algorithm 1, it is unclear what “neighbors ← permute(v.neighbors())” signifies and which technique is employed to permute the neighbors of the nodes. Additionally, the expression “S.insert(neighbors[l · k...l · (k + 1)])” is ambiguous and needs clarification. Furthermore, the line “f = train(w, d, sequences)” appears to indicate the embedding learning step, but it is not adequately explained within the context of this algorithm. Moreover, in the experimental section, it would be helpful to highlight that the second optimal performance serves as a benchmark for comparison. Finally, the terms “SUBGRPH-0,” “SUBGRPH-1,” and so on, in Tables 6 and 7 should be clearly defined to enhance understanding.\n\n7.Questions. The first question is: how is the \"high-order topology\" referenced in Section 1 reflected in the proposed approaches? The second question is: what evidence supports the claim made in Section 1 that \"our path-based approaches differ from random walk methods and can be considered specific instances of k-th order random walks for any value of k\"?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces two novel methods for generating node embeddings in graph structures, namely Maximum Adjacency Search (MAS) and Threshold-based Adjacency Search (TAS). These methods are inspired by the theory of s-t minimum cuts and aim to capture well-connected nodes within a neighborhood, which are essential for generating higher-order representations. This node embedding approach integrates the Skip-Gram model for both link prediction and node classification tasks and also serves as a pre-processing technique for Graph Neural Networks (GNNs).", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to the above-mentioned weaknesses to make revisions to this article.\n\n1.The revised version should directly address the various limitations identified in the proposed approaches.  \n2.It should clearly articulate the motivation for and advantages of the proposed approaches.  \n3.Please conduct a thorough review of the literature closely related to the proposed methods.  \n4.Extensive experiments should be performed to convincingly demonstrate the effectiveness of the proposed approaches.  \n5.The organization of the paper should be rearranged to enhance readability.  \n6.Please clarify the descriptions of the methodology to improve understanding.  \n7.Ensure that all raised questions are answered thoroughly.", "broader_impact_concerns": "The broader impact section is not included in this article, and based on my assessment, there are no concerns regarding the ethical implications of this work that need to be addressed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "lceHmzX8O6", "reviewer": "Reviewer_YuEp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n1. To the best of my knowledge, the proposed MAS and TAS are new, and are different than existing random walk based methods.\n\n2.  The experimental results demonstrate improvements in link prediction and node classification tasks compared to other shallow embedding techniques, and good performance as input features for GNNs.\n\n4. The paper evaluates the applicability MAS and TAS on both attributed and non-attributed graphs, showing their relevance to a different applications.\n\n5.  The authors show how MAS and TAS can be combined into GNNs, thereby going beyond simple shallow embedding techniques.\n\n**Weaknesses:**\n1. Missing discussion of some related works, in particular: \n\n1A. The relation to methods that pre-compute higher order information on the graph, such as [1] and [2].\\\n1B. The relation to other 'path' and sampled based methods in GNNs like [3,4,5].\n\n2. The performance of MAS and TAS is  likely sensitive to its hyperparameters. For example, the number of permutations and the walk length are crucial factors of such methods.  I would highly recommend that the authors add an experiment that shows the sensitivity of the method to its hyperparameters.\n\n3. Results on synthetic graph substructure benchmarks (such as shown in [2], and [6] that is cited in the paper) could help to shed light on the expressive power that can potentially be added by the proposed method.\n\n4. Results on datasets **with** node features would make the experiments more convincing.For example, the authors show results on Cora, Citeseer, and Pubmed, but to my understanding they do not consider the case where both the embeddings computed by MAS and TAS are combined with input node features. I think that it would be beneficial to show if there is merit in combining the two, as these essentially can be regarded as sort of Structural Encoding, and these are known to often times help performance wise.\n\n5. Because some elements of the method are stochastic, to the best of my understanding, it would be interesting to know how stable it is. i.e., how much do the results fluctuate between different realisations of the embeddings through different sampling over the graph? does the method converge to something if we take infinitely many samples?\n\n[1] Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting\n\n[2] An Efficient Subgraph GNN with Provable Substructure Counting Power\n\n[3] pathGCN: Learning General Graph Spatial Operators from Paths\n\n[4] Shortest Path Networks for Graph Property Prediction \n\n[5] Path neural networks: expressive and accurate graph neural networks \n\n[6] Random Features Strengthen Graph Neural Networks\n\n\n**Minors:**\n-  A typo in the introduction,  \"These shallow embedding techniques, though computationally efficient, suffers from the drawback of lacking parameter sharing during training.\" – \"suffers\" should be \"suffer.\"\n-  Grammatical error, \"This approach draws inspiration from the Maximum Adjacency/Cardinality search technique, which is employed for identifying s-t minimum cut in a graph.\" – Should be \"an s-t minimum cut.\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes two new embedding methods of the adjacency matrix: Maximum Adjacency Search (MAS) and Threshold-based Adjacency Search (TAS). The idea of the methods is to generate higher-order representations of nodes from the graph structure.\n\nThe proposed methods are shown to outperform existing shallow embedding methods like Node2Vec and DeepWalk in tasks such as link prediction and node classification.\n\nThe paper also discusses the use of MAS and TAS as preprocessing techniques to improve the performance of Graph Neural Networks (GNNs) such as GCN, GraphSage, and GATv2.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to the weaknesses section in my review. In particular, I think that it is important that you address points 1,2, and 4. Points 3 and 5 are very important and interesting in my opinion, but 1,2, and 4 are more core components I would expect to see in the final paper.", "broader_impact_concerns": "I have no concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1VS0MD4Yfq", "reviewer": "Reviewer_z7HS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThis paper studies the important problem of graph embedding and proposes two novel embedding methods.\n\nWeaknesses:\n\nThe works reviewed in intro are not up to date (most are earlier than 2020) and lack the works proposed in recent years\n\nWhat is the motivation of the proposed two methods. Why is the proposed methods more advantageous than existing works? It is mentioned that the proposed algorithm can better capture some types of graph motifs. However, it seems that these properties have also been studied in previous works and are not unique to the proposed method in this work.\n\nPlease explain more on the permutation. what is the meaning and how does it influence the empirical performance.\n\nThe adopted baselines are old, it would be better if the proposed method can be compared against recent state-of-the-art methods.\n\nPlease explain what does it mean by ‘maximally adjacent’. For example, in the algorithm of MAS, it is used to decide a node that is maximally adjacent to a set of nodes.\n\nPlease explain more on the s-t minimum cut. This part is also relevant to the motivation of the proposed method but is not clearly explained. It is unclear why the techniques designed for s-t minimum cut is advantageous to be adopted for node embeddings.\n\nIt would be better if larger datasets with more diverse properties can be adopted to tested the proposed method. Currently, the adopted Cora and Citeseer are small toy datasets and are all citation networks. Therefore it is unclear whether the proposed method is generally applicable.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper aims to propose novel and better node embedding for graph learning. Specifically, two methods are proposed, including MAS and TAS. MAS is inspired by the Maximum/Cardinality search technique, which is designed to identify the s-t minimum cut on graphs. TAS is a generalised variant of MAS, in which a threshold is introduced.\n\nThe proposed method is tested on Cora and Citeseer datasets, and is compared to several baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to the weakness part", "broader_impact_concerns": "No ethical concern", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors have proposed two new methods for node embedding, based on s-t minimum cuts. These methods use search-based algorithms rather than random walks to capture well-connected nodes within a neighborhood. These methods can be combined with methods such as skip-gram to obtain higher-order representations. The authors show improvement over shallow representations, and show that the the neighborhoods can be used to improve GNNs.

The reviewers and I agree that this work is valuable to the community -- the approaches are straightforward but show clear benefits (that are well-motivated by the authors). The reviewers had a number of concerns about the initial draft, including lack of motivation and discussion of applicability, and insufficient literature review, but these issues were resolved following discussion between authors and reviewers and updating of the manuscript. All reviewers are happy with the revised manuscript, and I recommend accepting as-is.
Decision: Accept (poster)