Stochastic Block Model-Aware Topological Neural Networks for Graph Link Prediction
Authors: Yuzhou Chen
Xiao Guo
Shujie Ma
Venue: Accepted by TMLR ()

Abstract: Link prediction is an important learning task for graph-structured data and is indispensable to understanding graphs' properties. Recent works focus on designing complicated graph neural networks (GNNs) architectures to explore and capture various pairwise interactions among graph nodes. Most GNNs are based on combining graph structural and node feature information by iterative message-passing schemes. However, despite GNNs revolutionizing the field of graph representation learning, some thorny questions are raised concerning whether GNNs can efficiently learn the edge probabilities based on topological structures (i.e., higher-order interactions) and node features, and provide statistically rigorous uncertainty estimates. In this paper, we tackle these challenges and propose a novel stochastic block model (SBM)-aware topological neural networks, called SBM-TNN, that uses SBMs to infer the latent community structure of nodes from graph structures and uses persistent homology to encode higher-order information. Furthermore, we theoretically study the entrywise bound and asymptotic normality of the estimated edge probability matrix to quantify the uncertainty in statistical inference of the edge probabilities. Our extensive experiments for link prediction on both graphs and knowledge graphs show that SBM-TNN achieves state-of-the-art performance over a set of popular baseline methods.

Published in Transactions on Machine Learning Research (07/2025)
Stochastic Block Model-Aware Topological Neural Networks for Graph Link Prediction
Yuzhou Chen
yuchou. cuehou.cheneeeee Sucr.
Deportment of Statistics University of California, Riverside
Xiao Guo
Siaoguootmuu..ccm edu.cc
School of Mathematics Northwest University Xi an
Shujie Ma
shujje. ma Bucr. edu
Department of Statistics
University of Colifornia, Riverside
Reviewed on OpenReview: https: openreview. net/
net/ forum? id- FBJVFPASppp
Abstract
Link prediction is an important learning task for graph-structured data and is indispensable to understanding graphs' properties. Recent works focus on designing complicated graph neural networks (GNNs) architectures to explore and capture various pairwise interactions among graph nodes. Most GNNs are based on combining graph structural and node feature information by iterative message-passing schemes. However, despite GNNs revolutionizing the field of graph representation learning, some thorny questions raised concerning whether GNNs can simultaneously learn topological information, node-wise communily memberships, block-to-block connection probabilities, and provide statistically rigorous uncertainty estimates. In this paper, we tackle these challenges and propose a novel stochastic block model (SBM)-aware topological neural networks, called SBM-TNN, that uses SBMs to infer the latent community structure of nodes from graph structures and uses persistent homology to encode higher-order information. Furthermore, we theoretically study the entrywise bound and asymptotic normality of the estimated edge probability matrix to quantify the uncertainty in statistical inference of the edge probabilities. Our extensive experiments for link prediction on both graphs and knowledge graphs show that SBM-TNN achieves state-oftthe-art performance over a set of popular baseline methods.
1 Introduction
Graph data are ubiquitous throughout the natural and social sciences, e.g., many real-world objects can represented by graphs, such as molecules, ecosystems, transportation systems, energy systems, citation networks, and internet networks (Sen et al., 2008; Li et al., 2018; Xia et al., 2021; Chen et al., 2023a). Tremendous advances in graph analysis have been achieved in recent years, especially in the field of geometric deep learning (GDL) (Defferrard et al., 2016; Bronstein et al., 2017; Zhang et al., 2020). In particular, graph neural networks (GNNs) have emerged effective architectures for various prediction problems, c.g., node classification (Kipf & Welling, 2017; Veličković et al., 2018a; Hamilton et al., 2017), community delection (Chen el al., 2018; Shehur & Günnemann, 2019), and graph classification (Xu el al., 2018; Ying data.
et al., 2018). specifically, GNNs are neural network architectures designed to handle graph-structun The fundamental idca behind GNNs involves trcating the underlying graph as a computation graph and leveraging neural network primitives to generate node embeddings. The key processes involve message passing, propagating, and aggregating node features and graph utructural information throughout the graph.

---

Published in Transactions on Machine Learning Research (07/)025)
In GNNs, the graph convolutional layer builds upon the observed graph adjacency matrix, also called the connection matrix. The adjacency matrix can be viewed as a noisy version of an edge probability matrix with additive noises. In practice, graphs often contain communities, and thus the probability of an edge between any two nodes can depend on their group assignment, which is popularly modeled through the stochastic block model (SBM) (Holland et al., 1983) or its variant the degree-corrected stochastic block model (DCSBM) (Karrer Newman, 2011). When a graph indeed has communitics, we propose to use the estimated edge probability matrix to replace the adjacency matrix for graph representation learning. We estimate the edge probability matrix using the spectral clustering method (von Luxburg, 2007), which is computationally fast. Compared to the adjacency matrix, which only has two values 0 and 1, the estimated edge probability matrix contains the probability value of each edge, which can provide more information about the relationship between nodes and better recover the graph structure. In addition, the estimated probability matrix is proven to have asymptotic normality, which can be used for uncertainty quantification and confidence interval estimation. By contrast, the adjacency matrix can not achieve this goal. We also establish uniform error bound for the estimated edge probability mairix in terms of the entrywise maximum norm. These theoretical results are novel in the SBM literature. Furthermore, GNNs tend to majorly focus on information propagation among nodes and thus the model capability is limited, i.e., almost fail in learning topological and structural information. However, as recently shown by Wasserman (2018): Hensel et al. (2021); Pun et al. (2022): Liang et al. (2025); Goel et al. (2025); Dixon et al. (2025), such topological structures, e.g., connected components and holes might be an important step in graph knowledge discovery. For instance, persistent homology (Edelsbrunner, 2013; Zomorodian & Carlsson, 2004) has been used to study the topologiaa information encoded in the graph (Zhao & Wang, 2019; Chen al., 2021a;b; Li et al., 2025; Coskunuzer et al., 2024; Chen et al., 2023a; Horn et al., 2021; Arafat et al., 2025). However, these ideas have never been yet applied in conjunction with knowledge representation learning.
Aiming to solve the above challenges, we turn to the idea of combining learned community information from using an SBM-based model and different types of topological features by using multiple descriptor functions that can generate more expressive node embedding. The SBM is a powerful tool to learn from graph-structured data, as it designed to model graphs with clear community structures. In GNNs, these communities represent groups of nodes having similar behaviors. By leveraging SBM in our topological neural networks (TNNs), the model can simultancously learn the latent communities and capture the topological structures to enhance the performance in link prediction and node classification. Moreover, the communily-based learning from SBM enables our TNNs to capture local structures to improve prediction accuracy, when dealing with sparse graphs with few connections, which in general is a great challenge for GNNs. SBM, on the other hand, provides a probabilistic framework that can help the model infer relationships between sparse connections as well as providing a better interpretability and understanding of the relationships between nodes. We use the learned community information from SBM together with different types of topological features by using multiple descriptor functions to generate more expressive latent node embedding. The primary contributions of this work can be summarized as follows:
We propose a Stochastic Block Model-Aware Topological Neural Networks (SBM-TNN), novel TNN-based model equipped with SBM concepts that captures topological structures, node features, and structure ure of neighborhood relations. It is the first approach bringing the concepts of topological signature representation learning and stochastic block models to graph learning.
We further study the important problem, i.e., how to quantify the uncertainty for the estimated edge probability matrix. To achieve this goal, we establish an entrywise error bound and asymptotic normality of the estimated edge probability matrix that can be used to construct asymptotically valid confidence intervals for the edge probabilities, and help quantify the accuracy and uncertainty of the estimated edge probability matrix and provide theoretical guarantee for the follow up procedures of the proposed SBM-TNN model.
Extensive experiments on benchmark datasets clearly show that SBM-TNN delivers saate-of-the-att link prediction and knowledge graph completion tasks with significant margin.
2

---

Published in Transactions on Machine Learning Research (07/2025)
2 Related Work
Graph Neural Networks. Recently, Graph Neural Network (GNN) has emerged as a primary tool for node classification, link prediction, graph classification, and graph forecasting (Wu et al., 2020; Zhou et al., 2020; Chen & Gel, 2023; Chen et al., 2022c; Zhao et al., 2023; Chen et al., 2022a; 2023b; 2024b;a; Chen & Gel, 2025). Based on the spectral graph theory, Bruna et al. (2014) introduces the Fourier domain. However, the complexity of this model is very high since all Laplacian eigenvectors are needed. To tackle this problem, ChebNet (Defferrard et al., 2016) integrates spectral graph convolution with Chebyshov polynomials. Then, Graph Convolutional Networks (GCNs) (Kipf & Welling, 2017) simplifies the graph convolution with a localized first-order approximation. SEAL (Zhang & Chen, 2018) extracts local enclosing subgraphs around the target links and learns a function mapping the subgraph patterns to link existence. Graph2Gauss (G2G) (Bojehevski & Günnemann, 2018) designs an unsupervised model that handles inductive link prediction by using deep encoder to embed each node a Gaussian distribution. Deep Generative Latent Feature Relational Model (DGL.FRM) (Mehta et al., 2019) proposes an overlapping stochastic blockmodel for community discovery tasks. In addition, the Hyperbolic Graph Convolutional Neural Networks (HGCN) (Chami et al., 2019) leverages both the hyperbolic geometry and GCN framework to learn node representations. Another interesting recent strategy is to use pairwise topological features to find latent representations of the goometrical structure of graph using GCN (Yan et al., 2021). Morcover, Bi-Level Attention Graph Neural Networks (BA-GNN) (Iyer et al., 2021) leverages both node-node and relation-relation interactions (without meta paths) to capture more information about graph components. Mixed-Curvatury Multi- Relational Graph Neural Network (MºGNN) (Wang et al., 2021a) is designed to embed multi-relational information in mixed-curvature space for knowledge graph (KG) completion. Additionally, Geometic Space Embedding Model (DGS) (Iyer et al., 2022) studies KG in complex non-Euclidean geometric space by modeling different views via different geometric spaces. A common limitation is that they fail to accurately capture correlated and rich topological properties of graphs and incorporate rich structure and topological information both in local and global domains.
graph-based convolution in
Stochastic Block Model. The SBM (Holland et al., 1983) is probabilistic model to generate networks with community structures, where nodes are partitioned into blocks and the probability of edges between nodes depends on their block memberships. The past few decades have seen various methods for recovering community memberships based on the observed network (Abbe, 2018). Spectral clustering stands out because of its computational tractability. The statistical properties of spectral clustering under SBM or its variant DCSBM have been widely studied. For example, the weak consistency of clustering, i.e., the proportion of misclustered nodes converges to zero as the number of nodes increases, has been investigated by Rohe et al. (2011); Lei & Rinaldo (2015); Joseph & Yu (2016), among others, and the strong consistency, namely, the memberships can be perfectly recovered in large samples, has been established in Su et al. (2019). Moreover, the minimax rate of the estimator for the edge probability matrix (i.e., the population counterpart of the adjacency matrix in terms of matrix norms such as Frobenius or spectral norm has been provided (Gao et al., 2015). However, how accurately the spectral clustering method can estimate each entry of the edge probability matrix is unclear. We develop the entrywise bound for the estimated edge probability matrix, which is essential to quantify the uncertainty in statistical inference for the population counterpart of the adjacency matrix in SBMs and DCSBMs. In addition, we establish the asymplotic normality of the estimated edge probability matrix, which turns out to be asymptotic efficient, under SBMs and DCSBMs, so we can construct asymptotically entrywise confidence intervals for the probability matrix. The asymptotic Gaussian behavior for the estimators of the block probability matrices (Tang et al., 2022) and the eigenvector matrix (Tang & Priebe, 2018; Cape et al., 2019; Xie, 2024) have been studied under SBMs. However, the asymptotic behavior of the estimator for the edge probability matrix under more general DCSBMs is undeveloped.
3 Stochastic Block Model-Awarr Topological Neural Networks: Undirected Graph
3.1 Mixed-Up Undirected Graph Construction
To capture the topological information from the graph & and node features, we construct a mixed-up graph GM = (AM, X) based on original input graph Go (Ao, X) and k-hop graph Gx (Ax, x) (where AM,
3

---

Published in Transactions on Machine Learning Research (07/2025)
Ao. and Ag denote adjacency matrices of the mixed-up graph, original graph, and k-hop graph respectively). N
X = [mr] #2 , E RNxd is the node feature matrix where N is the number of nodes, d is the number of features, and H, denotes the node features of the node ug
Original Graph Representation Learning. We adopt the Graph Convolutional Layer (GCL) to perform message passing on the original graph Go = (Ao; X) where Ao denotes the adjacency matrix of the original graph. It utilizes the original graph structure of Go with its node feature matrix X through the graph convolution operation and a multi-layer perceptron (MLP). Specifically, the designed graph convolution operation proceeds by multiplying the input of each layer with the 7-th power of the normalized adjacency matrix. The r-th power operator contains statistics from the 5-th step of a random walk on the graph (in this study, we set T to be 2), thus nodes can indirectly receive more information from farther nodes in the graph. Combined with a multi-layer perceptron (MLP), the representation learned at the &thh layer is given by:
(1) W())), Z 2((+1) So H
9o
A. Ao + I, and D is the corresponding degree matrix of A, H X, fMLP is an MLP which has layers with batch normalization, o()) is the non-linear activation function, ( is a trainable weight of é-th layer.
where do D
K-Nearest Neighbor Graph Representation Learning. First, in order to capture graph structural information of nodes in topology and feature spaces, we build K-nnarest neighbor (KNN) graph, ie., Gx (Ax, In our study, we first define the similarity matrix Sx E RNN among N nodes and we consider three different methods as follows: (i) Cosine Similarity: It uses the cosine value of the angle between two vectors to mcasure the similarity, i.c., Sue = su
(x_ [= (ti) Gaussian Kernel: It is based on the idea of the heat equation, a partial differential equation that describes how heat propagates over time t, which can be defined as follows Suv = exp(- - x,,1? /t); and (ti) Node Embedding Similarity: Let H (B+1) be the node embedding of (f)-th layer of GNN. For any u, 2 E V, we can calculate the similarity H H((+))
score Sue between nodes u and v as (i) Cosine Similarity: S.. || (-) [|! or (ii) Gaussian Kernel:
H ( (P1/t) (where t is a free parameter). Then, the adjacency matrix Ax can be obtained by selecting top-K similar neighboring nodes of each node. Similarly, we can use Eq. 1 to learn the (E + 1)-th layer node embeddings of the above KNNN graph, which is denoted by ((+1))
Sav= = exp (-I ((+1)
Scc
Mixup for Graph Construction. Here we adopt the node-level attention mechanism to learn the hidden connectivity between nodes. Specifically, given a node pair (u, v), the importance coefficient between nodes u and v can be formulated as (for the simplicity, we omit (E + 1) for z(++)) and Z (e+1)):
9c
uu MM_ = WM|Zso so. Zoch:
explo(Wines)) (y))))) M.M Softmax (M) Ever explo Me
where [ represents the concatenation operation, WM and WM M are trainable parameters, a()) denotes the LeakyReLU function with negative input slope 0.1. After the above calculation, we can get the mixup atlention score deM which represents the weight of the edge between nodes u and
3.2 Stochastic Block Models for Undirected Graph
We consider two classes of probabilistic models for generating undirected networks with communities. The first is the SBM (Holland et al., 1983). The second is the DCSBM (Karrer & Newman, 2011). Suppose the N nodes are assigned to K non-overlapping communitics. The k-th community has N₂ Nodes with Σk, N₂ = N, and denole т := Nr/N. Let E {1,.... K} be the community assignment. (i.e., cluster) of node i. Alternatively, the community assignments can be represented by a membership matrix Z E {0, 1] NxX where each row corresponds to a node and each column to a community. Specifically, Zi = if and only if g, = k. and Zi₁- = 0 otherwise. Let B E k be the block probability matrix, where B. specifies the probability of edge between nodes in communities and t.
4

---

Published in Transactions on Machine Learning Research (07/2025)
Given B and Z, the SBM assume that each entry Ay <) of A is generated independently by Asj Bernoulli(P) (B 9.9; )- In SBMs, the nodes within each community are stochastic equivalent. To incorporate the node heterogeneity, the more general model DCSBM is considered as follows. Let 0 = (01,..., 0N)T E RN be the node propensity paramcters and denote θ = d 0x) J. where each entry 6; captures the individual tendency or activity level of node to form edges the net work. Given B, Z and O, the DCSBM assume each entry Ai j) of A generated independently by Aiy Bernoulli g. It then easy to see that
P OZBZT E
N
(2)
is the population counterpart of A. P is referred to as the edge probability matrix. Note that O and B are only identifiable up to scaling. As a remedy, we use the following normalization rule
Σ 0, = Nk. k= K.,,,K K. 1acck
With this normalization rule, the SBM is nested by the DCSBM by lctting 0, = 1 for = I...,,N. To estimate P, we should estimate Z, B and θ respectively. Before that, we first recall and introduce some notation. Let d, = Σ Ai be the degree of node and D = diag(di,...,d dx. The graph Laplacian is D 1/2 AA/2AD-11 1/2, Note that this graph Laplacian matrix has the same eigenspaces that.
defined L of D A/AD-11/
Under SBMs, we estimate Z using the standard spectral clustering on the graph Laplacian matrix L. That is, conducting k-means on the top-K eigenvectors of L. The estimator is denoted by 2. WLOG, we assume that Ž has been orthogonally transformed to align with Z. We estimate B by the following = (Bu))sgsisk,
Byl.azi = Eg. -.0, -1 Ai N,
and Bug = Eg-gg Au N,
9.0,
Thereby, we obtain : 2B2r. Under the DCSBMs, we estimate Z using the spherical spectral clustering on the graph Laplacian matrix L. That is, conducting k-means on the Lo-row-normalized top-K eigenvectors of L. With a light abuse of notation, the estimator is also denoted by 2. We estimate B by B (Bal)
By EiSHASN Ag
Σ Eg.=g,;=- Aij Ng
EigtojN 2,1
We estimate 0, by 0 defined as
Nº. E,Ar Aij
0: Σg E/= A1j
where Ng. is the number of nodes the estimated community d:- We also denote é = diag((). Finally, we obtain P = θ The detailed derivations of the estimators can be found in the Appendix.
3.3 Multi-View Topological Graph Neural Networks for Undirected Graph
Multi-View Topological Convolutional Layer. To capture the underlying topological features of the subgraph Gn of each node u, we employ X filtration functions: fi V R for i {1,...,.Y,, Each filtration function fi gradually reveals specific topological structure at different levels of connectivity, e.g., degree contrality score, betweenness centrality score, closeness contrality score, and other node centrality measurements. With each filtration function fi, we construct a set of Q persistence images of resolution P x P using tools in persistent homology analysis. Combining Q persistence images of resolution P P from H different filtration functions, we construct malti- topological representation, i.c., the set of persistence images (PIs) Plg...., with the dimension X Q P P. We design a multi-view topological convolutional layer fMv-GCL. (i) jointly extract and learn the latent topological features and (ii)
5

---

Published in Transactions on Machine Learning Research (07/2025)
leverage and preserve the multi-modal structure. Firstly, hidden representations of the set of PIs are achieved through combination of CNN-based model and global pooling, which can be defined as
u - (ppooo////cx(( Pl,,. PIxl)))
where JONN is CNN-based neural network, ÊPOOr. is a pooling layer that preserves the information of the input in a fixed-size representation (in general, we consider either global average pooling or global max pooling). In Eq. equation 3, we first apply a CNN-basod model to learn the latent feature of Pls, and then employ global pooling layer over the latent feature and oblain an image-level feature.
Graph Convolutional Layer. Our third representation learning module is the Graph Convolutional Layer (GCL). It utilizes the graph structure of GM with its node feature matrix X through the graph convolution operation and multi-layer perceptron (MLP). The representation learned at the L-th layer is given by
z z(+1) (AL ( M of (PH ( with SBM SBM))),
where H = H (0)
SBM = X, fMLP is an MLP which has layers with batch normalization, a(-) is the non-linear activation function, w and W SBM are trainable weight matrices of ê-th layer. Then, we obtain the final embedding Z by combining embeddings from the above modules, i.c., Z = [ Zgl, where [:-] denotes the concatenation operation and g represents the final output of the graph convolutional layer.
4 Stochastic Block Model-Aware Topological Neural Networks: Knowledge Graph
A knowledge graph (KG) is defined as a directed graph that stores structured information about real-world entities and relations. Let g (V. R. L}} be an instance of a KG, where V, R. and L denote the entity (i.e., node), relation, and edge sets respectively. Each edge e E C presented as triple r,t) E R V, describing that there is a relationship E R from head entity h to tail entity f. In order to apply the stochastic co-block model (which is introduced in Section 4.1) to classify nodes into K clusters, we first transform the KG into a directed graph and then generate community information based on the graph's adjacency matrix instead of the knowledge graph by using SBM method. Note that, for the KG, we incorporate its information into the model and we don't have an additional assumption for KG. The overall architecture of SBM-TNN is as shown in Figure! 1.
4.1 Stochastic Co-Block Models for Directed Graph
Similar to the undirected networks, consider two classes of probabilistic models for generating directed networks with co-clusters, namely, row clusters (communities) and column clusters (communities). The first is the stochastic co-block model (ScBM), and the second is the degroc-corrected stochastic co-block model (DCS&BM) (Rohe el al., 2016).
Different from SBMs and DCSBMs, the models for directed networks incorporate two kinds of clusters. Suppose the N nodes are assigned K non-overlapping row clusters and K non-overlapping column clusters. WLOG, suppose Kv K² The 1"th (resp. k*th) row (resp. column) cluster has Ny (resp. NE) nodes with EK No = N (resp. ΣK N N), and denote T == N (resp. TH == NE/N). Let 9.¹ E (1,.., Kツ} (resp- of E (1,..., K*)) be the row (resp. column) community assignment of node i. Following the same logic as undirected networks, let Y {0, N and E (0, N denote the row and column membership matrices, respectively. Let B R** be the block probability matrix.
Given B, Y and Z, the ScBM assume that each entry Ay # j) of A is generated independently by Aij Bernoulli(A B B)gg)) In ScBMs, the nodes in common row (resp. column) cluster stochastically equivalent senders (resp. receivers) in the sense that they send (resp. receive) out an edge to a third node with equal probabilitics. To incorporate the node heterogeneity in sending and receiving edges, the more general model DCScBM is considered as follows. Let 0V (Ø"..., (T) E R and 0= -0f 0% E RN be the node propensity parameters in sending and receiving edges, respectively. Denote @² diag (V) and
6

---

Published in Transactions on Machine Learning Research (07 (07/2025)
e = (0)) Given B, Y, Z, O" and 0 the DCScBM assumes each entry Aij(t + of A is generated independently by Ag ~ Bernoulli 03 B s55)) Then, under the DCScBM, it is easy to see.
P = O'YB'' E NNN
(4)
is the population adjacency matrix of A, referred to as the edge probability matrix later. identifiability, we use the following normalization rule
To ensure
k2 = I,.,, K" Σ 0 = N
6 =>
(5)
Σ
0
Ni. == 1, 1,... K².
1. =k
The ScBM is nested by the DCScBM by letting 0% = and 0: for I,..., N.. To estimate P, we introduce some notation now. Let di = Ej=1 Aij (resp. di = Ej=ı A;i) be the out-degree (resp. in-degree) of node and D = diag(d",.... 8z) (resp. D diag(d', (di,..., H) Define the graph Laplacian by L I (Dv) ADD))=11 Under ScBMs, we compute the SVD of and then conduct the k-means on the u left (resp. top-K* right) singular vectors of L, to obtain K row (resp. K column) clusters, denoted by Y (resp. 2). WLOG, assume that Y (Z) has been orthogonally transformed to align with Y (resp. Z). Similar to the undirected set-up, we estimate B by the following B (Bx) 1osk
B = EISHASNA Aug Eg Aij N/Ñ
EiSiFiEN &zg2,1
where Ny (resp. Nf) denotes the number of nodes the estimated row cluster 9 (resp. column cluster 1). Thereby, we obtain P BÂT. Under the DCScBMs, we estimate Z by applying the spherical spectral clustering to the graph Laplacian matrix L. That is, we obtain the top-K" row and column singular vectors by computing the SVD of L, and then conduct k-means on the Ig-row-normallieed left and right singular vectors to obtain the K row clusters and K* column clusters, respectively. With a light abuse notation, the estimators are denoted by Y and 2. Following the same logic as DCSBM, we oblain the estimators B (By), Oy diag(Ov) and θ= diag(O=) follows.
= Aij
Nop E, Aij Aij
Byt=
04
NW ÑE
Esp=or E/= A1j
Noz E, Aij
0
Σ = Σn Au
where Ny is the number of nodes in the estimated row cluster d and No is the number of nodes in the di estimated column cluster 9f. With these estimators at hand, obtain P = θ
d:
4.2 Attention- Based Topological Neural Networks for Knowledge Graph
In this section, we propose novel allention-based lopological neural network (A-TNN) to combine the community information and topological signatures learned from ScBM for entity representation learning.
z (e+1)) = Σ
(r.1)ENs
(1) WKG, (6) (()
x (()
X X,),
C.
(6)
explo(W
(8)
KG,
a =
Eireees explo
0
KG, h
7

---

Published in Transactions on Machine Learning Research (07/2025)
where x x; and x denote embeddings of head entity h, tail entity i, and relation r respectively, WKG, and WKG, denote the linear transformation matrices, X (2) CC Mr denotes the set of neighboring tuples (r,t) for entity h, k Enec, (5) which aggregates node embeddings from the community Cj (i.c., results from Scction 4.1), and X fav-Gcu(91) (where 9r. denotes the subgraph of the node h).
5 Theoretical Guarantees
To establish the statistical property of P, we need the following assumptions. In order to provide the results uniformly and reduce redundancy, we use the notations in the more general ScBMs and DCScBMs. The SBMs and DCSBMs can be regarded as the special case of ScBMs and DCSeBMs.
Assumption 5.1. Suppose K2 and K* are both fixed and both the row and columa clusters satisfies that for any k2 E {1,.... K"), cN/K" s bo S CN/K" for some conslants 0 S c C; for any k² E (1,,.., K*}, dN/K* & N S C'N/K² for some constants 0 S d' C".
Assumption 5.2. Suppose the edge probability matriz B E 10, 1]"1"""X" (KY S K²) is of rank K², The entries of B are of the same magnitude PN with Npx 2 clog N.
Assumption 5.3. Define Oxx be the K th singular value of L diag/df, ..., } with df = -E Pij, and D= = diag!di...... with di = Σin Pj.- Suppose
where De
lim infx loo > 0.
Assumption 5.4. Define 0" = max; 0º and 0 = min, 0.. Suppose e S lim inf N 0" < sim 0" S C for some constants 0 < C. Similarly, define O = max, 0; and o = min, O; Suppose e' s limmin inf 0² <
lim sup,y 0- < C' for some constants 0 S d S C".
R with B = -0 BP BP 1/2 where OB is a Kv x Ky diagonal matria with [OB]. = Σ. Banj and PB is a K² x K* diagonal matria with PBllu = E, Bany Suppose there exits gap between any two columns of H such that min H. MHH-HA H.yll 2 for some consland {>
Assumption 5.5. Define H = B
Assumptions 5.1-5.4 are generally required for undirected network models SBMs and DCSBMs. For directed network models ScBMs and DCScBMs, we need additional Assumption 5.5. Assumption 5.1 requires that the number of nodes in each cluster is not. too small, which ensures the strong consistency of the spectral method, namely, each node is correctly clustered. For notational simplicity, we fix the number of communities, although the framework can naturally be extended to accommodate varying numbers of communitics as in Su et al. (2019). Assumption 5.2 requires that the network is not too sparse. This condition is the minimal requirement for strong consistency of SBM (Abbe et al., 2015; Su et al., 2019; Ma et al., 2021). Assumption 5.3 implies that the singular value of the population Laplacian matrix is lower bounded by a constant. For an SBM with cross- block probability being r, and block probability being r + P. then σж = (/(K++ + is a constant provided that r and p are of the same order. Assumption 5.4 requires that the node propensity parameters are upper and lower bounded. The upper bound is mild as the node propensity parameters are normalized to satisfy (5). The lower bound can be relaxed to n for some positive constant a with a sacrifice of the simplicity of other conditions (Su et al., 2019). This assumption is only needed when networks follow DCSBMs and DCSeBMs. Assumption 5.5 is required to ensure that there exists gap between two rows of the population right singular vectors when the two nodes are in different column clusters. This is a remedy assumption for the invalidity of the full column rank under directed network models.
Lemma 5.6 (Strong consistency). Suppose Assumptions 5. 1-5.5 hold. Then for large enough N, it holds for both ScBMs and DCScBMs that
sup ISISN
10 # )²) 0 and sup ISIEN
1 # o 0 a.s.
(7)
and
Vp N
sup 15g5Kv,1<IEN
By Bytl = Oa...
(8)
N
8

---

Published in Transactions on Machine Learning Research (07 2025)
For DCScBMs, it also holds that
log N
sup 10y - 0 = Oa.s. ISYSN
N
(9)
log N
10; 0 = Oa.s. ISSN
sup
Np p
Remark Lemma 5.6 also holds for SBMs and DCSBMs with the notation slightly changed and without the requirement of Assumption 5.5. The strong consistency results are critical for deriving the ervor bound and asymptotic normality of P. equation 7 and equation 9 can be implied by Corollary I1I.1 and Theorem III.6 in Su et al. Su et al. (2019).
Theorem 5.7 (Error bound). Suppose Assumplions 5.1-5.5 hold. Then for large enough N, it holds for ScBMs that
Vplog N N
sup ISiJEN
P.j - Piyl = Oa.e.
)
(10)
and for DCScBMs that
log N
sup P.j P Payl 0as..
(11)
ISLSEN
N
Remark 2. For SBMs and DCSBMs, equation 10 and equation 22 hold withortt Assumplion 5.5. Most of the current literature on SBM and its variants study the high probability spectral norm bound of A from Gao et al. (2015); Lei Rinaldo (2015). Our results are novel in that we provide the uniform entrywise bound of P from which holds almost surely. The less tightness of DCSBMs and DCScBMs comes from the estimation of the node propensity parometers.
Theorem 5.8 (Asymptotic normality). Suppose Assumplions 5.1-5.5 hold. Then for ScBMs, (12) holds with Co = 1, 0- = 0; = 1 and E 0. For DCSeBMs, (12) holds with co = and Eij = Oa.s. (log N/N) (where S i,j S N).
B. Bogg
Boyo7) 7o7
N(P P+ E)s NO0.co (0
(0))²).
(12)
Remark 3. (12) also holds for SBMs and DCSBMs without. Assumplion 5.5 and with the same order of E and notation slightly modified except that oo = when gi = 9j and co = when gi & gj- For SBMs, the estimator P is asymptotic efficient (Bickel et al., 2013). For DCSBMs and DCScBMs, the bias Esy and Fij come from the estimation of 0. Note that for denser networks, namely, Uilog N/N), the bias is dominated by the signal P.j. To the best of our knowledge, this is the first result to show the asymptotic normality of an estimator against the edge probability matria P.
6 Experiments
Datasets and Baselines. We experiment on 2 types of networks for link prediction (i) citation networks:
Cora-ML, Citeseer, and PubMed (Sen et al., 2008) and (ii) graphs related to Amazon shopping records: Photo and Computers (Shchur et al., 2018). For link prediction tasks, we compare against 10 state-of-the-
art (SOA) basclines, including (i) Graph convolution network (GCN) (Kipf & Welling, 2017); (ii) Graph Attention Networks (GAT) (Veličković et al., 2018b); (iii) Hyperbolic Graph Convolutional Neural Networks (HGCN) (Chami et al, 2019); (iv) Position-aware Graph Neural Networks (P-GNN) (You al., 2019); (v) SEAL (Zhang & Chen, 2018); (vi) Block Simplicial Complex Neural Networks (BScNets) (Chen et al,, 2022b); (vii) Topological Loop-Counting Graph Neural Network (TLC-GNN) (Yan et al., 2021). For knowledge graph completion lasks, we conduct experiments on well-known KG datasets including (i) FB15k-237 (Toutanova et al., 2015; Toutanova & Chen, 2015), WN1SRR Dettmers et al. (2018), and NELL-995 (Xiong et al., 2017), and use the following popular models as basclines: (i) CompGCN (Vashishth et al., 2019); (ii) Relational Graph Convolutional Network (RGCN) (Schlichtkrull et al., 2018); (iii) KBGAT (Nathani et al., 2019); (iv) Atrous Convolution and Residual Embedding (AcrE) (Ren et al., 2020); (v) ReInceptionF) (Xie al.,
9

---

Published in Transactions on Machine Learning Research (07/2025)
Table 1: AUC-ROC score on different link prediction benchmarks.
Model
Cora-ML Citeseer PubMed
Photo
Computers
GCN Kipf & Welling (2017)
90.5+0.2
82.6+199
89.643.7
91.840.0
87.8+0.0
GAT Veličković
(2018b)
72.8:0.2
74.8+1.
80.3+0.0
92.94:0.3
86.420.0
HGCN Chami et al. (2019)
93.820.1
96.640.1
96.3+0.0
95.4400.0
93.620..
P-GNN You et al. (2019)
74.12244
73.942.6
79.620.5
90.9400.7
88.311.0
SEAL Zhang & Chen (2018)
91.3+5.77
80.842.3
92.4+122
97.8+1.3
9.5
BScNets. Chen et al. (20226)
94.9=0.7
96.5+-0.5
97.6#0.1
96.640.33
97.0#0.3
TLC-CNN Yan et al. (2021)
91.91011
96.140.7
97.020.1
98.240.1
97. 07.910.1
SBM-TNN (ours)
96.2:0.2 0.311 98.
99.0:10.2
2020); (vi) Semantic Evidence aware Graph Neural Network (SE-GNN) (Li et al., 2022); and (vii) Neural Bellman-Foo Ford Network (NBFNett (Zhu et al., 2021).
Experiment Settings. We implement our proposed SBM-TNN with Pytorch framework on two NVIDIA RTX A5000 GPUs with 24 GiB RAM. Following Chami et al. (2019), for graph link prediction tasks, we randomly split edges into 85% /5%/10% for training, validation, and testing, and we evaluate link prediction using the ROC-AUC score on the test set. For KG completion tasks, we follow the settings in previous works (Vashishth et al., 2019; Schlichtkrull et al., 2018), i.e., triplets in these datasets are randomly split into training, validation, and test sets respectively, and we evaluate the KG completion performance by using Mean Reciprocal Rank (MRR) and @its@N (here we consider N E (1,3, 10)). Code and data are publicly available at https: https://githi: //gttuub./uut..../.. wwt hwwa///uhoogggg//SMM.... TNN. For further details on the experiment settings, please refer to Appendix.
Experiment Results. The link prediction and KG completion results are summarized in Tables 1 and 2. From Table 1, the results indicate that our SBM-TNN consistently achieves the best performance on all datasets. More specifically, we find that (i) Compared to the spectral-based GNN (i.c., GCN), our SBM-TNN yields up to 12.8% relative improvements for all 5 datasets; (ii) Compared to the spatial-based GNNs (i.e., GAT, P-GNN, and SEAL), SBM-TNN improves upon the runner-up by a margin of 5.4%, 8.1%, 6.3%, 1.0%, and 2.3% on datasets Cora-ML, Citeseer, PubMed, Photo and Computers; (iii) SBM-TNN outperforms the hyperbolic- based NNs, i... HGCN with a statistically significant margin; (iv) SBM-TNN further improves based GNN (i.e., BScNets and TLCC-GNN) with a significant. margin on all 5 datasets. We also compare with two additional sate-of-the-art baselines, i.e., NCNC (Wang et al., 2024) and LPFormer (Shomer et al., 2024) on Cora-ML and Citeseer datasets with MRR, and we observe that our SBM-TNN achieves average improvements of 23.1% and 3.3% over NCNC and LPFormer respectively (further details can be found in the Appendix). Additionally, Table 2 shows the performance of SBM-TNN and baseline methods on 3 KG datasets. From Table 2, we observe that SBM-TNN surpasses the baselines in terms of the MRR, Hits@1, 1, Hits@3, and Hits@ 10 on all datasets. Furthermore, we have conducted an additional comparison with the GNNs + NBFNet on ogbl-wikikg2 data (Hu et al., 2020). The test MRR of SBM-TNN and GNNs + NBFNet are 0.11210000009 and 0. 0.7086+000025 i.c., our SBM-TNN is significantly better than this state-of-the-an method. Overall, the results show that SBM-TNN can accurately capture and learn the key structural and local topological information, and achieve highly promising performance in both link prediction and KG completion tasks.
Table 2: KGC results (%) with different scoring functions.
FB1
WN18RR
NELL-995
MRR
Hnssg
MRR
Hiteen
Hitskg
Hir800
MRR
Hitsian
Hitsig
Hitskng
CompGGN Vashishth el al. (2019)
1
26. 410.1
39:0102
53.62033
47.2102
43.720.3
48.5203
54.2000
38 1404
30.103
422203
12.90.
RGCN Schiicttirll al. (2018)
29.610.3
19.5
310102
50.110.2
43.010.2
38.010.3
45.010.1
50.8...3
27.811.2
19.9102
$1.41000
13.010.3
KBGAT Nathoui el al. (2019)
35.00033
26.040.3
38 58.5
53.1
46.11022
42.6202
47.9203
589102
374116
29.7407
414108
52001044
AcrE Ren al. (2020)
35.810.3
26.610.2
39.310.3
5151022
45.910.2
42.21..3
47.3002
53.240.1
RelnceptionE Xie al. (2020)
31.91022
52.84022
48.310.3
5822003
SE SE-GNN La et al. (2122)
36.1
410.2
37.010.3
5L510.2
18.110.1
43.61..2
47.910.2
57.240.3
39.311.5
30210:3
03.0122
52.81033
GNNs + NBFNet 2bm el al. (2021)
11.5:10.1
32 120.1
16.6104
59.910.3
56.110.1
49.72:011
57.2403
66.620.3
40.5:0.3
32.7102
419203
56.0204
SDM-TNN (ours)
36.91.0.2
27.340.3
40.8402
55.610.1
49.110.2
44.120.2
48.01..11
50.34:0.2
41.740.2
34.740.2
45.240.1
56.240.1
3BM-TNN + NBENet (ours)
11.910.1
33.010.1
47.120.2
00.1-0.2
55.5
49.9
59.210.1
67.010.0
42.010.1
34.91022
45.510.3
55.910.1
10

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Table 3: Link prediction (AUC-ROC) of SBM-TNN with different. T.
Dataset
T=1
T=
T=3
T=4
Cors-ML
93.740.8
96.2+0.2
95.4+0.3
93.2+0.9
Citeseer 94.910.8
97.01:0.3
97.1
95.110.6
PubMed
97.9+0.3
98.2+0.2
98.740.6
95.5+0.7
Table 4: Performance comparison for link prediction (AUC-ROC) between P and P.
Architecture
Cora-ML
Citeseer
PubMed
SBM-TNN (P)
95.3+0.3
95.0=t0.5
96.3+0.3
SBM-TNN (P)
96.2+0.2
97.1+0.3
98.2+0.1
Sensitivity Analysis To evaluate the link prediction performance SBM-TNN with different т, we conduct experiments on the Cora-ML, Cileseer, and PubMed datasets. As shown in Table 3, we observe that our approach achieves optimal performance under a specific power of the normalized adjacency matrix. In addition, we have run additional experiments Cora-ML and Citescer. As shown in Table 4, SBM-TNN with estimated P outperforms SBM-TNN with actual P. In particular, the average relative gain of SBM-TNN with estimated P over SBM-TNN with actual P is 1.58%.
A Ablation Study We have also conducted ablation studies to explore the importance of different components, and considered two ablated variants, i.e., (i) SBM-GNN represents that replacing TNN by a graph neural network (GNN), and (ii) TNN represents that SBM-TNN without adding SBM method, (i.e., we do not incorporate community-level information into the model architecture). From Table we observe that our SBM-TNN always outperforms both the GNN model equipped with SBM (i.e., SBM-GNN) and TNN model Cora-ML and Citeseer data. That is, when ablating the components (i.e., SBM and TNN), the ROC AUC score of SBM-TNN drops significantly. Our results indicate that community and topological information consistently boost the performance of link prediction.
Computational Complexity The topological complexity of the standard persistent homology (PH) matrix roduction algorithm runs in time at most ((²)), where Q the number of simplices a filtration. For o-dimensional PH, can be computed efficiently using disjoint sets with complexity O(Qa where a (-) is the inverse Ackermann function. In study, for graph representation learning, only consider dimension (comnected components) and dimension 1 (cycles) due to the fact that we cannot observe enough higher-order (sub)structures in target datasets. If we consider high-dimensional topological features, the time complexity will grow large with the worst-case complexity O(m²) for d-dimensional topological features (where m denotes the number of edges).
7 Conclusion
We propose new Stochastic Block Model-Aware Topological Neural Networks (SBM-TNN) method for both link prediction and knowledge graph completion tasks. By leveraging the topological information and estimated probability matrix with communitios from different network topologics, SBM-TNN achieves state-of-the-art results on all datasets and the experimental evaluation confirms that SBM-TNN is accurate, flexible, and scalable. We also provide theoretical guarantee for statistical inference based on the estimated
Table 5: Ablation studies.
Architecture
Cora-ML
Citeseer
PubMed
SBM-TNN
96.2-0.2
97.140..3
98.2-10.1
SBM-GNN
90.7++0.3
83.7+0..4
93.7+0.2
TNN
93.2+0..5
96.0=1.5
95.310.66
11

---

Published in Transactions on Machine Learning Research (07 (07/2025)
edge probabilities. non-attributed, overlapping, dynamic network community detection, high-quality synthetic graph generation.
Interesting future directions include extending how the SBM-TNN be used for
Acknowledgments
The research Ma was supported part by the U.S. National Science Foundation grants DMS-22 23-80288 and SFS-24-12922 The research of Guo was supported part by the National Natural Science Foundation of China grant (12301384, 12326615), and the Major Key Project of PCL (No. PCL2024A06).
References
Emnanuel Abbe. Community detection and stochastic block models: recent developments. Journal of Machine Learning Research, 18(177):1-86, 2018.
Emmanuel Abbe, Afonso S Bandeira, and Georgina Hall. Exact recovery in the stochastic block model. IEEE Transactions Information Theory, 62(1):471-487, 2015.
Naheed Anjum Arafat, Debabrota Basu, Yulia Gel, and Yuzhou Chen. When witnesses defend: A witness graph topological layer for adversarial graph learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 15408 15466, 2025.
Peter Bickel, David Choi, Xiangyu Chang, and Hai Zhang. Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels. The Annals of Statistics, 41(4):1922 1943, 2013. doi: 10.1214/13-AOS1122 URL https://doi.. orggiiorg//// 10. 1214/13-A0S1124
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. In Proceedings of the International Conference on Learning Representations, 2018.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18 42, 2017.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. In Proceedings of the International Conference on Learning Representations, 2014.
Joshua Cape, Minh Tang, and Carey E Priebe. Signal-plus-noie matrix models: eigenvector deviations and fluctuations. Biometrika, 106(1):243-25)) 2019.
Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Y. Chen, I. Segovia--Dmmngguez B. Coskumuzer, and Y. R. Gel. TAMP-S2GCNets: Coupling time-aware multipersistence knowledge representation with spatio-supra graph convolutional networks for time-series forecasting. In Proceedings of the International Conference on Learning Representations, 2022a.
Yuzhou Chen and Yulia Gel. Topological zigzag spaghetti for diffusion-based generation and prediction on graphs. In Proceedings of the International Conference on Learning Representations, 2025.
Yuzhou Chen and Yulia. R Gel. Topological pooling on graphs. In Proceedings of the AAAI Conference on Arlificial Intelligence, volume 37, pp. 7096 7103, 2023.
Yuzhou Chen, Baris Coskunuzer, and Yulia Gel. Topological relational learning graphs. Advances in Neural Information Processing Systems, 94:27029-27042 2021a.
Yuzhou Chen, Ignacio Segovia, and Yulia R Gel. Z-GCNETs: Time zigzags at graph convolutional networks for time series forecasting. In Proceedings of the International Conference on Machine Learning, 2021b.
Yuzhou Chen, Yulia R Gel, and H Vincent Poor. BScNets: Block simplicial complex neural networks. In
Proceedings of the AAAT Conference Artificial Intelligence, volume 36, pp. 6333 6341, 2022b.
12

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Yuzhou Chen, Elena Sizikova, and Yulia R Gel. Topoattn-Nets, Topological attention in graph representation learning. In Joint Puropean Conference on Machine Learning and Knowleddge Discovery in Dalaboses, pp- 309 325. Springer, 2022c.
Yuzhou Chen, Roshni Anna Jacob, Yulia R Gel, Jie Zhang, and H Vincent Poor. Learning power grid outages with higher-order topological neural networks. JEEE Transactions on Power Systems, 2023a.
Yuzhou Chen, Tian Jiang, and Yulia R Gel. H²-Nets: Hyper-hodge convolutional neural networks for timo-serics forecasting. In Joint European Conference on Machine Learning and Knowledge Discovery in Dalabases, pp. 271 289. Springer, 2023b.
Yuzhou Chen, Jose Frias, and Yulia R Gel. TopoGCL: Topological graph contrastive learning. In Proceedings of the AAAI conference on artificial intelligence, volume 38, pp. 11453-114110 11461,, 2024a.
Yuzhou Chen, Shengyi Wang, and Liang Du Learning power system vulnerabilities through multi-view topological neural networks. In 2024 IEEE Power & Eneryy Society General Meeting (PESGM), pp. 1-5. TEEE, 2024b.
Zhengdao Chen, Lisha Li, and Joan Bruna. Supervised community detection with line graph neural networks In Proceedings of the International Conference on Learning Representations, 2018.
Baris Coskumuzer, Ignacio Regovia-Dominguez, Yuzhou Chen, and Yulia R Gel. Time-aware knowledge representations of dynamic objects with multidimensional persistence. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 11678-11686, 2024.
Michaël Defferrard, Xavier Bresson, and Picrre Vanderghoynst. Convolutional noural networks on graphs with fast localized spectral filtering. Advances in Neural Information Processing Systems, 29, 2016.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In Proceedings of the AAAI conference on Artificial Intelligence, volume 32, 2018.
Matthew Dixon, Yuzhou Chen, and Yulia R Gel. Topological K-means clustering in reproducing kernel hilbert spaces. Electronic Journal of Statistics, 19(1):204-28) 2099999,92222900 2025.
Herbert Edelsbrunner. Persistent homology: Theory and practice. 2013.
Chao Gao, Yu Lu, and Harrison H. Zhou. Rate-optimal graphon estimation. The Annals of Statistics, 43(6): 2624 2652, 2013. doi: 11-214/15-AOS1A
URL http:://abi.orr/1....2 http:///.....//.....2///1///-/// 12111111111111111155..44
Jaidev Goel, Yuzhou Chen, and Yulia Gel. Few-shot learning over graphs using topological prompts. In Compunion Proceedings of the ACM on Web Conference, pp. 976-989 980, 2025.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems, 30, 2017.
Felix Hensel, Michael Moor, and Bastian Rieck. A survey of topological machine learning methods. Fronliers in Artificial Intelligence, 4:681108, 2021.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social Networks, 5(2):109-131) 1983.
Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borgwardl. Topo- logical graph neural networks. In Proceedings of the International Conference on Learning Representations, 2021.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. Advances in Neural Information Processing Systems, 33:22118 221181,,21,,,-11111111 2020.
Roshni G Iyer, Wei Wang, and Yizhou Sun. Bi-level attention graph neural networks. In IEEE International Conference Data Mining, pp. 1 1126 1131. TEFE, 2021.
13

---

Published in Transactions on Machine Learning Research (07 (07/)025)
Roshni G Iyer, Yunsheng Bai, Wei Wang, and Yizhou Sun. Dual-geometric space embedding model for two-view knowledge graphs. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 676 686, 2022.
Antony Joseph and Bin Yu. Impact of regularization on spectral clustering. The Annals of Statisties, 44(4): 1765-1791, 2016.
Brian Karrer and Mark EJ Newman, Stochastic blockmodels and community structure in networks. Physical Review E, 8311)001 2011.
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. Proceed- ings of the International Conference on Learning Represenlations, 2017.
Jing Lei and Alessandro Rinaldo. Consistency of spectral clustering in stochastic block models. The Annals of Slalistics, 43(1):215- 237, 2015. doi: 10.1214/14-A0S1274 URL https://dof wrg/10..///.. 121.1.1411444101222
Hao Li, Hao Wan, Yuzhou Chen, Dongsheng Ye, Yulia Gel, and Hao Jiang. TMetaNet: Topological meta- learning framework for dynamic link prediction. In Proceedings of the International Conference on Machine Learning, 2025.
Ren Li, Yanan Cao, Qiannan Zhu, Guanqun Bi, Fang Fang, Yi Liu, and Qian Li. How does knowledge graph embedding extrapolate to unseen data: a semantic evidence view. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 5781-5791 2022.
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. In Proceedings of the International Conference on Learning Representations, 2018.
Peiyu Liang, Yulia R Gel, and Yuzhou Chen. Topology-ifformed pre-training of graph neural networks. In
IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 1-5. IEEE, 2025.
Shujie Ma, Liangiun Su, and Yichong Zhang, Determining the number of communities in degree-corrected stochastic block models. The Journal of Machine Learning Research, 22(1):321773377, 2021.
Nikhil Mchta, Lawrence Carin Duke, and Piyush Rai. Stochastic blockmodels meet graph neural networks. In Proceedings of the International Conference on Machine Learning, pp. 4466 4474. PMLR, 2019.
Deepak Nathani, Jatin Chauhan, Charu Sharma, and Manohar Kaul. Learning attention based embeddings for relation prediction in knowledge graphs. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 4710-4723, 2019.
Chi Seng Pun, Si Xian Lee, and Kelin Xia. Persistent- hwwee-hoooooooyooe based machine learning: survey and comparative study. Artificial Intelligence Review, 55(7):5169-5213 2022.
Feiliang Ren, Juchen Li, Huihui Zhang, Shilei Liu, Bochao Li, Ruicheng Ming, and Yujia Bai. Knowledge graph embedding with atrous convolution and residual learning. arXiv preprinl arXiv:2010.12121 2020.
Karl Rohe, Sourav Chatterjce, and Bin Yu. Spectral clustering and the high-dimensional stochastic blockmodel. The Annals of Statistics, 39(4))1878 1915, 2011, doi: 10.1214/11-AOSSY; URL htto::://doirrggg/
1214/11-A08887.
Karl Rohe, Tai Qin, and Bin Yu. Co-clustering directed graphs to discover asymmetries and directional communitics. Proceedings of the National Academy of Sciences, 113(45))12669-111 12684, 2016.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Tvan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In The semantic Web: International Conference, pp. 593-607. Springer, 2018.
Prithviraj Sen, Galiico Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rae Radd. Collective classification in worwork data. AT Magazine, 29(3):93 93, 2008
14

---

Published in Transactions on Machine Learning Research (07/2025)
Oleksandr Shchur and Stephan Günnemann. Overlapping community detection with graph neural networks. arviv preprinl arxi:: 1V::990.. 12001, 2019.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. ar preprint or Xiv: 1..05668, 2018.
Harry Shomer, Yao Ma, Haitao Mao, Juanhui Li, Bo Wu, and Jiliang Tang. LPFormer: An adaptive graph transformer for link prediction. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2686-2695 2024.
Liangjun Su, Wuyi Wang, and Yichong Zhang. Strong consistency of spectral clustering for stochastic block models. IEEF Transactions on Information Theory, 66(1):324-336 2019.
Minh Tang and Carey E Priebe. Limit theorems for eigenvectors of the normalized laplacian for random graphs. The Annals of Statistics, 46(5):2360-241) 2415, 2018.
Minh Tang, Joshua Cape, and Carcy E Pricbe. Asymptotically efficient estimators for stochastic blockmodols: The naive mle, the rank-constrained mle, and the spectral estimator. Bernoulli, 28(2):1049 1073, 2022.
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Proceedings of the Workshop on Continuous Vector Space Models and Their Compositionalilt, pp. 57-66, 2015.
Kristina Toutanova, Danqi Chen, Patrick Pantel, Hoifung Poon, Pallavi Choudhury, and Michael Gamon. Representing text for joint embedding of text and knowledge bases. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pp.
2015.
Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition-based multi-relational graph convolutional networks. arXiv preprint arXiv:1911.0000 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. Proceedings of the International Conference on Learning Representations, 2018a.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In Proceedings of the International Conference on Learning Representations, 2018b.
U. von Luxburg. tutorial on spectral clustering. Statistics and Computing, 17(4):395-41 -16, 2007.
Shen Wang, Xiaokai Wei, Cicero Nogueira Nogueira dos Santos, Zhiguo Wang, Ramesh Nallapati, Andrew Arnold, Bing Xiang, Philip S Yu, and Isabel F Cruz. Mixed-curvature multi-relational graph neural network for knowledge graph completion. In Proceedings of the Web Conference, pp. 1761-1771, 2021a.
Xiyuan Wang, Haotong Yang, and Muhan Zhang. Neural common neighbor with completion for link prediction. In Proceedings of the International Conference on Learning Representations, 2024.
Ziming Wang, Jun Chen, and Haopeng Chen. EGAT: Edge-featured graph attention network. In Artificial Neural Networks and Machine Learning -International Conference on Artificial Neural Networks, pp. 253 264. Springer, 2021b.
Larry Wasserman. Topological data analysis. Annual Review of Statisties and Its Application, 5:501-532, 2018.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1): 4-24, 2020.
Feng Xia, Ke Sun, Shuo Yu, Abdul Aziz, Liangtian Wan, Shirui Pan, and Huan Liu. Graph learning: A survey. IEFF Trans AT, 2(2): 127, 2021.
15

---

Published in Transactions on Machine Learning Research (07/2025)
Fangzheng Xie. Entrywise limit theorems for cigenvectors of signal-plus- matrix models with weak signals. Bernoulli, 30(1) ):388 418, 2024.
Zhiwen Xie, Guangyou Zhou, Jin Liu, and Xiangji Huang. ReinceptionE: relation with joint local-global structural information for knowledge graph embedding. In Proceediiggs of the Annual Meeting of the Association for Computational Linguistics, pp. 5929 5939, 2020.
relation-aware aware inception network
Wenhan Xiong, Thien Hoang, and William Yang Wang. DeepPath: reinforcement learning method for knowledge graph reasoning. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 2017.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proceedings of the International Conference on Learning Representations, 2018.
Zuoyu Yan, Tengfei Ma, Liangcai Gao, Zhi Tang, and Chao Chen. Link prediction with persistent homology: An interactive view. In Proceedings of the International Conference on Machine Learning, pp. 11659 11669. PMLR, 2021.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling, Advances in Neural Information Processing Systems, 31, 2018.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In Proceedings of the International Conference on Machine Learning, pp. 7134-7145 2019.
Jiaxuan You, Tianyu Du, and Jure Leskovee. ROLAND: Graph learning framework for dynamic graphs. Tn Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2358 2366, 2022.
Muhan Zhang and Yixin Chen. Link prediction based on graph noural networks. Advances in Neural Information Processing Systems, 31, 2018.
Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning on graphs: A survey. IEEE Transactions on Knowledge and Dala Engineering, 34(1):249 270, 2020.
Qi Zhao and Yusu Wang. Learning metries for persistence-based summaries and applications for graph classification. Advances in Neural Information Processing Systems, 32, 2019.
Zhenyu Zhao, Yuzhou Chen, and Liang Du Modeling and classification of ev charging profiles utilizing topological data analysis. In IEEE Transportation Electrification Conference & Erpo, pp. IEEE, 2023.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. AT open, 1:57-81, 2020.
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. Advances in Newral Information Processing Systems, 34:29976-29499, 2021.
Afra Zomorodian and Gunnar Carlsson. Computing persistent homology. In Proceedings of the Annual Symposium on Computational Geometry, pp. 347-356, 2004.
A Derivation of Estimators under Undirected Network Models
Under the SBMs, to estimate B, we note that for 1 5 <
By Eiswisn P.zZu En. Psg EisidjeN Zi
Σ Em=a.,,= Pv. NN -1)
and
B
N₂
16

---

Published in Transactions on Machine Learning Research (07/2025)
Thus, it is reasonable to estimate B by the following B (Bql)ssosIsk.
Bul.ght Ei Aij Nr
Eg.=q. Aij N,( - 1)
and
Bgg
Under the DCSBMs, to estimate B, we note that
Σ
P
0. 0, N,
9:-4
8)=1
Hence, we can estimate B by B = (Ba)IsaIsK.
Byt = EisiisN Aij AzZigZzi
- Asg NaNi
EISHFINN ZinZ,i
To estimate 0, we note that
0, E.
= = Σ N₂ By.
P
Pi
k 95=k
j=
where we used Byik- g, Egg (N No). Hence, estimate O2 by Ó defined as
No. E Aij
0:
Σg Σ Arj
where Ng. is the number of nodes the estimated community 9i. We also denote é =diag(0) (0).
B Proofs and Lemmas
For simplicity, we provide the proofs for the undirected network models SBMs and DCSBMs. In most cases, the proofs for the directed network models follow similarly. We highlight the differences if any.
B.1 Proof of Lemma 5.6
Proof. First, we consider the strong consistency of community detection. Under the undirected network model SBM, the strong consistency of 2 follows from the Corollary II.1 in Su al. (2019) and Assumptions 5.1 5.3. Under the undirected network model DCSBM, the strong consistency of Ž follows from Corollary III.1 in Su et al. (2019), where they considered the regularized DCSBMs with regularization parameter т. In our set-up, = 0. Assumptions 5.1 5.4 imply that Assumptions 11-13 in Su et al. (2019) are satisfied. Hence the result follows. Under the directed network model ScBM, the strong consistency derived as that under the SBM. The strong consistency of Z mainly depends on the success of Theorem 11.1 in Su al. (2019). In particular, Assumption 5.5 (with the notation simplified to the ScBMs) implics that the rows of the population singular vectors V (v:) Raxk* satisfies that
Ý is similarly
n 1/2/111 12 2 C>0
for oi + 99 and some constant C > 0 (see details in Theorem 2.1 in the first version of Su et al. (2019)). Hence, Theorem II.1 in Su et al. (2019) holds and the strong consistency of 2 follows from Corollary II.1 in Su et al. (2019). Under the directed network model DCSeBM, the strong consistency of Ý is similarly derived as that under the DCSBM. The strong consistency of 2 mainly depends on the success of Theorem I1I.4 Su et al. (2019). In particular, Assumption 5.5 implies that L2 normalized rows of the population singular vectors (w:) T=* satisfies that
Vi
12 2 C' > 0
10:112
1oy
17

---

Published in Transactions on Machine Learning Research (07 (075))
for of + 9j and some constant C' 0 Rohe et al. (2016). Hence, Theorem III.4 in Su et al. (2019) holds and the strong consistency Ž follows from Corollary III.1 Su et al. (2019).
The strong consistency of 0 (resp. Ov and 0²) under DCSBMs (resp. DCScBMs) follows from Theorem III.6 in Su et al. (2019). Actually, the strong consistency Z (resp. Y and 2) and Assumption 5.4 implics Assumption 15 in Su et al. (2019). And the result follows by noting that the minimal average degree in our set-up P(N)).
Now we proceed to show the strong consistency of B. The proof holds for both undirected and directed network models. For simplicity, use the notation under undirected network models. For eN to be selected, we have
I
sup 159CIKK
BBt Bul CN eN i.o.
sup 15qeIsK
Byt Byi 2 EN i.o., sup 1 + gs} =0 +P
sup USigN
1 + a)>0 >0 i.o.
ISIEN
Ay N₁
Ps N₂
S P
sup 1sq<lcK
Σ
E i.o.
(13)
9: 9.000
where the last inequality follows from the strong consistency of Jt's. To make the RHS of equation 13 zero, it suffices to show that
Σ
Σ
Σ
Ps N
)) 2 EN
<
(14)
N₂
K= ==IKS
9:
for some eN. To this end, use the Bernstein inequality. | < N,N; and
Define (
Ag
have E(X(0)) 0,
N₂N1
E Aij P.)
P.(1 P.j)
B₁(1 - BB))
Σ -
[(((())=
E
E
NZN
N?N?
Ng
=
9
Then by the Bernstein equality, have
1 12
P(I Σ
x(0 2 <N) S
B1 B.t)
+
ON
N₂
NN,N
Choosing EN C maxxl
V
B B.t) No
Vlog N O V plgg N
it is easy see that
N
Vplog
Ba((1 BBi) x
XCN,
N
where the inequality follows from Assumption 5.2. We thus have
PP(
Σ
x S
St ク
for some constant a > As a result, equation 14 met because fixed K. Finally, we obtain the strong consistency of B that
By Byl Oa.. Vologg N
sup
15ecisk
N
The proof for q I goes similarly by noting that can represent Bry B the following summation of independent terms,
Aij -P;
B Bgg
Σ
Ny(N,, - -1)/2'
9=
18

---

Published in Transactions on Machine Learning Research (07 (07/202) /025)
Hence omit it.
B.2 Proof of Theorem 5.8
Proof. We first provide the proof for the more general model DCSBMs, and then present the results for SBMs special case.
It is casy to see that
P P P= Ô2BZTó P= -- 0) 00
1 11 111 P.
(15)
Now we proceed to bound 1. We have by Lemma 5.6 that
sup 0. 0,1 Oa.s. (log N/(N))),
and thus
sup 0 s sup 0 -0,1 + sup 0 = O.... (1)
by noting Assumption 5.4. By Eqs. 8 and 9 in Lemma 5.6, We can easily have
sup B Bad a.s. sup Ba., I sup B Byss, sup B
9:.95
9..35
9..93
Vplog N
= =
Oa... (p) = (p.
N
where the last equality is implied by Assumption 5.2. As a result.
sup ISUS
14)g = sup [(diag 0
diag
ISiJEN
sup 10, B,) B.9, 0,1 Oa. (log N/N). ISiJEN
(16)
Similarly, we can show that
sup ISUJNN
(11) = 2lo.. N/N).
(17)
It remains bound 111 P. Noting
- P P ZB
(18)
and the boundness of by Assumption 5.4, we only need to bound ÂB2T ZBZT. It is easy to observe that
İB2 ZBZ (Ž 2) + ZB(2 2) + 2 B)
= E + Eg + Ez.
For Eg, we further have
E3 11B-BB2
Z) + (2 ZB B)2 + - Z)T.
Combining the above two facts, obtain
2B2T - ZBZ = - 1
(19)
where
R. + ZB Z)T + -- Z)T.
19

---

Vplog Published in Transactions on Machine Learning Research (07 2025)
By the strong consistency of Z,
2 - 2 = 0, 0.8.,
(20)
and thus =as.. remains bound
Z(B Z. Noting
(2 - B) = (B -B)
and equation 8 in Lemma 5.6, we have
Vplog N
sup,, (Z - 1b; = -a.s.
N
As result, we have Combining equation 16, equation 17 with equation 21, we have for DCSBMs that
Vplog N
sup (11I - P)ij Oa.s. ISÚJNN
(21)
N
P. P.yl = Oa. log
sup
)
(22)
IEiJEN
N
While for SBMs, the error terms and I/ exactly zero. Hence,
P.j - Pijl = Oa...
sup ISiJEN
N
The proofs for the directed network models ScBMs and DCSeBMs go similarly provided that Assumption 5.5 is additionally required for Lemma 3.6.
B.3 Proof of Theorem 5.8
Proof. Recall equation 15, can decompose P P by 1+I1+111----- P. For DCSBMs, have shown in the proof of Theorem 5.7 that su))(1) Oa.s. (log N/N) and sup (IT)gg) Oa.s. (log N/N). For SBMs,
11 0.
We now show the asymptotic normality of III- - P, for which by equation 18, equation 19 and equation 20, we only need to show the asymptotic normality of Z(B -B)tt. Note that
(Z B) (B- B) B By
provided that gi q and gj By strong consistency of 2, we have ÿ. =a.. Pi and N, =a.. Ng for all E [N] and q [K]. So for q 1,
Aú Ps
By Byl
Σ
NgN,
9s 0
We he Lindeberg-Fon Feller Central Limit. Theorem to derive the limit distribution of B Byt- First, note that
A P
Aij
b = Var( Σ
Σ Var
N₂
N₂
9: 9:
9: 9.=..
Σ
(1 P.j)/(N223
Byi(1 B,i)((N,M)
We only need to show
E(( Ag Psj (T
A Ps N₂N
Σ
2 (8N)) +
N₂Ni
9.
20

---

Published in Transactions on Machine Learning Research (07 (07/2025)
for every <> 0, which holds sufficiently if Au Au-PPs) N₂
S csN. Indeed,
Ai P N₂
11/2 EVBBll Bai Byi)/N,N.
N
Therefore, by central limit theorem, we can obtain in SBMs that.
(( BBt) N(O, Bar Byl)
for + 1. When =1, considering the dependency of Aij and Aji, we consider the following halved term
A, Psj
Bag BRg =
Σ
(23)
N₂ - 1)/2'
9,
Similarly, we can derive
N(Bm BBy) N(0,
2B qq
B
For DCSBMs, thus have that
B Ban (1 Bonas) 87)
N(P P+E); - N(, 0¹
Tg Fg
with Egj- = Oa.s. (log N/N) and Øi # gj. and
B Bug BR.n.) 0?)
N(P - P+ + N(O, 20
Tg
with Fúj = (log (log and gi =
The proofs for the directed network models ScBMs and DCScBMs are similar except that when g = =g. the directed networks do not involve dependency of pairs Aij and Aja like in (23), hence the constant 2 in the asymptotic variances replaced by 1.
B.4 Auxiliary lemmas
Lemma B.1 (Bernstein inequality). Let X1...., XN be independent zero-mean random variables. Suppose that [Xa] < M almost surely, for all i. Then, for all posilive I,
N
2
P
Σ
2
x
2
< exp
ΣN' | + Mt
C Notes, Notations, and Flowchart
The notations are summarized in Table 6.
D Additional Experiment Settings
For all 5 datasets (i.e., Cora-ML, Cileseer, PubMed, Photo, and Computers), SBM-TNN is trained by the Adam optimizer with the Cross Entropy Loss function. Additionally, all baseline methods are initialized with the parameters suggested in their respective works, we carefully tune the parameters during training to ensure that the bascline model achieves optimal performance. Here we treat the resulting topological features dimension (connected components) and (cycles) (i.e. Q 2). For link prediction, perform extensive
21

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Table 6: A summary of the notes and notations.
Notation
Definition
Notations for undirected network models:
N
Number of communities
91 E {1,..., K}
Community assigmment of node
NE Ty = NA/N
Number of nodes within the k-th community
Proportion of nodes in the k-th community
Z (0, 1JNXK
Membership malrix
B TR Kxk
Block probability matrix
O DENN
Node propensity vector
4 = diag 11..................... ON}
Node propensity matrix Edge probability matrix Population degree of node i
P = OZBZ E RNXN
d: 14=> -EE= Poj
D (iag(d),,... dN)
Population degree matrix
P AE 10. 13
Network sparsity
Symmetric Adjacency matrix
d = Σ Aij
Degree of node
D = diag d
dx)
Degree matrix
I= D 1/2 AD 1/2
Graph Laplacian
Notations for directed network models:
N
Number of nodes
K*(K*)
Number of row (column) clusters
of E {1,
K"Y E (1,..., K*1
Row (column) cluster assignment of node
(N)
Number of nodes in the 1 (A*th) row (column) cluster Proportion of nodes in the k"th (k*th) row (column) cluster Row (Column) membership matrix
Y E (0, 1 T == NE/N)
" = NO N
IZE (0.IN
B E R k" <*))
Block probability matrix
8" EERN EEEEE ERR
Node propensity vector for sending (receiving) edges
2 = diag 0 (() = diag (
Node propensity matrix for sending (receiving) edges
P = Y : E E RRNX NXN
Edge probability matrix
df = Σ (dj = E P..)
Population out-degree (in-degree) of node i
D = diag d" d (D= = diag df. .... d
Population out-degree (in-degree) matrix
Network sparsity
AE (0, NNNNN
Asymmetric adjaconcy matrix
Ad( = Σド Ajo)
Out-degree (in-degree) of node
D diag 26
3d \D= diag di dz))
Out-degree (In-degree) matrix
L (D*)
1122
Graph Laplacian
grid search for learning rate among (0.001, 0.008, 0.01, 0.1), the dropout rate among
the number of hidden units among E (8, 16, 32, 64, 128), and the model is trained for 5,000 epochs with early stopping applied when the metric (i.e., validation loss) starts to drop. For KG completion, we set the batch size be 512 and the model is trained for 500 epochs, and we perform an extensive grid search for learning rate among (0.00001, 0.001, 0.01, 0.1).
E
Additional Experiments
To better illustrate the benefits of involving community-level and topological information for link prediction tasks, we incorporate the SBM-TNN framework into ROLAND architecture You et al. (2022) for dynamic link prediction (in mean reciprocal rank (MRR)) on Bitcoin- OTC data. As shown in Table 7, found that ROLAND SBM-TNN achieves 17.80% performance gain the ROLAND.
22

---

Published in Transactions on Machine Learning Research (07/2025)
GNN
MLP
Structural
go
GNN
MLP
GM
GNN
Gxc
(I) Mixed-up Graph Construction
SBM
Go
(II) Stochastic Block Model
POOL
CNN
(III) Multi-view TGNN
Figure The overall architecture of SBM-TNN.
Table Performance comparison on Bitcoin-O1F
Method
Mean Reciprocal Rank (MRR)
ROLAND
0.2203 0.0167
ROLAND + SBM-TNN (ours)
0.2595=000026
We have also conducted additional experiments for link prediction by comparing with the Edge-featured Graph Attention Network (EGAT) model Wang et al. (2021b). From the below table, we observe that SBM-TNN always achieves the highest AUC-ROC score with average relative gain of 3.78%.
Table 8: Performance comparison on link prediction.
Method
Cora-ML
Citeseer
PubMed
EGAT
92.3 0.6
93.8 = 1.0
94.8 - 0.3
SBM-TNN (ours)
96.240.2
97.140.3
98.2+00.1
23


Reviews:
[{"review_id": "l2t0wnxQSR", "reviewer": "Reviewer_LToV", "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": "The Introduction section needs some revision as many of the references are much older or even outdated work. Most of the references are 2020 or earlier. Furthermore, several important references are also missing on much more recent and relevant GNN models. \n\n[WWW 2021] Mixed-Curvature Multi-Relational Graph Neural Network for Knowledge Graph Completion. In Proceedings of the Web Conference 2021 (WWW '21). Association for Computing Machinery, New York, NY, USA, 1761–1771. https://doi.org/10.1145/3442381.3450118\n\n[IEEE 2021] \"Bi-Level Attention Graph Neural Networks,\" in 2021 IEEE International Conference on Data Mining (ICDM), Auckland, New Zealand, 2021, pp. 1126-1131, doi: 10.1109/ICDM51629.2021.00133.\n\nThe authors summarize their contributions, however it would help to more clearly specify how their contributions are different from existing works e.g., the GCN component has already been proposed previously. It is not so clear that there is novelty in the work. \n\nFurthermore, even in the space of knowledge graphs, works have investigated using non-Euclidean geometric space to model the topological structures of cycles and hierarchy. For example, here is a recent work the authors should reference for relevance:\n[KDD 2022] Dual-Geometric Space Embedding Model for Two-View Knowledge Graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD '22). Association for Computing Machinery, New York, NY, USA, 676–686. https://doi.org/10.1145/3534678.3539350\n\nI am curious why the authors do not consider modeling the different topologies in non-Euclidean spaces? \n\nExperiment results are comprehensive and show non-trivial gains over the state-of-the-art.", "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": "The authors propose a novel stochastic block model (SBM)-aware topological neural networks, called SBM-TNN. It uses SBMs to infer the latent community structure of nodes from graph structures and persistent homology to encode higher-order information. Authors also theoretically study the entry-wise bound and asymptotic normality of the estimated edge probability matrix to quantify the uncertainty in statistical inference of the edge probabilities. The paper further shows various experiments with the proposed model for the link prediction task.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see above section for details.", "broader_impact_concerns": "N/A There are no concerns regarding the ethical implications of this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UTpF7AHqPT", "reviewer": "Reviewer_rmD1", "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": "Strength:\n1. The paper is overall easy to follow.\n2. The authors provide theoretical connections between the proposed ScBMs/DCScBMs and existing SBMs/DCSBMs.\n\nWeakness:\n1. The motivation of this paper is based on an over-claimed justification. The authors claim that existing GNNs 'can not efficiently learn the edge probabilities based on topological structures (i.e., higher-order interactions) and node features', which is absolutely over-claimed. There are many works that have the same motivation. Specifically, most of the generative GNNs are based on this motivation: the embeddings are related to topological structures and features, the edges probability is modeled by Bernoulli distribution related to the node embeddings. I suggest the authors catch up with the generative GNNs for better motivation.\n2. The authos propose two variants of existing methods SBMs/DCSBMs, namely ScBMs/DCScBMs.However, the model structure is highly similar to exitsing works while the major difference lies in the multi-view part. However, the multi-view part is manually designed and I did not understand why it is necessary and effective. Currently, this combination seems like the ensemble learning. As a result, the technical contribution should be further highlighted.\n3. The experiments are not extensive. Only a few tiny graphs are evaluated while the inference of this model is time consuming and the authors should provide both theoretical and experimental evaluation. Furthermore, as I mentioned, the baselines should include many generative GNNs to verify the effectiveness of the proposed method.", "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 proposes a stochastic block model-aware topologcal neural networks, named SBM-TNN. The proposed method is designed to learn the probabilities between pairs of nodes, which is acheved by replacing the discrete edges between nodes with probabilities. However, this idea has been widely used in the generative graph neural networks where the node embedding, clustering and edge properity are naturally correlated.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The motivation of this paper should be corrected, the authors should discuss the difference between generative GNNs and the proposed method.\n2. The technical contribution should be highlighted and clearly discussed, the current version is not very encouraging to me.\n3. The experiments should be more comprehensive.\n4. The paper written should be improved. The equations are indexed randomly, which should be carefully managed.", "broader_impact_concerns": "No ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Bb3V9Nwu8K", "reviewer": "Reviewer_nftF", "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. Novel Integration of Concepts\nThe integration of SBM-based community detection with topological neural networks is novel and addresses key limitations of GNNs, such as difficulty in capturing higher-order structure and uncertainty.\n\n2. Strong Theoretical Backbone\nThe paper provides rigorous statistical analysis of the edge probability estimator, including:\n\nEntrywise bounds on the estimated probability matrix.\n\nAsymptotic normality, enabling uncertainty quantification.\n\nThese are rare in deep learning-oriented graph papers and strengthen the theoretical contribution.\n\n3. Empirical Performance\nShows consistent and significant improvements over strong baselines across citation networks (Cora-ML, Citeseer, PubMed), Amazon graphs, and KGs (FB15k-237, WN18RR, NELL-995).\n\nAblation studies validate the individual contributions of SBM and topology modules.\n\n4. Multi-view Topological Learning\nUses multiple filtration functions (centrality scores) to build topological summaries, offering a richer representation space.\n\n5. Solid Benchmarks\nThe model is compared against a wide array of modern GNN and KGC baselines (e.g., SEAL, TLC-GNN, NBFNet).\n\n\nWeaknesses:\n\n1. Clarity & Overcomplexity\nThe method section is dense, with multiple architectures (SBM estimator, mixed-up graph, persistence images, GNN layers). The pipeline could benefit from a clear diagram or step-by-step illustration.\n\nSome notations are introduced with minimal explanation (e.g., Z, B̂, Θ̂), and repeated definitions for similar models (SBM, DCSBM, ScBM, DCScBM) could be streamlined.\n\n2. Lack of Baselines Using Edge Probabilities\nNo direct comparison is made with other models that use probabilistic or edge-weighted input graphs, which would contextualize the benefit of using SBM-derived probabilities.\n\n3. Efficiency / Scalability Discussion\nWhile some complexity is discussed (e.g., persistent homology at 0- and 1-dimensions), there’s little exploration of scalability on larger graphs, e.g., OGB datasets (aside from a brief mention of ogbl-wikikg2). No training time, GPU usage, or memory benchmarks are provided.\n\n4. Assumption Dependence in Theory\nThe strong theoretical guarantees (entrywise bounds, normality) rely on strong assumptions (e.g., balanced clusters, fixed K, bounded degree heterogeneity), which may limit real-world applicability.", "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 SBM-TNN, a novel graph neural network framework that integrates Stochastic Block Models (SBMs) and topological descriptors (via persistent homology) to improve link prediction tasks on graphs and knowledge graphs. The key contributions include:\n\n1) Incorporation of SBM-estimated edge probabilities in GNNs to better capture community structure.\n\n2) Use of topological signatures (e.g., persistence images) to encode higher-order information.\n\n3) Theoretical guarantees: Provides entrywise error bounds and asymptotic normality for the edge probability matrix.\n\n4) Demonstrates state-of-the-art results on both graph and knowledge graph link prediction tasks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Visualization: Add a high-level diagram summarizing the architecture: SBM estimation, topological embedding, mixup graph, GNN  link prediction.\n\n- Baselines: Include or mention models that use probabilistic edges or uncertainty, like variational GNNs or Bayesian GNNs.\n\n- Efficiency Metrics: Report time/memory vs baselines to show practical benefits of using SBM-based priors.\n\n- Model Generalization: Discuss whether this framework could extend to dynamic graphs, heterogeneous graphs, or non-relational data.", "broader_impact_concerns": "None concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)